Галеев Э.М. - Оптимизация (теория, примеры, задачи), страница 14

+со,смыслекобщей|х+оо,образом,найтитГ{<с,ж>иначеУпрограммирования(Р).8(Ь):Iыр{{у,Ь)=сопряженнойзадачи~сопряженную8**(Ь)-функциинеобходимог/^0,впрограммиро-второй5($ир{{А*у-с,х)},сопряженнуювторуюзада-(Р).линейногозадаче-=5-функцию—задачевдля.=Ь}нахождения81ф{<у,Ь>ь^Ь}Ах(Р)^сопряженнойкфункции=\ь,хк8**(Ь)8(Ь)}$ир{{у,Ь)-{с,х)=АхпараметрзадачавторойфункциюсопряженнуюкакформеобщейЬ.^|задачейфункциинахожденияпервуюж)ЬназываетсяЛежандра)смыслеАхтГ{(с,:—Двойственнойформеформевтт;->аргументОпределение.в общейпрограммирования8(Ь)черезобщейвпрограммирования(с, ж)Обозначимзадачек>0.сделать(Р**)О,122ГлаваКакмымаксимумзадачаиВыводПокажем,двойственнаячтопонятиезадачакчтобытого,свестиеекоторойВначаленазадачунеравенстваДвойственная{(с,Перепишемэту(с, ж1ж2)-ж-посколькунеужеж2)0.Заменяяктахнатти^вПолучимформе:обшей0,ж3<0.ж1 < 0,ж2<0,ж2ж1 ^0,-Ь,=ж3ж2)+-Ьэквивалентножперепишется—-А*ус,с=тах;->ОбозначимЗадачабудет.^А*у-с.задача:=-ж3+для^видеА(х1ж3 ^форме,равенствопрограммированииIвтах;->А(х1Равенство-Ь,задачузаменимА*уОсследующаяI х2I)А-Затем^(ж1, ж2, ж3)}0),-с,(АбудетнейкА*у^вначаленадообщейвминимум.линейногозадачу(Р**)задачекзадача.насэквивалентную(Р**)программированиядвойственнаясведемдвазадачуе.задачей.у^О.с,=двойственнуюизвестнаужеА*ут.правильно,исходнойявляетсялинейногозадачеформевведено-^тах;вывестикзадаче«двойственности»двойственнойтранс-наобщейвпрограммирования{Ь,у)Длядвойственнойклинейногозадачименяютсяменяетсязнак.меняетдвойственнойзадачидляАматрицанеравенствоматричноеопределен-бисЭлементыминимум,наобладаетслучаеэтомвисходной.кменяетсятранспонированную,программированиеотношениюпо2.3.2.Линейноедвойственнаявидим,определенной симметриейместами,2.ж2-ж1,умножаяж2)-ограничений0.^на>знаквидетах;—»тогдаж3А(х[неравенству=в(с, ж)-Ь,=Ах——Ь.^неравенствоматричноена-1,придемзадаче(с, ж)двойственнойявляющейсязадачейТакимиспользуетсяк(Р).образом,правильно.мыубедились,—»задачеАхтт;(Р**),что^котораятермин(Р)Ь,совпадает«двойственнаясисходнойзадача»Двойственность§2.2.3.3.ВыводЗадачузадачекна5^этомНайдем8*(Ь*)=;шр{=Ь,хх)\Ьаргумент(Р')О,^х-8(Ъ)}=$щ>{{Ъ*,Ъ)(с, х)\+АхкакАх=Ь,=в\Ахх0}^хзир{=(Р1).задаче8(Ь):-Ы{{-с,х)Ь,^-функцию—функциикъ0}^хпараметрфункциюсопряженнуютр{(Ъ*,Ь)ъ6)(Р*)О,^хЬ,=Ш{(-с,х):=рассматриваяпервуюF*,Ахтт;—+8(Ь)через(Р'),Ь,=форме-8р.—ОбозначимзадачиАхтах;—*формеканоническойвканоническойвминимум:(—с,призадачекпрофаммирования(с, х)123программированиидвойственнойзадачилинейногосведемлинейномв{Ь*, Ах)ж^0}}Ь,=|{с,х)+=0}^ххА*Ь*+=^синаче.Найдемт.е.сопряженнуювторую8**(Ь)у8Р>>функцию\ А*Ь*=$ир{{Ъ*,Ъ)Ы{(-Ь*,Ь)=8Р~получаем| А*Ь*тГ{(г/,Ь)=Вывестипрофаммирования2.вдвойственнуюзадачуформенормальнойВывестипрофаммированиялинейногосдвойственнуювследова-и,>(р;*)спрофамми-Лежандра.преобразованиязадачуформенормальнойлинейногозадачидляпомощьюлинейногозадачидляпрофам-еесведенияпутемобщейкзадачепрофаммирования.Вывестипрофаммированиядвойственнуювлинейногодлязадачуформеканоническойлинейногозадачипутемпрофам-еесведенияобщейкзадачепрофаммирования.4.двойственнойО},^сУпражнения1.3.+0}.^с=>задачуа*у2.3.4.с^0}++| -Л*г/двойственнуюследующую8*(Ь*),функциик8(Ь):функции-8**(Ь)=-Ь*,=имеемследовательно,кшр{{Ь*,Ь)-8*(Ь*)}==>ПолагаяЛежандрасмыслевсопряженнуюявляетсяПоказать,чтозадачадля(у, Ь)(с, х)задачи—»тах;А*утт;—*^с.Ах=Ь,х^0,двойствен-0,124Глава§ 3.2.ЛинейноеОбоснование3.1.симплекс-методаТеоремысуществования,критерийрешенияПриведемпрограммированиетридвойственности,важнуюифающиетеоремы,обоснованииприрольсимплекс-метода.Рассмотримлинейногозадачупрофаммирования(с, ж)гдеК",Ес,жа\а?\•••а\пЬОбозначим8ррешенийзадачикоторых(с, ж)Теоремачисленное—(Р),B?(Р)точтоСмножество—К",ЕжКЕдляконечночисленноепосколькузначе-элементовдопустимых|К™хнепусто(с,ж)Зж:<Аха,г}.^конус.изопределения{с1,.

.,ст}:—Ф 0).(Аг§Рчто(Р)задачизначениесразу,выпуклый—дваПустьАщРмножество{(а,г):=Напомним=п.точекчисленноемножествотоРассмотримК(Р),(а|)<=11.,^т=1,. .,=задачисуществуетрешениеОтметимК],допустимыхЕслиееконечно,ф 0).Ясно,\а1)множествосуществования.задачиI..значениет.е.Доказательство.значениеI=Ап8Р.=+со),</а{\а3столбцамисохга.I(Р)Ь,^размеровматрица<&/•••(\8р\К™,ЕАхтт;—»формеобщейванализа.выпуклогоК"Сконечноенекоторое—подмноже-ткЭлементство.=^Ь^,0,^иг\,. .,га,—коническойназывается1=1С.комбинациейВыпуклаяоболочкаконическаяконечнопорожденньш1.ЛеммаККонусДоказательствоВложениевсеобразующие—числаточекназываетсяконечнопорожденный.1.леммы,»?т}>Щ,щ,.

.конечногоконусом.^-где=(С],а[,. .сопе{±^1(..конусаПокажем,,От),,±^„,^о,-.лежат]■вК.Кчто,»?т}Действительно,сопе{±^ь..=1,. .,п,—СК,щ,±^„,изследуетполагая. .,0),A,0,—чтотого,ж=±е,-§ 3. Обоснование(еь.. ,е„канонический—получим,,±^чтоОбратно,жеслиз{с,х)Ноэто/30+какираз/Зт=0>означает,/3+3(о2(-кт& К).{кпк'п:—кксходящаясясодержитК':=^"*;т}пеN(кпК"Е=глибовозможности:к).ИзК1),конусакщшаясянат.<"■',е.к ЕКк=имеем:1п>\-{Ь"'}таккак—кт@К'.IIк"'>=1п'—»+со).0.^I6К'(в0приОткуда—>совоз-случаезамкнутостиВогвыберемпервомсилузамкнуто.К,двеВслучае,втором({&"'}сходя-—кк1"'——0}.>изИмеются+со.=1ктКктК1,6{Ь"}-1щкт-^к-к1"'противномвекторов—*ко-—предположениюк'1кт,+КпринадлежитнеПок'по-тоВкт-^}.=либоследовательно,и,последовательность,невозможнок—Есликт.кт,—которыйпо-0}^конусов,йь..

,последовательностичисло,к'щчислачтополучим,длямножество.-&„,),тпЬИс\,=точек—к\,. .,{^"'}конечноежпоследовательность_——>{к\,. .,{к \сопеКи|вернатпзамкнутоебудетэтозамкнут+е.числупоК"Етеоремавекторыт.(пусть{ж=заданыпустьиподпоследовательностьсходящуюсячтоПустькт}К'конусПустьКонечнопо-индукциейКконус2,>тпвекторОбозначимсуществуетиндукцииделятоподпространство,случаеконуса).проведем1,=замкнутая.{ку,.

.,конечномерноеКтпточкой,сопе=(а,г)то1=Доказательствоочевидно,К(/Зи.. ,рт)=12\хз\№пхг€з),Еслитп-1конуссопе{±^,.длязамкнут.точек.порожденных(/3г=конечнопорожденногоДоказательство.полупрямая,6Значит2.1=0замкнутостиконуспорождающих^п=Г=1рожденныйсуществуеттоАхчтоп^2хз^зЛеммаК,Еа,мы0.=соотношения1Поскольку^жвзятьнадо,гт)(с,ж)выполняютсяАха,тц(а,2Ь..=К,конусаопределенииввекторовдлякоторогодля/?о > 0,. .,некоторыхга;(а,г)К",ЕК")в1,. .,=вектор(ж1,. .,ж„)=базисК,Е125симплекс-методасходитсяк—кт,126ГлаваПоскольку8РсуществуютЛинейное{агшп—(с,ж*)которых(ак,Ь)точекпредельная|&ТеоремазамкнутомуЕ К.—(а, Ь)(с,&)чтотакая,.Аж*а*,=КЕточкаточкаа3.8(Ь)8пресуществует& ЕчтоАщР.выпуклаякакобщейв{(с,ж)Ь|АхЬ}^параметрвформе.^-функцию~задаче(Р).придоказательствефункция.замкнутаявыводитсялегкозамкнутыйер18соотношенияизрассмотренныйконус,К,—■4.существуетПустьтакая,задачейдвойственнойчтопрограммирования/(^о)формеявляется<&,»>->Теорема(Р)однойзначениезадачизсовпадают),(и тогда(Р**)илидругаялибоПо2)такая,ПустьБР5B0)чтоБрдвойственнойпо—(это0Критерийпусто),являютсяАгвПустьсоответственноР**)решениямитогдавитолькозадачах&, $(&Еследовательно,=(с, ж)8(г)8(Ь)значение).Уи(Р**)когда={у,Ь).Это=К™.6гчтоозначает,8**=-со,элементовV-со(это+со20точкасуществуетК™,6гтогдаозначает,что■элементы63леммеV-содопустимых>допустимые—-О(Р),(Р)тогда,а)либо+со,Ь)8**(Ь)по>совпадают.множестволибопустозначение).значениятогдабесконечноеимеетрешения.=чтоозначает,задача(Р**)8*8(г)8(Ь).обазадачизпоскольку4=и+со),—тогдаФенхеля—МородвойственнаяЕ-со,=задачетеоремеи(<ФФ- 8(Ь)0=тогдазна-значениябесконечноелемме8**(Ь)задачиобаиоднойвимеетсо,поп.2.1двойственнойзначение<тоФенхеля—Моротеоремеконечнодругойзначениеэлементов\8(Ь)\проилиальтернатива:либофункция,линейногозадачконечнонесовместна,замкнутаяпрограм-(Р")следующаятогда1) Пустьвыпуклая—линейногоу^О.допустимыхмножествозадачаДоказательство.5(иконечнойот/.Егзадача:двойственныхпарыместоимеетсуще-иV—со=задачеА*у=с,Дляикследующаяшах;двойственности.программирования/(г)Тогда—со.=функциязамкнутаявыпуклая—чтообщейвК"-»К/:2цточкаНапомним,$Ксуществования.ЛеммавПоэтомуозначает,программированияшГ:=аргумент—выпуклыйтеоремыЭтоЬ.су-+со,—*последовательностьмножеству.множества^тоа,й■леммы—=:приачтоозначает,2Ь}^-»ацлеммеопределениюАх8Р,—черезДоказательствоКпоАха,={а*},(этоЬ^ТогдарассматриваяЛеммаилинейногозадачекобозначили(Р),задачи(с,ж){ж*}доказана.ВернемсямыЭзж:по^существованияВ п.2.3т.е.программированиепоследовательностидлягде2.2?(Р**)).соответственновТогда(Р)задачахх,^точки(жЕАщР,§ 3.ОбоснованиеДоказательство.(у,Ь)иНеобходимость.=Значение8р..Аналогично,задачи(Р)двойственностиПустьэтомпри(8РДостаточность.ВозьмемПусть#(Р),6жАхА*Ь,^.у0.В(г?,Ь).=1>(Р**).2/ 6условийэтихсилу(у,Ь).(с,ж)иобаиконечно=$>.=теоремепоХ>(Р),6ж^г/с,=Значит(с,ж)О(Р**)6уэлементы(с, ж)итакжеСледовательно,допустимыечто+оо).<задачи8Р..).1>(Р**)Б(Р**)у 6тогда6у(|5р|конечно=произвольныеозначает,тогдадвойственнойсовпадаютАщР**,6уАх%Р,6жзначениезначения127симплекс-методаЭтожнаиг/имеемИзэтогоЭтосоотношениявытекает,3.2.СвойстваАналогично6)линейного()6хуЕАх%Р**.чтотточекдопустимыхзадачуV(с, ж)=доказывается,множестваРассмотрим> (#,(с, х)чтожбАгзР.чтоозначает,вканонической6К",программированияформе(с, х)гПредложение1,.