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