Про симплекс-метод простым языком / Хабр

В процессе изучения математики часто случается так, что за кучей математических символов, индексов и всяких закорючек теряется смысл происходящего. Конечно, многое зависит от лектора или книги, но, так или иначе, я решил, что будет не лишним разобрать симплекс-метод. Встречается эта штука часто, написано про неё много, написано человеческим языком — несколько меньше. Я постараюсь избегать формальностей, про них можно почитать в любом учебном пособии, и просто объяснить понятным языком, как это работает.

Начнём сначала. Симплекс-метод решает задачу линейного программирования (ЛП). Задача ЛП выглядит следующим образом:

$\begin{aligned}f(x)=&c_1 x_1 + c_2 x_2 \to min \\ & a_{i1}x_{1} + a_{i2}x_{2} \leq b_{i}, \quad i=1\dots m \\ & x_1 \ge 0, \quad x_2 \ge 0 \end{aligned}$

Разумеется, переменных может быть сколько угодно.

Система ограничений задаёт выпуклый полиэдр. Если множество допустимых решений непусто, а целевая функция на нём ограничена, то оптимум достигается хотя бы в одной из вершин. Симплекс-метод направленно перебирает вершины полиэдра, пока не найдет вершину, соответствующую оптимальному решению. Перебор осуществляется с помощью операции смены базиса: одна базисная переменная выходит из базиса, другая входит. Замечание: симплекс не прыгает от одной вершины к другой, как ему вздумается. Переход осуществляется от одной вершины к другой вдоль ребра полиэдра.

Теперь рассмотрим конкретный пример (из задачника Ефимова, Поспелова):

$\begin{aligned}f(x)=&-3x_1 - 2x_2 \to min \\ & x_1+2x_2 \leq 7 \\ & 2x_1 + x_2 \leq 8 \\ & x_2 \leq 3 \\ & x_1 \ge 0 \\ & x_2 \ge 0\end{aligned}$

Это задача в стандартной форме (впрочем, от курса к курсу стандартной формой называются разные вещи). Здесь под стандартной будем понимать, что задача на минимум и каждое ограничение имеет вид неравенства “ $\leq$ ”.

Перед тем как приступить к симплекс-методу, нужно сделать из неравенств равенства. Для этого к каждому неравенству “ $\leq$ ” добавляем вспомогательную переменную (slack):

$\begin{aligned}f(x)=&-3x_1 - 2x_2 \to min \\ & x_1+2x_2 + x_3 = 7 \\ & 2x_1 + x_2 + x_4 = 8 \\ & x_2 + x_5 = 3 \\ & x_1 \ge 0 \\ & x_2 \ge 0 \\ & x_3 \ge 0 \\ & x_4 \ge 0 \\ & x_5 \ge 0\end{aligned}$

Slack переменные обычно интерпретируются как запас некоего ресурса.

Начинаем решать задачу.

Шаг 1. Наша функция стремится к минимуму. Чему-то же она в конечном итоге будет равна, давайте это что-то обозначим как $\normalsize x_0$ . Тогда, можем записать еще одно равенство:

Шаг 2. Нужно выбрать базис. Если записать нашу систему равенств в матричном виде:

то базис – это набор из $\normalsize m$ линейно независимых столбцов матрицы A, где $\normalsize m$ – количество ограничений (без учета ограничений вида $x_i \ge 0$ ).

В нашем случае самый простой способ выбрать начальный базис – составить его из вспомогательных переменных, при этом все остальные переменные равны нулю. С точки зрения экономической интерпретации – это ответ на вопрос, что будет, если мы ничего не будем делать. Геометрически – мы стоим в начале координат нашего полиэдра (точка 0 на картинке ниже).

Шаг 3. Наконец-то можно начать выполнять симплекс.

Составим симплекс-таблицу. В сущности, это та же самая запись системы уравнений, но для собственного удобства и чтоб не потеряться в расчетах, мы добавляем несколько служебных столбцов: итерация, базис, $\normalsize b$ , . Столбец пока оставим незаполненным.

Итерация	Базис	$\large x_1$	$\large x_2$	$\large x_3$	$\large x_4$	$\large x_5$	b
0	$\large x_3$	1	2	1			7
	$\large x_4$	2	1		1		8
	$\large x_5$		1			1	3
	$\large x_0$	3	2				0

Что здесь записано, надеюсь, совершенно очевидно и в пояснении не нуждается. Теперь ответим на вопрос: как самым эффективным способом улучшить целевую функцию? Давайте еще раз посмотрим на неё:

$-3x_1 - 2x_2 \to min.$

Очевидно, самый эффективный способ уменьшить значение функции – это увеличить переменную с наибольшим по модулю отрицательным коэффициентом. Мы переписали целевую функцию в виде равенства и ввели $\normalsize x_0$ исключительно для удобства: во всяком случае, мне кажется, что удобнее искать самый большой положительный коэффициент. Видим, что самый большой коэффициент 3 соответствует $\normalsize x_1$ в последней строке симплекс-таблицы.

Тут остановимся и сделаем два важных замечания: во-первых, мы имеем дело с равенствами, нельзя просто взять и увеличить $\normalsize x_1$ , мы можем увеличить небазисную переменную только за счёт того, что уменьшим другую, базисную переменную; во-вторых, надо увеличить так, чтоб не поломать ограничения.

Для этого мы ищем отношения:

$Q=\{ \frac{b_i}{a_i} \}=\{ \frac{7}{1}; \frac{8}{2} \}$

для $\normalsize a_i$ , соответствующих $\normalsize x_1$ . Эти отношения показывают нам: на сколько максимально можно увеличить значение $\normalsize x_1$ , чтоб сохранялось равенство в соответствующей строке. Из всех $\normalsize Q$ выбираем минимальное, так как если увеличить значение $\normalsize x_1$ на величину больше минимума – обязательно поломается хотя бы одно из ограничений.

Давайте явно это покажем. Если мы увеличиваем $\normalsize x_1$ на 4 (значение $\normalsize Q$ для второй строки), то с нашей системой ограничений всё будет хорошо (подставляем в первое и второе равенство):

$\begin{aligned} & 1 \cdot 4 + x_3 = 7 \\ & 2 \cdot 4 = 8\end{aligned}$

При этом, очевидно, $x_3=3 \ge 0$ . Если же мы попробуем увеличить $\normalsize x_1$ на 7, что сохранит равенство в первой строке, то получим нарушение равенства во второй строке (помним, что $x_4 \ge 0$ ):

$\begin{aligned} & 1 \cdot 7 = 7 \\ & 2 \cdot 7 + x_4 \neq 8\end{aligned}$

Отношения ищутся только для положительных коэффициентов: положительные коэффициенты показывают, что переменная $\normalsize x_i$ при увеличении будет “вытеснять” базисную переменную из соответствующего равенства.

Заполним столбец $\normalsize Q$ симплекс-таблицы:

Итерация	Базис	$\large x_1$	$\large x_2$	$\large x_3$	$\large x_4$	$\large x_5$	b	Q
0	$\large x_3$	1	2	1			7	7/1
	$\large x_4$	2	1		1		8	8/2
	$\large x_5$		1			1	3
	$\large x_0$	3	2				0

Минимум $\normalsize Q$ соответствует второй строке, которая, в свою очередь, соответствует базисной переменной $\normalsize x_4$ . Мы вводим в базис $\normalsize x_1$ за счет $\normalsize x_4$ .

Далее следует обычная процедура Гаусса–Жордана: строка 2 делится на разрешающий коэффициент, т.е. 2, коэффициенты при $\normalsize x_1$ во всех остальных строках делаем равными нулю за счет манипуляций со второй строкой.

Переходим к следующей итерации симплекс-метода, а геометрически приходим в точку 1.

Итерация	Базис	$\large x_1$	$\large x_2$	$\large x_3$	$\large x_4$	$\large x_5$	b	Q
1	$\large x_3$	0	3/2	1	-1/2		3	2
	$\large x_1$	1	1/2		1/2		4	8
	$\large x_5$		1			1	3	3
	$\large x_0$	0	1/2		-3/2		-12

Посмотрим на таблицу и на рисунок. Переменная $\normalsize x_2$ все еще не в базисе, она равна 0. Значение $\normalsize b$ в строке, соответствующей базисной переменной $\normalsize x_1$ , равно 4. Точка и есть координата нашей точки 1. Значение -12 в последней строке соответствует значению целевой функции в этой точке.

Без всяких дальнейших вычислений и таблиц, глядя на график, можно догадаться, что дальше мы пойдем в точку (3,2). А это значит, что наверняка мы введем в базис $\normalsize x_2$ . Глядя на рисунок с изображением антиградиента, легко понять, что следующая итерация будет последней, именно в эту точку упрётся линия уровня.

Но все-таки доделаем симплекс до конца. Тем более, не всегда же задачи двумерные и можно построить рисунок. Находим, что наибольший коэффициент в последней строке таблицы действительно соответствует $\normalsize x_2$ . Найдем $\normalsize Q$ :

$Q=\{\frac{3}{3/2}; \frac{4}{1/2}; \frac{3}{1} \}=\{2;8;3 \}.$

Ещё раз, что мы сейчас сделали: нашли, что значение целевой функции эффективнее всего уменьшить за счет $\normalsize x_2$ (хотя других вариантов и нет), и нашли, на сколько можно выкрутить $\normalsize x_2$ , чтоб не сломать равенства: $\normalsize x_2$ можно увеличить на 2. При этом $\normalsize x_3$ становится равным 0 и выходит из базиса.

Снова применяем метод Гаусса–Жордана: в строке 1 коэффициент при $\normalsize x_2$ делаем равным 1, во всех остальных строках делаем равным 0.

Итерация	Базис	$\large x_1$	$\large x_2$	$\large x_3$	$\large x_4$	$\large x_5$	b
2	$\large x_2$	0	1	2/3	-1/3		2
	$\large x_1$	1	0	-1/3	2/3		3
	$\large x_5$	0	0	-2/3	1/3	1	1
	$\large x_0$	0	0	-1/3	-4/3	0	-13

Вот и всё, все коэффициенты в последней строке меньше либо равны нулю, значит, уменьшить целевую функцию больше нет возможности. Точка, соответствующая оптимуму, найдена:

$x^{*}=(3,2)$

Значение функции, соответствующее $x^{*}$ :

$f(x^{*})=-13.$

Заметим, что в базисе осталась вспомогательная переменная $\normalsize x_5$ и соответствующее ей значение в столбце $\normalsize b=1$ . Теперь посмотрим на ограничение: