Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 18
Текст из файла (страница 18)
' ' =( +со, иначе ( +со, иначе. Найдем сопряженную в смысле Лежандра функцию к функции Я'(у), т.е. вторую сопряженную к функции Я(6): Я" (6) = тах((У,Ь) — Я*(у)) = тах((У,Ь) ~ А У = с, У < О). г г Таким образом, двойственной задачей к задаче линейного программирования в обшей форме является следующая задача: (Ь,у)- тах; А'у=с, у<0. Для задачи линейного программирования в нормальной форме: (с,х) -~ тах; Ах ~ (Ь, х > О, выпишем без доказательства двойственную задачу (попробуйте сделать это самостоятельно): (Ь,у) пип; А'у > с, У > О. Как мы видим, двойственнал задача в этом случае обладает определенной симметрией по отношению к исходной. Элементы Ь и с меняются местами, максимум меняется на минимум, матрица А меняется на транспонированную, и матричное неравенство меняет знак.
4' Глава 2. Линейное программирование 2.3.2. Вывод задачи двойственной к двойственной задаче для задачи линейного программирования в общей форме Покажем, что понятие «двойственности» введено правильно, т.е. лвойственная задача к двойственной является исходной задачей. (Ьу)- тах; Ау=с, у<0 Для того, чтобы вывести двойственную задачу к задаче (Р"*) надо вначале свести ее к задаче линейного программирования в общей форме, для которой уже известна двойственная задача.
Вначале сведем задачу на минимум. Затем заменим равенство А'у = с на два неравенства с < А'у < с с» А'у < с, -А'у < — с. Получим эквивалентную задачу линейного программирования в общей форме: ( — Ь,у) — пнп; — А' у < — с Двойственная к ней будет следующая задача: ((с, — с, 0), (х, хэ, хэ)) — гпах; .! (А -Ау) х' =-Ь, х <О, '<О, х <О. з б 2. Двойственность в линейном программировании 10! 2.3.3. Вывод задачи двойственной к задаче в канонической форме Задачу линейного программирования в канонической форме (с,х) «тах; Ах=Ь, х>0, (Рь) сведем ее к задаче на минимум: ( с,х)-«пцп, Ах — 6, х>0, при этом ЯВ = — Яр' Обозначимчерез Я(Ь) = т1п(( — с,х) ! Ах = 6 х > О) — Я функцию « задачи (Р'), рассматривая аргумент Ь как параметр в задаче (Р').
Найдем первую сопряженную функцию к функции Я(Ь): Я (Ь )=шах((Ь',Ь)-Я(6)) =так((6",Ь) — пнп(( — с х) !Ах = Ь, х > О)) = ь Ь = тах((Ь', Ь) + (с, х) ! Ах = Ь, х > О) = гпах((6', Ах) + (с х) ! х > О) = »,* » А*Ь" < 0 = пъах((А'Ь' + с, х) ! х > О) = ( » 1 +оо, Найдем сопряженную в смысле Лежанара функцию к функции Я"(Ь ), т.е. вторую сопря;кенную к функции Я(Ь): Перепишем зту задачу в виде (с,х' — х)- тах; А(х — х)+х = — Ь, х'<О, х <О, х <О. Обозначая х = * — х, и учитывая, что равенство А(х' — хэ) + х' = — Ь э эквивалентно неравенству А(х' — х') > -Ь, поскольку х' < О, а ограничений на знак х уже не будет, получим — (с, х) «тах; — Ах > — Ь.
Заменяя тах на ппп и умножая матричное неравенство на — !, придем к задаче, являющейся двойственной к залаче (Р"), которая совпадает с исходной задачей (Р) (с, а) «т!п; Ах < Ь. Таким образом, мы убедились, что термин «двойственная задача» используется правильно. Я" (Ь) = тах((Ь",Ь) — Я*(6')) = гпах((Ь', Ь) ! А'Ь*+ с < 0) ~ ь. ь. Яр; = — Я" (Ь) = тт(( — Ь', Ь) ! А*Ь' + с < О). Полагая у — — Ь, получаем Яр- — ппп((у 6) ! А у + с 0) » э следовательно, имеем следующую двойственную задачу (у,Ь) «ппп; А'у > с.
2.3.4. Упралшения 1. Вывести двойственную задачу для задачи линейного программирования в нормальной форме с помощью преобразования Лежанлра. 2. Вывести двойственную задачу для зааачи линейного программирования в нормальной форме путем свеления ее к общей задаче линейного программирования. 3.
Вывести двойственную задачу для эалачи линейного программирования в канонической форме путем сведения ее к общей заааче линейного программирования. 4. Показать, что для задачи (с,х) — «т!п; Ах = Ь, х > О, двойственной является задача (у, Ь) — тах; А*у < с. Гог Глава 2. Линейное программировавие ф 3. Обоснованне симплекс-метода 3.1. Теоремы существования, двоаственностн, критерий решення Приведем трн теоремы, играющие важную роль при обосновании симплекс-метала. Рассмотрим задачу линейного программирования в общей форме (с,х) гп1п; Ах < Ь, где с,х Е К", Ь б К, матрица размеров га х и А = (а')! ! ! с !» а, ... а! 1 )г аэ»( ! со столбцами а' =,, у = 1 ... и.
» / а»! !эм / а~ Обозначим Яр — численное значение задачи (Р), Дгй Р— множество решений задачи (Р), т.е. множество допустимых точек х Е К", для которых (с,х) = бр. Т еврема существования. Если численное значение задачи (Р) конечно (1ор~ < +оо), то ее решение существует (Агб Р ~ й!). Доказательство. Отметим сразу, что поскольку численное значение задачи конечно, то множество допустимых элементов непусто (г!(Р) ОО м!). РаССМОтрИМ МНОжЕСтВО К: = ((а,э) б К х К ( З х: (с,х) < о, Ах < л). Ясно, что К вЂ” выпуклый конус. Напомним ряд сведений из выпуклого анализа. Пусть С: = (с!,..., с ) С К" — некоторое конечное подмножество.
»1 В Элемент о = г Лс;, Л > О, ! = 1,..., пэ, г , '1, = 1, называется выпуклой !=! ы комбинацией С, а элемент й = г 1,еч 1! > О, о = 1 ... пэ, — конической 1 ™ 1=! комбинацией С. Совок и овокупность всех выпуклых (конических) комбинаций конечных подмножеств множества С называется выпуклой (нонической) оболочкой С и обозначается со С (соне С). Мо!кно легко показать, что множество со С совпадает с пересечением всех выпуклых множеств, содержащих С (иногда это свойство берут за определение со С), а множество соле С совпадает с пересечением всех выпуклых конусов, солержаших С.
я 3 Обоснование симплекс метода 103 Выпуклая оболочка конечного числа точек называется выпунлогм мнаграннинам, а выпуклая коническая оболочка конечного числа точек— конечнопаролгденным конусам. Леввма 1. Конус К вЂ” конечнопоролгденный. Доказательство леммы 1. Покажем, что К = сапе(~Е!,...,хС„, г!о,п„ ..., О,„), где Е; = (с., а'„ ..., а~,), у = 1,...,и„ г1о = (1, О,..., 0), „, = (О, 1,..., О),..., О = (О,О,... 1). Вложение соле(~(!,...,~Е„,г!о,...,г! ) С К, следует иэ того, что все образующие конуса лежат в К. Действительно, полагая х = йе! (е„...,е, — канонический базис в К") в определении конуса К, мы падучим, что ~(1 6 К, у = !,...,п; для векторов гй надо взять х = О.
Обратно, если вектор (а,а) = (о,э!,...,з, ) б К, то существует х = (х!,,х„) б К", для которого (с,х) < а, Ах < а. Значит для некоторых )уо > О,..., Д„Р 0 выполняются соотношения (с,х) +!Уо =а, Ах+Д = а (на =(13! . Р )) в=о » » — Е' сх +1!о=а, .г агх,+!о!=э!, 1=1 ( Но это как раз и означает, что » !» х1(! Е ~~) !3!г1! = (о, э). 1=! в=о П у Э х!Гу = ~ /х,/(э!Впху. (3), то (о,э) б сове(хС6,",~С, у=.! 1=! г!о . %») . Лемма л (о замкнутости конечнопорожденного конуса). Конечнопораледенныи конус замкнут. Доказательство.
Доказательство проведем индукцией по числу п! порождающих точек. Если пэ = 1, то конус К = (х б К" ) х = ой!, ! > О)— полупрямая, очевидно, замкнутая. Пусть теорема верна для конусов, порожленных п! — !точкой, щ > 2, н пусть заданы гп точек й!,...,й . Если конус К = соле(й!,...,й ) содержит векторы — й!,..., — й, то К вЂ” конечномерное надпространство, т. е.
замкнутое множество. В противном случае существует вектор (пусть зто будет — й ), который не принадлежит К ( — й ЕК). Обозначим К'! = соле(й!,...,й !). По предположению индукции конус К' замкнут и К = (й ~ й = й'+ !й, й б К, 1 > О). Пусть (й": = й~+!"й,„)»еи — последовательность векторов из К, схоляшаяся к Й 6 К" (й" — Й). Из последовательности (1") выберем 104 Глава 2. Лииейвее программирование сходящуккя подпоследовательность (бь) — ! > О. Имеются дае аозм;, = со. первом случае получим, что числа й~ = йп' — Гьй й — !й Е К' (в силу замкнутости конуса К'), т. е. й Е К и, слелоаательно, К замкнуто. Во втором случае, яся последовательность, (!и') — +оо). Откуда —,, сходится к -й, что невозможно так как — й к К .
$ Поскольку Яр = пцп (а ! 3 х: (с,х) = а, Ах < ЬТ =: а, то существуют последовательности (хь) и (оь), оь а при й +со, для которых (с х ) = о, р (, ь) — оь, Ахь < Ь (это означает, что последовательность точек (о,Ь) Е К ( м ) — замкнутому по лемме 2 множеству. Поэтому предельная точка О Ь (а,Ь) Е К.
Тогда по определению множества К существует точка х такая, что (с, й) < а = Яр, Ах < Ь. Это означает, что х Е АгаР. Теорема существования доказана. ° Вернемся к задаче линейного программирования а общей форме. В п.2.3 мы обозначили через 5(6): = пйп ((с, х) ! Ах < 6) — Я-функцию н задачи (Р), рассматривая аргумент Ь как параметр в задаче (Р). Лемма 3. Я вЂ” выпуклая замкнутая функция. Доказательство леммы легко выводится из соотношения ер! 5 = К, где К вЂ” выпуклый замкнутый конус, рассмотренный при доказательстве теоремы существования, Лемма 4. П с .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
