Решить задачу линейного программирования симплексным методом.

Пример 1:

Решить  задачу  линейного  программирования  симплексным   методом; используя   теорию  двойственности   в  анализе  оптимальных   решений экономических  задач  найти  двойственные оценки; сравнить оптимумы целевых   функций  взаимодвойственных   задач  и  дать   экономическую интерпретацию  оптимальных  решений  этих  задач.

Решение от преподавателя:

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x₁+4x₂+x₃ = 8
5x₁+x₂+x₄ = 5
Решим систему уравнений относительно базисных переменных: x₃, x₄
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,8,5)

Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (8 : 2 , 5 : 5 ) = 1
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 1 войдет переменная x₁.
Получаем новую симплекс-таблицу:

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (6 : 3.6 , 1 : 0.2 ) = 1.667
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3.6) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x₃ в план 2 войдет переменная x₂.
Получаем новую симплекс-таблицу:

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

Оптимальный план можно записать так:
x₁ = 0.667, x₂ = 1.667
F(X) = -2·0.667 -1·1.667 = -3

Построим двойственную задачу

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
y₁=-0.167, y₂=-0.333

Оптимальный план двойственной задачи равен:
y₁ = -0.167, y₂ = -0.333
Z(Y) = 8·(-0.167)+5·(-0.333) = -3

Анализ оптимального плана.
Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.
Значение 0 в столбце x₂ означает, что использование x₂ - выгодно.
Значение -0.167 в столбце x₃ означает, что теневая цена (двойственная оценка) равна y₁=-0.167.
Значение -0.333 в столбце x₄ означает, что теневая цена (двойственная оценка) равна y₂=-0.333.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
2·(-0.167) + 5·(-0.333) = -2 = -2
4·(-0.167) + 1·(-0.333) = -1 = -1
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-й продукт экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₁>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-й продукт экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).                                                                                                     

Пример 2:

Для производства 4-х видов продукции используется 3 вида сырья. Нормы расхода сырья (кг) запасы (кг) его ценность от реализации единицы продукции заданы таблицей.

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

Решение от преподавателя:

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. 
y₁=0.86, y₂=0.11, y₃=0 
Это же решение можно получить, применив теоремы двойственности. 
Из теоремы двойственности следует, что Y = C*A^-1. 
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

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

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

Оптимальный план двойственной задачи равен: 
y₁ = 0.86, y₂ = 0.11, y₃ = 0 
Z(Y) = 150*0.86+170*0.11+190*0 = 147.7