4. 14. 100 Линейное программирование Канторовича

4.14 Экономика

4.14.100 Линейное программирование Канторовича


Математик, экономист, профессор Ленинградского университета, Высшего инженерно-технического училища ВМФ, Новосибирского государственного университета, академик АН СССР и ряда зарубежных академий, почетный доктор многих университетов мира; основатель и начальник математико-экономического отдела, заместитель директора Института математики им. С.Л. Соболева СО АН СССР; лауреат Сталинской и двух Ленинских премий; кавалер двух орденов Ленина, трех орденов Трудового Красного Знамени, орденов «Знак Почета», Отечественной войны 1-й степени и медалей — Леонид Витальевич Канторович (1912—1986) является автором более 200 научных работ и полутора десятка монографий по дескриптивной теории функций и теории множеств, функциональному анализу и теории экстремальных задач, по вычислительной математике.

Мировую известность Канторовичу принесли труды по математической экономике, за которые он был удостоен в 1975 г. Нобелевской премии по экономике (совместно с американским математиком Т.Ч. Купмансом) — «за вклад в теорию оптимального распределения ресурсов в экономике».


Лучше всего начать рассказ о главном научном достижении Л.В. Канторовича с двух практических задач, решенных математиком и ставших яркой иллюстрацией новой науки — математической экономики.

Канторович «мог служить отличным примером того, кого надо было бы называть «математиком-прикладником».

Его чутье в прикладных вопросах и обширнейшие контакты с инженерами, военными, экономистами сделали его необычайно популярным среди тех, кто применял математику. Сам он говорил, что чувствует себя не только математиком, но и инженером» (А.М. Вершик).

В 1959 г. ученому поручили найти оптимальные тарифы такси в пределах страны. Математик с 20 сотрудниками, детально проанализировав огромный массив данных, за неделю выдал свои рекомендации. В частности, предложил снизить тариф и ввести небольшую плату за посадку. Новые тарифы были внедрены и использовались до 1990-х гг.

А за двадцать лет до этого, в 1938 г. Канторовича, консультанта Ленинградского фанерного треста, руководство треста попросило рассчитать оптимальную загрузку оборудования. Методик для подобных расчетов в мире не было. А если и были классические методы, применяемые в математическом анализе, они требовали решения десятков тысяч или даже миллионов систем уравнений. Ученый блестяще справился с поставленной задачей.

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

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

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

Производители фанеры получили прибыль, а мировая наука новую дисциплину — линейное программирование (это название появилось позже в трудах американского математика Дж.Б. Данцига, разработавшего аналогичный алгоритм — т.н. симплекс-метод).

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

Обобщив «фанерный» опыт, в 1939 г. Канторович опубликовал работу «Математические методы организации и планирования производства». В ней впервые в истории были сформулированы принципы планирования и построения производственного процесса на основе математических моделей.

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

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

На основе своих трудов ученый создал математические методы оптимального планирования, эффективные как на микроуровне (предприятие), так и на макроуровне (корпорация или государство). Канторович открыл объективный механизм взаимосвязи оптимальных решений и оптимальных цен в планировании.

Созданную ученым математическую экономику оценили у нас после того, как аналогичные результаты стали использоваться на Западе. Но при этом никто из зарубежных ученых не оспаривал приоритета русского математика. «Работа Канторовича 1939 г. содержит почти все области приложений, известные в 1960 г.», — соглашались они. Т.е. фактически русский ученый опередил развитие мировой науки на 20 лет.

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

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

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

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

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

В 1965 г. исследования Л.Д. Канторовича в области экономико-математических методов были удостоены Ленинской премии (вместе с академиком В.С. Немчиновым и профессором В.В. Новожиловым), а в 1975 г. Канторович вместе с американским экономистом Т. Купмансом был отмечен Нобелевской премией по экономике — за «вклад в теорию оптимального использования ресурсов».

Один из выдающихся экономистов XX в., академик СО РАН А.Г. Аганбегян назвал открытие Л.В. Канторовича «переворотом в экономике». «Жизнь подкидывает множество разнообразных проектов, которые растянуты во времени, когда нужно дисконтирование, сопоставление доходов и расходов разных периодов, когда нужно учитывать связи разных производств. И все эти вопросы, оказывается, можно четко решить» при наличии соответствующего инструментария, в данном случае — линейного программирования.