Линейное программирование 🔺

Представь завод, который производит два вида продукции — скажем, алюминиевые оконные рамы и деревянные дверные рамы. У завода три цеха с ограниченной мощностью, у каждого продукта своя прибыль с единицы, и вопрос ровно один: сколько рам каждого вида выпускать в сутки, чтобы прибыль была максимальной? Ни интуиция, ни перебор вручную здесь не работают надёжно уже при десятке продуктов и десятке цехов — а в реальности таких переменных и ограничений могут быть тысячи. Но если и прибыль, и расход ресурсов на каждый продукт зависят от объёма производства линейно, у этой на первый взгляд необъятной задачи есть строгий, полностью предсказуемый способ решения. Он называется линейным программированием, и сегодняшний урок — первый шаг к тому, чтобы понять, откуда берётся эта предсказуемость.

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

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

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

История

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

Независимо, без какого-либо контакта с работой Канторовича, задачу переоткрыл американский математик Джордж Данциг. В 1947 году, работая над задачами планирования снабжения для ВВС США, Данциг не только сформулировал линейное программирование в его современном виде, но и предложил алгоритм для его решения — знаменитый симплекс-метод, которому целиком посвящён следующий урок этого курса. Идея Данцига опиралась ровно на тот геометрический факт, который ты докажешь сегодня: раз оптимум линейной задачи всегда лежит в вершине многогранника допустимых решений, достаточно методично перемещаться от вершины к соседней вершине, улучшая значение целевой функции на каждом шаге, — и рано или поздно алгоритм гарантированно остановится в оптимальной точке. Симплекс-метод оказался настолько практичным, что уже к 1950-м годам линейное программирование стало стандартным инструментом планирования в промышленности, логистике и экономике — и остаётся им сегодня, просто спрятанным внутри современных ERP-систем, логистических платформ и облачных планировщиков ресурсов.

Историческая ирония в том, что два человека по разные стороны железного занавеса, работая над формально не связанными задачами — оптимальное распределение фанерного сырья в Ленинграде и снабжение военно-воздушных баз в США, — пришли к одной и той же математической структуре с разницей в восемь лет. Заслуги обоих были признаны официально в 1975 году, когда Канторович вместе с голландско-американским экономистом Тьяллингом Купмансом получил Нобелевскую премию по экономике «за вклад в теорию оптимального распределения ресурсов» — единственную Нобелевскую премию, присуждённую советскому учёному за работу в области математической экономики (подробнее об этом — в разделе «Интересные факты»).

Стандартная форма задачи линейного программирования

Интуиция

В уроке 276 ты уже видел общий язык оптимизации: минимизировать (или максимизировать) целевую функцию $f(x)$ на допустимом множестве $D$. Линейное программирование — это конкретизация этого языка до предельно простого, но чрезвычайно широко применимого частного случая: и целевая функция, и все ограничения, задающие $D$, — линейные. Вернёмся к заводу с двумя продуктами. Пусть $x_1$ — суточный объём производства оконных рам, $x_2$ — дверных рам. Прибыль с рамы каждого вида известна и постоянна, поэтому суммарная прибыль — линейная функция $c_1 x_1 + c_2 x_2$. Каждый цех тратит на производство одной рамы фиксированное время, и суммарное время работы цеха за сутки не может превышать его мощности — это тоже линейное неравенство относительно $x_1, x_2$. Производить отрицательное количество рам, разумеется, нельзя — отсюда требование $x_1, x_2 \ge 0$. Вся задача целиком укладывается в три ингредиента: линейная цель, линейные неравенства, неотрицательность переменных.

Определение

Определение (задача ЛП в стандартной форме). Пусть $x = (x_1, \dots, x_n) \in \mathbb{R}^n$ — вектор переменных решения (decision variables), $c \in \mathbb{R}^n$ — вектор коэффициентов целевой функции, $A \in \mathbb{R}^{m \times n}$ — матрица коэффициентов ограничений, $b \in \mathbb{R}^m$ — вектор правых частей. Задачей линейного программирования в стандартной форме называется задача

$$\text{maximize } c^\top x \quad \text{при условиях } Ax \le b,\ x \ge 0$$

где неравенства $Ax \le b$ и $x \ge 0$ понимаются покомпонентно. Задача минимизации $c^\top x$ сводится к этой же форме заменой $c \to -c$ (минимизировать $c^\top x$ — то же самое, что максимизировать $-c^\top x$, а затем сменить знак у найденного оптимального значения).

Каждое отдельное неравенство $a_i^\top x \le b_i$ (строка матрицы $A$) задаёт полупространство — ровно тот объект из урока 277. Условие $Ax \le b$ — это пересечение $m$ таких полупространств, а вместе с $x \ge 0$ (ещё $n$ полупространств координатных осей) вся допустимая область $D$ представляет собой пересечение конечного числа полупространств — то есть выпуклый многогранник (полиэдр) по определению того же урока. Этот геометрический факт — не побочное наблюдение, а фундамент всего сегодняшнего урока, и следующий раздел посвящён именно ему.

Примеры

Пример 1: мебельная мастерская. Мастерская выпускает столы и стулья. Стол приносит прибыль $200$ рублей, стул — $120$ рублей. На стол уходит $4$ часа столярных работ и $2$ часа отделки, на стул — $2$ часа столярных работ и $1$ час отделки. В сутки доступно $40$ часов столярных работ и $18$ часов отделки. Пусть $x_1$ — количество столов, $x_2$ — стульев. Задача в стандартной форме:

