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

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

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

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

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

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

$c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}\rightarrow {\text{max}}$

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

$a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}\leq b_{1}$

$a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}\leq b_{2}$

$\cdots$

$a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}\leq b_{m}$

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

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

	$x_{1}$	$x_{2}$	…	$x_{n}$
$y_{1}$	$a_{11}$	$a_{12}$	…	$a_{1n}$	$b_{1}$
$y_{2}$	$a_{21}$	$a_{22}$	…	$a_{2n}$	$b_{2}$
…	…	…	…	…	…
…	…	…	…	…	…
$y_{m}$	$a_{m1}$	$a_{m2}$	…	$a_{mn}$	$b_{m}$
	$-c_{1}$	$-c_{2}$	…	$-c_{n}$	$0$

Алгоритм

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

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

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

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

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

…

<элемент на пересечении $a_{s_{l}}$ > … $a_{sj}$

$a_{ij}$ новый = $a_{ij}-(a_{il}*a_{sj})/(a_{sl})$

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

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

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