Оптимизация (математика)

Задачей оптимизации в математике называется задача о нахождении экстремума ( минимума или максимума) действительной функции в некоторой области. Как правило, рассматриваются области, принадлежащие \ Mathbb {R} ^ n и заданные набором равенств и неравенств.

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


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

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

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

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

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

  1. Показать, что \ Mathbb {X} = \ varnothing .
  2. Показать, что целевая функция f (\ vec {x}) не ограничена снизу.
  3. Найти \ Vec {x} ^ * \ in \ mathbb {X}: \; f (\ vec {x} ^ *) = \ min_ {\ vec {x} \ in \ mathbb {X}} f (\ vec {x }) .
  4. Если \ Nexists \ vec {x} ^ * , То найти \ Inf_ {\ vec {x} \ in \ mathbb {X}} f (\ vec {x}) .

Если минимизирована функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x_0 таких, что повсюду в некотором их окрестности f (x) \ ge f (x_0) для минимума и f (x) \ le f (x_0) для максимума.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. История

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

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

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

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

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

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

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

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


См.. также

Литература

  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