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

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

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

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

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

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

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

Ч.т.д.

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

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

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

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

8. Двухфазный симплекс-метод.

9. Выводы и следствия двухфазного симплекс-метода.

(1)

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

Пусть требуется решить каноническую задачу. Применим к ней двухфазный симплекс-метод. Возможны следующие исходы:

а) , то есть ограничения задачи (1) несовместны, и у неё нет ни одного плана, а значит, нет оптимального плана (случай первой фазы);

б) у задачи будет построен – оптимальный базисный план (случаи 2 и 3 первой фазы и теорема 1 симплекс-метода);

в) будет доказана неограниченность целевой функции (случаи 2 и 3 первой фазы и выполнение теоремы 2 на второй фазе).

Других случаев для задачи (1) быть не может.

Следствие 1. Если у задачи (1) есть планы, то у неё обязательно есть и базисные планы.

Доказательство. Действительно, в этом случае возможен либо случай 2, либо случай 3 на первой фазе и оба они заканчиваются построением базисного плана.

Ч.т.д.

Следствие 2. Если у задачи (1) существует решение, то у неё обязательно будет и оптимальный базисный план.

Доказательство. Действительно, если не выполняется в случаях а) и в) вывода, то остаётся лишь случай б).

Ч.т.д.

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

Доказательство. Необходимость. Если – оптимальный план задачи (1), то целевая функция ограничена сверху числом и множество планов задачи непустое.

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

Ч.т.д.