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