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

Решим систему уравнений относительно базисных переменных:
x3, x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,3,42,12,2)
Базис	B	x1	x2	x3	x4	x5	x6	
x3	3	-6	1	1	0	0	0	
x4	42	2	5	0	1	0	0	
x5	12	3	-1	0	0	1	0	
x6	2	1	-1	0	0	0	1	
F(X0)	0	4	-4	0	0	0	0	

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис	B	x1	x2	x3	x4	x5	x6	min	
x3	3	-6	1	1	0	0	0	-	
x4	42	2	5	0	1	0	0	21	
x5	12	3	-1	0	0	1	0	4	
x6	2	1	-1	0	0	0	1	2	
F(X1)	0	4	-4	0	0	0	0	0	

Получаем новую симплекс-таблицу:
Базис	B	x1	x2	x3	x4	x5	x6	
x3	15	0	-5	1	0	0	6	
x4	38	0	7	0	1	0	-2	
x5	6	0	2	0	0	1	-3	
x1	2	1	-1	0	0	0	1	
F(X1)	-8	0	0	0	0	0	-4	

Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
Базис	B	x1	x2	x3	x4	x5	x6	
x3	15	0	-5	1	0	0	6	
x4	38	0	7	0	1	0	-2	
x5	6	0	2	0	0	1	-3	
x1	2	1	-1	0	0	0	1	
F(X2)	-8	0	0	0	0	0	-4	

Оптимальный план можно записать так:
x3 = 15
x4 = 38
x5 = 6
x1 = 2
F(X) = -4•2 = -8
Составим двойственную задачу к прямой задаче.
 - 6y1 + 2y2 + 3y3 + y4≤-4
y1 + 5y2 - y3 - y4≤4
3y1 + 42y2 + 12y3 + 2y4 → max
y1 ≤ 0
y2 ≤ 0
y3 ≤ 0
y4 ≤ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 = 

Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 0
y3 = 0
y4 = -4
Z(Y) = 3*0+42*0+12*0+2*-4 = -8
В расширенном решении приведены все выкладки, а также анализ двойственных оценок (определение дефицитных и недефицитных (избыточных) ресурсов, обоснование эффективности оптимального плана) и их устойчивости.

Решение было получено и оформлено с помощью сервиса:
Двойственная задача линейного программирования
Вместе с этой задачей решают также:
Графический метод решения задач линейного программирования
Симплекс-метод
Двойственный симплекс-метод
Метод Гомори
Транспортная задача
Copyright © Semestr.RU