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

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

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

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 отрицательных оценок свидетельствует о том, что получено оптимальное решение.
, .

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

загрузка...