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

Когда число переменных больше двух, то графический метод не работает, и переходят к другим аналитическим методам решения. Одним из основных аналитических методов решения задач линейного программирования является симплекс метод. Свое название он получил от латинского слова “простой”. Теория и алгоритм симплекс метода строятся для канонической формы задач линейного программирования.

Как вытекает из графического метода решения задачи линейного программирования, оптимальное решение находится среди крайних точек (вершин) многоугольника допустимых решений. В общем случае, когда число переменных больше двух ограничения задают некоторую многогранную область. Известно, что экстремум (решение задачи линейного программирования) линейная функция достигает среди крайних точек этого многогранника. Это решение можно найти путем перебора всех этих крайних точек. Однако из-за большого числа вычислений такой путь практически невозможен.

В симплекс методе используется целенаправленный перебор, когда переход от одной вершины в соседнюю происходит в направлении скорейшего возрастания целевой функции, поэтому при решении задачи линейного программирования симплекс методом выделяются следующие три этапа:

отыскание какой-либо крайней точки;

проверка оптимальности;

указание процедуры целенаправленного перехода к следующей крайней точке.

В этом состоит эвалистическое обоснование симплекс метода.

Рассмотрим основные понятия симплекс метода. Пусть задача линейного программирования задана в канонической форме: (1) при ограничениях Ax=b (2), . Здесь матрица представляет собой набор векторов условий.

План задачи линейного программирования – вектор, удовлетворяющий ограничениям (2).

Базисный план - план векторы условий , соответствующие ненулевым компонентам, которого являются линейно независимыми.

Невырожденный базисный план – базисный план, содержащий ровно m ненулевых компонентов.

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

25

Первый этап: построение первоначального базисного плана.

Пусть задача линейного программирования задана в канонической форме, причем среди векторов условий найдутся m линейно независимых единичных векторов, образующих единичный базис. Соответствующие им компоненты вектора x – базисные компоненты, а оставшиеся – свободные компоненты. И пусть вектор . Неограничивая общности, будем считать, что единичными базисными векторами будут первые m векторов. Тогда задача линейного программирования примет следующий вид:

(3)

(4)

Другими словами матрица условий имеет вид:

Полагая, что в системе (4) мы получим что , и первоначальный базис угла будет . Если же задача задана в нормальной форме, то всегда легко найти первоначальный базисный план.

25

Второй этап: проверка (критерий) оптимальности.

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

- базисный план.

Тогда справедливо следующее утверждение:

,

где - оценка вектора ;

- координаты разложения вектора по единичному базису .

Таким образом, анализируя формулу (1) возможны следующие три случая:

все оценки (в этом случае базисный план оптимальный);

для некоторого отрицательного все соответствующие индексу j не положительны (в этом случае задача неразрешима);

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

25