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

Предполагается, что есть допустимое базисное решение – x_b x_s (базисные и свободные компоненты этого решения).

Из предыдущего можно отметить, что . Функционал тоже можно разделить на c_b и c_s.

– симплекс разности.

Важные выводы:

1. если все симплес разности £ 0, то значение целевой функции улучшить нельзя, то есть перед нами решение задачи;

2. не базисный столбец a_j имеет смысл вводить в базис, если симплекс разность > 0;

3. можно выбирать наибольшую из положительных симплекс разностей d_j.

Пусть a_r – столбец, который было решено ввести в базис.

из-за того, что остальные из свободных переменных останутся свободными.

.

® l