Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 32
Текст из файла (страница 32)
до тех пор, пока не будет обна»»Яз»п ружено множество д» (О < 1( т+ 1), состоящее иг единственного номера г, который и будет искомым номером. Доказательство. Если множество дг состоит из единственного номера в, то утверждение леммы тривиально. Если же дв состоит более чем из одного номера, то перейдем к рассмотрению множества 8». Иэ определения множества д» следует, что все многочлены /,(е) с номерами г «в д» имеют один и тот же младший коэффициент с, =ш1в с« .
Возможно„что «язв д«дь Тогда положим ее» = е» и заметим, что ш1п /» (е) = ш1в /» (з) при зо всех е (О < е ( еы). Если д» ва.дь т. е. дв~д» ча Я, то положим зо«ш»п~1' з«' ( ш«п с»е сге) гьа о«) д О т ' 2с~,«»в8,,8„ т где с шах ~ ) с» ). Тогда для всех в жди рш до ~8», О < е < еы имеем »~яв» « /г(е) ( с.в+ се < сто — са(/г(з), т. е. /,(е) </г(е).
Это значит, что ш1в /~ (е) при всех е (О ( е ( еы) может достигаться лишь на многочленах Ьия с номерами г»н Я», т. е, НИп /«(е) = шш /» (е) ( /р (е) при всех е (О < е <1 «ыяе ( ев») и всех р ш д». В частности, если д» состоит из единственного номера г, то этот номер будет искомым для всех е (О ( е< ее» = ег) и лемма будет доказана. Если же д» состоит более чем из одного номера, то перейдем к рассмотрению множества дг и т. д. Пусть уже рассмотрены множества Бгшд, ш ...
Изб,„(1< т(т), найдено число звн .м О и покааано, что: 1) ш(п / (е) ш»п /» (е) < / (е) для \»ЗБо»Ы8е» всех з (0< е< егн) и всех равд„; 2) все многочлевы /г(е) о нокерами е ш Я имеют одинаковые козффициевты при степенях о', е', ..., о 3) Я состоит более чем из одного номера. рассмотрим множество Я,+ — — ~з: зон Я„„е, ш1п сг,ф Отсюда о !ыню учетом индуитивного предположевия 2) заключаем, что все многочлены /,(е) с номерами з ш Я +«имеют одинаковые козффициенты при степенях е', и1, ..., зи. Возможно, что Я„+з=Я . Тогда положим ео,„+~ ее >О и с учетом индуктивного предположения 1) ааметим, что ш(п/1(е) !мне ш(п /!(е) </р(е) при всехО(о(ео, +ь рфЯ +ь емню.~.г Если же Я .д ча Я, то положим 1! ее,„+, — — ш!п~еою; — ш(п сгт езю)* зев Яю+т~~ > О.
' 2Е(!Мню~,я,„+ Тогда для всех зш Я +ь р он Я„~Я оь О < е < аь +, имеем /.(е) (с«о+ с„е+ ... + с. ю,о -'+си(е«+ ее) ( ( е о+ смз + ... + с., ~з -'+ е'"(с,„„— ее) = соо+ со«з+... ... + ео, „, ~ею-'+ соиаю — за+'с (/о(е), т. е. /,(е) < /о(е). Это значит, что ш!и /1(е) при всех е (О( е< еь,и+з) 1м ею может достигаться лишь на многочленах с номерами е ш Яи+ь т. е.
ш1п/1(е) = ш1п /!(з) </ (е) при всех е (О< с < зе,~ш) и всех емяе !Ыню+Г рФЯ-+ Если Я +«состоит из единственного номера е, то он и будет искомым номером для всех а (О ( е < е,, +~ = аг) и лемма будет доказана. Если же Я +, состоит более чем па одного номера и ш ( г, то переходим к рассмотрению множества Я +, и т. д. В самом худшем случае мы доберемся до последнего множества Я + — — (г: газ Я„, е„= шш ег„), зная, что « шш /!(е) = ш1п /1(е)</р(е), 1«то Я«+ь О< е < еь,«+ь и что все много!мне 1ы8„о 1 члейы /*(с) при ген Я,ь«имеют одинаковые коэффициенты при степенях ео, в', ..., е'. Однако по условию леммы среди многочлеяов (/~(е), ген Яе) нет двух одинаковых. Следовательно, множество Я«+~ будет состоять из одного номера г. Остается привять зз = ео, «+ь Если в лемме 2 взять /в(е) = ое(з)/увь (! ш!ь Яо) и применить изложенное в ней правило определения номера г, на котором достигается ш!п о! (е)/у;„, то мы получим именно тот самый аитициклин, который был !ыга описан в конце 1 3.
Этот антициклин в литературе часто называют лекеикогра«/«нивским краеилом выбора разрешающего элемента. Поясним это название. Определение 1. Вектор а (а', ..., а") называют лексикографически положительным и пишут а ) О, если а ~ О и первая иа отличных от нуля координат вектора а положительна. Вектор а ш Кю называют лексикогра4ически большим вектора 6 ем Еа и обоаначают а) Ь, если а — Ь ) О. другими словами, а) Ь означает, что а' > Ь' или же а' = 6««но аг > Ьз, или же а' = Ь', аз = Ьз, но аз > Ь' и т.
д. для любых а, Ь ен Е"' выполнено одне и только одно из соотношений: а ) Ь, Ь ) а или а = Ь. Ясно, что если а ) Ь, Ь ) е, то а ) с. Упорядочение множества векторов в их лексикографическом убывании вполне аналогично упорядочению слов в словарях, что $36 элемкнты линвннОГО пРОГРАммиРОВАння ~гл. э и объясняет присутствие слова «лекснкографическийэ в приведенном определении. Нетрудно видеть, что в лемме 2 с помощью цепочки множеств 8, пз 8, ж Рл 8 Рл ... из о< приводится лексикографическое упорядочение векторов (с< (ю<ю, сп, ..., с«), <жую): сз) с< для всех «ну, рф8„а вектор с, с номером «из одноэлементного множества о"< представляет собой иексикографический минимум на множестве (с<, «н8<), т.
е. ср) с, для всех раэ Яю, р чью. Таким образом, согласно лемме 2 минимум конечного числа различных многочленов при всех достаточно малых положительных значениях аргумента достигается на том многочлене, вектор иэ коэффициентов которого является лексикографически наименьшим среди всех векторов из коэффициентов рассматриваемых многочленов. й 5.
Выбор начальной угловой точки Выше при описании симплекс-метода для канонической задачи э(и)=<с, и>- ш(; иевУ=(ижК": и>0, Аи=Ы (1) мы предполагали, что нам уже известна некоторая угловая точка множества У и что система Аи= Ь уже записана в виде (3.5), где г = ганя А. Воаникают вопросы: как узнать, не пусто ли множество (2) У=(и<нЕ": и>0, Аи= Ы, где А — матрица размера тХп, Ь вЂ” вектор иэ Е"? Если это множество непусто, то имеет ли оно хотя бы одну угловую точку и как найти ее? Как исключить иэ системы Аи = Ь линейно зависимые уравнения и привести ее к виду (3.5)? Ниже будут даны ответы на все эти вопросы.
Замечательно то, что для ответа на них может быть использован симплекс-метод. 1. Можем считать, что Ь~ О, так как если 5<<0 при некотором < (1((~ и), то соответствующее <-е уравнение (Аи)'= Ь' из (2) можно умножить на — 1. Наряду с основными переменными и=(и', ..., и") введем вспомогательные (искусственные) переменные ш=(и"+', ..., и"+") и в пространстве К"«переменных г =(и', ..., и', ..., й+") =(и, ш) рассмотрим следующую каноническую задачу линейного программирования: 1< 1г) = и"+'+...
+ и'+ — ш(; г ен Я = (г: г=~ 1 ен Е", г) О, Сг = Аи + ш = Ь~. Систему Сг =Аи+ и = Ь перепишем в покоординатной форме а„и'+... + а,„й + и"+' = Ь' 1 а„и' +... + а,„и" + и'+' = Ь', (4) а„„и'+...+а„„и'+ и"+'" = Ь'". ВЫБОР нАчАльнОЙ уГлОВОЙ точки При и"+'=...=и"+" = 0 система (4) очевидно равносильна системе Аи= Ь. Множество Я непусто: оно содержит, например, точку г,=(0, Ь)~0. Более того, нетрудно видеть, что точка х, является угловой точкой множества 2 с базисом иэ последних гп столбцов в„..., в матрицы С=(А, Е), где Š— единичная матрица размера гпХт (гп=гапдС>гапдА г). Важно также ваметить, что иа системы (4) легко выразить бааисные переменные ю=(и"+', ..., и"+") угловой точки г, через небааисные: щ = Ь вЂ” Аи = Ь вЂ” А,и' —...— А„и".
Таким образом, задача (3) уже записана в форме, удобной для применения симплекс-метода с начальной угловой точкой г,. Поскольку У,(г) ~ 0 при всех вша, то случай 1п1,)',(х) = — со в здесь невозможен. Поэтому, ваяв в качестве начальной точку х„ с помощью симплекс-метода, описанного в $3, за конечное число шагов найдем угловую точку гв = (и„, юг) множества Я, являющуюся решением задачи (3): и, = (и„..., Р,), юг = (гг ..., Бг+ ), 1п1Х,(в) = У,(г ) = У",+~ + ... + У",~ )О. г Имеются две возможности: или г,(гв))0, или г (ха) =О. Если У,(гв)) О, то и, Ф 0 и, оказывается, множество У, определяемое условиями (2), будет пустым.
В самом деле, если бы существовала хотя бы одна точка иш С, то точка з (и, 0) принадлежала бы множеству Я и, кроме того, мы имели бы 1(з) О, что противоречит тому, что г (г) ~)У(гв)>0 при всех вшЯ. Таким образом, при Хг(гв)) О множество С пусто и эадача (1) не имеет смысла. Пусть теперь )' (за) = г"„+ + ... + Уг~ = О. Тогда юг= = (гг+',..., Рг+ ) = О, вв = (Р„О). Кроме того, по построению г = (уг, 0) — угловая точка множества Я. Покажем, что тогда Р,— угловая точна множества (2). Прежде всего ясно, что из зв))0 следует и,)0, а из Сзв = Ь имеем АР,=Ь.
Это значит, что и, ш У. Рассмотрим представление и,=аи,+(1 — а)и„О<а<1, и,~в У, и,шС, (5) и покажем, что оно возможно лишь при и, = и, = и,. Точки г, =* =(и„О), г,-(и„О), очевидно, принадлежат Я. Тогда (5) можно переписать в виде гв = аг, + (1 — а) гг (О< а ( 1).
Нога — угловая точка множества Я. Позтому последнее равенство для яв возможно лишь при гв = гг = в,. Отсюда следует, что и, = и, и,. Таким образом, и, — угловая точка множества У. Тем самым деказана важная Теорема 1. Если множество (2) непусто, го оно имеет яв тя бы одну угловую точку. 138 ЭЛЕМЕНТЫ ЛННЕИНОГО ПРОГРАММИРОВАНИЯ [гл, з 2. Итак, исходная угловая точка Р, множества У найдена.
Для того чтобы, отправляясь от атой точки, можно было решать задачу (1) с помощью симплекс-метода, остается еще найти ганя А, указать базис точки и, и записать систему Аи = Ь в виде, аналогичном (3.5), т. е. выразить базисные переменные через небазисные. Как это сделать7 Обратимся к симплекс-таблице 7 точки зз, которая получена при решении задачи (3) симплекс- методом. Поскольку т = ганя С > ганя А, то в базис точки гз могут входить не только столбцы матрицы А, но и столбцы матрицы Е (кстати, при т > ганя А в базис обязательно войдут столбцы матрицы Е).
Не ограничивая общности можем считать, что базисом точки хз являются столбцы А„..., А„, е„..., е, матрицы С=* =(А, Е), соответствующие основным переменным и', ..., и' и вспомогательным переменным и"+', ..., и"+ ' — именно зта ситуация отражена в симплекс-таблице 7. Подчеркнем еще раз, что в+1 и+в из зз = (Р„О) следует, что Р, = ... = Р, = 0 — эти равенства также нашли отражение в столбце свободных членов табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
