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

.симплекснуюУкажембазису.способфункционалаа10,векторисключитьвекторовЗначениевекторамит.е.Элементывырожденныеп.-^0Д,0.Построить3.3)лежащиеизставимПустьназываетсябазисныхчислабазиснымивеличинуновомуЯсно,тоиндексом.Есликачествева-'0.а19~\а:'0,а">+\. .,ат,потох^авекторновыминап.^значения^таблицы.вместопотакимразрешающей.г,Уо^столб-_/,любымсЭти\+разрешающимзначенияхтаблицы.Элементстроку.симплексной0.>называетсязначенияхлюбуюсоответствую-тчтоназываетсястолбец>Ясно,несколькихсимплекснойстолбцевектора10>х^0хПппоследнемСтрокавыбираем0.<./одостигаетсяхгГД,-о=настолбцаразрешающегонаД,-гшпачисла.индексуД,-гшпчисла,отрицательныесоответствующийЕслипрограммированиеположительныечтоСтолбец,ЛинейноеимеютсясодержатПредположим,в2.Глават.е.задачи.решениюточнорешатьЧислотакположительныхжеивы-1.§крайнейкоординатточкибазисныхчисломожетТеоретическиточкеиэтомзначениеважнейшихизданнойЬ],.

.,Ьт.производитпродукциикаждогопродукцииз-говидаравнас,-.каждогопродукциивидалНадоС}Х$.найтибудутозначать,полностью.ЕслиМожно,т.задачу,частьбытьможетЗадачанаприбыль-\а"хп+Ь{=полно-израсходовантоа}х\+а}х2-\про-план\-а?х„^Ь,-,производственнуюсмешаннуюбытьдолжнаполностью,израсходованачастично.израсходовананезадачу,ноа\х2+типанеполностью,рассматриватьресурсовчтобыминимаксПриведемпрограммирования,жевеличинутакой,а}х1г-гонеравенствамтаккоторойвчастьж„)еди-х$составитизрасходованыудовлетворятьдолжен,.

.ресурсбытьмогутресурсыизвоцстваприкаждогоединицыизготовлениипредприятияРавенствавесьпроизводиспользоватьреализацииот(х1,. .,максимальной.чтоп)объемахвНавидов.пред-натиповтребуетсяПрибыльСледовательно,прибыльтп1,. .,производствапланбылапредприятия(сырье)—а\.объемевтипаПустьзадача.продукцию(звидаз~гог-гоматематическойпрототиповресурсыПредприятиересурсаугодноскольпутемпроизводственнаяявляетсяпроизводственныеединицы■--Перейтизадачи.экономическихзадачиимеютсяпредприятии,:0.=задачаОдним^22,-0можноданныхПрираз.числозначит,и,невырожденнойккогдакрайнейПримерымоделиединиц1^ранеебесконечноеменяетсяненачальныхПроизводственнаяпроизводствочи-величиназацикливание,происходитьможетзадачи1.3.А,рассмотреннойужекфункцииизменениянот,меньшематрицывозможнозадачахприходимвозврашениецелевойвырожденнойотмалоговырожденныхэтаповэторангунулю.внесколькочерезбытьможетзадачахравняетсявсегдаравнойоказатьсятакихввекторов113Симплекс-методзадачейявляющуюсязаменыпутемпеременныхлинейногопрограммиро-сводящуюсяклинейногозадачепрограммирования./(ж),ж„)Пустьх=(с3, ж)(ж],.

