Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 30
Текст из файла (страница 30)
Зто значит, что если номер й из условий (15) зафиксирован, то номер переменной и', которая выводится пз числа базисных переменных, и разрешающий элемент 7,» сггзгплекс-таблицы в невыроягденных задачах определяются однозначно. Итак, мы выяснили, что в невырожденной задаче с помощью симплекс-метода можно осуществить переход от угловой точки, не являющейся решением задачи (1), к другой угловой точке со строгим уменьшением значения функции У(и)= (с, и).
Учитывая, что число угловых точек мноятества (2.3) конечно, заключаем, что случай П1 (условпе 15') бесконечно повторяться не может и процесс закончится тем, что на каком-то шаге симплекс-метода либо реализуется случай П (условие (14')) и выяснится, что 1п1(с, и) = — оо — задача (1) не имеет решения, лиоо и реализуется случай 1 (условпе (13') ), означающий, что рассматриваемая угловая точка является решением задачи (1). Таким образом, показано, что если в невырождеиной канонической задаче известна какая-либо угловая точка множества, то, отправляясь от нее, с помощью спмплекс-метода за конечное число шагов можно выяснить, разрешима ли эта задача, и если разрешима, то найти ее решение. 3.
Перейдем к рассмотрению вырожденных задач (1)'. Посмотрим внимательнее, к чему может привести применение симплекс-метода, если о — вырожденная угловая точка. Если в этой точке реализуется случай 1 или 11, то выводы останутся прежними: в случае 1 о — точка минимума функции <с, и) на УУ, а в случае П ш1(с,и) = — со; в обоих случаях процесс прекраи щается. Остается рассмотреть случай П1. Конечно, и в случае П1 может оказаться, что базисные координаты точки о с номерами 1»нУ„будут положительными, и тогда, как видно из фор- 124 элементы линейного пРОГРАммнРОВАнпя 1РЛ. 3 мулы (18), симплекс-метод приведет к новой угловой точке к» со значением функции»(1Р)(У(и).
Однако здесь возможна и худшая ситуация, когда 7.»>0, и' =О. Ясно, что тогда ганг» н минимум в (16) ичи (16') будет достигаться именно на этом номере г. Из формул (17), (18) в этом случае получим 1Р = и, У(и») = 1(и). Это значит, что в результате применения симплекс- метода мы оказались в прежней же угловой точке и лишь заменили один ее базис А„ ..., А, другим базисом (19). Возникает вопрос: не приведет лн дальнейшее применение симплекс-метода к бесконечному перебору базисов угловой точки Р? Поскольку угловая точка имеет конечное число базисов, то при фиксированном правиле выбора разрешающего элемента (например, часто выбирают разрешающим элементом ту величину 7„, у которой номера Й, г являются наименьшими среди всех номеров, удовлетворяющих условиям (15), (16) или (16') ) это привело бы к так называемому за»1икливани1о, т.
е. к бесконечному циклическому перебору базисов точки Р. Оказывается, действительно существуют примеры задач (1), в которых возможно зацикливание (см. ниже упражнение 6.7). Можно ли избежать зацикливания? Каким для этого должно быть правило выбора разрешающего элемента? Любое правило выбора разрешающего элемента, с помощью которого можно избежать зацикливания в задаче (1), назовем антициклином. К счастью, имеются достаточно простые антициклины. Остановимся на одном из них. Пусть Р, — некоторая угловая точка множества (2.3) с базисом А»,, ...,А;„. К симплекс-таблице точки Р» добавим еще г столбцов е„..., е, единичной матрицы порядка гХ г и в результате придем к табл. 4. На каждом шаге симплекс-метода вновь добавленные столбцы будем преобразовывать по тем же правилам, по которым преобразовываются столбцы небазпсных переменных, остающихся небазисными и на очередном шаге симплекс-метода (см.
(25), а также (4А1)). Пусть уже сделано несколько шагов симплекс-метода с расширенной симплекс-таблицей н найдена очередная угловая точка иь пусть в результате преобразований в дополнительных столбцах первоначальных е„ ..., е„ появились столбцы »?е ..., »?„ где »?, имеет координаты с?„, ..., о»„ (1 = 1, ..., г). Пусть табл. 5 представляет собой расптиренную симплекс-таблицу точки Р,— в ней для простоты излоязения предполагается, что базисом Р, являются столбцы А,, ..., А, (как уже отмечалось. этого всегда можно добиться перенумерацией переменных). Пусть Ь» > О, ?,=П: 1<1<г, т»>0) ~8, Образуем множество 7»1 — — ~ю г е=?», ш(п Р1/71» = Р»,'7,»). В не' »н1» вырожденной задаче, как было замечено выше, мноятество ?м всегда состоит из единственного номера г.
В вырожденных за- 126 элементы линеиного пРОРРАьгыиРОВАния (гл. 3 дачах это не всегда так, п множество Х„может состоять пз двух и более номеров. В последнем случае образуем множество Уаз = (8: 8е= гдгт шгп г(гг/уза = с(зг/угь) Если уже определено множе пнгат ство уь (т ) 2) и оно содержит не менее двух номеров, то образуем множество та,т+г = ~8: 8 е= гам~ шзп Йгж/Уга = г(гю/Узь). гьж Ниже будет показано, что в конце концов мы получим множество 1м (1 ( ( ( г+ 1), состоящее из единственного номера 8, причем все предыдущие множества 1м (1=1, ..., ( — 1) будут содержать не менее двух номеров.
Выведем переменную с полученным танин образом номером 8 из базисных и вместо нее в базисные введем переменную и'. Оказывается, применение на каждом шаге симплекс-метода описанного правила выбора номера 8 позволяет избежать зацикливания, и в результате через конечное число шагов симплекс-метода с расширенной симплекс-таблицей процесс закончится реализацией случая ( или 11. Антициклин для задачи (1) описан. Строгое обоснование этого антициклина дается в з 4. Следует заметить, что хотя среди прикладных задач линейного программирования вырожденные задачи встречаются довольно часто, но зацикливание бывает крайне редко.
Кроме того, использование антициклина на каждом шаге симплекс-метода приводит к заметному увеличению машинного времени ЭВМ, требугощегося для решения вадачи. Поэтому на практике чаще всего пользуются упрощенным правилом выбора номеров /г и 8 из условий (15), (16) или (16'), причем если выбор здесь неоднозначный, то берут наименьшие номера, удовлетворяющие указанным условиям. И лишь в том случае, когда обнаруживается зацикливание, принимают опнсанньш выше плн какой-нибудь другой антициклин, а после того, как зацикливание будет преодолено, снова возвращается к упрощенному правилу выбора разрешающего элемента.
Любопытно отметить, что длина циклов в задачах линейного программирования меньше шести не бывает. 4 4. Антицпклин 1. Нак было выше замечено, с практической точки зрения проблема зацикливания, по-видимому, не представлнет особой важности. Но с теоретической точки зрении указание хотя бы одного правила выоора разрешающего элемента, позволяющего избежать зацикливания, принципиально важно для полного обоснования симплекс-метода для канонической задачи /(и) =<с, н>-+1вй и зн (/= (о зп Е": и > О, Аа = Ь).
(1) Покажем, что описанное в конце 1 3 правило выбора разрешающего элемента в самом деле является аптицинлнном. С этой целью рассмот- 128 ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ угл. 3 Возьмем произвольное е (0( е < е~ =тпш(еб т>)) и пропавольпую угловууо точку и(е) множества (У, с базисом А, ..., А .
Тогда базисные координаты и(е) =1и1(е), ...,и'(е)) точки и(е), определяемые условиями А из(е)+ ... + А и "(е) = Ви(е) =Ь(е), представпмы в виде 11 уг и(е) = В 1Ь (е) = В 1Ь + ЧЭ. ег(В 1В ) 1=1 и, следовательно, принадлежат рассмотренному выше множеству ыпогочленов, а небазисные координаты, как им и полагается, равны нулю. Из того„что и(е) ш (Уо слеДУет, что и(е) > О.
Но тогда в силУ выбоРа е из 0 ( е ( е, имеем и(е) ) О, т. е. и(е) — невырождепная угловая точка множества 1У,. Отсюда следует невырожденность задачи (2) при всех е (О ( е ( е,). Утверждение 1) леммы доказано. Пусть и (т) — какая-либо угловая точка ыножества (ут (О < т ( е1) с базисом А..., А., т, е. уг' А иг(Т)+ ... +А и "(у) =Ви(у) =Ь(у), ит(у)=0,1чьу, 1=1,...,г, гдо В = >уА ... А 1, иу > = (и ' (у), ..., и'г (у)).
по доказанному выше угу' (т) р(Т) > О. Покажем, что точка и(е), определяемая условиями (3), является угловой точкой множества (у. при каждом е (О ( е < е~). Для этого прежде всего заметим, что условия (3) означают, что Аи(е) = Ь(е) при 0 ( е < ( еь Перепишем условия (3) в виде и(е) =В Ь+ зг,' ез(В ~Вгу, иг(е) =О, У~у>, 1=1, ...,г.
(4) 1=1 Отсюда и из определения е~ видно, что ни одна из координат вектора и(е) не может обратиться в нуль ни при каком е (О ( е ( е~). Но нам ух1е известно, что й(т) ) О. С учетом неврерывности п(е) тогда занлючаем, что и(е) > 0 при всех е (0< е < е~). Отсюда и из (4) при е-ь+О имееы Пш и (е) = В 1Ь = и (0) = и ~ )О. е ье Таким образом, показано, что точка и(е), определяемая условиями (3), при всех е (О ( е < е,) имеет неотрицательные координаты. Следовательно, и(е) 1Н(у, (0< а < е~).
Из (3) с помощью теоремы 2.1 заключаем, что и(е) — угловая точка ыиожества УУ, с базисом А, ..., А при каждом е уг (0( е ( е,). 2. Предполагая, что условия леммы 1 выполнены, рассмотрим подробнее один шаг сиыплекс-метода для задачи (2) при фикснрованноы е (О < е < е~). Пусть и(е) = (и'(е), ..., и" (е)) — какая-либо угловая точка множества УУ,. Без ограничения общности можем считать, что столбцы Аь ..., А, являются базисом, а координаты (и'(е), ..., и'(е)) =и(е) — базисными координатами этой точки. Согласно лемме 1 задача (2) невы- рожденная при 0 < е < еь поэтому р(е) ) О, игь1(е) ~= ...
= и" (е) = О. Обозначим В = (А, ... А„). Поскольку Аи(е) = Вр(е) = Ь(е), то й(е) = = В 'Ь(е) ) О. УмножаЯ УРавнение Аи = Вв+ Аг Ь иг+~+ ... + А„п" = = Ь(е) =. Ь+ ~ е>В на В-' слева, получаем следующее соотношение 1=1 АНТИЦИКЛИН между базисными переменными и = (я', ..., и") и небависными переменными иг+», ..., и" точки и(е): и и+ ~ В 1Ааиь =В 1Ь(е) =о(з) =В 1Ь+ ~чД~ еа(В 1В1). (5) а=;+1 Обозначим В 1А„= ™, й =В В = ..., з — В 1Ь Тогда соотношение (5) можно переписать в следующей покоординатной форме: и +7 „+ и+1+ ... +7 из+ ...+71„и"=и~+д з+ ...+ага» а ( г+1 ( (.»» ( (, з а+»( ( ),1 г ° ° (6) г~1 а для базисных координат и(е) = В 1Ь+ угви"= о" + «,1з+ " +й~з"» г ~к~~ е)(В 1В1) получим '()= '+Х й,,~1, 1=1, ...,г.
(7) Далее, по аналогии с (3.8), с помощью равенств (6) или (7) нетрудно выразить функцию У(и) = <с, и> через базисные переменные: У(и) = У(и(з)) — ~ Л»и, Л =(с, В 1А~~ — с, »=а+1 (8] Учитывая, что Л» = <с, В 'А»> — с» = О при 1 = 1, ..., г, на основе представлений (6), (8) выпишем симплекс-таблицу для угловой точки и(з), выделив в ней для векторов й», ..., о„дополнительные столбцы. В результате получим табл. 6. Заметим, что точка и = (г', ..., г") = з(О) согласно лемме 1 является угловой для множества У с тем же базисом Аь ..., А„ что и точка и(з). Ясно также, что выражения (3.5), (3.8) базисных переменных й = (и', ..., и') угловой точки г и функции У(и) через небазисные переменные пр+», ..., и" получаются соответственно из (6), (8) при е = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
