Задачи оптимизации при принятии решений

3.2. ЗАДАЧИ ОПТИМИЗАЦИИ  ПРИ ПРИНЯТИИ РЕШЕНИЙ

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

Среди оптимизационных задач  в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х₁ - число изготовленных стульев, Х₂ - число сделанных столов. Задача оптимизации имеет вид:

45 Х₁ + 80 Х₂  → max ,

5 Х₁ + 20 Х₂ ≤ 400 ,

10 Х₁ + 15 Х₂ ≤ 450 ,

Х₁   ≥ 0 ,

Х₂ ≥ 0 .

В первой строке выписана целевая  функция - прибыль при выпуске Х₁ стульев и Х₂ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х₁ и Х₂ . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х₁ = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х₁ положительно. Но невозможно представить себе отрицательный выпуск - Х₁ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс  откладывать значения Х₁ , а по вертикальной оси ординат - значения Х₂ . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х_{1 ,} Х₂) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения  по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта  примыкающей к началу координат  зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства  на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на

 

изготовление столов, то будет изготовлено 20 столов. Для  всех точек внутри треугольника выполнено  неравенство, а не равенство - материал останется.

Аналогичным образом можно  изобразить и ограничения по труду (рис.2).

0

Таким образом, ограничения  по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта  примыкающей к началу координат  зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства  на равенство. Прямая пересекает ось Х₁, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х₂, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает  рабочих рук, а для производства 30 столов есть рабочая сила, но нет  материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество  возможных значений объемов выпуска  стульев и столов (Х₁ , Х₂ ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений 

5 Х₁ + 20 Х₂ = 400 ,

10 Х₁ + 15 Х₂ = 450 .

Из первого уравнения: 5 Х₁ = 400 - 20 Х₂ , Х₁  = 80 - 4 Х₂ . Подставляем во второе уравнение:

10 (80 - 4 Х₂) + 15 Х₂ = 800 - 40Х₂  + 15 Х₂ = 800 - 25 Х₂ = 450,

следовательно, 25 Х₂ = 350, Х₂ = 14, откуда Х₁ = 80 - 4 х 14 = 80 -56 =24.

Итак, четвертая вершина  четырехугольника - это (24, 14).

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

Целевая функция 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 унции К	Содержание в 1 унции С	Потребность
Вещество Т	0,10 мг	0,25 мг	1,00 мг
Вещество Н	1,00 мг	0,25 мг	5,00 мг
Калории	110,00	120,00	400,00
Стоимость 1 унции, в центах	3,8	4,2

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

На рис.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 , W₁ + 5 W₂ + 400 W₃ → max , 

0,10 К + 0,25 С ≥ 1,00 , 0,1 W₁ + 1,10 W₂ + 110 W₃ ≤ 3,8 ,

1,00 К + 0,25 С ≥ 5,00 , 0,25W₁ + 0,25 W₂ + 120 W₃ ≤ 4,2 ,

110,00 К + 120,00 С ≥ 400,00 , W₁ ≥ 0 ,

К ≥ 0 , W₂ ≥ 0 ,