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

Пример 1:

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

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x₁+x₂-x₃ = 1
x₁+4x₂+x₄ = 3
Введем искусственные переменные x: в 1-м равенстве вводим переменную x₅; 
2x₁+x₂-x₃+x₅ = 1
x₁+4x₂+x₄ = 3
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = 10x₁+2x₂+Mx₅ → min
Из уравнений выражаем искусственные переменные:
x₅ = 1-2x₁-x₂+x₃
которые подставим в целевую функцию:
F(X) = 10x₁ + 2x₂ + M(1-2x₁-x₂+x₃) → min
или
F(X) = (10-2M)x₁+(2-M)x₂+(M)x₃+(M) → min
Решим систему уравнений относительно базисных переменных: x₅, x₄
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,3,1)

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

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

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

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

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

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x₁ = 0.143, x₂ = 0.714
F(X) = 10·0.143 + 2· 0.714 = 2.857