.-Л3хтах{2)(ж),. .являетсяп,Ь 6Вотличиеотлинейной.Покажем,с*К™,6Ах=задачаК,&5=Ь,ж^к,1,. .,=А—(Р)0./(ж)функция(Р)1(х)ЗдесьзадачупрограммированиячтоЛ3переменныхпфункций.следующуюпйп;линейногозадачиж,Рассмотрим—>функция—линейныхфункции,Кт./ (ж)является,^(ж)}максимумомлинейные—тматрица=эквивалентназадаченелинейногоявля-114ГлаваЛинейное2.программированиепрограммирования1в(х)^.хп+иж„+1-итпп;Действительно,чтоСчтовектор/(ж)<другойдопустить,/(ж)/(ж).<АР'—втоЯ(Р')6+ж3-+ж4-тах;начальнойРешение.крайнейБазисныеточкойжа31а4-1таблицыстолбцыа13, разрешающаявидно,и32вчтоа2.Возьмем1, 2,3,4,@,1).=базисаСоставим-11базис001-300столбцастолбецопределенностиЗаменяемвбазисеа4вектортаблицу:симплексную11а2а3-1а4а3143011а21321017511230032д3_1разрешающегоа1ж&1-32са41качестве-1а3-2вторуюстроим1-1дляа4.строканового=а4иа21ддляA,0)11-22ипрограммиро-3,@,0,1,3).==а1хъа3==2базисI^таблицу:сИзгж4векторысимплекснуювзятьчто(ж,ж„+!)=»ж„+,линейногож,-+х2первую(Еслитакой,Ж2-заданной<ж^(Если-О(Р)6формеканоническойх2сО{Р)ЕжзадачуневырожденнуюжАг^Р.6жтоиАг§Р'.векторвектор(ж,/(ж)Решитьсуществуетсуществуетвектор6(Р')0.^х/(ж))противоречие.)& Аг^Р',—Ь,=:=то(х,хп+\)противоречие.)1.(ж,ж„+1то^ Аг^Рж$ Аг§Р,Значит,Примерпрограммирования=»Ах^ Аг^Р',еслистороны,Ачто(х, /(ж))/(ж)Ат§Р,6жеслидопустить,такой,з=1,.

.,к,можноанавектор.Тогдаа~§ВекторзадачиДЕсличислоПример+Х\@,3,4,0)=столбца+Х2линейногозадачу+жз+ж4+х\заданной+Ж5Ж2+Х2+—+же2жзтах;+Ж4Жз4-ж4а5@,0,-1,0)=точкойБазисныеЖ5жF,1,2,1).=Аьэтогосводимпреобразованийна000ж63,1,1,—=а2A,1,0,0),=0-10Аьединичнойпреобразованийобратнойявляетсяииеди-элементарныхпутемрезультатевматрицыматрицу.АьматрицунашукПолученнаяобратнуюнеедляматрицы:двеединичнойместе0матрицустрок.матрица+найдемрядомДалееединичную.=1поэтомузаписываем2ж^9,6,1,. .,'~единичной,являетсяне4~==—Матрица1ДляЖбгA,2,0,0,1,1).A,0,0,0),=а1векторыа6ибжб++—0,^Х{Зж4+ЖзкрайнейначальнойРешение.@,3,4,0),точкежепрограммированияж4стойксимплекснойпервойвбыпришлиторешениемявляетсяшагов.Решить2.хразрешающегоа1,столбецбольшеезаточкапоэтомукачествеввзялино115Симплекс-метод7.=бытаблице0,^8тахи1.ма-нашейкАь.матрицеНапомним,чтоа)перестановкаЬ)умножениепреобразованиямиэлементарнымистрок;двухнастрокис) прибавлениеявляются:матрицыкодной10числоотличноестрокедругойстроки,0\/100отинуляумноженнойлюбоеначисло.'116000-10100010010,002,00001010010101001-200001000100-110000100/10-5\0|00@101/~Ч010000010000101-1-0-5'[01000\0000-100-20ч0110\01/01-1I "Ч1-15010-10-10021,116НапервомвычлиэтапемыктретьейстрокеТакимобразом,ДалееНапервойизстрокивторойизэтапе-1,напервойизтретьемстрокичетвертую,вычливычлистрокичетвертую,четвертую.удвоеннуючтополучили,а3, а4векторовразложения'1хъстрокутретьюприбавилинаходимпрограммированиеэтапевтором5.наЛинейноеумножилиНавторую.умноженнуюа2.Глава=0-1010-100-12а1, а2, а5,базисупоа-5,00010-51-1а;1 а4=010-100-12.0001РазложениемкрайнейЬвектораСоставимточки.являетсяРазрешающийразрешающаяа2а31101а212011а51100а6110005111000а5иа6.а4.столбецстрокаВозьмема.В0000011011011-111-200разрешающейкачествеопределенностиЗаменяемвстрокистрокубазисевектора6а5-3-1для111а41дкоординат11а12строки1а1хьненулевыхтаблицу:симплексную1сбазисA,2,1,1)векторпервуюанаможноа6.векторвзятьТогдаIа41,=идля§базисановогостроимтаблицу:симплекснуювторую11сбазис117Симплекс-метод1.а3а2а1хъ111а41а6а5а114101003а212011000а5100001110001017111113000002а42дДВекторзадачи0,^точкапоэтомуб^щи7.=положительныежПолученная-1D,2,0,1,0,0)=точкаЗначит,решеннаякрайнейточтсой.координаты.-1решениемявляетсякрайняятолькосодержитнами1триявляетсязадачавырожденной.1.4.ЗадачиЗадачилинейногозаданнойпервоначальной+Х\1.1.Х2+Х2—х\3x1х2-+1.2.—+ж3=+хъ=+Ж2+Ж2—1.4.хт,+2ж2+1.3.++жг+Ж2+Ж9++жг+Зж2+—Зж2+=4,=1,-+ж0ж4=4гож4-+тах;ж,-^0,ж41,=+Х4+5ж3+7ж4+9ж5=+ж4+2ж5=ж2+жз+ж4+Ж3+Зж4Х\+Х2—+тах;=3,Жз+Ж4=Жз+Щ=г=1,2,3,4,г=1,2,3,4,=A,0,0,1)-5,=жз«2=1,2,3,4,@,0,1,1).ж,-^0,тах;4,+г=форме1,2,3,=жг^0,гпах;=жз++~~*ж4гЖ4жз+Ж2Х42ж42ж4Ж1Ж1=@,1,1).+ж2—ж0+Ж1-^ 0,ж3352++ж,-2,0,5ж4+жзтах;—-Жз-+-1.6.жз4ж3++++—-1.5.Зжз5а?зканоническойвпрограммированияЖ5—+хо=@,1,0,1).тах;ж,-^0,жо=@,0,1,2,0).19,2,1=1,2,3,4,^О,1,1,=@,0,0,1).г=1,.

