Как назначить цену ресурсу

У любого завода ресурсы конечны: столько-то сырья, станков, электричества, рабочих часов. Из них можно собрать разный набор изделий — и прибыль выйдет разной. Какой план даст максимум? Перебрать все варианты невозможно: их астрономически много.

Ещё в 1939 году, до войны, ленинградский математик Леонид Канторович показал, что эту задачу можно решить математически — так родилось линейное программирование. А массовое применение в экономике метод получил уже в новосибирском Академгородке. Задача записывается коротко:

$$ \max\; c^{T} x \quad\text{при}\quad A x \le b $$

модель

где $x$ — план производства (сколько чего выпустить), $c$ — ценность единицы каждого изделия, $A$ — сколько ресурсов уходит на изделие, $b$ — сколько ресурсов в наличии. Надо найти такой план $x$, чтобы ценность $c^T x$ была наибольшей, не выйдя за запасы.

Главная красота — где прячется ответ. Оказывается, лучший план всегда сидит в углу.

Каждое ограничение «ресурса не больше, чем есть» — это прямая, которая отсекает половину плоскости. Сложи все такие ограничения — и останется многоугольник допустимых планов (всё, что физически выполнимо). А ценность $c^T x$ растёт в каком-то одном направлении: представь прямую постоянной прибыли, которая едет по многоугольнику. Последняя точка, где она ещё касается допустимой области, — это вершина (угол) многоугольника. Поэтому искать оптимум среди бесконечного множества планов не нужно: достаточно обойти вершины¹. На этом и стоит знаменитый симплекс-метод.

Где работает тот же закон?

Линейное программирование сегодня везде, где делят ограниченный ресурс: в логистике и развозе грузов со складов, в энергетике, в управлении цепочками поставок, в алгоритмах маркетплейсов и в системах ИИ. Частный случай — транспортная задача Канторовича о том, как развезти грузы с минимальными затратами, — лёг в основу целой математической теории оптимального переноса.

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

Что предполагается Метод работает, когда выполняются три условия. Их стоит держать в голове: как только одно нарушится, ответ поплывёт.

1. Расход ресурсов пропорционален выпуску: две единицы продукции требуют вдвое больше сырья, чем одна. Скидок за объём и переналадок между партиями нет.
2. Продукцию можно выпускать дробно. Полтора станко-часа и 6,5 партии — допустимый план.
3. Все запасы и удельные затраты известны заранее и не зависят от того, какой план выберут.

Считаем на числах Цех выпускает два вида фанеры. Партия первого даёт 3 тысячи рублей прибыли, партия второго — 5. Ограничений три: раскроечный станок осиливает не больше 4 партий первого вида; пресс отдаёт 12 часов, а партия второго вида забирает 2 часа; сборка располагает 18 часами, из них 3 часа уходит на партию первого вида и 2 часа — на партию второго.

$$ \max\;(3x_1 + 5x_2) \quad\text{при}\quad x_1 \le 4,\quad 2x_2 \le 12,\quad 3x_1 + 2x_2 \le 18. $$

модель

Оптимум: $x_1 = 2$, $x_2 = 6$, прибыль $f^{} = 36$ тысяч. Теперь главный вопрос — что даст лишняя* единица каждого ресурса.

Добавим один пресс-час (было 12, стало 13). Пресс отпускает второй вид до 6,5 партии, но сборка общая: $3x_1 + 2\cdot 6{,}5 \le 18$, значит $x_1 = 5/3$. Новая прибыль: $3\cdot\tfrac{5}{3} + 5\cdot 6{,}5 = 37{,}5$. Прирост 1,5 тысячи — это и есть цена пресс-часа.

Добавим час сборки (18 → 19): $x_2$ остаётся 6, $x_1$ вырастает до $7/3$, прибыль $7 + 30 = 37$. Цена часа сборки — 1 тысяча.

А пятая партия на раскроечном станке не даёт ничего: он и так недогружен — в плане $x_1 = 2$ при разрешённых четырёх. Его цена — ноль. Ресурс, которого хватает с запасом, не стоит ничего, сколько бы за него ни просили на рынке. В этом всё содержание идеи: цену задаёт не себестоимость ресурса, а то, насколько он держит план.

Записывают это так:

$$ \lambda_i = \frac{\partial f^{*}}{\partial b_i}, $$

модель

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

Где эта цена перестаёт работать Полторы тысячи за пресс-час — величина не вечная. Продолжим добавлять пресс-часы: при 18 часах решение упирается в $x_2 = 9$, $x_1 = 0$, прибыль 45 тысяч. Дальше цена падает до нуля — сборка исчерпана, пресс больше не узкое место. Теневая цена держится ровно в интервале $12 \le b_2 \le 18$ и на его границе меняется скачком. Это приближение, верное для малых добавок, а не коэффициент на все случаи.

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

Спор, который стоил Канторовичу двадцати лет Само слово «цена» в этой конструкции было опасным. По господствовавшей тогда трудовой теории стоимости цену определяют затраты труда, а здесь она выводилась из дефицитности — как на рынке. Канторович назвал свои величины «объективно обусловленными оценками»: нарочито громоздкий термин, выбранный, чтобы не произносить слово «цена». Работа 1939 года вышла тиражом около тысячи экземпляров и почти на два десятилетия осталась без продолжения; книгу «Экономический расчёт наилучшего использования ресурсов» удалось издать лишь в 1959-м. Нобелевскую премию по экономике он получил в 1975 году вместе с Тьяллингом Купмансом, пришедшим к тем же двойственным оценкам независимо — из задач морских перевозок.

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

Лекция по теме Александр Гасников, «Оптимизация в природе» — минимальные площади, шестиугольные соты и другие задачи на оптимум вне экономики.