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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При этом, очевидно, . Если же мы попробуем увеличить на 7, что сохранит равенство в первой строке, то получим нарушение равенства во второй строке (помним, что ):

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

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

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

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

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

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

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

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

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

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

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

Значение функции, соответствующее :

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

Действительно, если в качестве подставить значение 2 из точки оптимума, а в подставить 1, получим 2+1=3.

На этом простом примере мы разобрали работу симплекс-метода и, надеюсь, кому-то стало понятнее, как он устроен. Спасибо за внимание!