Метод искусственного базиса. Теорема о разрешимости исходной задачи ЗЛП.
Дает возможность любую каноническую модель ввести в симплексную таблицу без предварителного приведения к единичному базису. Это достигается введением в систему искусственных базисных переменных.
Балансовые переменные — те, которые превращают неравества вуравнения
Искусственные — те, которые вводятся, чтобы образовать базис. Они тогда появляются в целевой функции. Например, 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опт — оптимальное решение исходной задачи.