Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 18
Текст из файла (страница 18)
Таким образом, мы убедились, что термин «двойственная задача» используется правильно. Я" (Ь) = тах((Ь",Ь) — Я*(6')) = гпах((Ь', Ь) ! А'Ь*+ с < 0) ~ ь. ь. Яр; = — Я" (Ь) = тт(( — Ь', Ь) ! А*Ь' + с < О). Полагая у — — Ь, получаем Яр- — ппп((у 6) ! А у + с 0) » э следовательно, имеем следующую двойственную задачу (у,Ь) «ппп; А'у > с. 2.3.4. Упралшения 1. Вывести двойственную задачу для задачи линейного программирования в нормальной форме с помощью преобразования Лежанлра. 2. Вывести двойственную задачу для зааачи линейного программирования в нормальной форме путем свеления ее к общей задаче линейного программирования.
3. Вывести двойственную задачу для эалачи линейного программирования в канонической форме путем сведения ее к общей заааче линейного программирования. 4. Показать, что для задачи (с,х) — «т!п; Ах = Ь, х > О, двойственной является задача (у, Ь) — тах; А*у < с. Гог Глава 2. Линейное программировавие ф 3. Обоснованне симплекс-метода 3.1. Теоремы существования, двоаственностн, критерий решення Приведем трн теоремы, играющие важную роль при обосновании симплекс-метала. Рассмотрим задачу линейного программирования в общей форме (с,х) гп1п; Ах < Ь, где с,х Е К", Ь б К, матрица размеров га х и А = (а')! ! ! с !» а, ... а! 1 )г аэ»( ! со столбцами а' =,, у = 1 ...
и. » / а»! !эм / а~ Обозначим Яр — численное значение задачи (Р), Дгй Р— множество решений задачи (Р), т.е. множество допустимых точек х Е К", для которых (с,х) = бр. Т еврема существования. Если численное значение задачи (Р) конечно (1ор~ < +оо), то ее решение существует (Агб Р ~ й!). Доказательство.
Отметим сразу, что поскольку численное значение задачи конечно, то множество допустимых элементов непусто (г!(Р) ОО м!). РаССМОтрИМ МНОжЕСтВО К: = ((а,э) б К х К ( З х: (с,х) < о, Ах < л). Ясно, что К вЂ” выпуклый конус. Напомним ряд сведений из выпуклого анализа. Пусть С: = (с!,..., с ) С К" — некоторое конечное подмножество. »1 В Элемент о = г Лс;, Л > О, ! = 1,..., пэ, г , '1, = 1, называется выпуклой !=! ы комбинацией С, а элемент й = г 1,еч 1! > О, о = 1 ... пэ, — конической 1 ™ 1=! комбинацией С. Совок и овокупность всех выпуклых (конических) комбинаций конечных подмножеств множества С называется выпуклой (нонической) оболочкой С и обозначается со С (соне С). Мо!кно легко показать, что множество со С совпадает с пересечением всех выпуклых множеств, содержащих С (иногда это свойство берут за определение со С), а множество соле С совпадает с пересечением всех выпуклых конусов, солержаших С.
я 3 Обоснование симплекс метода 103 Выпуклая оболочка конечного числа точек называется выпунлогм мнаграннинам, а выпуклая коническая оболочка конечного числа точек— конечнопаролгденным конусам. Леввма 1. Конус К вЂ” конечнопоролгденный. Доказательство леммы 1. Покажем, что К = сапе(~Е!,...,хС„, г!о,п„ ..., О,„), где Е; = (с., а'„ ..., а~,), у = 1,...,и„ г1о = (1, О,..., 0), „, = (О, 1,..., О),..., О = (О,О,... 1). Вложение соле(~(!,...,~Е„,г!о,...,г! ) С К, следует иэ того, что все образующие конуса лежат в К.
Действительно, полагая х = йе! (е„...,е, — канонический базис в К") в определении конуса К, мы падучим, что ~(1 6 К, у = !,...,п; для векторов гй надо взять х = О. Обратно, если вектор (а,а) = (о,э!,...,з, ) б К, то существует х = (х!,,х„) б К", для которого (с,х) < а, Ах < а. Значит для некоторых )уо > О,..., Д„Р 0 выполняются соотношения (с,х) +!Уо = а, Ах+Д = а (нн = (13!~. Лы)) » » — Е' сх +1!о=а, .г агх,+!о!=э!, 1=1 ( Но это как раз и означает, что » !» х1(! Е ~~) !3!г1! = (о, э).
1=! в=о П у ~Э хд = г 1х./(э!Впх . ( ), то (о,э) б соле(хе! ° ° ° хе у=! 1=! г!о . %») . Лемма л (о замкнутости конечнопорожденного конуса). Конечнопораледенныи конус замкнут. Доказательство. Доказательство проведем индукцией по числу п! порождающих точек. Если пэ = 1, то конус К = (х б К" ) х = ой!, ! > О)— полупрямая, очевидно, замкнутая. Пусть теорема верна для конусов, порожленных по — !точкой, щ > 2, н пусть заданы гп точек й!,...,й . Если конус К = соле(й!,...,й ) содержит векторы — й!,..., — й, то К вЂ” конечномерное надпространство, т.
е. замкнутое множество. В противном случае существует вектор (пусть зто будет — й ), который не принадлежит К ( — й ЕК). Обозначим К'! = соле(й!,...,й !). По предположению индукции конус К' замкнут и К = (й ~ й = й'+ !й, й б К, 1 > О). Пусть (й": = й~+!"й,„)»еи — последовательность векторов из К, схоляшаяся к Й 6 К" (й" — Й). Из последовательности (1") выберем 104 Глава 2. Лииейвее программирование сходящуккя подпоследовательность (бь) — ! > О.
Имеются дае аозм;, = со. первом случае получим, что числа й~ = йп' — Гьй й — !й Е К' (в силу замкнутости конуса К'), т. е. й Е К и, слелоаательно, К замкнуто. Во втором случае, яся последовательность, (!и') — +оо). Откуда —,, сходится к -й, что невозможно так как — й к К . $ Поскольку Яр = пцп (а ! 3 х: (с,х) = а, Ах < ЬТ =: а, то существуют последовательности (хь) и (оь), оь а при й +со, для которых (с х ) = о, р (, ь) — оь, Ахь < Ь (это означает, что последовательность точек (о,Ь) Е К ( м ) — замкнутому по лемме 2 множеству. Поэтому предельная точка О Ь (а,Ь) Е К. Тогда по определению множества К существует точка х такая, что (с, й) < а = Яр, Ах < Ь.
Это означает, что х Е АгаР. Теорема существования доказана. ° Вернемся к задаче линейного программирования а общей форме. В п.2.3 мы обозначили через 5(6): = пйп ((с, х) ! Ах < 6) — Я-функцию э задачи (Р), рассматривая аргумент Ь как параметр в задаче (Р). Лемма 3. Я вЂ” выпуклая замкнутая функция. Доказательство леммы легко выводится из соотношения ер! 5 = К, где К вЂ” выпуклый замкнутый конус, рассмотренный при доказательстве теоремы существования, Лемма 4. П с . Пусть г; К К вЂ” выпуклая замкнутая функция и существует точка хе такая, что э(хе) = — оо. Тогда Т(х) = — оо У х Е догп,у.
Напомним, что двойственной задачей к задаче линейного программирования в общей форме является следующая задача: (Ьу) шах; А у=с, у <О (Р'*) Тес ма двой ре ствеииости. Для пары двойственных задач линейного программирования (Р) и (Р") ( ) (Р") имеет место следующая алыпгрнатива; или значение одной из задан конечно (и тогда конечно значение другой и оба значения совяадают), иэи мноэкество допустимых элементов в одной из задач пусто (и тогда другая задача либо несовместна, либо имеет бесконечное значение . Донвззтельство. !) Пусть )5(6)! < со, тогда поскольку по лемме 3 Я вЂ” выпуклая замкнутая функция, то по лемме 4 5(х) > -сю У а Е К По теореме Фенхеля — Моро п.2.! Я'*(6) = Я(Ь). Это означает, что конечно значение двойственной задачи и оба значения совладают.
105 $ 3. Обоснование симплекс-мепизз 2) Пусть Рр = о (еь 5(Ь) = +со), тогда либо а) существует точка ге такая, что 5(хе) = — оо, тогла Я': — +со, следовательно, Я" = -оо, т.е. Вр- = ю (это означает, что множество допустимых элементов а двойственной задаче пусто), либо Ь) Я(х) > — сю у х Е К, тогда по теореме Фенхеля — Моро 5*'(6) = 5(Ь) = +со (это означает, что двойственная задача имеет бесконечное значение), Критерий решения. Пусть х, у — допустимые элементы в задачах (Р) и (Р*') соответственно (х Е В(Р), у б Р(Р")). Тогда точки х,у являются решениями в задачах (Р) и (Р") соответственно (х Е Ага Р, у Е АгВР") тогда и только тогда, когда (с, х) = (у, Ь) .
Доказательство Необходимость Пусть у Е Агу Р тогда у Е В(Р ) и (у, Ь) = Яр-. Аналогично, х Е АгВР, тогда у Е В(Р") и (с,х) = Яр. Значение задачи (Р) при этом конечно (!Яр! < +со). Значит по теореме двойственности значение двойственной задачи также конечно и оба значения совпадают (Яр — — Яр-). Следовательно, (с,х) = (у, Ь). Достаточность. Пусть В б Р(Р), и' б Р(Р ') и (с,х) = (у 6). Возьмем произвольные допустимые элементы х Е В(Р), у Е Р(Р*'). Это означает, что Ах < Ь, А'у = с, у < О. В силу этих условий на х и у имеем (с,х) = (А*у,х) = (у, Ах) > (у, Ь), Из этого соотношения вытекает, что (с,х) > (у,6) = (с,х) ч х б В(Р). Это означает, что хб Агу Р. Аналогично доказывается, что уЕАгйР'*. ° 3.2.
Свойства множества донустнммх точек Рассмотрим задачу линейного программирования в канонической форме (с,х)- шах; Ах=6, х>0. (Рь) Предложение 1. Пусть х = (хн...,х„, 0,...,0) Е К", х; > О, ! = 1,...,й, — допустимая точка в задаче (Рг) (х Е В(Рь)). Тогда точна х является крайней точкой мноэкгства допустимых элементов Р(Рь) тогда и только тогда, когда столбцы а',..., а" матрицы А линейно независимы. Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
