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