Обрати внимание, что второе ограничение ($2x_1 + x_2 \le 18$) на самом деле строже первого при пересчёте на одну и ту же единицу — если $4x_1+2x_2\le40$ переписать как $2x_1+x_2\le20$, видно, что ограничение по отделке ($\le18$) более жёсткое. Такие «избыточные» на первый взгляд ограничения — обычное дело в реальных задачах, и графический (или алгебраический) метод решения автоматически определяет, какое из них реально ограничивает решение, а какое нет.

Пример 2: классическая задача о стекольной компании (Wyndor Glass). Компания производит алюминиевые оконные рамы (продукт 1, $x_1$) и деревянные дверные рамы (продукт 2, $x_2$) в трёх цехах. Цех 1 обрабатывает только продукт 1 и имеет запас мощности на $4$ единицы в сутки: $x_1 \le 4$. Цех 2 обрабатывает только продукт 2 и имеет запас на $6$ единиц: $2x_2 \le 12$. Цех 3 участвует в производстве обоих продуктов совместно: $3x_1 + 2x_2 \le 18$. Прибыль с единицы продукта 1 составляет $3$ тысячи рублей, с продукта 2 — $5$ тысяч. Задача в стандартной форме:

Эта задача (в оригинале известная как «Wyndor Glass Co.») — один из самых цитируемых учебных примеров в исследовании операций именно потому, что на ней предельно наглядно видна вся механика метода. Мы вернёмся к ней в следующих трёх разделах урока и решим её полностью — сначала перебором вершин, затем графически, затем в стандартной форме с дополнительными переменными.

Пример 3: задача минимизации (диета). Диетологу нужно составить рацион из двух продуктов с минимальной стоимостью, обеспечив при этом минимум $4$ единиц питательного вещества А и $6$ единиц вещества Б. Продукт 1 стоит $2$ рубля за порцию и содержит $1$ единицу А и $1$ единицу Б; продукт 2 стоит $5$ рублей за порцию и содержит $0$ единиц А и $3$ единицы Б. Пусть $x_1, x_2$ — количество порций каждого продукта. Задача:

Заметь, что ограничения здесь заданы через $\ge$, а не $\le$ — это никак не противоречит определению стандартной формы: каждое неравенство вида $a^\top x \ge b$ переписывается как $-a^\top x \le -b$ простым умножением обеих частей на $-1$ (со сменой знака неравенства). После такого умножения задача полностью укладывается в стандартную форму, а сама операция — рутинная, но обязательная процедура приведения к стандартному виду, к которой мы вернёмся отдельно в четвёртом разделе урока.

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

Стандартная форма — это не бюрократическая формальность, а общий интерфейс, через который любая практическая задача распределения ресурсов подключается к универсальным алгоритмам решения (симплекс-метод следующего урока, а на практике — промышленные солверы вроде scipy.optimize.linprog, PuLP, CVXPY, коммерческие Gurobi и CPLEX). Умение перевести словесную формулировку задачи в тройку $(c, A, b)$ — это ровно тот навык, который отделяет распознавание задачи как «линейной» от способности реально её решить. В прикладном машинном обучении эта формализация встречается чаще, чем кажется на первый взгляд: например, при развёртывании нескольких моделей на общем кластере нужно распределить ограниченный вычислительный бюджет (GPU-часы, память) между несколькими задачами так, чтобы максимизировать суммарную полезность (throughput инференса, качество на валидации при заданном бюджете дообучения) при жёстких ограничениях на доступные ресурсы каждого узла — это по структуре в точности задача ЛП, к которой мы вернёмся в практике этого урока на конкретном числовом примере.

Допустимая область как многогранник и оптимум в вершине

Интуиция

Допустимая область задачи ЛП — многогранник, как мы только что установили. Представь линейную целевую функцию $c^\top x$ как «наклонную крышу», натянутую над этим многогранником: значение функции в каждой точке — это высота крыши прямо над ней. Поскольку функция линейна, крыша идеально плоская — без единого изгиба, холма или впадины. У плоской крыши, натянутой над многогранной площадкой, самая высокая точка физически не может оказаться где-то в середине грани или внутри самой площадки — крыша либо параллельна всей грани целиком (и тогда высота на ней постоянна), либо обязательно достигает максимума в одном из углов площадки, там, где перепад высоты между соседними направлениями делает точку локально самой высокой. Это и есть интуиция ключевого факта сегодняшнего урока: оптимум линейной функции на многограннике всегда достигается в одной из его вершин.

Теорема

Теорема (об оптимуме в вершине). Пусть $P \subset \mathbb{R}^n$ — непустой ограниченный многогранник (выпуклый, как пересечение конечного числа полупространств — урок 277), а $c^\top x$ — линейная целевая функция. Тогда максимум $c^\top x$ на $P$ достигается по меньшей мере в одной из вершин $P$.

