6. Итерация. Симплекс-метод (алгоритм).

Пусть теперь для базисного плана не выполняется ни условие (4), ни условие существования (среди оценок существуют отрицательные и для всякой отрицательной оценки вектор содержит положительные коэффициенты). Возьмем и построим вектор , используя (7) и (8). Так как с ростом целевая функция увеличивается на величину (смотри (11)), то выберем максимально большим, но так, чтобы оставался планом задачи. С ростом могут лишь нарушиться прямые ограничения для , которые изменяются по формулам (9) или покомпонентно (12):

(9*)

Причём лишь для (при величина ). Поэтому для определения искомого вычислим числа:

(максимально возможное для этого ), и выберем: ,

(13)

Покажем, что при план – новый базисный план. Действительно, положим ; . Тогда

То есть . Убедимся, что векторы – линейно-независимые.

Обозначим через элементы матрицы . Из очевидного равенства: по столбцам получим:

(14)

Выделим из (12): и подставим в (14). Придём к соотношению: . Свернём эти равенства снова в матричное:

(15)

Равенство (15) и доказывает требуемое: матрица и невырожденные (справа в (15) невырожденная матрица) и их столбцы линейно-независимые. Одновременно доказано, что и её элементы определяются по (16).

Описанный переход называется симплекс-итерацией. Последовательное преобразование базисного плана с помощью таких итераций называется симплекс-методом.

7. Конечность. Геометрическая интерпретация.

Определение. Вычислительный метод оптимизации будем называть конечным, если удаётся найти либо точное решение, либо доказать его отсутствие за конечное число операций на ЭВМ.

Определение. Каноническая задача (1), называется невырожденной, если у неё все базисные планы не вырождены ( ).

Теорема 3. Симплекс-алгоритм для невырожденной канонической задачи конечен.

Если задача вырождена, то может оказаться, что на нескольких итерациях подряд (так как могут быть нулевыми) и если на итерациях это случится несколько раз подряд, то возникает опасность возвращения к уже встречавшемуся базисному плану. То есть в методе возможно зацикливание. Это редко встречается на практике, и к тому же разработана специальная модификация симплекс метода Бленда.

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

Геометрически множество планов канонической задачи (1), да и любой линейной представляет из себя некоторое многогранное выпуклое множество в (замкнутое или неограниченное), состоящее из внутренних точек, граней различной размерности, рёбер и угловых точек. Можно доказать, что базисному плану соответствует некоторая угловая точка множества и наоборот.

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