Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 20
Текст из файла (страница 20)
(4.11) хЕХ УЕЛ уЕП хЕХ Пусть Гь (х*, р) = впр((х, хх) — Гв'(х, у)). (4.12) х ФУнкпии Гу (хх, Р) выпУкла по совокУпности аРгУментов, так как она есть верхняя грань выпуклых функций <х, хх> — Гс(х, у). Последняя функция, очевидно, выпукла по хх; по у она выпукла, так как Ге(х, у) вогнута по этому аргументу. Ф а теогемА двойственности Рассмотрим многозначное выпуклое отображение о( *) = ((у, у'): у' > 1:(х*, у) у ~ Ч. Для этого отображения Их (хх, уе, уаа) = = 1п1 (<У у.')+У'*у': раей(ха у) У~ Ч. (т та) В частности, при уа = О, уае =1 И~, (х*, О, 1) = 1Е1 [~, (х*, у): у Бе Х) = у (х*). Аналогично, 1)х (Х, О, 1) 1Е1 ( — (х, х*)+у': уа))а'(хх, у), Уее)у) = (х*,а аа) 1Е1 ( — (х, ха)+),(х*, у): У~А') = (х*,а) = 1п1 1Е1( — (х, хе) + (а (х*, у)) = аня хх Бор((х1 ха) 1о (хе1 у)) = 1а(х у).
хх Так как у(х*) полуиепрерывна в ха = О, то согласно теореме 4.2 Бпр((Е1 ( — Ла(х, у))~ = у(0). (4.13) х ~Бек Но у (0) = 1Е1 Бпр ( — 1а (х, У)). теехел (4 14) еа = (п1 ( — Уа(х> У)). тем Здесь было использовано то, что ),(ха, у) есть (согласно (412)) функция, сопряженная к ~а(х, у) относительно х; а так как /а(х, у) замкнута по х, то в силу теоремы 4.4 1п1( — (х, х*) + )'" (хх, у)) = $32 Гл пь Выпуклые мнОГОзнАчные ОГОБРАжения Сопоставление (4.13) и (414) доказывает (4.И), а, значит, и (4.10). Теорема 4.8.
Пусть )о' — выпуклое компактное множество в У, функция 1(х, у) есть замкнутая выпуклом собственная функция х при каждом рона и з мкнутая вогнутая функция у при каждом х, а у(0) т=ж . Тогда имеет место соотношение 1В1зпр )(х, у) = зпр(п11(х, у). х ООК оси х Д о к а з а т е л ь с т в о. В рассматриваемом случае М = Х и необходимо проверить только полунепрерывность в нуле о1оункпип у (х») = (п1 )»(х», у), Рс к 1» (х», у) = зпр((х, х») — 1(х, у)). Так как 1(х, у) замкнута по у, то 1»(х», у) замкнута по х* и у. Поэтому согласно сказанному в начале этого раздела нижняя грань (»(х», у) по у он)о' достигается. Пусть теперь х'.— «О, у(хо) — «р. Ооозначпм через у; то значение у он)((, для которого 1» (хо, у;) = у (хб).
Так как у,ов)о' н )о' — компакт, то без ограничения общности можно считать, что у — уо он )у. Используя это, получаем р= 11шу(х;) = 1(ш1»(ха, у;)з1»(0, уо)~)у(0), (4.15) сю о так кэк )»(х», у) замкнута но совокупности переменных и 1»(0, уо) > (п1(1»(0, у): у~)о') =у(0). Тем самым полунепрерывность у(х*) в нуле доказана, и это завершает доказательство теоремы.
Глава 1Ч ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ Выпуклое программирование — это область исследований, объектом которых служат экстремальные задачи, связанные с минимизацией выпуклых функций на выпуклых множествах. Это, во-первых, задачи описания точек, в которых выпуклая функция достигает своего минимума на данном множестве, т. е'. формулировка необходимых условий экстремума. Во-вторых, описание задач, двойственных к данной задаче, т. е.
таких экстремальных задач, нахождение максимума в которых так или иначе тесно связано с решением исходной задачи. Этой проблематике, а также описанию решении некоторых более конкретных вопросов и посвящена данная глава. 5 1. Линейное программирование К задачам линейного программирования относятся задачи, в которых ищется минимум линейной функции на множестве, заданном системой линейных неравенств. Таким образом, задачей линейного программирования называется задача нахождения минимума целевой функции (х,яе) при ограничениях (х, х,'.) — а;:<-О, 1= 1, ..., т, (1Л) или, короче, 1п11(я, х"): (х, а,'.) — а;(О, 1= 1, ..., т).
(1.2) х В дальнейшем будет предполагаться, что система неравенств 11Л) совместна, т. е. существует по крайней мере одна точка л, ей удовлетворяющая. Множество точек х, удовлетворяющих системе 11Л),будем обозначать через Р: Р=1ж (х, х,'.") — сс;(О, 1= 1, ..., т), и называть допустимой областью. 134 ГЛ. 1У. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ 1. Необходимые условия минимума. Теорема 1.1. В задаче линейного программирования нижняя грань целевой фуннции либо достигается и конечна, либо равна — ег. Д о к а з а т е л ьс т в о. Согласно теореме 1.4И5 и формулам (1.4.24), (1.4.25) любые решения системы И.1) и только они представимы в виде х = ~~'.~ у;у;+ ~~", Л;х;, (1.3) 1егь 1игг ~ у)=1, у;>О„Л1>О, )их+ где 1г 01+ = И, ..., т).
Поэтому для любого хшР выполняется равенство <х, х*,> = Х у1<у;, ф+ Х );<х;, х,'> (1.5) 1ри1+ 1мге (1.4) и минимум достигается на точке у1,, для которой (у;,, х,') шш (у;, х*). 1Н1+ Согласно теореме 1.4И5 и формулам И.З), И.4) Р=й(.+К~ и задача линейного программирования сводится к минимизации выражения в правой части соотношения И.5) по (1 и Ль удовлетворяющим ограничениям И.4). Если (хг, х*) ( 0 для некоторого 11нгв, то, устремляя соответствующее Л1 к +, можно добиться неограниченного убывания (х, х'). Если же (хг, х ))О, ) еегв, (1.6) то при нахождении точной нижней грани (х, х,*) нужно положить все Л1 1Е 1' равнымп нулю.
Поэтому ш)п((х, х ): хан Р) = = ш)п) ~ у; (у,, х'): ~~З~ у; = 1, у, ) О) = т1 Ио1 ~ го1+ = ш1П(у1, хг) (1.7) ил 1+ З !. ЛННЕИНОЕ ПРОГРАММИРОВАНИЕ (Зб уууу+ Х Лох1 УН1+ Уе1 о о ,Р 7,.=1, уу>О, Л)~О, УН1+ о (1.8) где 1о = у ЕБ 1 : (у1 хо) = поп (уь хо)~з ае1+ 1о = (у ~1'.
(х;, хо) = 01. Доказательство. Легко проверить, что для любой точки х, представимой в виде И.8), выполняется соотношение (х, х') = ш(п (у;, х'), Уе1+ т. е. действительно в силу равенства И.7) в этой точке достигается минимум. Так же просто иа соотношения И.5) вытекает, что (х, х*) ) нйп (у;, х'), УО1.Ь если точка х не представима в виде И.8).
Теорема 1.3. Если множество ХУ ограничено, то 1) есть многогранник, минимум целевой функции достигается на некотором множестве его крайних точек и любая точка минимума есть выпуклая комбинация этих крайних точек. Теорема непосредственно вытекает иа предыдущей с учетом того, что АУ М„, Ко=(0) и х,=о, ум1о.
Следующая теорема полностью характеризует те точки, в которых достигается минимум в задаче линейного программирования. Теорема 1.4. Пусть хо — точка мини. мума задачи линейного программирования. Тогда существуют такие где Мо — многогранник, а Ко — многогранный конус. А по теоремам 1.4.6 и 1.4.3 точки у, в соотношении И.З) можно считать крайними точками многогранника М .
Теорема 1.2. Множество решений задачи линейного программирования есть множество точек х, представимых в виде 436 гл. гч. Выпуклов пгогглммиговлние числа Лч о= 1, ..., т, что х*+ ~~.', Л;х*. = О, г г=1 Лг((хо, х'г) — ггг) = О, (1.9) Лг гО, г=1, ...,т. Обратно, если выполнены условия (1.9), то хо гн Р— точка минимума задачи линейного программирования. Д о к а з а т е л ь с т в о.
Нусть хо — точка минимума. Расомотрим конус Ко(хо) = (х: хо+ Лх гмР при малых Л > 0). Обозначим 1о=(г: (хо,х,*) — юг=О, г=1, ...,т). Если хт Ко(хо), то при достаточно малых Л> 0 должны выполняться неравенства (хо + Лх, х'г) — иг = (хо, х,") — аг + Л (х, х,*) ( О.
Но легко видеть, что зтп неравенства выполняются тогда и только тогда, когда (х, х;)(О, гя 1о, так что Ко(х,) =(х: (х, — х,'))~0, т. е. (х, хо))0, хан Ко(хо). Инымп словами, хояКо(хо). Но тогда согласно теореме 1.4.9 и формуле (1.10) х* можно представить в виде х = — Х Лгхг, Лг> О г ен Хгг. гмго г ен г о) (1 10) Так как хо — точка минимума и хо+ЛхтР нри достаточно малых Л > О, если х т Кг (хо), то (хо + Лх хо) вт(хо хо) % Ь ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 137 Положив Х;=О, (Ф1о, с учетом определенпя 1о получим формулы (1.9). Пусть теперь х, принадлежит Р и выполнены условия (1.9).
Тогда для любой то зки х ы Р получаем (х, х",))(х, х") + ~~'., Х;((х, х'.) — ао) = о=1 =, х, х*-)- ~ Х;х". — ~ Х;соо = — ~жоао (1.11) ото ' о=о о=о В то же время в силу условий (1.9) (хо х ) = (хо х ) + Х )~~((хо х,,) — а~) = Оо О = — Д ).;хо (1 12) о=1 т. е.
(х, х,*,) ) (хо, х,',) для всех х он Р, н, следовательно, хо — точка минимума. 2. Двойствеинан задача. Пусть вектор уо он К" имеет компоненты йь 1= 1, ..., по. Обозначим ~в <р(уо) = — Д жоао 4=1 о. (и'.*,„. Хь*,=о. о=1 Х; ) О, 1 = 1, ..., т (1.13) Задача максимизации функции щ(уо) на множестве Р» называется двойственной задачей линейного программирования. Т е о р е м а 1.5. Если х ~ Р, уо он Ро, то <х, хо > > > <р(уо). Доказательство следует из формулы (1.11).
Теорема 1Я. Если нижняя грань целевой 4уннции в задаче линейного программирования равна —, то ограничения двойственной задачи несовместны, т. е. Р,=И. Действительно, нз предыдущей теоремы следует, что если Ро Ф И, то (х, х,*) ограничено снизу на Р. Теорема 1.7. Ясли исходная задача линейного программирования имеет решение хо, то двоцственная задача имеет решение Уо и (хо хо) = Ф(уо)' 1ЗВ ГЛ. 1У. ВЬ1ПУКЛОЕ ПРОГРАММИРОВАПИЕ Доказательство. В самом деле, если в качестве вектора уо взять вектор с компонентами Ль которые фигурируют в теореме 1.4, то вв равенства (1Л2) и теоремы 1.5 следует, что ф(уо) = (хо хо) >ф(у*) у*в-=По~ т. е. уо — решение двойственной задачи и выполняется требуемое теоремой равенство.
Теорема 1.8. Если хов1), ув и1)о, то х является решением исходной, а у* — двойственной задачи тогда и только тогда, когда Л;((х, х,*.) — со1) = О, 1= 1, ..., т. (1Л4) Доказательство непосредственно следует нз соотношения (1Л1) и теоремы 1.7. 3. Разрешимость линейных неравенств. Рассмотрим систему линейных неравенств (х, х;)(О, 1=1,..., т.
(1Л5) Обозначим через К~ полупростраиство, определяемое йм неравенством (1Л5). Очевидно, что 1п1К, состоит из то- чек, для которых (х, х1 ) строго меньше нуля, а 1лпКо=К". Т е ар е и а 1.9. Система неравенств (х,х )<О, 1=1,...,т, (1.16) разрешима тогда и только тогда, когда не существует таких Ц > О, 1 = 1, ..., т, не всех равных нулю, что т ,У', Л,х;' = О. (1.17) о=1 Д о к а з а т е л ь с т в о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