Обоснование через выпуклость. Любая точка ограниченного многогранника $P$ представима как выпуклая комбинация его вершин $v_1, \dots, v_k$ (это обобщение определения выпуклой комбинации из урока 277 на произвольное число точек — геометрически это означает, что многогранник и есть выпуклая оболочка своих вершин, и переизлагать доказательство этого геометрического факта здесь не будем, достаточно интуиции «многогранник состоит из отрезков и их сочетаний между угловыми точками»). Значит, любая $x \in P$ записывается как $x = \sum_{i=1}^k \lambda_i v_i$, где $\lambda_i \ge 0$, $\sum_i \lambda_i = 1$. Подставим в целевую функцию, используя её линейность:

Правая часть — взвешенное среднее чисел $c^\top v_1, \dots, c^\top v_k$ с весами $\lambda_i$, а взвешенное среднее набора чисел никогда не превышает наибольшего из них:

Значит, значение целевой функции в любой точке многогранника не превышает максимального значения функции по вершинам. А поскольку сама вершина с максимальным $c^\top v_j$ — тоже точка $P$, максимум по всему $P$ в точности равен максимуму по конечному набору вершин. $\blacksquare$

Примеры

Пример 1: полный перебор вершин задачи Wyndor Glass. Вернёмся к примеру 2 предыдущего раздела: $\text{maximize } 3x_1+5x_2$ при $x_1\le4$, $2x_2\le12$, $3x_1+2x_2\le18$, $x_1,x_2\ge0$. Найдём все вершины допустимого многоугольника — точки пересечения пар границ ограничений, которые сами удовлетворяют всем остальным неравенствам:

• $(0,0)$ — пересечение $x_1=0$ и $x_2=0$;
• $(4,0)$ — пересечение $x_1=4$ и $x_2=0$;
• $(4,3)$ — пересечение $x_1=4$ и $3x_1+2x_2=18$ (отсюда $2x_2=6$, $x_2=3$);
• $(2,6)$ — пересечение $2x_2=12$ и $3x_1+2x_2=18$ (отсюда $x_2=6$, $3x_1=6$, $x_1=2$);
• $(0,6)$ — пересечение $x_1=0$ и $2x_2=12$.

Вычислим значение $Z=3x_1+5x_2$ в каждой: $(0,0)\to0$; $(4,0)\to12$; $(4,3)\to12+15=27$; $(2,6)\to6+30=36$; $(0,6)\to0+30=30$. Максимум $Z=36$ достигается в вершине $(2,6)$ — компании выгоднее выпускать $2$ единицы оконных рам и $6$ единиц дверных рам в сутки.

Пример 2: минимизация задачи о диете (пример 3 предыдущего раздела). Задача $\text{minimize } 2x_1+5x_2$ при $x_1\ge4$, $x_1+3x_2\ge6$, $x_1,x_2\ge0$ имеет неограниченную сверху (но не снизу) допустимую область, но минимум по-прежнему достигается в одной из угловых точек нижней границы этой области. Вершины: $(4,0)$ (пересечение $x_1=4$ и $x_2=0$, проверка: $4+0=4\ge6$? Нет, не выполняется — эта точка не входит в допустимую область); $(6,0)$ (пересечение $x_1+3x_2=6$ и $x_2=0$: проверка $x_1=6\ge4$ ✓ — допустима); $(4, 2/3)$ (пересечение $x_1=4$ и $x_1+3x_2=6$: $3x_2=2$, $x_2=2/3$). Вычислим $Z$: $(6,0)\to12+0=12$; $(4,2/3)\to8+10/3\approx11{,}33$. Минимум $Z\approx11{,}33$ достигается в вершине $(4,\,2/3)$.

Пример 3: вырожденный случай — оптимум на целой грани. Возьмём область $x_1\ge0$, $x_2\ge0$, $x_1+x_2\le4$ и целевую функцию $\text{maximize } x_1+x_2$. Вершины треугольника: $(0,0)\to0$; $(4,0)\to4$; $(0,4)\to4$. Максимум по перебору вершин равен $4$ и достигается сразу в двух вершинах — но это не совпадение, а следствие того, что вектор коэффициентов целевой функции $(1,1)$ в точности параллелен направлению грани $x_1+x_2=4$. В такой ситуации оптимальное значение одинаково в каждой точке этой грани, а не только в её концах: возьми, например, точку $(1,3)$ на этой же грани — $Z=1+3=4$, то же самое значение. Теорема не нарушается: среди множества всех оптимальных решений по-прежнему есть хотя бы одна вершина (на самом деле их здесь ровно две), просто оптимум в этом вырожденном случае не единственный.

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

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

Графическое решение задачи ЛП с двумя переменными

Интуиция

Когда переменных всего две, всю задачу можно буквально нарисовать на плоскости: каждое линейное ограничение — это прямая линия, а неравенство отбирает одну из двух полуплоскостей, на которые эта прямая делит плоскость. Пересечение всех отобранных полуплоскостей — тот самый многоугольник допустимых решений. Целевую функцию $c_1x_1+c_2x_2$ удобно представить через семейство «линий уровня» — прямых $c_1x_1+c_2x_2=k$ при разных значениях константы $k$; все они параллельны друг другу (направление задаёт вектор $(c_1,c_2)$), а увеличение $k$ сдвигает линию в направлении вектора $(c_1,c_2)$. Решение задачи графически — это, по сути, поиск такой линии уровня, которая ещё касается допустимого многоугольника, но при малейшем дальнейшем сдвиге в сторону увеличения (для максимизации) полностью покидает его пределы.

Алгоритм

Алгоритм графического решения задачи ЛП с двумя переменными.

1. Начерти границу каждого ограничения как прямую линию (заменив неравенство на равенство).
2. Для каждой прямой определи, какая из двух полуплоскостей соответствует неравенству — например, подставив в неравенство контрольную точку вроде $(0,0)$.
3. Найди пересечение всех полуплоскостей (включая $x_1\ge0$, $x_2\ge0$) — это и есть допустимая область; определи её вершины как попарные пересечения границ.
4. Построй одну линию уровня целевой функции $c_1x_1+c_2x_2=k$ для произвольного удобного $k$ и определи направление вектора $(c_1,c_2)$ — это направление возрастания функции.
5. Мысленно (или физически, двигая линейку) сдвигай линию уровня параллельно самой себе в направлении $(c_1,c_2)$ при максимизации (или в противоположном направлении при минимизации), пока она в последний раз касается допустимой области.
6. Последняя точка (или грань) касания — оптимальное решение. Если сдвиг можно продолжать бесконечно без потери контакта с допустимой областью, задача неограничена (unbounded); если допустимая область вообще пуста, задача несовместна (infeasible).

Примеры

Пример 1: полное графическое решение задачи Wyndor Glass. Ограничения: $x_1=4$ — вертикальная прямая; допустимая полуплоскость слева от неё (проверка точкой $(0,0)$: $0\le4$ ✓). $2x_2=12$, то есть $x_2=6$ — горизонтальная прямая; допустимая полуплоскость ниже неё. $3x_1+2x_2=18$ — прямая, проходящая через точки $(6,0)$ и $(0,9)$; допустимая полуплоскость ближе к началу координат (проверка: $0\le18$ ✓). Пересечение всех трёх полуплоскостей вместе с $x_1,x_2\ge0$ образует пятиугольник с вершинами $(0,0)$, $(4,0)$, $(4,3)$, $(2,6)$, $(0,6)$ — теми же самыми, что мы уже нашли алгебраически в предыдущем разделе. Возьмём линию уровня $Z=3x_1+5x_2=0$ — она проходит через начало координат. Направление возрастания $Z$ задаёт вектор $(3,5)$ — сдвигаем линию параллельно вверх-вправо. При $Z=15$ линия проходит примерно через $(0,3)$–$(5,0)$, всё ещё пересекая многоугольник. Продолжаем сдвиг: при $Z=30$ линия проходит через $(0,6)$ — касается многоугольника в этой вершине и частично заходит внутрь него. Двигаем ещё дальше: при $Z=36$ линия проходит ровно через точку $(2,6)$ и больше нигде не пересекает многоугольник — это последняя точка контакта. При $Z>36$ линия уровня целиком покидает допустимую область. Оптимум: $x_1=2$, $x_2=6$, $Z=36$ — тот же ответ, что и при переборе вершин, что и должно быть по доказанной теореме.

Пример 2: неограниченная задача (unbounded). Рассмотрим $\text{maximize } x_1+x_2$ при $x_1-x_2\le1$, $x_1,x_2\ge0$ — заметь, что верхней границы на $x_1$ или $x_2$ по отдельности здесь нет. Прямая $x_1-x_2=1$ проходит через $(1,0)$ и, например, $(3,2)$; допустимая полуплоскость — та, что содержит $(0,0)$ (проверка: $0\le1$ ✓), то есть область выше и левее этой прямой. Вместе с $x_1,x_2\ge0$ получаем неограниченную область, «открытую» в направлении роста обеих координат: возьми, например, точку $(t+1,\,t)$ при любом $t\ge0$ — проверка $x_1-x_2=(t+1)-t=1\le1$ ✓, точка допустима при любом сколь угодно большом $t$. Линия уровня $x_1+x_2=k$ при этом продолжает пересекать допустимую область при любом $k$ — в частности, значение целевой функции в точке $(t+1,t)$ равно $2t+1\to\infty$ при $t\to\infty$. Сдвигать линию уровня в направлении роста можно бесконечно без потери контакта с областью — задача неограничена, конечного максимума не существует.

Пример 3: несовместная задача (infeasible). Рассмотрим ограничения $x_1+x_2\le2$ и $x_1+x_2\ge6$ при $x_1,x_2\ge0$. Первое неравенство задаёт полуплоскость ниже прямой $x_1+x_2=2$, второе — полуплоскость выше параллельной ей прямой $x_1+x_2=6$. Эти две полуплоскости в принципе не пересекаются: любая точка, для которой сумма координат не превышает $2$, автоматически имеет сумму координат меньше $6$, а значит не может одновременно удовлетворять второму ограничению. Допустимая область — пустое множество, у задачи нет ни одного допустимого решения, вопрос об оптимуме в такой ситуации попросту не имеет смысла — задача несовместна.

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

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

Приведение к стандартной форме и классические примеры

Интуиция

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

Определение

Определение (дополнительная переменная, slack variable). Неравенство $a^\top x \le b$ эквивалентно системе

$$a^\top x + s = b, \qquad s \ge 0$$

