Аналогичным образом можно изобразить и ограничения по труду.
Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х 2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство – часть рабочих будет простаивать.
Мы видим, что очевидного решения нет – для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо «совместить» графики, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве.
Таким образом, множество возможных значений объемов выпуска стульев и столов ( Х 1, Х 2 ), или, в других терминах, множество А , задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т. е. выпуклый четырехугольник. Три его вершины очевидны – это (0,0), (45,0) и (0,20). Четвертая – это пересечение двух прямых – границ треугольников, т. е. решение системы уравнений
5 Х 1 + 20 Х 2 = 400,
10 Х 1 + 15 Х 2 = 450.
Из первого уравнения: 5 Х 1 = 400 – 20 Х 2, Х 1 = 80 – 4 Х 2. Подставляем во второе уравнение:
10 (80 – 4 Х 2) + 15 Х 2 = 800 – 40 Х 2 + 15 Х 2 = 800 – 25 Х 2 = 450,
следовательно, 25 Х 2 = 350, Х 2 = 14, откуда Х 1 = 80 – 4 х 14 = 80–56 =24. Итак, четвертая вершина четырехугольника – это (24, 14).
Надо найти максимум линейной функции на выпуклом многоугольнике (в общем случае линейного программирования – максимум линейной функции на выпуклом многограннике, лежащем в конечномерном линейном пространстве). Основная идея линейного программирования состоит в том, что максимум достигается в вершинах многоугольника. В общем случае – в одной вершине, и это – единственная точка максимума. В частном – в двух, и тогда отрезок, их соединяющий, тоже состоит из точек максимума.
Целевая функция 45 Х 1 + 80 Х 2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х 1 + 80 Х 2 = 2200 проходит между прямыми ограничений 5 Х 1 + 20 Х 2 = 400 и 10 Х 1 + 15 Х 2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).
Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.
Двойственная задача . Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или, наоборот, вместо минимума – максимум). Задача, двойственная к двойственной – эта сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа):
45 Х 1 + 80 Х 2 → max, 400 W 1 + 450 W 2 → min,
5 Х 1 + 20 Х 2 ≤ 400, 5 W 1 + 10 W 2 ≥ 45,
10 Х 1 + 15 Х 2 ≤ 450, 20 W 1 + 15 W 2 ≥ 80,
Х 1 ≥ 0, W 1 ≥ 0,
Х 2 ≥ 0. W 2 ≥ 0.
Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т. е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют «объективно обусловленными оценками» сырья и рабочей силы.
Линейное программирование как научно—практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения – системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.
Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912–1986) в 1930–х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910–1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.
Рассмотрим несколько типовых задач линейного программирования.
Задача о диете (упрощенный вариант). Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).
Пищевая ценность рациона (в калориях) должна быть не менее заданной. Пусть для простоты смесь для цыплят изготавливается из двух продуктов – К и С . Известно содержание тиамина и ниацина в этих продуктах, а. также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в табл.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.
Ради облегчения восприятия четыре прямые обозначены номерами (1) – (4). Прямая (1) – это прямая 1,00 К + 0,25 С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С ) лежат выше прямой (1) или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования.
Прямая (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).
