Алексеев В.М., Тихомиров В.М., Фомин С.В. - Оптимальное управление (1050536), страница 44
Текст из файла (страница 44)
Предположим, что Я-Функция семейства ((й(гх, т)))) непрерывное точке (О, 0). Тогда: для любых (а, т)) Е !п1(бош 3) Я(сс, т))= зпр (Лсс+<т)', т)>+!п1Я(х, т)»,Л,!)). (11). хз- з, ч»ау' «ел Значения задачи (й) и двойственной ей задачи (й') равны между собой )пЕ 7з(х)=8(0, 0)=Х(0)= «ел л =ь О г«) < ас т= ), „„„ = зцр 'п( 1»(х) + ~Л, (~, (х) а,) (.<т)» Лх, ь> Ох) (12) Д ок а ватель ство. По следствию 1 функция 3 выпукла, а из непрерывности ее в одной точке вытекает (предложение 3 и.
2.6.2) непрерывность и равенство 3(а, т))=(сопело) (сс, т)) для всех (а, х))6!п1(осппо), По теореме Фенхеля — Моро (и. 2.6.3) и следствию 2 3(са, т)) =3'*(сс, т)) = зцр (Л)х+<т)', т)> — 3'(Л, т)')) = )а ч') = зцр (Лсс+<т)', т)>+ )п1 Я(х, т)', Л, 1)), азе хел Ч»е У» чем доказано (11). Подставляя сс *О, т) О, получаем (12). ° 666 С л е д с т в и е 3 (т е о р е м а о и и н и м а к с е). В условиях теоремы двойственности справедливо соотношение зпр Ы Я(х, т1', Х, 1)= 1п1 зпр Я(х, т1', й,1). (13) амо ел ел ело ч ег" а~е Г~ Доказательство.
Левая часть (13) равна Х(0) и в силу (!2) совпадает с Я(0, 0). Что же касается правой части, то !п1 зпр 2'(х, т)', й, 1)= 1пЕ зпр .У(х; Х, т(')= хел хм с ел аччч ° гч = !п! (( —,У)™(х; О, О)) = 1П1 У(х; О, О) сел сел согласно (7) и также совпадает с 5(0, 0). 3.3.3, Линейное программирование: теорема существования и теорема двойственности.
Пусть Х вЂ” линейное пространство, Х' — алгебраически сопряженное с ним (т. е. совокупность всех линейных функционалов на Х), К вЂ” некоторый полнэдральный конус (т. е. пересечение конечного числа полупростраиств Н, =(<х~, х> (О, х,' ~ Х', 1=1, ..., з) — иногда, впрочем, от условия йолиэдральности отказываются). Экстремальные задачи вида <хе, х> — !п1; гт(х) = <х,', х>~Ьт, ! =1, ..., т, х~К, (1) составляют отдельный класс задач линейного программирования. В этом пункте будет рассмотрен нонечномерный случай, когда Х=)тч Х'=йче К=1!+.
В этом случаезадачу (1) можно переписать так'): сх'- (п1; Ах'-" Ь, х О, (2) где с Е 1!"*, А =(ап), 1 = 1, ..., и, ! = 1, ..., т,— матрица, задающая линейный оператор из 1!" в мт, Ь~ к'". Символ ге~г для конечиомерных векторов г' и г означает, что все координаты вектора не превосходят соответствующих, координат вектора г'. Задачу (2) назовем конечномерной задачей линейного программирования. Эта т) Напомннм, что дхя конечномернмк пространств мм нмеем дав обоаначенна: л <с, х> = ох = ~ с,хо с Е и"', х Ч й", т-т задача — частный случай общей задачи выпуклого программирования. Однако в ней имеется еще более специальная структура: все функции здесь линейны и конус поливдрален. Как н обычно, условимся, что если задача (2) несовместна, т.
е. не имеет допустимых злементов, то ее значение считается равным +оо. Теорема существования. Если множество допустимых значений конечномерной задачи линейного программирования (2) испусти и ее значение конечно, то задача имеет решение. Доказательство теоремы 1 опирается на один простой факт конечномерной геометрии. Напомннм, что коническая оболочка сопе С некоторого множества С~Х определяется равенством 9 сапе С = х Е Х х = Х Л х„Л! =! О, х, Е С ! и является выпуклым множеством (н. 2.6.1).
Мы будем говорить, что конус соне С порожден множеством С. А) Лемма о замкнутости конечнопорожденного конуса в конечномерном пространстве. Всякий конус в конечномерном пространстве, по рожденный конечном множеством точек, замкнут. Д о к а з а т е л ь с т в о. Пусть К = соне С!= 11'ч, С = = (г„..., гл), г, Е Й'~ Доказательство проведем по индукции. 1) А=1. Тогда К=сопе(г,) =(х(х=Л!г„Л!)О)— полупрлмая, т. е.
замкнутое множество. 2) Допустим теперь, что лемма верна для й =з — 1. Докажем ее для й= з. Возможны два случая: а) конус К содержит векторы — г„..., — г,. Тогда К есть подпространство конечномерного пространства н, следовательно, замкнутое подмножество; б) хотя бы один нз векторов ( — г,), ! = 1, ..., з, например ( — г,) не прннадяежнт конусу К. Обозначим через К, = сопе (г„..., г, !). По индуктивному предположенню конус К, замкнут. Пусть вектор г принадлежит замыканию конуса К, т. е.
г = 1(щ $„; $„ЕК, и) 1. По опрео делению $„б К = сапе (г„..., г,) ФФ Ч„= ~~'~ Л,„г, = Ь„-1- Л,„г„ !=! где ь„чК, н Л,„~ )О. кто Если допустить, что ˄— оо при и — оо, то — г,=1пп "~ "— — 1пп — '" ЕКг Л Ф Ф .ЮИ П ~Ф Ю6 (напомним, что $,— г, и потому $„(Л,„— О, а ~„~Л,„ЕК, вместе с ь„), т. е. — г,ЕК, вследствйе.замкнутости К„ что противоречит допущению. Значит, Л,„не стремится к бесконечности и можно выбрать подпоследовательность Л,„, сходящуюся к некоторому числу Л, ) О.
В этом случае 1 Ф=$.» — Л»аг -г — Л"г =-г В силу замкнутости К, вектор гЕК, и, следовательно, г=г+Л.г.ЕК И Б) Докажем теперь теорему существования. Рассмотрим в пространстве 11"+' множество К, образованное такими векторами (и, г), и Е )с, г Е )с'", для каждога из которых найдется хотя бы один вектор хЕ 11"„.
такой, что сха а, Ах) г. Множество К вЂ” это конус, ибо если (а, г) Е К, то для некоторого хЕ й~, сх -а, Ах) г. Но тогда для любого 1)0, 1хЕ)с"„с(1х)<(а, А(1х)>(г, т. е. 1(а, г)ЕК. Покажем, что конус К порожден конечным множеством векторов в 11 +'. =(с„асо ..., а„,), ~,=(с„а„, ..., а,), ..., ~„= =-(с„, а»а ..., а „), ь„+, = (1, О, ..., 0), »„+,=(О, — 1, О..., 0), . = (О, ..., О, — 1). Прежде всего ~;ЕК, так что сапе Д„..., ~„„„1) ~ К.
Действительно, если ! ~ (а, надо взять в качестве х стандартный базисный вектор е,; для остальных 1 надо взять х =О. Пусть теперь вектор ~ =(а, г) = (сс, г„..., г ) Е К. Тогда для некоторого хЕ В'*, х=-(х„..., х„) такого, что х,~ О, ..., х„- 0 П некоторых ~,) О, $:» О, выполняются соотношения ~~'., сх +Ц,=я, ~ аоху — руэгг„(=1, ..., т. ~=! 1=! 271 Но зто как раз и означает, что В т Ь=(а, з)= ~ хД+~Д +с+ Х ()Д +с+с с=! с=с ху > О, р, ~) О, рс > О, Ь Есопе(~„..
„~„~Д. По лемме нз предыдущего пункта конус К замкнут. По условию теоремы задача (2) имеет допустимый эле- мент х и значение задачи а > — оо. Из определения К следует, что точка (сх, Ь), где сз=сх, принадлежит К, При зтом, очевидно, что и)й. Следовательно, множество ес=<аЕК<(а, Ь)ЕК) непусто и а=(п((сх<мб9Ц, т. е. (сс, Ь) принадлежит замыканию конуса К, а значит, и самому К. Следовательно, существует злемент х) О, для которого Ах)Ь и сх(сх, т. е.
х — решение задачи. ° Переходим к рассмотрению двойственной задачи. Теорема двойственности приобретает здесь более закон- ченный вид, чем в предыдущем пункте, поскольку ввиду специальной структуры 5-функция задачи оказывается замкнутой. В соответствии с формулами (5) и (б) п. 3.3.2 рас- ширенная функция Лагранжа имеет вид .У(х; Х) = сх+Х(Ь вЂ” Ах), хай+, А~К",; хай+", Кй+', + со, х( и". Отсюда мы находим семейство возмущений задачи (2) и двойственное семейство. Согласно (7) п. 3.3.2 7 (х; а) = ( †.2')* "' = зир (Хсс+ Я (х, Х)) = ( +, х(й"„ =~ зпр(Хсх+сх+Х(Ь вЂ” Ах), х~й", хьь сх, х) О, Ах~~Ь+сх, + со в остальных случаях. Обозначая г = Ь +сх, получаем возмущение задачи (2) сх спс, х О, Ах ) г.
(3) Аналогично для определения двойственной задачи мы 272 должны вычислить й(0, Л) =( — Янь) (О, Л) = — зпр ( — Я(х, Л)) ° кЬΠ— зпр( — сх — Л(Ь вЂ” Ах)), й.:ав О, Э~ Л ( )(ще ЛЬ, Л~ ~О, ЬА ~;с, — оо в остальных случаях. Это дает задачу ЛЬ зцр; ЛА ~с, Х;:г О, (4) двойственную задаче (2). Она имеет такое же строение, как задача (2), и легко понять, что если, отправляясь от задачи (4), построить двойственную задачу по тому же правилу, по которому из задачи (2) получилась задача (4), то мы вернемся к задаче (2). Поэтому имеет смысл говорить о паре двойспменных задач линейного программирования.
Теорема двойственности. Для пары дэойст. венных задач линейного программирования справедлива следующая альтернатива: либо значения задач конечны и равны и в обеих задачах существует решение, либо е одной из задач множесп|во допустимых элеменпюв пуспю. В первом случае хЕ)4" и ХЕ и"', в том и только е том случае, будут решениями задач (2) и (4) соопиитственно, когда они допустимы в этих задачах и удовлетворяют одному из двух соотношений сх=ЛЬ, (5) Л(Ах-Ь) =(ЛА — с) х. (6) Во втором случае одна из задач несовместна, а друэаа либо несовместна (т.
е. ее мнозееапво допустимых элементов пусто), либо имеет бесконечное значение, Доказательство. А) Построение Ю-функ. ц и и. Снова рассмотрим тот же конус К, что и в теореме существования. Если (а, г) е,К н ф~га, то (д, г)аК, а потому К является иэдграфиком функции 8(г) = 1п((а!(а, г) ЕК). (7) Из доказательства теоремы существования еледует, что 1п( достигается и 8(г) есть значение задачи (3) и, следовательно, формула (7) оиределяет 8-функцию задачи (2). 273 Поскольку К вЂ” выпуклый и замкнутый конус, 8-функция задачи (2) замкнута и выпукла.
Б) Вычислим функцию 8', сопряженнук7 с функцией 8, По определению, 8«(Л) = = зпр (Лг — 8(г)) = зпр(Лг — 1п1 (сх1х Е К"„Ах ~ гЦ = « « « =зпр (Лг — сх1хб 11"„г Е 11, г ~(Ах). («, «) Очевидно, что зцр(Лг~гЕ К", г(Ах) =ЛАх( ао в том и только в том случае, когда Л»0. Таким образом, ( зцр(ЛА — с) х, если Л6 К'«', 8«(Л) «ь з + сои если Л(1 К," О, если ЛА ~с, Л» О, +со в остальных случаях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