где $s$ — дополнительная (слэк-) переменная, доопределённая так, чтобы уравнение выполнялось. Аналогично неравенство $a^\top x \ge b$ приводится к равенству через избыточную переменную (surplus variable) $e \ge 0$: $a^\top x - e = b$. Значение $s=0$ (или $e=0$) означает, что исходное неравенство выполняется как равенство — ограничение активно (связывающее, binding); значение $s>0$ означает, что ограничение выполняется со строгим запасом — оно неактивно в данной точке.

Обрати внимание на терминологическую перекличку с прошлым уроком: условие «ограничение активно тогда и только тогда, когда его дополнительная переменная равна нулю» — это не что иное, как условие дополняющей нежёсткости (complementary slackness) из KKT-условий урока 279, просто выраженное явно через дополнительную переменную, а не через множитель Лагранжа. В следующем примере мы увидим это на конкретных числах.

Примеры

Пример 1: перевод одного неравенства. Ограничение $x_1+2x_2\le10$ переписывается как $x_1+2x_2+s=10$, $s\ge0$. Если, например, $x_1=2$, $x_2=3$, то $s=10-2-6=2$ — при таких значениях переменных решения остаётся запас в $2$ единицы неиспользованного ресурса.

Пример 2: полная стандартная форма задачи Wyndor Glass. Вводя по одной дополнительной переменной на каждое из трёх неравенств, перепишем всю задачу как систему равенств:

Подставим найденный ранее оптимум $(x_1,x_2)=(2,6)$: $s_1=4-2=2$ (цех 1 использует только $2$ из $4$ доступных единиц мощности — ограничение неактивно); $s_2=12-2\cdot6=0$ (цех 2 загружен полностью — ограничение активно); $s_3=18-(3\cdot2+2\cdot6)=18-18=0$ (цех 3 тоже загружен полностью — ограничение активно). Именно два активных ограничения (при двух переменных решения) и определили точку пересечения, которая оказалась оптимальной вершиной — снова прямая иллюстрация дополняющей нежёсткости KKT из урока 279: там, где множитель Лагранжа ограничения положителен, дополнительная переменная (аналог самого ограничения-неравенства) равна нулю, и наоборот.

Пример 3: транспортная задача. Два завода, $A$ и $B$, производят один и тот же товар с суточным выпуском $30$ и $20$ единиц соответственно (суммарное предложение — $50$). Три склада, $1$, $2$ и $3$, нуждаются в $10$, $25$ и $15$ единицах соответственно (суммарный спрос — тоже $50$, баланс соблюдён). Стоимость перевозки одной единицы товара с завода $i$ на склад $j$ задана таблицей: от $A$ — $4$, $6$, $8$ рублей на склады $1,2,3$ соответственно; от $B$ — $5$, $3$, $7$ рублей. Обозначим $x_{ij}\ge0$ — объём перевозки с завода $i$ на склад $j$. Задача:

Обрати внимание на особенность транспортной задачи: все её ограничения — равенства с самого начала, дополнительные переменные тут просто не нужны, задача и так в форме, удобной для алгебраических методов. Построим одно допустимое (не обязательно оптимальное — поиск настоящего оптимума транспортной задачи заслуживает отдельного алгоритма и станет естественным продолжением темы после симплекс-метода) решение методом «северо-западного угла»: сначала максимально заполняем перевозку $A\to1$: $x_{A1}=\min(30,10)=10$ (остаток завода $A$ — $20$, спрос склада $1$ закрыт); затем $A\to2$: $x_{A2}=\min(20,25)=20$ (завод $A$ исчерпан, у склада $2$ остаётся потребность в $5$); затем $B\to2$: $x_{B2}=\min(20,5)=5$ (у завода $B$ остаётся $15$, склад $2$ закрыт); наконец $B\to3$: $x_{B3}=\min(15,15)=15$ (оба ресурса исчерпаны одновременно). Остальные переменные равны нулю: $x_{A3}=0$, $x_{B1}=0$. Проверка: $10+20+0=30$ ✓, $0+5+15=20$ ✓, $10+0=10$ ✓, $20+5=25$ ✓, $0+15=15$ ✓ — решение полностью допустимо. Стоимость: $4\cdot10+6\cdot20+3\cdot5+7\cdot15=40+120+15+105=280$ рублей.

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

Стандартная форма с дополнительными переменными — это в точности тот вид, который принимают на входе промышленные солверы линейного программирования: функция scipy.optimize.linprog из экосистемы Python или библиотека PuLP внутри себя оперируют именно такой алгебраической записью, а пользователю остаётся лишь корректно задать $c$, $A$, $b$. Транспортная задача заслуживает отдельного внимания за пределами логистики: её структура — минимизация суммарной «стоимости перемещения массы» при ограничениях баланса между источниками и приёмниками — практически дословно совпадает со структурой задачи вычисления расстояния оптимального переноса (optimal transport, расстояние Вассерштейна), которое в последние годы активно используется в машинном обучении — для сравнения распределений вероятностей, в генеративных моделях (Wasserstein GAN, «Вассерштейновская генеративно-состязательная сеть») и при выравнивании эмбеддингов между доменами. Дискретная формулировка задачи оптимального переноса — это в буквальном смысле транспортная задача линейного программирования с массой в узлах распределения вместо физического товара на складах.

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

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

Задание 1: Запиши в стандартной форме ЛП задачу: максимизировать прибыль $40x_1+30x_2$ при ограничении на труд $2x_1+x_2\le40$ и на материал $x_1+2x_2\le50$, $x_1,x_2\ge0$. Укажи явно $c$, $A$, $b$.

