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