Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 14

Действительно, не трудно заметить, что симплекс-таблица с условиями исходной задачи включает и условия двойственной задачи. Так, строки этой таблицы содержат левые части ограничений исходной задачи, столбцы – левые части ограничений двойственной задачи. Элементы столбца B представляют собой коэффициенты вектора ограничений прямой задачи и одновременно оценки плана двойственной задачи. Элементы строки D дают оценки плана исходной и одновременно коэффициенты вектора ограничений двойственной задач. Поэтому при решении двойственной задачи можно не строить специальную симплекс-таблицу, а решать ее по таблице, где записаны условия исходной задачи. Компоненты оптимального плана двойственной задачи находятся в клетках оценочной строки, соответствующих начальному единичному базису другой задачи.

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

На основании теории двойственности разработан так называемый двойственный симплекс-метод. Как неоднократно отмечалось, обычный симплекс-метод применяется для решения задач с неотрицательными коэффициентами b_i вектора ограничений и произвольными по знаку D_j . Иногда бывает легче найти базис, удовлетворяющий признаку оптимальности (все Dj³ 0), но не удовлетворяющий критерию допустимости (так как не все b_i ³0).

Вариант симплекс-метода, применяемый для решения таких задач, называется двойственным симплекс-методом. С его помощью решаются задачи линейного программирования

max z = CX ; AX=B ; X³0, где матрица A содержит единичный базис и все приведенные коэффициенты целевой функции D_j³0, j=1, …, n. При этом условие b_i ³ 0, i=1, .., m, не требуется. Определенную таким образом задачу будем называть задачей в двойственной базисной форме.

Обычный симплекс-метод, применяемый к задаче в базисной форме, приводит к последовательности эквивалентных задач с возрастающими значениями целевой функции и неотрицательными значениями b_i, так что каждое базисное решение является допустимым. Двойственный симплекс-метод, применяемый к задаче в двойственной базисной форме, приводит к последовательности задач с убывающим значением целевой функции, неотрицательными коэффициентами D_j, j=1, …, n, и значениями b_i любого знака.

Преобразования задач выполняются до тех пор, пока не будет установлено, что исходная задача не имеет допустимого решения или будет получена задача с допустимым базисным решением (все b_i ³ 0), которое одновременно и оптимально.

Рассмотрим задачу в двойственной базисной форме. В отношении ее возможен один из трех случаев.

С л у ч а й 1. Все координаты вектора ограничений неотрицательны, b_i ³0, i=1, .., m. Тогда они дают не только допустимый, но и оптимальный план задачи, поскольку по предположению все оценки D_j³0.

С л у ч а й 2. Имеется строка iÎ1, .., m, такая, что b_i < 0 и a_ij ³0 для всех j=1, .., n. Тогда задача неразрешима в силу несовместности ограничений

С л у ч а й 3. Имеется строка rÎ1, .., m, такая, что b_r<0 и a_rj<0 хотя бы для одного jÎ1, .., n. Пусть sÎ1, .., n таково, что a_rs<0 и

                                    D_s /a_rs = max (D_j/a_rj) .

Тогда жорданово преобразование с ведущим элементом a_rs приводит к эквивалентной задаче, в которой, во-первых, оценки D_j³0, j=1, …, n, а во-вторых, значения целевой функции z^¢ £ z, и если D_s ¹0, то z^¢  <z.

Рассмотрим далее вычислительную схему двойственного симплекс-метода, приводимую в [4]. Данный метод, применяемый к задаче в двойственной базисной форме, состоит из следующих шагов, повторяющихся до тех пор, пока в ходе жордановых преобразований не будет установлено соответствие очередной эквивалентной задачи приведенным случаям 1 или 2.

1. Проверяем знаки коэффициентов ограничений b_i. Если все b_i³0, i=1, …, m, то имеет место случай 1. Базисное решение и значение целевой функции, записанное в столбце свободных членов B, дают оптимальное решение исходной задачи. Если не все b_i³0, переходим к шагу 2.