Задание 2: Найди все вершины допустимой области $x_1\le5$, $x_2\le6$, $x_1+x_2\le8$, $x_1,x_2\ge0$.

Задание 3: Для области из задания 2 вычисли $Z=2x_1+3x_2$ в каждой вершине и найди максимум.

Задание 4: Переведи ограничение $x_1+x_2\le8$ в равенство с дополнительной переменной и найди значение этой переменной в точке $(2,6)$.

Задание 5: Приведи неравенство $3x_1-2x_2\ge4$ к стандартному виду (через умножение на $-1$ и избыточную переменную).

Задание 6: Проверь, является ли точка $(3,3)$ допустимой для ограничений $x_1+2x_2\le10$, $2x_1+x_2\le10$, $x_1,x_2\ge0$.

Задание 7: Определи, совместна ли система ограничений $x_1+x_2\le2$, $x_1+x_2\ge6$, $x_1,x_2\ge0$. Объясни почему.

Задание 8: Для задачи $\text{maximize } x_1+x_2$ при $x_1-x_2\le2$, $x_1,x_2\ge0$ определи, ограничена ли задача.

Задание 9: Найди вершины треугольника $x_1\ge0$, $x_2\ge0$, $2x_1+x_2\le8$ и вычисли в них $Z=5x_1+4x_2$, чтобы найти максимум.

Задание 10: Задачу минимизации $\text{minimize } 3x_1+2x_2$ при $x_1+x_2\ge5$, $x_1,x_2\ge0$ преобразуй в задачу максимизации в стандартной форме.

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

Задание 11: Реши графически (переборои вершин) задачу $\text{maximize } 4x_1+3x_2$ при $2x_1+x_2\le10$, $x_1+3x_2\le15$, $x_1,x_2\ge0$.

Задание 12: Реши задачу минимизации $\text{minimize } 2x_1+5x_2$ при $x_1+x_2\ge4$, $x_1+3x_2\ge6$, $x_1,x_2\ge0$.

Задание 13: Для оптимума $(3,4)$ из задания 11 определи, какие из двух ограничений активны, и свяжи это с дополняющей нежёсткостью KKT из урока 279.

Задание 14: Вычисли значения дополнительных переменных $s_1,s_2$ в оптимуме $(3,4)$ из задания 11.

Задание 15: Вычисли значения тех же дополнительных переменных $s_1,s_2$ в начале координат $(0,0)$ и объясни их экономический смысл.

Задание 16: Рассмотри ту же допустимую область, что в задании 11, но с целевой функцией $\text{maximize } 2x_1+x_2$. Проверь, не параллельна ли она одному из ограничений, и опиши множество оптимальных решений.

Задание 17: Докажи неограниченность задачи $\text{maximize } x_1+2x_2$ при $-x_1+x_2\le2$, $x_1,x_2\ge0$, предъявив явное направление роста.

Задание 18: Определи, совместна ли система $x_1+x_2\le3$, $x_1+x_2\ge7$, $x_1,x_2\ge0$.

Задание 19: Запиши полную стандартную форму (с дополнительными переменными) для задачи из задания 11, явно выписав $c$, ограничения-равенства и условия неотрицательности.

Задание 20: Компании нужно распределить вычислительный бюджет в $100$ GPU-часов между обучением модели $A$ (прирост качества $0{,}8$ за час, но не более $60$ часов доступно по инфраструктурным ограничениям) и модели $B$ (прирост качества $0{,}5$ за час, не более $80$ часов). Составь и реши задачу ЛП на максимизацию суммарного прироста качества.

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

Задание 21: Восстанови доказательство теоремы об оптимуме в вершине: почему значение линейной функции в произвольной точке многогранника не может превышать её максимального значения по вершинам?

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

Задание 23: Покажи, что неограниченность задачи из задания 17 формально связана с существованием направления $d$, вдоль которого допустимость сохраняется, а целевая функция растёт: проверь, что $d=(1,1)$ удовлетворяет $-d_1+d_2\le0$ и $c^\top d>0$ для $c=(1,2)$.

Задание 24: Заводы $A$ (запас $25$) и $B$ (запас $35$) снабжают склады $1$ ($15$), $2$ ($20$), $3$ ($25$) с затратами $c_{A1}=3,c_{A2}=7,c_{A3}=6,c_{B1}=5,c_{B2}=2,c_{B3}=4$. Проверь допустимость плана $x_{A1}=15,x_{A2}=10,x_{A3}=0,x_{B1}=0,x_{B2}=10,x_{B3}=25$ и вычисли его стоимость.

Задание 25: Сформулируй (без решения) стандартную форму ЛП для распределения облачного бюджета $B$ рублей между двумя сервисами инференса с ценами за запрос $p_1,p_2$, лимитами пропускной способности $u_1,u_2$ запросов в час и целью максимизировать суммарное число обработанных запросов в час.

Задание 26: Портфель из двух активов с ожидаемой доходностью $8\%$ и $12\%$: веса $w_1+w_2=1$ (равенство), $w_2\le0{,}4$ (ограничение на долю более рискового актива), $w_1,w_2\ge0$. Найди веса, максимизирующие ожидаемую доходность.

