![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Табличный симплекс метод.
Идея симплекс метода состоит в последовательном продвижении по базисам опорных планов задачи, т.е. в последовательном улучшении планов задачи по определенному критерию, до тех пор, пока не будет найдено оптимальное решение. Рассмотрим процесс подготовки исходных данных и алгоритм решения задачи ЛП табличным симплекс-методом. Предварительный этап: 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.
|