История математического программирования

История математического программирования

Б.Т. Поляк, Институт проблем управления, Москва

Задачи математического программирования

Задача математического программирования

Задача оптимизации

Виды моделей

· детерминированные;

· вероятностные;

· игровые;

· неполные (задачи в условиях неопределенности).

Исследованием детерминированных моделей занимается математическое программирование (МП).

Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).

(

)

Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f(x) на множестве всех допустимых решений.

История математического программирования

История математического программирования в СССР: попытка анализа

1. Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России

2. Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств

3. А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)

4. А.М. Ляпунов, 1857-1918, разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации

5. Л.В. Канторович, 1912-1986, в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.

Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование.

С именем Канторовича Л.В.связаны следующие достижения:

Линейное программирование, 1939:

Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича.

Общие условия оптимальности, 1940

Техника функционального анализа, 1939-1948