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

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

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

В предыдущем пункте мы видели, что итерация совершается за конечное число операций. Поэтому для конечности метода нужно убедиться в конечном числе итераций.

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

 Доказательство. Пусть у задачи (1) построен начальный базисный план. Из пункта «Алгоритм обратной матрицы», ясно, что для доказательства конечности метода достаточно доказать конечность итераций. Если все базисные планы невырождены, то на каждой итерации .     

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

                                                                                                        Ч.т.д.

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

 

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

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

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

⇐ Предыдущая12

Поделиться: