Линейное программирование.

Линейное программирование (ЛП) является наиболее глубоко исследованной областью математического программирования. Большинство практически решаемых задач оптимизации относится именно к задачам ЛП. Основные идеи ЛП были разработаны во время второй мировой войны Дж. Данцигом (США) для планирования военных операций. Основная процедура ЛП - симплекс – метод опубликован в 1947 г.

1. Основные идеи и результаты.

Пример 1.

Фирма производит две модели А и В книжных полок. Их производство ограничено поставкой сырья (высококачественных досок) и временем машинной обработки. Для каждой модели А требуется 3 м², а для В – 4 м² досок. Фирма может получить от поставщиков до 1700 м² досок в неделю. Для каждой модели А требуется 12 мин. машинного времени, а для В – 30 мин. В неделю можно использовать 160 часов машинного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?

Чтобы сформулировать задачу математически, обозначим через количество выпущенных за неделю полок модели А, а за - модели В. Задача состоит в том, чтобы найти такие наилучшие и , которые максимизируют еженедельную прибыль.

Целевая функция еженедельной прибыли

(1.1)

Согласно классической теории оптимизации функция принимает экстремальные значения в точках, где обращаются в нуль ее производные или на границе области определения. Рассмотрение производных в данном случае не дает результата, поскольку

и

и никаким выбором и нельзя обратить эти производные в нуль. Чтобы увеличить функцию P, надо увеличивать и . Но (и в этом суть проблемы) значения и не могут быть увеличены неограниченно. Эти значения ограничены лимитами на доски и машинное время .

Поскольку и выражают еженедельный объем выпускаемых полок, то они не могут быть отрицательны, т.е.

, (1.2)

Ограничения на сырье и машинное время:

(для досок) (1.3)

(для машинного времени).

Задача состоит в том, чтобы найти значения и , удовлетворяющие условиям неотрицательности (1.2) и ограничения типа неравенства (1.3) и максимизирующие целевую функцию (1.1). Это типичная двумерная задача ЛП. Целевая функция является линейной функцией своих переменных. Ограничения на эти переменные тоже линейны.

Двумерные задачи ЛП допускают графическое решение (рис. 1.1).

Рис. 1.1

Заштрихованная область ОАВС, содержащая точки, для которых соблюдаются условия (1.2) и (1.3), называется областью допустимых решений (допустимой областью). Область ограничена отрезками положительных полуосей (условия неотрицательности) и прямыми и . Стрелка на каждой границе рис.1.1 указывает, с какой стороны выполняется ограничение. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы найти решение, максимизирующее значение .

Штриховыми линиями на рис.1.1 изображены прямые и , обозначенные a и b соответственно. Эти прямые параллельны и представляют собой две линии уровня функции со значением 0 и 800 соответственно. Ясно, что значение функции возрастает по мере удаления линий уровня от начала координат в положительном квадранте. Направление возрастания указывает градиент , , т.е. вектор с компонентами , перпендикулярный линиям уровня и направленный от начала координат.

Линией уровня с наибольшим значением , имеющей хотя бы одну общую точку с допустимой областью, является прямая с , проходящая через вершину В. На ней принимает значение 1400. Точка В, в которой , соответствует оптимальному решению задачи. Поскольку в точке В пересекаются прямые, эти значения могут быть получены как решения системы уравнений

Следовательно, максимальная прибыль составляет 2*300+4*200=1400. При оптимальном решении оба ограничения превращаются в равенства, что означает полное использование ресурсов – сырья и машинного времени.

Рассмотренная задача может быть расширена до трех и более моделей и соответствующего количества неотрицательных переменных. Могут быть введены дополнительные ограничения, связанные с возможностями рынка, упаковкой и т. д. В этом случае задача по-прежнему заключается, в максимизации линейной функции от нескольких неотрицательных переменных с линейными ограничениями в форме неравенств.

Общая задача линейного программирования состоит в максимизации (или минимизации) линейной функции

(1.4)

от вещественных переменных , , …, , удовлетворяющих условиям неотрицательности

(1.5)

и m линейным ограничениям

(1.6)

. . . . . . . . . . . . . . . . . . . . . . . . . .

Среди ограничений могут одновременно встречаться знаки , = и . Значения , , предполагаются известными. В матричных обозначениях задача может быть представлена следующим образом:

максимизировать (минимизировать) функцию

, (1.7)

где

(1.8)

(1.9)

и

– вектор-столбец ,

а

– вектор-строка ,

– вектор-столбец ,

– матрица .

Индекс 0 в векторе и в матрице указывает на то, что это начальные значения. Смысл этого станет ясен ниже.