Классификация и условия оптимальности математических моделей задач оптимального проектирования
Как было показано ранее, задачи параметрической оптимизации можно свести к математической модели минимизации функции n переменных, обозначенной нами Однако, прежде всего, следует определить, что мы понимаем под минимумом функции. 2.1 Глобальный и локальные минимумы. Рассмотрим вначале случай, когда ограничения на варьируемые параметры Точка Глобальным минимумом функции n переменных Примеры локальных и глобальных минимумов функций одной и двух переменных показаны на рис. 2.1 и 2.2 соответственно. Рассмотрим теперь задачу с ограничениями: Точка Глобальным минимумом функции n переменных На рис. 2.3 видно, как функция одной переменной, которая при отсутствии ограничений вообще не имела минимумов, при наличии ограничений имеет два локальных минимума, один из которых является глобальным. Рис. 2.4 показывает как функция двух переменных, имевшая при отсутствии ограничений один минимум (локальный и глобальный одновременно), при наличии ограничений, исключающих этот минимум, получает два новых локальных минимума. 2.2 Классификация математических моделей. Математические модели задач оптимального проектирования можно классифицировать по нескольким признакам. 1) По наличию или отсутствию ограничений на варьируемые параметры: · Задачи минимизации функций, в которых ограничения на варьируемые параметры отсутствуют, называются задачами безусловной минимизации. · Задачи минимизации функций, в которых присутствуют ограничения на варьируемые параметры, называются задачами условной минимизации. 2) По числу варьируемых параметров: · Задачи минимизации функций одной переменной называются задачами одномерной минимизации. · Задачи минимизации функций нескольких переменных называются задачами многомерной минимизации. 3) По числу точек локального минимума в области допустимых значений варьируемых параметров: · При наличии одного локального минимума (одновременно являющегося глобальным), задача минимизации называется одноэкстремальной. · При наличии нескольких локальных минимумов, задача минимизации называется многоэкстремальной. 4) В зависимости от вида минимизируемой функции и ограничений на варьируемые параметры: · Если минимизируемая функция и ограничения являются линейными функциями, такая задача называется задачей линейного программирования. Обобщением задачи линейного программирования является задача сепарабельного программирования, в которой целевая функция и ограничения представляют собой суммы n функций, каждая из которых зависит только от одного варьируемого параметра. · Если минимизируемая функция является квадратичной, а ограничения являются линейными функциями, такая задача называется задачей квадратичного программирования. Обобщением задачи квадратичного программирования является задача геометрического программирования, когда целевая функция и ограничения являются положительными полиномами. · Если минимизируемая функция и ограничения являются нелинейными функциями, задача называется задачей нелинейного программирования. Если при этом целевая функция и область допустимых значений варьируемых параметров являются выпуклыми функциями, такую задачу называют задачей выпуклого программирования. 5) В зависимости от того, какие значения могут принимать варьирумые параметры: · Если варьируемые параметры могут принимать только дискретные значения, получаем задачу дискретной оптимизации. В частном случае, когда варьируемые параметры могут иметь только целочисленные значения, задачу называют задачей целочисленного программирования. Для решения задач линейного программирования применяются хорошо разработанные и строго обоснованные методы, такие как симплекс-метод [1]. В большинстве случаев задачи квадратичного и геометрического программирования также удается решить специальными методами [2] или свести к задачам линейного программирования. Так как названные задачи представляют ограниченный интерес для исследований в области естественных наук и инженерной практики, ограничимся в данном курсе ссылкой на литературные источники. Задачи дискретного или целочисленного программирования зачастую оказываются более трудоемкими, чем задачи минимизации функций непрерывных (вещественных) переменных. Для решения таких задач используется метод ветвей и границ [1], а также появившиеся сравнительно недавно эволюционные алгоритмы [3]. Изложение этих методов также выходит за рамки настоящего курса. Таким образом, далее мы будем рассматривать задачи нелинейного программирования: при отсутствии и наличии ограничений, одномерные и многомерные. Большинство методов, которые мы будем рассматривать, строго обоснованы лишь для одноэкстремальных задач выпуклого программирования. Тем не менее, с некоторыми оговорками, большинство из них применимо и для решения невыпуклых задач. Что касается многоэкстремальных задач, то конструктивных методов, позволяющих гарантированно найти глобальный минимум функции, не существует. На практике с помощью рассматриваемых ниже методов решения одноэкстремальных задач пытаются найти все локальные минимумы в области допустимых значений варьируемых параметров. Для различных классов моделей задач оптимального проектирования существуют различные методы решения. Тем не менее, можно выделить два подхода к построению этих методов. Первый основан на непосредственном применении условий оптимальности для соответствующего класса задач. Второй подход основан на применении эмпирических алгоритмов поиска оптимальных решений. В зависимости от того, требуется для реализации того или иного метода решения задачи оптимального проектирования вычисление производных или нет, эти методы разделяют на следующие группы. Методы прямого поиска или методы нулевого порядка – методы, не требующие вычисления производных целевой функции. Градиентные методы – методы, требующие вычисления производных. Порядок градиентных методов определяется порядком старшей производной, которую необходимо вычислить. Обычно на практике используются градиентные методы первого, реже второго порядка. Градиентные методы обычно отличаются более высокой скоростью сходимости, чем методы прямого поиска. Однако, применение градиентных методов может оказаться затруднительным, если производные целевой функции приходится находить численно, и просто невозможным, если целевая функция не дифференцируема требуемое число раз. 2.3 Условия оптимальности.Перейдем к рассмотрению условий оптимальности математических моделей задач нелинейного программирования и попытаемся оценить возможности построения на основе этих условий конструктивных методов минимизации. 1) Безусловная минимизация унимодальной (имеющей один экстремум) функции одной переменной:
Решение задачи (2.1) – локальный минимум функции одной переменной
Таким образом, найти локальный минимум выпуклой унимодальной функции 2) Безусловная минимизация унимодальной (имеющей один экстремум) функции многих переменной:
Локальный минимум функции n переменных Здесь H – матрица Гессе - квадратная матрица размера 3) Условная минимизация унимодальной функции n переменных:
Можно доказать [4], что необходимые условия минимума выпуклой функции Условия (2.6) известны как условия Куна-Таккера. Из них можно найти значения компонент вектора Значение каждого из множителей Если правую часть неравенства Из третьего соотношения в (2.6) видно, что Второе соотношение в условиях Куна-Таккера совпадает с ограничениями исходной задачи (2.5). Для того, чтобы понять, как работают условия Куна-Таккера полезно самостоятельно с их помощью решить две простые задачи: К сожалению, нахождение оптимального решения путем решения системы (2.6) не проще, чем решение исходной модели (2.5). Поэтому конструктивных численных методов минимизации, основанных на условиях Куна-Таккера нет.
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Почему стероиды повышают давление?: Основных причин три... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1022)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |