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