Ф.П. Васильев - Методы оптимизации (1125241), страница 37
Текст из файла (страница 37)
Оказывается, если исходная симплекс-таблица Я(е, В) >- О, то имеют место следующие лексикографические неравенства: Я(ш, В) >-О, Я(е, В) ~- Я(ш, В). (49) В самом деле, если Я(е,В) >- О, то по определению 5 в этой симплекс- таблице строки Гг = Г,.(е) >- О, 4 = 1,..., т. Тогда из (26), из неравенства у„ > 0 и свойства 1) отношения ~ следует, что Г,(ш) = Г,(е)/7м(е) ь- О. у)усть теперь у~а.
Тогда, возможно, либо у. >О, либо.у> <О. Еслй 7> >О, тоуЕХ (и) и, согласно правилу(48), имеем Г,.(е)/Та(е)тГ (е)/7„(е). В силу свойства 2) отношения ь- тогда Г,(е) >- ( 7,.„(е)/.у,„(е))Г,(е), т, е. Г,.(ш) = =Г,.(е) — (у. (е)/7, (е))Г,(е)ь-О. Если 7 <О, то сг = — (7,„(е)/7, (е)) >О и Г (ш) = Г (е)+ Г (ш)( — "~,,(е)/Т,„(е)) >-О в силу свойства 3) отношения >-. Таким образом, 1>(ш) >-0 для всех в' = 1,..., т, что означает, что симплекс— г таблица Я(ю, В) Ь-О. Наконец, из того, что Г,(ш) >- О, У),ь = Ь,(е) > О, из формулы (26) для строки Ь(ш) и свойства 4) отношейия ь. имеем: Ь(е) >- Гз(е) — Ь (е)Г,(ш) = с>(ш). Это значит, что Я(е, В) >- Я(ю, В), Лексикографические неравенства (49) доказаны.
Теперь посмотрим, к какому симплекс-процессу приведет применение правил (34), (48). Пусть у нас имеется некоторая угловая точка е с базисом В,, с симплекс-таблицей Я,>- О. Пользуясь правилами (34), (48), (26), организуем симплекс-процесс, йачинающийся с точки е„ и получим последовательности угловых точек (е„), их базисов (В ), симплекс-таблиц (Я„), где Я вЂ” симплекс-таблица точки е с базисом А,, Оказывается, последовательность (Я ) удовлетворяет лексикографическим неравенствам (4?), в чем легко убедйться с помощью математической индукции, основываясь на г неравенствах (49) и Я ь-О. Так как в цепочке неравенств (47) повторение симплекс-таблиц невозможно в силу транзитивности отношения ь- и в задаче (1) множество симплекс-таблиц конечно, то такой симплекс-процесс закончится на каком-то шаге реализацией одного из условий (32) или (33). Это значит, что правило выбора разрешающего элемента по формулам (34), (48) является антициклином.
Тем самым доказана Теорема 2. Пусть в канонической задаче (1) множество Х ~0, гапиА = т = та < и, пусть еь — какая-либо угловая точка этого множестг ва с симплекс-таблицей Я >-О. Тогда симплекс-процесс, начинающийся с точки е,, при выборе разрешаюиуего элемента у,„из условий (34), (48) завершится за конечное число шагов определением некоторой угловой точки е„множества Х, в которой реализуются либо условия (32), либо (33), причем в случае (32) е, — решение задачи Я, Х(е,) =/„> — оо, а в случае (33) задача (1) не имеет решения, У„= — со. Напомним, что построенный антициклин (34), (48) обоснован при услог вии, что начальная симплекс-таблица Я, >-О.
Но это условие нельзя считать серьезным требованием к антициклину, так как выше мы показали, что переставив некоторые из базисных столбцов и соответствующим образом перенумеровав переменные, любую симплекс-таблицу Я, легко сделать лексикографически положительной, К тому же такую операцию с перестановкой 128 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ $3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН 129 столбцов и перенумерацией переменных нужно сделать самое большее один раз в самом начале симплекс-процесса. Впрочем, операцию с перестановкой столбцов и перенумерацией переменных можно явно и не делать, если эту операцию учесть при порядке формирования множеств М„М,..., указанных в лемме 1 и используемых при поиске номера а из условия (48).
Более того, можно доказать, что условия (34), (48) являются антициклином и без г требования Я г- 0 (148; 259]. Заметим также, что антицнклин (34), (48) оставляет некоторый произвол в организации симплекс-процесса из-за того, что условие (34) определяет номер й, вообще говоря, неоднозначно; для устранения указанной неоднозначности к правилу (34),(48) можно сделать дополнение, руководствуясь какими-либо другими соображениями, например, можно выбирать минимальный или максимальный номер й, удовлетворяющий условиям (34). П р и м е р 4.
Для иллюстрации изложенного антициклина (34), (48) рассмотрим задачу (45), (46), в которой, как обнаружилось выше, использование правила (34), (35) выбора разрешагощего элемента может привести к зацикливанию. Сначала симплекс-таблицу 9 начальной угловой точки и = (О, О, О, О, О, О, 1) сделаем лексикографически положительной, переставив базисные столбцы х', х' между столбцами Ъ' и х'! в результате придем к таблице 16, в которой сохранена первоначальная нумерация переменных.
Таблица 1б Таблица 17 Таблица !8 В строке 1а таблицы 16 величина Ь, = 1 > 0 и весь столбец х' заполнен положительными числами: ум — — 1, Таа — — 1, 7,„=4. Таким образом получаем, что условия (34) здесь выполненй и Х (и ) = (1, 2, 3). Для применения лексикографического правила (48) выпишем следующие строки: -'- = (1, О, О, 1, 1, 1, 1, 1), — ' = (О, 1, О, -2, 1, -3, 4, 0), Последовательно сравнивая по величине первые, вторые и т.
д. координаты этих векторов-строк Га/Та„а е !1~ =1 (аг ), легко находим указанньге в лемме 1 множества М, = (2, 3), М, = (3), йскомый номер а = 3, так что здесь !ехгп!п(Г,/чм, Г,/74, Га~Таа) = Г /Уа4. ПонЯтно, что те же множества М„М, и номер а = 3 можно было получить непосредственно из таблицы 9, просматривая ее столбцы в таком порядке: 17; х', х', х', х', ха, х', х'.
Таким образом, с помощью правила (48) мы однозначно нашли разрешающий элемент 7„=4. Далее, по формулам (26) в базис вводим переменную ха и выводим из базиса х'. В результате придем к симплекс-таблице 17 угловой точки тн совпадающей с иа, но имеющей другой базис (А, А„Аа), В этой таблице разрешающим элементом может быть лишь величина Т,а = 3/2. Из базиса выведем переменную х', заменив ее х', по формулам (26) получим +,:-, табл.
18. В строке Ь все величины 1л,, 1 < а' < 7, неположительны, реализовались условия (32), Симплекс-процесс на этом заканчивается. Выясняется, что невырожденная угловая точка иа = (О, 5/3, О, 1/3, 2/3, О, 0) является решением задачи (45), (46), /(еа) = У„= — 1. Заметим, что хотя среди задач линейного программирования вырожденные задачи встречаются доволыю часто, но тем не менее на основе всего практического опыта применения симплекс-метода к таким задачам сложилось убеждение, что вероятность получения бесконечных симплекс- процессов ничтожно мала. Добавим также, что использование антициклина на каждом шаге симплекс-метода может привести к заметному увеличению машинного времени ЭВМ, требующегося для решения задачи.
Поэтому на практике чаще всего пользуются упрощенным правилом выбора номеров й и а из условий (34), (35), беря, например, наименьшие или наибольшие номера, удовлетворяющие этим условиям. Из сказанного следует, что наличие симплекс-метода, снабженного антициклином, для практики, видимо, не является слишком актуальным, но в теоретическом плане это принципиально важно и ставит симплекс-метод на надегкный математический фундамент. 5. Кратко остановимся на применении симплекс-метода для решения канонической задачи максимизации: /(х)=(с,х)- зпр, хеХ=(хеЕ": х>0, Ах=5), (50) где А — ненулевая матрица размера т х я, с еЕ", й е Е", т =гапдА < и. "с~":,,-'',:,:„:.:,';: Конечно, эту задачу можно свести к равносильной задаче минимизации д(х) = -/(х) — !п(, х е Х, и к ней применить описанный выше симплексметод без каких-либо изменений, В то же время нетрудно несколько видоизменить симплекс-метод и приспособить его для непосредственного приме=;.!..-:..'К пения к задаче (50).
Легко понять, посмотрев на формулы (6),(9) и (29), что при решении задачи максимизации (50) нас прежде всего будут интересовать величины Ьа <О, и мы естественно придем к рассмотрению следующих трех случаев, аналогичных случаям (32)-(34) Сл у чай 1. В нижней строке симплекс-таблицы 3 все Ь,,..., Ь неотрицательны. Исходная угловая точка и является решением задачи (50). :4'..:::. 9 3. СИМПЛЕКС-МЕТОД.
АНТИПИКЛИН 130 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 131 С л у ч а й 11, В нижней строке симплекс-таблицы 3 найдется величина Ьз < О, 1 < [с < и, и находящийся над ней столбец у„неположителен. Тогда У* = зпр(с, ж) = +со, задача (50) не имеет решения, рех Случай 111. В нижней строке симплекс-таблицы 3 имеются вели- чины ухь < О, 1 < [с < и, пРичем в каждом столбце над величиной 1.'ьь < 0 найдется хотя бы одно число 74ь > О, Тогда фиксируем один из таких но- меров й с 135 < 0 и выбираем разрешающий элемент Т„ь по правилу (35) илй, точнее, (48), а затем по формулам (36) совершаем переход от угло- вой точки и с базисом В к точке ш, которая согласно замечанию 1 также будет угловой точкой множества Х с базисом В, имеющим вид (37), при- чем 1(ш) > 1(п).
Один шаг симплекс-метода для задачи (50) описан. Как и выше, можем считать, что исходная симплекс-таблица В(п, В) >-О. Тогда будут справедливы следующие лексикографические неравенства, аналогичг д ные неравенствам (49); В(цу, В) >- О, Я(п, В) < В(го, В), Отсюда следует, что симплекс-процесс для задачи (50) будет конечным и закончится реали- зацией одного из случаев 1 или 11. Все высказанные здесь утверждения, касающиеся задачи (50), доказы- ваются сове)ошенно также, как и аналогичные утверждения, касающиеся з д а ачи (1).
редлагаем читателю убедиться в этом самостоятельно. 1 Остается напомнить, что в течение всего этого параграфа задача ( ) (а также задача (50)) рассматривалась в предположении, что гп = г = гапиА < < и, и нам известна хотя бы одна угловая точка множества Х. В следующем параграфе покажем, как избавиться от этих ограничении. Упражнения 1.
С помощью симплекс-метода решить следующие канонические задачи; а) 1(х) — х'.ьхе.ьхз+х4+х5,;и!! х=(х',хз,,х5) >О, х1ч.хзчгхзч.х4 гх5=2, б) 1(ж) =х +Зжз+2жз+х4 — Зхз-ч !и!! ж= (х1,,х ) > О, ж + 2ж — 42х — х =О, 2 4 5 в) 1(ж) = х ' — 2х2-Ь хз — х4 41п(; ж = (х ',..., х ) > О, х ' — 2ж + х = 1, х + х — 2ж = 1; г) 1( )=*'+*'+х'+ 4-ьхз пй х=(ж',...,. ')>о, х142хз — х'+2*'= 1, хзч-хзч- +2х4 — ж =О, -х — 2х +х +х =1. 4 5 2 4 5 5 2. П оверить, что точка х является угловой, найти ее базис, приведенную систему и, ваяв в качестве начальной точки, с помощью симплекс. метода решить следу щ ад ю нез ачи: ьо в а) 1(х)=х~ чгхх+х~ их'-ч!пцзпр[1х=(ж,, х ) >О, ж -ь2ж -ж +2х — х ч- х = — 1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
