🔴 Сложный ⏱️ 55 минут

Симплекс-метод

📋 Содержание урока

Симплекс-метод 🔺

В прошлом уроке ты доказал (точнее, увидел на конкретных примерах и понял через геометрию) ключевой факт: если задача линейного программирования вообще имеет решение, то оптимум обязательно достигается в одной из вершин допустимого многогранника. Это радикально сужает поиск — вместо того чтобы перебирать бесконечное множество точек внутри допустимой области, достаточно проверить конечный набор вершин. Кажется, что задача решена: посчитай значение целевой функции в каждой вершине, выбери максимум, готово.

Проблема в том, что «конечный набор» и «маленький набор» — это разные вещи. Для задачи с $n$ переменными и $m$ ограничениями число вершин-кандидатов растёт как биномиальный коэффициент $\binom{n+m}{m}$, и уже при паре сотен переменных и ограничений (совершенно нормальный размер для реальной задачи распределения ресурсов, логистики или обучения модели с линейными ограничениями) это число исчисляется десятками и сотнями цифр. Перебрать их напрямую не успеет ни один компьютер, который когда-либо будет построен.

Симплекс-метод — это ответ на вопрос: как эффективно найти оптимальную вершину, не проверяя их все? Идея обманчиво простая: стартуй в какой-нибудь одной допустимой вершине, а дальше на каждом шаге переходи не в произвольную, а в соседнюю вершину — такую, которая связана с текущей ребром многогранника, — причём переходи только тогда, когда это улучшает (или хотя бы не ухудшает) значение целевой функции. Останавливайся, когда ни одна из соседних вершин уже не даёт улучшения. Эта простая на вид стратегия — по сути жадный локальный поиск по графу вершин многогранника — оказывается не просто работающей, а работающей почти всегда быстро, несмотря на то что теоретически число шагов может оказаться экспоненциальным.

Именно поэтому симплекс-метод — это не просто исторический курьёз, а один из самых влиятельных алгоритмов XX века и прекрасный учебный пример того, как выглядит эффективный алгоритм на экспоненциально большом пространстве кандидатов. Он лежит в основе промышленных решателей линейных программ, встречается внутри библиотек вроде scipy.optimize.linprog, а понимание его механики — прямой путь к пониманию двойственности, теневых цен и чувствительности решений, о которых пойдёт речь в следующем уроке.

История

В 1947 году американский математик Джордж Данциг работал в Пентагоне над задачами планирования снабжения армии США — как распределить ограниченные ресурсы (топливо, боеприпасы, личный состав) между конкурирующими военными задачами наилучшим образом. Военные аналитики того времени решали подобные задачи вручную, с помощью таблиц и интуиции, и результат сильно зависел от опыта конкретного планировщика. Данциг предложил формализовать задачу как линейную программу — максимизацию или минимизацию линейной функции при линейных ограничениях — и придумал систематический алгоритм для её решения, который назвал симплекс-методом (название происходит от геометрического термина «симплекс» — простейший многогранник вроде треугольника или тетраэдра, хотя сам алгоритм работает с куда более общими многогранниками).

Первая версия алгоритма была представлена летом 1947 года на встрече с группой математиков и экономистов, включая будущих нобелевских лауреатов по экономике. Реакция была неоднозначной: часть аудитории сомневалась, что метод вообще будет практичен для задач сколько-нибудь реального размера — интуиция подсказывала, что число вершин многогранника растёт слишком быстро. Данциг и его коллеги начали тестировать метод на реальных задачах планирования — сначала совсем небольших, на несколько переменных, решаемых вручную за часы, — и обнаружили, что алгоритм сходится к оптимуму за считаные десятки шагов даже там, где теоретическое число вершин исчислялось миллионами. Это расхождение между «страшной» теорией худшего случая и «дружелюбной» практикой преследует симплекс-метод до сих пор и остаётся одной из интереснейших открытых тем в теории алгоритмов.

К 1950-м годам симплекс-метод стал стандартным инструментом зарождающейся дисциплины «исследование операций» (operations research): авиакомпании использовали его для планирования расписаний экипажей, нефтяные компании — для оптимизации смешивания топлива, промышленные предприятия — для распределения ресурсов производства. Сегодня, спустя почти восемьдесят лет, вариации симплекс-метода (например, метод пересмотренного симплекса, revised simplex, экономный по памяти вариант для разреженных задач) остаются одним из двух основных семейств алгоритмов для линейного программирования — наряду с методами внутренней точки, которые появились на сорок лет позже и о которых мы вкратце поговорим в конце урока.

Идея: как перейти от одной вершины к другой, не перебирая все

Интуиция

Представь допустимую область задачи линейного программирования как многогранный камень, поставленный на стол, — с плоскими гранями, рёбрами и вершинами. Целевую функцию представь как высоту над определённым направлением — скажем, ты наклонил лампу так, что каждая точка камня отбрасывает тень определённой длины, и чем больше значение целевой функции в точке, тем длиннее тень. Задача — найти вершину с самой длинной тенью.

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

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

Алгоритм

Общая схема симплекс-метода. Начни в любой допустимой вершине многогранника (для задачи в стандартной форме с ограничениями вида «$\le$» и неотрицательными переменными такой вершиной почти всегда служит начало координат). На каждом шаге проверь все вершины, соседние с текущей по рёбрам многогранника. Если среди них нет ни одной с большим значением целевой функции (для задачи максимизации), останови алгоритм — текущая вершина оптимальна. Если такая вершина есть, перейди в неё (если подходящих соседей несколько, выбери по фиксированному правилу, например с наибольшим приростом на единицу перехода) и повтори проверку заново.

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

Примеры

Пример 1: столярная мастерская. Небольшая мастерская выпускает два вида продукции — назовём их изделие A ($x_1$ штук в день) и изделие B ($x_2$ штук в день). Есть три ограничения производства: станок для изделия A может обработать не больше 4 единиц в день ($x_1 \le 4$), станок для изделия B — не больше 6 единиц ($2x_2 \le 12$, то есть $x_2 \le 6$), а на общую обработку обоих изделий уходит совместный ресурс времени: $3x_1 + 2x_2 \le 18$. Прибыль с одного изделия A — 3 условные единицы, с изделия B — 5 условных единиц. Требуется максимизировать $Z = 3x_1 + 5x_2$.

Допустимая область — пятиугольник с вершинами $(0,0)$, $(4,0)$, $(4,3)$, $(2,6)$, $(0,6)$ (последние две находятся на пересечении линий $x_2=6$ и $3x_1+2x_2=18$, а также $x_1=4$ и $3x_1+2x_2=18$ соответственно). Значения целевой функции в вершинах: $Z(0,0)=0$, $Z(4,0)=12$, $Z(4,3)=27$, $Z(2,6)=36$, $Z(0,6)=30$. Максимум — в вершине $(2,6)$ со значением $36$.

Симплекс-метод стартует в $(0,0)$ (естественная стартовая точка, поскольку все ограничения там выполняются с запасом). У неё два соседа по рёбрам многогранника: $(4,0)$ и $(0,6)$. Переход в $(4,0)$ даёт $Z=12$, переход в $(0,6)$ даёт $Z=30$ — метод выбирает более выгодное направление и переходит в $(0,6)$. У вершины $(0,6)$ соседи — $(0,0)$ (уже пройдена, возврат бессмыслен) и $(2,6)$ с $Z=36$. Метод переходит в $(2,6)$. У вершины $(2,6)$ соседи — $(0,6)$ (хуже, $Z=30$) и $(4,3)$ (хуже, $Z=27$). Улучшения нет — алгоритм останавливается, оптимум найден за два перехода.

Итого: из пяти вершин многогранника симплекс-метод посетил только три — $(0,0)$, $(0,6)$, $(2,6)$, — пропустив $(4,0)$ и $(4,3)$ вообще. Для пятиугольника разница между «проверить все 5» и «проверить 3» кажется незначительной, но идея масштабируется: чем больше переменных и ограничений, тем разительнее становится этот разрыв.

Пример 2: рост числа кандидатов в вершины. Число базисных решений (потенциальных вершин-кандидатов, включая недопустимые) для задачи с $n$ переменными и $m$ ограничениями равно биномиальному коэффициенту $\binom{n+m}{m}$ — это число способов выбрать, какие $m$ переменных из $n+m$ (исходные плюс добавочные, о которых пойдёт речь в следующем разделе) объявить «базисными», то есть потенциально ненулевыми в данной вершине. В примере 1 у нас было $n=2$ переменные и $m=3$ ограничения, всего $5$ переменных с учётом добавочных, и $\binom{5}{3}=10$ кандидатов в вершины (из которых реально допустимыми оказались только 5 — некоторые комбинации дают точки вне допустимой области или с отрицательными координатами).

Возьми задачу побольше: $n=10$ переменных, $m=10$ ограничений. Тогда $\binom{20}{10} = 184\,756$ кандидатов. При $n=m=50$ число кандидатов $\binom{100}{50}$ — это число из 29 цифр, больше, чем оценочное число атомов в человеческом теле. При этом реальные промышленные задачи линейного программирования нередко содержат тысячи и десятки тысяч переменных и ограничений. Перебор такого множества кандидатов невозможен физически, а симплекс-метод на практике решает подобные задачи за число шагов порядка нескольких сотен — то есть буквально в миллионы раз меньше, чем размер множества кандидатов.

Пример 3: граф вершин и рёбер. Формализуем «соседство» вершин из примера 1 как граф: вершины — узлы, рёбра многогранника — рёбра графа. Для нашего пятиугольника граф выглядит так: $(0,0)$ соединена с $(4,0)$ и $(0,6)$; $(4,0)$ соединена с $(0,0)$ и $(4,3)$; $(4,3)$ соединена с $(4,0)$ и $(2,6)$; $(2,6)$ соединена с $(4,3)$ и $(0,6)$; $(0,6)$ соединена с $(2,6)$ и $(0,0)$ — замкнутый цикл, как и положено многоугольнику на плоскости. Путь, пройденный симплекс-методом в примере 1 — $(0,0) \to (0,6) \to (2,6)$ — это путь длины 2 в этом графе, тогда как альтернативный путь $(0,0) \to (4,0) \to (4,3) \to (2,6)$ имел бы длину 3 и, что важнее, включал бы шаг к $(4,0)$, где значение целевой функции $Z=12$ меньше, чем в $(0,0)+$улучшение по другому ребру — такой шаг никогда не будет выбран, поскольку на каждом шаге метод сравнивает прирост по каждому доступному ребру и выбирает направление с наибольшим приростом.

В многомерном случае у каждой вершины многогранника, определённого $n$ переменными, обычно ровно $n$ соседей (по одному на каждое «направление», в котором можно сдвинуться, оставаясь на границе допустимой области) — и именно по этим $n$ направлениям на каждом шаге и происходит проверка, какая из них лучше, что мы дальше и переведём на язык вычислений.

Почему это важно

Идея локального перехода по графу вершин — это не техническая деталь, а фундаментальный сдвиг в том, как вообще думать об алгоритмах на экспоненциально больших пространствах кандидатов. Это ровно тот же принцип, который заставляет работать жадное построение дерева решений (выбор локально наилучшего разбиения на каждом узле вместо перебора всех возможных деревьев), локальный поиск в комбинаторной оптимизации и даже — в несколько ином виде — стохастический градиентный спуск, который тоже двигается локально, шаг за шагом, вместо того чтобы проверять все точки пространства параметров разом. Понимание того, почему локальные жадные шаги в задаче линейного программирования гарантированно приводят к глобальному оптимуму (а не просто к «неплохому» результату, как в случае деревьев решений) — это прямое следствие выпуклости многогранника, доказанной в прошлых уроках, и оно объясняет, почему именно для линейного программирования такая гарантия вообще возможна.

Симплекс-таблица и ведущий элемент

Интуиция

Геометрическая картина «ходи по вершинам многогранника» прекрасна для интуиции и совершенно бесполезна для вычислений в пространстве, скажем, из сорока переменных — там нет рисунка, который можно было бы разглядывать. Нужен способ представить вершину, соседство и «улучшение по ребру» на языке чисел и элементарных операций над ними, которые можно закодировать и выполнять миллионы раз в секунду. Этот способ — симплекс-таблица.

Первый шаг — привести задачу к стандартной форме, превратив все неравенства в равенства. Для ограничения вида $a_1x_1+\dots+a_nx_n \le b$ это делается добавлением новой, добавочной переменной $s \ge 0$ (её называют slack-переменной, «переменной запаса»): $a_1x_1+\dots+a_nx_n+s=b$. Смысл простой: $s$ — это то, насколько ограничение выполняется «с запасом». Если $s=0$, ограничение выполняется впритык (точка лежит на границе многогранника), если $s>0$ — с запасом (точка строго внутри по этому конкретному ограничению).

После добавления добавочных переменных у нас есть система линейных уравнений с числом переменных $n+m$ (исходные плюс добавочные) и числом уравнений $m$. У такой системы бесконечно много решений — но нас интересуют не любые, а базисные решения: те, где ровно $m$ переменных ненулевые (их называют базисными), а остальные $n$ переменных равны нулю (небазисные). Каждое такое базисное решение с неотрицательными значениями всех переменных — это в точности вершина многогранника из предыдущего раздела. Начальная вершина $(0,0,\dots,0)$ (все исходные переменные нулевые) соответствует базису из одних добавочных переменных — это тот самый естественный старт, о котором шла речь выше.

Алгоритм

