Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 36
Текст из файла (страница 36)
Так, например, в таблице 9 для этого достаточно переставить столбцы х', х' между столбцами У и х'. После сказанного теперь неудивительно, что симплекс- таблица 1 лексикографически положительна. А вот симплекс-таблица 2 может потерять это свойство, если в строке Г„ окажется «ь» = О, т,„ < О. Используя введенные лексикографические понятия, перейдем к описанию обещанного антициклина, Напомним, что применение симплекс-метода во всякой невырожденной задаче приводит к построенисо последовательности угловых точек еы е„ ..., е„,...
со свойством (43). Так как Ь„ь = Г(е ), то согласно определению 4 свойство (43) будет означать, что соответствующие этим точкам симплекс-таблицы Я, Я„..., Я„,... таковы, что При написании цепочки лексикографических неравенств (47) мы учли Ь Ь Ь транзитивность отношения >- для симплекс-таблиц: если Я, >- Я, Я, ~ Я, то 127 4 З, СИМПЛЕКС-МЕтоД. АнтИЦИКЛИН 126 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Я,«- Я,. Так как симплекс-таблиц конечное число, а в (47) повторение таблиц невозможно, то еще раз убеждаемся в конечности симплекс-процесса в невырожденных задачах.
А в вырожденных задачах последовательность (/(е,)) обладает, вообще говоря, лишь свойством (41), а свойство (47), как видно из примера 3 (см, табл. 9-15), может не выполняться. Возникает идея: нельзя ли как-то дополнить правило (34), (35) выбора разрешающего элемента так, чтобы и в вырожденных задачах получались последовательности симплекс-таблиц со свойством (47)7 Реализация этой идеи приведет нас к антициклину. Пусть ь — какая-либо угловая точка множества Х с базисом В = (А,, ..., Аг ) и с симплекс-таблицей Я = Я(е, В), пусть это будет таблица 3. Предположим, что таблица Я удовлетворяет условиям (34), и уже зафиксирован какой-либо номер к ф Х(ь), к > О, из (34). Выберем номер в и РазРешаюЩий элемент 7м из УсловиЯ вЂ” '=1ехппп — ', зЕХ„(ь)=(г: 1<( <т; 7а >0).
(48) Г, . Г; тм 'вгц ) та С помощью леммы 1 убедимся, что условие (48) однозначно определяет Г,. номер в. Для этого нам надо показать, что множество С =(у,. = — ', г Е пм Е Хь(е) = М,) состоит из различных векторов. Допустим, что два вектора из этого множества оказались равными; Г,/7,, = Г,/7„„, р, й е Х (ь), р ф к. Тогда Г,.
= (7м/7м)Г„, т. е. строки Г,, Г„в матрице Г = (7ь, 7„... ...,7 ) = (В 'б, В 'А„..., В-'А„) = В,'(5, А) пропорциональны. Однако по предположению множество Х непусто, поэтому система (2), Ак = 6, совместна, и тогда, согласно теореме Кронекера — Капелли [192; 353), гапй(Ь, А) = гапиА = г. Отсюда н из невырожденности матрицы В ' следует, что гапдГ = гапдА = т. Это значит, что строки Г„..., Г, 'матрицы Г образуют линейно независимую систему векторов, и никакие строки Г,, Г„ в этой матрице пропорциональными не' могут быть. Полученное противоречие показывает, что множество С состоит из различных векторов.
Согласно лемме 1 условие (48) однозначно определяет номер з е Хь(е), причем для его практического нахождения можно воспользоваться конструкциями, указанными в этой лемме. Важно заметить, что лексикографическое правило (48) выбора разрешающего элемента не отменяет ранее сформулированное правило (34), (35), а, наоборот, включает его в себя, дополняет и уточняет его. В самом деле, в соответствии с конструкциями леммы 1 для поиска номера в из условия (48) мы в первую очередь образуем множество М, = (з Е М = Х„(ь): 7, /-»„= ппп 7,. /7м), котоРое в точности совпадает 'Со множеством номеРов В в М> в, определяемых условием (35). Отсюда, кстати, следует, что если многкество Ы, состоит из единственного номера (так будет,,например, в невы- рожденных задачах), то оба правила (34), (35) и, (48) определяют один и тот же номер з, один и тот же разрешающий элемент 7,„.
Если же М, содержит более одного номера, то правило (48) устраняет возможную в вырожденных задачах неоднозначность в выборе разрешающего элемента при пользовании правилом (34), (35). Итак, выберем номера к, в и разрешающий элемент 7„, = 7,„(е) из условий (34), (48) и по правилам (26) совершим переход от симплекс-таблицы Я(е, В) угловой точки е с базисом В к симплекс-таблице Я(ю, В) угловой точки ю с координатами (36) и с г базисом (37), Оказывается, если исходная симплекс-таблица Я(ь, В) «-О, то имеют место следующие лексикографические неравенства: Я(ю, В) «- 0> Я(ь, В) «- Я(ю, В). (49) г В самом деле, если Я(ь, В) «-О, то по определению 5 в этой симплекс- таблице строки Г,. = Г,,(ь) «-О, з = 1,, г.
Тогда из (26), из неравенства 7„> 0 и свойства 1) отношения «- следует, что Г,(ю) =Г (ь)/7м(ь) «-О. Г(усть теперь Ефа. Тогда, возможно, либо 7 >О, либо 7а<0. Еслй 7, >О, то г Е Х„(е) и, согласно пРавилУ (48), имеем Г,. (ь)/7ч(е) «-Г,(ь)/7м(ь). В силу свойства 2) отношения «- тогда Г,(ь) «- (7,.„(ь)/7,ь(е))Г,(ь), т. е. Г.(ю) = =Г,.(о) — (7а(о)Х7„(™))Г,(е) «'О. Если 7м < О, то а = — (7а(ь)/7,„(ь)1> 0 и Г (ю) = Г(ь)+1 (юК вЂ” 7а(ь)/7,„(ь)) «-0 в силу свойства 3) отношения «., Таким образом, 1,.(ю) «-0 для всех г =1,..., г, что означает, что симплекс— г таблица Я(ю, В) «-О. Наконец, из того, что Г,(ю) «-О, Ь = Ли(ь) > О, из формулы (26) для строки сг(ю) и свойства 4) отношейия «- имеем; Ь(ь) «- Ь(е) — Ь„(е)Г,(ю) = Ь(ю). Это значит, что Я(ь, В) «- Я(ю, В).
Лексикографические неравенства (49) доказаны. Теперь посмотрим, к какому симплекс-процессу приведет применение правил (34), (48). Пусть у нас имеется некоторая угловая точка ь, с базиг сом В„с симплекс-таблицей Я, «- О. Пользуясь правилами (34), (48), (26), организуем симплекс-процесс, йачинающийся с точки ею и получим последовательности угловых точек (ь„), их базисов (В ), симплекс-таблиц (Я„), где ߄— симплекс-таблица точки е, с базисом В„.
Оказывается, последовательность (Я„) удовлетворяет лексикографическим неравенствам (47), в чем легко убедйться с помощью математической индукции, основываясь на г неравенствах (49) и Я «- О. Так как в цепочке неравенств (47) повторение ь симплекс-таблиц невозможно в силу транзитивности отношения «- и в задаче (1) множество симплекс-таблиц конечно, то такой симплекс-процесс закончится на каком-то шаге реализацией одного из условий (32) или (33), Это значит, что правило выбора разрешающего элемента по формулам (34), (48) является антициклином.
Тем самым доказана Т е о р е м а 2. Пусть в канонической задаче (1) множество Х ф О, гапдА = г = гп <г, пусть е, — какая-либо угловая точка этого множества с симплекс-таблицей Я, «-О. Тогда симплекс-процесс, начинаюгцийся с точки ею при вгяборе разрешающего элемента 7,„из условий (34), (48) завершится за конечное число шагов определением некоторой угловой точки ь„множества Х, в которой реализуются либо условия (32), либо (33), причем в случае (32) ь„— решение задачи (1), Х(ь,) =/, > — оо, а в случае (33) задача (1) нв имеет решения, /, = — оо.
Напомним, что построенный антициклин (34), (48) обоснован при услог вии, что начальная симплекс-таблица Яь «-О. Но это условие нельзя считать серьезным требованием к антициклину, так как выше мы показали, что переставив некоторые из базисных столбцов и соответствующим образом перенумеровав переменные, любую симплекс-таблицу Я легко сделать лексикографически положительной.
К тому же такую операцию с перестановкой $3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН 128 Гл. 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, в которой сохранена первоначальная нумерация переменных. Таблица 16 Таблица 17 Таблица 18 В строке Ь таблицы 16 величина Ь, = 1 ) 0 и весь столбец х' заполнен положительными числами: Ты — — 1, ~„= 1, уа, = 4.
Таким образом получаем, что условия (34) здесь выполнены и 7,(иа) = (1, 2, 3). Для применения лексикографического правила (48) выпишем следующие строки: -'- = (1, О, О, 1, 1, 1, 1, 1), — ' = (О, 1, О, — 2, 1, -3, 4, 0), (0~0)4)4~1~лга>0) Последовательно сравнивая по величине первые, вторые и т. д. координаты этих векторов-строк Га/Та,, 1 е М = 7 (и ), легко находим указанные в лемме 1 множества М = (2, 3), М, = (3), йскомый номер а = 3, так что здесь !ех ш!п(Г,/Ты, Га~.Уы, Г,/Уа„) = Г,/Тал.
ПонЯтно, что те же множества М„М, и номер а = 3 можно было получить непосредственно из таблицы 9, просматривая ее столбцы в таком порядке: У х', х', х', х', ха, х', х'. Таким образом, с помощью правила (48) мы однозначно нашли разрешающий элемент 7,„=4. Далее, по формулам (26) в базис вводим переменную х4 и выводим из базиса х'.
В результате придем к симплекс-таблице 17 угловой точки еп совпадающей с иа, но имеющей другой базис (А„А„А ). В этой ;4:::,'::: таблице разрешающим элементом может быть лишь величина ум — — 3/2. Из базиса выведем переменную х', заменив ее х', по формулам (26) получим табл.
18. В строке 1л все величины 1з„! < 4 < 7, неположительны, реализо- :Ю, вались условия (32). Симплекс-процесс на этом заканчивается. Выясняется, что невырожденная угловая точка и =(О, 5/3, О, 1/3, 2/3, О, 0) является решением задачи (45), (46), У(иа) = У, = — 1. Заметим, что хотя среди задач линейного программирования вырожденные задачи встречаются довольно часто, но тем не менее на основе всего практического опыта применения симплекс-метода к таким задачам сложилось убеждение, что вероятность получения бесконечных симплекс- процессов ничтожно мала. Добавим также, что использование антициклина на каждом шаге симплекс-метода может привести к заметному увеличению машинного времени ЭВМ, требующегося для решения задачи. Поэтому на практике чаще всего пользуются упрощенным правилом выбора номеров й и и из условий (34), (35), беря, например, наименьшие или наибольшие номера, удовлетворяющие этим условиям.
Из сказанного следует, что наличие симплекс-метода, снабженного антициклином, для практики, видимо, не является слишком актуальным, но в теоретическом плане это принципиально важно и ставит симплекс-метод на надежный математический фундамент. 5. Кратко остановимся на применении симплекс-метода для решения канонической задачи максимизации: /(х) = (с, х) -+ зцр, х е Х = (х е Е™: х > О, Ах = б), (50) где А — ненулевая матрица размера и х гт, с е Е", Ь е .Е , и = гапяА < и, Конечно, эту задачу можно свести к равносильной задаче минимизации д(х) = — У(х) — !п1, х е Х, и к ней применить описанный выше симплекс- метод без каких-либо изменений. В то же время нетрудно несколько видоизменить симплекс-метод и приспособить его для непосредственного применения к задаче (50).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
