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

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

Причины создания этого учебника[править]

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

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

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

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

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

Симплекс-таблица[править]

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

Алгоритм[править]

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

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

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

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

……………………………………. <пересч.элемент a_{ij}>

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


новый =

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

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

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