Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 33
Текст из файла (страница 33)
Таким образом, один шаг симплекс-метода, заключающийся в переходе от одной угловой точки и множества Х к другой угловой точке >л, описан. Этот шаг формально можно истолковать как переход от одной симплекс-таблицы 1 к другой симплекс-таблице 2 по формулам (25) или (26), где номера й, а и разрешающий элемент 7„= у, (и) выбираются из условий (12), (13). Таблица 2 Рюи $3.
СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН 115 которую можно переписать в виде (29) й=!,2,...,п, (а„,, ..., а„.3 (27) (32) 114 Гл. 3, ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 2. Формулы перехода (25), (26) были получены в предположении, что множество номеров базисных переменных угловой точки (! имеет специальный вид 1(и) = (1, 2,..., г), что соответствует таблице 1.
Конечно, путем перенумерации переменных всегда можно добиться, чтобы множество 1(и) имело указанный вид, но это связано с дополнительной обработкой числовых массивов, усложняет программную реализацию симплекс-метода на ЭВМ. Однако нетрудно убедиться, что можно обойтись без какой-либо перенумерации переменных, а формулы перехода (25), (26) остаются справедливыми для угловых точек с любым множеством базисных номеров.
В самом деле, пусть номера базисных переменных начальной точки е образу)от множество 1(о) = ()'„3'„...,3'„). Заметим, что в процессе применения симплекс-метода множество 1(о) обновляется на каждом шаге и нельзЯ ожидать, что номеРа 3'„ ум ...,3'„ из этого множества бУДУт УпоРЯ- дочены, скажем, в порядке монотонного возрастания или убывания (так, например, в таблице 2 в отличие от таблицы 1 монотонность номеров базисных переменных в столбце Б уже нарушена). Однако это обстоятельство нашим дальнейшим рассуждениям никак не помешает, Обозначим х= ..., 6= ..., с= ..., А 7 =' уа(в) = В !Аа 'уо = уо(в) = В !Ь 'уо = 'У!а((!) = (В Аа) !.=7!.( ) =(В-'Ь), Так как В-'В=В '(А,,, А, )=(В-'А,,, В 'А,)=(е„..., е,)=7— единичнаЯ матРица РазмеРа т х и, то Гт = В-'Ат = е! длЯ всех г = 1,..., и, Кроме того, согласно теореме 2.1 ВВ=А ей+...+А:е'=Ь; о'=О, 3'~7((!), Ь !', поэтомУ 6= В-! Ь = уо, ет = (В ' Ь)' = Уо, г = 1,..., и; хт =О, 3' ф 1(()).
Таким а образом, умножая систему Ах = 2', А,.х! = Ь слева на матрицу В ' как и а=! при выводе системы (4), (5), получим приведенную систему угловой точки и с базисом В в векторной форме 0< В=В-'Ь = ~о= от+ Х, (В-'Аа)х' = ) Та. ", ааг( ) или в покоординатной форме А ="йо=х!) Р 2' ,7!ах" = ЕТ!а ', г =1,..., и (28) ааг(а) а= ! По аналогии с (6), (7) для целевой функции получим ее приведенную форму ,7(х)=(с,х)+ ~ с'х'=(с,б — ~ (В-'Ат)х')+ ! ФГ(а) ! а )(.) + 2„ с'х! = (с, 6) — 2' ,1(с, В ' А)) — са)ха, ! аг(а) 3 й )(а) 7А.=их)+ Е Ь,ха=пх)+ Е Л,ха, а ге( ) а=! где приняты обозначения (аа)=,Г((!)=(с, 6), ааа =(с, В ' Аь) — с"=(с, уа) — с"= ~„ с" .>, — с', — "-"=,, ' '-' (30) причем учтено, что для всех й = 3! 6 7(о) величина (зз = (с,В 'А)) — сй = = с, е!) — с" = с" — с' = О, а = 1,..., и, т.
е. (1)а = О, Чй е Х(о). нформацию из (27) — (30) об угловой точке и с базисом В = (А,,, Аз ) удобно записать в виде симплекс-таблицы 3: строка Г! в ней соответствует г-у уравнению (28), строка (1 — представлению (29) для целевой функции. Таблица 3 Отметим, что в столбце базисной переменной х" вектор Тт = еа, т. е..~), =0 при всех 1 ~ г, 1 <1 < т, Ти =1; в нижней строке этого столбца Ь,. =О. Симплекс-таблицу 3 можно кратко записать в виде матрицы В=(" В)= ~~~" ~Л" ''' Ь" = Л )гГ, ') размера (и+1)х(п+1), где столбцы уа подматрицы Г = ~...) и элементы строки А вычисляются по стандартным формулам: Г, Та=В А„, Ьа=(с,В 'А„) — с"=(с, Та) — с", й=0,!,,п; (31) здесь для единообразия формул принято Ь = А, предполагается, что с =О, остальные обозначения взяты из (27).
Опишем один шаг симплекс-метода в общем случае. По аналогии с (10)— (12) рассмотрим следующие три взаимоисключающие возможности. С л у ч а й 1. Справедливы неравенства !а(,=(с,В 'Ат) — с'<О, 3'=1,...,п, т. е. в нижней строке симплекс-таблицы 3 все величины (а„..., (а„непо- $3. СИМПЛЕКС-МЕТОД. АНТИБИКЛИН 117 116 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (37) ложительны. Тогда с учетом равносильности систем (2) и (28) для любой точки х Е Х имеем /(х)=(с,х)+ ~ с'х'> (с,х)+ ~" (с, В 'А!)х'= 14/(л) )Фг() = (с, х+ 2", В 'А,х') = (с, о) =/(о). з'4цю Это значит, что г) — решение задачи (1). Случай 11. Существует номер й >О, й гд1(о), такой, что Ьй >О, уй =В 'Ай <О, (33) т. е.
в й-м столбце симплекс-таблицы 3 над Ьй > 0 нет ни одной поло- жительной величины 7/й Тогда точка х = х(() =(х',..., х") с кооРдината- надлежать множеству Х при всех 1 > О. Отсюда и из (29) следует, что Цх(!))=/(и) — Ьйз- -оо при Ф- +со. Это значит, что/„= !п! /(х)= — оо, т. е. задача (11 не имеет решения, Случай ! 11. Существует номер Уз > О, й йА1(и), для которого (.'йй > О, причем для каждого такого номера й найдется номер з, 1 < з < г, что 7г„> О, УЬ,>О Зугй=(В-'Ай) >О.
(34) Это значит, что в каждом й-м столбце симплекс-таблицы 3 над величиной Ьй > 0 имеется хотя бы одно положительное число 7зй. Тогда выберем номер з и разрешающий элемент 7„> 0 из условий: ппп тга = — йд, а Е 1й(и)=(г'; 1< )' <г, Узй >0). (35) гаг,(л) 7гй 7,й' Далее, рассуждая также, как выше (см. формулы (14) — (16) и пояснения к ним), убеждаемся, что точка (и = (и),..., и") с координатами юй = ал = 7'0; ю! =О, 2'41(о), 2'ФЬ, 7,й 7,й принадлежит множеству Х, является угловой точкой этого множества с базисом (А,,..., А,, А, А,,, Ау ) = В, значение функции /(х) в этой точке равно / ((и) — / (") /Уйй,„~ /2йа ~й -( „( ) 'бй Замечание 1 с очевидными изменениями сохраняет силу в рассматрива- емом общем случае.
Приведенная система точки гц выводится так же, как система (18), (20), и имеет вид: (39) аналогичное (23) выражение для функции /(х) выглядит так /(*)=/( )-~ —',1*3- К 'Ь,-~.Ж*': (40) той / 4 г(л) ~ " твй / в (39), (40) знак 2 означает, что суммирование ведется по всем )'(б 1(о), )' ~ й. Нетрудно видеть, что если 1(и) = (1, 2,..., и), то формулы (35) †(40) переходят в соответствующие формулы (13) — (16), (18), (20), (23).
Анализируя коэффициенты при переменных х', х',..., х" в выраженйях (39), (40), получаем аналогичные (21), (22), (24) формулы для величин, которые должны находиться в строках Г,(ю), й = 1, 2,..., г,,лй(ю) симплекс-таблицы точки гл, и убеждаемся в том, что переход от симплекс-таблицы точки о с базисом В = (А,,..., А! ) к симплекс-таблице точки и с базисом (37) совершается по тем же формулам (25), (26), где номера Уз, л определяются из условий (34), (35). Для иллюстрации вышеизложенного приведем несколько примеров. П р и м е р 1.
Будем минимизировать функцию /(х) =10хз — х'+4х" +хз на множестве Х =(х=(х', хз,, хз) >0: х'+2хз+х =2, 2х' — ха+ха =3, — х'+ хз+ хз = Ц. Уравнения, задающие это множество можно записать в виде Таблица 4 '.~ф ,) "' 3 = 2 х! + О хз + 1 хз + О х( + 1 хз ''1:::;- :-':) ' "'3'' ' Е И х' аз хз х4 Г~ х" 2 1 О 2 1 О Гз а~ 3 2 Π— ! 0 1 (з * 1 -1 1 С!) Ь 21 -4 О 13 О О :=;(л, и впишем их в строку йй таблицы 4. В втой строке величина Ьз > О, а в столбце хз имеются положительные элементь! 7м — — 2, у„= 1. Это значит, что в точке о реализовались условия (34).
Определим номер а из условия (35): гп!и( ую/7,3 7за/733) = гп!п(2/2, 1/Ц = 1. Как видим, здесь минимум достигается сразу йри двух значениях а = 1 и а = 3. Для определенности возьмем а = 3. Тогда разрешающий элемент равен у„=1, й = 3, а =3. В таблице 4 и в последующих таблицах разрешающий элемент будем обводить кружочком. В соответствии с выбранным разрешающим элементом переменную хл = х' и столбец А. = А, будем выводить из базиса и заменим их переменной х' и А столбцом А, соответственно. Согласно формуле (26) разделим строку Г, на у„= 1 и полученные величины внесем в строку Г, таблицы 5.
Затем будем 118 Гл. 3, ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ последовательно умножать строку Г, таблицы 5 на величины Т„=2, Тм — — — 1, 7аа — — — 1, Ьа = 1 8, полУчившиесЯ стРоки вычтем соответственно из стРок Г Г„Ь таблицы 4 и результат вычитания внесем в строки Го Г„Ь таблицы 5, Таким образом, придем к симплекс-таблице 5 следующей угловой точки Таблица б $ 3 СИМПЛЕКС МЕТОД АНТИЦИКЛИН 119 при а=2, й=З совершим переход к симплекс-таблице 8 угловой точки о, =(2, О, 1, О, 0) с базисом В,=(А„А,), со множеством 7(о,)=(7',=1, 7' =3), В строке аа таблицы 8 имеется величина Ь„=2 > О, но столбец л' не содежит положительных элементов, Это значит, что реализовался случай (33). Следовательно, У, = — оо, рассматриваемая задача не имеет решейия, Таблица 7 о, =(О, О, 1, О, 4) с базисом В, =(А„, А„А ), со множеством базисных номеров 7(о,)=(7',=4, 7' =5, 7 =37 и со значенйем функции 7(о,)=3 < 7(оа)=21.
В строке Ь таблицы 5 величина Ь, = 14 > О, в столбце з' имеются положительные элементы 7п — -3, Т, =1, т. е. снова реализовались условия (34). По правилу (35): ш1п(07'3; 4/17=0 однозначно определяем номер а=1 и разрешающий элемент Гп=З. Это значит, что переменную ха =х' и столбец А. =А, выводим из базиса и заменяем их переменной х' и столбцом А, соответственно. По формулам (26) вычислим симплекс-таблицу 6 следующей Таблица б угловой точки о, = (О, О, 1, О, 4) с базисом В, = (А„А„А,), со множеством 7(ма) = ( г, = 1, 7', = 5, 7а — — 3) и со значением фУйкцйи 7" (оа) = 3 = 7'(о, ). В строке Ь этой таблицы среди величин Ьп..., Ь, нет положительных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
