SHPORA.net :: PDA

[ Back ]

Дает возможность любую каноническую модель ввести в симплексную таблицу без предварителного приведения к единичному базису. Это достигается введением в систему искусственных базисных переменных.

Балансовые переменные — те, которые превращают неравества вуравнения

Искусственные — те, которые вводятся, чтобы образовать базис. Они тогда появляются в целевой функции. Например, Z*= x1+5x2+3x3-M(x6+x7), где М сколь угодно большое положительное число.

Ключевая теорема М-метода.

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

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

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

Теоремы о неразрешимости исходной задачи ЗЛП.

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

Уопт=(1,2,n+1…,n+m)

ПУстьn+1 — искомая переменная не равная 0.

Предположим, что задача вопреки теореме имеет оптимальное решение.

Хопт=(х1,х2,…,хn), тогда существует У’опт (х1,х2,..,хn,0,0,0).

Cравним значения функции Z при Хопт и Уопт

Z*(Yопт) – Z(Y’опт)=Ск(к-Хк) - Мn+i.

Так как М- сколь угодно большое число, то его можно выбрать так, чтобы Z*(Уопт) – Z*(У’опт) оказалось меньше 0. Сл-но

Z*(Уопт)<Z*(У’опт), сл-но задача не может иметь допустимых решений.



Система уравнений М-задачи всегда совместна — имеет исходное опорное решение. предположим, что исходная задача разрешима и имеет исходное опорное решение и М-задача имеет соответствующее решение.

Хопт=(х1,х2,…,хn). Уопт’=(x1,x2,…,xn,0,0,0)

Тогда в М-задаче: Уопт=(х1,х2,…,хn,0,0,0)

При этом Z*(векторУ)<Z*(векторУопт)=Z(Xопт).

Таким образом Хопт существует, а значение Z(Хопт)— число.

Z*(ВекторУ)<Z(векторХопт).

Но Z(векторУ) стремится к бесконечности, сл-но, неравенство противоречивое (не имеет смысла), поэтому исходная задача не имеет решения.