Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
07.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
915 Кб
Скачать
☆

Сведение задачи с ограничениями к безусловной методом штрафных функций

Задачу минимизации целевой функции f(x) в допустимой области

min f(x), (x) 0

можно привести к эквивалентной задаче безусловной минимизации

min L(x),

где L(x) = f(x) + {(x)} – комплексная целевая функция, учитывающая как целевую функцию исходной задачи, так и ограничение,  – коэффициент штрафа за нарушение ограничений. Выражение в фигурных скобках (функция штрафа) равно нулю, если ограничение не нарушено, в противном случае равно степени нарушения ограничения (рис. 2 а):

{(x)} = 

Свободный минимум комплексной целевой функции L(x) при надлежащем выборе коэффициента штрафа совпадает с условным минимумом истинной целевой функции f(x).

Рис. 2. Сведение задачи минимизации с ограничением к безусловной методом штрафных (а) и барьерных (б) функций

Комплексную целевую функцию можно представить в виде

L(X) =  W(X) + ,

с выбором знака в зависимости от того, нужно найти минимум (+) или максимум (–) целевой функции W(X). Задача поиска условного экстремума целевой функции W(X) эквивалентна минимизации функции L(X), если удачно выбраны коэффициенты штрафа. Объективных способов выбора коэффициентов штрафа не существует. Ясно, что надежность приближения точки, минимизирующей L(X), к истинному решению тем надежнее, чем больше коэффициенты штрафа (в пределе – до бесконечности), но надежность приближения к оптимуму при этом снижается. Поэтому обычно решают последовательность задач с возрастающими коэффициентами штрафа или используют накопленный опыт оптимизации аналогичных задач.

Метод барьерных функций

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

L(x) = f(x) + ,

где С – достаточно малая величина. В пределах допустимой области вдали от ее границ функция L(x) практически совпадает с f(x), но с приближением к границам знаменатель стремится к нулю, а функция L(x) – к бесконечности. Таким образом, минимизация L(x) приводит почти к тому же результату, что и условная минимизация f(x) (рис. 2 б). Степень близости приближенного решения к истинному зависит от значения коэффициента С (обычно решается последовательность задач с уменьшающимся С). В комплексной целевой функции некоторые штрафные слагаемые, которые соответствуют «непреодолимым» ограничениям, можно заменить выражениями

.

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

Принципиальным образом методы решения задач вида:

min W(X)

Fk(X)  Fkтр, k =1, …, m,

ai x i bi, i=1, …, n,

зависят от характера целевой функции W(X) и функций-ограничений Fk(X).

Линейное программирование

Простейший частный случай задачи математического программирования – линейное программирование (ЛП) – состоит в минимизации или максимизации линейной функции на допустимом множестве, заданном линейными ограничениями:

, k = 1, …, m.

Особенность задач ЛП в том, линейная целевая функция в системе линейных ограничений достигает минимума в одной из угловых точек (рис. 3 а). На этом свойстве основан симплекс-метод решения задач ЛП за конечное число шагов направленного перебора угловых точек допустимой области с последовательным уменьшением значений целевой функции (рис. 3 б).

а б в

Рис. 3. Иллюстрация двумерной (а) и трехмерной (б) задач ЛП и задачи КП (в)

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

Квадратичное программирование

Целевая функция, заданная квадратичной формой с симметричной, положительно определенной матрицей g

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

Выпуклое программирование

Из всех задач оптимизации с нелинейными функционалами самые благоприятные для решения задачи выпуклого программирования, в которых целевая функция и функции-ограничения обладают свойствами выпуклости. Как известно, график выпуклой функции лежит выше касательной в любой его точке. Ограничения сверху на выпуклые функции образуют выпуклую допустимую область, содержащую вместе с любой парой точек и отрезок между ними. Это очень важное свойство с точки зрения поиска экстремума, но еще важнее то, что экстремальная точка единственна и является искомым решением задачи. Большинство методов нелинейного программирования (НЛП) предполагают наличие единственного локального экстремума, но только в выпуклой области может существовать не более одной точки, в которой выполняется критерий оптимальности выпуклой целевой функции.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]