Правило выбора входящей и выходящей переменной (правило Данцига). Запиши систему ограничений и строку целевой функции в виде таблицы: строки — текущие базисные переменные, столбцы — все переменные задачи (исходные и добавочные) плюс столбец свободных членов (RHS). В нижней строке (строке целевой функции, записанной как $Z - c_1x_1 - \dots - c_nx_n = 0$) найди наиболее отрицательный коэффициент — соответствующий столбец становится входящей переменной (той, что войдёт в базис). Если отрицательных коэффициентов нет, текущее базисное решение оптимально — останови алгоритм. Иначе для входящего столбца вычисли отношение свободного члена к коэффициенту в каждой строке, где этот коэффициент строго положителен (отношения с нулевым или отрицательным коэффициентом в расчёт не берутся); строка с наименьшим таким отношением — выходящая (переменная, соответствующая этой строке, покидает базис). Элемент на пересечении входящего столбца и выходящей строки — ведущий элемент (pivot). Выполни исключение Гаусса вокруг ведущего элемента: раздели всю выходящую строку на значение ведущего элемента, а затем вычти подходящее кратное новой строки из всех остальных строк (включая строку целевой функции), чтобы обнулить весь остальной входящий столбец. Повтори проверку заново.

Правило минимального отношения — не произвольная деталь, а гарантия того, что после пересчёта все свободные члены (значения базисных переменных) останутся неотрицательными, то есть новое решение по-прежнему будет допустимой вершиной, а не выходом за пределы многогранника.

Примеры

Пример 1: приведение мастерской к стандартной форме и построение начальной таблицы. Вернёмся к задаче из примера 1 предыдущего раздела: максимизировать $Z=3x_1+5x_2$ при $x_1\le4$, $2x_2\le12$, $3x_1+2x_2\le18$, $x_1,x_2\ge0$. Вводим добавочные переменные $s_1,s_2,s_3\ge0$:

$$x_1+s_1=4,\qquad 2x_2+s_2=12,\qquad 3x_1+2x_2+s_3=18$$

Строку целевой функции записываем как $Z-3x_1-5x_2=0$. Начальная симплекс-таблица (базис — $s_1,s_2,s_3$, что соответствует вершине $x_1=x_2=0$):

Базис     x1     x2     s1     s2     s3   | RHS
s1         1      0      1      0      0   |  4
s2         0      2      0      1      0   |  12
s3         3      2      0      0      1   |  18
Z         -3     -5      0      0      0   |  0

Эта таблица — точное алгебраическое отражение вершины $(0,0)$ из геометрического примера: базисные переменные $s_1=4$, $s_2=12$, $s_3=18$ (справа), а $x_1=x_2=0$ (небазисные).

Пример 2: первый выбор входящей и выходящей переменной. В строке $Z$ два отрицательных коэффициента: $-3$ у $x_1$ и $-5$ у $x_2$. Наиболее отрицательный — $-5$, значит входящая переменная — $x_2$, столбец $x_2$. Теперь тест отношений по столбцу $x_2$: в строке $s_1$ коэффициент при $x_2$ равен $0$ — эта строка не участвует в тесте (деление на ноль не определено, и вдобавок нулевой коэффициент означает, что увеличение $x_2$ вообще не влияет на $s_1$, значит и ограничивать рост $x_2$ эта строка не может). В строке $s_2$ коэффициент $2$, отношение $12/2=6$. В строке $s_3$ коэффициент $2$, отношение $18/2=9$. Минимальное отношение — $6$, у строки $s_2$: значит выходящая переменная — $s_2$, а ведущий элемент — число $2$ на пересечении столбца $x_2$ и строки $s_2$.

Геометрический смысл этого шага в точности совпадает с примером 1 предыдущего раздела: рост $x_2$ при $x_1=0$ означает движение вдоль ребра многогранника от $(0,0)$ вверх, и первое ограничение, которое «упирается» в эту прямую, — это как раз ограничение $2x_2\le12$ (при $x_2=6$ ресурс $s_2$ исчерпывается ровно до нуля), а не ограничение $3x_1+2x_2\le18$, которое на этом же направлении исчерпалось бы только при $x_2=9$ — то есть позже. Минимальное отношение алгебраически находит именно ту границу, до которой геометрически можно безопасно двигаться, не выходя из многогранника.

Пример 3: почему нельзя выбрать неминимальное отношение. Проверим, что случится, если по ошибке выбрать строку $s_3$ (отношение $9$) вместо правильной строки $s_2$ (отношение $6$) в качестве выходящей. Ведущий элемент — коэффициент $2$ в строке $s_3$. Делим строку $s_3$ на $2$: получаем $1{,}5,\ 1,\ 0,\ 0,\ 0{,}5\ |\ 9$. Пересчитываем строку $s_2$, вычитая $2$ раза новую строку $s_3$ (чтобы обнулить коэффициент при $x_2$ в строке $s_2$, который равен $2$): $s_2^{\text{новая}} = (0,2,0,1,0\mid12) - 2\cdot(1{,}5,1,0,0,0{,}5\mid9) = (-3,0,0,1,-1\mid-6)$.

Свободный член новой строки $s_2$ равен $-6$ — отрицателен. Это означает, что если бы мы выбрали неправильную выходящую строку, следующее «базисное решение» имело бы отрицательное значение переменной $s_2$, то есть точку вне допустимой области (нарушающую ограничение $2x_2\le12$). Правило минимального отношения существует ровно для того, чтобы этого никогда не происходило: оно гарантированно выбирает то ограничение, которое становится тесным первым при движении вдоль выбранного направления.

Почему это важно

Симплекс-таблица — это в буквальном смысле алгоритм, который выполняет компьютер: scipy.optimize.linprog с методом 'simplex' (в старых версиях) или 'revised simplex', коммерческие решатели вроде CPLEX и Gurobi (в одном из режимов работы), и даже надстройка «Поиск решения» в Excel — все они на определённом уровне абстракции делают то же самое: строят таблицу, выбирают входящую и выходящую переменные, выполняют исключение Гаусса и повторяют, пока строка целевой функции не перестанет содержать отрицательных коэффициентов. Понимание этой механики — не упражнение в бумажной арифметике, а прямой доступ к тому, что происходит «под капотом» у любого инструмента линейного программирования, которым ты когда-либо воспользуешься в реальном ML- или дата-инженерном проекте.

Полная пошаговая трассировка симплекс-метода

Пример 1: завершаем задачу о мастерской от старта до оптимума

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

Базис     x1     x2     s1     s2     s3   | RHS
s1         1      0      1      0      0   |  4
x2         0      1      0     0.5     0   |  6
s3         3      0      0     -1      1   |  6
Z         -3      0      0     2.5     0   |  30

Проверим арифметику этого шага. Строка $s_1$ имела коэффициент $0$ при $x_2$, поэтому не изменилась. Новая строка $x_2$ — это старая строка $s_2$, делённая на $2$: $(0,1,0,0{,}5,0\mid6)$. Новая строка $s_3$ получена вычитанием $2$ раз новой строки $x_2$ из старой строки $s_3$: $(3,2,0,0,1\mid18) - 2\cdot(0,1,0,0{,}5,0\mid6) = (3,0,0,-1,1\mid6)$. Новая строка $Z$ получена прибавлением $5$ раз новой строки $x_2$ к старой строке $Z$ (поскольку коэффициент при $x_2$ был $-5$, нужно прибавить $5$ строк, чтобы обнулить его): $(-3,-5,0,0,0\mid0) + 5\cdot(0,1,0,0{,}5,0\mid6) = (-3,0,0,2{,}5,0\mid30)$.

Текущее базисное решение: $x_2=6$, $s_1=4$, $s_3=6$, а $x_1=s_2=0$ — это в точности вершина $(0,6)$ из геометрического разбора, со значением $Z=30$. В строке $Z$ остался один отрицательный коэффициент — $-3$ у $x_1$, значит алгоритм ещё не закончен. Входящая переменная — $x_1$.

Тест отношений по столбцу $x_1$: строка $s_1$ — коэффициент $1$, отношение $4/1=4$. Строка $x_2$ — коэффициент $0$, не участвует в тесте. Строка $s_3$ — коэффициент $3$, отношение $6/3=2$. Минимальное отношение — $2$ у строки $s_3$: выходящая переменная — $s_3$, ведущий элемент — $3$.

Делим строку $s_3$ на $3$: $(1,0,0,-1/3,1/3\mid2)$. Пересчитываем остальные строки. Строка $s_1$ (коэффициент при $x_1$ был $1$): $(1,0,1,0,0\mid4) - 1\cdot(1,0,0,-1/3,1/3\mid2) = (0,0,1,1/3,-1/3\mid2)$. Строка $x_2$ не меняется (коэффициент при $x_1$ был $0$). Строка $Z$ (коэффициент был $-3$, прибавляем $3$ раза новую строку): $(-3,0,0,2{,}5,0\mid30) + 3\cdot(1,0,0,-1/3,1/3\mid2) = (0,0,0,1{,}5,1\mid36)$.

Финальная таблица:

Базис     x1     x2     s1      s2      s3   | RHS
s1         0      0      1     1/3    -1/3   |  2
x2         0      1      0     0.5      0    |  6
x1         1      0      0    -1/3     1/3   |  2
Z          0      0      0     1.5      1    |  36

В строке $Z$ отрицательных коэффициентов больше нет ($1{,}5$ и $1$ у небазисных $s_2$ и $s_3$ — оба неотрицательны) — алгоритм останавливается. Оптимум: $x_1=2$, $x_2=6$, $Z=36$ — то же самое решение, что было найдено геометрическим перебором вершин в предыдущем разделе, но теперь получено чисто алгебраически, за два пересчёта таблицы (пивота), без единого взгляда на график.

Пример 2: вторая полная трассировка, три переменные

Небольшое производство выпускает три продукта с объёмами $x_1,x_2,x_3$ (в условных единицах в день) и прибылью на единицу $2,3,1$ соответственно: максимизировать $Z=2x_1+3x_2+x_3$ при ограничениях $x_1+x_2+x_3\le10$ (общий ресурс сырья), $2x_1+x_2\le12$ (ресурс первого станка, не используемый третьим продуктом), $x_3\le5$ (ограничение спроса на третий продукт), $x_1,x_2,x_3\ge0$.

Стандартная форма с добавочными $s_1,s_2,s_3$ и начальная таблица (базис $s_1,s_2,s_3$, вершина $x_1=x_2=x_3=0$):

Базис     x1     x2     x3     s1     s2     s3   | RHS
s1         1      1      1      1      0      0   |  10
s2         2      1      0      0      1      0   |  12
s3         0      0      1      0      0      1   |  5
Z         -2     -3     -1      0      0      0   |  0

Наиболее отрицательный коэффициент строки $Z$ — $-3$ у $x_2$: входящая переменная $x_2$. Тест отношений: строка $s_1$ — $10/1=10$; строка $s_2$ — $12/1=12$; строка $s_3$ — коэффициент при $x_2$ равен $0$, не участвует. Минимум — $10$ у строки $s_1$: выходящая переменная $s_1$, ведущий элемент — $1$ (пересчёт особенно простой, поскольку ведущий элемент уже равен единице).

Строка $s_1$ становится строкой $x_2$ без изменений: $(1,1,1,1,0,0\mid10)$. Строка $s_2$ (коэффициент при $x_2$ был $1$): $(2,1,0,0,1,0\mid12)-(1,1,1,1,0,0\mid10)=(1,0,-1,-1,1,0\mid2)$. Строка $s_3$ не меняется (коэффициент при $x_2$ был $0$): $(0,0,1,0,0,1\mid5)$. Строка $Z$ (коэффициент был $-3$, прибавляем $3$ раза новую строку): $(-2,-3,-1,0,0,0\mid0)+3\cdot(1,1,1,1,0,0\mid10)=(1,0,2,3,0,0\mid30)$.

Финальная таблица (уже после одного пересчёта):

Базис     x1     x2     x3     s1     s2     s3   | RHS
x2         1      1      1      1      0      0   |  10
s2         1      0     -1     -1      1      0   |  2
s3         0      0      1      0      0      1   |  5
Z          1      0      2      3      0      0   |  30

В строке $Z$ отрицательных коэффициентов нет ($1$, $2$, $3$ — все неотрицательны у небазисных $x_1$, $x_3$, $s_1$) — алгоритм останавливается уже после единственного пересчёта. Оптимум: $x_2=10$, $x_1=x_3=0$, $Z=30$. Проверка напрямую: при $x_1=0$ ограничение сырья превращается в $x_2+x_3\le10$, а поскольку прибыль от $x_2$ (коэффициент $3$) выше, чем от $x_3$ (коэффициент $1$), при фиксированном суммарном ресурсе выгоднее весь ресурс отдать под $x_2$ — ровно то, что и выдал алгоритм, всего за одну итерацию, потому что первый же выбор входящей переменной ($x_2$, с самым выгодным коэффициентом прибыли) сразу оказался верным направлением до конца.

Пример 3: что означают коэффициенты $1{,}5$ и $1$ в финальной строке $Z$ примера 1

Вернёмся к финальной таблице примера 1 (задача о мастерской). В строке $Z$ под столбцами $s_2$ и $s_3$ стоят числа $1{,}5$ и $1$. Это не случайные остатки вычислений — это теневые цены (shadow prices) соответствующих ограничений: значение, на которое вырастет оптимальная прибыль $Z$, если увеличить правую часть соответствующего ограничения на одну единицу. Коэффициент $1{,}5$ под $s_2$ означает: если бы ресурс второго ограничения ($2x_2\le12$) был на единицу больше (то есть $2x_2\le13$), оптимальная прибыль выросла бы на $1{,}5$. Коэффициент $1$ под $s_3$ означает то же самое для третьего ограничения ($3x_1+2x_2\le18$): дополнительная единица этого ресурса стоит ровно $1$ единицу прибыли. У столбца $s_1$ (первое ограничение, $x_1\le4$) коэффициент в финальной строке $Z$ равен $0$ — это не опечатка: ограничение $s_1=2>0$ в оптимальном решении выполняется не впритык, у станка для изделия A остаётся неиспользованный запас, а значит, увеличение этого ограничения вообще не изменило бы оптимальную прибыль.

Это ровно та идея, которую следующий урок разовьёт в полноценную теорию двойственности: коэффициенты небазисных столбцов в финальной строке $Z$ симплекс-таблицы — это в точности решение двойственной задачи, и они получаются «бесплатно», без дополнительных вычислений, просто как побочный продукт уже проведённого решения исходной (прямой) задачи.

Вырожденные случаи и вычислительная сложность

Интуиция

Симплекс-метод, как описан выше, молчаливо предполагает, что задача устроена «хорошо»: у многогранника есть хотя бы одна вершина, целевая функция на нём ограничена сверху (для задачи максимизации), а каждый пересчёт таблицы либо строго улучшает $Z$, либо алгоритм останавливается. В реальности встречаются три отклонения от этой идиллической картины. Допустимая область может оказаться пустой — ограничения противоречат друг другу, и ни одна точка не удовлетворяет им всем одновременно. Целевая функция может оказаться неограниченной — допустимая область простирается в направлении, в котором $Z$ растёт бесконечно, и оптимума попросту не существует. Наконец, могут возникать вырожденные вершины, где число активных (тесных) ограничений больше числа переменных — в таких точках возможны пересчёты таблицы, не меняющие $Z$ вовсе, и в редких патологических случаях алгоритм может даже зациклиться, бесконечно возвращаясь к одному и тому же набору вырожденных вершин.

Алгоритм

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

Критерий недопустимости (двухфазный метод, кратко). Если исходная задача не имеет очевидной начальной допустимой вершины (например, среди ограничений есть неравенства вида «$\ge$» или равенства, для которых начало координат не подходит), вводят искусственные переменные и сначала решают вспомогательную задачу — минимизацию суммы искусственных переменных. Если минимум этой вспомогательной задачи строго больше нуля, значит хотя бы одну искусственную переменную нельзя обнулить ни при каком допустимом наборе исходных переменных — то есть исходные ограничения противоречивы, а допустимая область пуста.

Примеры

Пример 1: неограниченная целевая функция. Максимизировать $Z=x_1+x_2$ при единственном содержательном ограничении $x_1-x_2\le2$, $x_1,x_2\ge0$. Стандартная форма: $x_1-x_2+s_1=2$. Начальная таблица (базис $s_1$, строка $Z=-x_1-x_2$):

Базис     x1     x2     s1   | RHS
s1         1     -1      1   |  2
Z         -1     -1      0   |  0

Оба коэффициента строки $Z$ отрицательны, выбираем, скажем, $x_1$ (можно и $x_2$, порядок не принципиален для итога). Тест отношений: единственная строка $s_1$ с коэффициентом $1$, отношение $2/1=2$. Пересчёт: строка $s_1$ делится на $1$ (уже готова), строка $Z$ обновляется: $(-1,-1,0\mid0)+1\cdot(1,-1,1\mid2)=(0,-2,1\mid2)$.

Базис     x1     x2     s1   | RHS
x1         1     -1      1   |  2
Z          0     -2      1   |  2

Строка $Z$ всё ещё содержит отрицательный коэффициент $-2$ у $x_2$: входящая переменная $x_2$. Смотрим на столбец $x_2$: единственная строка $x_1$ имеет коэффициент $-1$ — отрицательный, не подходит для теста отношений. Больше строк нет. Весь столбец входящей переменной состоит из неположительных чисел — сработал критерий неограниченности: можно сколько угодно наращивать $x_2$ (одновременно с $x_1$, чтобы оставаться в допустимой области — ведь ограничение $x_1-x_2\le2$ выполняется при любом росте $x_1$ вместе с $x_2$), и $Z=x_1+x_2$ растёт без предела. Оптимума не существует.

Пример 2: пустая допустимая область. Рассмотрим два ограничения: $x_1+x_2\le2$ и $x_1+x_2\ge5$ одновременно (плюс $x_1,x_2\ge0$). Первое ограничение требует, чтобы сумма переменных не превышала $2$, второе — чтобы она была не меньше $5$. Одновременно эти два требования выполнить невозможно ни при каких неотрицательных $x_1,x_2$: любая точка, удовлетворяющая первому, автоматически нарушает второе. Формально это обнаруживается на первой (вспомогательной) фазе двухфазного метода: минимальное значение суммы искусственных переменных окажется строго положительным (в данном случае — ровно $3$, разрыв между границами $5$ и $2$), что и сигнализирует о противоречивости исходных ограничений. Мы не разворачиваем здесь двухфазный метод в деталях — важно зафиксировать сам факт: как и неограниченность, пустая допустимая область — это не сбой алгоритма, а корректно распознаваемое свойство самой задачи, которое стоит проверять раньше, чем удивляться отсутствию ответа.

Пример 3: куб Кли — Минти и разрыв между худшим и типичным случаем. В 1972 году Виктор Кли и Джордж Минти построили специальную серию многогранников (сегодня известную как куб Кли — Минти) размерности $n$ с ровно $2^n$ вершинами, устроенных так, что классическое правило Данцига (входящая переменная — с самым отрицательным коэффициентом) заставляет симплекс-метод посетить все $2^n$ вершины одну за другой, прежде чем найти оптимум — притом что оптимум находится в одной конкретной вершине, до которой по более удачному пути можно было бы дойти всего за пару шагов. Уже при $n=3$ такой куб имеет $8$ вершин, и неудачно устроенный путь обходит все восемь; при $n=20$ таких вершин больше миллиона, при $n=100$ — число с тридцатью цифрами. Это строгое доказательство того, что симплекс-метод с правилом Данцига в худшем случае работает экспоненциально долго — не гипотеза и не недоработка конкретной реализации, а математический факт про сам алгоритм.

И тем не менее на практике — на промышленных задачах линейного программирования с тысячами и десятками тысяч переменных, ни капли не похожих на специально сконструированный куб Кли — Минти, — число пересчётов таблицы почти всегда оказывается в пределах нескольких сотен, эмпирически близко к $2$–$3$ пересчётам на каждое ограничение задачи. Строгое математическое объяснение этому разрыву дали Дэниел Спилман и Шанхуа Тенг в 2001 году с помощью техники «сглаженного анализа» (smoothed analysis): они показали, что даже если для отдельных специально сконструированных задач (как куб Кли — Минти) время работы экспоненциально, при небольшом случайном возмущении входных данных (что моделирует шум и неидеальность реальных измерений) ожидаемое время работы становится полиномиальным. Иными словами, задачи, на которых симплекс-метод действительно медленный, существуют, но встретить такую задачу «случайно», без специального конструирования, практически нереально.

