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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Методы дискретной оптимизацииСтолбцовые симплекс-таблицы.Двойственный симплекс-метод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).

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций