14.Сходимость симплекс-метода Метод искусственного базиса (м-метод)

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

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

будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы. Напомним, чтоF допустимый базисный план канонической задачи ЛП, соответствующий базису β(q), называется вырожденным, если некоторые его базисные компоненты равны нулю, т. е. вектор b(β(q)) содержит нулевые элементы.

Задача ЛП, имеющая вырожденные планы, называется вырожденной. При «выходе» на вырожденный план мы фактически получаем разложение столбца b по системе из меньшего, чем m, количества столбцов аj и, следовательно, лишаемся возможности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуации, в конечном счете, могут привести к зацикливанию вычислительного процесса, т. е. бесконечному перебору одних и тех же базисов.

С точки зрения первой геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи. Иными словами, одно или несколько ограничений в данной точке являются избыточными.

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро конуса, натянутого на систему расширенных векторов текущего базиса. Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего названия метода возмущений: при выходе на вырожденный план осуществляется незначительный сдвиг вектора b и вырожденность (как это видно из иллюстрации) устраняется.

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

Метод искусственного базиса (М-метод)

М-метод применяется для решения любых задач ЛП, в том числе и тех, где начальное базисное решение сразу не определяется. М-метод состоит во введении новых искусственных переменных, которые сразу можно взять в качестве базисных, и дальнейшем решении полученной задачи симплекс-методом.

Исходная ЗЛП в канонической форме: F(X) = c1Х1 + ... + сnXn => max

ai,1X1 + ... + ai,nXn = bi, (i=1,m)

Xj>0 , (j=1,n)

Алгоритм М-метода:

В каждое i-ое ограничение вводим искусственную переменную Xn+i >0. Всего m новых искусственных переменных.

В целевую функцию F вводим m дополнительных отрицательных слагаемых вида :

-M*Xn+1 -M*Xn+2 ...-M*Xn+m , где М - произвольная очень большая константа.

Получим новую ЗЛП вида : F(X) = c1Х1 + ... + сnXn -M*Xn+1 - ... -M*Xn+m => max

ai,1X1+ ... + ai,nXn +Xn+i = bi , (i=1,m)

Xj >0 , (j=1,n+m)

Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных: Xn+i = bi - ai,1X1 - ... - ai,nXn , (i=1,m)

Формируем начальное базисное решение новой М-задачи : X' = ( 0, ... 0, b1, ... bm )

Решаем М-задачу симплекс-методом

Анализируем решение М-задачи в соответствии со следующими правилами :

Если в оптимальном решении М-задачи: X" = ( X"1, ... X"n, X"n+1, ... X"n+m )

все искусственные переменные равны 0, то вектор X" = ( X"1, ... X"n ) является оптимальным решением исходной ЗЛП. Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.

Если М-задача не имеет решения , то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.

Методи відтинання. Метод Гоморі

В основу методів цілочислового програмування покладено ідею Данціга. Допустимо, що необхідно розв’язувати задачу лінійного програмування, всі або частина змінних якої мають бути цілочисловими. Можливо, якщо розв’язувати задачу, не враховуючи умову цілочисловості, випадково одразу буде отримано потрібний розв’язок. Однак така ситуація малоймовірна. Переважно розв’язок не задовольнятиме умову цілочисловості. Тоді накладають додаткове обмеження, яке не виконується для отриманого плану задачі, проте задовольняє будь-який цілочисловий розв’язок. Таке додаткове обмеження називають правильним відтинанням.

Комбінаторні методи. Метод гілок та меж

В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої задачі. Кожен з них характеризується певною послідовністю перебору варіантів та правилами виключення, що дають змогу ще в процесі розв’язування задачі виявити неоптимальні варіанти без попередньої їх перевірки. Відносна ефективність різних методів залежить від того, наскільки кожен з них уможливлює скорочення необхідного процесу перебору варіантів у результаті застосування правила виключення.

Наближені методи. Метод вектора спаду

Розроблення та дослідження наближених алгоритмів є досить перспективним напрямком цілочислової оптимізації. Наближені методи заслуговують на увагу більше з практичного погляду, оскільки, як зазначалося вище, застосування точних методів потребує невиправдано значних витрат часу, тоді як пошук наближеного розв’язку дає змогу суттєво скоротити процес знаходження оптимального плану задачі.