Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 20
Текст из файла (страница 20)
3, ( допустимый элемент для любого 1 > О, при этом (с,х( )) = (с,х — 1(хз,О) +Ге ) = (с,х) — Г(с х') +1(с е ) = =(сх) — га +Ге =(с ) — 1( ) = (с х) — 1сьу — +ос при Г +ос с) Предположим, что не выполнены условия пп. а) и Ь) Тогда лля некого го та ) и ) теоремы. араго зь такого, что гп+! < за < и, выполнено условие ОЗЬ < 0 и величина ГО,: = пВзп ) — ~ х,. > 0» = — ' > О.
х! згз ХО)У) Возьмем х'! = х — Ц (хзь, О) + Г е., Д ;,(, ) + „е;. Докажем, что вектор х' является новой крайней точкой в задаче (.Рь). Покажем вначале, что он является допустимым вектором. Как и а пункте Ь) вы, А ' = водим, что х = Ь.
Имеем Таким образом, х) > О, и значит, вектор х является допустимым ) в невырожденной задаче (Рь). По построению у вектора х' по сравнению то обратились в н с вектором х добавилась одна положительная г' -я координа ись в ноль. Поскольку по предложению 2а) у допустимой точки число положительных координат не ме нее пз, то в ноль может обратиться только одна координата (зто *';,-я координата обратилась в ноль). Значит, у вектора х' имеется ровно зп положительных координат на местах 1,..., Оь — 1, за+1,..., пз, уь.
Следовательно, по предложению 2Ь) — крайняя точка. (Отметим, что в невырожденной задаче число положительных компонент у крайней точки может уменьшаться.) Выписанные формулы означают, что в новой симплексной таблице столбец х' вычисляется согласно указанному методу построения симплексной таблицы. Покажем, что и остальные столбцы х" в новой симплексной таблице строятся по этому же способу.
Для этого вычислим координаты х,'1 разложения столбцов а1, з' = 1,...,и, матрицы А по базису а',..., а" ', азь, а" » !,..., а В старом базисе мы имели следующие разложения: В частности при 2 = яь ау' = Е а'хауз + а" х)оО. )=! )ьл) ч Поскольку х;„; Ф О, то выразим а ' из последнего уравнения О) 1О ч ' хзй а — +— ) х- „хь; ) ЗНО и подставим в соотношение (1).
Получим разложения по базису а,... ! а" ан а"' а ,/ хь хб,)З а ~х, — — +ай —, з 1,...,п. хий / хз)1О х, =х; —, зФзть з=1,...,гп, ~хзй=О, ОФзо х)О1*)1О ) х)О1О 110 Гла лава 2. Линейное программировавие $4. Методы нахождения начальной крайней точки 4.1. Пе хо ре д к решению двойственной эддвчн Рассмотрим мета тем перехода к двойстве й д решения задач линейного п рограммирования пузадачи. При этом стро ственной задаче и решения пол че ученной двойственной шение исходной задачи.
строка последней симплексс-таблицы даст нам ре- П усть нам дана следующая з а задача линейного программирования: (6~у) ппп; А'у > с у > О Двойственной для нее я вляется задача в нормальной ф форме (Р") Сведем э з ту апачу к эквивалентной задаче в канани еотрицательных (искусственных) пе мен матрицы 1: (с,*) шах; А <Ь, *>0 (ся)- шах; Аэ+1У=Ь, я>0, У>0 е— (с,е)- гпах; АУ=Ь У> У = Ь, У > О (с = (с О), У = (х, ), А = Аг!.
— —,У, = АГ!. (Р) (Ь,у) — ~ш!и; Ау>с е» 4' с То есть у является решением исходной задачи (Р). П Я вЂ” Я и АХ Х=А ~1= ния ь = А сь Х = Аь А еь Х = А 'А„ „1 = Аь получим, что вектор у = сьАь ' = сьХ = л = У вЂ” с = гз Таким образом, часть щей под разложениями вект ь строки Л последней симплекс-та блицы, лежа- решение исходной задачи (Р). векторов искусственных пе ременных, дает нам ЗалачУ (Р) с ве ктором Ь > 0 можно решить симпл а качестве исходной край й шить симплекс-методом, взяв Эта точка будет крайней по П единичной матрицы 1, соот по редложению 1 п.
3.2, носк оскольку столбцы этой точки, линейно независимы. , соответствующие положит ожительным координатам П сть ве Тогда соответственно х я ением задачи (Р) (У Е АгйР). но х является решением задачи (Р") (х Е А А по теореме п.3.3 вектор: = с А ' д ственной к задаче в кано й фо вой у; = сь ь является решением канонической форме Р: задачи, 4 4. Методы иахожлеииа начальной крайней точки 111 Пример. Решить задачу линейного программирования путем перехода к двойственной задаче.
Пусть необходимо решить следующую задачу: 4у~ + 2уз 9У,+ у, >15, Зу, + 4„, > 27, „, +5У,>20. 15я, + 27яз + 20хз — пзах; ал > О, ь ж 1, 2, 3, 9х1+ Зяз + яз < 4, я ~ + 4хз + 5хз < 2. Сведем эту задачу к задаче в канонической форме путем добавления неотрицательных (искусственных) переменных я4, и аз и заменяя неравенства равенствами: 15х, +27хз+20яз- шах; яг > О, ь =1,...,5, 9к, +Зхгч- аз +аь — — 4, х~ + 4хз + 5хь + лз = 2. В выписанной задаче линейного программирования в канонической форме в качестве первоначальной крайней точки возьмем точку я = (0,0,0,4, 2).
Эта точка будет крайней по Предложению 1 и. 3.2, поскольку столбцы единичной матрицы, соответствующие положительным координатам этой точки, линейно независимы. Тогда базисными векторами будут векторы а =(1,0), а =(0,1). Составим первую симплексную таблицу лля задачи в канонической форме (Р): Решение.
Двойственной для данной задачи линейного программирования будет следующая задача в нормальной форме (выведите это самостоятельно): 11г Глава 2. Линейное программироваиие (с,х) гпах; Ах=Ь, х >О. В первой симплексной таблице разрешающий столбец а, разрешающая строка а, разрешающий элемент симплексной таблицы 4. Заменяем в базисе вектор искусственных переменных а на вектор аз и для нового базиса строим вторую симплексную таблицу: Во второй симплексной таблице разрешающий столбец а', разрешающая строка а, разрешающий элемент симплексной таблицы 4 зз 4 ' Заменяем в базисе вектор искусственных переменных а на вектор а' и для нового базиса строим третью симплексную таблицу: Вектор зз > О, поэтому точка х = (з, Ц,О,О,О) является решением двойственной задачи с добавленными искусственными переменными (Р), а вектор х = ( —, з,О) является решением задачи (Р") и Бр — — Яр- = 16.
В последней симплекс-таблице под разложениями векторов искусственных переменных стоят числа 1, 6, являющиеся значениями решения исходной задачи (Р), т. е. вектор у = (1, 6) является решением задачи (Р) и Яр —— 16. б 4. Методы иахождеиия вачальиой крайней точки 4.2. Метод нскусстненного бйзнсй Метод добавления искусственных переменных используется лля отыскания начальной крайней точки в залаче линейного программирования в канонической форме Не ограничивая общности, можем считать, что все координаты вектора Ь неотрицательны. Если это не так, например, 6з < О, то умножим обе части 1-го уравнения на — 1. Поэтому палее считаем, что 6 > 0 Рассмотрим вспомогательную задачу, добавляя искусственные переменные х =- (х„еп...,х„э ) и единичную матрицу л, — х„, шах; Ах+эх.= Ь, х > О, У > О.
с=~ Поскольку значение задачи Яр < 0 и множество допустимых элементов 13(Р) Ф. И (х: = (0,...,0,6н...,Ь ) Е 22(Р)), то значение задачи конечно (!зр! < +со). По теореме существования п. З.! решение в задаче (Р) существует. Причем, если в исхолной заааче (Рх) множество допустимых элементов непусто (!!(Рь) ~ И), то значение залачи Яр — — О, а решениелз задачи (Р) будет крайняя точка, у которой все искусственные переменные равны нулю.
Задачу (Р) можно решить симплекс- методом, взяв в качестве исходной крайней точки точку х. Зта точка будет крайней по Предложению 1 и.3.2, поскольку столбцы единичной матрицы 2, соответствующие базисным координатам точки х, линейно независимы. При решении задачи (Р) симплекс-методом могут возникнуть три исхода: 1) Не все искусственные переменные равны нулю. Зто означает, что исходная задача (Рь) не имеет допустимых элементов. Действительно, если не все искусственные переменные равны нулю, то Яр < О. Предположим, что исходная задача (Ра) имеет допустимые элементы, например, х~. Но тогда Яр < 0 = ((О, — 1),(х',0)) — противоречие. Значит, наше прелположение, что исходная задача (Рэ) имеет допустимые элементы.
неверно. 2) Все искусственные переменные равны нулю и среди базисных векторов нет векторов, соответствуюзиих искусственным переменным. Зто означает, что решением в задаче (Р) будет х = (х,0) — крайняя точка множества 22(Р). Точка х будет крайней точкой множества 22(Рь) по Предложению 1, поскольку столбцы матрицы А, соответствующие базисным координатам, линейно независимы. 114 Глава 2. Линейное ярограммироваиие х~+2хз+ хз +хл =10 2х, + хз + 5хз — — 20, х~ + 2хз + Зхз = 15. х, +2х,+ хз +хл = 10, 2х~+ хз +5хз +хз =20, х, + 2хз + Зхз + хл = 15.
Далее, взяв в качестве первоначальной крайней точки точку х, можем приступать ко второму этапу — решению задачи (Рл) по симплекс-методу с найденной крайней точкой. Таким образом, мы имеем двуэтапный метод решения задачи (Рл). 3) Все искусственные переменные ровны нулю и среди базисных векторов есть вектора, соответствуюигие искусственным переменным. В этом случае надо исключить из числа базисных вектора, соответствующие искусственным переменным. Пусть, например, в последней таблице имеется строка с искусственной переменной х„вь. Будем считать эту строку разрешающей.
В качестве разрешающего столбца возьмем столбец аз', зл < п, такой, что х„эг„д ~ О. Столбец 6 новой симплексной таблицы при этом не изменится (по правилу прямоугольника х'; = х; — ' ' = х,, хл ыкн так как х„в;, = 0), только вместо переменной х„ч будет стоять перелзенная хз. Значение функционала (с,х) также не изменится. Этот процесс закончится удалением всех базисных векторов, соответствующих искусственным переменным, с заменой их на неискусственные, или окажется, что х„„ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
