Применение численных методов для задач математического программирования

Для аналитического решения задачи типа

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

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

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

где л - вектор множителей Лагранжа размерности [mxl],соответствующей количеству ограничений gj(х)<0, j=l, ...,m .

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

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

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

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

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

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

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

возможных сочетаниях активных и пассивных ограничении, включая крайние случаи:

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

В результате применения НУ для всех возможных сочетаний активных

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

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

То есть:

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

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

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

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

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

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

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

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

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

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

Таким образом, при подтверждении положительной определенности

Матрицы Гессе в стационарных точках, в которых согласно НУ возможно было

Нахождение условного локального минимума, то есть при > 0 , такие

стационарные точки переводятся в число точек условного локального минимума целевой функции f(x) при условиях gj(x) < 0, j=l,...,m :

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

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

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

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

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

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

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

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

I. Найдём безусловный минимум функции:

Стационарная точка:

Проверим достаточные условия минимума функции по критерию Сильвестра, построив, матрицу Гессе:

Найдём значение функции в стационарной точке:

II.

Найдём условный минимум:

Запишем функцию Лагранжа:

Стационарная точка:

Проверим достаточные условия минимума функции по критерию Сильвестра, построив, матрицу Гессе:

Найдём значение функции в стационарной точке:

III.

Найдём условный минимум:

Запишем функцию Лагранжа:

Стационарная точка:

Найденная стационарная точка не удовлетворяет условию не отрицательности множителей Лагранжа.

Проверим достаточные условия минимума функции по критерию Сильвестра, построив, матрицу Гессе:

Найдём значение функции в стационарной точке:

IV.

Найдём условный минимум:

Запишем функцию Лагранжа:

Стационарная точка:

Найденная стационарная точка не удовлетворяет условию не отрицательности множителей Лагранжа.

Проверим достаточные условия минимума функции по критерию Сильвестра, построив, матрицу Гессе:

Найдём значение функции в стационарной точке:

V.

Найдём угловую точку:

Найдём значение функции в точке:

VI.

Найдём угловую точку:

Найдём значение функции в точке:

VII.

Найдём угловую точку:

Найдём значение функции в точке:

VIII.

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

6

Не удовлетворяют ограничениям:

IX. Находим минимальное значение функции:

Построим график:

Выводы

Построена целевая функция f(x) с помощью линий уровня С1,С2,…С8;

Причём С1>С2>С3…>C8; ограничения gj < О, j=1,2,3, выделяющие множество допустимых аргументов (параметров). Точки условного локального минимума определены как f1, f2, f3…f7, причём на рисунке видно, что точки f1 и f3 не удовлетворяют всем ограничениям gj ? 0;

Угловые точки: f5, f6, f7.

Как следует из рассмотренной выше методики в результате сравнения значений функции в точках условного локального минимума f2 и в «угловых» точках f5, f6, f7 определяются координаты условного глобального минимума, которые на рисунке обозначены f2.

Применение численных методов для задач математического программирования

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

Метод заключается в последовательном сравнении значений функции в конечном числе точек, равномерно распределенных на отрезке [a,b].

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

1. Дискретизация точек на отрезке:

.

2. Определение приближенного минимума целевой функции:

,

где - точный минимум функции на отрезке [a,b].

Очевидно, что точность метода определяется расстоянием между точками на начальном отрезке неопределенности (количеством точек дискретизации - n), т.е. количеством экспериментов (оценок значений функции) производимых в этих точках.

где Ln - значение последнего интервала неопределенности.

Эффективность любого метода одномерного поиска оценивается величиной:

.

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

На рис. 1 изображена функция, имеющая два локальных минимума, один из которых (левый) - глобальный.

Рис. 1

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

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

· Для повышения точности метода согласно его логике рекомендуется «сгущать» точки экспериментов по мере приближения к минимуму.

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

· Метод позволяет осуществлять поиск глобального минимума функции.

Блок схема алгоритма метода простого перебора

Метод покоординатного спуска

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

Метод состоит в том, что минимум целевой функции ищется по всем аргументам (координатам) поочерёдно (см. рис. 2). С этой целью рекомендуется использовать методы одномерного поиска.

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

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

где - неограниченное арифметическое пространство размерности .

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

Рис. 2

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

1)Предположим, что в процессе реализации алгоритма получена некоторая промежуточная точка x(k). В этом положении фиксируются все составляющие вектора x со значениями: x1(k), x2(k),…., xi-1(k), xi+1(k),…, xn(k), кроме переменной xi(k) , которая должна варьироваться в направлении уменьшения целевой функции.

2)Решается задача одномерного минимума (одномерной оптимизации) по xi(k) и затем полученные значения аргумента фиксируются.