Задание 27: Объясни своими словами, почему дискретная формулировка расстояния оптимального переноса (optimal transport, расстояние Вассерштейна) между двумя распределениями по структуре совпадает с транспортной задачей ЛП из этого урока.

Задание 28: В задаче с переменной $z$, не ограниченной по знаку (может быть отрицательной), участвующей в ограничении $z+y\le5$, $z\le3$, $y\ge0$, с целью $\text{maximize } z+2y$, покажи, как привести $z$ к стандартной неотрицательной форме через подстановку $z=z^+-z^-$.

Задание 29: Проверь, что в оптимальной вершине $(2,6)$ задачи Wyndor Glass ровно две (то есть столько же, сколько переменных решения) из трёх ограничений активны, и сформулируй общее наблюдение о количестве активных ограничений в невырожденной вершине.

Задание 30: Своими словами опиши весь путь от словесной формулировки задачи распределения вычислительного бюджета между ML-сервисами (как в задании 20 или 25) до готового решения: какие идеи этого и прошлых уроков курса задействованы на каждом шаге?

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

Ошибка 1. Путают допустимую область (многогранник ограничений) с самой целевой функцией, пытаясь «максимизировать» ограничение вместо цели.

Как выглядит: при решении задачи ученик подставляет коэффициенты ограничения в формулу для линии уровня вместо коэффициентов $c_1,c_2$ целевой функции.

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

Как правильно: чётко выделять целевую функцию (после слова maximize/minimize) отдельно от системы ограничений и всегда проверять направление сдвига линии уровня именно по коэффициентам целевой функции, а не по коэффициентам произвольного ограничения.

Ошибка 2. Считают, что оптимум может находиться где-то внутри многогранника, а не обязательно на его границе или в вершине.

Как выглядит: попытка найти оптимум, приравняв градиент целевой функции к нулю (как в задачах без ограничений урока 278), хотя градиент линейной функции — это просто константа $c$, никогда не равная нулю (если $c\ne0$).

Почему возникает: привычка из безусловной оптимизации, где решение действительно ищется через $\nabla f(x)=0$; для линейной функции такой подход попросту неприменим, потому что у неё нет ни одной стационарной внутренней точки.

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

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

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

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

Как правильно: прежде чем перебирать вершины, явно проверить, ограничена ли допустимая область целиком (или хотя бы в направлении вектора $c$); если найдётся допустимое направление $d$ с $c^\top d>0$, вдоль которого можно двигаться бесконечно без нарушения ограничений, задача неограничена — конечного оптимума нет.

Ошибка 4. Теряют знак при переводе неравенства $\ge$ в стандартную форму $\le$, забывая, что умножение неравенства на отрицательное число меняет его направление.

Как выглядит: неравенство $3x_1-2x_2\ge4$ механически переписывается как $-3x_1+2x_2\ge-4$ вместо $-3x_1+2x_2\le-4$ — знак самого неравенства при умножении на $-1$ не поменяли.

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

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

Ошибка 5. Путают дополнительную (slack) переменную с переменной решения по смыслу, приписывая ей содержательную «полезность» наравне с $x_1, x_2$.

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

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

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

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

Как выглядит: при графическом решении путают прямую $c_1x_1+c_2x_2=k$ (линию одинакового значения цели) с одной из прямых-ограничений $a^\top x=b$ и пытаются найти пересечение линии уровня с самой собой.

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

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

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

• Задача линейного программирования в стандартной форме — это $\text{maximize } c^\top x$ при $Ax\le b$, $x\ge0$: линейная целевая функция при линейных ограничениях-неравенствах и неотрицательности переменных.

• Допустимая область задачи ЛП всегда является выпуклым многогранником — пересечением конечного числа полупространств, как в уроке 277 про выпуклые множества.

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

• Именно эта теорема лежит в основе симплекс-метода следующего урока: вместо перебора бесконечной допустимой области достаточно перебрать конечный набор вершин многогранника.

• Графическое решение задач с двумя переменными строится через нахождение допустимого многоугольника (пересечение полуплоскостей) и параллельный сдвиг линии уровня целевой функции до последней точки контакта с этим многоугольником.

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

• Дополнительные переменные (slack variables) переводят неравенство $a^\top x\le b$ в равенство $a^\top x+s=b$, $s\ge0$; равенство нулю дополнительной переменной означает, что соответствующее ограничение активно в данной точке — прямая связь с дополняющей нежёсткостью KKT из урока 279.

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

• В невырожденной вершине задачи с $n$ переменными решения ровно $n$ ограничений активны одновременно — их пересечение и задаёт вершину как единственную точку.

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

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

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

Сегодняшний урок напрямую опирается на два предыдущих. Из урока 277 про выпуклые множества нужно понимание того, что полупространство — выпуклое множество, а пересечение конечного числа полупространств образует многогранник (полиэдр), тоже выпуклый по теореме о пересечении выпуклых множеств. Каждое линейное ограничение задачи ЛП — это ровно такое полупространство, а вся допустимая область — их пересечение. Из урока 278 про выпуклые функции важно осознание того, что линейная функция $c^\top x$ одновременно и выпукла, и вогнута (неравенство Йенсена для неё выполняется как равенство при любых $x,y,\lambda$) — а значит, у задачи ЛП нет проблемы ложных локальных оптимумов в принципе, теорема о совпадении локального и глобального минимума из урока 278 выполняется автоматически. Из урока 279 про условия KKT пригодилось понятие дополняющей нежёсткости — активные и неактивные ограничения, которые мы сегодня увидели в явном численном виде через дополнительные переменные.

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

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

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

🤖 Распределение вычислительных ресурсов в ML. При развёртывании нескольких моделей на общем кластере серверов распределение ограниченного бюджета GPU-часов, памяти и пропускной способности между задачами инференса и дообучения — прямая задача ЛП, как в заданиях 20 и 25 этого урока: максимизировать суммарную полезность при жёстких инфраструктурных ограничениях.

💰 Финансовое машинное обучение. Простейшая линейная оптимизация портфеля — распределение капитала между активами при линейных ограничениях на суммарный вес и допустимую долю риска (задание 26) — частный случай задачи ЛП; более сложная версия с квадратичным риском (модель Марковица) выходит за рамки чистого линейного программирования, но многие практические ограничения (лимиты на сектор, на отдельный актив, на оборот) остаются линейными и добавляются к любой более сложной модели именно в этой форме.

📐 Классификация с линейными ограничениями и оптимальный перенос. Некоторые постановки задач классификации с жёсткими линейными ограничениями (например, поиск допустимой разделяющей гиперплоскости как задачи выполнимости, а не оптимизации) сводятся к проверке совместности системы линейных неравенств — ровно тому вопросу feasible/infeasible, который мы разбирали графически. А вычисление расстояния оптимального переноса (Вассерштейна) между дискретными распределениями — это буквально транспортная задача ЛП, где вместо физического товара перемещается вероятностная масса.

🏭 Логистика и планирование производства. Транспортная задача из этого урока и обобщающая её задача о распределении ресурсов остаются рабочим инструментом промышленного планирования, снабжения и логистики уже восемьдесят лет — просто спрятанным сегодня внутри современных ERP-систем и облачных платформ маршрутизации.

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

• В 1975 году Леонид Канторович стал единственным советским учёным, когда-либо получившим Нобелевскую премию по экономике — «за вклад в теорию оптимального распределения ресурсов», совместно с голландско-американским экономистом Тьяллингом Купмансом. Примечательно, что Канторович пришёл к идее линейного программирования не из экономической теории, а из сугубо прикладной задачи распределения сырья на ленинградском фанерном тресте в 1939 году — за восемь лет до того, как ту же математическую структуру независимо переоткрыл Джордж Данциг в США.

• Название «линейное программирование» — историческое недоразумение с точки зрения современного слуха: слово programming в 1940-х годах в военном и плановом контексте означало «составление расписания» или «планирование», а не написание компьютерного кода (который в те годы, в сущности, ещё не существовал в современном виде) — правильнее было бы переводить термин как «линейное планирование», но исторически сложившееся название прижилось и осталось неизменным.

• Симплекс-метод Данцига, несмотря на то что в теории существуют примеры (специально сконструированные, редко встречающиеся на практике), где он перебирает экспоненциальное по размеру задачи число вершин, на подавляющем большинстве реальных задач работает исключительно быстро — эмпирически число шагов растёт линейно или слабо-полиномиально от размера задачи, а не экспоненциально. Это долго оставалось загадкой для теоретиков, пока в 2001 году Дэниел Шпильман и Шанг-Хуа Тенг не объяснили этот феномен через понятие «сглаженного анализа» (smoothed analysis) — метода, который сегодня используется для объяснения практической эффективности и других алгоритмов, формально имеющих плохую наихудшую сложность.

• Транспортная задача — частный случай ЛП, который исторически возник даже раньше общей теории: французский математик Гаспар Монж поставил близкую по духу задачу об оптимальном перемещении грунта ещё в 1781 году, за полтора века до Канторовича и Данцига, хотя строгого алгоритма решения тогда предложено не было. Современное название «задача Монжа — Канторовича» для теории оптимального переноса — прямое признание этой исторической связи, и именно та же теория лежит сегодня в основе вычисления расстояния Вассерштейна в машинном обучении.

Лайфхаки

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

• Чтобы быстро заподозрить неограниченность задачи, посмотри, есть ли у каждой переменной решения хотя бы одно верхнее ограничение (не считая $x\ge0$); если переменная, коэффициент которой в целевой функции положителен (при максимизации), нигде не ограничена сверху ни одним неравенством, задача почти наверняка неограничена.

• Для проверки несовместности системы ограничений быстро просканируй пары неравенств на противоречие в духе «$x_1+x_2\le a$» и «$x_1+x_2\ge b$» с $a

• На практике для задач с числом переменных больше двух-трёх используй готовые солверы, а не ручной перебор вершин: scipy.optimize.linprog в Python принимает задачу почти в той же стандартной форме, что разобрана в этом уроке (просто передай c, A_ub, b_ub и ограничения неотрицательности), а PuLP удобен, если хочется описывать задачу в более читаемом, декларативном виде ближе к математической записи.

• Значение дополнительной переменной в найденном оптимуме — это готовый диагностический инструмент: большие положительные значения $s_i$ сигнализируют, что соответствующий ресурс использован не полностью и увеличение его лимита не изменит найденное решение, тогда как нулевое значение $s_i$ показывает, какой именно ресурс на самом деле ограничивает результат и заслуживает первоочередного внимания при расширении мощностей.

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