1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 11
Текст из файла (страница 11)
Так как x * = - z00 = 1 > 0 , то исходная задача неразрешима из-за несовместности ограничений.55Пример 7. Решить задачу- x1 - 4 x2 - x3 ® minx1 + x2 + x3 = 2 ,- 2 x1 + x2 - x3 = -1 ,3 x1 + 2 x3 = 3 ,x j ³ 0, j = 1,2,3 .Решение. Будем искать начальное базисное допустимое решение методомискусственного базиса. Для этого умножим второе ограничение-равенство на- 1 и добавим искусственные переменные x4 , x5 и x6 . Получим вспомогательную задачуx4 + x5 + x6 ® minx1 + x2 + x3 + x4 = 2 ,2 x1 - x2 + x3 - x5 = 1 ,3 x1 + 2 x3 + x6 = 3 ,x j ³ 0, j = 1, K,6 .с базисным допустимым решением x = (0,0,0,2,1,3)T . Исключим базисные переменные x4 , x5 и x6 из целевой функции этой задачи:x = ( 2 - x1 - x2 - x3 ) + (1 - 2 x1 + x2 - x3 ) + (3 - 3x1 - 2 x3 ) = 6 - 6 x1 - 4 x3 .Данное равенство запишем в принятом виде- x - 6 x1 - 4 x3 = -6 .Получаем исходную симплекс-таблицу, которая не является двойственно допустимой:-xx4x5x6-6213x1-6123x201-10x3-4112x40100x50010x60001Выбираем ведущий столбец s .
Пусть s = 3 . Выбираем ведущую строку. Получаем r = 2 и, следовательно, ведущий элемент z23 = 1 . Переходим к новому базису, которому соответствует следующая симплекс-таблица:-xx4x3x6-2111x12-12-1x2-42-1256x30010x40100x54-11-2x60001Полученная таблица все еще не двойственно допустима. Выбираем в качестве ведущего элемента z32 . Выполнив элементарные преобразования, получим таблицу-xx4x3x2x1003/21/2003/2-1/2x20001x30010x 4 x50011000-1x62-11/21/2Данная таблица прямо и двойственно допустима. Получено оптимальное решение вспомогательной задачи.
При этом x * = - z00 = 0 . Поэтому на шаге 2в таблице произойдет удаление нулевой строки и трех последних столбцов,соответствующих искусственным переменным:03/21/2x4x3x2x103/2-1/2x2001x3010В числе базисных осталась искусственная переменная x4 , при этом встроке, соответствующей ей, имеются только нулевые элементы. Значит, этустроку можно удалить. Исходная матрица имеет ранг равный 2 . Действительно, если вернуться к предпоследней симплекс-таблице и переписатьстроку, соответствующую базисной переменной x4 , в виде равенстваx4 + x5 = x6 , то сразу обнаружим, что третье ограничение-равенство в исходной задаче является суммой первых двух, то есть они линейно зависимы.После удаления строки в базисе остались только переменные исходной задачи.
Переходим на шаг 7 . Выразим через небазисные переменные целевуюфункцию w(x) . Из последней симплекс-таблицы имеем равенства3 / 2 x1 + x3 = 3 / 2 ,- 1 / 2 x1 + x2 = 1 / 2 ,то естьw( x ) = - x1 - 4(1 / 2 + 1 / 2 x1 ) - (3 / 2 - 3 / 2 x1) = -7 / 2 - 3 / 2 x1 .Добавляем нулевую строку - w - 3 / 2 x1 = 7 / 2 к предыдущей таблице, учитывая, что первая строка вычеркнута,-wxw3x27/23/21/2x1x2-3/2 03/2 0-1/2 157x3010Получим прямо допустимую симплекс-таблицу исходной задачи с базисомB = ( A2 , A3 ) и соответствующим решением x = (0,1 / 2,3 / 2) . Теперь переходим на шаг 8 и ищем оптимальное решение.
Так как симплекс-таблица неявляется двойственно допустимой, то выбираем s = 1 , r = 1 . Преобразуемтаблицу с ведущим элементом z11 = 3 / 2 и окончательно приходим к прямо идвойственно допустимой таблицеx1-w 5 0x1 1 1x2 1 0x 2 x3010 2/31 1/3из которой следует, что x* = (1,1,0) , w( x* ) = -5 .§ 5. Двойственный симплекс-методЗадача линейного программирования D(b, y ) ® maxyA £ cназывается двойственной к прямой задаче (1)-(3), которую обозначим черезP [2, 3, 5-7, 9-11]. Существует глубокая связь между этими задачами.
Чтобывыявить ее, проанализируем итоги работы лексикографического симплексметода. Как следует из его описания, может быть только два варианта завершения работы алгоритма.Рассмотрим первый вариант, когда задача P разрешима. Пусть x - оптимальное б.д.р. Тогда в оптимальной симплекс-таблице оценки замещения небазисных переменных удовлетворяют условию c N - c B B -1 N ³ 0 , а для базисных переменных выполняется тривиальное тождество c B - c B B -1B = 0 .Из приведенных уравнений и неравенств следует, что вектор y = c B B -1 является допустимым решением задачи D .
Из определения вектора y такжеследуют равенства (b, y ) = (b, c B B -1 ) = ( B -1b, c B ) = ( c B , x B ) = ( c, x ) . Рассмотрим два произвольных допустимых решения x и y прямой и двойственной задач, соответственно. Тогда, ( c, x ) ³ ( yA, x ) = ( Ax , y ) = (b, y ) . С учетом предыдущих равенств ( c, x ) ³ (b, y ) = ( c B , x B ) = ( c, x ) ≥ (b, y ) .
То есть y –оптимальное решение задачи D .Во втором варианте обнаруживается неразрешимость задачи P . Тогда неразрешима и задача D . Так как в противном случае мы могли бы найти ееоптимальное решение. Для этого необходимо записать двойственную задачув каноническом виде и применить симплекс-метод для ее решения. По при-58веденной выше схеме найти оптимальное решение задачи P , что невозможно.Для того чтобы связи между этими задачами стали более ясными и понятными, введем понятие базиса и базисного решения двойственной задачи.
Вектор y называется базисным решением задачи D , если среди неравенствyA £ c , которые он обращает в равенства, имеется m линейно независимых,а базис состоит из векторов A j , j = 1,K, m , образующих эти независимыеограничения. Б.д.р. y называется невырожденным, если для любого вектораA j , не входящего в его базис, то есть j Î S ¢ , выполняется yA j < c j . Двойственную задачу назовем невырожденной, если все ее б.д.р.
являются невырожденными.Теперь все базисные решения задач P и D можно разбить на пары решений, на которых значения целевых функций совпадают. Если x – базисноерешение задачи P с базисом B , то ему соответствует базисное, но недопустимое решение y = c B B -1 задачи D , так как могут нарушаться некоторые изограничений yN £ c .
Верно и обратное утверждение. Очевидно, что выполняются равенства ( c, x ) = ( c B , x B ) = ( yB, x B ) = ( Bx B , y ) = (b, y ) .Из вышеизложенного следует, что фактически в симплекс-методе на каждой итерации рассматриваются базисные решения прямой и двойственнойзадач с равными значениями целевых функций. Алгоритм организован такимобразом, что на нулевом шаге 1-ой итерации выбирается прямо допустимыйбазис и затем с помощью элементарных преобразований, сохраняющих прямо допустимость, происходит перебор базисов. В тот момент, когда обнаруживается двойственно допустимый базис или неразрешимость задачи, процесс останавливается.Теперь мы можем сформулировать идею нового алгоритма, который назовем двойственным симплекс-методом. На нулевом шаге 1-ой итерации выбирается начальный двойственно допустимый базис и затем с помощью элементарных преобразований, сохраняющих двойственную допустимость, происходит перебор базисов.
В тот момент, когда обнаруживается прямо допустимый базис или неразрешимость задачи, процесс останавливается.В приведенном ниже описании алгоритма этого метода предполагается,что используются та же форма симплекс-таблицы и то же элементарное преобразование, что и в параграфе 1. Под s (i ) , i = 1,..., m , как и прежде, понимается набор номеров базисных столбцов (переменных).Описание алгоритма двойственного симплекс-метода.Шаг 0. Начать с двойственно допустимой симплекс-таблицы.Шаг 1. Если симплекс-таблица прямо допустима, то КОНЕЦ (полученооптимальное решение).Шаг 2.
Выбрать ведущую строку r по правилу: z r 0 < 0 , r Î{1,K , m} .59Шаг 3. Если { j | z rj < 0, j = 1,K, n} ¹ Æ , то выбрать ведущий столбец s поправилу:üïìï z0 jz0 s= min í| z rj < 0, j = 1,K, n ý ,| z rs |ïþïî | z rj |иначе КОНЕЦ (задача неразрешима, так как Q = Æ ).Шаг 4. Преобразовать симплекс-таблицу, положить s ( r ) := s и перейти нашаг 1.Замечания.1. Доказательство того, что двойственная допустимость симплекс-таблицыв результате ее преобразования на шаге 4 сохраняется, может быть выполнено аналогично тому, как проводилось ранее доказательство сохранения прямой допустимости в случае прямого симплекс-метода.
Таким образом, если впрямом симплекс-методе идет целенаправленный перебор прямо допустимыхбазисов, то в двойственном симплекс-методе – двойственно допустимых базисов. Цель в обоих случаях одна и та же – найти прямо и двойственно допустимый базис.2. Если на шаге 3 имеем z rj ³ 0 , j = 1,...n , то это означает, что задача неразрешима ввиду несовместности ограничений. В самом деле, r -ой строкесимплекс-таблицы соответствует уравнение системы (8)nå z rj x jj= 1= z r 0 , изкоторого при x ³ 0 следует z r0 ³ 0 .
С другой стороны, согласно правилу выбора ведущей строки, z r0 < 0 . Эти два противоречащих друг другу неравенства свидетельствуют об отсутствии у системы (8) неотрицательных решений, то есть о несовместности ограничений задачи (1)-(3).3. Рассмотрим ряд случаев, когда вопрос о нахождении двойственно допустимого базиса решается просто.а) Предположим, что требуется решить задачу ЛП min{cx | Ax £ b, x ³ 0} снеотрицательным вектором c . С помощью введения дополнительных переменных y = ( y1 ,..., y m ) T задача может быть преобразована в каноническуюформу min{cx | Ax + y = b, x ³ 0, y ³ 0} . Очевидно, базис, образованный последними m столбцами матрицы [A, E ] системы ограничений новой задачи,является двойственно допустимым и итерации двойственного симплексé0 c 0 ùметода можно начинать с симплекс-таблицы êú.ëb A E ûб) Может сложиться такая ситуация, когда после получения оптимальногорешения задачи (1)-(3) и соответствующего прямо и двойственно допустимо-60го базиса B нужно получить оптимальное решение задачи с измененнымиправыми частями системы ограничений (2).
Нетрудно видеть, что для измененной задачи базис B является также двойственно допустимым и можетбыть использован в качестве начального базиса для решения задачи двойственным симплекс-методом.в) Прием, использованный в случае а) для получения двойственно допустимой симплекс-таблицы, может быть распространен на ситуации, когда кограничениям задачи ЛП, для которой известна некоторая двойственно допустимая симплекс-таблица, добавляются новые ограничения. Эта возможность используется при решении задач целочисленного линейного программирования методами отсечения, о чем более подробно речь будет идти в параграфе 3 главы 4.4.
Конечность двойственного симплекс-алгоритма доказывается так же,как и конечность прямого симплекс-метода. Если двойственная задача D невырожденная, то алгоритм конечен при любом уточнении правил выбора ведущего элемента. Отметим, что в случае невырожденной задачи D в каждойдвойственно допустимой симплекс-таблице элементы z 0 j , j Î S ¢ , должныбыть положительными.В случае вырожденной задачи конечность двойственного симплекс-методаможет быть обеспечена за счет использования тех же способов, что и в случае прямого симплекс-метода, в частности, путем применения некоторогоаналога правила Блэнда или лексикографической процедуры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
