24. Особые случаи применения симплекс-метода

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

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

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

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

- Неограниченная целевая функция

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

31. Двойственная ЗЛП- это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи. В этом разделе рассмотрены правила построения двойственных задач.

Правила построения-свободной переменной прямой задачи соответствует ограничение в виде равенства двойственной задачи, и, наоборот, ограничению в виде равенства прямой задачи соответствует свободная переменная двойственной задачи.

33. Теорема двойственности

Фундаментальные свойства, которыми обладают двойственные задачи линейного программирования, могут быть сформулированы в виде приводимых ниже утверждений. Их обычно называют теоремами двойственности:

Если х, и— допустимые планы для пары двойственных задач (D,f) и (D*,f*), тo f(x) ≤ f(u).

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

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