Aleksandr Andrianov

By this author

THE MAKING AND EARLY DEVELOPMENT OF LINEAR-PROGRAMMING METHODS

Issue 2 from 01.04.2017

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

1173 4

L.V. KANTOROVICH AS THE FOUNDER OF LINEAR PROGRAMMING

Issue 4 from 01.10.2009

В данной статье рассмотрена история возникновения линейного программирования из конкретных задач экономики 1930-х гг. в контексте математических исследований Л. В. Канторовича (прежде всего, его работ по функциональному анализу). Особое внимание уделено первой публикации Канторовича на эту тему - работе 1939 г. «Математические методы организации и планирования производства», родившейся в результате решения так называемой «задачи фанерного треста». Проведена оценка этой и других довоенных работ Канторовича с современной точки зрения. Кроме того затронут ряд вопросов, касающихся исследований Леонида Витальевича 1940-1960-х гг., а также развития и применения методов, появившихся в работе 1939 г. Другая обсужденная в статье тема - история признания вклада Канторовича в экономическую науку. Сейчас его приоритет в создании линейного программирования бесспорен, однако так было не всегда. В связи с этим в статье освещены те сложности, с которыми пришлось столкнуться идеям линейного программирования и их автору на пути к признанию как на родине в СССР, так и в рамках мирового научного сообщества.

1280 0