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

Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой в системе уравнений, имеется m единичных векторов. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, когда прямой симплекс-метод не может быть использован, т.е. когда свободные члены системы уравнений могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными), а система ограничений задана неравенствами вида « »,« », «=». Определенная таким образом задача называется задачей в двойственной базисной форме.

Идея двойственного симплекс-метода с учетом существующей взаимосвязи с прямым симплексным методом заключается в получении вначале недопустимого, но «лучшего», чем искомое оптимальное решение, а затем в последовательном «приближении» решения к области допустимых при выполнении условия оптимальности.

Рассмотрим такую задачу, т.е. рассмотрим каноническую задачу ЛП, записанную в векторной форме, предварительно предположив, что имеется m единичных векторов:

,

где – матрица-столбец свободных членов; где среди чисел имеются отрицательные.

, ,…, – вектора условий функции при соответствующих переменных (столбцы), среди которых есть единичные,

– матрица-столбец неизвестных,

0 – нулевая матрица-столбец той же размерности, что и Х.

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

Решение системы линейных уравнений, определяемое базисом, называется псевдопланом исходной задачи, если .

Таким образом, псевдопланом называется план, в котором условия оптимальности удовлетворяются, а среди компонент имеются отрицательные числа.

Теорема. Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то исходная задача вообще не имеет планов.

Алгоритм решения задачи двойственным симплекс-методом.

1. Составление псевдоплана.

Систему ограничений исходной задачи требуется привести к системе неравенств вида « ». Для этого обе части неравенства вида « » необходимо умножить на (-1). Затем от системы неравенств вида « » переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. На основе исходных данных составляют симплекс-таблицу), в которой некоторые элементы столбца вектора В отрицательные числа, и получаем первый опорный план.

2. Проверка плана на оптимальность.

Если в опорном плане условие оптимальности выполняется и все значения базисных переменных – положительные числа, то получен оптимальный план. Если же имеются отрицательные базисные переменные, то говорят, что получен псевдоплан.

3. Выбор направляющих строки и столбца.

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

Чтобы определить, какой вектор следует ввести в базис (направляющий столбец), находим , где - отрицательные коэффициенты направляющей строки.

Число, стоящее на пересечении направляющей строки и направляющего столбца называется направляющим элементом.