Министерство образования Российской Федерации

ГОУ ВПО «Ижевский государственный технический университет»

Кафедра «Программное обеспечение»
Лабораторная работа №1

на тему:

«Нахождение минимума функции методом регулярного симплекса»

по курсу:

«Теория принятия решений»
Выполнили                                                                                    

студенты гр. 7-78-11                                                             Красноборов И.В.
Проверил                                                                              Лугачев П.П.
Ижевск 2010


1.   
ПОСТАНОВКА ЗАДАЧИ

Ознакомится с методом регулярного симплекса. Разработать программу, реализующую нахождение минимума функции  и построение промежуточных вычислений.
2.   
ТЕОРИТИЧЕСКИЕ СВЕДЕНИЯ

Симплекс или n-симплекс (от лат. simplex — простой) — геометрическая фигура, являющаяся n-мерным обобщением треугольника. Определяется как выпуклая оболочка n+1 точек, не лежащих в одной n-мерной гиперплоскости. Эти точки называются вершинами симплекса. Симплекс называется правильным, если все его рёбра имеют одинаковую длину.



Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.




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




3.   
АЛГОРИТМ


1) указание двух начальных точек x¹ и x²
2) достраивание третьей точки x³, до получения равностороннего треугольника
3) если длина стороны треугольника<ε, к пункту 9
4) упорядочивание вершин по возрастанию значению функции в них так, что бы в x³ оказались координаты вершины, в которых функция больше остальных
5) нахождение точки x⁴ такой, что бы она являлась отражением точки x³ относительно вектора (x¹, x²)
6) если f(x⁴)>f(x³), к пункту 8
7) x³= x⁴, к пункту 3
8) уменьшение размеров треугольника, к пункту 3
9) x¹ минимум функции




4.   
ОПИСАНИЕ КОНТРОЛЬНО ПРИМЕРА





5.   
ТЕКСТ ПРОГРАММЫ

//---------------------------------------------------------------------------
#include <vcl.h>

#pragma hdrstop

#include "math.h"

#include "Unit1.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

CRITICAL_SECTION cs;

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

__fastcall TForm1::TForm1(TComponent* Owner)

   : TForm(Owner)

{

   Form1->Image1->Canvas->Pen->Color=clWhite;

   InitializeCriticalSection( &cs );

}

//---------------------------------------------------------------------------
float k1=80,k2=160,c3=240,e=0.00001;

int zader = 5;

int Msh=1;
float f(float x1,float x2){

   return (float)(k1*x1*x1+k2*x2*x2+c3);

}
float f_x1(float x2){

   return (float)(2*k2*x2);

}
float f_x2(float x1){

   return (float)(2*k1*x1);

}
struct xy_{float x,y;};

Graphics::TBitmap *bb = new Graphics::TBitmap();

DWORD PN2_ID=0;

HANDLE PN2=NULL;

