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