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