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

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

Исторически сложилось так, что основным термином здесь является слово «программирование», совершенно отличное от другого значения этого термина, связанное с компьютерным программированием. Наиболее общим названием является «математическое программирование».

Данное обстоятельство связано с тем, что хотя первые, но в тоже время и основные, методы оптимизации восходят к Ферма (1630 г.), Ньютону, Лейбницу, Эйлеру, Бернулли и Лагранжу (17-18 века), в 1939 году математик Л.В. Канторович поставил и нашёл оригинальные способы решения важных практических задач, за что получил в 1965 году Нобелевскую премию по экономике, которые сводились к оптимизации на многогранниках (линеалах) и получили название «линейное программирование».

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

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

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

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

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

Методам линейного программирования также посвящено много работ зарубежных учёных. В 1941 году Ф.Л. Хитчкок поставил «транспортную задачу». Основным методом решения задач линейного программирования является «симплекс-метод», опубликованный в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна, А. Таккера, Гасса (Saul. I. Gass), Чарнеса (A. Charnes), Била (E.M. Beale) и других.

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

Начиная с 1955 году опубликовано много работ, посвященных «квадратичному программированию» (работы Била, Баранкина и Дорфмана (Dorfman R.), а также Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J.B.), Розена (Rosen J.B.) и Зонтендейка (Zontendijk G.) были разработаны градиентные методы решения задач нелинейного программирования.

Рассмотрим терминологию и классификацию задач оптимизации