Перейти к содержанию

Симплекс-метод. Простое объяснение

Материал из Викиучебника — открытых книг для открытого мира

Причины создания этого учебника

[править]

В интернете опубликовано множество объяснений алгоритма симплекс-метода, про которые можно смело сказать «лучше ничего, чем это». Они написаны крайне заумным языком и доставляют множество страданий всем, кто пытается с их помощью изучить этот метод линейного программирования.

Целью данного учебника является создание простого и доступного описания алгоритма симплекс-метода, которое можно понять, что называется, «с ходу».

Задача линейного программирования

[править]

Задача линейного программирования в стандартной форме заключается в том, чтобы найти экстремум функции

при заданных ограничениях:

Симплекс-таблица

[править]

Запишем симплекс-таблицу:

Алгоритм

[править]

Первый шаг алгоритма состоит в том, чтобы найти минимальный элемент в последней строке (). Номер этого элемента определит разрешающий столбец.

На втором шаге определяется разрешающая строка. Для этого нужно найти симплекс отношение: в каждой строке элемент последнего столбца делится на соответствующий элемент разрешающего столбца. Так получается столбец симплекс-отношений. Минимальный элемент в этом столбце и определяет разрешающую строку.

Приступаем к построению новой симплекс-таблицы. Метки и для разрешающей строки и столбца соответственно меняются местами: обозначает теперь столбец, а  — строку. Элемент на пересечении разрешающего столбца и разрешающей строки возводим в степень . Все элементы разрешающей строки, кроме того, что на пересечении, делим на этот элемент на пересечении. Все элементы разрешающего столбца, кроме того, что на пересечении, делим на этот элемент на пересечении и умножаем на .

Остальные элементы новой симплекс таблицы высчитываются по правилу прямоугольника:

……………………………………. <пересч. элемент >

<элемент на пересечении > …


новый =

Вышеуказанные операции выполняются для всех элементов, включая , и и повторяются до тех пор, пока в строке будут отрицательные элементы.

Если же отрицательных элементов в строке больше нет, значит, оптимальное решение достигнуто. Оно будет находиться в последнем столбце , его будут обозначать соответствующие метки «» строк.

Подставив найденные в целевую функцию, находим оптимальное решение.