Ф.П. Васильев - Методы оптимизации (1125241), страница 35
Текст из файла (страница 35)
Отсюда следует, что У("а) > УИ) » ° ° ХЬр) > (41) Процесс получения последовательностей (н,), (Г(е )) в дальнейшем будем кратко называть симплекс-процессом. Заметим, что в примерах 1, 2 симплекс-процесс завершился за конечное число шагов выполнением одного из условий (32) или (33).
Однако всегда лн это будет так? Возможно, существуют канонические задачи, для которых симплекс-процесс может неограниченно продолжаться? Для ответа на этот принципиально важный вопрос, внимательнее проанализируем описанный симплекс-процесс. Прежде всего заметим, что поскольку варианты (32)-(34) изменения знаков величин Ла(н), Га„(н) исчерпывают все возможности н взаимоисключааот друг друга, то симплекс-процесс может быть бесконечным лишь в том случае, когда на каждом шаге этого процесса будут реализовываться условия (34). Каждая реализация условий (34) связана с переходом от одной угловой точки к другой угловой точке, от одной симплекс-таблицы к другой симплекс-таблице.
Это значит, что всякий бесконечный симплекс-процесс порождает последовательности угловых точек 120 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Г> 3, СИМПЛЕКС-МЕТОЛ. АНТИЦИКЛИН 121 4(еО)>>( 2) >У( р)> (43) Поскольку угловых точек конечное число, и из-за строгих неравенств они повторяться в симплекс-процессе не могут, то этот процесс закончится на каком-то шаге выполнением либо условия (32), либо (33). Впрочем, конечность симплекс-процесса здесь вытекает и из несовместимости соотношений (42), (43).
Таким образом, доказана Т е о р е м а 1. Пусть в канонической задаче Я множество Х непусто и нввырождгно, гапдА = г = гп < и, пусть еь — произвольная угловая точка этого множества. Тогда симплекс-процесс, начинающайся с точки е при выборе разрешающего элемента Т„иэ условий (34), (35), эавершйтся эа конечное число шагов определением некоторой угловой точки е, множества Х, в которой реализуются либо условия (32), либо (33), причем в случае (32) е„— решение задачи (1), Де ) = /, > — со, в случае (ЗЗ) задача (1) нг имеет решения, У, = -оо, Заметим, что хотя теорема 1 справедлива при любом выборе номеров к, г из условий (34), (35), но продолжительность симплекс-процесса и послед- (е,), их базисов (В,), симплекс-таблиц (Я,), где Я„является симплекс- таблицей точки е„с базисом В, причем, как видно из (41), соответствующая последовательность (У(е,)) не возрастает. Поскольку угловых точек и их базисов в задаче (1) конечйое число, то конечно и множество симплекс- таблиц этой задачи.
Отсюда следует, что симплекс-процесс может быть бесконечным лишь в том случае, когда хотя бы одна из симплекс-таблиц Я, соответствующая некоторой угловой точке е с базисом В, будет повторяться бесконечно много раз. Это значит, что найдется бесконечная подпоследовательность номеров (р,): р, < р, « ... р, < ..., такая, что е„ = е, В, =В, Я, =Я, У(е,)=У(е) при всех 1=1, 2,, В силу(41) это возможно лйшь тогда, когда /(е ) = сопз1 42'р > р,. (42) Таким образом, необходимым условием бесконечности симплекс- процесса является условие (42), которое должно выполняться, начиная с некоторого номера р .
Посмотрим, когда это возможно. Начнем с выяснения того, когда /(ю) =/(е) и когда У(ю) </(е), где угловая точка ю получена из угловой точки е в результате одного шага симплекс-метода. В силу Условий (34), (35) с2„(е) > О, Тм(е) > 0 и, кРоме того, ~, (е) = е' >0 как базисная переменная угловой точки е. Отсюда и из формулы (38) следует, что /(>е) = У(е) тогда и только тогда, когда е' =О, т. е, е — вырожденная угловая точка. Такое явление мы наблюдали в примере 1 при переходе от таблицы 5 к таблице 6.
Таким образом, среди канонических задач имеет смысл выделять задачи вырожденные и невырожденные. О п р е д е л е н и е 1, Задачу (1) называют вырожденной или нгвырожденной, если множество Х в этой задаче содержит хотя бы одну вырожденную угловую точку или не содержит таковые, Покажем, что в невырожденных задачах (1) симплекс-процесс всегда конечен. В самом деле, в таких задачах все базисные координаты угловой точки е будут положительны. Поэтому какими ни были номера к, г, определяемые из условий (34), (35), всегда е' > О, и, согласно (38), тогда Дю) < Де).
Отсюда следует, что в невыро>кденных задачах симплекс-процесс порождает такую последовательность угловых точек е, е„..., е„,..., для которых няя точка е, могут существенно зависеть от выбора этих номеров. Впрочем, интересно отметить, что если номер к из условий (34) как-то уже выбран и зафиксирован, то в невырожденных задачах номер г условием (35) определяется однозначно. В самом деле, для невырожденной угловой точки ю =(ю',..., ю") с базисом (37) координаты ю' >0 для 2 фа, 1 < 2 < т. Из формул (36) тогда следует, что е' — гйхех/7~2 > 0 или е'/Т>„> ех/Т„для всех 2 Е Х„(е), 2 ~ г, так что минимум в левой части (35) будет достигаться на единственном номере г е Хь(е).
Отсюда следует, что условие (35) может неоднозначно определять номер г лишь в вырожденных задачах, Кстати говоря, если в (35) минимум достигается по крайней мере на двух номерах г,1 е Х,(е), г ф 1, то, согласно формулам (36), ю' = юх = О, т.
е. угловая точка ю непременно будет вырожденной (так случилось в таблицах 4, 5). Конечно, точка ю может быть вырожденной и в том случае, когда условие (35) однозначно определяет номер г е Х,(е), для которого е' =0 (как видим, тогда сама точка е вырожденная); в этом случае, как видно из (36), у точки е> базисная координата ю' = 0 (см. табл. 5, 6). Впрочем, если (44) г Е Х„(е), е' = О, то минимум в (35) равен нулю и будет достигаться именно на этом номере г, (и на всех других номерах 1 е Х (е), для которых е" = 0) и, согласно формулам (36), (38), тогда ю = е, Х(ю) = У(е). Это значит, что при выполнении условий (44) мы сделаем один шаг симплекс-метода и останемся в той же точке ю = е, лишь заменив один ее базис В = (А,..., А, ) на другой базис (37) (именно так случилось в таблицах 5, 6).
Здесь возникает естественный вопрос: при выполнении условий (44) не может ли привести дальнейшее применение симплекс-метода к бесконечному перебору базисов угловой точки е, не может ли здесь реализоваться бесконечный симплекс- процесс? Оказывается, так вполне может быть. Приведем пример вырожденной задачи 1?75), в которой симплекс-процесс приводит к так называемому зацикливанию, заключающемуся в бесконечном циклическом переборе базисов одной и той же угловой точки (другой пример — см. упражнение 6).
П р и м е р 3, Рассмотрим задачу минимизации функции (45) /(х) = х' — х4 хэ -~- хг при условиях х =(х', х2, х>) > О, х' + х4+ хэ+ хз+ х" = 1, — 2х'+х'+х' — Зхз+4х'=О, Зх'+х +4х' — 2х +х2=0. (46) Нетрудно видеть, что точка ер — — (0,0,0,0,0,0, 1) является угловой точкой с базисом (А„А„А,) = В, система (46) представляет собой приведенную систему этой точки. Образуем симплекс-процесс, взяв в качестве начальной точку е, с указанным базисом. В таблицах 9 — 15 приведены результаты вычислений для первых точек е„е„..., е,; в кружочках указаны разрешающие элементы этих таблиц.
В таблицах 9, 11, 13 разрешающий элемент условием (35) определяется неоднозначно, в таблицах 10, 12, 14 разрешающий элемент находится однозначно. Как видно, таблицы 9 и 15 совпадают 123 122 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ $3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН Таблица 1б Таблица 9 Таблица !О Таблица 11 Таблица 12 Таблица 13 Таблица 14 выбор тех ж есконечному ческий переб „А)- (А, г> 4г) огра ммирова е разреша- симплексор базисов ,А,А,) — ~ Любопытно ния меньше симплекс-мето процессу и с его адача (1), Если нескольких выр ее сложные бе вания с участпе д действипомощью функция ожденных сконечные м,в цикле бесконеч- 5) выбора с-'процесс, ся за ко- 3)? Поло- основания принципе, тодом. ыбора разкливания й канони- нее, появления равило (34), (3 ачи (1) симплек и точки, завершал вий (32) или (3 начение для об райней мере в ия симплекс-ме (35) правило в о избежать заци роцесса во всяко образом; гдля котов несколь.
и номера уточнение ора разреере 3, как ия. Одна- в общем ния такое едовательостроение ществуют мени уже имер, [52; яют следующим ), выбирают тот и таких номеро е такой фиксаци вий (35). Такое означность выб енным и в прим жать зацикливан показывает, что программирова кливання и, сл ит о том, что и неясно даже, су настоящему вре клины (см., напр и поэтому, если на следующих шагах продолжать ющих элементов в том же порядке, то придем к б процессу, в котором будет осуществляться цикли точки и<, в следующем порядке: (А„А„А,)-+ (А„, А отметить, что длийа цикла в задачах линейного пр шести не бывает [??5).
Этот пример показывает, что описанный выше тельно может привести к бесконечному симплекс- может быть решена не всякая каноническая 3 ,Г(х) = (с, х) принимает одинаковые значения в угловых точках, то, по-видимому, возможны бол симплекс-процессы, в частности, явления зацикли базисов различных таких точек. 4. Можно ли избежать зацикливания или, точ ных симплекс-процессов? Нельзя ли уточнить п разрешающего элемента так, чтобы для любой зад начинающийся с произвольной начальной углово" нечное число шагов реализацией одного из усло жительный ответ на эти вопросы имеет важное 3 симплекс-метода и означал бы, что можно, по к решить любую задачу линейного программирован Определен не 2, Любое уточняющее (34), решающего элемента, с помощью которого можн или, точнее, появления бесконечного симплекс-п ческой задаче (1), назовем антициклином.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
