Альтернативные оптимальные решения

Альтернативные оптимальные решения

Особенные СЛУЧАИ Внедрения СИМПЛЕКС-МЕТОДА

Вырожденность.

Другие рациональные решения.

Неограниченные решения.

Отсутствие допустимых решений.

1. Вырожденность

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

В вырожденном решении нет никакой угрозы Альтернативные оптимальные решения, кроме маленьких теоретических неудобств. С практической точки зрения вырожденность разъясняется тем, что в начальной задачке находится по последней мере одно лишнее ограничение.

Пример:

На исходной итерации в качестве исключаемой можно избрать как переменную Х3, так и Х4.

Если бросить в базисе переменную Х4, на последующей итерации она воспримет значение Альтернативные оптимальные решения 0 (как показано в таблице), т.е. получим вырожденное базовое решение.

Наилучшее решение выходит на последующей итерации.

Графически представление решения задачки указывает, что точка оптимума Х1= 0, Х2= 2 является скрещением 3-х прямых. Но данная задачка двухмерна, и на плоскости для определения точки довольно 2-ух прямых), и одно из ограничений Альтернативные оптимальные решения сверхизбыточно.

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

С вычислительной точки зрения вырожденность может привести к двум последствиям.

1). Во-1-х, в процессе вычислений может появиться зацикливание.

Если в приведенной Альтернативные оптимальные решения таблице сопоставить первую и вторую итерации, то можно увидеть, что значение мотивированной функции не поменялось: Z = 18. Потому может появиться ситуация, когда некая последовательность будет повторяться, не изменяя значения мотивированной функции и не приводя к окончанию вычислительного процесса.

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

2). Последствие вырожденности решения можно найти, сравнивая две поочередные итерации (1 и 2 итерации в приведенной выше таблице): Хотя в этих итерациях состав базовых и небазисных переменных различен, значения всех переменных и значение мотивированной функции Альтернативные оптимальные решения не меняются:

Х1 = 0, Х2 = 2, Х3 = 0, X4 = 0, Z = 18.

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

Другие рациональные решения

Когда гиперплоскость/(ровная), представляющая мотивированную функцию, параллельна

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

Эти решения именуются другими хорошими решениями.

Таких решений (если они есть) нескончаемое огромное количество.

Пример:

Поочередные итерации выполнения симплекс-метода :

На рис. огромное количество других Альтернативные оптимальные решения хороших решений (точки отрезка ВС) параллельны прямой, соответственной связывающему ограничению. Любая точка отрезка ВС соответствует хорошему решению со значением мотивированной функции Z = 10.

Неограниченные решения

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

Неограниченность решения задачки свидетельствует только об одном: модель разработана не довольно корректно.

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

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

Симплекс-таблица исходной итерации этой задачки имеет последующий вид.

Из таблицы видно, что в качестве вводимой переменной можно взять как X1 так Альтернативные оптимальные решения и Х2,

Но Х1 имеет наибольший (по модулю) отрицательный коэффициент в z-строке, конкретно ее следует ввести в базовое решение.

Но во всех ограничениях коэффициенты, стоящие перед переменной Х2, отрицательны либо равны нулю. Это значит, что значение переменной Х2 может возрастать до бесконечности, и при всем этом не нарушается Альтернативные оптимальные решения ни одно ограничение.

Так как повышение на 1 значения Х2 приводит к повышению на 1 значения Z , то неограниченное повышение значения переменной Х2 приведет к неограниченному повышению значения мотивированной функции.

По графическому решению видно, что место допустимых решений не ограничено в направлении оси Х2, и значение мотивированной функции Z может быть каким угодно Альтернативные оптимальные решения огромным.

Правило выявления неограниченности решения:

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

Не считая того, если коэффициент этой переменной в Z-строке отрицателен, когда рассматривается задачка максимизации, либо положителен в Альтернативные оптимальные решения задачке минимизации, мотивированная функция также не граничена.


amerikanskaya-dramaturgiya-referat.html
amerikanskaya-i-yaponskaya-modeli-menedzhmenta-referat.html
amerikanskaya-korporaciya-issledovaniya-medikamentov.html