Симплекс-метод. Простое объяснение
Причины создания этого учебника
правитьВ интернете опубликовано множество объяснений алгоритма симплекс-метода, про которые можно смело сказать «лучше ничего, чем это». Они написаны крайне заумным языком и доставляют множество страданий всем, кто пытается с их помощью изучить этот метод линейного программирования.
Целью данного учебника является создание простого и доступного описания алгоритма симплекс-метода, которое можно понять, что называется, «с ходу».
Задача линейного программирования
правитьЗадача линейного программирования в стандартной форме заключается в том, чтобы найти экстремум функции
при заданных ограничениях:
Симплекс-таблица
правитьЗапишем симплекс-таблицу:
… | |||||
… | |||||
… | |||||
… | … | … | … | … | … |
… | … | … | … | … | … |
… | |||||
… |
Алгоритм
правитьПервый шаг алгоритма состоит в том, чтобы найти минимальный элемент в последней строке ( ). Номер этого элемента определит разрешающий столбец.
На втором шаге определяется разрешающая строка. Для этого нужно найти симплекс отношение: в каждой строке элемент последнего столбца делится на соответствующий элемент разрешающего столбца. Так получается столбец симплекс-отношений. Минимальный элемент в этом столбце и определяет разрешающую строку.
Приступаем к построению новой симплекс-таблицы. Метки и для разрешающей строки и столбца соответственно меняются местами: обозначает теперь столбец, а — строку. Элемент на пересечении разрешающего столбца и разрешающей строки возводим в степень . Все элементы разрешающей строки, кроме того, что на пересечении, делим на этот элемент на пересечении. Все элементы разрешающего столбца, кроме того, что на пересечении, делим на этот элемент на пересечении и умножаем на .
Остальные элементы новой симплекс таблицы высчитываются по правилу прямоугольника:
……………………………………. <пересч. элемент >
…
<элемент на пересечении > …
новый =
Вышеуказанные операции выполняются для всех элементов, включая , и и повторяются до тех пор, пока в строке будут отрицательные элементы.
Если же отрицательных элементов в строке больше нет, значит, оптимальное решение достигнуто. Оно будет находиться в последнем столбце , его будут обозначать соответствующие метки « » строк.
Подставив найденные в целевую функцию, находим оптимальное решение.