Ф.П. Васильев - Методы оптимизации (1125241), страница 36
Текст из файла (страница 36)
На практике правило (34), (35) нередко уточн среди номеров й, удовлетворяющих условиям (34 рого г3а принимает максимальное значение, а есл ко, то берут минимальный из них, и затем, посл й, берут номер а минимально возможным из усло правил (34), (35) действительно гарантирует одн шающего элемента Т,а, выглЯдит вполне естеств легко проверить, на самом деле позволяет избе ко пример задачи из упражнения 6 (см. ниже) случае в классе канонических задач линейного уточнение правила (34), (35) не спасает от заци но, не может служить антициклином. Это говор антициклина — дело тонкое, и с первого взгляда ли они, К счастью, антициклины существуют, и к созданы различные и не очень сложные антици 54; 116; 148; 259; 499; 51?; 652; 685)).
125 124 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4 3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН Остановимся на одном из них [52]. Для описание этого антициклина нам понадобится понятие лексикографического упорядочения конечномерного пространства. О п р е де л е н и е 3, Говорят, что вектор х = (х',..., х') е К' лексикографически положителен (отрицателен), и обозначают х >-0 [х -ч О], если х ~ 0 и первая ненулевая координата вектора х положительна (отрицательна). Говооят, что вектор х е К' лексикографически больше (меныие) вектора уЕ К, и пишут х ~- у [х-ч у], если х — у>-0 [х — у-«О]. Другими словами, запись х >-0 означает, что существует номер р, 1 < р < < 1, такой, что х' =...
= х" ' =О, хг > О, остальные координаты хг+',... ..., х могут быть лгобыми. Лексикографическое неравенство х >- у означает существование такого номера р, 1<р<1, что х'=у',, хг '=дг ', хг > у», Для любых х, у е К' выполнено одно и только одно из соотношений: х >- у, х -ч у, или х = у. Ясно, что отношение >- транзитивно, т. е. если х >- у, у >- г, то х >- г.
Упорядочение векторов в их лексикографическом убывании (или возрастании) вполне аналогично упорядочена>о слов в словарях, что и объясняет присутствие слова «лексикографический» в определении 3. Опираясь на определение 3, несложно вывести следующие, важные для дальнейшего, свойства отношения >-: 1 если х >- О, то сгх ~- 0 для всех чисел а > 0; 2 если х >- у, то ах >- р»у для всех г» > 0; 3 если х >-О, у ~ О, то х+ ау ~ 0 для всех а > 0; 4 если х >. О, то у>- у — с»х для всех с» > 0 и у е К'.
Оп р е делен не 4. Пусть Мр — некоторое множество целых чисел (номеров), пусть С =(у, =(у,',..., у ) Е К', » Е Мр). Вектор у„г е Мр называется лексикографическим минимумом множества С, если для всех » е М либо у» ~ у„либо у» = х,. Обозначение: у, =!ех пппу, » «М» Лемма 1. Пуста Мр — конечное множество номеров и пусть во множестве С =(уг е К', » е Мр) все векторы различны. Тогда лексикографический мийимум множества С достигается на единственном векторе у е С, т. е.
у,-чу, Ч» еМр (случай у, ='у, при»фг исключается). Для определения номера г нужно последовательно строить множества Мр, М,=(г: геМ,у,'=пину), ...,М„=(г<'геМ;,у»= ппп угг) до г р мо г-3 тех пор, пока не будет обнаружено множество М„, 0 < м <1, состоящее из единственного номера 'г, который и будет искомым. Доказательство.
В простеишем случае, когда множество Мр состоит из единственного номера г, то, по определению, у, — искомый вектор. Поэтому пусть М, содержит более одного номе1оа. Тогда строим множество М,. Если М, содержит лишь один номер г, то уг, < у! для всех» е М, » ф г, и ясно, что у, = 1ех ш1пу, Если М, содержит по крайней мере два йомера, » «М» то строим множество М, = (» е М,; у,' = ппп у,.') и т. д. Пусть уже постро» «М| ены множества М, э М, Э... З М, р < 1, причем множества Мр,..., М„ содержат более одного номера.
Если М состоит из одного номера г, то у, — искомый вектор. Если М содержит более одного номера, то строим множество М„„, и т. д. В крайнем случае, когда множества М,..., М окажутся состоящими более чем из одного номера, этот процесс закончится построением множества М, = (г ЕМ,,: у,' = ш!и 1А!). Если бы М, содерг р ь~ жал два различных номера г, у, то у векторов у„у, все координаты были бы одинаковыми, т. е. у, = у,. Однако по условию во множестве С нет двух одинаковых векторов.
Следовательно, М, состоит из единственного номера г, причем у, = !ех пппу, Лемма доказана, С) >«М, г л Опираясь на отношение >- между векторами, введем отношения >-, >- на множестве симплекс-таблиц. Не стремясь к общности построений, мы можем ограничиться следующим определением, достаточным для дальнейших рассмотрений. О п р е де л е н и е 5. Симплекс-таблицу В = о(е, В) угловой точки е с базисом В назовем лексикографически положительной и будем обог значать Я >-О, если все ее строки Г, = (Т,р, у„,..., 7, ) >. О, » = 1,..., г (см.
табл. 3). Скажем, что симплекс-таблица В = В(«>„В,) лексикографически больше другой симплекс-таблицы В = В~«1, В,) и будем обозначать Ь Я, >- о„если строка Ь, = (Ь,р,..., Ь, ) таблицы о, лексикографически больше строки Ь, = (Ьрр,..., г",„) таблицы Я,. Для примера укажем, что таблицы 4-8, 13 лексикографически положительны, таблицы 9 — 12, 14, 15 не являются таковыми; симплекс-таблица 12 лексикографически больше симплекс-таблицы 11.
Нетрудно видеть, что если угловая точка «> с базисом В = (А,,, Ат ) невырожденная, то ее симплекс-таблица В >. О, так как тогда (см. табл. 3) 7„, = и' > 0 и, следовательно, Г, >- 0 при всех » = 1,..., г. Если точка о вырожденная, то 7» = 0 хотя бы для одного номера », 1 < « < т, и первый отличный от нуля элемент в строке Г,. может оказаться отрицательным и тогда Г, -чО.
(см., например, строки Äû таблицы 9). Впрочем, такой «недостаток» строки Г. легко исправить, если соответству>ощий базисный 1 столбец х" симплекс-таблицы переставить между столбцами Ъ' и х . Такая перестановка, равносильная перенумерации переменных, приведет к тому, что в строке Г» сразу после величины т,.р —— 0 окажется величина 7» =1 и строка Г, станет >-О, а на лексикографической положительности'или отрицательйости других строк это не отразится, так как 7м = 0 при всех г ф.«', 1 < г < г. Отсюда ясно, что последовательно переставляя указанным образом базисные столбцы хл для всех строк Г, ч О, нетрудно добиться, чтобы симплекс-таблица стала лексикографическй положительной.
Так, например, в таблице 9 для этого достаточно переставить столбцы х', хз между столбцами Ъг и х'. После сказанного теперь неудивительно, что симплекс- таблица 1 лексикографически положительна. А вот симплекс-таблица 2 может потерять это свойство, если в строке Г, окажется и>' = О, у„< О. Используя введенные лексикографические понятия, перейдем к описанию обещанного антициклина. Напомним, что применение симплекс-метода во всякой невырожденной задаче приводит к построению последовательности угловых точек ер,«>м ..., е,... со свойством (43). Так как йг = Г(е ), то согласно определению 4 свойство (43) будет означать, что соответствующие этим точкам симплекс-таблицы ор, ом..., Я„,... таковы, что В> ~- 3~ >- >.
Вр ~. (4?) При написании цепочки лексикографических неравенств (47) мы учли ь Ь Ь транзитивность отношения >- для симплекс-таблиц: если Я, >- о„д, >- В,, то 127 4 3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН 126 Гк 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Ь Я, >- Я,. Так как симплекс-таблиц конечное число, а в (47) повторение таблиц невозможно, то еще раз убеждаемся в конечности симплекс-процесса в невырожденных задачах. А в вырожденных задачах последовательность (/(е„)) обладает, вообще говоря, лишь свойством (41), а свойство (47), как видно из примера 3 (см. табл. 9-15), может не выполняться. Возникает идея: нельзя ли как-то дополнить правило (34), (35) выбора разрешающего элемента так, чтобы и в вырожденных задачах получались последовательности симплекс-таблиц со свойством (47)7 Реализация этой идеи приведет нас к антициклину.
Пусть е — какая-либо угловая точка множества Х с базисом В = (А,, ..., А, ) и с симплекс-таблицей Я = Я(е, В), пусть это будет таблица 3. Предположим, что таблица Я удовлетворяет условиям (34), и уже зафиксирован какой-либо номер й ф Х(е), й > О, из (34). Выберем номер з и разрешающий элемент Т„из условия — = 1ехш!и — ', з Е Х„(е)= (1: 1 < з' < т, уг > 0).
(48) 7ь 1лпм> 7м С помощью леммы 1 убедимся, что условие (48) однозначно определяет Г; номер з. Для этого нам надо показать, что множество С = (у> = — ', 1 е 7й ' е Х„(е) = М,) состоит из различных векторов. Допустим, что два вектора из этого множества оказались равными: Г,/Т,.„= Г,/Тм, р, й е Х,(е), р Ф к.
Тогда Г> = (.у,.„/-у,,)Г„, т. е. строки Г,, Г„в матрице Г = (у„у„... ..., 7 ) = (В '5, В-' А„..., В-'А ) = В .'(5, А) пропорциональны. Однако по предположению множество Х непусто, поэтому система (2), Ах = 6, совместна, и тогда, согласно теореме Кронекера — Капелли 1192; 353], гани(5, А) = гапиА = т. Отсюда и из невырожденности матрицы В ' следует, что гапдГ= гапдА = т. Это значит, что стро)ги Г„..., Г„матрицы Г образуют линейно независимую систему векторов, и никакие строки Г,, Г„ в этой матрице пропорциональными не могут быть.
Полученное противоречие показывает, что множество О состоит из различных векторов. Согласно лемме 1 условие (48) однозначно определяет номер з б Х„(е), причем для его практического нахождения можно воспользоваться конструкциями, указанными в этой лемме. Важно заметить, что лексикографическое правило (48) выбора разрешающего элемента не отменяет ранее сформулированное правило (34), (35), а, наоборот, включает его в себя, дополняет и уточняет его, В самом деле, в соответствии с конструкциями леммы 1 для поиска номера з из условия (48) мы в первую очередь образуем множество: М, = (з е Мь = Х (е); Т,ь/7„= гп(п Тю/7>„), котоРое в точности совпадает со множеством номеРов ген з, определяемых условием (35).
Отсюда, кстати, следует, что если множество М, состоит из единственного номера (так будет, например, в невы- рожденных задачах), то оба правила (34), (35) и,(48) определяют один и тот же номер з, один и тот же разрешающии элемент 7„. Если же М, содержит более одного номера, то правило (48) устраняет возможную в вырожденных задачах неоднозначность в выборе разрешающего элемента при пользовании правилом (34), (35). Итак, выберем номера к, з и разрешающий элемент Т,„= 7м(е) из условий (34), (48) и по правилам (26) совершим переход от симплекс-таблицы Я(е, В) угловой точки е с базисом В к симплекс-таблице Я(ю, В) угловой точки ш с координатами (36) и с базисом (37).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
