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

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

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

Впервые такие задачи решались советским математиком Л.В. Канторовичем (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. Ради облегчения восприятия четыре прямые обозначены номерами (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).   

Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (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 ,

С ≥ 0 . W₃ ≥ 0 . 

Минимальное значение в прямой задаче, как и должно быть, равно  максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация  двойственных переменных: W₁ - "стоимость" единицы вещества Т, а W₂ - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W₃ = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W₁ , W₂ , W₃ - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий). 

Планирование номенклатуры и объемов выпуска. Вернемся к организации производства. Предприятие может выпускать автоматические кухни (вид кастрюль), кофеварки и самовары [2]. В табл.2 приведены данные о производственных мощностях, имеющихся на предприятии (в штуках изделий).

 

 

 

 

 

Таблица 2. 

Производственные мощности (в шт.)

	Кухни	Кофеварки	Самовары
Штамповка	20000	30000	12000
Отделка	30000	10000	10000
Сборка	20000	12000	8000
Объем выпуска	Х1	Х2	Х3
Удельная прибыль (на одно изделие)	15	12	14

 

При этом штамповка и отделка  проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем  количестве. А вот сборка проводится на отдельных участках. 

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

Х₁  ≥ 0 , Х₂ ≥ 0 , Х₃  ≥ 0 , (0)

Х₁  / 200 + Х₂ / 300 + Х₃   / 120 ≤ 100 , (1)

Х₁  / 300 + Х₂ / 100 + Х₃   / 100 ≤ 100 , (2)

Х₁ / 200 ≤ 100 , (3)

Х₂ / 120 ≤ 100 , (4)

Х₃ / 80 ≤ 100 , (5)

F = 15 Х₁ + 12 Х₂  + 14 Х₃ → max . 

Здесь: 
(0) - обычное в экономике условие неотрицательности переменных; 
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах); 
(2) - ограничение по возможностям отделки; 
(3) - ограничение по сборке для кухонь;  
(4) - то же для кофемолок; 
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.  

Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно из формулировки задачи линейного  программирования исключить.  

Отметим сразу любопытный факт. Как будет установлено, в  оптимальном плане Х₃ = 0, т.е. самовары выпускать невыгодно. 

Методы решения  задач линейного программирования.

Методы решения задач  линейного программирования относятся  к вычислительной математике, а не к экономике и менеджменту. Однако инженеру, менеджеру и экономисту полезно знать о свойствах  интеллектуального инструмента, которым  он пользуется. 

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

Простой перебор.

Возьмем некоторый многомерный  параллелепипед, в котором лежит  многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х₁ + 5Х₂  ≤ 10, то, очевидно, 0 ≤ Х₁ ≤ 10/2 = 5 и 0 ≤ Х₂ ≤ 10/5 = 2. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед. 

Проведем перебор точек  параллелепипеда с шагом 1/10ⁿ последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10ⁿ.)  

Направленный  перебор.

Начнем с точки, удовлетворяющей  ограничениям (ее можно найти простым  перебором). Будем последовательно (или случайно – с помощью т.н. метода случайного поиска) менять ее координаты на определенную величину ∆, каждый раз  в точку с более высоким  значением целевой функции. Если выйдем на плоскость ограничения, будем  двигаться по ней (находя одну из координат  по уравнению ограничения). Затем  движение по ребру (когда два ограничения-неравенства  переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆. Если необходимо, в окрестности найденного решения проводим направленный перебор  с шагом ∆/2 , ∆/4 и т.д.) 

Симплекс-метод.

Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут  быть применены для решения практически  любой задачи оптимизации. Симплекс-метод  был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит  в продвижении по выпуклому многограннику  ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех  пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл.2.  

Рассмотрим задачу линейного  программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:

F = 15 Х₁ + 12 Х₂  + 14 Х₃ → max .

Х₁  / 200 + Х₂ / 300 + Х₃   / 120 ≤ 100 ,

Х₁  / 300 + Х₂ / 100 + Х₃   / 100 ≤ 100 ,

Х₃ / 80 ≤ 100 .

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

В соответствии с симплекс-методом  введем т.н. "свободные переменные" Х₄, Х₅, Х₆, соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:

Х₁  / 200 + Х₂ / 300 + Х₃   / 120 + Х₄  = 100 ,

Х₁  / 300 + Х₂ / 100 + Х₃   / 100 + Х₅ = 100 ,

Х₃ / 80 + Х₆  = 100 ,

15 Х₁ + 12 Х₂  + 14 Х₃   = F .

У этой системы имеется  очевидное решение, соответствующее  одной из вершин многогранника допустимых значений переменных:

Х₁  = Х₂  = Х₃  = 0, Х₄  = Х₅ = Х₆  = 100,  F = 0.

В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо  только на период летних отпусков. 

В соответствии с симплекс-методом  выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х₁. 

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при  только что выбранной переменной Х₁:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

Выбираем строку из системы  уравнений, которой соответствует  минимальное из всех положительных  отношений. В рассматриваемом примере - это первая строка, которой соответствует  отношение 20000.

Умножим первую строку на 200, чтобы получить Х₁  с единичным коэффициентом:

Х₁  + 2/3 Х₂  + 2/1,2 Х₃   + 200 Х₄  = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х₁, получим 

7/900 Х₂  + 4/900 Х₃  - 2/3 Х₄ + Х₅ = 100/3.

Ту же преобразованную  первую строку умножим на (-15) и сложим со строкой, в правой части которой  стоит F, получим: