§ 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом

(0

(2)

jf1 ^^ Су

при условиях

ТІ

fi -

xv ^ 0t v = 1, n.

Fi = Z Куи

прн условиях

m

afii/ytl ^ v — I7n,

1*^=1

ytl ^ 0, ft = T, k.

Задача (4)-(6) называется двойственной по отношению к исходной {прямой) задаче (1)-(3). Задачи (І)-(З) н (4)-(6) образуют пару задач, называемую в линейном программировании двойственной парой.

Двойственная задача по отношению к прямой составляется по следующему правилу,

3. Двойственная задача решается на минимум, если прямая — на максимум, н наоборот.

Коэффициентами целевой функции двойственной задачи служат свободные члены системы ограничений яря мой задачи.

Матрица коэффициентов системы ограничений двойственной задачи поду чается из матрицы коэффициентов системы ограничений прямой задаЧн путем транспонирования (замены строк столбцами, а столбцов — строками).

Система ограничений двойственной задачи записывается в виде Неравенств противоположного смысла неравенствам системы ограниче-ний прямой задачи.

Число переменных в двойственной задаче равно числу ограничений п прямой задаче.

Свободные члены системы ограничений двойственной задачи являются коэффициентами целевой функции прямой задачи.

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

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

Рассмотрим пример.

Для задачи, состоящей в определении максимума функции F - = + + Ъх-л при условиях

2нТі + + 5,гз ^

+ 4x2 + бяэ ^ 61, 4л;і + 2t2 + Zxz < XI, х\ >0, Х2 > 0, ІЗ ^ 0

составить двойственную задачу.

Решение Число переменных в двойственной задаче равно числу ограничений прямой задачи, т.е.

Следователь ко, дізойственная задача по отношению к исходной состоит о нахождении минимума функции F\ = 35yi + 6ly2 + 11 при условн-

ЇУі + Уі > її + 6у2 4- Зуг Р З,

Уі 2 0, У2> 0, уз^О.

При решен ни задач симплексным методом предполагалось, что система ограничений задана в виде системы неравенств вида а свободные члены неотрицательные {Ь ^ О). Двойственный симплексный метод позволяет решать задачи, s которых система ограничений задана в виде системы неравенств вида (^0), либо смешанного вида ^ 0), либо — (5і, = 0), а свободные члены любого знака.

Пусть задана задача, записанная в форме основной задачи линейного программирования, для которой среди векторов А^ (см. §64), составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных векторов, а среди свободных членов уравнений имеются отрицательные.

Пусть X = (0; 0; ...; 0; ftij h2\ bm) есть решение системы уравнений дайной задачи. Это решение не является планом рассматриваемой задачи, так как среди его компонент имеются отрицательные числа. Если это решение удовлетворяет признаку оптимальности» 'го это решение называется псевдопланом. Для того, чтобы псевдоплан стал оптимальным планом, достаточным условием является условие неотрицательности всех базисных переменных.

Нахождение решения задачи двойственным истодом включает следующие этапы.

Нахождение псевдоплана.

Систему ограничений исходной задачи приводят к системе неравенств вида Напомним, что неравенства вида (>0) приводят к неравенствам вида л у тем умножения обоих частей неравенства на (—1). Затем от системы неравенств переходят к системе уравнении, вводя неотрицательные дополнительные переменные. Дополнительные переменные берут за базисные. Получив- первый псевдоплан, составляют первую симплеЕ(сную таблицу также, как прн решении задачи симплексным методом.

Проверка оптимальности псевдоплана.

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

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

Определение направляющих столбца и строки.

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

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

602 Линейное программирование І^л. Х

Задача. Составить и решить двойственную задачу к задаче, рассмотренной в § 65.

Решение. Используя правило составления двойственной задачи, получим: найти минимум функции Fi = 1450?/: + 700т/г + lOSOjte при условия* 50з/1 + + ЗЬу2 ^ 50)

I 25у, + lQjte +¦ ? 45, 1 + + 15да ^ 40, L У: > 0, > 0, г/з ^ 0,

Решаем эту задачу двойственным симплексным методом

Умножим обе части неравенств на (-1), приведём систему от нера^ венств вида (^0) к системе неравенств айда «0).

50yL - - 35і/з +Ул = -50, 25у\ - Юуз - lSj/з = -45, 2Ьуі -20У2 - 15уз +Ув = -40.

Составляем первую симплексную таблицу.

В таблице Т-1 получен псевдоплан, так как условие оптимальности в индексной строке выполняется, в столбце свободных членов имеются отрицательные значении (-50; —45; —40), наличие которых показыва-ет. что полученный псевдоплан неоптимальный. Так как в строках с отрицательными свободными членами имеются отрицательные элементы (кроме свободных членов), то система ограничений задачи совместна и задача имеет решение (если бы они отсутствовали, то задача была бы неразрешима).

За направляющую строку выбираем строку, соответствующую переменной так как j — 50J > (f — 45J, I —401).

Вычисляем элементы строки в (на нули и положительные числа деление не производим). 0 *= шш(29; 20; 30) = 20, которое соответствует столбцу переменной уз- Разрешающий элемент равен (—35).

В следующей таблице (Т-2) в состав базисных переменных войдёт переменная у2, а выйдет Выполняем вычисления до тех пор, пока не будет выполнен признак оптимальности.

Пятый план (таблица Т-5) является оптимальным, так как все базисные переменные положительные, и го индексной строке выполня-ется признак оптимальности.

Таким образом, план двойственной задачи равен

П = (|i 0; 0; 40; 0; Б) , Fmia т =26X0.

Сравнивая симплексные таблицы, определяющие оптимальные пла-вы прямой и двойственной задач, видим, что коэффициенты индексной строки в оптимальном плане прямой задачи являются значениям* переменных оптимального плана двойственной задачи. Коэффициенты индексной строки о оптимальном плане двойственной задачи являются значениями переменных оптимального плана прямой задачи. При этом минимальное значение целеьоЙ функции двойственной задачи равно максимальному значению целевой функции прямой задачи.

Установим сопряжённые пары переменных прямой н двойственной задач:

K^X^xq —» 40,0,5; 9/5,0,0;

УиУ2,Уъ -* 40,0,5; 0/5,0,0.

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

Т-1 Біззічсньіс ные Св&бсщчые переменные VI п уа V4 Уъ t/e я VI -гю -50 t-SS| -35 1 0 G -45 -25 -10 —15 0 1 0 -94 vt -40 —25 —20 —15 0 0 1 -09 F, 0 -И5С1 -700 -10S0 0 О 0 -3200 0 ТПІҐІ 29 20 30 — — —

1

Т-2 SE 10

т 10

у. 1 1 1 0 0 1G9 35 Ж 315 7 ! Т5П

1 " 7 0 —5

і 2 7 1 0 320 7 ЭЙ SO 7 25

Т 0 5 4 0 1 17 7 Fi 1000 -450 0 -350 0 0 ISO 9 тіл 42 70 70 — —

Ї

т-з V2 a

3 0 1 1

3 1

15 2 15 0 19 У1 43 15 1 0 . 7 15 1 7Я 7 75 0 64 15 Vs G5 3 0 0 10

3 ?

a 1

3 1 S3 3 F] 2290 0 0 ^140 -8 —A2 0 2100 e mln — — — 12 — —

г

СО 4

Т-4

Т-5 !

№ 1 0 1 0 0 1

10 Г--1

1 ...JL<1 1 а VI 2 J 0 3

5 0 2 1

25 80 2Ь ил 2 0 0 -5 і і

~ 2 3 " 2 53

2 Fi 2550 0 0 -180 -м -12 2313 0 тпі:і — — — — — 120 f 3/е 5 0 -10 0 0 -J ї Б Ш 9 ] 2 Б 0 і 0 № 25 W4 40 0 -IS -5 ] 0 19 Fx 2610 0 -120 -JfiO 0 0 2252 О ІЇ1ЇП

Замечания,

Если Xjt есть некоторый план прямой задачи, a Yin произвольный план двойственной задачи, то F(X^) ^-Fi(itii), т, е. значение целевой функции прямой задачи при плане Xjl всегда не превосходит значения целевой функции двойстве! іной задачи при плане Ym.

Если прямая задача имеет оптимальный план, то и двойственная задача имеет оптимальный план.

Если F(X) = J*i(Y*), то X есть оптимальный план прямой задачи, a Y оптимальный план двойственной задачи

ЕСЛИ целевая функция прямой задачи (1)-{3) не ограничена сверху (F —юо); то двойственная задача (4)-(6) решения не имеет.

Если целевая функция двойственной задачи (4)-(6) не ограничь на снизу (і*1] —+ —оо), то прямая задача решения не имеет.

Каждая из задач двойственной пары является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой.

Задание І.

Задача I. Найти минимум функции F\ — llfidj/i + 560^ + 8%з при условиях

- 40у, Н- 28у2 + 28у3 ^ 40, 20У1 + 8yi + 12у3 ^ 36, 20У1 + 16У2 + 12уз ^ 32, Vi ^ О, > 0, yz ^ 0,

F"liri ^ Fi(Y6) = 2088, Гб = 0; 0; 32; 0; 4).

2 Найти минимум функции Fx = SlC%i + 9000у2 +250у3

при условиях ( , -г лгі . гл ^

f + I00y2 f 50у3 > 70.

+90у2 + 50ш ? 70,

90г/! + 150уй + Юуз ^ 60,

У\ > 0, уъ ^ 0, з/з ? О,

Задача 3. Найти минимум функции Fj =» 1740уі + 840уг + 12б0у3

«р* условиях , 60^+4^ + 42^60,

ЗОтл + \2уъ + 18уз ^ 54, ЗОуі + 24У2 + 18Ш > 48.

FFUl = Fi(YB) = 3X32, tt - (}ї * 4$; 0; б).

Задача 4. Найти минимум функции Ft — ЬАуі -I- 63У2 при условиях f Па . n '

4Уі + Sift + Уз ^ 14,

+ Sift ^ 5, Vi ^ 0, y2> 0, j/з ^ 0.

FTln = - Ю8, Г4 = (0; 1; 9; 0; 0; 0).

Таблиць: к задаче 1,

Т-І

Т-2 Оаэнсные перемен-ные Свободные переменные У1 уг Ї4 Ъга їв S У4 -40 -40 f-58| -23 1 0 0 —135 1/5 -3G -20 -8 -12 0 1 0 -75 VB -32 -20 —12 0 О I -79 Fi 0 -11GQ -660 —S40 с 0 0 —2560 О ШІП 29 20 30 -0 — — і Уг 10 7 10

У 1 1 1 0 0 135 2& Уа 172 .[ GCC1 п. 2 І 0 255 7 -у: и — 4 7 7 Уо 64

Т 20 У О 4 0 І IS 7 Fi 800 -360 0 -280 -20 0 0 НО О тіл ¦ 42 - 70 70 — —

60G Jhпрограммирование jJfj^X

і

Т-І

Таблицы к задаче 2 Базисные перемен-ные Соободиис переменные Hi уг УЗ У'і .Iff У6 S3 У* -ТО -ЗО -100 1 -501 І 0 0 У5 -зо -90 -GO 0 1 0 —330 УЄ -ео -90 -150 -10 0 0 і -зо? Ft 0 -8100 -УООО —2500 0 0 0 -196Ш 9 min 270 90 — — — Т

Продолжение на следующей странице 606

т-з V2 8

3 1 0 1 1 1

~І2 1 6 0 1

4 VI 43 15 1 0 7 15 1

Ж) 7 0 17

т Ув 52

з~ 0 0 8 3 FH 1

3 1 -14 Fi 1 532 0 0 -112 -в —42 0 1670] в miri — — — 12 — — 1 Г 02 1 2 0 1 0 0 1 'в LU 1 2 У\ 2 3 0 3 5 0 1 і 20 71 20 УЛ 26 0 0 -4 1 і 3 2 21 Fi 2040 0 -144 0 -46 -12 ІЄЗЄ 0 mlti — — — — — 9G Г Уб 4 0 -a 0 0 1 1 -4 У1 9 Б I 2

5 3 5 0 0 15

Т У4 32 0 —12 -4 1 -2 0 15 Ft 20В8 0 -ее -144 о ^36 0 1790 $ min

уJ 7 5 3 5 2 1 1

50 0 0 249 50 У& 0 0 J0 0 -І 1 0 10 .

5 F1 3500 -6600 -4СС0 0 -50 0 0 -7150 в min 550 7 400

13 — 250 — — т уз 9

із 9 ІЗ 0 1 3

~ 130 0 1

65 129

УЬ 46 13 84 13 0 0 ш

, . 65 ] і

Тз 616 ~ 65 1/2 23 42 1 0 1 0 і ш 65 65 650 130 325 Л 63 900 52200 0 0 570 13 — 400 10 730 13 13 13 13 0 min 4350 47$ 7 11 Т УЗ 17 Й 0 L 0 Л4 3 131 22 11 220 110 У4 ш

зз" 70 11 0 0 I 65 5 66 323 т 23 7 1 г

0 0 1 1 653 № 11 6G0 132 330 1Л O5750 11 41100 11 0 0 0 ^75 11 375 11 13800 11 в mlii і Табг ицы К задачей Базисные пер елей-ные Свободные переменные Уі и уа уч уъ к -60 -60 -42 1 0 0 -203 УЬ -54 —ЗО -18 0 1 0 -113 1/& —48 -зо -24 0 0 1 -119 Pi 0 -1740 -126С 0 0 0 -3840 0 ГҐІІП 29 20 30 j—и_ — — 1

Продолжение на следующей странице 607

Т-2 У2 1CI

7 10

7 I ] 1

~42 0 0 2Ш 42 У* 258 7 7 0 -6 2 7 1 0 -66 96 " 7 30 7 0 6 4 7 0 і -3 1200 -540 0 -430 -20 0 0 220 в min 42 70 70 - — 1 1 У2 8 3 0 1 1

3 1

~ 18 I 0 0 23 13 VI 86 30 1 0 7 15 1

45 7

so 0 77 18 Уъ -20 0 0 4 2

3 1

3 ] 3 Fx 2748 0 0 -168 -8 -42 0 2530 в min — — — 12 — I

? V2 L

2 0 1 0 0 1

12 " r 1 2 2 і 0 3 5 0 1

15 І

30 107 30 39 0 0 -6 1 1

2 3 ~ 2 32 Fl 3060 0 0 —216 0 -46 -12 2786 9 min — — — — — 144 1

3 уа б 0 — 12 0 0 -J і -6 У1 9 5 1 2 5 3 5 0 1

30 0 Ш Vi 48 D -IS 1 ~2 0 23 Л 3132 0 -144 —216 0 -58 Q 2714 0 min

Таблицы к задаче 4

ft Базисное перемен-ные CsiitSwtHbffr переменные -

т V2 уз У* 1 » z У4 —9 -о 0 і 0 " 0 — 26 Уъ —14 QI 0 J 0 -23 № -5 -б о 0 0 ] -13 Fx 0 ¦ 1

—54 —«3 —о 0 0 0 -122 0 "НІЛ —ТГ

1 2 5

а 1 5 — — — г

г : 1М -У СЕН 0 1 . 0 0 -26 м 14 4 5 1 0 -г 0 23 j- -¦¦¦ -1 f w —s 0 0 0 1 -13 f - і ^ 70 -34 0 0' —5 0 -7 • ґПРп 34 а 38 9 — 1 1 —

Т

