Алгоритм симплексного метода

Идея симплексного метода нахождения оптимального решения

Симплексный метод – метод последовательного улучшения решения задачи линейного программирования, то есть задачи оптимизации.

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс–таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.

Идея симплексного метода заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательный направленный переход от одного допустимого решения к другому и так далее – к оптимальному решению. Значение целевой функции для задач на максимум не убывает.

Так как число допустимых решений конечное, то через конечное число шагов получим оптимальное решение. Процесс упорядоченного перебора допустимых решений продолжается до тех пор, пока не найдено оптимальное решение или не установлено, что задача не имеет такого решения.

Математическую модель задачи привести к каноническому виду.

1. Построить начальную симплекс-таблицу. В ней система ограничений должна быть приведена к единичному базису. Подробнее – см. пример.

2. Найти разрешающий столбец (в строке коэффициентов ЦФ найти значение с наименьшим отрицательным числом. Этот столбец и будет разрешающим).

3. Определить разрешающую строку (почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей). Разрешающий элемент будет на пересечении разрешающего столбца и разрешающей строки.

4. Построить вторую симплекс-таблицу.

· Построение элементов разрешающей строки (почленно поделить всю разрешающую строку на разрешающий элемент).

· Построение других строк в новой таблице. Пересчитать каждый элемент в предыдущей таблице по правилу прямоугольника

.

Схематично «правило прямоугольника» выглядит так:

Здесь - пересчитываемый элемент, - новое значение элемента , - разрешающий элемент.

При построении новой таблицы «убирается» из базиса строка с переменной разрешающей строки в предыдущей таблице, а «вводится» в базис строка с названием разрешающего столбца предыдущей таблицы.

Дата добавления: 2014-01-07