Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 29
Текст из файла (страница 29)
Однако это обстоятельство не должно огорчать нас, так как, оказывается, при выполнении условий (13) рассматриваемая точка является решением задачи (1). В самом деле, для любой точки и ш У = (кк и Р- О, Аи = б) с учетом представления (4) н неравенств (13) писем У(и) =- (с, и) = ~~~~~с;и'+ ~~ с;и')(с, и) + 1=1 7=~+1 И / ч + ~, (с, В ~А,)и' =(с, и+ ~~Э~ В чьи' = (с, с) = Х(э). 1=г-(-1 з=т-~-1 Таким образом, У(и) У(э) при всех ишь, т.
е. и — решение задачи (1). Случай 11. Существует номер й (г+1<)г<п) такой, что Л~>0, та<0, ~=1, ..., г, т. е. В 'Аз<0. (14) Это значит, что в симплекс-таблице 1 в )с-м столбце, где нахо- дитсЯ Л~> О, нет ни одного положительного числа ун. В этом случае при всех й>0 точка и, определяемая формулой (10) (или (11)), будет иметь неотрицательные координаты и, следовательно, будет принадлежать множеству У. Тогда, как видно из (12), Ци) = э'(в) — Л,и" — — при и" — . Это значит, что ш1(с, и) = — со, т.
е. задача (1) не имеет решения. Случай П1. Существуют номера 7г, 1 (г+1 < й < п, 1<1< < г) такие, что (15) Л„>О, 7а>О. Это значит, что в к-и столбце симплекс-таблицы 1, где находится Л, > О, имеется хотя бы одно положительное число 7а. В этом случае множество индексов 1, = (О 1 < ~ < г, 7н> 0) непусто. Тогда для точки и, координаты которой определяются формулами (10), согласно (12) при любом и'>0 будем иметь У(и) =Х(и) — Л,и'<Х(э).
Остается лишь позаботиться о выполнении условия и > О. Как видно из формул (10) при уа < О, т. е. 1Ф 1ь будем иметь и* = и' — уаи' > и'> 0 при любом выборе и" >О. Если же уа>0, т. е. 1ш1„то при слишком больших значениях и', а именно, при и")шп1пи'!уы величина и'=о'— 'пт — 7ни' станет отрицательной хотя бы для одного номера точек, И8 злкмкнты липкиного пгогглммпговхнпя ~гл. з определяемых формулами (10), нужно й взять так, чтобы О~( (иь(ш1п и'!7;ю Пусть сить п1(п из~ум из~у ь (16) слт Поскольку множество 1, непусто и конечно, то хотя бы один такой номеР г сУществУет. ВеличинУ 7м, где номеРа й, г опРеделяются из (15), (16), называют ризрешающил~ злементом симплекс-таблицы 1.
ЗафиксиРУем один из РазРещающпх злементов ум и в фоР- мулах (10), (12) положим й = и,/7,„. Получим точку и = =(в', ..., и~") с координатами и' и в в 3 и и и' = и' — ум — = О, ю'-' = и'ьт — у,ет ~ —, ..., и~" = гх — у„ь —, ~п'+д=. 0 юь — т == 0 и:" = — и~ь+т = 0 и:и = 0 (17) М п с соответствующим значением функции У(си) = (с, и) = Х(и) — Л,и'/7м ( У(и) . (18) В силу формул (7), (10) и условия (16) ясно, что ю ~н П. Покажем, что и~ — угловая точка множества П с базисом А„...,А,„А,„...,А„,А„, (19) получающимся из базиса точки и заменой столбца А.
на А,. Учитывая, что и'=и~"~'=...=иР '=и~"+'=...=и" =О, условие Аю=Ъ можно зависать в виде А,ш'+...+А,,в* '+ +А,.„ю'+'+... +А„и~'+А,и'= Ъ, Согласяо теореме 2 1 остается показать, что система векторов (19) линейно независима. Пусть для некоторых чисел ссо ..., сс, о а,+о ..., сс„сс, оказалось, что сс,А, +...
+ а,,А,, + сс,+,А,~, +... + а,А„+ а,А, = О. (20) Поскольку Аа = ВВ 'Аь = ~ А; (В "А„)' = ~~'„угаАь то из з=1 з=т (20) следует т т а;Ас+ ссь ~, уиА; = ~ (а;+ ииум)Ас+ азу,ьА, = О. з=1дфз с=с 1=к1Фю Но система Ао ..., А„..., А, является базисом точки и и, следовательно, линейно независима. Тогда последнее равенство симплекс-мвтод % з» »»з возможно лишь пРи а»+а»7»»=0 (»=1, ..., г, »Фз, а»7.»=0). Но 7„) О, как разрешающий элемент, поэтому а,=О. А тогда все остальные а,=О (»=1, ..., г, »Фз).
Таким образом, равенство (20) возможно лишь при а, ... = а., = а,+, =... ... =а,=с»,=0, т. е. система (19) линейно независима. Тем самым показано, что ив — угловая точка множества У, причем система (19) является ее базисом, а и', ..., иб ', и'+', ..., и', и'— ве базисными переменными. Пользуясь соотношениями (7), нетрудно выразить новые базисные переменные и', ..., иб ', и'+', ..., й, и" через остальные небазпсные переменные. Для этого из з-го уравнения системы (7) нужно выразить переменную и'.
ид „в ит вз Гбз ~ уж (21) 'ЮУ (здесь и ниже в'» означает, что суммирование ведется по всем у=г+1, ..., п, исключая 1=1) и затем подставить ее во все остальные уравнения этой системы. С учетом равенств (17) получим и» = ⻠— ~~'~ уцив = в т+» Чвт = ⻠— „7, уцив — р»д1— в'-т-»-» 1б бд » твд в т.»1»д лз 'чвт» ты ив ~ .70 7,. ив (22) т=т.»-» т »»бв У (и) = Х(в) — т„Л.и» вЂ” Лд — — — и' —,т — ' и» Л~ ..2 ~, т в'=т-»- » = Х (ит) — — — и' — г Л вЂ” Лд — и»; (23) здесь мы учли равенство (18).
Таким образом, базисные переменные угловой точки ит и значение функцип 1(и) выражаются через небазисные переменные этой точки по следующим для всех» = 1, ..., з — 1, г+ 1, ..., г. Аналогично, подставляя выражение (21) для и' в (8), функцию У(и) также можно выразить через новые небазпсные переменные: 120 элементы лннейнОГО пРОГРЛ11миРОВАнпя !Гл. 3 формулам: б б б-~ 1 Д вЂ” 1 ид=ибд — 7 и' — у балади+ —... — у бд и 1+1 ' бб — у,д+,и ' —...— у„,и, 1 б б ' бЧ1 ' Д вЂ” 1 и = иб — 71,и — 71 „+,и —... — у'; д,и 1+1 ' бб — у;деди — ...
— 71 и, Д+1 ' бб уб — 1,1+1и ° ° ° Уб — б,пи бб1 б В б б+1 б Д вЂ” 1 и — у...и — уб+1 „+,и — ... — у,+1 „,и ДЕ1 б бб — бб-~-1,дт1и — ° ° ° — Убе1,бби й '= и б+1 Л;=Л; — Лд — ", 7'=г+1, ...,й — 1, й+1, ...,п. (26) Убд Табл. 2 представляет собой спмплекс-табл1щу новой угловой точки иб. Таким образом, один шаг симплекс-метода, заключающийся в переходе от одной угловой точки Р множества дб' к другой угловой точке иб, описан.
Этот шаг формально можно истолковать как переход от одной симплекс-таблицы 1 к следующей Ф б Д-1 и = иб — у„,и — 7„,,+ди —... — у„д,и 1+1 ' бб — у„д+ди — ... — у„„и, Д Д б б «+1 Д-д и = ш — Уд,и — уд „+ди — ... — У, д,и 1+1 в — Уд д+,и — .. — удаи, Х(и) = У(и) — Л,и' — Л„,и" ' —... — Лд,ид Д+1 бб — Л„„.,и — ... — Л„и, где ибб, ..., иг' ', иб'дб, ..., иб', ибд и б'(иб) определяются формулами (17), (18), а уп, Л; получаются пз (21) — (23) приравпиванием козффицпентоз прн соответствующих непзвестных: у;,= — —, 1=1, ...,з — 1,з+1, ...,г, уд,= —, (24) "б'11 тм б 71;=711 — — у„, 1=1, ...,г — 1, я+1, ...,г, 711= —, (2о) у =- г + 1, ..., й — 1, й + 1, ..., и; Лд Л = —— б Убд симплвкс-мктод з з~ г21 симплекс-таблице 2 по формулам (17), (18), (24) — (26), в которых разрешающий элемент 7„определяется условиями (15), (16).
Эти формулы перехода были получены в предположении, что базисные переменные угловой точки в имеют номера 1, ..., г. Нетрудно видеть, что если базисные переменные точки в имеют, скажем, номера Хо ..., 1„(1 ~ у, (... ( у, ( п), то можно выписать формулы иэ' = э" — ~ рдп", 1= 1, ..., г, Х(и) = Х(э) — ~ Льиа, акт, ьл гт выражающие базисные переменные и функцию Х(и) через небазиспые переменные и аналогичные формулам (5) — (9). Здесь Х.=(/о ..., Х„), 7и=(В 'А,)', ~=1, ..., г, йФХ,, В=(Аг ...А~), и"=(В 'Ь)', г=1,...,г; Ла= ~~э~ суч — сю йфХ„; Ла=О, гелХ„; табл. 3 представляет собой спмплекс-таблицу точки и.
Как и выше, здесь нужно рассмотреть три случая. Случай 1. (13') Л,<0, йФХ„. Сл у чай 11. Существует номер й ФХ, такой, что Л, > О, В 'А„( О. (14') Случай 111. Существуют номера йФХ., ДшХ, такие, что Л„>0, (В 'А„)'=7„>0. (15') Как и выше, нетрудно убедиться, что в случае 1 точка и является решением задачи (1), в случае 11 — 1п1(с, и) = — оо и задача (1) не имеет решения, а в случае 1П можно выбрать разрешающий элемент 7,~ из условий Л„>О, ш1п в"/ум = г"/у„, Х„= (О Х; ел Хю уы> 0), (16') гетто аналогичных условиям (15), (16), и затем осуществить переход к следующеп угловой точке ю по формулам, аналогичным формулам (17), (18), (24) — (26). 2. Итак, описаны правила перехода от одной угловой точки и множества ХХ к другой угловой точке и, в которой Х(ю) ~ Х(и). Возникает вопрос, когда Х(ю)=Х(и) и когда Х(ю)(Х(в)? Учитывая, что поскольку по определению номеров г и Й согласно (15), (16) Л~>0, 7.~>0, а э'>О из-за эш 0', то из соотношений (18) нетрудно усмотреть, что Х(ю)=Х(э) тогда и только 122 ЭЛЕ11ЕНТВ1 ЛИНЕИНОГО ПРОГРАМЫИРОВАНИЯ !ГЛ.
3 ! Э . В Э о ° о ° о о о ° о ° . о о о ° ° о ° о о 1!1п О ' О: О О о о о о о ?- ? ' "- ' ?- ' ?- п1 1 1п о о: о о о ° ' и 3 Юй о? О Ю Ф 2 ЗИ пд С й аИ ~0 ? и п ?- ?- ?- '?и ~ 1 ? ?- ~ ?" ? О , "О О ! О О О: О О: ' О О о ! о: о о о ?? ?и ?? о и д Юп ? П В й и?, симплккс-мктод »23 тогда, когда о*=О, т. е. угловая точка о вырожденная. Таким образом, среди канонических задач имеет смысл выделять задачи вырожденные и невырожденные. О п р е д е л е н и е 1. Задача (1) называется невырожденной, если все угловые точки множества УУ невырожденные.
Если хотя бы одна угловая точка множества УУ вырожденная, то задачу (1) называют вырожденной. В том случае, когда задача (1) невыролгденная, все базисные координаты угловой точки о будут положительны. В частности, тогда о') О п согласно (18) У(и ) С У(о). Далее, пз формул (17) видно, что следующая угловая точка и» уже имеет п — г нулевых координат: ю' = и'+' =... = и~' ' = и»"+' =... = и»" = О. Поэтому в невырожденной задаче все остальные г координат точки и», являющиеся базисными, должны быль положительными. А тогда для всех 1»нУ, (1тьз) из формул (17) будем иметь и»»= =7»»(о'/7»» — о'/7„)) О, о»У7»» о'/7,», так что минимум в левой части (!6) достигается на единственном номере з»нУ».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