.,5,сза-118Глава_"2ж2Х\+х1+3ж22ж33ж3++++2.Линейное+6ж5ж4Ж+5ж+2жхх-2ж!_++Щ+ж4+«з+Зж4+ж2хх+Ж!++ж3х2+ж5--хъ+Зж5+ж5Зж4++ж^О,Зж3+ж3+2ж4Зж4+2ж5+х5линейном-жо=(О,1,2,О,1).тах;ж;7,-2,5,х0-+х7-+тах;+х7=8,+Зж7+-г1,. .,=5,6,1,. .,=@,0,2,0,1,1).11,5,=ж7г^ О,=A,0,0,1,0,1,4).анализа.выпуклогоК™/:/функцииИзЛежандраК-+(илифункциейсопряженной/*(ж,у)функций(какмножествомСледовательно,функцииследует:=зирважнойвторойявляетсяонамножество).полупространств).определениясопряженнойявляющаясясопряженнойтеоремазамкнута/.к(т.линейногозадачдляпрограммированияанализа.выпуклого6,п.(/(ж)сопряженнойивыпукла/*(у)},—[Гл.Фенхеля—Моро.второйсвоейсо—ИзсопряженнойследующаяТеоремамножеств{{ж,у)двойственноститеориивыпуклымявляетсяЮнга:неравенствоназываетсясемействаграньверхняянадграфикфункция.выпуклаяуВЕефункцияназывается—выпуклых—/**(ж)Функция/(ж).пересечение/*/*что—/)квидно,ЛежандраПреобразованиемфункция.некоторая—определенияаффинныхзамкнутоеО,программированииЭлементыПустьи2ж6Зж6+2ж6+3ж7=15,Зж62ж6-жо=Преобразованиекогда==ж5-^Двойственность2.1.совпадает=ж6-1=1,.