DWORD CALLBACK Grad_metod(void* Ptr){

   Form1->Memo1->Clear();

   xy_* xy=(xy_*)Ptr;

   AnsiString s;

   int shi=0;

   float x1[2],x2[2],p[2],Ak;

   x1[0]=(float)(xy->x -Form1->Image1->Width/2)/Msh;

   x1[1]=(float)(xy->y -Form1->Image1->Height/2)/Msh;

   Form1->Image1->Canvas->MoveTo(0,0);

   s=(String)"Хо = ["+(floor(x1[0]*1000000)/1000000)+" ; "+(floor(x1[1]*1000000)/1000000)+"]\r\n";

   Form1->Memo1->Lines->Add(s);

   p[0]=-(float)f_x1(x1[0]);

   p[1]=-(float)f_x2(x1[1]);

   float kz;

   int tz,ttz;

   while(1){

     if(shi<3){

          kz=(float)f(x1[1],x1[0]);

          bb->Assign(Form1->Image1->Picture->Bitmap);

          for(int j=-Form1->Image1->Width/2;j<Form1->Image1->Width/2;j++){

                tz=(f(j/Msh,-200/Msh)>kz)?1:-1;

                ttz=(f(-200/Msh,j/Msh)>kz)?1:-1;

                for(int i=-Form1->Image1->Height/2;i<Form1->Image1->Height/2;i++){

                   if(f(j/Msh,i/Msh)>kz && tz<0 || f(j/Msh,i/Msh)<kz && tz>0){

                         bb->Canvas->Pixels[i+200][j+200]=clBlack;

                         tz+=-2*tz;

                   }

                   if(f(i/Msh,j/Msh)>kz && ttz<0 || f(i/Msh,j/Msh)<kz && ttz>0){

                         bb->Canvas->Pixels[j+200][i+200]=clBlack;

                         ttz+=-2*ttz;

                   }

                }

          }

          Form1->Image1->Picture->Assign(bb);

     }

     shi++;

     if(PN2==NULL){PN2_ID=0;return 0;}

      Ak=-( f_x1(x1[0])*p[0] +f_x2(x1[1])*p[1] )/( p[0]*p[0]*f_x1(1) + p[1]*p[1]*f_x2(1));

     x2[0]=x1[0]+Ak*p[0];

     x2[1]=x1[1]+Ak*p[1];

     Form1->Image1->Canvas->Pen->Color=(Form1->RadioButton2->Checked)?clBlue:clGreen;

     Form1->Image1->Canvas->MoveTo(x1[0]*Msh+Form1->Image1->Width/2,x1[1]*Msh+Form1->Image1->Height/2);

     Form1->Image1->Canvas->LineTo(x2[0]*Msh+Form1->Image1->Width/2,x2[1]*Msh+Form1->Image1->Height/2);

     Form1->Image1->Repaint();

     s=(String)"Шаг "+shi+".\r\n       E = "+floor(sqrt( pow(x1[0]-x2[0],2)+pow(x1[1]-x2[1],2))*pow(10,13))/pow(10,13)+"\r\n       X = ["+(floor(x2[0]*1000000)/1000000)+" : "+(floor(x2[1]*1000000)/1000000)+"]\r\n";

     Form1->Memo1->Lines->Add(s);

     SendMessage(Form1->Memo1->Handle, WM_VSCROLL, MAKEWPARAM(SB_BOTTOM,0), 0);

     if(e>sqrt( pow(x1[0]-x2[0],2)+pow(x1[1]-x2[1],2) )){PN2_ID=0;return 0;}

     Sleep(100*zader);

     if(Form1->RadioButton1->Checked){

          p[0]=-f_x1(x2[0]);

          p[1]=-f_x2(x2[1]);

     }else if(Form1->RadioButton2->Checked){

          p[0]=-f_x1(x2[0])+p[0]*( pow(f_x1(x2[0]),2) +pow(f_x2(x2[1]),2) )/( pow(f_x1(x1[0]),2) +pow(f_x2(x1[1]),2) );

          p[1]=-f_x2(x2[1])+p[1]*( pow(f_x1(x2[0]),2) +pow(f_x2(x2[1]),2) )/( pow(f_x1(x1[0]),2) +pow(f_x2(x1[1]),2) );

     }

     x1[0]=x2[0];

     x1[1]=x2[1];

   }
   Form1->Memo1->Lines->Add("Готово!!!");

}
void VectorRotate(xy_* buf,xy_* t1,xy_* t2,float angle){

   angle=acos(((t2->x-t1->x))/sqrt(pow(t2->x-t1->x,2) + pow(t2->y-t1->y,2)))+angle*3.14/180;

   if(t2->y-t1->y<0)angle*=-1;

   float len=sqrt(pow(t2->x-t1->x,2)+pow(t2->y-t1->y,2));

   buf->x=len*cos(angle)+t1->x;

   buf->y=len*sin(angle)+t1->y;

}
struct TwoPoint{xy_ t1,t2;};

xy_ ptmp;

bool flag=0;

