Галеев Э.М. - Оптимизация (теория, примеры, задачи) (1050545), страница 19
Текст из файла (страница 19)
.,т,*=;=1,. .,п,(а)(Ь)(тг»т^2<1гп.2.5)М).—(Ь, V)+2_^:-+й{Щ1=1двойственнымикоторойВкнейбудетзадача(о, и)вДвойственной'.77=1=1■=1(смч1>2Ъ]=/10..\10100001....11000000являются............(Р**)задачиограничениявиде0010..00000100010001110011001................->тах;3=1переменнымиматричномЪ]У,2_^имеют0\01щивид:/00спс-пс22ит1Щ001потенциалы/С2т»\§ 5. ТранспортнаяМатрицаограниченийограниченийматрице5.7.методатранспортнойзадачиКрайняязадачеиV])+базисных+Щ0,>^V]г1,. .,=т,1,. .,=тому,здругой1,.
.,—зстороны,п,1,. .,=а?утранс-А> 0.:=сцЭтоА^+щТакиму}-0базис-дляАусловиев(г,з)& В,Разбиваяпоследнююнасуммупоследнееучитываяидве0тоV■)X^^.+(а)условия(Ь),иравенствопт;'-11=1^двойственнойМ*продолжимс,.,-=Следовательно,образом,прис^-сц=допустимым=чтоозначает,В).являетсяпоскольку0.>чтопричемобозначимп.(и,«)вектор(Р**).САтакие,индексовт,чтовекторПустьбазисныхгсц,равносильнозадачекогдащ,ь^невырожденнойврешениемтогда,потенциалы(множествог,зявляетсятолькома-решенияДостаточность.найденыхточки(щхтогдакотношениюпо(Р).задачипотенциаловточка(Р)Доказательство.длятранспонированнойтранспортнойявляетсяисходнойОбоснованиеТеорема.транспортной161задача]тОтсюда'(Р),задачепо—Необходимость.А^условиех+1^-В,60,хгде—товектор1=хй В.существуетВозьмем{2,у}выбираетсяе.У]Ь,впротивного.А>мо<иначе.6=Ч,+прямой,0.Докажем,Допустим,ПосколькуI >малоедостаточног,зг(а, и)(Ь, »>.зада-(Р**).план.по=решение—задачеотт.(г<ь.7о)3.1]Р+оптимальныйдоказательствовыполняется,не(г,з)длярешениеща{двойственнойвПустьПроведем0.п.решениякритерию(и, V)а^Гпотенциалов,методуВ,3=Зо,тогдачтоэточтоД,^0 так,=чтобы01622.Става(а)-(Ь)УсловияЛинейноепрограммированиеЬ+хвекторадопустимости(Р)задачевравносильныусловиям:У-11=1Посколькус,у(с, х+1)-(с, х)Ду—+Ду'=с,^т(с, *}=7=1»=1т»«=1Последние1цДу^у0=(г,])при(г,])& В,ф (ц,3о)-(с,х+г)-(с,х)значит,хненашехеслиоптимальный—5.8.ЗадачаПустьИзвестно,мест.получитгкакиезт0.^Д,оуо<о]-енадокого6противоречие.0 невернои,вакантныхфирмаместочтобыназначить,являетсяназначениичастнымфункционала,максимумепкогдаслучаемо^=Ь^п:=^2^2^х^-(с,х)<=11=1>=1Задачипредварительно3=1оперейдяназначениитакжеотВ,наибольшей?быланазначенийонана1,.
.,п:т(г,])■служащихслужащегодолжностизадача=этомвприПолучилиДг-гопослезадачи],. .,т,=Наобразом,0=соот-силукак<0,существуетнанимаетназначениифирмывтакПримерприприбыли.Такимобразом,обязательнотофирмачтотранспортнойТакимпланом.назначении.некотораясуприбыльобщаяонулюнулю:чтоплан,1=1(го,3о),ДуФ=Акк1ккдопущение,1=равняются{%,])равеноптимальнымявляетсяСледовательно,Усумме0 при==пУ=1сомножителейизодинпроизведенииэтойвСлагаемыев>))'«+т»1=1слагаемыхдва(*).соотношения(щ+т1=;топX! X! (Лч=т(м< +»,-),+х)кмаксимумт-<С.методомрешаютсяназадачи=X! X!потенциалов,назадачеп~ЪзХЦ->■ПШ1.минимумпредва-=1,§ 5.
ТранспортнаяПоэтому,еслибылиплатежнойвпритоСу,задачиматрицерешении163задачаметодомназначенииостоимостиберутсяпотенциаловстоимости—сц.Пример.5жп+4ж,27ж13++Ж12^И+Ж13ЗадачуРешение.нег,зможноа{,Ь^,величины46назадачиотплатежнойматрице7максимумПостроимчислотак,чтобыбазисев-4-7-7-3угла»+пминимальные—первоначальное1рас-базисными,считать=3+3—1чтобы5.=стоимости:1100Значениефункционаларавно1Построим—14.«2«з1==-3С:матрицу«2И,=0-8=«з1=_д-81-4-72-8этомзнак:_2будемтпприминимум,на-11былоимелионизадачесвойэлементанулевыхэлементов3«Северо-западногометодупоДва1:равны2к-8платежнойвидевонипоменяютстоимости-6распределение.тах;7118Перейдемзадатьпоскольку5в->■1,2,3.=назначенииоуказывая2ж33+1,=^0,хцматрицы,11ж32Зж2з-11-2Выберемих1642.ГлаваЛинейноепрограммирование'ВАматрицеС=С-0-2=\АпнаА,-,'гшп=место-8=-5минимальныйэлементО/начальныйвнебазисногонулевого-8Л0ОДобавляя0.<О4элементапланраспределения*,величинухцвторойполучимплан:\-101111Ь0 +Величина-22.двухобнулявшихсяПостроимбазисных0—3-6-11-8А21наплан=ДцшместоС——2=0.<небазисногонулевогоС—I—V—-10040\20003|Добавляявоэлемента0Iо +1.=Изэлемент-24.планраспределенияI,третийполучим011 -*равноэлементвеличинуЖ21двух0гПостроимматрицу0=И2=Из=_^элементоввЗначениестоимостью.функционалаС:«2щ1базисныхобнулявшихсянаименьшейс111-*Величинаминимальный8/второйдолжностей:распределенияоставили-7о/Аматрице—7=о_ВЩ4—=-8=_дИ2=1избазисефункционалаС:«2и,вэлементовЗначениестоимостью.матрицу=01наименьшейсэлементравно\-1Из4=1.оставили0-8=-7=-5-8-7-6-9-8-8-11-10базисе§ 5.
Транспортная/0_ВДматрицеС=С-2\0Значитнайденноеисходной5.1.5]2жцЗжп5ж41+4жв2ж42+++Зж21+Ж14+8ж4з4ж22+2ж44+значениеиЗц+Ъ\2+ХЦ+Хи=321+»22+Ж23+324=ХЦ+Ж32+ЖЗЗ+Ж34«41+«42+«43+=~«44ЖцЗжп++10Ж132ж41+9жз4++6жи+х424жц+9ж42+7Ж21Зж4з+хц+хц+хц+хи=321+«22+«23+Ж24=331+«32+333+334=341+342+343+344=ЗжпЮж4зЗж13+Х\\++3з+бЖп+++Х\2ЖK+Ж+з2Ж138жзз331+Хц=332=Ж13+Ж23+333=6,Хи+Ж24+Ж34=++4ж2211,2,6,7,1,2,3,4.=2ж224ж445Ж23++8Ж245Ж31+2ж32+гшп;-*•хп+х21+хц+х41=ХП+Х22+Ж32+342=Зп+Ж23+333+343=Ж}4+Ж24+Ж34+З44=14,И,8,15,1,2,3,4.=5ж2з+ж^8,^25жз1++++3,1+Ж21+Ж31177!г,4жз2+6+ЗЖ25бжзз+2Ж15+Ж142жз4+5жз5+-++Ж14+Ж15=322323+324+325=332+333+334+335=Жу^О,1=1,2,3,+Ж41=с5,Хп+Хп+Ж32+Ж42=313+Ж23+ЖЗЗ+343=1,2,3,4,=Ж13+321+++Зц+Ж12+Ж21Ж226,18,14,Ю,+жо->0,2жц++пгш;-+3ХПЖ12г,;6ж21+7,8,5,%,]+2ж2з+ппп;-*•жо>0,5.4.оптимальнымявляетсяЗадачи2жзз5.3.неотрицательны.24.Яц>0,5.2.элементывсе8/0распределениеравняетсязадачи5.9.0\40I=165задача;9з2_15П'1,2,3.=4Ж22+1ОЗЖ23+4Ж24+пйп;13,И,27,;=ЖB+Ж22+332=Ж(з+Ж23+333=ХЫ+324+334=315+325+335=1,2,3,4,5.7,14,9,6,166ГлаваОтветы1.1.1.2.1.3.1.4.1.5.1.6.1.7.1.8.1.9.4.1.4.2.Линейное2.2главызадачамкпрограммирование6 Ащ;4.5ШИA,3,0)@, 3, 0, 2), B, 1, 0, 0) е А1В Р; Злах4.8тах@,4,0,0)еАгё;5.$„,«B,0,3,0)еА1в;8.5шахE,3,0,0)еА1в;3.е Лад;^пшхA,1,1,0)15.ЕАщ;5,^E,0,3,4,0)2.ЕАщ;Зш№A,2,3,0,0,0)5^=10.еАг§;E,0,4,1,0,1,0)6еАщ;8тахЕйг,E,2,0)E,2,0)=5.=======A,0,2)еЕхгг;93 н14.3.(о.-т-Д^)4.5.@,1,1,2)4.6.2?8тах+оо-+0D,0,2,0)^щахАхв;еA,2,0,3)Езйг,=Ф-+оо.—*бЕх1г,е=2приA +10*,*,2+^*)}(A,-10,1),+оо,=13.=8аАщ;е-оо.=^ч4.7.@,0,0,0, у) Ехгг; 8тах@,0,0,*,?(A,2,3,4,5),е@,0,10,0,0),4.9.(О, О, О, I, О, I)жц<?5.2.жц5.3.хц5.4.жц4,=5тш=146.6,=-=Езйг,Ж]4=3,ж22=11,Агё;8тях(О, О, О, I, О, I)ж2[2,=+оо►ж238^Ащ;6,=+оо.->-10.=6*приуж3]==2.5,ж428,ж41=2,ж44=4;2,ж44=8;46—■ее38*10+^*))+A0,0,0,0,10)4.8.5.1.+оо,=8,10,ж2215,=ж13=ж24ж233,=ж23==7,2,хъх11,ж31=хц6,—5;81т=ж33=5,ж32==114.=7,ж34=9,ж35=6;Глава3ВариационноеНачалуБернуллиИ.1696плоскостипокоторомуизточкикоторойпоставленаЗдесьифункциитак,пользуясьбылаГалилеятяжести,М,двигатьсяВводявплоско-горизонтальна,аосьхпадающеготела,скоростиоформализованнуювыписатьможноспускаясьначаввремя.IосьзакономсилыточкадалеебылооснованозадачеймыВприсейчастретьейивариационногоониявляютсяслучаиконцамиизадачатакжеРазвитаяпрямыхусловияхза-методовобзадачанаисчисления,такжеиБольца,болееслучаямиЛагранжасовышезаданныхзадачачастнымизадачиЛейбницаэкстремумеконцах,явля-рассмотрениюкперейдем.исчисления:частныеаРешениеосновывариационногоприводятсяглавеБернулли,ломаными.заложилаидеяВыписаннаяфункционалапростейшейНьютоном.кривыхэтаисчислении.интегральногокоторыхэтойпроизводнуюИ.самимиаппроксимацииЭйлера,вариационномявляетсяозначаетрешенаЛопиталемнаработахвбылазадачаЛейбницем,Бернулли,затем(хA))функциейнадг.поПоставленнаяВсекратчайшеечтобыАМВ,путьтелотяжестизаприглашаютсяВ вертикаль-задачи:постановкувВточкидодействиемподЯ.собственнойкоординатвертикальна,Определитьработатолчокбрахистохроне.оВ.идалакоторойрешениюзадачаАточкидведойдетикзадача,действиемподсистемувниз«НоваягодаданыА,исчислениявариационногопоявлениявматематики»,вертикальнойплоскостиисчислениестаршимирассматриваютсяпроизводными.другиезадачиэлементарныезадача.изопериметрическаяобщейЛагранжа.задачизадачасподвижнымиКак168Глава§ 1.Вариационное3.Простейшаязадачаисчислениявариационного1.1.ПостановказадачиПростейшейзадачейэкстремальнаяисчислениявариационногоIЬ{1,хA),Щ)=Л-^следующаяназывается([#о,Спространствевзадача.7(ж(-))исчисление],К.):*1ехИг,хЦ0)трехпеременных,х(и)х0,=(Р)хх.=кЗдесьЬЦ1,х,х)=#онавкраевымиликонцах,С1([^о,€хусловиям:*1],К),ж(#о)конечным,идиф-непрерывносредирассматриваетсязадачеинте-называемаяфиксированнымпредполагаетсяфункцийусловиямудовлетворяющих=хA\)жо,функцииТакиеЖ[.=допустимыми.называютсяОпределение.Говорим,локальныйминимумсуществует6функциихНаряду0>есослабымсредивименно,Однако,какболеесредифункций,вВыводНапомним,леммыПусть(Р)—функцийфункция(&€ЭйлерахвРС1([10,5главеимен-гг]).п.I.(глоэкстремумабсолютнонепрерывныхопределен.спомощьюисчислениявариационногоМосех1гР),^]),аабсолютныйвсех—1уравненияданомини-абсолютныйдоставляютфункционалкоторыхТеорема.'* \УеакС1([10,доставляющиеРС1,иликлассаосновнойзадачеС1широкогона1.2.2>функции,правило,экстремумСильныйфункцийбудетэкстремумаис-расширяетсяэтомзадача.чемпространстве,сильногоопределение(глобальный)вариационномкусочно-дифференцируемыхпространствеСтрогое6.<Прирассматриваетсякоторыхеслидопустимойж(-)||С1([М1]J>-экстремум.широкомМостт'*Р,любойклассическомвсильныйболеевищетсяминимумДляслабыйдоставляетеж^(%(^))| ж(-)экстремумом&пишем^которойдляизучаетсяфункций,класси^(x(^)}что#(Р)),(х(Р),задачетакое,функциядопустимаячтовтакжеисчислениив1\]Экстремумг\.<дифференцируемыхи[Ц,Отрезокгрантом.функция—доставляетфункциислабыйЬ,Ьх,Ьхлокальный—экстремумкакнепрерывныслабый.что!Ы!с1([<„,<1]):=тах{Ы\с([10,11])А\у\ с([10,11])},где1М1с([*0,*1]):=§функцииПростейшая1.трехЬхA)Здесь(ввпервыеподозреваемуючасть,точкефункцииС1сВозьмем^]K'-Со([#(ъчтовариамыметодомграничнымизаданнымидопустимыминазываютсяПосколькуДо-экстре-функ-фиксированнуюно6назы-БЕ(Р).обозначаемпроизвольную,х(Р),Е(Р).условиями),задачиобозначаемэкстремалейдопустимыхДоказательство.еМетодЭтимЭйлераЭйлера,уравнениюМножествоЛглавнуютем,нуль.вэкстремалей(классаудовлетворяющиеподо-функционалауравнениюМножествоэкстремалями.экстремалями.СамЭйлера.кривую,Эйлера.удовлетворяющиеДопустимыекривыевоспользовалсяиобращатьсяобщепринятым.сталвпер-удовлетворятьварьируяприращениядолжнауравнениеФункции,году),вариациями,Лагранжем,далеефункциюиз*=Фбылоуравнениемегоназвал1759(ввариацияпредложенныйвыведемназываютсядолжныназывалкоторыеэкстремумавариации,аппроксимируяВыделилэкстремум.налинейнуюОн,былиЛагранжг^щ.порядкавторогокоторомууравнениеэтовыводилудовлетворяет—Щ,х,х)ах:=Эйлером.уравнение,Впоследствииэкстремали.ЛагранжхЬхA)аналогачно,выведеновывелфункцияТогдауравнениегоду)1744Ъг])-*=*(<>дифференциальноеломаными,иС'([$о,Е-—Ь(г,х,х)ах:=ВыписанноевЬхпеременных,Эйлерауравнению169исчислениявариационногозадачаМосехйР,функциятоодногопеременного«1<р(\)имеет./(ж(-):=экстремумАЛB)).условий<рвизвестнойиР(г,анализаизАполагая=0,Со'([*о,<!]):={*(■)еС'([<о,<1»Ь,х,Н,^^]х! М<о)=А(<1)=о}.VчтоРи,подЛ+следует,[—Ао,Ад],0.—получаем0\НA),хA)функции<р'@)Ферма='+дифференцироватьможнотеоремепоЬ(г,х(г)=на(Действительно,[1о,нуле.прямоугольникетогдаА)наложенныхвнекоторомНо<рПоложимгладкости,теоремеинтеграла.)функцию0.=дифференцируеманепрерывныпоАприИзфункцияАЛ(-))+[=ДифференцируяпзначитзнакомР\1703.ГлаваПроинтегрируемСо([^О)1\])(здесьA)соотношениивтеоремы,ЛдляЕС'([#о,ввидеЬ±чтоЕ1\\))'-и1/Ь±КсНСвободные11±йН=Л(^)=IЛ-ТогдаПустьфункцияотрезкенанепрерывнаа/-перепишетсяоV[1о,^]е^([«о,(^нулю,равняютсячастямлсй([*о,е(аС"([#о,Етак*!])■(леммаисчислениявариационноголемма=A)соотношение=Основная0Ь±поинтегрировании0.=|'Ь*{1)Щ)=причленыЛ(*о)какслагаемоеусловиемпользуемсямыисчислениепервоечастямпоВариационное*]])B)Лагранжа).м«1в(*)А(«)Л=0ЛV*!])•«оа(*)0.=ДоказательствотЕДля[т0,отрезкет{\ЛПустьиаA)ЕнулюравнаяС0>[*о,^])ЛЕСо([*<ьнекоторойвокрестностинекоторойввточкиее,*1])«шапочки»,—/С~точкесилунепрерывт,например,Т1J>вIфункцияокрестностинапример,т°J(*"допустимаяэтойвположительная—типа-ТогдаиФ 0Тогда0.>*\]-Со'([#о,внеа(т)пустьопределенности,функциянепрерывностио(т)Предположимлеммы.(*о> ^)-о(*)л(*)-л],функция,леммесн[т0,* е>ноо,«очтоПоЭйлера.леммеЛагранжаЛеммалеммы.условиюпротиворечитизсоотношенияЛагранжаB)доказана.вытекаетуравнениеЭй■§1.3.этомлеммымывыведемналоженныхвместо(жокрестности3:МосехггР),расширенногоЬхудовлетворяетГ±х^(Ь,ЬХ,ЬХ(Ьхфункцияэкстремумнекоторойвнепрерывны—ЭйлерауравнениюДюбуа-Реймона.локальныйЬ,ЬХ,ЬХдифференцируемаянепрерывно—уравненияслабыйдоставляетфункцииграфикаусловийЭйлераменьшихдлявыводелеммуиспользоватьфункцияеЬ.интегрантбудемПусть(Р)задачеЭйлераПриуравнениенаЛагранжалеммыТеорема.хЭйлераДюбуа-Реймонауравненияпункте171исчислениявариационногозадачапомощьюгладкостей,вПростейшаяВыводсВ1.С{О{Г^))).С1(Цо,^^]))Тогда€еифункция(льВозьмемДоказательство.Нфункцию^]).Со(Цо,бпроизвольную,фиксированнуютофункцияно&Поскольку\у]осех1гР,ефунодногопеременного(р(Х)имеет1{х{-):=Изфункцияусловий<ризвестнойНоинтеграла.)ЗдесьпомыГ(ЬЯA)ЩУравнениеравнанекакможем,непосколькучастям,=A)означает,<^'@)Ферма0,получаем+Щ1)Щ)ЛЬ,х,Н,VчтовариацияпоЛVКеебратьЛагранжунулю:ЩЦ-),Н(-))=0С10ф0,Р[-Ао,Ао],0.Дифференцируя*,]).^([«о,иЕ\значити,поддифференцируемостьзаданачтоследует,функциих=случае,предыдущемв0=Л+дифференцироватьможнотеоремепоАА(*))+ЬA,хA)=(Действительно,[#о, 1\]нуле.анализаизАА)напрямоугольникеполагая=РA,ЩАА(«),+наложенныхвтогдаиЩПоложимгладкости,теореме<р0.=некоторомвфункцию[ Щ=дифференцируеманепрерывныпоАприэкстремумАЛ(^)).ХЩ)+знакомк])-A)второйинтегралфункциифункционалаЬхЦ)3172ГлаваВариационное3.ПустьДюбуа-Реймона.ЛеммаисчислениефункцииС(\1й,€ай,а\1\\)и1((ах{1)К{1)во(*)А(*))+МО=VКб«офункцияа(хЬа^)аоB)+ИзС'([*0)ба,О V=М)м[2(ь2 б^](аналогДюбуа-РеймоналеммыдифференциальноевыполняетсяиуравнениеЭйлера).уравненияA)соотношенияутверждениеследуеттеоремы.ДоказательствоВозьмемлеммы.функциюС1(Ц0,€р1\])такую,чтоОна1-готаксуществует,выборомаконстантыЕдифференциальное—удовлетворить1\])Сд([#о,уравнениеточностьюсопределеноможноНфункциилюбойайA)—которогорешениепорядка,рA)какдовтороепоТогдаусловие.леммыусловиюконстанты,длявыполнятьсядолжноравенство«11*'-(а^Щ)И+ЩрA)=I1I(а1A)-рA))Щ<И=р(т))йт.р(Ь)ЩеИ=0.B)*0*функциюВозьмемй(#)/=(а^т)—Тогдака\—ир—«окбопределения^([^о,*11)-Действительно,к,функциий(^0)равенствоЩ\)равенство0=0=ввытекаетиза!едуетопределе-функциивыборасилур:«1Щ\)~Лемма-=рA).Дюбуа-Реймона,Р^))B),равенствонятьсяахA)\ (а1@Таким(ИтоЗначит0.=(агестьобразомавместесрJ-С\[1а,ба,функциидлянейш1{[)итеоремакОтсюда0.=и-доказаны.—выпол-должночтоследует,а^)+ао{1)=0.■§ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
