Симплекс-метод решения задачи линейного программирования

Допустимым решением ОЗЛП называют любую совокупность неотрицательных x₁, x₂, ..., x_n, удовлетворяющую исходной системе линейных уравнений.

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

Наиболее универсальным методом решения ОЗЛП является симплекс-метод, основанный на том, что вначале отыскивается произвольное допустимое решение, а затем оно последовательно улучшается до оптимального.

Схема решения ОЗЛП симплекс-методом:

1) составляется симплекс-таблица из коэффициентов системы, представляющая собой расширенную матрицу, дополненную строкой коэффициентов целевой функции, например (N+1)-й, а также нулевыми строкой и столбцом для учета производимых перестановок.

2) выбирается произвольный набор базисных переменных по числу имеющихся в наличии линейных алгебраических уравнений;

3) система разрешается относительно базисных переменных, выражая их через остальные (свободные);

4) свободные переменные приравнивают нулю, получая некоторое решение в виде компонент вектора свободных членов;

5) проверяют решение на допустимость – то есть на отсутствие отрицательных компонент;

6) при наличии отрицательных свободных членов производят последовательную замену базисных переменных на свободные до получения допустимого решения, которое называют опорным.

7) опорное решение является оптимальным, если в строке коэффициентов целевой функции отсутствуют отрицательные элементы, то есть целевая функция не может быть уменьшена за счет увеличения каких-нибудь свободных переменных сверх нуля.