Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 31
Текст из файла (страница 31)
Это значит, что выписанная ранее табл. 5 является симплекс-таблицей точки о, расширенной дополнительными столбцами й», ..., й;, кстати, теперь выясняется, что элементы»1»„..., й»г Ой строки табл. 5 представляют собой коэффициенты многочленов (7). Опираясь на симплекс-таблицу 6, сделаем один шаг симплекс-метода нз угловой точки г(е) для задачи (2) и посмотрим, чему это будет соответствовать в задаче (1).
Как и в Ь 3, рассмотрим три случая, Случай 1. В нижней строке симплекс-таблицы 6 величины»Ь» ( О при всех »=г+ 1, ..., и. Тогда, как и в Ь 3, нетрудно показать, что о(з) — решение задачи (2), т. е. (с, и(е)) =1п((с, и) ) — о». Теперь и ба! с» (е) са (е) ш!и — = —, а»н 7, (О) »=гй ™ уж ' й где и'(е) вадино выражением (7), определяем номер а. Поскольку задача (2) нееырожденная, то номер а и, следовательно, раарешающий злемент 7,А нз (9) определяются одпозначно. Тогда, рассу»кдая так же, как в 1 3, выведем нз числа базисных переменную и', а переменную и" введем в число базисных и придем к следующей угловой точке ш(е) = (из'(е), ..., ш" (е)) с координатами 1' ш (е) = е (е) — — и (е) = е + д »1"з — — ~ с -(- г »7 е уш а» чч ! 2»й а чзч ,Д» П, ~~» аа / ай »'=» ай » уш а ~ч У»й У»А» Тай (10) а »с (з) = — + — 'з е й й (е) е' 'кз»»»1 Тай 7»А ° » !»й ш'(з)=0,1 з,г+1,...,й — 1,й+1,...,а.
Таким обрааом, в симплекс-таблице угловой точки ш(е) в столбце свободных членов будут находиться числа а 3 3 узй узй' '' Узй с' ,й уж в' ш+» = "+» — у —, ..., з" = сг — у — »+НА у *" ай у, ° а з 1-м дополнительном столбце »» (1 = 1, ..., г) появятся величины 1 уы аз »» ° ° =»7 ° »», » 1 °,а 1 »+1 ...
г»» ° = (11) — 7 »1 з"' з з" з йз у зй ай Это аначит, что дополнительные столбцы»»» симплекс-таблппы в задаче (2) преобразуются по тем же правилам, по которым преобразуются столоцы, соответствующие небазнсным переменным, остающимися небазисными и заме~им, что в нижней строке симплекс-таблицы б угловой точки и = о(0) находятся те же величины Ь» < 0 (» = г+ 1, ..., п). Следовательно, с = с(0) — решение задачи (1), т. е.
(с, о) = 1п1 (с, и) > — зо. н Случай П. Существует номер й (г+ 1< А<и) такой, что ЬА > > 0 и 7»А < 0 при всех 1= 1, ..., г. Тогда, как н в 1 3, нетрудно показать, что !п1 <с, и) = — со. Поскольку в симплекс-таблице б угловой точки пв с = с(0) в столбце переменной и" находятся те же величины ЬА > О, '1ы < 0 (» = 1, ..., г), то и в задаче (1) будем иметь !п1(с, и) = — ов. и Таким образом, в случае П задачи (1) и (2) не имеют решения. Случай П1. Существуют номера й, » (г+ 1< А <и, 1<1< с) такве, что Ьа > О, 7»а > О.
Тогда множество 1а= (и 1<»< г, 7»л > О) непусто и из условия 132 инементы линейнОГО пРОГРАммиРОВАния 1ГЛ, Э на следующем шаге симплекс-метода (ср, с (3.25)). Далее, из (8), (10) следует, что У (ю (е)) = У(и(з)) — 54 — < 1 (и(з)). ив (е) ув» Наконец, исходя из равенств (6) и польауясь формулами, аналогичными (3.21) — (3.23), нетрудно показать, что остальные элементы 7ы, б; симплекс- таблицы 6 при переходе к следующей угловой точке ю(з) преобразуются по прежним же формулам (3,24) — (3.26).
Описание одного шага симплекс- метода в задаче (2) закончено. Теперь вернемсл к задаче (1). В угловой точке и = и(0) в качестве разрешающего элемента выберем тот же элемент Ты, который обеспечил выше переход ог точки и(з) к точке ю(з). Такой выбор разрешающего элемента в задаче (1) вполне возможен, так как в симплекс-таблице 5 угловой точки и = и(0) в столбце переменной в» находятся те же величины Ь» > О, Тв» > 0 при вви1», 7ы < 0 при 1Ф 1м что и в симплекс-таблице 6.
Кроме того, ниже в лемме 2 будет покааано, что для того же номера в, который был однозначно определен из условия (9), справедливо равенство (ЗЛ6). Конечно, в отличие от условия (9) в условии (ЗЛ6) минимум может достигаться и на некоторых других, не совпадагощих с в номерах из 1», поскольку невырожденность задачи (1) мы здесь не предполагаем. С выбранным разрешающим элементом 7,» сделаем один шаг симплекс-метода по формулам (3.17), (3.18), (3.24] — (3.26) и из точки и = и(0) придем к следующей угловой точке нь Сравнение формул (ЗЛ7) и (10) показывает, что ю = ю(0); ясно также, что расширенная симплекс-таблица угловой точки ю = м(0) может быть получена из симплекс-таблицы точки ю(с) при е = О. Отсюда следует весьма важный для дальнейшего вывод: если в возмущенной задаче (2) с помощью симплекс-метода совершается переход от угловой точки и(е) к другой угловой точке ю(з) с помогцью разрешавощего элемента 7,» нз (9), то в задаче (1) при выборе того же разрешающего элемента 7.» произойдет переход от угловой точки и = и(0) к угловой точке ив = ю(0).
Рассмотрение случая П1 закончено. 3. Теперь уже нетрудно дать обоснование антицпклина, изложенного в конце 1 3. Пусть и = (и»г, ..., и") †некотор угловая точка множества У с базисом А , ..., А.. Обозначим В = /А. ... А, ), и = (и ', ..., и Согласно теореме 2Л Аи =А.ив+...+А йг=Ви =4, и1=0, !Ф)0 1=1,...,г, в, ' ' ' 1, 1 так что и~ = В-'Ь > О. Рассмотрим следующую возмущенную задачу: ) ~ в и,=~: ~в, А =ь(в-~-3- 2 в ), ивв получающуюся из задачи (2) при В = (А ... А ) =В.
Воз»»ге»г точку 1» )г) и (е) = (идт(з), ..., и" (е)) с координатами ив' (з) = ив' + е', и( (з) = О, 1 ~ 1,, в = 1, ..., г. Напоминаем, что здесь и в (12) е' — Ья степень числа з > О. Поскольку и, > О, то ясно, что ив(з) > О, причем и (е) = (й»(е), ..., и ' (е)) > 0 при 124 всех е ) О. Кроме того, т Аи (е) = »ч А ог~(е) ~ А (зо' ) ег) Ь+ ~~~~~ А ег Ь(е) в=х»=1 1-1 Следовательно, и»(е) ш 47, при всех е) О, причем согласно теореме 2.1 э,(е) — угловая точка множества (Г» с тем же базисом А, ..., А., что и Рг точка зь Полезно также заметить, что з» = и,(0). Таким образом, множество (Г„образованное иэ множества У с по- мощью невырожденной матрицы )7 = В, непусто при всех е ) О.
Согласно лемма 1 тогда задача (12) невырожденная при каждом е (О < е < е~). При- меним к задаче (12) симплекс-метод, беря в качестве начальной угловой точки множества (Г» введенную выше точку ш (е) и считая, что 0 < е < еь В силу невырожденности этой аадачи мы получим конечную последователь- ность угловых точек и,(е), ..., и (е) из множества (Г» со значениями функ- ции Х(ш(е)) > ... ) У(и (е)), причем в последней точке реализуется либо случай 1, либо случай П. Из проведенного выше исследования следует, что если применить сим- плекс-метод к задаче (1), беря в качестве начальной точки ш и выбирая на каждом шаге те нге разрешающие элементы, которые в задаче (12) при- вели к последовательности ш (е), ..., и (е), то получим последовательность угловых точек и» = з»(0), ..., г = о (0), причем в последней точке и,„ будет реализовываться соответственно либо случай !, либо случай Н.
Выше было выяснено, что в случае ! г (е) — реп»ение задачи (12), а о и (О)— решение аадачи (1), а в случае !! аадачи (12) и (1) не имеют решения. Тем самым показано, что если задачу (1) решать симплекс-методом, выбирая на каждом гпаге разрешающий элемент с помощью возмущенной задачи (12) указанным выше способом, то зацикливания не будет и за конечное число шагов этого метода выяснится, имеет ли задача (1) реше- ние, и если имеет, то оно будет найдено.
4. Однако изложенный способ, поаволяющий набежать зацикливания и имеющий принципиальное значение для обоснования симплекс-метода, пока что не слишком удобен для практического использования, поскольку требует рассмотрения возмущенной задачи (12) при достаточно малых и заранее неизвестных е ) О. Нельзя ли все-таки определить разрешающий элемент на каждом шаге симплекс-метода, явно не прибегая к возмущенной задаче (12)? Оказывается, можно. Чтобы понять, как зто делается, вспомним, как выбирается раарешаю- щий элемент 7,» в задаче (2) (или (12)): сначала фиксируется номер Ь небазисной переменной с величиной Л» ) 0 (если таких Ь несколько, то можно из них выбрать наименьший), а затем иа условия (9) одно- значно определяется номер в и тем самым находится разрешающий элемент 7.». Важно ааметить, что коэффициенты многочленов з'(е), опре- деляемые формулами (7), можно узнать, явно не привлекая возмущенную задачу (2),— эти коэффициенты расположены в столбце свободных членов и дополнительных столбцах расширенной симплекс-таблицы (см.
табл. 4, 5). В частности, для начальной точки ш с базисом А , ..., А в силу выбора матрицы В = (А ... А1 ) = В имеем Ыг = В-'А» = еь что и отражено в табл. 4, а в дальнейшем при переходе от одной угловой точки к следую- щей величины 1-го дополнительного столбца преобразуются по формулам (11), аналогичным формулам (3.25). Таким образом, коэффициенты многочленов иг (е) — — 11 (е) = сю+ с, е+ ... + »ые" на каждом шаге симплекс-метода могут быть определены без явного при- влечения возмущенной задачи по формулам: сю = о'/7ы, сы = »!»»!7»ь 134 Влкмниты линнинОГО ~РОГРАммиРОВАния «ГЛ.
3 0 1, ..., т). Заметим, что все эти многочлевы различны. В самом деле, если бы /»(з) ен/н(е) йри»т'* и, то коэффициенты (сн) и (с») были бы раВНЫ: СЫ = С~«ИЛИ б»» = б «т»Ь/тне (/ 1, ..., т). Эта ЗваЧИЛО бЫ, Чта пропорциональны»-я н ж-я строки в матрице Р (б» ... б,) из дополнительных столбцов расширенной симплекс-таблицы. Однако это невозможно, так как на каждом шаге матрица Р невырожденная — она является произведением невырожденных матриц виде (А ... А» «на /«. Таким образом, приходим к следующей аадаче: задано конечное число различных многочленов /»(е) = о»(е)/у»ь (» вя /ь) и требуется найти и«(п /»(е) при достаточно малом, но заранее неиавестном е ) О, Здесь нам »ыта будет полезна Л е м м а 2.
Пусть дано множество многочлсков /» (е) = с»г+ сие+... + с»,е', О < е < е», » «н Юе, степени не выие т, среди которых нвт совпадающих; дг — конечное множество номеров. Тогда существует число ег (О < ег( е») такое, что ш(п /» (е) «ы8г будет достиваться на единственном мковочлене, номер которого не вависит от з (О ( е < ег). Для определения номера этого мноеочлена нужно рекуррентным образом строить множества дш 8 =~г«гшдг, с =ш1п с 8, ° °,О»а+« = (г» г«ма»к, С, = Ш1п с»„,~» ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
