Симплекс метод

Решим прямую задачу линейного программирования симплексным  методом, с использованием симплексной  таблицы. 
Определим максимальное значение целевой функции F(X) = x₁ - 2x₂ - 4x₃ + 2x₄ + 3x₅ при следующих условиях-ограничений. 
2x₁ + 3x₂ - x₃ + x₄ + x₅=18 
- 2x₂ + 3x₃ + x₄=>24 
- x₁ + 4x₂ - x₄=>12 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
2x₁ + 3x₂-1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ = 18 
0x₁-2x₂ + 3x₃ + 1x₄ + 0x₅-1x₆ + 0x₇ = 24 
-1x₁ + 4x₂ + 0x₃-1x₄ + 0x₅ + 0x₆-1x₇ = 12 
Введем искусственные переменные x: в 1-м равенстве вводим переменную x₈; в 2-м равенстве вводим переменную x₉; в 3-м равенстве вводим переменную x₁₀;  
2x₁ + 3x₂-1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ + 1x₈ + 0x₉ + 0x₁₀ = 18 
0x₁-2x₂ + 3x₃ + 1x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 1x₉ + 0x₁₀ = 24 
-1x₁ + 4x₂ + 0x₃-1x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ + 0x₉ + 1x₁₀ = 12 
Для постановки задачи на максимум целевую функцию запишем так: 
F(X) = x₁-2x₂-4x₃+2x₄+3x₅ - Mx₈ - Mx₉ - Mx₁₀ → max 
Из уравнений выражаем искусственные переменные: 
x₈ = 18-2x₁-3x₂+x₃-x₄-x₅ 
x₉ = 24+2x₂-3x₃-x₄+x₆ 
x₁₀ = 12+x₁-4x₂+x₄+x₇ 
которые подставим в целевую функцию: 
F(X) = (1+M)x₁+(-2+5M)x₂+(-4+2M)x₃+(2+M)x₄+(3+M)x₅+(-M)x₆+(-M)x₇+(-54M) → max 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 
Решим систему уравнений относительно базисных переменных: 
x₈, x₉, x₁₀, 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,0,0,0,0,18,24,12)

 
Переходим к основному алгоритму  симплекс-метода. 
Итерация №0. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 
и из них выберем наименьшее: 
Следовательно, 3-ая строка является ведущей. 
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

 
 
Получаем новую симплекс-таблицу:

 
Итерация №1. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₄, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i4 
и из них выберем наименьшее: 
Следовательно, 1-ая строка является ведущей. 
Разрешающий элемент равен (1³/₄) и находится на пересечении ведущего столбца и ведущей строки.

 
 
Получаем новую симплекс-таблицу:

 
Итерация №2. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 
и из них выберем наименьшее: 
Следовательно, 2-ая строка является ведущей. 
Разрешающий элемент равен (3²/₇) и находится на пересечении ведущего столбца и ведущей строки.

 
 
Получаем новую симплекс-таблицу: