Методические указания. 1. Постановка задачи многомерной оптимизации при ограничениях проведена в разделе 3, тема 5

1. Постановка задачи многомерной оптимизации при ограничениях проведена в разделе 3, тема 5. Описание методов оптимизации при ограничениях: метода движения вдоль границ, отражения от границ, метода штрафных функций − приведены в разделе 3, тема 6. В данной работе многомерная оптимизация рассматривается на примере двухпараметрической задачи. В качестве методов использованы, в зависимости от варианта, метод Хука-Дживса или метод покоординатного спуска.

Алгоритмы методов многомерной оптимизации при ограничениях (метода движения вдоль границ, отражения от границ) состоят из двух этапов:

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

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

На первом используется один из методов, описанных в разделе 4, тема5, например, метод Хука-Дживса или метод покоординатного спуска.

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

2. Программа многомерной оптимизации при ограничениях объединяет согласно алгоритму (см. п. 1) две программы: программу расчета области допустимых значений параметров и программу оптимизации без ограничений, использованную в предыдущей работе №7. Начнем с первой. Программа расчета области допустимых значений параметров, заданной ограничениями, двумерной задачи приведена на рис. 38.

Рис.38. Область допустимых значений параметров оптимизации и целевая функция двумерной задачи оптимизации.

Целевая функция Z(X,Y), как и в предыдущей работе №7, задана в виде двух слагаемых:

Z(X,Y) = F(X) + H(Y) (8.1)

Для отладочного примера ограничения заданы эллипсом и линейной функцией. Эллипс задан в тригонометрической форме уравнениями:

x2(t) = A cos(t)+xc, (8.2)

y2(t) = B cos(t)+y.

Заметим, что функция, описывающая эллипс, неоднозначная, поэтому для ее отображения в виде графика приходится применять вспомогательные функции Р1 и Р2, которые изображают выпуклый и вогнутый участки эллипса соответственно.

Прямая, отсекающая часть эллипса, описывается уравнением:

u(t) = kt + b1 (8.3)

В рассмотренном на рис. 38 примере коэффициент наклона прямой принят k=0.

Там же приведены графики области допустимых значений параметров оптимизации в формате 2D и график целевой функции в 3D.

Программа расчета точки экстремума приведена на рис.39. Выражение целевой функции записывается в виде (8.1). В качестве параметров оптимизации принимаются переменные х и у. В отладочном примере область допустимых значений определена границами (Ах,Вх и Ау,Ву), которые находятся из уравнений для ограничений.Точность определения минимума задается по каждому параметру Ех и Еу.

В задачах с ограничениями более эффективно использовать одномерные методы деления отрезка пополам либо «золотого сечения». Если ограничение задаются функциями (в отладочном примере):

Q1(x,y) = С, (8.4)

Q2(x,y)=A(x-a)² + (y-b)²,

где А, a, в, С - коэффициенты, которые выбираются согласно варианту (таблица 7), то область допустимых значений параметров оптимизации (Ах,Вх и Ау,Ву) может быть определена путем совместного решения уравнений (8.4) как системы. Эти решения дадут границы интервала поиска решения по каждой координате x и y соответственно (Ах,Вх) и (Ах,Вх).

Приведенная на рис. 39 программа написана для метода покоординатного спуска, в котором для движения вдоль координаты использована программа одномерного метода деления отрезка пополам (см. Работа 1), оформленная в виде процедуры.

3. При выполнении оптимизации для функции и параметров согласно варианту, используются данные, представленные в табл. 9. Варианты заданий, как по методу, так и по компонентам целевой функции F(x) и H(y), а также интервалу по координатам х и у отражены сочетанием номеров строк табл. 8, как и в работе №7.

Рис. 39. Программа метода покоординатного спуска и пример оптимизации при ограничениях.

Таблица 9. Варианты параметров для ограничений.

В качестве программ одномерной оптимизации методами деления отрезка пополам и «золотого сечения» рекомендуется использовать программы из работ №2 и №3 соответственно, оформив их как процедуры. Выбор метода в зависимости от варианта таков: четные номера вариантов соответствуют методу деления отрезка пополам, нечетные – методу «золотого сечения».

Задание рекомендуется выполнять в следующей последовательности:

Дополнить модуль выбора направления движения соответствующего многомерного метода п. 2 блоком отыскания границ интервала вдоль выбранного направления, решив совместно систему:

Q(x,y) = C, (8.5)

Y = k ۰ X + d.

В программе из работы 7 п. 2 рис. 36 заменить модуль одномерной оптимизации равномерного поиска на модуль метода деления отрезка пополам или метод «золотого сечения» в соответствии с вариантом.

3.3. Провести оптимизационный расчет для функции п. 2 с ограничением, согласно варианту табл. 8.2.

Дата добавления: 2014-12-27