Раздел 6. Задачи скалярной оптимизации, линейные, нелинейные, дискретные
6.3 Линейное программирование
Линейное программирование – это набор математических и вычислительных инструментов, позволяющих найти конкретное решение системы, которое соответствует максимуму или минимуму какой-либо другой линейной функции. Линейное программирование – это фундаментальный метод оптимизации, десятилетиями применяемый в областях, требующих большого объема математических вычислений. Эти методы точны, сравнительно быстры и подходят для множества практических приложений.
Пример №1. Производственная задача.
Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?
Обозначим: Х1 - число изготовленных стульев, Х2 - число сделанных столов. Задача
оптимизации имеет вид:
45 Х1 + 80 Х2 → max ,
5 Х1 + 20 Х2 ≤ 400 ,
10 Х1 + 15 Х2 ≤ 450 ,
Х1 ≥ 0 ,
Х2 ≥ 0 .
В первой строке выписана целевая функция - прибыль при выпуске X1 стульев и X2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных X1 и X2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если X1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то X1 положительно. Но невозможно представить себе отрицательный выпуск - X1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны. Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения X1 , а по вертикальной оси ординат - значения X2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (X1 , X2) объемов выпуска в виде треугольника (см. рис. 1).
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось X1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось X2, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется
Аналогичным образом можно изобразить и ограничения по труду (см. рис. 2).
Таким образом, ограничения по труду также изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось X1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось X2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.
Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).
Таким образом, множество возможных значений объемов выпуска стульев и столов (X1 , X2 ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис. 3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая
- это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений
5 X1 + 20 X2 = 400 ,
10 X1 + 15 X2 = 450 .
Из первого уравнения: 5 X1 = 400 - 20 X2 , X1 = 80 - 4 X2 . Подставляем во второе уравнение: 10 (80 - 4 X2) + 15 X2 = 800 - 40X2 + 15 X2 = 800 - 25 X2 = 450, следовательно, 25 X2 = 350, X2 = 14,
откуда X1 = 80 - 4 х 14 = 80 - 56 = 24. Итак, четвертая вершина четырехугольника - это (24, 14).
Надо найти максимум линейной функции на выпуклом многоугольнике. (В общем случае линейного программирования - максимум линейной функции на выпуклом многограннике, лежащем в конечномерном линейном пространстве.) Основная идея линейного программирования состоит в том, что максимум достигается в вершинах многоугольника. В общем случае - в одной вершине, и это - единственная точка максимума. В частном - в двух, и тогда отрезок, их соединяющий, тоже состоит из точек максимума.
Целевая функция 45 X1 + 80 X2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 X1 + 80 X2 = 2200 проходит между прямыми ограничений 5 X1 + 20 X2 = 400 и 10 X1 + 15 X2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).
Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.
Двойственная задача. Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу:
45 Х1 + 80 Х2 → max ,
5 Х1 + 20 Х2 ≤ 400 ,
10 Х1 + 15 Х2 ≤ 450 ,
Х1 ≥ 0 ,
Х2 ≥ 0 .
И двойственную к ней:
400 W1 + 450 W2 → min ,
5 W1 + 10 W2 ≥ 45,
20 W1 + 15 W2 ≥ 80,
W1 ≥ 0,
W2 ≥ 0.
Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W1 и W2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W1 и W2 называют "объективно обусловленными оценками" сырья и рабочей силы.
Пример №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.
На рис. 4 ради облегчения восприятия четыре прямые обозначены номерами (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).
Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых). Область допустимых значений параметров (К, С) можно назвать "неограниченным многоугольником". Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого "многоугольника". Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина - это точка пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений:
0,10 К + 0,25 С = 1,00 ,
1,00 К + 0,25 С = 5,00 .
Из второго уравнения К = 5 - 0,25 С, из первого 0,10 (5 - 0,25 С) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 = 40/9. Итак, А = (40/9; 20/9).
Прямая (3) на рис. 4 - это прямая, соответствующая целевой функции 3,8 К + 4,2 С . Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.
Двойственная задача, построенная по описанным выше правилам, имеет приведенный ниже вид (мы повторяем здесь и исходную задачу об оптимизации смеси, чтобы наглядно продемонстрировать технологию построения двойственной задачи):
Исходная задача:
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 .
Двойственная задача:
W1 + 5 W2 + 400 W3 → max ,
0,1 W1 + 1,10 W2 + 110 W3 ≤ 3,8 ,
0,25W1 + 0,25 W2 + 120 W3 ≤ 4,2 ,
W1 ≥ 0 ,
W2 ≥ 0 ,
W3 ≥ 0 .
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация двойственных переменных: W1 - "стоимость" единицы вещества Т, а W2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W1 , W2 , W3 - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).