Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 37
Текст из файла (страница 37)
Легко понять, посмотрев на формулы (6),(9) и (29), что при решении задачи максимизации (50) нас прежде всего будут интересо- :,'„)„4' вать величины Ь„< О, и мы естественна придем к рассмотрению следующих трех случаев, аналогичных случаям (32) — (34). Сл уч а й 1, В нижней строке симплекс-таблицы 3 все Л„..., Ь неотрицательны. Исходная угловая точка и является решением задачй (оО).
1 Ф.П Васильаа 5 3. СИМПЛЕКС-МЕТОД. АНТИЦИКЛИН [ЗО Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ [З[ ш' " 2 Упражнении й и С л у ч а й 1!. В нижней строке симплекс-таблицы 3 найдется величина «55 <О, 1 < й < у), и находящийся над ней столбец у„неположителен, Тогда 1* = зцр(с, х) = +оо, задача (50) не имеет решения. иех Случай 111. В нижней строке симплекс-таблицы 3 имеются величины 435 < О, 1 < й < и, причем в каждом столбце над величиной «35 < 0 найдется хотя бь) одно число у. > О, Тогда фиксируем один из таких номеров ю с «'.ьь < 0 и выбираем разрешающий элемент "«,„по правилу (3 ) ы 5 или, точнее, (48), а затем по формулам (Зб) совершаем переход от угловой точки е с базисом В к точке ш, которая согласно замечанию 1 также будет угловой точкой множества Х с базисом В, имеющим вид (37), причем 1(ш) > ?(е).
Один шаг симплекс-метода для задачи (50) описан. лак и выше, можем считать, что исходная симплекс-таблица В(е, В) >- О. Тогда б дут справедливы следующие лексикографические неравенства, аналогич— г а ные неравенствам (49)! Я(п), В) >-О, В(е, В) -< Я(ш, В). Отсюда следует, что симплекс-процесс для задачи (50) будет конечным и закончится реализацией одного из случаев 1 или 11.
Все высказанные здесь утверждения, касающиеся задачи (50), доказываются совеошенно также, как и аналогичные утверждения, касающиеся задачи (1), [)редлагаем читателю убедиться в этом самостоятельно. Остается напомнить, что в течение всего этого параграфа задача (1) (а также задача (50)) рассматривалась в предположении, что тп = г = гапнА < < уь, и нам известна хотя бы одна угловая точка множества Х. В следующем параграфе покажем, как избавиться от этих ограничений. 1. С помощью симплекс-метода решить следующие канонические задачи: а х — х х х х х ' 1 2 5 1 2 '3 4-хб— а) 1(х) = х!+ хг+ ха+ ха+ хб-«!п1; х=(х, х,, х ) > О, х + х + 2х +х — 2х = 2, 1 2 3 4 5 б) 1(х) = х' -)-Зхг+ 2хз+ х4 — Зхб-«)п1; х = (х',..., хб) ) О, х + 2х — 42х — х = О, 2 4 5 о, в) 1(х)=х! — 2хг+хз — х4 — «)п1; х=(х',...,хз)>0, х — 2х +х =1, х +х — 2х =1; г) у(х)=х .) хг) хэ ) х41 хб-«!п( х=(х,..., хб) >О х)) 2хг — х4 ) 2хб=) х2 ) хз+ +2х — х =О, -х — 2х +х +х =!.
2. Проверить, что точка ио является угловой, найти ее базис, приведенную систему и, взяв естес начальной точки, с помощью симплекс. метода решить следующие задачи: в) 1(х)=х'+2хгчх~+х' — «)ппзцр]; х=(х),..., х ) ) О, х +2х -х +2х -х +2х =О, х)-4хг ~2хз+2х4-4хб=),2х)-2хг+хз+4хз.~х5-2хб=З; ио-(1,000,1,0); б)1(х) х1)х2+хз+2х413 5!2 б )л(1 «]; =(,...,х)>0 ) +4 4!2 б в) 1(х)= х'-! 2хг+Зхз ) х4+хб-«)п([з~у]) х=(х',..., х ) >О, х)) 2хг+4хз — х'.) х5= 1, *' — *'-2 '4-*4+ я'= 1, — '+*'-бх +*'+*'= 1; и,=(1, ),О, ),О). 3.
Найти начальную угловую точку ио, ее базис, приведенную систему и решить следующие задачи: ! 4 ! 2 „3 4 а) 1(х)=-х!+Зх245хз+х4-«)п([зцр]1 х=(х,...,х )>О, х +4х +4х +х = з б) 1(х)=хг — ~3+*4 )п1[зцр]! х=(х',...,х )>О, +х — =1, + +2х =3; 3 4 в~ 1(х) =4х! — хг — Зхз — 1Охб — «)пЦзцр]) х =(х,..., х ) )но, х + х — х +х =О, 14х + + х + 1Охз — 1Охэ = 11. 4.
С помощью приемов, описанных в $1, записать задачи линейного программирования в каноническом виде и пошить их с помощью симплекс-метода; а~ 1(х) = — х' + 4х — 5хз — «)п! [зар]! х = (х), хг, хз) > О, 2х! 4 х + хз = 4 [(4 ) 4], и'— в х — х <2 [(2;=2~ б) 1(х) = х + х -) х -«!п1 [зцр]; х = (х, х, х ) > О, — ! < х -)- х 4 х < 1, — х .1 х + х < 1, хг+ 3 <1 в) 1(х)=х) )х 4-х +х4-«)и![зцр]! х=(х,..., хб) >О, х — хг >О, х +х~-хзгхз — хб >1. 5. При каких значениях параметра а задача 1(х) = х ~+2х~+Зх344х4 — «)ц( [зцр]; х =, (х),...
..., х4) ) О, х'+ хг+ хз+ ох4 < 1, [> 1; = 1] имеет решение? Не имеет решения? Единственнре решение? 6. С помощью симплекс-метода с антициклином (48) решить задачу [216]; 1(х)=--х'+150хг 50хэ+бх4-«!п1; х (х!«ху))0« — х — бох — — х +9х + х 1 1 2 1 3 4 5 4 25 =О 1 ! г ! з пах — 90х — 5-х +Зх +х =0 б 50 х з +х =1, взяв в качестве начальной угловую точку и =(0,0,0,0,0,0„1) с базисам В =(АшАш А ), Показать, что если разрешающий элемент т,ь выбирать по правилу (34), (35) так, что Ь— наименьший из номеров, для которых Аь — — шах А«, з — наименьший из номеров, удов- 1<1<2 летворяющих условию (35), то придем к циклическому перебору базисов точки ио по схеме: (Аб«Аб, Ау)-«(А), Аб, Ау) -«(А), Аг, Ау) — «(Аз, Аг, Ау) — «(Аз, А4, Ау) — «(«(5, А4, Ау) — « -«(Аш Аб, Ау)-'...
7. Пусть и — угловая точка множества Х = (х > 0: Ах = Ь) с базисом В = (А,, А. ), 1«1 где А — матрица размера тп х и, т = гапкА = «и < п. Пусть некоторая система уравнений )41) =хг'+ 2 )«цх", 1=1,...,т; Ци)=(У),...,У'„) (5!) 54«! ) равносильна системе Ах = Ь. Доказать, что система (51) является приведенной системой для точки и с базисом В. Указан не: сначала покажите, что системы (51) и (28) равносильны, затем подставьте в (51) следующие решения системы (28); хо — — и; хр — -(х),..., хр ), р 4 Ци), где х«' = еу — у), 1 = 1,..., т, хр = 1, ху = О, у «Ь Ци), уф р, и убедитесь, что Ру« = и«, Рь — — ум, Ь 71(и), 4' =1,.«., т. В. Пусть задача (! ) имеет своим решением угловую точку е с симплекс-таблицей 3, Можно ли утверждать, что тогда «51 (0 для всех у' = 1, 2,, и? (см, табл.
3, 4). 9. Для тою, чтобы задача (1) имела своим решением угловую точку и, необходимо и до- статочно, чтобы для какого-либо базиса В точки и соответствующая симплекс.таблица удов- летворяла условиям (32). Доказать. 10. Пусть угловая точка и с базисом В = (А«, „ А .) является решением задачи (1) и пусть ее симплекс-таблица (см. табл, 3) удовлетворяет условиям (32).
Пусть при некотором Ь «7 1(и) = (21,..., у„) величина Аь — — 0 и в столбце хь имеется величина уы > О. Пусть раз- решающий элемент т,ь определен по правилам (35) или (48), и получена угловая точка «а с координатами (36) й с базисом (37) (см. замечание 2).
Доказать, что тогда и — решение задачи (1). Можно ли таким способом получить все угловые точки множества Х, являющиеся решением задачи (1)? 11. Пусть и — угловая точка множества Х =(х > 0: Ах = Ь), В = (А,..., А ) — ее базис, А — матрица размера т х и, т = гзпкА ( и) пусть в матрице Г=( уо, т),, «„) (см. обозна- чения (27)) один из столбцов у < О, Ь ф 1(и) = [у'„..., у'„). Доказать, что тогда множест- ва Х неограничено, и найдется такой вектор с = (с),..., с„), для которого )п1 (с, х) = -со.
иеХ У к а з а н и е: взять с« = О, 1 е 1(и), сь — — — 1, остальные с) — произвольные числа, составить симплекс-таблицу точки и для задачи (1) с выбранным с. Можно ли утверждать обратное; если множество Х неограничено, то в матрице Г найдется столбец уь (О, й !( 1(и)? 1ЗЗ $ 4. ПОИСК НАЧАЛЬНОЙ УГЛОВОЙ ТОЧКИ Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 132 у 4. Поиск начальной угловой точки «! (2):«л тх ' «ь 6«= и' +апх' +...+аех' +...+амх", Ь = и +а,х'+...+а,х'+...+а „х".
При и' =... = и =0 система (3) превращается в систему Ах = Ь, Множество 1' непусто: оно содержит, например, точку л =(Ь,О) > О. Более того, с помощью теоремы 2.1 легко убедиться, что точка ха является угловой точкой множества У с базисом (е„..., е„) = 1 . Система (3) является приведенной системой этой точки, гапеС = т. А(ля целевой функции приведенная форма равна д(у) = (1„, Ь вЂ” Ах) = д(х,) — (АТ1, х), где А" — транспонированная матрица А. Теперь симплекс-таблица точки ха составляется просто (см. табл.
19): в столбце Б — базисные координаты и',...,и , в столбце Ъ' — Та = Ь, в столбцах и',...,и вспомогательных переменных у,'= е„..., 1' = е„, в столбцах х',..., х" основных переменных 1. Будем рассматривать каноническую задачу ,!'(х) =(с«х) — «!п1, х Е Х =(х=(х!«...«х")) 0«Ах= Ь), '(1) где А — матрица размера т х и, с Е Е", Ь е Е", в самом общем виде, отказавшись от ограничительных требований гапяА = т < и, принятых в предыдущем параграфе. Можем считать, что А фО, так как при А =0 либо Х = Е" = (х > О) (случай Ь = 0), либо Х = 0 (Ь ~ 0), и задача (1) становится малосодержательной.
Нас будут интересовать вопросы, как узнать, не пусто ли множество Х, и если оно непусто, то имеет ли оно хотя бы одну угловую точку? Как найти эту угловую точку, ее базис, ее симплекс-таблицу? Йиже будут даны ответы на все зти вопросы. Здесь замечательно то, что для ответа на них может быть использован изложенный выше симплекс-метод с антициклином.
Оказывается, по задаче (1) легко можно составить новую вспомогательную каноническую задачу, к которой очень удобно применять симплекс-метод,и в зависимости от того, чем закончится симплекс-процесс для вспомогательной задачи, можно будет сказать, пусто или непусто множество Х, найти ее угловую точку.
Этот метод поиска начальной угловой точки в литературе часто называют методом искусственного базиса. Можем считать, что в (1) вектор Ь > О, так как если Ь! < 0 прн некотором а', 1 < а < т, то соответствующее аче уравнение (Ах)' = Ь' системы Ах = Ь можно умножить на (-1), Наряду с основными переменными х =(х',..., х") введем вспомогательные (искусственные) переменные и = (и',..., и") и в пространстве Е"+" переменных у = (и, х) = (и',... ... и х' ... х") рассмотрим следующую каноническую задачу линейного «« ' ' '« программирования; д(у) = и' + и~+... + и =< 1, и > — «!и1; у е У, 'г" =(у= !и, х] ЕЕ"+: у >О, Су= и+ Ах = 6), где 1 = (1,..., 1) Е Е, С= (1 „А), 1„— единичная матрица размера х т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
