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

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

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

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

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

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

$c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\to \text{max}$

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

$a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le b_1$

$a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n\le b_2$

$\cdots$

$a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\le 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$ в целевую функцию, находим оптимальное решение.