Історія розвитку математичного програмування.

Рання історія лінійного програмування тісно пов’язана з роботами за наступними напрямами:

1) математичні та фізичні підходи до проблеми віртуальних скоростей;

2) дослідження переміщення земляних мас для побудови французьких фортець;

3) процес математизації економічної науки.

Формулювання задач лінійного програмування і створення перших методів розв’язку стимулювали конкретні економічні задачі. Це, перш за все, необхідність вдосконалення перевезень на радянському транспорті в 30-ті роки, а також потреба в найкращий організації перевезень американського торгового флоту під час другої світової війни, також дослідження по балансуванню окремих галузей народного господарства. Саме вони дали перші результати в 20-30-ті роки ХХ століття. В цих перших роботах відбулася взаємодія різних наукових напрямів, що призвело до виникнення нової математичної дисципліни – “лінійного програмування”.

В цілому перша фаза виникнення лінійного програмування як самостійної математичної дисципліни охоплює біля 200 років (з середини XVIII сторіччя до 1939 року) в той час як період його затвердження тривав всього 10 років (з 1939 по 1949рр.)). Цей процес завершився проведенням першої спеціальної конференції по лінійному програмуванню в 1949 році в Чикаго. В той же час почався перехід до третьої фази – фази вдосконалення та розширення нової дисципліни.

Очевидно, вперше постановка задачі лінійного програмування у вигляді пропозиції по складанню оптимального плану перевезень, мінімізуючого загальний кілометраж (зараз подібні задачі отримали назву транспортних), зустрічається в роботах радянського економіста А.Н. Толстого (1930р.).

В 1931 році угорський математик Б. Егерварі розглянув в математичній постановці одну з окремих задач лінійного програмування, яка отримала в подальшому назву “проблеми вибору”. Він же й намітив метод її розв’язання, який був розвинений американським математиком Г. У. Куном стосовно загального класу транспортних задач і отримав назву угорського методу.

Систематичне дослідження задач лінійного програмування, перш за все як економічних задач, розробка загальних методів їх розв’язку розпочалися в 1939 році в роботах радянського математика Л.В. Канторовича та його учнів. Канторовичем був запропонований загальний метод розв’язання задач лінійного програмування, названий ним методом “розв'язуючих множників”, який лише в деталях відрізняється від загальноприйнятого зараз симплекс-методу.

Для розв’язку транспортних задач Л.В. Канторовичем та М.К. Гавуріним в 1949 році був запропонований метод потенціалів, що являє собою реалізацію методу “розв'язуючих множників” стосовно розв’язання транспортної задачі.

В наступних роботах Л.В. Канторовича, В.С. Немчинова, В.В. Новожилова, А.Л. Лур’є, А. Брудно, Г.Ш. Рубінштейна, Ц.Б. Юдіна, Б. Г. Гольдштейна, А.Г. Аганбегяна та багатьох інших радянських вчених-математиків та економістів отримали подальший розвиток як математична теорія лінійного та нелінійного програмування, так застосування її методів у дослідженні різних економічних проблем.

Одночасно з Канторовичем і, очевидно, не залежно від нього методи лінійного програмування розроблялися зарубіжними, перш за все американськими вченими. В американській літературі перша робота, яка містила постановку транспортної задачі, була опублікована в 1941 році Ф. Л. Хічкоком. Основний метод розв’язання задач лінійного програмування – симплексний метод – був опублікований в 1949 році Дж. Данцигом. Подальший розвиток методи лінійного і нелінійного програмування отримали в роботах Форда, Фулкерсона, Куна, Лемке (двоїстий симплекс-метод), Гасса (параметричне програмування), Чарнеса (проблема виродження), Біла, Данскіна, Раднера (опукле програмування) та інших.