Стратегия социально-экономического развития Омской области

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

Целевая функция 45 Х₁ + 80 Х₂  принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х₁ + 80 Х₂  = 2200 проходит между прямыми ограничений 5 Х₁ + 20 Х₂ = 400 и 10 Х₁ + 15 Х₂ = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14). 

Таким образом, оптимальный  выпуск таков: 24 стула и 14 столов. При  этом используется весь материал и  все трудовые ресурсы, а прибыль  равна 2200 долларам США. 

Двойственная  задача.

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

45 Х₁ + 80 Х₂  → max , 400 W₁ + 450 W₂ → min ,

5 Х₁ + 20 Х₂ ≤ 400 , 5 W₁ + 10 W₂ ≥ 45,

10 Х₁ + 15 Х₂ ≤ 450 , 20 W₁ + 15 W₂ ≥ 80,

Х₁  ≥ 0 , W₁ ≥ 0,

Х₂ ≥ 0 . W₂ ≥ 0. 

Почему двойственная задача столь важна? Можно доказать, что  оптимальные значения целевых функций  в исходной и двойственной задачах  совпадают (т.е. максимум в исходной задаче совпадает с минимумом  в двойственной). При этом оптимальные  значения W₁ и W₂ показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W₁ и W₂ называют "объективно обусловленными оценками" сырья и рабочей силы.  

Линейное  программирование как научно-практическая дисциплина.

Из всех задач оптимизации  задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или  равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции  также линейны. 

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента  с целью оптимизации организации  производства и производственных процессов, например, процессов загрузки станков  и раскройки листов материалов. После  второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал  в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.  

Рассмотрим несколько  типовых задач линейного программирования (см. также [1,2]). 

Задача о  диете (упрощенный вариант).

 Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).

Таблица 1. 

Исходные данные в задаче об оптимизации смеси.

 Пищевая ценность рациона (в  калориях) должна быть не менее заданной. Пусть для простоты смесь для  цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а. также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в табл.1.  

Задача линейного программирования имеет вид:

3,8 К + 4,2 С → min ,

0,10 К + 0,25 С ≥ 1,00 ,

1,00 К + 0,25 С ≥ 5,00 ,

110,00 К + 120,00 С ≥ 400,00 ,

К ≥ 0 ,

С ≥ 0 .

Ее графическое решение  представлено на рис.4. Ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00 К + 0,25 С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (1) или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования.

Рис.4. Графическое решение  задачи об оптимизации смеси. 

Прямая (2) - это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К = 0, прямая (1) проходит через точку (0,20), а прямая (2) - через расположенную ниже точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений

1,00 К + 0,25 С = 5,00 ,

110,00 К + 120,00 С = 400,00 .

Из первого уравнения К = 5 - 0,25 С. Подставим во второе: 110 (5- 0,25 С) + 120 С = 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С, т.е. решение достигается при отрицательном С. Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С точки зрения менеджера они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.  

Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (4) или на ней, как и для прямой (1).