![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Симплекс-метод. Анализ процедуры решения задачи линейного программирования (с примером).
Рассмотрим вычислительные и логические процедуры, обеспечивающие поиск решения задачи линейного программирования симплекс-методом. Процедуры поясняются в процессе решения конкретной задачи: найти совокупность значений
и условиям неотрицательности переменных целевая функция z=10+7x1-5/3x2 (3.2) достигает максимума.
Преобразуем заданную форму задачи в каноническую, введя дополнительные переменные
и форму z:
Выберем в качестве свободных (независимых) переменных Выше были приняты значения свободных переменных равными нулю (наименьшими при условии их неотрицательности). Попробуем за счёт их увеличения добиться уменьшения формы z. Из выражения целевой функции видно, что, так как
Соответствующее допустимое базисное решение:
Проведя аналогичные рассуждения, принимая во внимание, что
Теперь свободные неизвестные входят в выражение линейной формы со знаком плюс. Их увеличение может привести только к увеличению формы. Следовательно, базисное решение, являющееся оптимальным, имеет вид:
минимальное значение формы: Таким образом, идея симплекс-метода преобразования модели заключается в таком итеративном направленном переходе от одного допустимого базисного решения к другому, при котором последовательно улучшается значение линейной формы.
|