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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

КУРСОВАЯ РАБОТА

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



I Часть. ПОСТАНОВКА ЗАДАЧИ

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

f (x)	(1.1)

Где х - вектор аргументов (параметров), имеющий в общем случае размерность [n1], f(x) - скалярная унимодальная дифференцируемая функция, Х - множество допустимых значений аргументов х, заданное совокупностью ограничений типа неравенств:

	(1.2)

Где gj(x) - дифференцируемая функция векторного аргумента, j - число ограничивающих функций.

Задача (1.1) считается поставленной корректно, если ограничения gj(x)?0, j=1,…,m совместимы и образуют непустое множество Х , на котором существует целевая функция f(x) .

Аналитическое решение задачи условной оптимизации следует найти с помощью необходимых условий оптимальности - теоремы Куна и Таккера. Существо этой теоремы и построенный на ее основе алгоритм решения поставленной задачи излагаются в разделе 2.1.

В результате аналитического решения задачи типа должен быть получен набор локальных условных минимумов, из которых путем сравнения выбирается решение. Кроме того, полученное решение необходимо сопроводить графической иллюстрацией т.е. построить линии уровня целевой функции, ограничения и найденных точек глобального и локальных минимумов. Для графических построений рекомендуется использовать доступные математические пакеты, например MatCAD, MatLab и др.

1.1 Методическое Обеспечение домашней работы

Для аналитического решения задачи типа (1.1, 1.2) предлагается использовать методику, в основе которой лежит теорема Куна и Таккера (H.W. Kuhn, A.W. Tucker) [1], представляющая собой в общем случае необходимые условия минимума целевой функции при наличии ограничений типа неравенств на множество допустимых значений векторного аргумента функции (см.(1.2)). В рассматриваемом приложении эту методику целесообразно представить в виде следующего расширенного алгоритма.

1. Формирование функции Лагранжа.

Исходя из обозначений принятых в постановке (1.1, 1.2), функция Лагранжа будет иметь вид:

F(x,) = f (x) + Tg(x)	(2.1)

где - вектор множителей Лагранжа размерности [m1], соответствующей количеству ограничений gj(x)?0, j=1,…,m .

2. Применение необходимых условий (НУ) в форме Куна и Таккера для определения условных стационарных точек для задачи (1.1, 1.2).

В компактной форме для случая минимизации функции условия Куна и Таккера могут быть записаны в виде:

	(2.2)



Где - координаты стационарных точек.

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

gi(x)=0, i  I1 ; gj(x)<0, j  I2	(2.3)

Где I1 - множество номеров индексов активных ограничений, I2 - множество номеров индексов пассивных ограничений (сумма элементов этих множеств всегда равна m).

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

когда множество номеров активных ограничений I1 пусто ( = 0 ), то есть фактически рассматривается задача безусловной оптимизации;

и когда количество активных ограничений, то есть количество элементов множества I1 равно размерности вектора х - [n1] (так называемые «угловые» точки), тогда эта точка фиксируется активными ограничениями и не допускает вариации целевой функции (имеется ввиду корректная постановка задачи (1.1, 1.2)).

В результате применения НУ для всех возможных сочетаний активных ограничений будут получены варианты стационарных точек - , в которых могут оказаться условные локальные минимумы и, в конечном итоге, - условный глобальный минимум, являющийся решением поставленной задачи.

3. Исключение всех стационарных точек, не удовлетворяющих пассивным ограничениям.

То есть:

gj()<0, j  1,m	(2.4)

4. Исключение стационарных точек, не удовлетворяющих условиям неотрицательности множителей Лагранжа.

Из оставшегося числа вариантов стационарных точек необходимо исключить все точки, не удовлетворяющие условиям неотрицательности соответствующих множителей Лагранжа - , в которых согласно НУ не могут находиться условные локальные минимумы целевой функции.

5. Проверка оставшихся стационарных точек на достаточные условия локального минимума функции.

Все оставшиеся стационарные точки, за исключением «угловых» точек, должны быть проверены с помощью достаточных условий (ДУ), подтверждающих или опровергающих наличие в них условного локального минимума.

Одним из широко распространенных вариантов ДУ нахождения в исследуемой стационарной точке условного локального минимума является положительная определенность матрицы Гессе, размера [nn] (матрицы вторых частных производных) для функции Лагранжа F(х, ) по вектору х - [n1].

H(x)(х, ) =	(2.5)

Известно, что матрица положительно определена, если составленная с ее помощью квадратичная форма положительно определена [1], то есть:

yTH(x)(х, ) y > 0	(2.6)



Где H(x)(х, ) - матрица Гессе (Гессиан) по вектору х; y - любой вектор с фиксированными значениями , размера [n1].

Для проверки положительной определенности квадратичной формы (2.6) предлагается применить критерий Сильвестра [2, 4]. Суть его заключается в следующем.

Для того, чтобы квадратичная форма (2.6) была положительно определенной, необходимо и достаточно, чтобы матрица H(x)(х, ) имела все положительные угловые миноры, нарастающие вдоль главной ее диагонали, то есть были бы положительными определители матриц:

?1 = h11> 0; ?2 = > 0;…; ?n = > 0	(2.7)

Где hij - элементы матрицы Гессе H(x)(х, ) .

Таким образом, при подтверждении положительной определенности матрицы Гессе в стационарных точках, в которых согласно НУ возможно было нахождение условного локального минимума, то есть при  > 0 , такие стационарные точки переводятся в число точек условного локального минимума целевой функции f(x) при условиях gj(x) ? 0, j=1,…,m :

для номеров «s», удовлетворяющих НУ и ДУ	(2.8)

6. Определение условного глобального минимума.

Сравнение значений целевой функции f(x) в точках условного локального минимума и в «угловых» точках позволяет выявить условный глобальный минимум:



	(2.9)

Где xугл - координаты «угловых» точек, определяемых n активными ограничениями из числа j1,…,m (см. пункт 2).

Таким образом условный глобальный минимум целевой функции равняется f(xmin ).

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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис	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.

1.2 Решение поставленной задачи

Вариант № 16

f(x1, x2)	gi (x1, x2) ? 0, i = 1,m
(х1 - 5)2 + 2(х2 - 3)2	2х1 + х2 - 6=g1
	-2х1+ х2- 4=g2
	-х2 - 3=g3

Составим функцию Лагранжа:

Найдём частные производные и запишем необходимое условие экстремума:

Добавим условия Куна-Таккера:

Получаем следующую систему уравнений:

Из последних трёх уравнений следует, что хотя бы одно лiдолжно равняться нулю. Задавая соответствующие лi равными 0, получим условные стационарные точки:

1) -безусловный минимум

2) Активные ограничения: g2

Пассивные ограничения: g1,g3

3) Активные ограничения: g3

Пассивные ограничения: g1,g2

4) Активные ограничения: g1

Пассивные ограничения: g2,g3

5) Активные ограничения: g2,g3

Пассивные ограничения: g1

6) Активные ограничения: g1,g3

Пассивные ограничения: g2

7) Активные ограничения:g1, g2

Пассивные ограничения: g3

Так как множители Лагранжа должны быть неотрицательны, получаем одну условную стационарную точку 4:

(1.9, 2.3, 1.45, 0, 0).

Проверим достаточные условия локального минимума: матрица Гёссе функции Лагранжа равна положительно определена в любой точке. Следовательно, в точке (1.9, 2.3, 1.45, 0, 0) достигается локальный минимум.

Так как точка расположена на границе активного ограничения, то в этой точке достигается глобальный минимум.

Рис. 1

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

Определяются координаты условного глобального минимума, которые на рисунке обозначены №4.



II Часть. Безусловная оптимизация функции

2.1 Постановка задачи

Рассматривается задача оптимизации целевой скалярной функции по аргументам (параметрам) , на вариации которых никаких ограничений не накладывается.

Моему варианту № 5 соответствуют следующие данные:

f(x1, x2) = 2(х1 - 5)2 + (х2 - 8)2

16	Модифицированный метод наилучшей пробы
	Метод простой градиентной оптимизации

2.2 Модифицированный метод наилучшей пробы

Суть метода

Этот метод в отличие от предыдущего позволяет выбирать наилучшее направление изменения функции (при этом оно не обязательно совпадает с антиградиентом функции).

Алгоритм метода

Из некоторой промежуточной точки поиска минимума целевой функции x(k) осуществляется m-случайных независимых пробных шагов:

(5.52)

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

Наилучшим направлением считается направление, в котором функция достигает минимального значения.

f(x(k)+hпр(kj*)) = min f(x(k)+hпр(kj)), (5.53)

В этом направлении - (kj*) совершается рабочий шаг движения:

, (5.54)

где . (5.55)

Из формул (5.52)-(5.55) следует, что эффективность метода определяется следующими параметрами метода, задаваемыми оператором:

hпр , hраб , m.

Они, как правило, входят в состав формальных параметров компьютерной подпрограммы, реализующей данный метод.

Замечание

Можно показать, что в пределе при m стремящемся к , направление (kj*) стремится к антиградиенту функции, то есть:

(5.56)

Преимущества метода

Метод позволяет при количестве проб m<n получить направление (kj*) близкое к антиградиенту функции.

Метод просто программируется.

Позволяет определить глобальный экстремум (в принципе).

Недостатки метода

Метод не исключает выбор «наилучшего» из m-направлений , в котором функция f(x) будет возрастать !

Накопленная при m-проб информация о поведении целевой функции используется не эффективно.

2.3 Модификация метода наилучшей случайной пробы

В ответ на 1-ый недостаток рассмотренного метода возникла идея дополнить процедуру (5.53) операцией, присущей методу простой случайной оптимизации.

(5.57)

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

2.4 Блок-схема модифицированного метода наилучшей пробы



2.5 Метод простой градиентной минимизации

Сущность метода

Метод характеризуется относительно малым постоянным шагом = h, который задаётся как параметр метода.

Идея метода видна из простого соотношения:

(5.75)

где - i-я составляющая вектора - градиента функции в точке x(k) .

При заданном малом шаге hалгоритм метода определяется формулой (5.74).

Замечание

Хотя шаг поиска h должен быть малым, но не меньше порога чувствительности функции:

| f(x(k+1)) - f(x(k)) | >

где - максимальная вычислительная погрешность ПЭВМ.

Окончание численной процедуры поиска минимума функции может определяться выполнением следующего условия.

где - евклидова норма вектора, - малая положительная величина, задаваемая как параметр.

Графически метод простой градиентной минимизации в двумерном пространстве иллюстрируется на рис. 5.18.

Рис. 5.18

Недостатки

Основным недостатком метода является его низкая эффективность с точки зрения количества шагов поиска, а также с точки зрения затрат машинного времени.

Метод склонен к зацикливанию в местах резкого изменения направления «оврага» целевой функции.

Преимущества

Метод прост при программной реализации.

Метод надежен при использовании его в условиях сложной поверхности целевой функции.

Примеры работы программы:

В данном примере введена начальная точка (-10;-15) и точность 0,01. Программа приходит к точке (5; 3), что является минимумом целевой функции.

Метод простой градиентной оптимизации сходится за 399 итераций, а модифицированный метод наилучшей пробы за 845 итераций.

Выводы

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

Метод простой градиентной оптимизации сходится за 399 итераций, а модифицированный метод наилучшей пробы за 845 итераций.



Листинг метода случайного поиска с направляющей сферой:

procedure TMetNaiProb.Executing(var X : TVectorMass; Eps : real;var n : integer);

var

h,hrab,A1,A2: real;

g1 : array[1..100] of real;

g2 : array[1..100] of real;

g3 : array[1..100] of real;

m,i: integer;

begin оптимизация поиск случайный точка

n:=2;

m:=20;

h:=0.1;

hrab:=0.3;

A1:=0;

A2:=F(X[n-1,1],X[n-1,2]);

while (Abs(A2-A1)>Eps) Do

begin

A2:=A1;

for i:=1 to m do

begin

g1[i]:=Random(100)-50;

g2[i]:=Random(100)-50;

g3[i]:=Power((g1[i]*g1[i])+(g2[i]*g2[i]),0.5);

if g3[i]=0 then

g3[i]:=1;

g1[i]:=g1[i]/g3[i];

g2[i]:=g2[i]/g3[i];

end;

for i:=1 to m do

begin

A1:=F(X[n-1,1]+g1[i]*h,X[n-1,2]+g2[i]*h);

if A1<A2 then

begin

X[n,1]:=X[n-1,1]+g1[i]*hrab;

X[n,2]:=X[n-1,2]+g2[i]*hrab;

n:=n+1;

end;

end;

end;

n:=n-2;

end;

function TMetNaiProb.F(X1, X2 : real) : real;

begin

F := Power(X1 - 5, 2) + 2 * Power(X2 - 3, 2);

end;

Листинг метода простой градиентной минимизации:

procedure TOptGradMeth.GetSolution(var X : TVectorMass; Eps : real; var n : integer);

var

gradF : TVector;

h, step : real;

begin

n := 1;

h := 0.1;

gradF[1] := 100;

gradF[2] := 100;

while ((Abs(gradF[1]) > Eps) or (Abs(gradF[2]) > Eps)) do

begin

gradF[1] := (F(X[n, 1] + h, X[n, 2]) - F(X[n, 1], X[n, 2])) / h;

gradF[2] := (F(X[n, 1], X[n, 2] + h) - F(X[n, 1], X[n, 2])) / h;

n := n + 1;

X[n, 1] := X[n - 1, 1] - h * gradF[1];

X[n, 2] := X[n - 1, 2] - h * gradF[2];

end;

end;

function TOptGradMeth.F(X1, X2 : real) : real;

begin

F := Power(X1 - 5, 2) + 2 * Power(X2 - 3, 2);

end;



III Часть. Условная оптимизация функции

Постановка задачи

Рассматривается задача условной оптимизации (нелинейного программирования) с ограничивающими неравенствами:

Моему варианту соответствует:

f(x1, x2)	gi (x1, x2) ? 0, i = 1,m
(х1 - 5)2 + 2(х2 - 3)2	2х1 + х2 - 6
	-2х1+ х2- 4
	-х2 - 3

Данную задачу я буду решать двумя способами:

Сведением задачи условной оптимизации к задаче безусловной оптимизации;

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

Метод штрафной функции

Методы «штрафных» функций характеризуются простотой реализации алгоритмов и широкими возможностями применения большинства методов безусловной оптимизации. Это достигается с помощью специальной процедуры сведения задач условной оптимизации к безусловной.

Введем в рассмотрение функцию s(x,), именуемую в дальнейшем функцией «штрафа» («штрафной» функцией), со следующими свойствами.



(6.3)

В идеальном случае, при «штрафная» функция будет иметь вид, представленный на рис. 6.1

Гипотеза:

Предполагается, что задача , эквивалентна задаче безусловной оптимизации следующего вида:

, (6.4)

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис.6.1



При наличии нескольких ограничений , каждой из них будет соответствовать своя штрафная функция sj(x,).

Если ввести новую функцию , то решение задачи условной минимизации (6.1), (6.2) может быть приближенно получено с помощью итеративной процедуры безусловной оптимизации:

(6.5)

где последовательность коэффициентов i строится по правилу:

