2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)

Из геометрической иллюстрации ЗЛП следует, что она имеет бесконечно много решений, если линия уравнения проходит через сторону прямоугольника (Рис. 14).

Для решения задачи симплексным методом ответ на вопрос: имеет ли задача бесконечно много решений, дает теорема:

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

Следствие: Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки соответствующие свободным переменным положительны, то найденное решение - единственное.

2.10. Признак неограниченности целевой функции

Из геометрической иллюстрации ЗЛП видно, что задача не имеет решений, если область допустимых решений не ограничена (Рис. 15).

Область допустимых решений неограниченна, если область неограниченна сверху для решения задач на max, неограниченна снизу – для задач на min. Ответ на вопрос о неограниченности целевой функции при решении ЗЛП симплексным методом дают следующие теоремы.

Теорема 1: Если в индексной строке последней симплексной таблицы ЗЛП на max содержится отрицательная оценка , а в соответствующем столбце нет ни одного положительного элемента, то целевая функция на множестве допустимых планов неограниченна сверху.

Теорема 2: Если в индексной строке последней симплексной таблицы ЗЛП на min содержится положительная оценка , а в соответствующем столбце переменнойнет ни одного положительного элемента, то на множестве допустимых планов целевая функция неограниченна снизу.

2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание

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

Определение: Каноническую ЗЛП называют невырожденной, если все ее опорные планы невырождены. Если среди опорных планов есть хотя бы один вырожденный, то задачу называют вырожденной.

Пусть ЗЛП решается на максимум. На двух последовательных итерациях значения целевой функции связаны соотношением:

где

Если задача невырожденная, то для любого шага . Отсюда, т. е. значение целевой функции будет не хуже прежнего (монотонно возрастает). Аналогично, если задача решается на минимум, то, поскольку, на любом шаге значения целевой функции на двух последовательных итерациях будут связаны неравенством, т. е. целевая функция монотонно убывает. В этом и состоит монотонность симплексного метода.

Конечность алгоритма следует из конечного числа опорных планов ЗЛП (их не больше).

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

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