3)Из числа остальных переменных выбирается j-тая переменная и назначается варьируемым аргументом.

4)Процедура 2) повторяется для j-той переменной, при этом xi(k+1) остаётся фиксированной! В результате получаем:

Одной (в честности, k-ой) итерацией покоординатного поиска считается полное прохождение всеми переменными xi , процедуры одномерной оптимизации и получение всех значений xi(k+1), соответствующих одномерному минимуму целевой функции по этим координатам.

5)После проведения очередной, k-ой итерации осуществляется сравнение полученного значения целевой функции в полученной точке x(k+1) с предыдущим ее значением , т.е.

<

Если разница между ними меньше заданного малого >0, принимается решение об окончании процедуры. В противном случае происходит переход на пункт 1).

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

· Метод имеет низкую эффективность (многократное повторение итераций).

· Метод плохо работает при ярко выраженной «овражности» функции => возникает «заедание» (зацикливание) см. рис. 3.

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

· Относительная простота программирования и тестирования при отладке программы.

Блок-схема алгоритма метода покоординатного спуска

Метод сопряженных градиентов

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

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

.

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

,

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

,

где коэффициент должен удовлетворять условиям сопряжения

.

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

Исходя из двух последних условий, можно получить выражения (соотношения) для коэффициентов , а именно

.

Что качается шага , он выбирается из условия минимизации функции в направлении .

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

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

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

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

Алгоритм Флетчера - Ривса

1. Выбрать начальную точку поиска ;

2. Определить направление начального поиска ;

3. Осуществить одномерный поиск точки

;

4. Определить новое направление поиска ,

где .

5. В общем случае после точки вычисляется градиент функции и определяется направление

, где .

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

6. Производится проверка условия окончания поиска минимума.

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

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

· Метод сопряженных градиентов успешно применяется не для квадратичных гладких функций, у которых матрица Гессе мало меняется в процессе спуска. В этом случае поиск минимума будет заканчиваться за более, чем n шагов.

Недостатки:

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

Блок-схема алгоритма метода сопряженных градиентов:

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

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

Все методы условной оптимизации делятся на 2 группы:

1. Методы сведения задач условной оптимизации к безусловной.

2. Методы непосредственно учитывающие ограничения.

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

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

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

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

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

(*)

Введем в рассмотрение функцию , имеющую свойства:

Будем считать, что задача (*) эквивалентна задаче безусловной оптимизации следующего вида:

Другими словами, если ввести функцию:

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

зададимся последовательностью коэффициентов такими, что .

Тогда итеративная процедура решения представляется в виде:

Различают два основных подхода к построению функции штрафа:

1. Метод внутренней точки (метод барьерных функций);

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

В данной задаче мы будем использовать метод внешней точки.

Метод внешней точки

Идея метода:

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

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

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

Рис. 4

Этот метод применим для ограничений типа равенств и неравенств.

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

Примеры «штрафных» функций:

а) Для ограничений типа равенств:

функция штрафа:

s(2)(x,) = [ gj(x)]2k , k=1,2,3,………,n

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

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

· Метод применим при любых ограничениях.

· Начало поиска может происходить из любой точки арифметического пространства Rn.

Недостатки:

· Элементы последовательности могут не находиться в допустимой области .

· Не все методы численной безусловной оптимизации применимы для ряда функций штрафа.

· Общим недостатком метода штрафных функций является возрастание овражности функции с ростом коэффициентов штрафа .

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

Метод покоординатного спуска

Начальная точка:

Шаг:

Точность:

Коэффициент штрафа: 1.25

Результат:

Метод Сопряженных градиентов

Начальная точка:

Шаг:

Точность:

Коэффициент штрафа: 1

Результат:

Программная реализация

Метод покоординатного спуска

//$$---- Form CPP ----

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include <math.h>

#include <vector.h>

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

double shp = 1.25;

double shp1 = shp;

double shp2 = shp;

double shp3 = shp;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

vector<double> Simple(double(*f)(vector<double>), vector<double> x0, double h)

{

double fxk, fxk1;

vector<double> xk = x0;

vector<double> xk1 = x0;

for(int i=0;i<2;i++)

{

do

{

fxk = f(xk);

xk1[i] = xk[i] + h;

fxk1 = f(xk1);

xk = xk1;

}

while( fxk > fxk1 );

}

return( xk1 );

}

vector<double> Descent(double(*f)(vector<double>), vector<double> x0, double h, double e)

{

vector<double> xk = x0;

vector<double> xk1 = x0;

for(int NumOfMetIt=1;;NumOfMetIt++)

{

Form1->LabeledEdit3->Text = IntToStr(NumOfMetIt);

xk1 = Simple(f, xk, h);

Form1->Series1->AddXY(xk[0], xk[1], "", Form1->ColorBox1->Selected);

Form1->Series1->AddXY(xk1[0], xk1[1], "", Form1->ColorBox1->Selected);

if( fabs(f(xk)-f(xk1)) < e )

return( xk1 );

else

xk = xk1;

}

}

//---------------------------------------------------------------------------

double g1(vector<double> x)

{

return( x[0]+x[1]-2.0 );

}

double g2(vector<double> x)

{

return( -x[0]+x[1]-1.0 );

}

double g3(vector<double> x)

{

return( -x[1]-3.0 );

}

//---------------------------------------------------------------------------

double f(vector<double> x)

{

return( 2.0*(x[0]-3.0)*(x[0]-3.0)+(x[1]-2.0)*(x[1]-2.0) );

}

//---------------------------------------------------------------------------

double rf(vector<double> x)

{

return( 2.0*(x[0]-3.0)*(x[0]-3.0)+(x[1]-2.0)*(x[1]-2.0) +

shp1*(x[0]+x[1]-2.0)*(x[0]+x[1]-2.0) +

shp2*(-x[0]+x[1]-1.0)*(-x[0]+x[1]-1.0) +

shp3*(-x[1]-3.0)*(-x[1]-3.0) );

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{

vector<double> x0;

x0.push_back(-3.75);

x0.push_back(-2.0);

vector<double> res = Descent(f, x0, 1e-3, 1e-2);

LabeledEdit1->Text = FloatToStrF(res[0],ffFixed,10,2);

LabeledEdit2->Text = FloatToStrF(res[1],ffFixed,10,2);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

double e = 1e-2;

vector<double> prev;

prev.push_back(-3.75);

prev.push_back(-2.0);

Form1->Series1->Clear();

vector<double> last;

for(int NumOfIt=1;;NumOfIt++)

{

Form1->LabeledEdit6->Text = IntToStr(NumOfIt);

last = Descent(rf, prev, 1e-3, e);

if( fabs(rf(prev)-rf(last))<e ||

fabs(prev[0]-last[0])<e ||

fabs(prev[1]-last[1])<e )

break;

else

{

if( g1(last)<=0 )

shp1 = 0.0;

else

shp1*= 12.0;

if( g2(last)<=0 )

shp2 = 0.0;

else

shp2*= 12.0;

if( g3(last)<=0 )

shp3 = 0.0;

else

shp3*= 12.0;

}

prev = last;

}

LabeledEdit4->Text = FloatToStrF(last[0],ffFixed,10,2);

LabeledEdit5->Text = FloatToStrF(last[1],ffFixed,10,2);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button4Click(TObject *Sender)

{

Form1->Series3->AddXY( 0.500, 1.500, "", Form1->ColorBox1->Selected);

Form1->Series3->AddXY(-4.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series4->AddXY(-4.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series4->AddXY( 5.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series5->AddXY( 5.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series5->AddXY( 0.502, 1.501, "", Form1->ColorBox1->Selected);

}

//---------------------------------------------------------------------------

Метод сопряженных градиентов

//$$---- Form CPP ----

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include <math.h>

#include <vector.h>

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

double shp = 1;

double shp1 = shp;

double shp2 = shp;

double shp3 = shp;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

vector<double> Simple(double(*f)(vector<double>), vector<double> x0, double h)

{

double fxk, fxk1;

vector<double> xk = x0;

vector<double> xk1 = x0;

for(int i=0;i<2;i++)

{

do

{

fxk = f(xk);

xk1[i] = xk[i] + h;

fxk1 = f(xk1);

xk = xk1;

}

while( fxk > fxk1 );

}

return( xk1 );

}

vector<double> Conjugate(double(*f)(vector<double>), vector<double>(*agrad)(vector<double>), vector<double> x0, double h, double e)

{

vector<double> xk = x0;

vector<double> xk1 = x0;

vector<double> agradXk, agradXk1, Sk, Sk1(2);

for(int NumOfMetIt=1;;NumOfMetIt++)

{

Form1->LabeledEdit3->Text = IntToStr(NumOfMetIt);

agradXk = agrad(xk);

Sk = agradXk;

xk1 = Simple(f, xk, h);

agradXk1 = agrad(xk1);

double Bk = (pow(agradXk1[0],2)+pow(agradXk1[1],2))/(pow(agradXk[0],2)+pow(agradXk[1],2));

Sk1[0] = agradXk1[0] + Bk*Sk[0];

Sk1[1] = agradXk1[1] + Bk*Sk[1];

Form1->Series1->AddXY(xk[0], xk[1], "", Form1->ColorBox1->Selected);

Form1->Series1->AddXY(xk1[0], xk1[1], "", Form1->ColorBox1->Selected);

if( fabs(f(xk1) - f(xk)) < e )

return( xk1 );

else

xk = xk1;

}

}

//---------------------------------------------------------------------------

double g1(vector<double> x)

{

return( x[0]+x[1]-2.0 );

}

double g2(vector<double> x)

{

return( -x[0]+x[1]-1.0 );

}

double g3(vector<double> x)

{

return( -x[1]-3.0 );

}

//---------------------------------------------------------------------------

double f(vector<double> x)

{

return( 2.0*(x[0]-3.0)*(x[0]-3.0)+(x[1]-2.0)*(x[1]-2.0) );

}

//---------------------------------------------------------------------------

vector<double> agradf(vector<double> x0)

{

vector<double> x = x0;

x[0] = -(4.0*(x0[0]-3.0));

x[1] = -(2.0*(x0[1]-2.0));

return( x );

}

//---------------------------------------------------------------------------

vector<double> agradrf(vector<double> x0)

{

vector<double> x = x0;

x[0] = -(4.0*(x0[0]-3.0) + 2.0*shp1*(x[0]+x[1]-2.0) - 2.0*shp2*(-x[0]+x[1]-1.0));

x[1] = -(2.0*(x0[1]-2.0) + 2.0*shp1*(x[0]+x[1]-2.0) + 2.0*shp2*(-x[0]+x[1]-1.0) - shp3*(-x[1]-3.0));

return( x );

}

//---------------------------------------------------------------------------

double rf(vector<double> x)

{

return( 2.0*(x[0]-3.0)*(x[0]-3.0)+(x[1]-2.0)*(x[1]-2.0) +

shp1*(x[0]+x[1]-2.0)*(x[0]+x[1]-2.0) +

shp2*(-x[0]+x[1]-1.0)*(-x[0]+x[1]-1.0) +

shp3*(-x[1]-3.0)*(-x[1]-3.0) );

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

double e = 1e-3;

vector<double> x0;

x0.push_back(-3.75);

x0.push_back(-2.0);

vector<double> res = Conjugate(f, agradf, x0, 1e-5, e);

LabeledEdit1->Text = FloatToStrF(res[0],ffFixed,10,2);

LabeledEdit2->Text = FloatToStrF(res[1],ffFixed,10,2);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{

double e = 1e-3;

vector<double> prev;

prev.push_back(-3.75);

prev.push_back(-2.0);

Form1->Series1->Clear();

vector<double> last;

for(int NumOfIt=1;;NumOfIt++)

{

Form1->LabeledEdit6->Text = IntToStr(NumOfIt);

last = Conjugate(rf, agradrf, prev, 1e-5, e);

if( fabs(rf(prev)-rf(last))<e ||

fabs(prev[0]-last[0])<e ||

fabs(prev[1]-last[1])<e )

break;

else

{

if( g1(last)<=0 )

shp1 = 0.0;

else

shp1*= 9.0;

if( g2(last)<=0 )

shp2 = 0.0;

else

shp2*= 9.0;

if( g3(last)<=0 )

shp3 = 0.0;

else

shp3*= 9.0;

}

prev = last;

}

LabeledEdit4->Text = FloatToStrF(last[0],ffFixed,10,2);

LabeledEdit5->Text = FloatToStrF(last[1],ffFixed,10,2);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button4Click(TObject *Sender)

{

Form1->Series3->AddXY( 0.500, 1.500, "", Form1->ColorBox1->Selected);

Form1->Series3->AddXY(-4.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series4->AddXY(-4.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series4->AddXY( 5.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series5->AddXY( 5.000,-3.000, "", Form1->ColorBox1->Selected);

Form1->Series5->AddXY( 0.502, 1.501, "", Form1->ColorBox1->Selected);

}

//---------------------------------------------------------------------------

Выводы

Выполнив в курсовой работе два оптимизационных метода:

1. Метод покоординатного спуска

2. Метод сопряженных градиентов

И на основании полученных результатов, сделаем следующие выводы:

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

Так же можно сказать, что скорость сходимости обоих методов зависит от шага и точности. А от подбора коэффициента штрафной функции зависит точность результата.

численный метод задача оптимизация

Список литературы

1. Усачов В. Е. Методы оптимизации организационно-технических систем. (Учебное пособие). 2009 г.

2. Усачов В. Е. Методы оптимизации организационно-технических систем. (Учебное пособие для выполнения курсовой работы). 2005 г.

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