≥ 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).
Следовательно, область допустимых значений параметров ( К, С ) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (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) – это прямая, соответствующая целевой функции 3,8 К + 4,2 С . Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А , через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.
Двойственная задача, построенная по описанным выше правилам, имеет приведенный ниже вид (мы повторяем здесь и исходную задачу об оптимизации смеси, чтобы наглядно продемонстрировать технологию построения двойственной задачи):
3,8 К + 4,2 С → min, W 1 + 5 W 2 + 400 W 3 → max,
0,10 К + 0,25 С ≥ 1,00, 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8,
1,00 К + 0,25 С ≥ 5,00, 0,25 W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2,
110,00 К + 120,00 С ≥ 400,00, W 1 ≥ 0,
К ≥ 0, W 2 ≥ 0,
С ≥ 0. W 3 ≥ 0.
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т. е. оба числа равны 236/9. Интерпретация двойственных переменных: W 1 – «стоимость» единицы вещества Т, а W 2 – «стоимость» единицы вещества Н, измеренные «по их вкладу» в целевую функцию. При этом W 3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W 1 , W 2, W 3 – это т. н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).
Планирование номенклатуры и объемов выпуска. Вернемся к организации производства. Предприятие может выпускать автоматические кухни (вид кастрюль), кофеварки и самовары. В табл.2 приведены данные о производственных мощностях, имеющихся на предприятии (в штуках изделий).
При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо
