Решим задачу симплекс- методом

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 11x₁+10x₂ при следующих условиях-ограничений.
7x₁+8x₂≤50
6x₁+3x₂≤35
4x₁+x₂≤17
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅.
7x₁ + 8x₂ + 1x₃ + 0x₄ + 0x₅ = 50
6x₁ + 3x₂ + 0x₃ + 1x₄ + 0x₅ = 35
4x₁ + 1x₂ + 0x₃ + 0x₄ + 1x₅ = 17
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅
Полагая, что свободные переменные равны 0, получим первый опорный план:
X₀ = (0,0,50,35,17)
Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (50: 7, 35: 6, 17: 4) = 4¹/₄
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 1 войдет переменная x₁.
Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₁ записываем нули.
Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

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

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (20¹/₄: 6¹/₄, 9¹/₂: 1¹/₂, 4¹/₄: ¹/₄) = 3⁶/₂₅
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (6¹/₄) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x₃ в план 2 войдет переменная x₂.
Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₃ плана 1 на разрешающий элемент РЭ=6¹/₄. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂записываем нули.
Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

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

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

Оптимальный план можно записать так:
x₁ = 3¹¹/₂₅, x₂ = 3⁶/₂₅
F(X) = 11•3¹¹/₂₅ + 10•3⁶/₂₅ = 70⁶/₂₅