VIVOS VOCO: Л.В. Канторович, "Об истории линейного программирования"

Л.В. Канторович

Об истории
линейного программирования
(Ответы на вопросы Сони Брентьес)

Глубокоуважаемая Соня Брентьес!

Прошу извинить за задержку ответа на Ваши письма, связанную с занятостью другими делами, хотя Вашему намерению написать историю вопроса вполне сочувствую и готов помочь Вам.

Отвечаю на Ваши вопросы:

1) Почему Вы занялись в 1939 году линейными оптимальными задачами?

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

2) Занимались ли Вы до 1939 года подобными проблемами?

Такими проблемами я непосредственно не занимался, но для интереса к проблеме и занятий ею, имело значение следующее.
Данная работа 1939 года является примерно 60-ой в списке моих научных публикаций с 1929 года, в частности, для меня повидимому имели значение следующие предыдущие циклы работ:
а) Работы по вычислительной математике, в частности, книга «Приближенные методы высшего анализа» (совм. с В.И. Крыловым изд. 1, 1936 г.).
б) Некоторое число связанных с предыдущим циклом работ по применению приближенных методов в различных задачах механики. Это было связано с моей педагогической деятельностью в инженерных вузах.
в) Цикл работ по ункциональному анализу.
г) Интерес, правда в то время дилетантский, к экономике (впрочем, во время студенческой практики в 1929 году, я работал несколько месяцев экономистомстатистиком).

3) Знали ли Вы о работах Фурье, Фаркаша, Минковского и т.д.?

С этими работами я познакомился позднее.

4) Кто кроме Вас и проф. Гавурина в Ленинграде и в СССР занимался линейной оптимизацией?

В моей книге указано, что расчет примера, относящегося к задаче фанерного треста, методом разрешающих множителей был проведен А.И. Юдиным. Абрам Исакович Юдин был тогда моим аспирантом по функциональному анализу. Очень способный молодой ученый, погиб на фронте в начале войны в 1941 году.
Этот расчет он выполнил самостоятельно и квалифицированно, но специально этими проблемами не заинтересовался.
М.К. Гавурина я привлек к работе в 1940 году, в связи с рассмотрением транспортной задачи. Наша работа, опубликованная в 1949 году, была написана фактически в конце 1940 года и тогда же докладывалась нами в нескольких учреждениях, в том числе в секции математики ленинградского Дома ученых.
Абстрактный вариант транспортной задачи - работа о перемещении масс, включая теорему о потенциале и основу метода потенциалов, опубликована мною в 1942 году в Докладах Академии наук СССР (переведена в 1958 году журналом Management Science).
Других советских работ по линейной оптимизации (кроме Толстого, которую Вы знаете) не могу указать. Были некоторые работы по системам неравенств, например, работа Школьникова.

5) Каков был резонанс на собраниях, в которых Вы говорили о значении этого класса экстремальных задач?

На этих двух собраниях (а также на собрании в 1938 году, где я рассказывал еще только постановку задачи фанерного треста, и других), доклады вызвали положительное отношение, но все значение их вряд ли было оценено. Некоторые высказывавшиеся возражения, связанные с трудностями практического приложения, обсуждаются в моей книге 1939 года.
Некоторые из этих докладов вызвали попытки практического применения этих методов. Отмечу начатую в 1940?41 гг. аспирантом Лен[инградского] политехнического института А.Ф. Метсом работу по использованию метода разрешающих множителей для загрузки прокатных станов, прерванную войной. Эта работа была опубликована им позднее - в 50х годах, а фактически широкое применение методов линейного программирования в этой задаче началось в 1960х годах.
Первое доведенное до использования применение касается рационального раскроя, относится к 1948–1950 годам (книга моя и В.А. Залгаллера).
Применения в техникоэкономических проблемах встречали скорее трудности и неверие, чем принципиальные возражения. С последними пришлось встретиться по отношению к применениям в плановоэкономических вопросах. Эта дискуссия отражена в печати (например, «Математики и экономисты за круглым столом», 1965).

6) Вывели ли Вы Лагранжевский алгорифм для решения экстремальных задач с дополнительными условиями посредством переработки Вашего алгорифма?

В своей заметке 1940 года в ДАН я указываю, что рассматриваемый мною подход позволяет не только наново вывести Лагранжев метод (что, конечно не особенно интересно), но получить его в более общей форме - в этой формулировке он действителен и для нерегулярного случая (классический метод Лагранжа предполагает дифференцируемость функций). Я возвращаюсь к этому вопросу в недавней заметке (1967 года), совместной с Г.П. Акиловым и Г.С. Рубинштейном.

7) Каковы были Ваши контакты с А.Н. Толстым?

Я не встречался с ним. С одной из его статей, которая цитируется в моей работе с М.К. Гавуриным, я познакомился уже в процессе работы над темой. В работе А.Н. Толстого имеется ряд практических приемов решения задачи, но недостаточно эффективных и не универсальных. Общая характеристика оптимального плана транспортировки и эффективные универсальные методы были даны впервые в указанных наших работах (в 1940 году).
Впоследствии в послевоенное время в 1947–48 гг. я знакомился с работами по планированию перевозок, которые велись в Министерстве путей сообщения. Работы по реализации оптимальных планов перевозок методами линейного программирования, в частности на основе наших работ (на автотранспорте и других видах), начались в конце 50х годов.

8) Как Вы оцениваете сами значение Ваших работ для линейной оптимизации?

Мне трудно говорить о личном вкладе, но в целом первые работы по линейному программированию открыли новое актуальное направление прикладной математики, существенно обогатившее ее методы для решения техникоэкономических задач, задач исследования операций, теории управления, плановоэкономических и других, наметили пути дальнейших обобщений (нелинейное программирование, целочисленное программирование и др.), имели и общематематическое значение. Еще большее значение эти работы и их последующее развитие имели для экономической науки, в особенности в социалистических странах, где они не только обогатили науку планирования методами оптимального планирования, весьма эффективными на всех уровнях, но дали новый объективный подход к изучению природы и структуры экономических показателей и методы их исчисления (объективно обусловленные оценки, цены оптимального плана).
Я Вам посылаю мои биографии, опубликованные в связи с моим 50летием и 60летием, а также некоторые статьи, написанные в связи с этим. В частности, содержательную статью покойного Ал. Л. Вайнштейна в связи с 25летием линейного программирования. Посылаю также свою фотографию. Просил М.К. Гавурина также послать фотографию Вам.

С уважением

Л. Канторович

24.2.75 г.