SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Метод искусственного базиса. Теорема о разрешимости исходной задачи ЗЛП.


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

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

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

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

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

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

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

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

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

Пусть М-задача имеет оптимальное решение: Yопт=(х1,х2,…хn,0,0,0)

тогда соответствующим решением исходной задачи будет Хопт=(х1,х2,…,хn)

Рассмотрим любое допустимое решение исходной задачи:

векторХ’=(x1’,x2’,…,xn’)

тогда М-задача будет иметь также у=(х1',х2',…,хn’,0,0,0)

Z*(У')Z*(Уопт)

Z*(У’)=Z*(X’)

Но, Z*(векторУопт) совпадает с Z(векторXопт)

Z*(X’)Z(Xопт), что означает, что Xопт — оптимальное решение исходной задачи.