Ф.П. Васильев - Методы оптимизации (1125241), страница 40
Текст из файла (страница 40)
Сколько нужно в сутки покупать концентратов, чтобы необходимый суточный рацион был наиболее дешевым? 5. Показать, что множество Х = ~ж = (ж,... х ) > 0; х + 4ж — бх — 5х — 3 ж — хз = 2, 1 6 . 1 2 3 4 б 6 -4х +4ж — 12х -2х +2х =2, х +2х -Зх +Зж +х +жз= П состоит из единственной 1 2 3 5 6 2 3 4 б 6 точки, Указ вине: применить метод искусственного базиса, выбрав в нвчвльнойсимплекс- таблице разрешающий элемент из столбца жг с помощью лексикогрвфического правила (3.48). б. Множество Х зздвнобтсловиями! х=(х,..., ж )>О: х -2х +ж =1, х -2х 42х +х = 1 6 .
1 2 3 1 2 3 4 = 1, х'-2хг+2хз+2ж4-х = [, х1-2хг+2хз+2х4-2хб+х6=1, ж!+хг+хз+хб+хб+хб = !. Симплекс-методом решите задачу 7"(х)=(с, ж)-«[о[, хе Х при различных с б Е и убедитесь, 6 что минимум достигается в одной и той же точке множества Х, Объясните это явление. 7. Примените симплекс-метод к основной задаче (!.21) с вектором Ъ > 0 сведя ее к канони- ческой задаче (1.23). У к з з в н и е; сравните системы (1.22) и (3) и найдите угловую точку множества Е задачи (1.23). 8. Обобщить симплекс-метод нв задачу: 7(х) = (с, х) -«[и[; ж Е Х = (х е Еь! х > О, Ах = = Ъ, ог < х' < р;, ! = 1,..., и[, где оз, р! заданные величины,;оз < рз (возможно, некоторые ог = — оо и некоторые Ру =+со) [775].
9. Пользуясь упражнением 8, рассмотреть задачи из упражнений 1-3 при дополнительных ограничениях 0 < хг < 2, ц 6. Условие разрешимости задач линейного программирования. Теоремы двойственности Будем рассматривать общую задачу линейного программирования: у(х) =(с, х) =(с„х) + (~, хг) — «!п1, х =(х„х ) е Х, Х =(х =(х„тг): х, ЕЕ", хг ЕЕ", Апх, + Анхг < Ь„А2 х, + А„цг= 62, х, >0), (2) 4' (3) ,7(х) = (с«х) — «!п[, х е Х = (х е Е'Ц Ах = Ь, х ) 0), Ц, 7" '. ~Ц! г, Ь = (Ь„Ь2) Е Е при этом с Е .Е", Ь Е Е", А — матрица размера гп х и.
С этой целью поло- жим (см. $1) х =㫠— г, г, =шах(0; х), гг =шах(0;-х), е = 6, — Апх, — А«гхг, и в пространстве переменных е« = (х„г„гг, е) Е Е', д = и, + 2п + т„рас- смотрим задачу: д(то) = (с„х ) + (с, 21) + ( — с, г ) + (О, е) — «!п1, ц«Е [47«(4) [«]г = (ш Е Еч: е«) О, Ап х, + А «гг« + ( — Аш)гг + Х е = Ь„ Аг,х, + Аггг«+ ( — Агг)кг+ Ое = Ь,), (5) где 1 — единичная матрица размера т, х т,, Задача (4),(5) совпадает с задачей (3), если принять с = (с„с, — с, 0) Е Е", ( 411 '4«г« .4«ю ),А21, А „— А, 0,7 — матрица размера гп х и, где т=гп, +т, п=д=п, +2п +ты Согласно теореме 1.1 из х ф Я, у, > -со следует, что [47 ф Я, д, = !и[ д(ш) ) — со.
же И« где Ае — матрицы размера гп! х и., с, Е Е"', Ь, Е Е, 3, д' = 1,2, Как и выше, будем обозначать у, = !п1 7'(х), подразумевая при этом, что Х ~ еех ~Я. Для случая, когда у„> — оо, введем множество Х, = (х е Х: ['(х) = =7",). Напоминаем, что задача (1), (2) называется разрешимой, если Х, ф.Я; каждую точку х„б Х, называют решением этой задачи. 1. Приведем теорему существования решения задачи (1), (2), которая дополняет теоремы Вейерштрасса из Ц 2.1 н характеризует специфику задач линейного программирования.
Т е о р е м а 1. Задача (1), (2) разрешима тогда и только тогда, когда Х ~ Я и целевая функция [(х) ограничена снизу на Х, т. е. 7„> — оо, Нетрудно видеть, что для нелинейных задач такая теорема неверна. Например, задача: Г(х) =е ' — 4!и[, х 6 Х=(х ЕЕ'! х >0) не имеет решения, хотя и 7", =0> — со. Д о к а з а т е л ь с т в о.
Н е о 6 х о д и м о с т ь очевидна, так как условие Х.~Я предполагает, что Х~Я и 7", > — со. Докажем до ст аточ но сть, Пусть Х ~ Я, ['. > -оо. Покажем, что тогда Х, ~ Я. Пользуясь конструкциями теоремы 1,1, задачу (1), (2) запишем в канонической форме: 140 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4 з. УслОВие РА3РешимОсти. теОРемы ДВОЙстВеннОсти 141 й Задача (11), (12) называется двойственной задачей по отношению к исходной задаче (1), (2), переменные Л =(Л„Л ) называются двойственными переменными по отношению к исходным йеременным х = (х„х ).
Будем обозначать !й' = зпр !й(Л), Л* = (Л Е Л: !й(Л) = !й*). Как видим, двойственл~ь ная задача (11), (12) однозначно определяется по элементам со с, ЬР Ь„ Ап, Аиь Ам, Ам исходной задачи (1), (2). Л ем м а 3. Если в задачах (1), (2) и (11), (12) множества Х и Л непусты, то величины 7", = 1п17(х), !й*=зцртЬ(Л) конечны и Ф*~У.
(13) Доказательство. Возьмем произвольные хЕ Х, Л ЕЛ. Тогда справедлива следующая цепочка неравенств, вытекающая из определений (2) и (12) множеств Х и Л: ,Г(х) — 4(Л) = (с„х,) + (с„хз) + (Ь„Л,) + (Ью Л,) ) ) (с„х,) + (с~, хз) + (А„х, + Аыжз, Л,) + (Ам х, + Аыж2, Л,) = = (с, + Ат Л, + А~~! Лм х) + (г + А !~~Л ! + А~~2Лю хз) ) О. (14) Таким образом, Дх)) !Ь(Л), !УхЕХ, Л ЕЛ.
(15) Последовательно переходя в неравенстве (15) сначала к нижней грани по х е Х, затем к верхней грани по Л е Л, убеждаемся, что величины У'„!Ь* конечны и удовлетворяют неравенству (13). Лемма 3 доказана. П Вьисним, как выглядит задача, двоиственная по отношению к двойственной задаче (11), (12).
Замечательно, что эта задача, оказывается, с точностью до эквивалентной формы совпадает с исходной задачей (1), (2), Чтобы убедиться в этом, перепишем задачу (11),(12) в равносильном виде, как задачу минимизаций! — !Ь(Л) = (Ь„Л,) + (Ьм Л,) — ! 1п1, Л Е Л, Л=(Л =(Л„Л,); Л, ЕЕ"ь, Л, Е Ь~, ( — А;",)Л, +( — Ат)Л, (с„(16) по форме совпадающей с исходной задачей (1), (2), и затем, пользуясь тем же правилом, с помощью которого была сконструирована двойственная задача (11), (12) на основе исходной задачи (1), (2), составим двойственную к (13) задачу. Обозначив двойственные к Л = (Л„Л,) переменные через х = (х„х,), придем к следующей задаче: — (с„х,) — (сз, х,) — ! зир1 х = (х„х,) Е М, М=(х=(х„хз): х, ЕЕ", жгЕ.Е", ( — А',;)'х,+( — А,')тхз+Ь, )О, (17) ( — Ай)тх, +( — А,',)~жз+ Ь, =О, х, ) 0), являющейся двойственной по отношению к задаче (16). Так как ( — А;.,".)т = = — Аи, ь', у =1, 2, то нетрудно видеть, что М = Х и задача (17) равносильна задаче (1), (2).
Таким образом, с учетом сделанных эквивалентных переходов от задачи (11), (12) к задаче (16), от (1?) к (1), (2), можем сказать, что задача, двойственная по отношению к двойственной задаче (11), (12), совпадает с исходной задачей (1), (2), и, следовательно, задачи (1),(2) и (11), (12) образуют пару взаимодвойственных задач. Оказывается, параллельное изучение взаимодвойственных задач способствует более глубокому понима- нию природы этих задач, оказывается полезным при разработке методов их решения, обогащает теорию линейного программирования. Связь между взаимодвойственными задачами (1), (2) и (11), (12) отражена в следующих теоремах, называемых теоремами двойственности. Т е о р е м а 2.
Задача (1), (2) имеет решение тогда и только тогда, когда имеет решение двойственная к ней зада~!а (11), (12). Иначе говоря, взаимодвойственньге задачи линейного программирования либо обе одновременно разрешимь!, либо ни одна из них не имеет решения. Если задачи (1), (2) и (11), (12) разрешимы, то значения их экстремумов совпадают, т. е. Л=Ф'.
(18) Д о к а з а т е л ь с т в о. Пусть задача (1), (2) имеет решение, т. е. Х, ~ О. Возьмем произвольную точку х, Е Х,. Согласно лемме 2 тогда существует точка Л* Е Л, для которой справедливо равенство (10). Таким образом, Л ~ О, и, кроме того, ?„= 7(х,) = !Ь(Л") < ф*. Отсюда и из (13) следует Л=,?(х.) =4(Л')=!Р", т. е.
Л* ЕЛ. Таким образом, из разрешимости задачи (1), (2) следует разрешимость двойственнои к ней задачи (11), (12), Так как задача (1), (2) в свою очередь является двойственной к двойственной задаче (11), (12), то из разрешимости задачи (11), (12) следует разрешимость задачи (1), (2), причем !й' = ?",. Теорема 2 доказана. П Теорема 3. Взаимодвойственные задачи(1), (2) и(11), (12) имеют решение тогда и только тогда, когда существуют точки х, = (х„, ж„), Л * = (Л;, Л,*) такие, что х, Е Х, Л* Е Л, У(х„) = !й(Л*).
(19) Соотношения (19) справедливы для всех точек х, Е Х„, Л' Е Л* и только для них. Доказательство. Необходимость. Пусть задачи (1), (2) и (111, (12) разрешимы, т. е. Х„ф О, Л' ~ О. Возьмем любые точки х, е Х., Л* еЛ. Это означает, что х е Х„, 7(х )=~„Л*еЛ, !й(Л ) =!Ь'. Но согласно теореме 2 тогда ?"„= !1 *, поэтому 7(х„) = !р(Л*). Таким образом, в качестве точек х„Л', удовлетворяющих условиям (19), можно взять любые точки из множеств Х„Л. Достаточность. Пусть для каких-то точек х„= (жн, х,), Л' = = (Л;, Л,*) выполняются соотношения (19).
Это значит, что множества Х и Л непусты и по лемме 3 тогда ?", ) — со, !Ь* < +со. Отсюда, из теоремы 1 и следствия к ней следует, что задачи (1), (2) и (11), (12) разрешимы, т. е. Х, ф О, Л ~ О. Согласно теореме 2 тогда 7, = !Ь*. Отсюда и из (19) имеем 7 < ~(х ) = !й(Л*) < !Р' = 7". Это значит что все неравенства здесь обращаются*в равенства, т, е. 7(х,) = ~„!й(Л*) = !й* и, следовательно, х, е Х„ Л* Е Л.
Теорема 3 доказана, С1 3 а м е ч а н и е. Условия (19) равносильны условиям х, ЕХ, А*ЕЛ, Дх„)~(1Ь(Л*). (20) В самом деле, совмещая неравенство из (20) с неравенством (15) при х = х„ Л = Л', приходим к равенству 7(х,) = ф(Л*). Т е о р е м а 4. Взаимодвойственные задачи (1), (2) и (11), (12) имеют решение тогда и только тогда, когда существуют точки х„= (хьл ж,), Л* =(Л;, Л,") такие, что х, ЕХ, Л*ЕЛ, х,',(Ат,Л,*+Ат,Л, *+с,)' =О, у =1,..., и„ (Л,')'(Ь! — А!,х!* — Аыхз„)' = О, 1 = 1,..., тп!. 143 142 Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
