Леонид Канторович: линейное программирование и премия 1975 года

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

В 1975 году Канторович разделил с Тьяллингом Купмансом премию по экономическим наукам памяти Альфреда Нобеля за исследования оптимального распределения ресурсов. Речь шла о научном методе, применимом к разным хозяйственным системам, а не о награде за успехи советской экономики в целом.

Математик, пришедший к хозяйственным задачам

Канторович родился в Петербурге в 1912 году. Он поступил в Ленинградский университет в 1926-м и стал профессором в 1934-м. Позднее его работа была связана с Сибирским отделением Академии наук и Москвой. Эта биография помогает увидеть в нём прежде всего математика, чьи интересы вышли за пределы одной дисциплины.

В автобиографии для Нобелевского фонда учёный связывал начало экономических исследований с консультацией для лаборатории фанерного треста в 1938 году. Практический вопрос об использовании оборудования привёл к более общему классу задач. В 1939 году появилась его брошюра о математических методах организации и планирования производства.

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

Что такое линейное программирование

Слово «программирование» в данном случае означает построение плана. Оно не требует, чтобы задача обязательно была связана с написанием компьютерного кода. Компьютер может помогать рассчитывать решение, но математическая постановка существует независимо от конкретной программы.

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

Разница между допустимым и оптимальным решением принципиальна. Допустимый план не нарушает заданных ограничений. Оптимальный даёт лучший результат по выбранному критерию среди всех допустимых планов. Исполнение ограничений само по себе ещё не означает, что возможности использованы наилучшим образом.

Условная мастерская: почему не стоит выбирать один продукт

Рассмотрим учебный пример, придуманный для этой статьи. Это не данные советского предприятия. Выпускаются два делимых вида продукции, А и Б. На единицу А нужны два часа оборудования и одна единица материала, на единицу Б — один час оборудования и две единицы материала. Всего доступны 100 часов и 80 единиц материала.

За единицу А результат оценивается в три условных балла, за единицу Б — в четыре. Баллы здесь служат только для сравнения вариантов. Если производить исключительно А, получится 50 единиц продукции и 150 баллов. Если исключительно Б — 40 единиц и 160 баллов. Второй вариант выглядит лучше первого, но это ещё не лучшее решение задачи.

Сочетание 40 единиц А и 20 единиц Б использует ровно 100 часов и 80 единиц материала. Результат равен 200 баллам. Оно превосходит оба однопродуктовых варианта: разные изделия по-разному расходуют два ограниченных ресурса.

Почему здесь можно говорить об оптимуме, а не просто об удачном подборе? Если количество А обозначить x, а Б — y, ограничения имеют вид 2x + y ≤ 100 и x + 2y ≤ 80. Умножим первое неравенство на 2/3, второе на 5/3 и сложим. Получится 3x + 4y ≤ 200. Любой допустимый план даёт не больше 200 баллов, а найденное сочетание достигает этого предела.

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

Почему дефицитному ресурсу нужна оценка

В примере два ограничения имеют разное значение. Дополнительный час оборудования и дополнительная единица материала не обязательно одинаково увеличивают возможный результат. Их полезность зависит от всей системы, а не только от того, сколько их сейчас имеется на складе.

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

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

Чего математический оптимум не обещает

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

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

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

За что присудили премию 1975 года

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

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

История Канторовича дополняет рассказы о таких советских теоретиках, как Лев Ландау. В обоих случаях ценность работы состоит в способе описать проблему и получить проверяемые выводы. Но предметы исследований разные: квантовые жидкости у Ландау, выбор при ограниченных ресурсах у Канторовича.

Источники

• Нобелевский фонд: факты о Леониде Канторовиче и премии 1975 года.
• Леонид Канторович: автобиография, подготовленная к присуждению премии.
• Пресс-релиз Шведской королевской академии наук от 14 октября 1975 года.
• Леонид Канторович. Mathematics in Economics: Achievements, Difficulties, Perspectives, лекция 11 декабря 1975 года.