У любого завода ресурсы конечны: столько-то сырья, станков, электричества, рабочих часов. Из них можно собрать разный набор изделий — и прибыль выйдет разной. Какой план даст максимум? Перебрать все варианты невозможно: их астрономически много.
Ещё в 1939 году, до войны, ленинградский математик Леонид Канторович показал, что эту задачу можно решить математически — так родилось линейное программирование. А массовое применение в экономике метод получил уже в новосибирском Академгородке. Задача записывается коротко:
$$ \max\; c^{T} x \quad\text{при}\quad A x \le b $$
где $x$ — план производства (сколько чего выпустить), $c$ — ценность единицы каждого изделия, $A$ — сколько ресурсов уходит на изделие, $b$ — сколько ресурсов в наличии. Надо найти такой план $x$, чтобы ценность $c^T x$ была наибольшей, не выйдя за запасы.
Каждое ограничение ресурса — прямая, отсекающая часть плоскости. Вместе они вырезают многоугольник допустимых планов; оптимум всегда лежит в его вершине.
Главная красота — где прячется ответ. Оказывается, лучший план всегда сидит в углу.
Каждое ограничение «ресурса не больше, чем есть» — это прямая, которая отсекает половину плоскости. Сложи все такие ограничения — и останется многоугольник допустимых планов (всё, что физически выполнимо). А ценность $c^T x$ растёт в каком-то одном направлении: представь прямую постоянной прибыли, которая едет по многоугольнику. Последняя точка, где она ещё касается допустимой области, — это вершина (угол) многоугольника. Поэтому искать оптимум среди бесконечного множества планов не нужно: достаточно обойти вершины1. На этом и стоит знаменитый симплекс-метод.
Где работает тот же закон?
Линейное программирование сегодня везде, где делят ограниченный ресурс: в логистике и развозе грузов со складов, в энергетике, в управлении цепочками поставок, в алгоритмах маркетплейсов и в системах ИИ. Частный случай — транспортная задача Канторовича о том, как развезти грузы с минимальными затратами, — лёг в основу целой математической теории оптимального переноса.
Линейное программирование: оптимум линейной целевой функции на выпуклом многограннике ограничений достигается в вершине; основы заложил Л. В. Канторович (1939) (Wikipedia, «Linear programming»; «Leonid Kantorovich»). ↩
Самое неожиданное у Канторовича — не сам план, а цена. Спросим: насколько вырастет прибыль, если добавить одну единицу дефицитного ресурса (лишний час станка, лишнюю тонну сырья)? Этот прирост и есть цена ресурса — но не та, что на ценнике, а выведенная из самой задачи. Математически это производная оптимума по запасу ресурса:
Величины $\lambda_i$ — это двойственные множители (те самые множители Лагранжа). Канторович назвал их «объективно обусловленными оценками»: цена ресурса не назначается сверху, а объективно вытекает из того, насколько он узок. В рыночной теории то же самое зовут теневой ценой1. За эту идею — что оптимальное распределение само порождает правильные цены — Канторович получил Нобелевскую премию по экономике, единственную в истории отечественной науки.
Теневая цена: добавили единицу дефицитного ресурса — граница сдвинулась, оптимум переехал в новую вершину, прибыль выросла на λ. Это и есть цена ресурса.
Открытый вопрос
Если у каждого ресурса есть объективная цена, вытекающая из общей задачи, — почему реальные рынки так часто назначают цены иначе? Где проходит граница между «объективно обусловленной оценкой» и живой ценой, которую двигают спрос, ожидания и случай?