DWORD CALLBACK Treangle_metod(void* Ptr){

   Form1->Memo1->Clear();

   AnsiString s;

   TwoPoint* ptr=(TwoPoint*)Ptr;

   int shi=0;

   xy_ t[4]={{(ptr->t1.x-Form1->Image1->Width/2)/Msh,

                  (ptr->t1.y-Form1->Image1->Height/2)/Msh},

                 {(ptr->t2.x-Form1->Image1->Width/2)/Msh,

                  (ptr->t2.y-Form1->Image1->Height/2)/Msh}

                };

   VectorRotate(&t[2],&t[0],&t[1],60);

   s=(String)"Х0 = ["+(floor(t[0].x*1000000)/1000000)+" ; "+(floor(t[0].y*1000000)/1000000)+"]\r\nХ1 = ["+(floor(t[1].x*1000000)/1000000)+" ; "+(floor(t[1].y*1000000)/1000000)+"]\r\n";

   Form1->Memo1->Lines->Add(s);

   Form1->Image1->Canvas->Pen->Color=clBlack;

   while(PN2!=NULL && e<sqrt(pow(t[1].x-t[0].x,2)+pow(t[1].y-t[0].y,2)) ){

     Form1->Image1->Canvas->MoveTo(t[0].x*Msh+Form1->Image1->Width/2,t[0].y*Msh+Form1->Image1->Height/2);

     Form1->Image1->Canvas->LineTo(t[1].x*Msh+Form1->Image1->Width/2,t[1].y*Msh+Form1->Image1->Height/2);

     Form1->Image1->Canvas->LineTo(t[2].x*Msh+Form1->Image1->Width/2,t[2].y*Msh+Form1->Image1->Height/2);

     Form1->Image1->Canvas->LineTo(t[0].x*Msh+Form1->Image1->Width/2,t[0].y*Msh+Form1->Image1->Height/2);

     Form1->Image1->Repaint();

     shi++;

     s=(String)"Шаг "+shi+".\r\n       E = "+floor(sqrt(pow(t[1].x-t[0].x,2)+pow(t[1].y-t[0].y,2))*pow(10,13))/pow(10,13)+"\r\n       X = ["+(floor(t[2].x*1000000)/1000000)+" : "+(floor(t[2].y*1000000)/1000000)+"]\r\n";

     Form1->Memo1->Lines->Add(s);

     Sleep(100*zader);

     //упорядочивание вершин

     if(f(t[0].x,t[0].y)>f(t[1].x,t[1].y)){

          t[3].x=t[0].x; t[3].y=t[0].y;

          t[0].x=t[1].x; t[0].y=t[1].y;

          t[1].x=t[3].x; t[1].y=t[3].y;

     }

     if(f(t[1].x,t[1].y)>f(t[2].x,t[2].y)){

          t[3].x=t[1].x; t[3].y=t[1].y;

          t[1].x=t[2].x; t[1].y=t[2].y;

          t[2].x=t[3].x; t[2].y=t[3].y;

     }

     if(f(t[0].x,t[0].y)>f(t[1].x,t[1].y)){

          t[3].x=t[0].x; t[3].y=t[0].y;

          t[0].x=t[1].x; t[0].y=t[1].y;

          t[1].x=t[3].x; t[1].y=t[3].y;

     }

     //определение 4 вершины

     t[3].x=(t[0].x+t[1].x)/2;

     t[3].y=(t[0].y+t[1].y)/2;

     t[3].x+=t[3].x-t[2].x;

     t[3].y+=t[3].y-t[2].y;

     if(f(t[3].x,t[3].y)<f(t[2].x,t[2].y)){ t[2].x=t[3].x; t[2].y=t[3].y;

     }else{

          t[1].x=(t[0].x+t[1].x)/2;

          t[1].y=(t[0].y+t[1].y)/2;

          t[0].x=t[1].x-(t[1].x-t[2].x)/3;

           t[0].y=t[1].y-(t[1].y-t[2].y)/3;

          VectorRotate(&t[2],&t[0],&t[1],-60);

     }

   }
   Form1->Memo1->Lines->Add("Готово!!!");

   PN2_ID=0;

   return 0;

}
//---------------------------------------------------------------------------
void __fastcall TForm1::Image1MouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift,

           int X, int Y)

{

   PN2=NULL;

   while(PN2_ID!=0) Sleep(10);

   if(RadioButton3->Checked){

     Image1->Canvas->Pen->Color=clYellow;

     Image1->Canvas->Pen->Width=5;

     Image1->Canvas->Ellipse(X,Y,X+1,Y+1);

     Image1->Canvas->Pen->Width=1;

     flag=!flag;

     if(flag){

          ptmp.x=X;

          ptmp.y=Y;

     }else{

          TwoPoint* tp = new TwoPoint ;

          tp->t1.x=ptmp.x;

          tp->t1.y=ptmp.y;

          tp->t2.x=X;

          tp->t2.y=Y;

          PN2=CreateThread(0, 0, Treangle_metod, tp, 0, &PN2_ID);

     }

   }else{

     Image1->Picture->Assign(0);

     xy_* xy = new xy_ ;

     xy->x=X;

     xy->y=Y;

     PN2=CreateThread(0, 0, Grad_metod, xy, 0, &PN2_ID);

   }

}

//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton3Click(TObject *Sender)

{

   flag=0;

}

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






6.   
СПИСОК ЛИТЕРАТУРЫ

1.         Д. Химмельблау Прикладное нелинейное программирование. – М: Издательство «Мир», 1975.

2.         http://ru.wikipedia.org/wiki/Симплекс-метод