Методы нахождения безусловного и условного экстремума
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
ницы значение штрафа быстро убывает при продвижении внутрь допустимой области. На самой границе значение не определено, как и в предыдущем случае возможно появление недопустимых точек.
Штраф типа квадрата срезки.
, где
Этот штраф является внешним, и недопустимые точки не создают проблем по сравнению с допустимыми. Различие заключается том, что в допустимых точках штраф равен нулю. Этот вид штрафа удобен тем, что непрерывна и определена всюду. Параметр положителен и увеличивается от итерации к итерации.
Алгоритм метода:
Шаг 1. Задать начальные данные:
- начальная точка
- начальное значение штраф параметра
- параметр окончания работы алгоритма
Шаг 2. Построить штрафную функцию:
Шаг 3. Находим , доставляющее экстремум , методом Ньютона.
Шаг 4. Выполняется ли условие:
Да: , процесс решения закончен.
Нет: перейти к шагу 5.
Шаг 5.
, перейти к шагу 2.
Нахождение минимума целевой функции :
Исходные данные:
- начальная точка;
Ограничение на решение:
Преобразуем целевую функцию введением в неё заданного квадратичного штрафа:
Найдем минимум целевой функции с заданным квадратичным штрафом:
Совместное решение даёт:
Устремляя к нулю, получаем
То есть, при изменении от нуля до бесконечности, решение будет изменяться от минимума задачи с учётом ограничений до минимума функции без учёта ограничений.
Исследуем функцию при различных значениях параметра , то есть
1.
.
.
.
Таблица. Сведем все данные в таблицу:
Решением задачи условной оптимизации является точка: , значение целевой функции в которой равно: . Мы подтвердили, что при увеличении штрафного параметра все ограничения уменьшаются, что доставляет минимум задачи безусловной оптимизации. Наоборот, при уменьшении штрафного параметра до нуля вес ограничения возрастает, что доставляет минимум задачи условной оптимизации.
Рис 9. Графическое пояснение метода штрафных функций
Вывод: метод штрафных функций служит для решения задач условной оптимизации путем перевода их в задачу безусловной оптимизации. Как видно их рисунка, величина штрафного параметра сильно влияет на вид функции. При его увеличении "вес" ограничения в целевой функции уменьшается, и функция принимает свой обычный вид (без штрафной составляющей).
Рис.10 Интерфейс программы.
Библиографический список
.Микрюкова В.И. Методы оптимизации. - методические указания по выполнению курсовой работы. - Киров ВятГу,2004. - 41.
.Конспекты лекций.
3.Карманов В.Г. Математическое программирование. - М: Наука. Главная редакция физико-математической литературы, 1986
.Коршунов Ю.М. Математические основы кибернетики. - М: Энергия, 1980.
.В. И. Методы оптимизации. Методические указания по выполнению курсовой работы. Киров, 2010.
экстремум линейный функция программирование
Приложение
Листинг программы.
//---------------------------------------------------------------------------
#include
#include
#include
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"*Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------a[6] = {1,1,1,1,1,1}, nx[2] = {-10,-9}, E=1E-5;
//---------------------------------------------------------------------------f(double x[2])
{a[0]*x[0]*x[0]+a[1]*x[1]*x[1]+a[2]*x[0]*x[1]+a[3]*x[0]+a[4]*x[1]+a[5];
}
//---------------------------------------------------------------------------get_f_opt(double cur_x[2], double&df, double x[2])
{temp;= a[2]*a[2]-4*a[1]*a[0];[0] = (-a[2]*a[4]+2*a[3]*a[1])/temp;[1] = (-a[2]*a[3]+2*a[4]*a[0])/temp;= 1/2.*sqrt(pow(x[0]-cur_x[0],2)+pow(x[1]-cur_x[1],2));= ceil(df);f(x);
}
//---------------------------------------------------------------------------paint_line(TChart*& Chart, int count, int ie)
{x[2],x0_min,x0_max,dx0,temp,f,f_opt,df;i, j;_opt=get_f_opt(nx,df,x);>Series[2]->AddXY(x[0],x[1],"x*");(i=0,f=ceil(f_opt+df);i<ie;f+=df,i++)
{= a[3]*a[3]*a[1]*a[1]-a[3]*a[1]*a[2]*a[4]+a[1]*a[0]*a[4]*a[4]+
*a[1]*a[1]*a[0]*f-4*a[1]*a[1]*a[0]*a[5]-a[2]*a[2]*a[1]*f+[2]*a[2]*a[1]*a[5];(temp<0) {continue;i--;}= pow(temp,0.5);_min=(1/(2*(4*a[1]*a[0]-a[2]*a[2])))*(-4*a[3]*a[1]+2*a[2]*a[4]-4*temp);_max=(1/(2*(4*a[1]*a[0]-a[2]*a[2])))*(-4*a[3]*a[1]+2*a[2]*a[4]+4*temp);= (x0_max-x0_min)/count; x0_min-=dx0; x0_max+=dx0;(x[0]=x0_min;x[0]<x0_max;x[0]+=dx0)
{= a[4]*a[4]+2*a[4]*a[2]*x[0]+a[2]*a[2]*x[0]*x[0]-
*a[1]*a[0]*x[0]*x[0]-4*a[1]*a[5]+4*a[1]*f-
*a[1]*a[3]*x[0];(temp<0) temp=0; else temp = pow(temp,0.5);(j=-1;j<=1;j+=2)
{[1]=1/(2*a[1])*(-a[4]-a[2]*x[0]+j*temp);>Series[0]->AddXY(x[0],x[1]);
}
}[0] = x0_min+random(count)*dx0;= a[4]*a[4]+2*a[4]*a[2]*x[0]+a[2]*a[2]*x[0]*x[0]-
*a[1]*a[0]*x[0]*x[0]-4*a[1]*a[5]+4*a[1]*f-
*a[1]*a[3]*x[0];(temp<0) temp=0; else temp = pow(temp,0.5);[1]=1/(2*a[1])*(-a[4]-a[2]*x[0]+(random(2)*2-1)*temp);
}
}
//---------------------------------------------------------------------------grad(double x[2], double gr[2])
{[0] = 2*a[0]*x[0]+a[2]*x[1]+a[3];[1] = 2*a[1]*x[1]+a[2]*x[0]+a[4];
}
//---------------------------------------------------------------------------gess(double x[2], double ge[2][2])
{[0][0]=2*a[0]; ge[0][1]=ge[1][0]=a[2]; ge[1][1]=2*a[1];
}
//---------------------------------------------------------------------------get_alpha(double x[2], double s[2])
{t[2];[0] = 2*a[0]*s[0]*x[0]+ 2*a[1]*s[1]*x[1]+[2]*s[0]*x[1]+ a[2]*s[1]*x[0]+[3]*s[0] + a[4]*s[1];[1] = a[0]*s[0]*s[0]+ a[1]*s[1]*s[1]+[2]*s[0]*s[1];(fabs(t[0])<E) return 0;-0.5*t[0]/t[1];
}
//---------------------------------------------------------------------------TForm1::Calc(double E1, double E2, double count, int n)
{i,j,k; bool l;gr[2], //градиент[2], //направление[2][2]={{nx[0],nx[1]}}, //точки; //коэффициент поиска вдоль прямой_line(Chart1,count,n);->AddXY(x[0][0],x[0][1],"f(x[0])="+FloatToStrF(f(x[0]),ffGeneral,5,0));
->Cells[0][1] = 1;->Cells[1][1] = x[0][0];->Cells[2][1] = x[0][1];->Cells[3][1] = f(x[0]);->RowCount = 2;(k=0;1;k++)
{(x[k],gr);(sqrt(pow(gr[0],2)+(gr[1],2))AddXY(x[1][0],x[1][1],"f(x["+In