Почему это важно

Разрыв между экспоненциальным худшим случаем и практически всегда полиномиальным поведением — это не курьёз, характерный именно для симплекс-метода, а узнаваемый паттерн, который встречается по всей теории алгоритмов и машинному обучению: быстрая сортировка (quicksort) в худшем случае работает за $O(n^2)$, но на практике — за $O(n\log n)$; хеш-таблицы в худшем случае деградируют до $O(n)$ на операцию при неудачном распределении коллизий, но обычно работают за $O(1)$; жадное построение дерева решений не гарантирует глобально наилучшего дерева (задача построения оптимального дерева решений NP-трудна), но на практике даёт результат, почти неотличимый от оптимального на большинстве датасетов. Симплекс-метод — вероятно, самый старый и самый тщательно изученный пример этого явления, и именно поэтому он остаётся классическим учебным случаем в курсах по анализу алгоритмов, даже несмотря на то, что для линейного программирования существуют и другие семейства методов — метод эллипсоидов Леонида Хачияна (1979) и методы внутренней точки Нарендры Кармаркара (1984), — которые гарантируют полиномиальное время работы в худшем случае, без всяких оговорок про сглаженный анализ. На практике методы внутренней точки нередко эффективнее симплекс-метода на очень больших разреженных задачах, и современные промышленные решатели обычно реализуют оба семейства и выбирают между ними в зависимости от структуры конкретной задачи.

Отдельная причина держать симплекс-метод в голове как специалисту по данным — он не только самостоятельный инструмент, но и подпрограмма внутри более сложных задач оптимизации с линейными ограничениями, которые встречаются в машинно-обучающихся пайплайнах: например, точное (не приближённое) вычисление расстояния Вассерштейна между двумя дискретными распределениями — популярная в современном ML метрика сравнения распределений, используемая в генеративных моделях и анализе сдвига данных, — в своей базовой формулировке сводится к задаче линейного программирования (транспортной задаче), и специализированные варианты симплекс-метода (в первую очередь сетевой симплекс-метод, network simplex) — один из практических способов решить её точно. На практике для больших задач чаще применяют приближённые методы вроде энтропийной регуляризации (алгоритм Синкхорна), которые быстрее, но именно точная LP-формулировка и связанный с ней сетевой симплекс-метод остаются эталоном, с которым сверяют качество приближения.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Приведи ограничение $2x_1+3x_2\le12$ к стандартной форме, введя добавочную переменную.

Задание 2: Для задачи максимизировать $Z=4x_1+2x_2$ при $x_1+x_2\le6$, $x_1\le4$, $x_1,x_2\ge0$ построй начальную симплекс-таблицу.

Задание 3: В таблице из задания 2 определи входящую переменную на первом шаге.

Задание 4: Для входящей переменной $x_1$ из задания 3 проведи тест отношений и найди выходящую переменную.

Задание 5: Объясни своими словами, почему в тесте отношений строки с нулевым или отрицательным коэффициентом во входящем столбце не участвуют.

Задание 6: Дана финальная строка $Z$ симплекс-таблицы: $0,\ 0,\ 1{,}5,\ 0,\ 2$ (для переменных $x_1,x_2,s_1,x_3,s_2$ соответственно). Является ли текущее решение оптимальным?

Задание 7: Дана строка $Z$: $-1,\ 0,\ 3,\ 0$. Оптимально ли решение? Если нет, какая переменная войдёт в базис следующей?

Задание 8: Сформулируй задачу максимизировать $Z=x_1+x_2$ при $x_1\le3$, $x_2\le5$, $x_1,x_2\ge0$ в стандартной форме и укажи начальное базисное решение.

Задание 9: Для задачи из задания 8 найди оптимум геометрически (без таблицы) и объясни, почему он очевиден без единого пересчёта.

Задание 10: Сколько базисных переменных должно быть в симплекс-таблице для задачи с $m=4$ ограничениями (в стандартной форме, без учёта неотрицательности переменных как отдельных строк)?

Средние задания (11–20)

Задание 11: Максимизировать $Z=5x_1+4x_2$ при $x_1\le6$, $x_2\le8$, $x_1+x_2\le10$, $x_1,x_2\ge0$. Построй начальную таблицу и сделай первый пересчёт.

Задание 12: Продолжи задачу из задания 11 до оптимума.

Задание 13: Проверь ответ задания 12, подставив $x_1=6, x_2=4$ во все исходные ограничения.

Задание 14: В финальной таблице задания 12 коэффициент при $s_1$ в строке $Z$ равен $1$, а при $s_3$ — $4$. Что это означает экономически?

Задание 15: Максимизировать $Z=x_1+2x_2$ при $x_1-x_2\le4$, $x_1,x_2\ge0$ (единственное содержательное ограничение). Определи, ограничена ли задача.

Задание 16: Приведи содержательный пример реальной ситуации, где задача линейного программирования оказалась бы неограниченной, и объясни, какая ошибка в постановке задачи обычно к этому приводит.

Задание 17: Даны ограничения $x_1+2x_2\le8$ и $x_1+2x_2\ge10$ (плюс $x_1,x_2\ge0$). Определи, допустима ли эта система, и объясни почему.

Задание 18: Для задачи с $n=4$ переменными и $m=6$ ограничениями посчитай число потенциальных базисных решений (кандидатов в вершины) по формуле $\binom{n+m}{m}$.

Задание 19: Оцени, насколько больше кандидатов в вершины появится, если в задаче из задания 18 число ограничений вырастет с $6$ до $12$ при том же числе переменных $n=4$.

Задание 20: Объясни своими словами разницу между «вершиной, соседней с текущей» и «произвольной другой допустимой точкой», используя понятие ребра многогранника.

Продвинутые задания (21–30)

Задание 21: Максимизировать $Z=3x_1+2x_2+4x_3$ при $x_1+x_2+2x_3\le4$, $2x_1+3x_3\le5$, $2x_1+x_2+3x_3\le7$, $x_1,x_2,x_3\ge0$. Проведи полную трассировку симплекс-таблицы до оптимума.

Задание 22: В задаче 21 после первого пересчёта в строке $s_1$ появился отрицательный коэффициент $-1/3$ при $x_1$. Означает ли отрицательный коэффициент в промежуточной (не финальной) таблице ошибку?

Задание 23: Сформулируй, при каком условии симплекс-метод остановится ровно за один пересчёт таблицы, и приведи пример такой задачи.

