Построить двойственную задачу линейного программирования. Решить исходную и двойственную задачу с использованием пакета MS Excel.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = 8x1 + 6x2 + 5x3 при следующих условиях-ограничений.
2x1 + x2 + 3x3≥4
3x1 + x2 + 2x3≥5
4x1 + 5x2 + x3≥3
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 1x2 + 3x3-1x4 + 0x5 + 0x6 = 4
3x1 + 1x2 + 2x3 + 0x4-1x5 + 0x6 = 5
4x1 + 5x2 + 1x3 + 0x4 + 0x5-1x6 = 3
Умножим все строки на (-1) и будем искать первоначальный опорный план.
-2x1-1x2-3x3 + 1x4 + 0x5 + 0x6 = -4
-3x1-1x2-2x3 + 0x4 + 1x5 + 0x6 = -5
-4x1-5x2-1x3 + 0x4 + 0x5 + 1x6 = -3
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:
x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-4,-5,-3)
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | -4 | -2 | -1 | -3 | |||
| x5 | -5 | -3 | -1 | -2 | |||
| x6 | -3 | -4 | -5 | -1 | |||
| F(X0) |
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2).
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | -4 | -2 | -1 | -3 | |||
| x5 | -5 | -3 | -1 | -2 | |||
| x6 | -3 | -4 | -5 | -1 | |||
| F(X0) | |||||||
| θ | 8 : (-3) = -22/3 | 6 : (-1) = -6 | 5 : (-2) = -21/2 | - | - | - |
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | 31/2 | 21/2 | 1/2 | -11/2 | |||
| x3 | 21/2 | 11/2 | 1/2 | -1/2 | |||
| x6 | -1/2 | -21/2 | -41/2 | -1/2 | |||
| F(X0) | -121/2 | 1/2 | 31/2 | 21/2 |
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/2).
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | 31/2 | 21/2 | 1/2 | -11/2 | |||
| x3 | 21/2 | 11/2 | 1/2 | -1/2 | |||
| x6 | -1/2 | -21/2 | -41/2 | -1/2 | |||
| F(X0) | -121/2 | 1/2 | 31/2 | 21/2 | |||
| θ | 1/2 : (-21/2) = -1/5 | 31/2 : (-41/2) = -7/9 | - | - | 21/2 : (-1/2) = -5 | - |
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | -3 | ||||||
| x3 | -1 | ||||||
| x5 | -2 | ||||||
| F(X1) | -15 | -12 | -19 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (9) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | min |
| x4 | -3 | 5/14 | ||||||
| x3 | -1 | 3/5 | ||||||
| x5 | -2 | 1/9 | ||||||
| F(X1) | -15 | -12 | -19 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | 34/9 | 22/9 | -15/9 | 1/9 | |||
| x3 | 24/9 | 12/9 | -5/9 | 1/9 | |||
| x2 | 1/9 | 5/9 | 1/9 | -2/9 | |||
| F(X1) | -128/9 | -14/9 | 21/9 | 7/9 |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (5/9) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | min |
| x4 | 34/9 | 22/9 | -15/9 | 1/9 | 111/20 | |||
| x3 | 24/9 | 12/9 | -5/9 | 1/9 | ||||
| x2 | 1/9 | 5/9 | 1/9 | -2/9 | 1/5 | |||
| F(X2) | -128/9 | -14/9 | 21/9 | 7/9 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | -4 | -2 | |||||
| x3 | 21/5 | -21/5 | -4/5 | 3/5 | |||
| x1 | 1/5 | 14/5 | 1/5 | -2/5 | |||
| F(X2) | -123/5 | 23/5 | 22/5 | 1/5 |
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| x4 | -4 | -2 | |||||
| x3 | 21/5 | -21/5 | -4/5 | 3/5 | |||
| x1 | 1/5 | 14/5 | 1/5 | -2/5 | |||
| F(X3) | -123/5 | 23/5 | 22/5 | 1/5 |
Оптимальный план можно записать так:
x4 = 3
x3 = 21/5
x1 = 1/5
F(X) = 5•21/5 + 8•1/5 = 123/5
Составим двойственную задачу к прямой задаче.
2y1 + 3y2 + 4y3≤8
y1 + y2 + 5y3≤6
3y1 + 2y2 + y3≤5
4y1 + 5y2 + 3y3 → max
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 22/5
y3 = 1/5
Z(Y) = 4*0+5*22/5+3*1/5 = 123/5