Канторович: оптимизация раскроя фанеры

Задача, которую принесли

В 1938 году в лабораторию Ленинградского университета обратился фанерный трест. Задача была скучная до неприличия.

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

Двадцатишестилетний профессор Леонид Канторович — он окончил университет в восемнадцать, профессором стал в двадцать два — взялся посчитать и увидел, что задача не решается ничем из известного.

Почему не решается

Запишем её. Пусть $x_{ij}$ — доля времени, которое станок $i$ тратит на сорт $j$, $a_{ij}$ — его производительность. Тогда надо

$$\max\ z \quad\text{при}\quad \sum_i a_{ij}x_{ij}\geqslant c_j z,\qquad \sum_j x_{ij}\leqslant 1,\qquad x_{ij}\geqslant 0 .$$

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

Классический анализ не работает. Метод ЛагранжаЖозеф Луи Лагранжфранцузский математик и механик итальянского происхождения · 1736–1813Написал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней. ищет точку, где производная обращается в нуль. У линейной функции производная не обращается в нуль нигде. Максимум сидит не внутри области, а в углу многогранника, заданного неравенствами, и добраться до него дифференцированием нельзя.

Перебор углов не работает тоже. Углов у такого многогранника — число сочетаний из числа ограничений, и оно растёт быстрее любого разумного счёта.

Задача выглядела как арифметическая, а оказалась новой.

Разрешающие множители

Идея Канторовича: не искать план прямо, а искать числа при ресурсах.

Припишем каждому сорту $j$ число $u_j$ — во сколько мы «оцениваем» единицу этого сорта. Тогда каждому станку выгодно работать на том сорте, где произведение $a_{ij}u_j$ наибольшее. Канторович доказал: числа $u_j$ можно подобрать так, что план, оптимальный для каждого станка по отдельности при этих оценках, оптимален и в целом.

Он назвал их разрешающими множителями. Сегодня их называют двойственными переменными или теневыми ценами.

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

	сорт A	сорт B
станок I	10	20
станок II	30	20

Наивное решение «каждый делает то, что у него лучше» даёт: I на B (20 единиц B), II на A (30 единиц A) — комплектов 20, и десять единиц A пропали.

Оптимум: станок II целиком на A даёт 30 A; станку I надо дать 30 B, на что уходит всё его время (30 > 20) — не выходит. Пусть II работает на A долю $t$, а долю $1-t$ на B; I весь на B. Тогда $A = 30t$, $B = 20 + 20(1-t)$. Приравняем: $30t = 40 - 20t$, $t = 0{,}8$, комплектов 24 вместо 20.

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

Двойственность

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

$$\max\{\,c^{\mathsf T}x\ :\ Ax\leqslant b,\ x\geqslant 0\,\} \;=\; \min\{\,b^{\mathsf T}u\ :\ A^{\mathsf T}u\geqslant c,\ u\geqslant 0\,\}.$$

Прямая задача спрашивает: как построить план? Двойственная: сколько на самом деле стоит каждый ресурс? И это один и тот же вопрос, заданный с двух сторон.

Отсюда сразу следует полезное правило: ресурс, который в оптимуме не израсходован до конца, имеет нулевую оценку, а положительную оценку имеет только дефицитный ресурс. Стоимость — это не свойство вещи, а свойство её нехватки при данном плане.

Почему за это было страшно

Работа вышла в 1939 году отдельной брошюрой Ленинградского университета — «Математические методы организации и планирования производства», сто страниц, тираж крошечный. И почти не была замечена.

Причина не в математике. В советской политэкономии цена определялась затратами труда; всё, что выводило цену из редкости и предельной полезности, называлось «буржуазным маржинализмом». А двойственные оценки Канторовича — это ровно оценки по редкости.

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

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

Задача Монжа

У линейного программирования есть частный случай, который старше его на полтора века.

В 1781 году Гаспар Монж поставил «задачу о выемках и насыпях»: как перевезти грунт из карьеров в насыпи с наименьшей суммарной работой? МонжГаспар Монжфранцузский математик, государственный деятель · 1746–1818Восемнадцатилетним решил чертежом за часы задачу, на которую уходили сутки арифметики, — и метод немедленно засекретили. Основал Политехническую школу, из которой вышла вся французская математика XIX века. искал отображение — кто куда едет, и на этом задача сто пятьдесят лет стояла.

В 1942 году Канторович в короткой заметке «О перемещении масс» заменил отображение мерой на произведении: не «каждая точка едет в одну точку», а «сколько массы из окрестности $x$ попало в окрестность $y$». Задача стала линейной, и у неё появилась двойственная — с оценками, которые теперь называют потенциалами Канторовича.

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

С названием расстояния, которое отсюда получается, вышла история поучительная. В русской традиции это метрика Канторовича (или Канторовича — Рубинштейна, 1958). В западной литературе её называют расстоянием Васерштейна: Р. Л. Добрушин в 1970 году сослался на работу Л. Н. Васерштейна 1969 года и дал метрике его имя. Когда Добрушину в 1975-м указали, что метрика канторовичевская, он согласился и написал об этом сам, — но название уже прижилось. Так что в каждой второй статье по генеративным моделям сегодня считают метрику Канторовича под чужой фамилией.

Признание

Симплекс-метод, практический способ решать такие задачи, независимо построил Джордж Данциг в 1947 году, и на Западе линейное программирование выросло из его работы, а не из работы Канторовича, о которой там узнали в пятидесятых.

Дальше: Сталинская премия 1949 года — за работы по функциональному анализу; Ленинская премия 1965 года — вместе с В. В. Новожиловым и В. С. Немчиновым; Нобелевская премия по экономике 1975 года — вместе с Тьяллингом Купмансом, за вклад в теорию оптимального распределения ресурсов. Данцига в списке не оказалось, и несправедливым это считают до сих пор.

Канторович — единственный советский лауреат Нобелевской премии по экономике. О том, что он делал в Сибири в промежутке между двумя премиями, речь пойдёт через несколько точек.

Задача. В примере выше найдите разрешающие множители $u_A$, $u_B$ и проверьте, что при них обоим станкам безразлично или выгодно то, что они делают в оптимуме.
(Ответ: возьмём $u_A = u_B = 1/2$ — тогда «стоимость» комплекта равна 1. Станок II: $30\cdot\tfrac12 = 15$ на A и $20\cdot\tfrac12=10$ на B, ему выгодно A — он и работает на A большую часть времени. Станок I: $10\cdot\tfrac12=5$ против $20\cdot\tfrac12=10$, выгодно B — он весь на B. Остаток времени станка II уходит на B потому, что комплект требует обоих сортов: оценки задают направление, а связывает их условие комплектности.)

Соседние точки: Монж (1781) → Канторович (1939) → Данциг (1947) → Хачиян (1979); продолжение — Академгородок.