Задание 24: В примере 2 раздела «Полная пошаговая трассировка» (три переменные, продукты $x_1,x_2,x_3$) объясни, почему входящей переменной сразу стала именно $x_2$, а не $x_1$ или $x_3$, несмотря на то что итоговое решение вообще не использует $x_1$ и $x_3$.

Задание 25: Сравни число вершин допустимой области в примере из задания 21 (три переменных, три ограничения плюс неотрицательность) с числом вершин куба Кли — Минти той же размерности $n=3$.

Задание 26: Объясни, почему метод эллипсоидов и методы внутренней точки гарантируют полиномиальное время в худшем случае, а симплекс-метод — нет, хотя на практике симплекс-метод часто быстрее.

Задание 27: Своими словами объясни связь между вырожденностью вершины (более $n$ активных ограничений в вершине $n$-мерного пространства) и риском зацикливания симплекс-метода.

Задание 28: Опиши, как задача вычисления расстояния Вассерштейна между двумя дискретными распределениями сводится к задаче линейного программирования, и какую роль там играют ограничения.

Задание 29: Сравни жадную стратегию симплекс-метода (переход к соседней вершине с наибольшим приростом) с жадной стратегией построения дерева решений (выбор разбиения с наибольшим приростом информации). В чём принципиальное отличие по силе гарантии результата?

Задание 30: Придумай собственный пример задачи линейного программирования с двумя переменными и тремя ограничениями, у которой оптимум достигается сразу в двух соседних вершинах одновременно (альтернативные оптимумы), и объясни, что это означает для завершения симплекс-метода.

Частые ошибки

Ошибка 1. Выбирают входящую переменную по любому отрицательному коэффициенту в строке $Z$, а не по наиболее отрицательному.

Как выглядит: «в строке $Z$ есть $-2$ и $-5$, возьмём $-2$, потому что так проще считать».

Почему возникает: кажется, что любой отрицательный коэффициент одинаково «разрешает» улучшение, а выбор между ними — вопрос удобства.

Как правильно: классическое правило Данцига требует брать наиболее отрицательный коэффициент — это не строго обязательное условие для корректности алгоритма (любой отрицательный коэффициент в принципе допустим как входящий), но отступление от стандартного правила меняет число итераций и путь по вершинам, и при самостоятельном решении задач для сверки с учебным ответом стоит придерживаться этого стандартного правила.

Ошибка 2. При тесте отношений включают в сравнение строки с нулевым или отрицательным коэффициентом во входящем столбце.

Как выглядит: деление свободного члена на ноль или взятие отрицательного отношения как «наименьшего».

Почему возникает: механическое применение формулы «отношение = RHS / коэффициент» без проверки знака коэффициента.

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

Ошибка 3. Путают строку $Z$ с обычной строкой ограничения и применяют к ней тест отношений или считают её кандидатом на выходящую переменную.

Как выглядит: попытка «сократить» строку $Z$ так же, как строки ограничений, или включить её в тест отношений.

Почему возникает: визуально строка $Z$ ничем не отличается от остальных строк таблицы, но по смыслу она принципиально другая — это не ограничение, а индикатор оптимальности.

Как правильно: строка $Z$ пересчитывается вместе со всеми остальными строками при каждом пивоте (по тем же правилам исключения Гаусса), но никогда не участвует в выборе выходящей переменной и не является кандидатом на «выход из базиса».

Ошибка 4. Останавливают алгоритм, как только значение $Z$ перестаёт заметно расти, вместо проверки знаков коэффициентов строки $Z$.

Как выглядит: «прирост $Z$ стал маленьким, наверное, мы почти у оптимума, можно остановиться».

Почему возникает: интуитивное (и в общем случае неверное для линейного программирования) предположение, что скорость улучшения плавно убывает по мере приближения к оптимуму, как у градиентного спуска.

Как правильно: единственный корректный критерий остановки — отсутствие отрицательных коэффициентов в строке $Z$; прирост $Z$ на конкретном шаге может быть маленьким или даже нулевым (в вырожденном случае) при том, что алгоритм ещё далёк от завершения, и наоборот — большой прирост не гарантирует, что следующий шаг будет последним.

Ошибка 5. Забывают проверить исходную задачу на неограниченность и пустоту допустимой области, предполагая, что у любой корректно записанной задачи линейного программирования обязательно есть конечный оптимум.

Как выглядит: попытка бесконечно продолжать пересчёт таблицы, когда весь входящий столбец состоит из неположительных чисел, в ожидании, что «где-то дальше найдётся выходящая строка».

Почему возникает: интуиция, что реальная (не учебная) задача оптимизации обязана иметь ответ, раз она вообще была сформулирована.

Как правильно: всегда явно проверять критерий неограниченности при выборе входящей переменной (если весь столбец неположителен — задача неограничена, оптимума нет) и, если для задачи нет очевидной начальной допустимой вершины, отдельно убеждаться в непустоте допустимой области, прежде чем интерпретировать результат.

Ошибка 6. Считают теневые цены в финальной строке $Z$ универсальными константами, верными для любого изменения правой части ограничения, включая очень большие изменения.

Как выглядит: «теневая цена ограничения равна $1{,}5$, значит увеличение ресурса на $100$ единиц увеличит прибыль на $150$».

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

Как правильно: теневая цена верна только в определённом диапазоне изменения правой части — пока структура оптимального базиса (набор базисных переменных) не меняется; за пределами этого диапазона многогранник допустимых решений перестраивается, входит или выходит другое ограничение, и теневая цена может измениться — точный диапазон устойчивости теневой цены — отдельный вопрос анализа чувствительности, тесно связанный с темой двойственности следующего урока.

