Симплексный метод решения задачи линейного программирования
Симплексный метод позволяет по известному базисному решению построить другое базисное решение, для которого значение линейной формы больше, чем для исходного. Для вывода основных соотношений симплексного метода запишем систему уравнений (1.3) в векторной форме
Предположим, что известно какое-нибудь базисное решение системы, в котором m значений
Ненулевые значения
Векторы
Умножим уравнение (1.5) на произвольную положительную константу
или
Величина
Обозначим При Если коэффициенты Пусть не все
Допустим, что минимальное значение
Тогда при данном Поэтому вместо исходного базисного решения получим новое
На основе нового базисного решения (1.7) уравнение (1.6) будет записано в виде
Сравнивая полученное уравнение (1.8) с (1.6), получим, что вектор Таким образом, изложенная процедура позволяет находить при известном базисном решении другое базисное решение, отличающееся от исходного одним базисным вектором. Как же меняется значение критерия оптимальности при переходе от одного базисного решения к другому? Подставим исходное базисное решение в выражение критерия
Число членов под знаком суммы сократилось за счет того, что в исходном базисном решении n членов равно нулю. Для первого базисного решения значение критерия равно
Найдем приращение критерия
Величина
Если же Вопрос о целесообразности перехода к новому базисному решению следует решать проверкой условия (1.9) еще до выбора Читайте также: Cоставляющие линейного температурного перепада по вертикали (метод 1) Рекомендуемые страницы: Читайте также: Почему стероиды повышают давление?: Основных причин три... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ![]() ©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (673)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |