История. Одно из самых десемантизированных понятий в современном языке - понятие "империя"

История

Задачи линейного программирования были первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин «линейное программирование» был предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Поэтому наименование «Математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий.

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

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

Л. В. Канторовичем совместно с М. К. Гавуриным в 1949 г разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 г. Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Куна, А. Таккера, Гасса, Чарнеса, Била и др.

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

Начиная с 1955 г опубликовано много работ, посвященных квадратическому программированию (работы Била, Э. Баранкина и Дорфмана, Франка и Вольфа, Г. Марковица и др.). В работах Денниса, Розена и Зонтендейка разработаны градиентные методы решения задач нелинейного программирования.

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

Литература

1. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование одного алгоритма глобальной оптимизации — Труды ФОРА, 2004.
2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов — М.: Высшая школа, 1986.
3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ — М.: Мир, 1985.
4. Жиглявский А.А., Жилинкас А.Г. Методы поиска глобального экстремума — М.: Наука, Физматлит, 1991.
5. Карманов В.Г. Математическое программирование = Математическое программирование — Изд-во физ.-мат. литературы, 2004.
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров — М.: Наука, 1970. — С. 575—576.
7. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики — М.: Энергоатомиздат, 1972.
8. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования — М.: МИФИ, 1982.
9. Максимов Ю.А. Алгоритмы линейного и дискретного программирования — М.: МИФИ, 1980.
10. Плотников А.Д. Математическое программирование = экспресс-курс — 2006. — С. 171. — ISBN 985-475-186-4.
11. Растригин Л.А. Статистические методы поиска — М., 1968.
12. Хемди А. Таха Введение в исследование операций = Operations Research: An Introduction — 8 изд.. — М.: «Вильямс», 2007. — С. 912. — ISBN 0-13-032374-8.
13. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения — М.: Радио и связь, 1981. — 560 с.