Главное запомнить

  • Оптимум задачи линейного программирования достигается в вершине допустимого многогранника (доказано в прошлом уроке), но полный перебор вершин невозможен из-за экспоненциального роста их числа — $\binom{n+m}{m}$ кандидатов для $n$ переменных и $m$ ограничений.

  • Симплекс-метод стартует в допустимой вершине (обычно в начале координат) и на каждом шаге переходит к соседней по ребру многогранника вершине с лучшим значением целевой функции, пока не останется улучшающих соседей.

  • Стандартная форма задачи вводится через добавочные (slack) переменные, превращающие неравенства в равенства; базисное допустимое решение такой системы (ровно $m$ ненулевых переменных из $n+m$) соответствует вершине многогранника.

  • В симплекс-таблице входящая переменная выбирается по наиболее отрицательному коэффициенту строки целевой функции $Z$, а выходящая — по минимальному отношению свободного члена к положительному коэффициенту входящего столбца (правило минимального отношения).

  • Ведущий элемент (пересечение входящего столбца и выходящей строки) задаёт пересчёт таблицы методом исключения Гаусса; алгоритм останавливается, когда в строке $Z$ не остаётся отрицательных коэффициентов.

  • Если весь столбец входящей переменной состоит из неположительных чисел, целевая функция неограничена на допустимой области и оптимума не существует; если исходные ограничения противоречивы, допустимая область пуста — оба случая распознаются алгоритмически, а не наугад.

  • Коэффициенты небазисных переменных в финальной строке $Z$ — это теневые цены соответствующих ограничений, показывающие, насколько выросла бы оптимальная прибыль при увеличении ресурса на единицу; это прямой мост к теории двойственности.

  • В худшем случае (куб Кли — Минти) число шагов симплекс-метода с классическим правилом Данцига растёт экспоненциально с размером задачи, но на практике почти всегда требуется лишь несколько сотен пересчётов даже для тысяч переменных — этот разрыв строго объяснён сглаженным анализом Спилмана и Тенга (2001).

  • Методы внутренней точки и метод эллипсоидов гарантируют полиномиальное время работы в худшем случае в отличие от симплекс-метода, но на практике симплекс-метод часто оказывается быстрее — современные промышленные решатели реализуют оба семейства.

  • Специализированные варианты симплекс-метода (сетевой симплекс) применяются как точный способ решения транспортной задачи, к которой сводится вычисление расстояния Вассерштейна между дискретными распределениями — метрики, широко используемой в современном машинном обучении.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую продолжает урок 280 про линейное программирование: там было доказано (геометрически и через теорему из блока выпуклой оптимизации), что оптимум линейной задачи достигается в вершине допустимого многогранника — сегодняшний урок отвечает на вопрос «как найти эту вершину эффективно», не перебирая их все. Понимание выпуклых множеств из урока 277 тоже лежит в основе: без выпуклости многогранника локальный жадный переход по соседним вершинам не гарантировал бы глобальной оптимальности, точно так же как локальный минимум невыпуклой функции не обязан быть глобальным (урок 278).

Что изучить дальше

Следующий урок 282 разбирает двойственность в линейном программировании — формальную теорию, стоящую за теневыми ценами, которые естественным образом появились в финальной строке $Z$ сегодняшних симплекс-таблиц. Каждая задача линейного программирования (прямая) имеет парную ей двойственную задачу, и коэффициенты небазисных переменных в оптимальной таблице прямой задачи — это в точности оптимальное решение двойственной. Дальше по курсу, в блоке про методы оптимизации в машинном обучении, ты встретишь методы внутренней точки — второе большое семейство алгоритмов для линейного (а затем и более общего выпуклого) программирования, упомянутое в этом уроке лишь вскользь.

Где это нужно в жизни

📦 Логистика и цепочки поставок. Задачи распределения товаров по складам, маршрутизации транспорта и планирования производства промышленного масштаба (тысячи переменных) решаются коммерческими LP-решателями, использующими вариации симплекс-метода или методы внутренней точки — то же семейство алгоритмов, что появилось в этом уроке, просто оптимизированное для скорости и разреженных данных.

🤖 Машинное обучение и оптимальный транспорт. Точное вычисление расстояния Вассерштейна между распределениями — метрики, применяемой в генеративно-состязательных сетях (Wasserstein GAN) и в анализе сдвига распределения данных, — сводится к транспортной задаче линейного программирования; сетевой симплекс-метод — один из точных алгоритмов её решения.

📊 Экономика и распределение ресурсов. Теневые цены, естественно возникающие как побочный продукт симплекс-таблицы, — стандартный инструмент экономического анализа: они напрямую отвечают на вопрос «на что стоит потратить дополнительный бюджет в первую очередь», без пересчёта задачи с нуля.

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

Интересные факты

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

  • Слово «симплекс» в названии метода не связано напрямую с алгоритмом как таковым в его практической реализации: симплекс — это геометрический термин для простейшего выпуклого многогранника заданной размерности (отрезок в 1D, треугольник в 2D, тетраэдр в 3D) — Данциг использовал его, поскольку в его ранних геометрических рассуждениях о задаче он представлял допустимую область как объединение таких простейших фигур; в современном практическом изложении метод работает с произвольными многогранниками, не обязательно симплексами.

  • В 2000 году журнал «Computing in Science & Engineering» включил симплекс-метод в список десяти алгоритмов, оказавших наибольшее влияние на развитие науки и техники в XX веке — в этом же списке присутствуют, например, быстрое преобразование Фурье и метод Монте-Карло.

  • Куб Кли — Минти, построенный в 1972 году для демонстрации экспоненциального худшего случая симплекс-метода, изначально задумывался авторами не как критика метода, а как математический вызов: на момент публикации было неизвестно, существует ли вообще какой-либо вариант симплекс-метода с полиномиальным временем работы в худшем случае. Спустя полвека этот вопрос остаётся открытым: для некоторых конкретных правил выбора входящей переменной (не только для правила Данцига) доказан экспоненциальный худший случай, но существование правила, гарантирующего полиномиальность именно у симплекс-метода (в отличие от принципиально других семейств — методов внутренней точки), до сих пор не доказано и не опровергнуто в общем виде.

Лайфхаки

  • При решении задачи вручную для проверки промежуточного результата подставляй текущие базисные значения обратно во все исходные ограничения (не в стандартную форму) — если хотя бы одно нарушается, ошибка закралась в один из предыдущих пересчётов, и её проще найти сразу, чем после финальной таблицы.

  • Прежде чем выбирать входящую переменную, быстро просканируй всю строку $Z$ целиком, а не останавливайся на первом встреченном отрицательном коэффициенте — легко ошибочно выбрать не самый отрицательный, особенно в больших таблицах с многими столбцами.

  • Если при тесте отношений получилась ничья (два одинаковых минимальных отношения), выбери строку с переменной меньшего индекса (правило Бланда) — это не только избегает зацикливания в вырожденных случаях, но и упрощает воспроизводимость расчётов при сверке с чужим решением той же задачи.

  • Перед тем как садиться за таблицу, реши задачу геометрически (если переменных всего две-три) — так у тебя будет независимая проверка правильного ответа, а заодно интуиция для того, чтобы сразу заметить арифметическую ошибку, если финальный ответ таблицы разойдётся с графиком.

  • В scipy.optimize.linprog метод 'highs' (по умолчанию в современных версиях) автоматически выбирает между вариантами симплекс-метода и методом внутренней точки в зависимости от структуры задачи — если тебе нужно решить реальную задачу, а не потренироваться в ручных пересчётах, доверься этому выбору вместо того, чтобы вручную указывать конкретный метод, если для этого нет специфической причины (например, требование получить именно вершинное, а не приближённое внутреннее решение).

  • Если после решения реальной задачи промышленного размера видишь, что решатель работает подозрительно долго (минуты вместо секунд для задачи в тысячи переменных), заподозри не баг в постановке, а особую структуру задачи, приближающуюся к патологическим случаям вроде куба Кли — Минти, — переформулировка задачи (например, изменение порядка или группировки ограничений) иногда кардинально меняет практическое время работы, даже не меняя математического содержания задачи.

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

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!