XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 19
Текст из файла (страница 19)
Из этих неравенств следует, что сХ* = (Х*) с < (Х*) А У* = (У') АХ* < (Я*) 6 = 6 У*. Так как Х* и х," — оптимальные решения прямой (3.36) и двойственной (3.37) задач линейного программирования, то, согласно теореме 3.8, выполнено равенство сХ' = 6 Е*. Поэтому (Х*) (А Я* — с ) = О, (У ) (АХ' — Ь) = О. Учитывая обозначения (3.35), заключаем, что т и и ПЪ г,*(Яапьха — 6) =0= ~! х~(~ а!ах; '— са), 1=! а=! '=г 3.5.
Двойственнал задача линейного программирование 137 откуда и следуют равенства (3.42), (3.43). Действительно, в соответствии с формулировками прямой (3.36) и двойственной (3.37) задач а;ьха < 6„ Е *- а=! Е а;аг," > сы и г,* (~~ аеьха а=! х~( ! а;ая,". Остается лишь учесть, что если сумма неположительных (нео- трицательных) слагаемых равна нулю, то равно нулю каждое из этих слагаемых.
и Пример 3.16. Рассмотрим задачу линейного программи- рования 1(х!, хг,хз) = 5х! + 12хг+4хз -+ шах; х!+2хг+хз < 10, 2х! — хг+Зхз = 8, ха > О, 6=1,2,3. Считая эту задачу прямой задачей линейного программирова- ния, преобразуем ее в соответствии с (3.33): г (хг,хг,хз) = 5х!+12хг+4хз -+ и!ах; х! + 2хг+ хз < 10, 2х! — хг+Зхз < 8, — 2х!+хг — Зхз < — 8, х! )~ 0~ хг ~ )0~ хз )~ О. 3. СИМЛЛЕКС-МЕТОД 138 (3.45) Таблица 3.13 Базисные пере- менные Ите- Значе- ыз ыз из из Таблица 3.13 1 2 2 — 1 1 3 5 12 4 — 1 0 0 0 — 1 0 0 0 — 1 Базисные переменные Ите- рация Значение У! Уз 1 — 3 ыв ыв 0 0 -1 2 — 1 — 1 10 8 8 Ув Уз Ув 21 0 — 1 0 -10 -8 — 1 0 — 1 0 — 1 0 0 0 -1 0 1 2 — 1 — 1 0 — 1 12 — 7 3 ыв -1/3 -1 1/3 О 1/3 1 1 0 — 1/3 1/3 7/3 0 0 2/3 -1/3 22/3 о 8/3 Ув Уз уз 5 40 -22 22 — 10 — 1 -4/3 0 4/3 3/7 4/7 40/7 0 0 7/3 40/3 1/7 5/7 -1/7 2/7 -3/7 — 1/7 О 0 0 — 1 1 0 0 -32/3 — 1 0 0 ыз 0 1/7 1 1 0 — 2/7 3/7 О 1/7 1/7 0 5/7 22/7 О 26/7 Уз Уз уз 3/7 368/7 1/7 5/7 -22/7 — 26/7 — 1 0 0 -4/7 -40/7 3/5 2/5 29/5 — 368/7 3/7 0 -7/5 2/5 — 1/5 1/5 — 1/5 -2/5 0 0 Π— 1 1 0 0 1/5 1 1 0 — 2/5 2/5 0 1/5 -1/5 О 7/5 ыз ыз 12/5 0 26/5 Уз Уз Уз 0 274/5 0 -26/5 0 -12/5 Π— 2/5 -29/5 — 3/5 -274/5 О 0 Двойственная ей задача, согласно (3.34), примет вид /з(гззхг,гз) = 10г1+8гг — 8хз — > тзп; гг+2лг — 2лз) 5, 2г1 — гг+ гз ) 12, г1+Згг — Згз)~ 4, г1 ) О, гг ) О, гз ) О.
Для решения прямой задачи линейного программирования полагаем ув = хю й = 1,2,3, вводим новые переменные модели ую й = 4,5,6, искусственное переменное ут и используем симплекс-метод при неизвестном начальном базисном решении (см. 3.3). Результаты вычислений представлены в табл. 3.12. На первой итерации ут перестает быть базисным переменным, целевая функция д вспомогательной задачи (3.25) достигает 3.5. Диойстиеннал задача линейного программироиаиии 139 своего максимального значения, и, начиная со второй итерации, в симплекс-таблице вычеркнуты столбец, соответствующий дт, и строки, соответствующие уз.
Итак, оптимальному решению Х' = (26/5 12/5 0) прямой задачи линейного программирования (3.44) соответствует значение целевой функции / = 274/5. Для решения двойственной задачи линейного программирования (3.45) полагаем юь = гю /с = 1,2,3, вводим новые переменные модели ю4, пза, юе, три искусственных переменных аз7, юв, озв и (см. 3.3) используем симплекс-метод при неизвестном начальном базисном решении (табл. 3.13). Целевая функция вспомогательной задачи в данном случае имеет вид З.о. Двойственнал задача линейного программирование 141 140 3. СИМПЛЕКС- МЕТОД чз = — шт — шв — ьзв.
По мере того как искусственные переменные перестают быть базисными, соответствующие столбцы симплекс-таблицы вычеркиваются, равно как и строки, соответствующие оо, вычеркиваются при достижении р минимального значения. Из табл. 3.13 следует, что на третьей итерации найдено начальное базисное решение двойственной задачи линейного программирования, которое оказалось ее оптимальным решет нием У* = (29/5 0 2/5) .
Заметим, что наличие допустимых решений означает, что (см. теорему 3.8) для оптимальных решений выполняется равенство (3.40): сХ'= 274/5= 5 У*. На практике наличие ограниченного оптимального решения одной из задач линейного программирования в системе „прямая — двойственная" практически всегда означает наличие ограниченного оптимального решения и у двойственной ей задачи. Это объясняется равноправием задач в системе „прямая — двойственная" и позволяет (см. замечание 3.5) по известному оптимальному решению прямой задачи находить оптимальное решение двойственной ей задачи.
Заметим также, что наличие неограниченного оптимального решения прямой задачи линейного программирования, соответствующего бесконечному значению ее целевой функции, означает (см. теорему 3.6), что множество допустимых решений двойственной ей задачи пусто. Если известно оптимальное решение одной из задач линейного программирования в системе „прямая — двойственная" и оно найдено с использованием симплекс-таблиц, то оптимальное решение двойственной ей задачи уже известно и может быть записано без дополнительных вычислений.
Пример 3.17. В табл. 3.12, описывающей решение задачи примера 3.16, на третьей итерации числа, расположенные на пересечении строки, обозначенной — /, и столбцов переменных у4, уя, уе, соответственно равны — 29/5, О, — 2/5, а оптимальное т решение двойственной ей задачи имеет вид У* = (29/5 О 2/5) . Аналогично в табл. 3.13 на последней итерации числа, расположенные на пересечении строки, обозначенной — 5, и столбцов переменных ша, озя, озе, соответственно равны — 26/5, — 12/5, О, а оптимальное решение прямой задачи имеет вид Х' = = (26/5 12/5 0) . й1 Теперь остановимся на зкономической интерпретации переменных в задаче линейного программирования, являющейся двойственной по отношению к задаче распределения ограниченных ресурсов (см.
задачу исследования операций (2.3), задачу 2.13 и пример 3.11). Рассматривая задачу распределения огра; ниченных ресурсов как прямую задачу, будем считать, что она записана в виде (3.33) или (3.36) с неотрицательными параметрами, а двойственная ей задача представлена в виде (3.34) ил и (3. 37) . Пусть /* = сХ' — значение целевой функции задачи распределения ограниченных ресурсов, соответствующее оптимальному решению Х*, а У* = (г,*, ..., г' ) — оптимальное решение двойственной ей задачи. В этом случае, согласно теореме 3.8, имеет место равенство б;г;.
~=1 В соответствии с экономической интерпретацией /' — максимально возможная прибыль (в денежных единицах), 5; общее количество т-го ресурса (в принятых единицах). Поэтому значение г,* должно выражаться в денежных единицах на единицу измерения т-го ресурса (т = 1, та). Таким образом, переменное г, двойственной задачи отражает ценность" т-го ресурса.
В связи с этим переменные двойственной задачи нв; зывают еще тттекевымц ценами или скрытттымтт доводами. Двот7стттвеккые кеременкые, т,е. переменные двойственной задачи, могут быть использованы для определения приоритетов используемых ресурсов в соответствии с их вкладом в прибыль, выражаемую значением целевой функции. Параметр 143 3. СИМПЛЕКС- МЕТОД Вопросы и задаче Вопросы и задачи п етируют как норму потребления 1-го ресурса в й-м аъ интерпретиру производственном процессе, а сумма а1ьх1 + аиьхи " эффект за счет Й-го производственопределяет экономический эф е т го п о есса вычисленный с учетом теневых цен. Ограничения, входящие в двойственную задачу, гарантирую р у пропорциональность экономичес и про о к х эффектов отдельных производственных процессов затраче у енным снлням, если имеет место оптимальный режим функцион р и ования всей системы.
ь, этих условиях исключаются варианты допустиьолее того, при э мых решении, не опра правданных с зкономической точки зрения. Дадим экономическую интерпретацию р тео еме 3.9, суть которой выражается равенствами ~ . (3.42) (3.43,: а) если й-й производственный процесс является строго нех ен ге 1= 1, т, соответствувыгодным с точки зрения теневых ц Х'= (х' ...
х',, то интенсивющих оптимальному решению, =,х1 ность его использования х* должна быть равна нулю, т.е. б) если в оптимальном решении 1-й ресурс используется не полностью, то его теневая цена должна быть равна нулю, т.е. ь,<о) ~ (я=0). /сж1 В заключение отметим, что объем вычислительных затрат, связанных с нахождением оптимального р ешения любой задачи линейного программирования, определи е еляется в основном не числом переменных модели и, а числом р ог аничений т. А так как любую задачу линейного программирования можно рассматривать в системе „прямая — двойствен ал р н " и ешение любой из них симплекс-методом автоматически приводит к решению второй, то решать нужно ту задачу, у которой меньшее число ограничений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
