История математического программирования
Под теорией и методами оптимизации понимают большой круг задач, связанный с поиском оптимальных решений, которые имеют значительное число подразделов и большое число разнообразных названий: оптимизация, экстремальные задачи, исследование операций, линейное программирование, выпуклое программирование, квадратичное программирование, нелинейное программирование, оптимальное программирование, целочисленное программирование, задачи минимакса, невыпуклое оптимизация, многоэкстремальные задачи, вариационное исчисление, оптимальное управление, оптимальные процессы.
Исторически сложилось так, что основным термином здесь является слово «программирование», совершенно отличное от другого значения этого термина, связанное с компьютерным программированием. Наиболее общим названием является «математическое программирование».
Данное обстоятельство связано с тем, что хотя первые, но в тоже время и основные, методы оптимизации восходят к Ферма (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.) были разработаны градиентные методы решения задач нелинейного программирования.
Рассмотрим терминологию и классификацию задач оптимизации
Обзор курса
Обзор делается на основе оглавления книги. Примерно 14 занятий = 4 месяца х 4 занятия в месяц. Кратко характеризуются все пункты (главы (их 5) и параграфы (их 16)) курса. Теоретическая часть. Что будет на лабораторных занятиях.
Название курса определяет достаточно большую область прикладной математики. Широкую по охвату тем, богатую теоретическими методами и алгоритмами и имеющую большое практическое применение. Основные темы курса «Теория и методы оптимизации» хорошо отражены в книге Пантелеева и Летовой, на которой построен курс: и лекции и лабораторные работы (практические занятия). Скорее всего, наш курс сможет охватить только эти разделы, относящиеся к классическим основным методам:
- Глава 1 – необходимые и достаточные условия экстремума в простейшем случае гладких (дифференцируемых) функций;
- Глава 2, § 5.1 – численные методы безусловной одномерной оптимизации;
- Глава 2, §§ 4, 5.2-5.6, 6, 7 – численные методы безусловной многомерной (векторной) оптимизации;
- Глава 3 – численные методы поиска условного экстремума;
- Глава 4 – задачи линейного программирования;
- Глава 5 – задачи вариационного исчисления.
Как дальнейшее развитие темы примерно после 1940 года возникли следующие разделы, вызванные к жизни сложнейшими практическими задачами в технике и экономике.
Нелинейное программирование является естественным, но абсолютно нетривиальным обобщением линейного программирования. Эта тематика имеет и другие названия: экстремальные задачи, выпуклое программирование. Первоначально линейное программирование было создано Канторовичем для решения сложных экономических задач планирования. Методы нелинейного программирования применяются для намного большего класса задач как в фундаментальных научных исследованиях и инженерном деле, так и в экономике – на них построена вся современная теория планирования балансов предприятий и целых стран.
Теория управления или оптимального управления. Возникла как обобщение вариационного исчисления для решения задач управления движением в воздушном пространстве и космосе. В настоящее время применяется в сложных случаях при решениях сложных задач во многих отраслях техники и гуманитарных областях.
Внутри этих теорий были созданы такие подразделы, как теория игр, дифференциальные игры, многоэкстремальные задачи.
Была построена абстрактная теоретическая база методов оптимизации, охватывающая и обобщающая многие похожие задачи и случаи, на основе теории нормированных пространств и методов функционального анализа.
Мы до этого всего, из-за ограниченного времени курса (1 семестр) почти наверняка не дойдём и изучать не будем. Я решил лучше сосредоточиться на аккуратном изучении основ, чем на поверхностном ознакомлении с многочисленными темами и подтемами этой науки. Кроме того, акцент будет сделан на практические навыки решения задач, а не на их теоретическом обосновании. Хотя бы удовлетворительное владение этими навыками будет крайне полезно при решении практически любой научно-технической или инженерной задачи.
Лекции будут читаться по тексту книги на компьютере, лабораторные (или практические) работы также будут основаны на задачах из книги и будут состоять из 2-х или 3-х разделов (пока не знаю, будет ли третий раздел):
- аналитическое решение в тетради задач к разделам книги – там, где возможно разумное аналитическое решение, в основном это – одномерный случай (20-30 задач): задачи стр. 21 (все 8), задачи стр. 33 (все 10), задачи стр. 96 (5-6 штук);
- написание программ на Matlab (примерно 5 штук), реализующие векторные методы безусловной и условной оптимизации;
- написание программы на Matlab, решающей реальную несложную задачу методами глав 4 и 5 (если останется время).
Результаты лабораторных работ будут обеспечивать получение зачёта. Для получения стандартного задания необходимо посетить 50% занятий. В случае нарушения этого условия, для получения зачёта надо будет выполнить задание большее по объёму или сложности в 2-3 раза.
Экзамена не будет, если не поменяли с прошлого года.