Двойственный симплекс-метод. Подробный пример решения

см. также Как найти двойственные оценки.

Задание.
5x1 + 6x2≥1
15x1≥1
7x1 + 12x2≥1

Решение находим через калькулятор.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x1 + x2 при следующих условиях-ограничений.
- 5x1 - 6x2≤-1
- 15x1≤-1
- 7x1 - 12x2≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
-5x1-6x2 + 1x3 + 0x4 + 0x5 = -1
-15x1 + 0x2 + 0x3 + 1x4 + 0x5 = -1
-7x1-12x2 + 0x3 + 0x4 + 1x5 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A= -5 -6 1 0 0
-15 0 0 1 0
-7 -12 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,-1,-1,-1)
Базисное решение называется допустимым, если оно неотрицательно.

Базис

B x1 x2 x3 x4 x5

x3

-1 -5 -6 1 0 0

x4

-1 -15 0 0 1 0

x5

-1 -7 -12 0 0 1

F(X0)

0 -1 -1 0 0 0

1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x3 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-6).

Базис

B x1 x2 x3 x4 x5

x3

-1 -5 -6 1 0 0

x4

-1 -15 0 0 1 0

x5

-1 -7 -12 0 0 1

F(X)

0 -1 -1 0 0 0

θ

0 -1 : (-5) = 1/5 -1 : (-6) = 1/6 - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B x1 x2 x3 x4 x5

x2

1/6 5/6 1 -1/6 0 0

x4

-1 -15 0 0 1 0

x5

1 3 0 -2 0 1

F(X0)

1/6 -1/6 0 -1/6 0 0

Представим расчет каждого элемента в виде таблицы:

B

x 1 x 2 x 3 x 4 x 5

1/6 : 1

5/6 : 1 1 : 1 -1/6 : 1 0 : 1 0 : 1

-1-(1/6 • 0):1

-15-(5/6 • 0):1 0-(1 • 0):1 0-(-1/6 • 0):1 1-(0 • 0):1 0-(0 • 0):1

1-(1/6 • 0):1

3-(5/6 • 0):1 0-(1 • 0):1 -2-(-1/6 • 0):1 0-(0 • 0):1 1-(0 • 0):1

1/6-(1/6 • 0):1

-1/6-(5/6 • 0):1 0-(1 • 0):1 -1/6-(-1/6 • 0):1 0-(0 • 0):1 0-(0 • 0):1

1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x4 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-15).

Базис

B x1 x2 x3 x4 x5

x2

1/6 5/6 1 -1/6 0 0

x4

-1 -15 0 0 1 0

x5

1 3 0 -2 0 1

F(X)

1/6 -1/6 0 -1/6 0 0

θ

0 -1/6 : (-15) = 1/90 - - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B x1 x2 x3 x4 x5

x2

1/9 0 1 -1/6 1/18 0

x1

1/15 1 0 0 -1/15 0

x5

4/5 0 0 -2 1/5 1

F(X1)

8/45 0 0 -1/6 -1/90 0

Представим расчет каждого элемента в виде таблицы:

B

x 1 x 2 x 3 x 4 x 5

1/9-(1/15 • 0):1

0-(1 • 0):1 1-(0 • 0):1 -1/6-(0 • 0):1 1/18-(-1/15 • 0):1 0-(0 • 0):1

1/15 : 1

1 : 1 0 : 1 0 : 1 -1/15 : 1 0 : 1

4/5-(1/15 • 0):1

0-(1 • 0):1 0-(0 • 0):1 -2-(0 • 0):1 1/5-(-1/15 • 0):1 1-(0 • 0):1

8/45-(1/15 • 0):1

0-(1 • 0):1 0-(0 • 0):1 -1/6-(0 • 0):1 -1/90-(-1/15 • 0):1 0-(0 • 0):1

В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис

B x1 x2 x3 x4 x5

x2

1/9 0 1 -1/6 1/18 0

x1

1/15 1 0 0 -1/15 0

x5

4/5 0 0 -2 1/5 1

F(X1)

8/45 0 0 -1/6 -1/90 0
Оптимальный план можно записать так:
x1 = 1/15
x2 = 1/9
F(X) = 1•1/9 + 1•1/15 = 8/45
загрузка...