Оптимизация (в математике , информатике и исследовании операций ) — это задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства , ограниченной набором линейных и/или нелинейных равенств и/или неравенств .

Теорию и методы решения задачи оптимизации изучает математическое программирование .

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

Постановка задачи оптимизации

В процессе проектирования ставится обычно задача определения наилучшей, в некотором смысле, структуры или наилучших значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией . Задача выбора оптимальной структуры является структурной оптимизацией .

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов χ, образующих множества Χ, найти такой элемент χ ^* , который доставляет минимальное значение f(χ ^* ) заданной функции f(χ). Для того, чтобы корректно поставить задачу оптимизации, необходимо задать:

1. Допустимое множество — множество ${\displaystyle \mathbb {X} =\{{\vec {x}}|\;g_{i}({\vec {x}})\leq 0,\;i=1,\ldots ,m\}\subset \mathbb {R} ^{n}}$ ;
2. Целевую функцию — отображение ${\displaystyle f:\;\mathbb {X} \to \mathbb {R} }$ ;
3. Критерий поиска (max или min).

Тогда решить задачу ${\displaystyle f(x)\to \min _{{\vec {x}}\in \mathrm {X} }}$ означает одно из:

1. Показать, что ${\displaystyle \mathbb {X} =\varnothing }$ .
2. Показать, что целевая функция ${\displaystyle f({\vec {x}})}$ не ограничена снизу.
3. Найти ${\displaystyle {\vec {x}}^{*}\in \mathbb {X} :\;f({\vec {x}}^{*})=\min _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}$ .
4. Если ${\displaystyle \nexists {\vec {x}}^{*}}$ , то найти ${\displaystyle \inf _{{\vec {x}}\in \mathbb {X} }f({\vec {x}})}$ .

Если минимизируемая функция не является выпуклой , то часто ограничиваются поиском локальных минимумов и максимумов: точек ${\displaystyle x_{0}}$ таких, что всюду в некоторой их окрестности ${\displaystyle f(x)\geq f(x_{0})}$ для минимума и ${\displaystyle f(x)\leq f(x_{0})}$ для максимума.

Если допустимое множество ${\displaystyle \mathbb {X} =\mathbb {R} ^{n}}$ , то такая задача называется задачей безусловной оптимизации , в противном случае — задачей условной оптимизации .

Классификация методов оптимизации

Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом).

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.
• Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1. детерминированные;
2. случайные (стохастические);
3. комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации .

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

• Задачи оптимизации, в которых целевая функция ${\displaystyle f({\vec {x}})}$ и ограничения ${\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m}$ являются линейными функциями, разрешаются так называемыми методами линейного программирования .
• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
  • если ${\displaystyle f({\vec {x}})}$ и ${\displaystyle g_{i}({\vec {x}}),\;i=1,\ldots ,m}$ — выпуклые функции, то такую задачу называют задачей выпуклого программирования ;
  • если ${\displaystyle \mathbb {X} \subset \mathbb {Z} }$ , то имеют дело с задачей целочисленного (дискретного) программирования .

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

• прямые методы, требующие только вычислений целевой функции в точках приближений;
• методы первого порядка : требуют вычисления первых частных производных функции;
• методы второго порядка: требуют вычисления вторых частных производных, то есть гессиана целевой функции.

Помимо того, оптимизационные методы делятся на следующие группы:

• аналитические методы (например, метод множителей Лагранжа и условия Каруша — Куна — Таккера );
• численные методы ;
• .

В зависимости от природы множества X задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации ) — если X конечно или счётно ;
• задачи целочисленного программирования — если X является подмножеством множества целых чисел;
• задачи нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства .
• Если же все и целевая функция содержат лишь линейные функции, то это — задача линейного программирования.

Кроме того, разделами математического программирования являются параметрическое программирование , динамическое программирование и стохастическое программирование .

Математическое программирование используется при решении оптимизационных задач исследования операций .

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• Определение границ системы оптимизации
  • Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается
• Выбор управляемых переменных
  • «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)
• Определение ограничений на управляемые переменные
  • … (равенства и/или неравенства)
• Выбор числового критерия оптимизации (например, )
  • Создаём целевую функцию

История

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

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

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

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

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

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

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

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

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

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

См. также

• Многокритериальная оптимизация
• Математический анализ
• Скалярное ранжирование

Примечания

Литература

• Абакаров А. Ш., Сушков Ю. А. . — Труды ФОРА, 2004.
• Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М. : Высшая школа, 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
• Гирсанов И. В. Лекции по математической теории экстремальных задач. — М. ; Ижевск : НИЦ «Регулярная и хаотическая динамика», 2003. — 118 с. — ISBN 5-93972-272-5 .
• Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. — М. : Наука, Физматлит , 1991.
• Карманов В. Г. Математическое программирование. — Изд-во физ.-мат. литературы, 2004.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575—576.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М. : Энергоатомиздат , 1972.
• Лотов А. В. , Поспелова И. И. от 21 января 2022 на Wayback Machine Учеб. пос. М., 2005. 127 с.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М. : МИФИ, 1980.
• Плотников А. Д. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4 .
• Растригин Л. А. Статистические методы поиска. — М. , 1968.
• Сергеев Я. Д., Квасов Д. Е. от 26 октября 2017 на Wayback Machine . — М.: ФИЗМАТЛИТ, 2008. 341с.
• Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. — 8 изд. — М. : , 2007. — С. 912. — ISBN 0-13-032374-8 .
• Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М. : Радио и связь, 1981. — 560 с.
• Зуховицкий С. И. , Авдеева Л. И. Линейное и выпуклое программирование. — 2-е изд., перераб. и доп.. — М. : Издательство «Наука», 1967.
• Минаев Ю. Н. Стабильность экономико-математических моделей оптимизации. — М. : Статистика, 1980.
• Моисеев Н. Н. . — М. : Наука, 1971. — 424 с.
• Моисеев Н. Н. . — М. : Наука, 1975. — 528 с.
• Моисеев Н. Н. , Иванилов Ю. П. , Столярова Е. М. . — М. : Наука, 1978. — 352 с.

• Дегтярёв Ю. И. Методы оптимизации. — М. : Советское радио, 1980. — 272 с.
• Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. — М. : Мир, 1986. — 400 с.
• Романовский И. В. Алгоритмы решения экстремальных задач. — М. : Наука, 1977. — 352 с. — 16 000 экз.
• Умнов А.Е. , Умнов Е.А. от 9 июля 2021 на Wayback Machine (pdf)
• Хохлюк В. И. от 18 января 2021 на Wayback Machine Курс лекций. Новосибирск , 2007.
• Хохлюк В. И. от 18 января 2021 на Wayback Machine Учебное пособие. НГУ, 2013. 154 с.

Ссылки

• Поляк Б. П. // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения». — 2008. — Т. 1 . — С. 2—20 .