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