Лекция 9. Столбцовые симплекс-таблицы. Двойственный симплекс-метод (Лекции 2016 года)

Методы дискретной оптимизацииСтолбцовые симплекс-таблицы.Двойственный симплекс-метод1 / 26Столбцовые симплекс-таблицыРассмотрим задачу линейного программирования (ЛП) в каноническомвидеn(c, x) → max, x ∈ X = {x ∈ R+| Ax = a0 }.(1)Здесь матрица A ∈ Rm×n имеет m линейно независимых строк, впротивном случае система либо несовместна либо часть уравнений можноисключить. Вектор правой части системы и столбцы матрицы A сутьaj , j = 0, .

. . , n.Назовем базисом матрицы A набор из m линейно независимых еестолбцов, а базисным решением системы Ax = a0 , соответствующимвыбранному базису, назовем такое решение , для которого любаякоордината, не соответствующая базисному столбцу, равна нулю.Если базисное решение системы является неотрицательным вектором, т.е.точка x допустима для задачи (1), то такая точка является крайнейточкой для допустимого множества задачи (1) и наоборот: крайняя точкамножества X есть неотрицательное базисное решение системы Ax = a0 .2 / 26Столбцовые симплекс-таблицыБудем обозначать через IB множество номеров базисныхвекторов-столбцов матрицы A, а через IN множество номеров небазисных(или свободных) переменных.Запишемв задаче (1) в видеP систему уравненийPa0 = j∈IB aj xj + j∈IN aj xj .

Если матрицы (aj , j ∈ IB ) и (aj , j ∈ IN )обозначить через B и N соответственно, тоPбазисные переменныевыражаются через небазисные: xi = xi0 − j∈IN xij xj , здесьxij = (B −1 aj )i ,j ∈ IN[{0},i ∈ IB .Значение целевой функции представим тогда в видеXXX XXX(c, x) =cj xj +ci xi0 −ci xij xj =ci xi0 −x0j xj ,j∈INi∈IBj∈IN i∈IBi∈IBj∈INздесь и далееx0j =Xi∈IBci xij − cj ,j ∈ IN ,x00 =Xci xi0 .i∈IB3 / 26Столбцовые симплекс-таблицыЗадача (1) теперь запишется в видеXx0 = x00 −x0j xj → max,(2)j∈INxi = xi0 −Xxij xj ≥ 0,i ∈ IB ,(3)j∈INxj = 0 − (−xj ) ≥ 0,j ∈ IN .(4)Таким образом, если x – крайняя точка допустимого множества задачи(1), то ее координаты суть xi = xi0 при i ∈ IB , xi = 0 при i ∈ IN .Из условий (2)-(4) непосредственно следует , что одновременноевыполнение неравенств x0j ≥ 0, j ∈ IN есть необходимое и достаточноеусловие максимума для базисного допустимого решения.4 / 26Столбцовые симплекс-таблицыДля любой пары (i, j)такой, что i, j ∈ IN положим0, i 6= j,xij =−1, i = jЗадаче (2)-(4) теперь можно поставить в соответствие столбцовуюсимплекс-таблицу, т.е.

матрицу T ∈ R(n+1)×(|IN |+1) :x00 x0jT =,xi0 xijздесь i ∈ {1, . . . , n}, j ∈ IN . i−я строка ti этой матрицы равна−eTi , ei ∈ R(|IN |+1) при всех i ∈ IN , нулевой столбец t0 содержит значениецелевой функции в текущей крайней точке (x00 ) и координаты этой точки(xi0 , i = 1, . . . , n).Поскольку базис матрицы A может быть выбран неоднозначно и нампридется переходить от одного базиса к другому, то необходимо выяснить,как изменяются элементы матрицы T при замене базиса. Рассмотримслучай, когда из базиса выводится один из столбцов и вместо неговводится какой-то небазисный столбец.5 / 26Столбцовые симплекс-таблицыВыберем номер s ∈ IB такой, что xsl 6= 0 для некоторого l ∈ IN .

Выведемстолбец as из базиса матрицы A и вместо него введем в базис al .Переменную xl можно выразить из s−го неравенства (3):xl =xs0xs−−xslxslXj∈IN ,j6=lxsjxj ;xslподставляя Sданное выражение в выражения для каждогоxi , i ∈ IB {0}, i 6= s получим:X xsjXxxs0s−−xj  =xi = xi0 −xij xj − xil xslxslxslj∈IN ,j6=lj∈IN ,j6=lX xilxilxsjxi0 − xs0+xs −xij −xil xj =xslxslxslj∈IN ,j6=lX xs0xsjxilxi0 −xil −xij −xil xj −(−xs ).xslxslxslj∈IN ,j6=l6 / 26Столбцовые симплекс-таблицыТогда для столбцов tj , j 6= l матрицы T верны формулы перехода:[xsj ltj → tj −t , j ∈ {0} IN ,xsltl.−xslНетрудно убедиться в том, что строки преобразованных векторовсимплекс-таблицы, соответствующие небазисным переменным, будутравны[−eTi , ei ∈ R(|IN |+1) , i ∈ {s} IN , i 6= l.ts →(5)(6)Покажем, что условие xi0 ≥ 0, j ∈ IN является необходимым идостаточным условием оптимальности. Достаточность.

xj = 0j ∈ INрассмотрим вариации точки x. Фиксируем номер j ∈ IN , увеличиваясоответствующие координаты xj . При любом таком увеличении значениецелевой функции может только уменьшиться. НеобходимостьдоказываетсяP аналогично, но если существует i такое что xi0 = 0 тогдаxi = xi0 − j∈IN xij xj ≥ 0. Значит соответствующий столбец можновыбросить из симплекс-таблицы и перейти в пространство меньшейразмерности.7 / 26Прямо- и двойственно допустимые симплекс таблицыВектор a называется лексикографически положительным: a  0, еслипервая ненулевая координата его положительна.

При этом вектор aлексикографически больше вектора b, если a − b  0. Кроме того,a ≺ 0 ⇐⇒ −a  0.Назовем симплекс-таблицу T прямо допустимой, если xio ≥ 0, i ≥ 1.Рассмотрим двойственный симплекс-метод, предполагая, чтосимплекс-таблица T двойственно допустима: векторы-столбцыtj  0, j ∈ IN . Если симплекс-таблица кроме того и прямо допустима, токрайняя точка, соответствующая этой таблице, является решениемисходной задачи и координаты этого решения находятся в столбце t0 .

Впротивном случае обозначим через s какой-либо элемент среди техномеров i ∈ {1, . . . , n}, для которых xi0 < 0. Для найденного номера sопределим номер l из условия jttl= lexmin| xsj < 0, j ∈ IN .−xsl−xsj8 / 26Прямо- и двойственно допустимые симплекс таблицыЗдесь мы предполагаем, что множество Js = {j ∈ IN | xsj < 0} =6 ∅. Вэтом случае номер as выводим из базиса, а вектор al вводим в базис.Симплекс-таблица при этом в соответствии с (5),(6) переходит вдвойственно допустимую симплекс-таблицу: jttlxsj ljt = −xsj− 0 при всех j ∈ Jst −xsl−xsj−xslпо правилу выбора номера l; кроме того,tj −xsj lt ≥ tj  0 при всехxslj ∈ IN : xsj ≥ 0иtl0−xslпо предположению двойственной допустимости.9 / 26Прямо- и двойственно допустимые симплекс таблицыВ случае, когда множество Js = ∅, ограничение, соответствующее номеруs, дает пустое множество, поскольку в этом случае xs ≤ xs0 < 0, еслиxsj ≥ 0, j ∈ IN .

Таким образом, если Js = ∅, то множество допустимыхточек исходной задачи является пустым.По условию вектор-столбец tl  0, xs0 < 0, xsl < 0, поэтомуt0 −xs0 lt ≺ t0 ,xslчто означает лексикографическое убывание вектора t0 при нашей заменебазиса. Отсюда непосредственно следует Двойственныйсимплекс-метод.10 / 26Двойственный симплекс-методТеоремаДвойственный симплекс-метод за конечное число итераций позволяетполучить решение задачи ЛП в случае ее разрешимости илиустанавливает ее неразрешимость вследствие несовместности ееограничений.Доказательство. Число базисных решений системы Ax = a0 (а значит имножеств IB ) конечно и каждая симплекс-таблица взаимно однозначносоответствует множеству IB , следовательно, число симплекс-таблиц дляконкретной задачи также конечно. С другой стороны, вследствиемонотонного убывания вектора t0 на каждой итерации метода мыполучаем двойственно допустимую симплекс-таблицу, неприсутствовавшую ранее.

Значит, на каком-то шаге либо будет полученоусловие xi0 ≥ 0, i ∈ IB , которое означает, что решение уже получено, либоусловие xs0 < 0, Js = ∅, что означает пустоту исходного допустимогомножества.11 / 26Двойственный симплекс-методДо сих пор предполагалось, что исходная симплекс-таблица являетсядвойственно допустимой, что обеспечивало двойственную допустимость ина всех последующих итерациях. Если же для выбранного базисаматрицы A наше предположение не выполнено, то наряду сограничениями (3),(4) можно рассмотреть неравенствоXxn+1 = M −xj ≥ 0.j∈INЗдесь значение параметра M выбирается из условия, что хотя бы дляодного решения исходной задачи это неравенство выполнено.

Тогдавозможно будет сужено допустимое множество, но некоторые решенияисходной задачи будут по-прежнему являться решениями полученной"суженной"задачи. У симплекс-таблицы появится дополнительная строка(M 1 . . . 1) ∈ R1×(|IN |+1) ,и симплекс-таблица с этой новой строкой будет состоять извекторов-столбцов j 0[tttjM , j ∈ {0} IN , где tjM =, j ∈ IN , t0M =.1M12 / 26Двойственный симплекс-методТеперь выведем переменную xn+1 из числа базисных переменных, а вместонее введем xl , где номер l выберем из условия tl = lexmin{tj | j ∈ IN }.Тогда вектор tlM перейдет в вектор −tlM  0, а при других j ∈ IN векторыtjM перейдут в векторы tjM − tlM  0.

Таким образом будет полученадвойственно допустимая симплекс-таблица, которая после конечногочисла итераций двойственного симплекс-метода перейдет в оптимальную,т.е. и прямо допустимую с множеством IN небазисных переменных. Дляэтой оптимальной симплекс-таблицы справедливаЛеммаЕсли Pлюбое решение исходной задачи удовлетворяет условиюM − j∈IN xj 0, то вспомогательная переменная xn+1 является базисной.Доказательство этого факта легко провести от противного.13 / 26Двойственный симплекс-методУсловие леммы может быть выполнено, если множество решенийисходной задачи ограничено, а значение M достаточно велико. Иначепеременная xn+1 останется небазисной. В любом случае после вывода избазиса дополнительной строки эту строку можно вычеркнуть изсимплекс-таблицы. Следует отметить, что слишком большой величину Mвыбирать нецелесообразно, так как при этом нулевой столбецсимплекс-таблицы может слишком сильно увеличитьсялексикографически, вследствие чего может потребоваться много лишнихшагов метода.

Поэтому для получения двойственно допустимойсимплекс-таблицы рассмотрим другой метод, в котором не требуетсяоценки компонент решения исходной задачи, но при этом возникаетнеобходимость рассмотрения вспомогательной задачи, аналогичной задачев методе искусственного базиса.14 / 26Двойственный симплекс-методБудем считать, что в матрице A известен базис, то есть множества IB , INзаданы. Данному базису соответствует симплекс-таблица с элементамиxij , не являющаяся двойственно допустимой, по этой таблице нужнопостроить двойственно допустимую таблицу, то есть выбрать другой базисматрицы A, используя двойственный симплекс-метод. Для этогорассмотрим вспомогательную задачу(c, x) → max,2n(x, v) ∈ Xv = {(x, v) ∈ R+| Ax = 0,x + v = l}.(7)Здесь координаты вектора l равны lj = 1, j = 1, .

. . , n, а матрицаограничений задачи (7) состоит из векторовdj = (aj .ej )T ∈ Rm+n , g j = (0, ej )T ∈ Rm+n , ej ∈ Rn -j-й координатныйвектор, j = 1, . . . , n, Для задачи (7) выберем начальный базис матрицыограничений: dj , j = 1, 2, . . . , n, g i , i ∈ IB и будем множество базисныхggddвекторов этой задачи обозначать как IB, IB| = n, |IB, |IB| = |IB |. Такимобразом, начальному базису задачи (7) соответствуют номера базисныхgdпеременных IB= 1, 2, .

. . , n, IB= IB . Покажем, что выбранные векторылинейно независимы.15 / 26Двойственный симплекс-методВ самом деле, если существуют числа xj , j = 1, 2, . . . , n, vi , i ∈ IB такие,чтоnXaj xj = 0, xj = 0, j ∈ IN , , xi + vi = 0, i ∈ IB ,j=1то отсюда вытекает, что xi = 0, i ∈ IB , а значит vi = 0, i ∈ IB , что означаетлинейную независимость указанных векторов.Теперь выразим все переменные ограничений задачи (7) через небазисныепеременные vj , j ∈ IN . Непосредственно из условий(7) следует, чтоSxj = 1 − vj при всех j ∈ IN , откуда для i ∈ 0 IB величинаXXXxi = −xij xj = −xij +xij vj .(8)j∈INj∈INj∈INКроме того, для i ∈ IB переменнаяvi = 1 − x i = 1 +Xj∈INxij −Xxij vj .(9)j∈IN16 / 26Двойственный симплекс-методИз перечисленных выражений для базисных переменных следует, чтоначальная симплекс-таблица для задачи (7) имеет видx0xi (i ∈ IB )xj (j ∈ IN )vi (i ∈ IB )vj (j ∈ IN )t0P− j∈IN x0jP− j∈IN xij1P1 + j∈IN xij0tj , j ∈ IN−x0j , j ∈ IN−xij , j ∈ IN(ej )T ∈ Rn−mxij , , j ∈ IN−(ej )T ∈ Rn−m , , j ∈ IN17 / 26Двойственный симплекс-методДля полученной симплекс-таблицы условия задачиP (7) означают, чтолюбая допустимая точка удовлетворяет условию j∈IN vj ≤ n − m.Поэтому вводя строку,соответствующую вспомогательной переменнойPxn+1 = n − m − j∈IN vj ≥ 0, и выводя xn+1 из базиса, как это былоописано ранее, получим двойственно допустимую симплекс-таблицу.Далее, улучшая ее двойственным симплекс-методом, получим решениезадачи (7).