XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 18
Текст из файла (страница 18)
(3.32) При выполнении условий (3.29) — (3.32) третья итерация симплекс-метода является завершающей, и оптимальное решение, найденное при рассмотрении примера 3.11, так же, как и оптимальный базис, остается неизменным. Из примера 3.12 видно, что процедура определения диапазонов допустимых изменений коэффициентов в целевой функции является достаточно громоздкой. Но на практике подобные исследования чаще всего связаны с анализом допустимых изменений сь удельной прибыли сь к-го вида производственной деятельности при неизменности значений всех остальных ее параметров.
В этом случае рассмотренная процедура заметно уцрощается. В частности, для с2 в рассмотренной задаче допустимыми являются изменения от — 2/15 и до 11/5, т.е. при любом с2 из интервала (58/15, 93/15) оптимальное решение задачи линейного программирования, рассмотренной в примере 3.11, остается неизменным. Если четыре числа с2, с2, сз и с4 удовлетворяют условиям (3.29) — (3.31), то на третьей итерации симплекс-разности О, ( — 3 — 5с2 + 7с2 — 2сз)/7, О, ( — 11+ 5с2 — 12сз + 7с4)/7, ( — 13 — 10с2+Зсз)/7, О, (' — 5+с2 — сз)/7 не должны быть положительными, т.е. 128 3. СИМПЛЕКС-МЕТОД < 1(Х) = еХ -+ тах; АХ<Ь, Х>0„; (3.36) прямая задача 1(х1,..., х„) = ~~1 сгхг — 1 шах; я=1 (3.33) а1ьхг < Ь1, Е я=1 хн >О,1=1,п, 1=1,т, х1+ 2хг+ хз = 6, хз 3 4, хь>0, Й=1,3.
Ь(г1,...,г ) =~1 Ь;г;-+ ппп; (3.34) аслг; > сы Е 1=1 и=1,п, г,>О, Аналогично проводится анализ возможных вариаций параметра Ьз = 100 и возможных одновременных вариаций параметров (Ь;). 4 Рассмотренные выше приемы формально позволяют провести анализ модели на чувствительность для любой задачи линейного программирования. Однако они отличаются громоздкостью и трудоемкостью, а потому не нашли широкого практического применения. 3.5.
Двойственная задача линейного программирования В математическом программировании и, как следствие, в линейном программировании существует понятие двойственности [Х1ч'1, которое позволяет установить взаимосвязи для различных методов анализа математических моделей на чувствительность. Поэтому приступим к изучению некоторых аспектов двойственности в линейном программировании. С каждой задачей линейного программирования вида можно связать другую задачу линейного программирования 3.5. Двойственная эалача линейного программирования 129 Задачу (3.34) называют двойспзвеккой задачей лккейкого программкроваккя по отношению к задаче (3.33) (последнюю при этом часто называют прямой задачей лккейкого программкроваккя).
Введя обозначения с е=(с1 ... с„), Ь=(Ь1 ... Ь ), А=(ася)6М„,н(1э), (3.35) Х = (х1 ... х„), У = (г1 ... г,„), прямую и двойственную задачи линейного программирования можно записать в векторном виде: (й(У) = Ь У-+ай(п; двойственная задача т т (3.37) (А У>с, Я)0 Отметим, что задача линейного программирования, двойствен- ная к задаче (3.37), совпадает с исходной задачей линейного программирования (3.36).
Пример 3.14. Рассмотрим задачу линейного программи- рования у(х1 х2 хз) х1 4х2 Зхз — + п1п1 ~ Зх1+4х2+хз < 7, В сформулированнойзадачезаменим минимизируемуюфункцию р максимизируемой функцией 1 = — уэ. Неравенство хз 3 4 эквивалентно неравенству — хз < — 4, а равенство х1+ 2х2+ хз = = 6 можно представить как два неравенства: х1+ 2х2+хз < 6 и З.Л.
Двойственная задача линейного программирования 131 3. СИМИЛЕКС-МЕТОД 1ЗΠ— х1 — 2х« — хз < — 6. Таким образом, рассматриваемую задачу линейного программирования можно представить в виде (3.33); Дхыхз,хз) = — х1+4хт+ хз — > зпах; Зх1+4««+ хз ( 7 х1+ 2«з+ хз ( 6, — х1 — 2«т хз ~4 — 6, — хз < — 4 хь > О, аа = 1, 3. В этом случае в соответствии с (3.35) имеем пт = 4, н = 3 и Ь= Поэтому двойственнан задача имеет следующий вид: й(«1 «з «з,«а) = 7«1+6«« — 6«з 4«4 — + т1п; 3«1+ «« — «з > — 1 4«1+2«« — 2«з ) 4, «1 + «« — «з — «а > 1, «;) О, 1=1,4.
Заметим, что если в двойственной задаче ввести переменное « = «« — «з, которое не ограничено е знаке, то эта задача сводится к минимизации функции Ь* = 7«1+6« — 4«4 при ограничениях: 3«1+«) — 1, 4«1+2«)4, «1+« — «а) 1, «~ )О, «а) О. Можно показать, что: а) если в прямой задаче линейного программирования есть ограничения типа равенства, то в 3 1 — 1 0 4 1 2 1 — 2 — 1 0 — 1 7 б с=( — 1 4 1).
— 4 двойственной задаче им соответствуют переменные, которые не ограничены в знаке (см. пример 3.14); б) если в прямой задаче линейного программирования есть переменные, которые не ограничены в знаке, то в двойственной задаче им соответствуют ограничения типа равенства (см. пример 3.15). Пример 3.15. Пусть необходимо найти максимум функции ~*(х~,х) = бх1+10х при ограничениях: 5х1+ Зх > 10, ха — х < 4, х1 > 0 и условии, что переменное х не ограничено в знаке. Полагал х = х« — хз, где хз > 0 и хз > О, приходим к прямой задаче линейного программирования: ,1(«1,хг,хз) = 6«1+ 10х« — 10«з — ) щах; — 5«а — Зхз + Зхз ( -10, х| — из+из(4, хв>0, 1=1,3. Двойственная ей задача имеет следующий вид: "(«1 «г) = — 10«1+4«з — а щ1п; — 5«1+«г > б, — З вЂ” > 1О, 3«~+««> — 10, «1 ) 0> «г ) О.
Два ограничения типа неравенства — З«1 — «з > 10 и 3«1+ ««) > — 10 можно заменить одним ограничением типа равенства 3«ь+ «г = — 10 41 Вернемся к прямой и двойственной задачам линейного программирования, записанным в матричной форме (3.36) и (3.37).
Пусть задача (3 37) — это исходная задача. Если рассматривать ее как прямую задачу линейного программирования, то необходимо ее преобразовать: с в Ь Я-+ так; — А У< — с; Я>0 132 3. СИМПЛЕКС-МЕТОД З.о. Двойственная палача линейного программирования 133 Тогда двойственная ей задача линейного программирования будет иметь следующий вид: с в сХ + ппп; — АХ> — 6, Х>0„. (3. 38) Теорема 3.6. Если прямая (3.36) и двойственная (3.37) задачи линейного программирования имеют непустые ограниченные множества С и Н доцрснзимых ре!пений, то для любых Х Е С и 2 Е Н имеет место неравенство сх<ь г, т.е.
значение целевой функции прямой задачи не может превос- ходить значение целевой функции двойственной задачи, < По условию множества С и Н не пусты. Пусть Х Е С и х, 6 Н. ТогдаАХ<6,Я>0 иА х>сс,х>0„. Векторное равенство АХ < Ь представляет собой совокупность скалярных неравенств Умножив каждое а-е неравенство этой совокупности на х; > 0 и просуммировав их, приходим к неравенству т и ПЪ х! ~~ а! х < ~~ х;6;, з=! !'=1 !=! А так как (3.38) совпадает с (3.36), то мы пришли к ранее отмеченному свойству: двойственная задача к двойственной задаче линейного программирования — это прямая задача линейного программирования. Таким образом, в системе „прямая -- двойственная" обе за; дачи линейного программирования являются равноправными.
Любую из них можно рассматривать как прямую, и тогда вторая будет двойственной ей. или в матричной записи г'АХ < г'Ь. Х Ах>хе. Таким образом, сХ=Х с <Х А Я=У АХ<Я 6=6 2, откуда и следует неравенство (3.39). ~ Теорема 3.7. Если у прямой (3.36) и двойственной (3.37) задач линейного программирования множества С и Н допустимых решений не пустые и ограниченные, причем существуют такие допустимые решения Х Е С, х' Е Н, что сх' = ь'г", (3.40) то допустимые решения Х' и Я" являются оншимальными ре!пениями.
< Согласно теореме 3.6, для любого допустимого решения Х Е т Е С прямой задачи выполняется неравенство (3.39): сХ < 6 х,'. Таким образом, если существует такое Х' 6 С, что имеет место равенство (3.40), то сХ < сХ' для любого Х Е С и поэтому Х" — оптимальное решение прямой задачи.
Аналогично для любого допустимого решения х, 6 Н двойственной задачи выполняется неравенство сХ' < 6 У. Таким образом, если существует У' Е Н, такое, что выполнено равенство (3.40), то 6 Я" < 6 х, для любого х, Е Н и поэтому х," оптимальное решение двойственной задачи. !и Теорема 3.8. Если Х' и х,' — оптимальные решения прямой (3,33) и двойственной (3.34) задач линейного программирования, то (в обозначениях (3.35) ) имеет место равенство (3.40). т т Аналогично из векторных неравенств А Я > с, Х > с!„может быть получено неравенство 3. СИМПЛЕКС-МЕТОД 134 то 1(уь,...,у„) = 2 сьуь-+ шах; Ь=1 1=1,т, сь — ",2 а!ьи; < О, 1=1 — и;<О, /с = 1, и; 1=1,т, или 2, а;ьи! ) сь, !в1 и;)О, 1=1 6=1, и; АьУь" — — Ь, У') О г = ГьУь, где При этом если если; = сь, Е ЬЕ11; и; п=О, еь Пусть прямая задача линейного нрогральльированил (3.33) предстньвлена в стандартной узорие: аиьуь+уп+; = 6;, Е Ь=1 Уь ~ О, й = 1, п+нь.
Понятно, что для любого У из множества Я допустимых решений и для любого набора действительных параметров и,, 1 — 1, тгг, имеет место равенство П2 и П2 П2 г (у1 ° ° ° уп) ~ Ь;и; = ~ь (сь — ~ аььи;) уь — ~ и;у„+; (3А1) 1=1 ь=! !в1 1=1 т Если У = (У1 "° У*,+, ) б Я вЂ” оптимальное решение прямой задачи линейного программирования в стандартной форме, а у ...у" — значения базисных переменных в У*, то равенство (3.41) принимает вид П2 П2 У(у1'''' у„) — ~ 6;и; = !! (сь ~~ а,ьи )~у* '~ь и у ев1 ье1! 1=1 !еИ !1 = ( 1, ..., и) П 1у1, ..., у ) 12=(и+1, ..., н+т)п(у1, ..., у ) З.Б. Двойственнвв звдвчв линейного нрогрвмннроввннв 135 у(у',...,у„')=~6!и,=Ь и, и=(и! ... и ) .
!п1 Если в равенстве (3.41) положить у; = у,*, ! = 1, о+т, то все коэффициенты при неизвестных в правой части будут неполо- жительными: Сравнивая полученные ограничения с ограничениями двойт ственной задачи (3.34) и учитывая, что )'(У1,...,у„') = 6 и, убеждаемся в том, что и = о" — оптимальное решение двойственной задачи. Так как в системе „прямая — двойственная" обе задачи являются равноправными, то теорема доказана. ~ Замечание 3.5.
Если при записи прямой задачи линейного программирования в стандартной форме воспользоваться обозначениями (3.2), (3.12), то для оптимального решения У* будем иметь Таким образом, Ь и = и Ь= и*АьУь* и ~ — Ь и = (Гь — и Аь)У<,*. При этом если и Аь = Гь (т.е. и=(А ') Гь), то !'=Ь и. 4 В общем случае нельзя гарантировать выполнение неравенств и = (А ') Г ) О и А и) с, но если множество допустимых решений Н двойственной задачи не является пустым, 1 т т то (см. доказательство теоремы 3.8) и = (А ) Гь — ее оптимальное решение. 136 З.СИМПЛЕКС-МЕТОЛ п ( агьх~,— 6!)х; =О, г=1,т; /с= ! г=1,т; х," > О, (3.42) х~>0, (3.43) г=! Поэтому — 6) <О, г=1,т; — са) >О, й=1,и. (г*)'Ах =(г )'ь, (Х') с = (Х*) А х*, (3.44) Теорема 3.9.
Если Х*=(х* ... х„") и У*=(х!" ... х ) оптимальные решения прямой (3.33) и двойственной (3.34) задач линейного программирования, то тп ( ~~! а!ья,* — са) х~ — — О, й = 1, и. !=1 а Если Х* и У* — оптимальные решения, то, согласно (3.36) и (3.37), имеют место неравенства АХ*<6, Х*>о„, А'г*> т, г" >о . Как и при доказательстве теоремы 3.6, можно показать, что в данном случае имеют место неравенства (У') АХ* < (У*) 6, (Х*) А Я* > (Х*) с .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
