Методы оптимизации организационно-технических систем (стр. 3 )

Рис	2.1

В частности, на рис. 2.1 изображены: целевая функция f(x) с помощью линий уровня C1, C2, C3, …., причем C1 < C2 < C3 и т. д.; ограничения gj ≤ 0, j =1,2,3 , выделяющие множество допустимых аргументов (параметров) - Х (запретные области условно заштрихованы); точки условного локального минимума определены номерами №1, №2, №3, №4, причем на рисунке видно, что точки №1 и №3 не удовлетворяют всем ограничениям gj ≤ 0 ; «угловые» точки: №5, №6, №7.

Как следует из рассмотренной выше методики в результате сравнения значений функций в точках условного локального минимума №2, №4 и в «угловых» точках №5, №6, №7 определяются координаты условного глобального минимума, которые на рисунке обозначены №2.

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

Численное решение задачи условной оптимизации с ограничениями типа неравенств должно осуществляться посредством нескольких методов с цель последующего сравнительного анализа соответствующих реализаций решения. Сравнение должно осуществляться как с точки зрения эвристических оценок показателей сходимости методов, так и с точки зрения затрат машинного времени на реализацию численного решения конкретной задачи с заданной точностью.

Выбор и фиксация вариантов численных методов безусловной оптимизации осуществляется исходя из их классификации (см. рис. 2.2).

Рис	2.2

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

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

Для численного поиска условного минимума целевой функции (1.1) при условиях (1.2) предлагается применить метод «Штрафных функций» [1, 2], позволяющий свести задачу условной минимизации к последовательности итеративно решаемых задач безусловной минимизации. Суть этого метода заключается в следующем.

На основе целевой функции формируется функция вида:

Φ(x, α) = f(x) + αТ s((g(x))

(2.10)

Где s(g(x)) – сложная функция вектора х, называемая функцией «штрафа» (или «штрафной» функцией), α – вектор коэффициентов «штрафа», размера [m´1].

Функция s(g(x)) должна иметь следующие свойства.

s((g(x)) =

(2.11)

То есть, если ограничения типа неравенств не нарушаются (g(x) < 0) , то функция «штрафа» не должна никак себя проявлять в функции (2.10), и если это ограничение нарушено, то с ростом этого нарушения должен расти «штраф» за него, вплоть до бесконечности. При этом в точках g(x) = 0 функция «штрафа» должна быть непрерывной справа.

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

Предполагается, что последовательность аргументов решений задач безусловной оптимизации {x*i безусл}, i = 1, 2,….., а именно:

Φ(x, αi ) = [ f(x) + αi s((g(x))] = x*i безусл

(2.12)

стремится к решению задачи условной оптимизации (1.1, 1.2) при неограниченном росте последовательности коэффициентов «штрафа» {ai} , то есть:

x*i безусл (αi ) = x* усл Φ(x*i безусл (αi ), αi ) = f(x* усл)

(2.13)

Где x*i безусл – вектор безусловного минимума функции Φ(x, αi) , зависящий от конкретного значения коэффициента «штрафа» αi, x*усл - вектор координат условного минимума, соответствующего поставленной задачи.

Таким образом, согласно приведенной гипотезе алгоритм приближенного численного решения задачи (1.1, 1.2) должен включать следующие операции.

1)  Ввод в программу: конкретных целевой функции - f(x) и ограничений - g(x) < 0 .

2)  Определение и ввод в программу конкретной функции «штрафа» - s(g(x)) .

3)  Фиксация исходных значений коэффициентов «штрафа» - α0 и сопутствующих параметров (например, параметра итеративного роста коэффициентов «штрафа» и параметра допустимого числа итераций).

4)  Определение метода безусловной оптимизации.

5)  Фиксация параметров выбранного метода.

6)  Задание начального приближения вектора аргументов x(0) .

7)  Организацию с помощью программных средств «охватывающего» цикла перебора коэффициентов «штрафа» - αi , i = 1, 2, …. (с нарастанием до определенного значения).

8)  Организацию с помощью программных средств и в соответствии с выбранным методом безусловной оптимизации «внутреннего» цикла поиска минимума функции Φ(x, αi) для текущего значения αi и определение промежуточного значения x*i безусл (αi ). В случае применения в рамках заданного численного метода конкретной процедуры одномерной оптимизации, необходимо «внутри» этого цикла организовать еще один цикл - минимизации функции в заданном направлении.

9)  Проверка условий окончания процедуры поиска условного минимума целевой функции и в случае их выполнения – прекращение процедуры, в противном случае – назначение новых значений αi и x(0i) и переход к пункту 6 алгоритма (рекомендуется в качестве новых значений x(0i) выбирать последние значения этого вектора на предыдущей итерации «внутреннего» цикла, то есть - x(p)i-1 ).

Этот алгоритм может быть представлен в виде укрупненной блок-схемы (см. рис. 2.3).

Задание исходных данных (параметров, коэффициентов и др.)   вход
Рис	2.3

В качестве функции «штрафа» предлагается использовать следующую составную функцию.

s((g(x)) =

(2.14)

Где gj(x) одна из m функций ограничений.

В общем случае для каждой функции gj(x) должна быть определена своя функции «штрафа» - sj((gj(x)) типа (2.14). В результате функция Φ(x, α) приобретет более конкретный вид:

Φ(x, αi) = f(x) +  αij sj((gj(x))

(2.15)

Коэффициенты «штрафа» αij могут быть различны для каждого ограничения gj(x), однако, имея в виду абстрактность рассматриваемой задачи, они могут определяться одинаковой последовательностью значений {ai}, i = 1,2,…. Тогда (2.14) с учетом этого и (2.15) будет иметь вид: