Симплексный метод

Б₂{x₁, x₃, x₅}.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x₁ из второго уравнения и подставим в остальные, в том числе и в функцию.
Имеем:

F = -2 - x₂ + x₄.
Базисное решение, соответствующее базису Б₂{x₁, x₃, x₅}, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F= -2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x₂. Однако, глядя на систему, x₂ можно увеличивать лишь до 1, т. к. иначе из последнего равенства x₅ = 3 - 3x₂ + x₄ следует, что при x₂ > 1 x₅ станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x₂. Поэтому увеличим x₂ до 1, введя его в базис вместо x₅: Б₃{x₁, x₂, x₃}.
Выразим x₂ через x₅ и подставим во все уравнения:




Базисное решение, соответствующее базису Б₃{х₁, х₂,х₃}, выписывается (4, 1, 9, 0, 0), и функция принимает значение F= -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции  , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x₄ = 0, x₅ = 0 значение F= -3. как только x₄, x₅ станут положительными, значение F только увеличится, т. к. коэффициенты при x₄, x₅ положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x₁* = 4, x₂* = 1, x₃* = 9, x₄* = 0, x₅* = 0.
На этом примере очень наглядно продемонстрирована идея метода: постепенно переходя от базиса к базису, при этом всегда обращая внимание на значения целевой функции, которые должны улучшиться, мы приходим к такому базису, в котором значение целевой функции улучшить нельзя, оно оптимально. Заметим, что базисов конечное число, поэтому количество шагов, совершаемых нами до того нужного базиса, конечно.
Задача
Определим максимальное значение целевой функции F(X) = 2x₁+3x₂ при следующих условиях-ограничений.
3x₁+8x₂≤240
4x₁+5x₂≤200
9x₁+4x₂≤4
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅.
3x₁+8x₂+x₃ = 240
4x₁+5x₂+x₄ = 200
9x₁+4x₂+x₅ = 4
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =

3 8 1 0 0 4 5 0 1 0 9 4 0 0 1