7.8. Двойственные задачи линейного программирования
Таблица 7.22 Цены Запасы Продукция на ресурсы сырья Я, П2 пп «1 <*\\ <*\2 <*\п и2 ... ^22 <*2п ит Q ml Я ml <*тп Прибыль с Cl С2 сп единицы продукции
Запишем в общем виде экономико-математическую модель задачи об использовании ресурсов. Для этого введем переменные Хр у = 1 — количество продукции у-го вида. Тогда ограничения на сырье запишутся в виде
а\\х\ + а\2х2 + — +ах#л<>ах\
021*1 + «22*2 + - +*2ІЛІ ? «2; (7.55)
ат\х\ + *«2*2 + - +*І»І/Л, ^ ат• Целевая функция, определяющая максимум прибыли, имеет
вид
Zmax = с\х\ + С2Х2 + ••• + W (7-56)
xj>qj = т7л.
По этим же исходным данным сформулируем задачу по предприятию № 2.
Допустим, предприятие № 2 решило закупить все ресурсы, которыми располагает предприятие № 1. В этом случае предприятию № 2 необходимо установить оптимальные цены на эти ресурсы, исходя из следующих условий:
общая стоимость ресурсов для предприятия № 2 должна быть минимальной;
за каждый вид ресурса предприятию № 1 надо уплатить не менее той суммы, которую это предприятие может получать при переработке данного вида ресурса в готовую продукцию.
Обозначим цены, по которым предприятие № 2 покупает ресурсы у предприятия № 1, через uh і = 1,/и. Запишем экономико- математическую модель для предприятия № 2 с учетом вышеуказанных условий 1) и 2).
Целевая функция, определяющая минимальную суммарную стоимость ресурсов, имеет вид
Апіп = <*\Щ + + - + атит- (7.57)
В соответствии с условием 2) запишем систему ограничений:
аххих + а2Хи2 + ...
+ ат1ит>сх;ах2их + а22и2 + ... + ат2ит > с2;
а\пи\ + а2пи2 + ... + > число неизвестных одной задачи равно числу ограничений другой задачи; матрица коэффициентов системы ограничений получается одна из другой путем транспонирования; неравенства в системах ограничений имеют противоположный смысл; свободные члены системы ограничений одной из задач становятся коэффициентами целевой функции другой задачи, коэф-фициенты целевой функции превращаются в свободные члены ограничений; целевые функции в задачах имеют противоположный смысл: в первой - шах, во второй - min. Задачи линейного программирования, обладающие пятью указанными формальными признаками, называются симметричными. Одна из них называется основной, а другая — двойственной. В линейном программировании кроме симметричных двойственных пар существуют несимметричные двойственные пары, которые имеют следующий вид: основная задача ахххх + ах2х2 + ... + аХпхп = Ьх; : (7.59) ат\х\ + ат2*2 + — + атпхп = Ьт> ^шах = СХХХ + С&2 + ... + с„хЛ; (7.60) xj > 0, j = Т77Ї; двойственная задача ^тах = Ьхух + bjy2 + ... + Ь„ут; (7.61) й\\У\ + а2\Уг + - + ^ С\> : (7.62) + а2пУ2 + - + втпУт * сп- ЭТИ задачи отличаются от симметричной пары двумя особенностями: ограничения задачи (7.59)—(7.60) выражены уравнениями вместо неравенств; в задаче (7.61)-(7.62) отсутствуют условия неотрицательности переменных yh і = I, т. Общее правило построения двойственной пары. К пяти признакам, сформулированным ранее, необходимо добавить следующие: в исходной задаче ограничения неравенства следует записывать со знаком >, если целевая функция стремится к min, и со знаком <, если целевая функция стремится к шах; каждому ограничению неравенства исходной задачи соответ-ствует в двойственной задаче условие неотрицательности переменных у і > 0; каждому условию равенства соответствует переменная у; без ограничения на знак, и наоборот: неотрицательным переменным хк из основной задачи в двойственной задаче соответствуют ограничения неравенства, а неограниченным по знаку переменным соответствуют равенства. Пример 7.15. Дана следующая система: І*! +2х2 +*з [2хх +Х3 >4; хх >0\х2> 0; х3 > 0; ^min = х1 + х2 + ху Проверяем условие: целевая функция стремится к min, а знак неравенства должен быть >. Так как в прямой задаче в системе ограничений два неравенства, то в двойственной будет две переменных их и и2, причем их > 0, и2 > 0. Целевая функция ^тах = 9их + 4W2. Учитывая, что целевая функция на шах и в прямой задаче хх > 0; х2 > 0; х3 > 0, то система ограничений запишется в следующем виде: щ+1и2<\\ 2их <1; их+и2<1. Пример 7.16. Имеем систему
-2X2 +х3 +3^4 -2х5 = 6,
2Х] +3х2 "2*3 ~*4 +х5 ^ 4,
+Зх3 -4х5 ? 8,
хх >0;х3> 0; х5 > 0; х2 и х5 не имеют ограничения знака; Zmin = х\ - 2*2 + х3 - х4 + *5- Так как целевая функция на min, то в исходной задаче ограни-чения неравенства должны иметь знак >. Умножим второе неравенство системы на —1: -2хх - За:2 + 2х3 + х4 - х5 > - 4. В прямой задаче число ограничений равно 3, значит, в двойственной будет три переменных: их; и2\ и3. Так как и2 и ы3 соответствуют неравенствам, то и2 > 0; ы3 > 0. Параметр их соответствует равенству, поэтому их — переменная без ограничения знака. Число ограничений в двойственной задаче равно 5, так как в прямой задаче пять переменных, в том числе первое, третье и пятое ограничения будут неравенствами, потому что они соответствуют неотрицательным переменным, а второе и четвертое ограничения будут уравнениями, так как соответствуют переменным без ограничения знака. Запишем двойственную задачу с учетом вышеиз-ложенного: целевая функция ^тах = - 4"2 + 8"3; ограничения их — 2и2 + ы3 < 1; -2их - 3и2 = -2; их + 2и2 + Зы3 < 1; 3 их + и2 = -1; —2их — и2 — 4и3 < 1. Решение симметричных двойственных задач. Сформулируем без доказательства теорему, справедливую для любых двойственных задач. Теорема (первая теорема двойственности). Если одна из двойственных задач имеет оптимальное решение, то и другая его имеет. Причем экстремальные значения целевых функций совпа-дают. Если же в одной задаче целевая функция не ограничена, то двойственная ей задача противоречива. Запишем в общем виде прямую и двойственную задачи линей-ного программирования: 1) прямая задача: ахххх + аХ2х2 + ... : (7.63) ат\*\ + ат&2 + - + amrPn ^ ат\ Zmax = СЛ + + ... + CJCn\ xt > 0; / = ГГл; 2) двойственная: апих + a2lu2 + ... 4- amlum > cx\ \ (7.64) alnu{ + a2nu2 + ... + amnum > cn\ Lmin = Wi + + - + amum\ Uj > 0, / = 1,/w. Преобразуем задачи (7.63) и (7.64) к виду, допускающему применение симплекс-алгоритма. Для этого введем выравнивающие переменные ypj = 1,/и в прямую задачу и v,, / = 1,« — в двойственную задачу: прямая: ух = а{ - (апх{ + а12х2 + ... + а1пхп); I (7.630 Ут = от - (ат1хх + ат2х2 + ... + атпхп); Zmax = 0 - (~C\Xi - <%> - ... - cjcn); двойственная: vi = —с\ - (-ацЩ - а21и2 - ... - ат1ит)'9 : (7.640 vn = ~~сп - (~а\пи\ - а2пи2 - ... - атпит)\ Lmm = 0 " (-«1^1 - Wl " - ~ <*mUm). Построим для задач (7.63') и (7.64') общую симплекс-таблицу (табл. 7.23), причем эта таблица имеет дополнительные столбец и строку для двойственной задачи: Таблица 7.23
Двойственная Vl v2 v„ Anin
задача С *2 свободные
Б члены
-"і аХ2
-«2 У2 а}х ар «2 я а?
Ут <*т\ ^/пя
7 ^т ах ~С\ -С2 -с* 0
Задачи, представленные в общей симплекс-таблице (табл. 7.23), решаются обычным симплекс-методом, алгоритм которого приведен выше. Сформулируем признаки оптимальности двойственной пары задач: планы X— (хх, х2, хп) и ?/= (uXi w2, ит) оптимальны, если Zmax(X) = Lmln(U); решения Х= (xb х2, ..., хп) и t/ = (wj, w2, ..., wm) оптимальны, если все произведения сопряженных условий для этих решений равны 0. Запишем следующие сопряженные условия: группа: (ах - ахххх - аХ2х2 - ... - аХпхп) их = 0; (<*т ~ <>т 1*1 ~ Я/я2*2 - - ~ "т = группа получается, если умножить нахь х2, ..., хп выражения для базисных переменных двойственной задачи: (аххих + а2Хи2 + ... + атХит - сх) X! = 0; (ахпих + а2пи2 + ... + атпит - сп) хп = 0. Пример 7.17. По исходной задаче построить двойственную и найти оптимальное решение обеих задач. Zmax = ~~3*1 + 5Х2 + Х3 + Х4; Зх! + 8Х2 + х3 + х4 < 50; 5хх — 4Х2 — х3 + х4 > 14; ху>0,у=ГТ4. Согласно общему правилу составления двойственных задач запишем: 3их + 5и2 > -3; 8их - 4и2 > 5; их- и2 > 1; их + и2 > 1; Anin = 50«! + 14W2; их и и2 > 0. Решим задачи в единой симплекс-таблице. прямая задача: вводим выравнивающие переменные х5, х6: х5 = 50 — (3xj + 8*2 + *з + x4)i х6 = 14 — (5xj - 4х2 - + х4); ^тах = 0 — (3xj — 5х2 — х3 — х4); двойственная задача: вводим в левую часть ограничений выравнивающие перемен-ные Vj, v2, v3, v4 со знаком «—»: V! = 3 - (-3их -5w2); v2 = - 5- (-8«! +4k2); v3 = - 1 - (-ні + к2); v4 = -1 - (u{ - w2); ^rnin = 0 - (—50wj - 14w2). Итак, составим таблицу, внешний контур которой образует двойственную задачу, внутренний - прямую задачу (табл. 7.24): Таблица 7.24
Б* Vl v2 v3 V4 -^min
С** С Б *2 *з х4 свободные члены
-щ -и2 *5 *6 3 5 1 -1 1 1 50 14
Свобод-ные члены z 3 -5 -1 -1 0
*Б - базисные переменные. **С — свободные переменные. Т
Будем работать по симплекс-методу, но так как записанная в последней строчке функция стремится к максимуму, то в этой строчке мы будем искать наименьший отрицательный элемент. Построим итоговую таблицу (табл. 7.25):
Б* Vl Щ v3 V4 Lmin
С* С Б *5 *3 Х4 свободные члены
-v2 -w2 *2 *6 3/8 1/8 1/8 1/8 52/8 4/8 -4/8 12/8 50/8 39
Свобод-ные члены z 39/8 5/8 -3/8 -3/8 Т 250/8
Б* Vl V2 v4 ^rnin
С* С Б Хь *2 Х4 свободные члены
-v3 -w2 *3 *б 3 18 1 8 1 4 | 2 1 50 64
Свобод-ные члены 7 ^тах 6 13 0 Т 50
Б* Vl Щ V2 "2 Lmin
С* С Б *1 Х2 *6 свободные члены
-v3 -v4 *3 х4 -1 1/2 6 -1/2 4 1/2 2 1/2 18 32
Свобод-ные члены 7 ^тах 6 13 0 50
Итак, мы получили итоговую таблицу (табл. 7.25), в последней строчке которой нет отрицательных элементов, следовательно, за-дачи решены: прямая задача X = (0; 0; 18; 32), Zmax = 50; двойственная задача U ~ (1; 0), Zmin = 50. Проверим полученное решение на оптимальность: условие 1) выполнено: Z (X) = L (U) = 50. Для выполнения условия 2) составим произведения сопряжен-ных условий: XjVJ = X! (3 - (-3их - 5и2)) = 0 (3 - (-3 -1-50» = 0; X2V2 = х2 (- 5 - (-Щ + 4и2)) = 0 (- 5 - (-8 • 1 + 4 • 0)) = 0; x3v3 = х3 (-1 - (~их + и2)) = 18 (-1 - (-1 + 0)) = 0; X4V4 = х4 (-1 - (~их - и2)) = 18 С— 1 — (-1 - 0)) ^ 0; ихх5 = их (50 - (Зх! + 8х2 + х3 + х4)) = 1 (50 - (3 • 0 + 8 • 0 + 18 + + 32)) = 0; "2*6 = и2 О - (5*1 ~ 4х2 - х3 + х4)) = 0 (14 - (5 • 0 - 4 . Итак, оба условия выполняются, значит, полученный план — оптимальный. Рассмотренную задачу примера 7.17 можно решить иначе. Для этого необходимо: решить прямую задачу обычным симплекс-методом. Решение получим следующее: Zmax = 50; X = (0; 0; 18; 32); составить произведение сопряженных условий и приравнять их 0: xxvx = хх (3 - (-3их - 5и2))\ x2v2 = х2 (- 5 - (-8их + 4и2))\ X3V3 = х3 (- 1 - (~их + и2))\ X4V4 = х4 (- 1 - (-их - и2))\ иххЗ = их (50 - (Зхх + 8Х2 + х3 + х4)); w2*6 = w2 (14 - (5хх - 4Х2 - х3 + х4)). Подставим вектор X в записанные условия, тогда будем иметь: 18 • (— 1 — ( —их + и2)) = 0; 32 . (-1 _ (-их - и2)) = 0. После преобразований получим: 1 + U{ + и2) = о; \ + (- их- и2) = 0. Откуда их = 1; и2 = 0, Lmln = 50, так как Zmax = Z,min, значит, задача решена верно.