Двойственный симплекс-метод.
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 15x1 + 7x2 + 12x3 при следующих условиях-ограничений.
- x1 - x2 - 2x3≤-2
- 3x1 - x2 - x3≤-3
- 5x1 - x2 - 4x3≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
-1x1-1x2-2x3 + 1x4 + 0x5 + 0x6 = -2
-3x1-1x2-1x3 + 0x4 + 1x5 + 0x6 = -3
-5x1-1x2-4x3 + 0x4 + 0x5 + 1x6 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
EQ A = \b\bc\| (\a \al \co6 \hs3 (-1;-1;-2;1;0;0;-3;-1;-1;0;1;0;-5;-1;-4;0;0;1))
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-2,-3,-1)
Базисное решение называется допустимым, если оно неотрицательно.
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x4
|
-2
|
-1
|
-1
|
-2
|
1
|
0
|
0
|
x5
|
-3
|
-3
|
-1
|
-1
|
0
|
1
|
0
|
x6
|
-1
|
-5
|
-1
|
-4
|
0
|
0
|
1
|
F(X0)
|
0
|
-15
|
-7
|
-12
|
0
|
0
|
0
|
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3).
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x4
|
-2
|
-1
|
-1
|
-2
|
1
|
0
|
0
|
x5
|
-3
|
-3
|
-1
|
-1
|
0
|
1
|
0
|
x6
|
-1
|
-5
|
-1
|
-4
|
0
|
0
|
1
|
F(X)
|
0
|
-15
|
-7
|
-12
|
0
|
0
|
0
|
θ
|
0
|
-15 : (-3) = 5
|
-7 : (-1) = 7
|
-12 : (-1) = 12
|
-
|
-
|
-
|
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x4
|
-1
|
0
|
-2/3
|
-12/3
|
1
|
-1/3
|
0
|
x1
|
1
|
1
|
1/3
|
1/3
|
0
|
-1/3
|
0
|
x6
|
4
|
0
|
2/3
|
-21/3
|
0
|
-12/3
|
1
|
F(X0)
|
15
|
0
|
-2
|
-7
|
0
|
-5
|
0
|
Представим расчет каждого элемента в виде таблицы:
B
|
x 1
|
x 2
|
x 3
|
x 4
|
x 5
|
x 6
|
-1-(1 • 0):1
|
0-(1 • 0):1
|
-2/3-(1/3 • 0):1
|
-12/3-(1/3 • 0):1
|
1-(0 • 0):1
|
-1/3-(-1/3 • 0):1
|
0-(0 • 0):1
|
1 : 1
|
1 : 1
|
1/3 : 1
|
1/3 : 1
|
0 : 1
|
-1/3 : 1
|
0 : 1
|
4-(1 • 0):1
|
0-(1 • 0):1
|
2/3-(1/3 • 0):1
|
-21/3-(1/3 • 0):1
|
0-(0 • 0):1
|
-12/3-(-1/3 • 0):1
|
1-(0 • 0):1
|
15-(1 • 0):1
|
0-(1 • 0):1
|
-2-(1/3 • 0):1
|
-7-(1/3 • 0):1
|
0-(0 • 0):1
|
-5-(-1/3 • 0):1
|
0-(0 • 0):1
|
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x4 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2/3).
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x4
|
-1
|
0
|
-2/3
|
-12/3
|
1
|
-1/3
|
0
|
x1
|
1
|
1
|
1/3
|
1/3
|
0
|
-1/3
|
0
|
x6
|
4
|
0
|
2/3
|
-21/3
|
0
|
-12/3
|
1
|
F(X)
|
15
|
0
|
-2
|
-7
|
0
|
-5
|
0
|
θ
|
0
|
-
|
-2 : (-2/3) = 3
|
-7 : (-12/3) = 41/5
|
-
|
-5 : (-1/3) = 15
|
-
|
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x2
|
11/2
|
0
|
1
|
21/2
|
-11/2
|
1/2
|
0
|
x1
|
1/2
|
1
|
0
|
-1/2
|
1/2
|
-1/2
|
0
|
x6
|
3
|
0
|
0
|
-4
|
1
|
-2
|
1
|
F(X1)
|
18
|
0
|
0
|
-2
|
-3
|
-4
|
0
|
Представим расчет каждого элемента в виде таблицы:
B
|
x 1
|
x 2
|
x 3
|
x 4
|
x 5
|
x 6
|
11/2 : 1
|
0 : 1
|
1 : 1
|
21/2 : 1
|
-11/2 : 1
|
1/2 : 1
|
0 : 1
|
1/2-(11/2 • 0):1
|
1-(0 • 0):1
|
0-(1 • 0):1
|
-1/2-(21/2 • 0):1
|
1/2-(-11/2 • 0):1
|
-1/2-(1/2 • 0):1
|
0-(0 • 0):1
|
3-(11/2 • 0):1
|
0-(0 • 0):1
|
0-(1 • 0):1
|
-4-(21/2 • 0):1
|
1-(-11/2 • 0):1
|
-2-(1/2 • 0):1
|
1-(0 • 0):1
|
18-(11/2 • 0):1
|
0-(0 • 0):1
|
0-(1 • 0):1
|
-2-(21/2 • 0):1
|
-3-(-11/2 • 0):1
|
-4-(1/2 • 0):1
|
0-(0 • 0):1
|
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис
|
B
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
x2
|
11/2
|
0
|
1
|
21/2
|
-11/2
|
1/2
|
0
|
x1
|
1/2
|
1
|
0
|
-1/2
|
1/2
|
-1/2
|
0
|
x6
|
3
|
0
|
0
|
-4
|
1
|
-2
|
1
|
F(X1)
|
18
|
0
|
0
|
-2
|
-3
|
-4
|
0
|
Оптимальный план можно записать так:
x2 = 11/2
x1 = 1/2
x6 = 3
F(X) = 7•11/2 + 15•1/2 = 18
Ответы на вопросы преподавателя:
1. По какому методу пересчитываются симплекс-таблицы?
Используется правило прямоугольника (метод жордановских преобразований).
2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки?
Можно не выбирать, но это может привести к зацикливанию алгоритма.
3. В индексной строке в n-ом столбце нулевое значение. Что это означает?
Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов.
Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Решение было получено и оформлено с помощью сервиса:
Двойственный симплекс-метод
Вместе с этой задачей решают также:
Графический метод решения задач линейного программирования
Симплекс-метод
Двойственная задача линейного программирования
Метод Гомори
Транспортная задач