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

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

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

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

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

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

$c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} \to max$

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

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

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

$\dots$

$a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} \leq b_{m}$

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

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

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

Алгоритм

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

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

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

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

$a_{i L}$ ……………………………………. <пересч. элемент $a_{i j}$ >

…

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

$a_{i j}$ новый = $a_{i j} - (a_{i l} * a_{s j}) / (a_{s l})$

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

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

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