Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 20
Текст из файла (страница 20)
строка последней симплексс-таблицы даст нам ре- П усть нам дана следующая з а задача линейного программирования: (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), только вместо переменной х„ч будет стоять перелзенная хз. Значение функционала (с,х) также не изменится. Этот процесс закончится удалением всех базисных векторов, соответствующих искусственным переменным, с заменой их на неискусственные, или окажется, что х„„ч. = О, 3 = 1,...,и. Так как хзз — з-я координата разложения вектора аз по базисному вектору а', то тогда все векторы аз, з = 1,...,п, включая вектор Ь, можно разложить по базисным без вектора а . Значит, Зв-я строка исходной системы уравнений является „Л+Во линеЙно зависимой от остальных строк и на егором этапе можем просто вычеркнуть из симплексной таблицы ле-ю строку, содержащую эту искусственную переменную, н начать второй этап с меньшим числом базисных векторов.
Таким образом, двуэтапный симплекс-метод позволяет для любой задачи линейного программирования в канонической форме: 1) обнаружить, что исходная задача не имеет допустимых элементов, или 2) найти первоначальную крайнюю точку в задаче (Р) и решить задачу по симплекс-методу, или 3) исключить линейно зависимые равенства и решить задачу по симплекс-методу с найденной крайней точкой, имеюцгей менее га положительных элементов. Замечание. Вместо такого двузтапнога решения задачи (Рл) можно решать следующую задачу (ее принято называть М-залачей) (с(х х)) — гпах; Ах+2х=Ь, х>0, х>0, где с = (с, — М,..., -М) Е К"""', М вЂ” полозкительное число.
Нетрудно показать, что при любом достаточно большом М первые п координат полученного решения определяют решение в (Рл), а искусственные переменные равны нулю. 04. Методы нахождения начальной крайней точки 115 4.3. Примеры /Зример 1. Решить методом искусственного базиса задачу: х1+ 2хз+ Зхз — хл — гааз; х; ) О, з = 1,2,3,4, Рассмотрим вспомогательную задачу, добавляя искусственные переменные хз,хл. — хз — хл- шах; хг)0, з=1,...,6, Исходная крайняя точка х = (0,0,0,10,20,15).
Базисные векторы а = (1, О, 0), аз = (О, 1, 0), а = (О, О, 1). Составим первую снмплексную таблицу для вспомогательной задачи: Из таблицы видно, что разрешающим столбцом является столбец а, з разрешающая строка аз. Заменяем в базисе вектор а на вектор а и для 5 з нового базиса строим вторую симплексную таблицу: !16 Глава 2. Линейное программирование 5=1,2,3, х1 — 2хг+ тз щах; х; > О, х, + хг +хз=5, 2х1+ хг — — 3, -2х1+ 2хг = 4. 5=1,...,5, -х4 — хз — гпах; х; > О, х~ + хг + хз =5, 2х~+ хг +х4 =3, — 2х~ + 2хг +аз=4. Из таблицы видно, что разрешающим столбцом является столбец а', разрешающая строка а .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
