Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Табличный симплекс метод.
Идея симплекс метода состоит в последовательном продвижении по базисам опорных планов задачи, т.е. в последовательном улучшении планов задачи по определенному критерию, до тех пор, пока не будет найдено оптимальное решение. Рассмотрим процесс подготовки исходных данных и алгоритм решения задачи ЛП табличным симплекс-методом. Предварительный этап: 1. Привести математическую модель задачи к каноническому виду. 2. Определить начальное допустимое базисное решение задачи. 3. Ввести в исходную симплекс-таблицу параметр оценки по формуле - весовые коэффициенты при базисных переменных. Алгоритм: 1. Заполняется исходная симплекс-таблица. 2. Если все для всех то данный план оптимален. 3. Если имеются и в столбце все элементы то функция не ограничена сверху на ОДР. 4. Если имеются и в столбцах , соответствующих этим отрицательным оценкам, существует хотя бы один элемент , то возможен переход к новому, лучшему плану, связанному с большим значением целевой функции. 5. Вектор , который необходимо ввести в базис для улучшения плана, определяется по наименьшей отрицательной оценке . Столбец, содержащий эту оценку, называется направляющим. 6. Вектор который нужно вывести из базиса, определяется по отношению . Из базиса выводится вектор , на котором достигается минимум . Строка называется направляющей.
Элемент , который стоит на пересечении направляющей строки и направляющего столбца, называется направляющим. 7. Заполняется таблица, соответствующая новому базисному решению. Все элементы таблицы определяются по рекуррентному соотношению:
где l- номер итерации. 8. Процесс вычисления заканчивается, когда найдено оптимальное решение (пункт2) или когда функция будет неограниченной на ОДР (пункт 3).
Пример:
Приведем задачу к каноническому виду:
Построим начальную симплекс таблицу:
Строим новую симплекс-таблицу:
Строим новую симплекс-таблицу:
Строим новую симплекс-таблицу:
Получили оптимальный план: Хопт= (11, 7, 0, 0, 9) Fопт=516
Вопрос для самоподготовки 1. Из каких основных двух моментов состоит симплекс? 2. Как определяется в симплекс методе тот факт, что задача ЛП решения не имеет? 3. В чем состоит идея симплекс метода? 4. Как определить вектор, который выводится из базиса? 5. Как прочитать решение задачи ЛП из последней симплекс таблицы?
ЛЕКЦИЯ 5.
|