(6.6)

При этом, с ростом i , соответствующая последовательность решений задач безусловной оптимизации будет приближаться к решению задачи условной оптимизации (6.1), (6.2) :

(6.7)

Широко используются два основных подхода к построению функций «штрафа». Для решения своей задачи я буду использовать метод внешней точки, т.к. начальная точка может не удовлетворять всех ограничениям и при этом метод внутренней точки будет неприменим.



3.2 Метод внешней точки (Метод «штрафных» функций)

Идея метода

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

На рис. 6.3 представлены тенденции изменений итеративных решений с ростом коэффициентов i .

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рис.6.3

Штрафная функция будет иметь вид:

sj(2)(x,) = [max(0, gj(x))]2

В качестве подпрограммы для безусловной оптимизации будет использоваться метод сопряженных градиентов из I Части курсовой работы.



Пример работы программы при начальной точке внутри ограничений:

В данном примере выбрана начальная точка (0; 0), которая удовлетворяет всем ограничениям. Программа находит условный минимум целевой функции за 7 шагов методом простой градиентной оптимизации за 17 шагов модифицированным методом наилучшей пробыи сходится к значению (1.9; 2.3).

Пример работы программы при начальной точке вне ограничений:

В данном примере начальная точка не удовлетворяет всем ограничениям, поэтому вначале программа приходит к точке (5; 6), что является безусловным минимумом целевой функции, но после этого текущая точка перестает удовлетворять всем ограничениям и на целевую функцию налагается штраф, что приводит к “сваливанию” точки к границе одного из ограничений. Программа приходит к условному минимуму функции (1.9; 2.3) за 5 шагов методом простой градиентной оптимизации и за 16 шагов модифицированным методом наилучшей пробы.

Выводы

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

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

Листинг основной подпрограммы:

function MSF.Executing(var X : TArg; Eps : real; var n : integer; switcher : boolean) : boolean;

var

alfa : real;

Sol : boolean;

_X1, _X2 : TVector;

MyProsGrOpt : TProsGrOpt;

MyMetNaiProb : TMetNaiProb;

begin

n := 0;

MyProsGrOpt := TProsGrOpt.Create;

MyMetNaiProb := TMetNaiProb.Create;

_X1[1] := X[1, 1]; _X1[2] := X[1, 2]; _X2[1] := _X1[1] + 2 * Eps; _X2[2] := _X1[2] + 2 * Eps;

alfa := 1;

Sol := false;

while (((Abs(_X1[1] - _X2[1]) > Eps)or(Abs(_X1[2] - _X2[2])> Eps)) and (Sol = false)) do

begin

_X2[1] := _X1[1]; _X2[2] := _X1[2];

if ((G1(_X1[1], _X1[2]) <= 0) and (G2(_X1[1], _X1[2]) <= 0) and (G3(_X1[2]) <= 0)) then

begin

if (switcher = false) then Sol := MyProsGrOpt.GetSolution(_X1, Eps, 0)

else Sol := MyMetNaiProb.GetSolution(_X1, Eps, 0);

n := n + 1;

end

else

begin

if (switcher = false) then Sol := MyProsGrOpt.GetSolution(_X1, Eps, alfa)

else Sol := MyMetNaiProb.GetSolution(_X1, Eps, alfa);

n := n + 1;

if (switcher = false) then alfa := alfa * 7

else alfa := alfa * 1.6;

end;

X[n, 1] := _X1[1]; X[n, 2] := _X1[2];

end;

Executing := Sol;

end;

function MSF.G1(X1, X2 : real) : real;

begin

G1 := 2 * X1 + X2 - 6;

end;

function MSF.G2(X1, X2 : real) : real;

begin

G2 := - 2 * X1 + X2 - 4;

end;

function MSF.G3(X2 : real) : real;

begin

G3 := - X2 - 3;

end;

end.

Размещено на Allbest.ru