. 7,в/*,2ж6+ж2к-+х6-2ж2§2.3,+Ж!+Зж2+2ж31.9.=Ж5+2ж6ж4+ж318,13ж5ж2ж;тах;=8ж+ж2х1—+ж4+9ж5ж3+.программированиее.когда0.3.]Собственная/**(ж))=еенадграфиктогдаиер1функциясовпа-толькотогда,/—выпуклое§ 2. Двойственность2.2.линейномвПримерыПримерНайти1.функциипервуюЬ,а,1*{у)Ъх+{(ж,8ир=(У-ЪJу)/(ж)}-параболатодостигаетс4а0,>{хуялр=X{ -ах28ир■>-аж(у+вторуюГ»:={{х,вирУу)-Г (У)}и(у)Гвир^мумаприГу**(х)Еслижа—+—оо.==Ъ +=8ир40,-1--——-Л+^а(у-Ъ-2ахJвторуюу-Ъ=——.2а4а,ахЪх++с=2ах1+Ъх+своегодостигает—4афункция(уЪ)х-2ах1+-с-+Ъх+++оо,сесли1]>ах=у2фЪ,Поэтому1 1Найдемж+)+—I1-2ажJ(У-Ъ-Iтоприс1—сЧ^}.макси-Следовательно,2ах.(уили2ахJ(у-Ъ-:=~г^~-(.УуПараболау-ъ\2жопределению^др/жу=(-а(—-с}.Ъ)х-ЪJ-=4аПо=(ус-(у/.ксопряженную-Ъх-с)+Ъ)х-максимумасвоегоах2-ПоэтомуНайдемзначенийотфункции=аЛежандра)смыслезависимостивссопряженнойопределениюXЕсли+с.ПоРешение.ах2=(всопряженныевторуюи/(ж)функциикпараметров—119программированиисопряженнуюк/.Нетрудновидеть,чтоЪх+при+с.ж-++оо120ГлаваЕсливверх,0,<а:=УПримерНайти2.функцииРешение./(ж)Поу-ех:=будетд(х),вНайдем\пууэтойфункции.д(х)вирд(х)+оо—упри<0,>0=потоэтойвхЫу=§щ>{-ех}=Если0.—<уXТаким-оо.-+хуПодставляяXтоприд'(х)у.-чтоочевидно,тоу\пу=Имеем-ех=функциигладкойд{х)зирд"(х)Поскольку0.>уд(х).функциимаксимум0,$ирд(х),=максимумпричто=функцииэкстремумахЕслиЛежандра)смыслеXXдостигатьсянаходим,-оо.=(всопряженныесопряженнойусловиюточкеНайдем=(+оо)}-~тр{ху-ех}=достаточному{хувирУвторуюнаправленными+оо.}*{у)что=Xех.ху0&х=осями,сЗначит,ех.=определению/*(у)=8ир{(ж,у>-/(ж)}д(х)ис.-видеть,/*(р)}-первуюфункциикгде{(х,у)вирЪ)х+оо.Нетрудно/.к(у-+-+хприсопряженнуюпрограммирование-ах2+оок/**(ж)Линейноепараболатостремитсявторую2.образом,у0,=у<0.НайдемГ*{х)вторую:=вир»сопряженную{(х,у)!*{у)}-видеть,»примаксимумаДействите0>уууI0,у=О+оо,^<о;:=хууЪгу—+нульв—Ь\ух-и"{у)этозначение1 +-=у--ввыражение1<=0х\куу-при>удляу},0}0 <&■==производной.у=ех,получаемтах{е*,0}=своегодостигаетусвоей0./**(ж),Лу},0}.|/1пу+»>ольно,и\у)ПодставляяI{-обращенияточкевопределениюхутах{вир{жуи(у)функциячто{вир==НетрудноПо/.к=е*.0,§2.Двойственность/**(ж)РавенствоФенхеля—Моро,теоремылинейномв/(ж)=ех=непосредственнотакжеследуетехфункцияпоскольку121программированииизвыпуклойявляетсятео-замк-изамкнутой.2.3.Вывод2.3.1.двойственныхВыводзадачдвойственнойзадачиРассмотримлинейногозадачу(Р),задачи(врассматриваяДля8*(у)=ыр{{у,ъ Ъ)-~Найдемт.е.Такимвэтобезявляется—>\ А*у*ир{{у,Ъ)=ку=с,у ^0}.програм-^Ь,(Р")у^О.с,жуформе:нормальной>(Р„)О,(попробуйтезадачуА*у>с,^8*(у),функциилинейногозадачевАх=самостоятельно):<Ь,р>->тш;с,иначе-задача:А*ушах;+00.кследующаяшах;I=8(Ь):двойственнуюдоказательстваА*уфункциюпрограммирования(с, ж)выпишем=Г0,задачейформе==УлинейногозадачиЬ}}^иначеЛежандрадвойственнойвначалехфункции8*(у)}-<&,»>->Для<АхI.