2.11 Двойственный симплекс-метод

В приведенном ниже описании алгоритма этого метода пред­полагается, что используется та же самая форма симплекс-таблицы и то же самое ее элементарное преобразование.   Под сг(г), г = 1,..., то, как и прежде, понимается набор номеров базисных столб­цов (переменных).

0) Начать с двойственно допустимой симплекс-таблицы.

1) Если симплекс-таблица прямо допустима, т.е. 2г'о > 0, г = 1,..., то, то КОНЕЦ (получено оптимальное решение).

 

2) Выбрать ведущую строку г : гг$ < 0, г I

3) Если {] | 2Г]- < 0, ^' > 1} / 0, то выбрать ведущий столбец в:

> 1.

г,

= П11П

 

2гэ < О, І > 1

иначе КОНЕЦ (задача неразрешима). 4) Преобразовать симплекс-таблицу, положить а (г) := в и перейти на шаг 1.

Замечания.

1. Доказательство того, что двойственная допустимость симп­лекс-таблицы в результате ее преобразования на шаге 4 сохраня­ется, может быть выполнено аналогично тому, как проводилось ранее доказательство сохранения прямой допустимости в случае прямого симплекс-метода. Таким образом, если в прямом симп­лекс-методе идет целенаправленный перебор прямо допустимых базисов, то в двойственном симлекс-методе — двойственно допу­стимых базисов. Цель в обоих случаях одна и та же — найти прямо и двойственно допустимый базис.

2. Если на шаге 3 имеем 2Г]- > 0, і = 1,..., га, то это означает, что задача неразрешима ввиду несовместности ограничений. В самом деле, г-й строке симплекс-таблицы соответствует уравне­ние системы (2.2")

из которого при х > 0 следует 2го > 0. С другой стороны, со­гласно правилу выбора ведущей строки гг$ < 0. Эти два проти­воречащих другу неравенства свидетельствуют об отсутствии у системы (2.2") неотрицательных решений, т.е. о несовместности ограничений задачи (2.1)-(2.3).

3. По поводу выполнения шага 0 мы не будем приводить об­щих рецептов, а ограничимся указанием на ряд случаев, когда

п

 

3 = 1

34вопрос о нахождении двойственно допустимого базиса решается достаточно просто.

а) Предположим, что требуется решить задачу ЛП тш{сж | Ах < Ь, х > 0} с неотрицательным вектором с. С помо­щью введения дополнительных переменных у = (?/!,..., ут)т за­дача может быть преобразована в каноническую форму тш{сж | Ах + у=Ь,х>0,у> 0}. Очевидно, базис, образо­ванный последними то столбцами матрицы [А, I] системы огра­ничений новой задачи, является двойственно допустимым и ите­рации двойственного симплекс-метода можно начинать с симп­лекс-таблицы

0

с   0 '

ь

А I

б) Может сложиться такая ситуация, когда после получения оптимального решения задачи (2.1)-(2.3) и соответсвующего пря­мо и двойственно допустимого базиса В мы хотели бы получить оптимальное решение задачи с измененными правыми частями V системы ограничений (2.2). Нетрудно видеть, что для изме­ненной задачи базис В является также двойственно допустимым и может быть использован в качестве начального для решения задачи двойственным симплекс-методом.

в) Прием, использованный в случае а) для получения двой­ственно допустимой симплекс-таблицы, может быть распростра­нен на ситуации, когда к ограничениям задачи ЛП, для которой известна некоторая двойственно допустимая симплекс-таблица, добавляются новые ограничения. Эта возможность используется при решении задач целочисленного линейного программирования методами отсечения (о чем более подробно речь будет идти поз­же).

4. По поводу конечности двойственного симплекс-алгоритма могут быть, фактически, повторены с естественными поправка­ми все высказывания, сделанные ранее по вопросу о конечности прямого симплекс-метода. В частности, если двойственная зада­ча (Д) невырожденна, то алгоритм конечен при любом уточнении правил выбора ведущего элемента. Отметим при этом, что в слу­чае невырожденной задачи (Д) в каждой двойственно допустимой симплекс-таблице элементы для номеров ]' небазисных пере­менных должны быть положительными, т.е. \{] | > 0, і > 1}| = п — т.

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