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

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

Алгоритм двойственного симплекс-метода

1) выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;
2) выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;
3) пересчитывают симплексную таблицу по правилам обычного симплекс-метода;
4) решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.
Замечания
1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.
2. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.

Пример. Решить задачу, используя алгоритм двойственного симплекс-метода

L = x1 + 4x2 → min

Составляем исходную симплексную таблицу.

Баз. x1 x2 x3 x4 x5 x6 x7 Св.
x4 -2 -3 1 0 0 0 -20
x5 -5 1 -2 0 1 0 0 -12
x6 1 2 -1 0 0 1 0 2
x7 -1 4 -2 0 0 0 1 1
L -1 -4 -1 0 0 0 0 0

Отсутствие в L строке положительных оценок свидетельствует об оптимальности исходного решения, а наличие в столбце свободных членов отрицательных элементов – о его недопустимости. Согласно алгоритму двойственного симплекс-метода выбираем разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных элементов. В нашем примере разрешающая строка – первая. Разрешающий столбец выбирается в соответствии с правилом, изложенным в пункте 2 схемы алгоритма. Разрешающий элемент равен (-4). После пересчета получаем следующую таблицу

Баз. х1 х2 х3 х4 х5 х6 х7 Св.
х3 1 0 0 0 5
х5 0 1 0 0 -2
х6 0 0 1 0 7
х7 0 0 0 0 1 11
L 0 0 0 0 5

Аналогично рассуждая, получим еще одну таблицу

Баз. х1 х2 х3 х4 х5 х6 х7 Св.
х3 0 1 0 0
х1 1 0 0 0
х6 0 0 1 0
х7 0 0 0 0 1 11
L 0 0 0 0

Отсутствие в столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение , .
Замечание. Если решение ЗЛП и недопустимо и неоптимально, то сначала получаем допустимое решение, используя алгоритм двойственного симплекс-метода, а затем по правилам обычного симплекс-метода получаем оптимальное решение.
Пример.
L = 5x1 – x2 – x3 → max
или

Составляем исходную симплекс-таблицу

Баз.

x1 x2 x3 x4 x5 x6 x7 Св.
x4 0 -2 1 0 0 0 -9
x5 1 -1 0 0 1 0 0 -1
x6 -1 -1 3 0 0 1 0 -8
x7 1 0 -1 0 0 0 1 4
L -5 1 4 0 0 0 0 0

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

Баз. x1 x2 x3 x4 x5 x6 x7 Св.
x2 0 1 2 -1 0 0 0 9
x5 1 0 2 -1 1 0 0 8
x6 -1 0 5 -1 0 1 0 1
x7 0 -1 0 0 0 1 4
L -5 0 2 1 0 0 0 -9

В столбце свободных членов нет отрицательных элементов, но в строке L есть отрицательная оценка (-5), значит решение допустимо, неоптимально.
Используем обычный симплекс-метод и получаем следующие таблицы

Баз. x1 x2 x3 x4 x5 x6 x7 Св.
x2 0 1 2 -1 0 0 0 9
х5 0 0 3 -1 1 0 -1 4
х6 0 0 -1 0 1 1 5
x1 1 0 -1 0 0 0 1 4
L 0 0 -3 1 0 0 5 11

Баз. x1 x2 x3 x4 x5 x6 x7 Св.

x2 0 1 0 0
x5 1 0 0 1
x6 0 0 1 0
x1 0 0 0 0
L 0 0 0 0

Отсутствие в строке L отрицательных оценок свидетельствует о том, что получено оптимальное решение.
, .

Перейти к онлайн решению своей задачи

Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект