Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 32
Текст из файла (страница 32)
!' = «а ! Таким образом, У(х) > У(е) при всех х Е Х, т. е. е — решение задачи (1). Случай 11. Сушествует номер й, т+1< й < и, такой, что оьа>0,-~«а<0, 1.=1,...,т, т.е, у„=В 'А,<0. (11) Это значит, что в й-м столбце симплекс-таблицы 1 над величиной !ха > 0 нет ни одного положительного числа ум.
В этом случае при всех х' > 0 точка ю, определяемая формулами (8), будет иметь неотрицательные координаты и, следовательно, будет принадлежать множеству Х. Тогда как видно из (9), ,Г(ю) = у(е) — аа х" — — оо при х" — +со. Это значит, что У = 1п1 у(х) = — со, а * «ах т, е. задача (1) не имеет решения. Сл уч а й 11!. Существует номер й, т+1< й < и, для которого аа >О, причем для каждого такого номера й найдется номер г, 1 < г < т, что у«, > О, или, иначе говоря, в каждом й-м столбце симплекс-таблицы 1 над величиной Наша ближайшая задача: выбрать номер й, т+ 1 < й < и, и величину ха > 0 так, чтобы новая точка (8) удовлетворяла требованиям: Аю = Ь, ю > О, У(ю) < у(е) (будет еще лучше, если удастся получить |(ю) < у'(е)). Что касается первого требования Аю = Ь, то здесь проблем нет: точка (8) при любом выборе номера й и величины х', очевидно, является решением системы (5) и равносильной ей системы (2).
Анализируя знаки величин ьъ,, ум, нетрудно выяснить, можно ли удовлетворить оставшимся двум требованиям: ю > 0 и у'(ю) < у(е), и указать правило выбора нужного номера й и нужной величины х' > О. Такой анализ приведет к рассмотрени!о следующих трех взаимоисключающих друг друга случаев 1 — П1. С л у ч а й 1. Справедливы неравенства: ПО Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ й 3.
СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН Ьй > 0 имеется хотя бы одно положительное число 7(, Используя извест- нйе кванторы ((, 3 всеобщности и существования, рассматриваемый случай кратко запишем в виде; ЧХт„>0 Зум>0. (12) Для точки ю, определяемой формулами (8), согласно (9) здесь будем иметь |(ю) = У(о) — Ьйхй < У((в) при любом хй > О. Остается лишь позаботиться о выполнении условия ю > О. В рассматриваемом случае множество номеров Хй(э) = (г ! 1 ( г ( г, 'уа > О) ф О. Если в' ф Хй(()), т. е. 7м < О, то как видно из формул (8), ю! = (>1 — у,х' > > е( > 0 при любом выборе хй > О.
Если же 7а > О, то при слишком больших значениях х', а именно, при хй > ппп (е!/ у ), величина ю( = э( — у, х' вй Ж станет отрицательной хотя бы для одного номера 1 е Хй(о). Таким образом, для обеспечения условия ю > 0 для точек, определяемых формулами (8), здесь нужно хй взять так, чтобы 0 < х' < ппп (ов/у(й).
Пусть в е Гв(в) вв' вв' гп1п — = —, вйй(в) 7м !вй (13) з е Хй(е) О 1 ВВ' 7вй ' 7вй 7, — =О, ю'"' =твв+! —; вй в "\ ю =Ою = —,ю+ й-1 й х й 7вй ' Ю =1! ! ! в 7в-1й 7 .й 7вй.~ ,в 7вй ' ю =() в в (14) ю" +' =О, '=0 ...,ю =О, и значение функции /(х) в этой точке Х(ю) = (с, ю) = Х(()) — Ь ов/ ~„й (15) По построению точка ю с координатами (14) принадлежит множеству Х Покажем, что ю — угловая точка множества Х с базисом А„..., А, !в АйвА,й(!...! А„ (16) получающимся из базиса точки (в заменой столбца А, на Ай. Учитывая, что ю' = ю" й',=...
= ю = ю =... = ю =О, условие Аю = 5 можно й-! записать в виде А, ю' +... + А,, ю' '+ А, й ! ю'+ ' +... + А„ю" + Ай юй = 5. Согласно теореме 2,1 остается показать, что система векторов (16) линейно независима. 11усть для некоторых чисел а„..., а, „а,й„..., а„, а оказалось, что а, А, +... + а,, А,, -1- а„! А,, -1-... -(- а„А .( ай А, — О Так как множество Хй(и) непусто и конечно, то хотя бы один такой номер з существует. Величину 7„, где номера й,з определяются условиями (12), (13), называют разрешающим (ведущим) элементом симплекс-таблицы 1. Зафиксируем один из разрешающих элементов 7„таблицы 1 и в формулах (8), (9) положим х' = (),/7,й.
Получим точку ю =(ю',..., ю") с коор- динатами ю' = —" = — 'х'+ ~', — "х'+ хй+ ~„"— "х'. 7вй Ьй вй ! 7вй й! !вй (18) Отсюда выразим переменную хй через остальные переменные: в (19) 7вй 7вй в=вй! 7й и подставим ее в другие уравнения системы (5) (здесь и ниже в (20)-(24) знак 2," означает, что суммирование ведется по всем У=с+1,...,)й, исклю- Поскольку Ай = ВВ 'Ай = Х,А((В !Ай)1 = ~„7!йА(, то из (17) следует 1=! ;=! а,А(+ ай ~ у(йА! = А,' (с!в+ ай у!й)А(+ ай уйА, =О.
в=1, ' ив 1=1 '=1,ввв Но система А„..., А„..., А„является базисом точки е и, следовательно, линейно независима. Тогда последнее равенство возможно лишь при а,.+айу,й=о, с=1,...,г, Е~з; а,),й=о. Но Ум>0, как РазРешаюший элемент, поэтому а,, =О. А тогда все остальные свв =О, г =1,..., г, й ф з.
Таким образом, равенство (17) возможно лишь при а( =... = а, = а, й ! =... = а, = а, = О. Это значит, что система (16) линейно независима. Тем самым показано, что точка ю, определяемая формулами (14), является угловой точкой множества Х с базисом (16), с базисными переменными х',..., х' ', х", х'+',..., х", причем /(ю) < /(()), так как в (15) сйй > О, у >О, э'>О. 3 а м е ч а н и е 1. Для дальнейшего полезно подчеркнуть, что при до.
казательстве того, что точка ю является угловой точкой, мы нигде не пользовались тем, что Хйй > О. Это означает, что независимо от знака Ьй, 'формулы (13), (14) позволяют перейти от одной угловой точки () множества Х к другой его угловой точке ю, лишь бы Хй(э) ~ О, е' > О. Если твв = О, то формулы (13), (14) да!от ту же угловую точку, т. е. ю = (), но при этом происходит замена базиса А„..., А, на базис (16). Далее, познакомимся с правилами заполнения симплекс-таблицы точки ю (см. табл. 2), постараемся понять, как связаны симплекс-таблицы точек (в и ю. Как и в таблице 1 в столбце Б укажем базисные переменные х',..., х' ', х', х'+',..., х' точки ю, в столбце 1с — соответствующие значения ю',..., ю' ', юй, ю'+',..., ю" ее базисных координат, вычисленных по формулам (14).
В столбцах хв' нам нужно поместить координаты 7и вектоРа 73 = В А, где  — матРица, обРатнаЯ к матРице В = (А„..., А, „Ай, А,„„..., А ). Следует однако заметить, что обращение матриц, их умйожейие является довольно трудоемкими операциями, поэтому вычисление координат вектора 7, опираясь на его определение, может потребовать большого объема вычйслений. В связи с этим полезно вспомнить, что вектор уу совпадает со столбцом коэффициентов при — ! — -1 переменной х' в приведенной системе В 6 = В Ах, соответствуюшей угловой точке ю с базисом (16).
К счастью, имея приведенную систему (5) для угловой точки и, из нее нетрудно получить такую систему и для точки ю. Покажем, как это делается. С этой целью разделим з-е уравнение системы (5) на разрешающий элемент 7м > 0; учитывая, что в силу (14) юй = о'/7„, получим 112 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ чая номер у' = й). Будем иметь ! в >' «+! 7>й '>вй !.! 7>й в и откуда с учетом (14) получим в и ! й = 1,..., а — 1, а + 1,..., т.
(20) Система т уравнений (18), (20) относительно неизвестных л>, х'..., жи равносильна системам (5), (2) и представляет собой приведенную систему для угловой точки и> (см. упражнение?). Отсюда следует, что в строке Г, таблицы 2 согласно (18) мы должны записать величины 7„., !' =0,1,..., гй, определяемые формулами 7,й ии 1, 7«у = О, У' = 1,..., и — 1, и + 1,..., т. (21) В других строках Г., 4 ф и, таблицы 2, согласно (14), (20) следует поместить величины уи. !' =(), 1,..., тй, определяемые формулами 7'=т+1,..., й — 1, й+1,...,ам у>,=0, 7я=О, 1< т'< т, т'фа.
(22) Наконец, заполним строку Ь таблицы 2. С этой целью подставим переменнуйо мй из (19) в (6), с учетом формулы (15) получим следующее выражение значения функции ?(л) через небазисные переменные точки мс и и ,?(х) =)'(») — 2; йй.х' — Ь ~ —" — — х' — 2' ,-"'-х~) = ! «+! 7 7 . 7 и ! =' У(и>) — ( — — ') м' — Я (Ьу — Ьй — ") х'. (23) 7вй ! „+! ! й7й Таблица 2 $3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН 113 ;«1~,, '' Из (23) следует, что в строке Ь симплекс-таблицы 2 точки и> должны быт ь записаны величины Ь, ! =О, 1,..., и, определяемые формулами " 7,й ' ' " 7,й ' в в 7«й ' ,)'=т+1,..., й — 1, й+1,..., и; ййй =0; Ей=О, 7'=1,...,а — 1,а+1,,т. (24) Таким образом, симплекс-таблица 2 угловой точки ю с базисом (16) полностью заполнена: Несложный анализ формул (21), (22), (24) с учетом конкретных числовых значений у„, уи, Ьу, Ьу в базисных столбцах таблиц 1,2 показывает, что элементы этих таблиц связаны следующими простыми соотношениями: 7«й 7«й Ь.
= Ь. — й.'йй — "', !' = О, .. и ти (25) 7,й ' Если элементы и строки таблицы 1 обозначить через 7я(и), Ь.(и), Гв(и), Ь(»), а элементы и строки таблицы 2 через 7,"(и>), Ьу(ю), Гй(и>), Ь(>л), то соотношения (25) можно записать в векторной форме: й' =1>..., а — 1, а+ 1,..., т; Ь(>л) =вл(и) — Ьй(й>) — '. (26) Г,(и) 7 й(и) Соотношения (25) и (26) описывают один шаг известного метода Гаусса — Жордана, соответствующий исключению переменной хй из всех строк симплекс-таблицы 1, кроме строки Г,, в которой переменная мй остается с коэффициентом 7,й(и) = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