Т-3 Vi 1 1 1 0 1 іі 0 0 26

0 № (0 0 1 ] 4 9 0 1 103 JM -1 0 м 0 4

D 0 1 13 9 Л 104 0 -4 0 34 9 0 S21 9 9 тіл — і 17

Т — —

Г

Т-4 0 ї 0 0 5 9 0 1 13 9 S3 9 - 0 0 . 1 0 -і 1 10 1 0 1 0 4 9 0 -1 13 9 Р/ 103 0 0 0 -г -5 — 4 97 0 ІТ1ІП

20 Ю, И. Климемко

Задание 2. Решить двойственным симплексным методом следую-щие задачи.

Задача 5. Найти минимум функции F = 5xi -f 12х3 4- 8хз + при условиях ( ^2аїз + зэ + ? 12,

Xi + 4x2 — Зх^ + 8x4 ^ С, —xi — -Нл^з — ?4 ^ — 7, Xfr > О, А; — Т~4.

Решение. Записав исходную задачу я виде: найти минимум функции F прн условиях

-Xj - 2х2 - " 2^4 + xs = -12, -xi - + 3хз- &X4 + Хе — -6, Яі + 5І2 4 -f- Л<1 + х7 = 7,

хк > 0, t = Т77.

Составляем таблицы. Базисные перемен-ные Свободные переменные осі х а ач 3=5 17 ? Хв -12 І-Ч —2 -1 1 0 0 -17 is -6 3 -8 0 1 0 -15 JT7 7 і 5 -1 1 0 0 1 И F 0 -Е -12 -8 -11 0 0 0 -36 в mln & 6 В 11 2 — 43

2 т ?1 Ї2 1 ' 2 1 2 -1 0 0 17 те 6 0 -2 4 -б ] 0 2 Xj -З 0 3 -2 О 1 0 г -3 F 60 0 -2 -3 -5 0 0 49 в nun W — 3/2 ] — — — г - 11 2 L Б ^3 0 1 0 2 1 1 36 0 -20 16 0 -7 1 -6 20 XT 5 0 -3 2 1 0 -і 3 F 65 0 -5 -І 0 —G 0 52 0 mm

Ответ; Fmill ^ = G5; - (2; 0; 0; 0; 36; U),

Задача 6. Найти максимум функции F » 250 — — - - — 2^4 при условиях

Г 2xi + 3x2 ~ + $хЛ ^ 1 2х\ + + — Х4 > 4t 4л;! + 4x2 — 2хз + 2jc4 ^ 8F ^ > 0, —1^4,

Решение, Записав исходную задачу в виде: найти минимум функ цки i^t = 5-Ті + &Х2 + Зз^з + при условиях

' 2ХІ + 3x2 - 2хз + За?4 + ~ $ —2хІ — 6x2 ~ + Я4 + і'о - -4,

1

—4х\ — 4x2 + - + ягт = -8, Хк > О, fr = Т7. Со ста п ля ем таблицы. Базисные перемен-ные Свободные переменные Ї1 IJ їй JET ? 6 2 3 3 1 0 0 ІЗ -4 1 0 1 0 -13 Х7 -В -4 2 - 2 0 0 ] -15 JFI 0 -в -3 0 0 0 -16 (? mtn 5 4 б

л — 1 — т Ї5 -4 -3 1 0 1 0 a 2 1Э 37В -fc 0 0 1 і І2 41 1 - Л «4 4 2 Й 1 О а 1 IS А -а -2 —5 0 0 о -1 f П?ГП і 4 2 7 * Г і

3 — — —

Т

го* 2 0 4 4 0 J -I 1 и 1 7 3 0 1 1 41 \ 2 1 4 4 0 4 8 S 0 0 3 'І Ъ 3 і 0 1

1

4 11

4 Fx 10 0 1

4 17 4 0 0 1

~ 4 0 33 3 в min

Ответ: F= « 10, Fmax - 240 - 10 = 230

Хз - (2; 0; 0; 0; 2; 0; 0)