2 Dasar-Dasar Matematika Optimasi SS [PDF]

Citation preview

DASAR - DASAR MATEMATIKA OPTIMASI



1. Gradien f (x ) adalah fungsi bernilai skalar yang didefinisikan pada ruang vektor x



 x1  x   2 x   x3    .  x n 



Differensial f (x ) skalar dim(1x1) terhadap vektor



x



df



dim(nx1) akan menghasilkan d x



vektor dim(nx1). f ( x ) : gradien dari fungsi f (x )



 f   x   1  f   x  df f ( x )   2   . dx    .   f   x   n df



Untuk mencari titik-titik optimal dari suatu fungsi f (x ) , maka d x  f ( x )  0 . 2. Matriks Hessian Differensial vektor kolom dim(nx1) terhadap skalar dim(1x1) = vektor baris dim(1xn). Differensial vektor kolom dim(mx1) terhadap vektor kolom dim(nx1) = matriks dim(nxm).  f1  f   2 f   f3  ,   .   x m 



 x1  x   2 x   x3  ,   .  x n 



df m  df 2  df1 .......  dx dx1 dx1   1  df df df m  2 df  1 .......   dx dx2 dx 2  dx  2 ....... ........ ....... ........  df df m  df 2  1  ....... dx dx dx  n n   n



DASAR - DASAR MATEMATIKA OPTIMASI



1



 x12  x22  2 x1 x2    2 Misal: f ( x)  2 x1  3x 2  6 x 2  ,  4 x1  6 x2  4   



x  x   1 ,  x2 



2 x  2 x 2  1 d x 2 x 2  2 x1



df



2 4 6 x 2  6  6



H (x ) : Matriks Hessian dari f (x )  2 f  2 f H ( x)    2  xi x j   x



 2 f   x12x1   f H ( x)   x x  2 1  ....... 2   f  x n x1



2 f x1x 2 2 f x 2 x 2 ........ 2 f x n x 2



....... ....... ....... .......



2 f   x1x n  2 f  x 2 x n   ........  2 f  x n x n 



Operator Integral dan differensial mempunyai sifat linier, karena linier maka juga mempunyai sifat komutatif. Matriks Hessian merupakan Matriks Simetri (upper diagonal = lower diagonal) Untuk mengetahui minimum atau maksimum suatu fungsi f (x ) , maka



2 f  H ( x)  0 2 x



fungsi



2 f f (x ) adalah minimum dan  H ( x)  0 fungsi f (x) adalah maksimum. 2 x CONTOH : 2



2



f ( x)  3 x1  2 x 2  4 x1 x 2  6 x1  8 x2  6 maka,



 f   x  6 x  4 x 2  6 f ( x)   1    1   f   4 x1  4 x 2  8  x 2 



DASAR - DASAR MATEMATIKA OPTIMASI



2



 2 f  x x H ( x)   12 1   f  x x  2 1



2 f   x1x 2  6 4   2 f  4 4 x 2 x 2 



3. Matriks Definit Positip dan Definit Negatif  a11 a A   21 ......   a n1



a12



......



a 22



......



...... an2



...... ......



a1n  a 2 n  ......  a nn 



Minor utama ( principle minor ) dari A :  a11 A1   a11  , A2   a 21



 a11 a12   , A3  a 21  a 22   a31



A disebut Definit Positip



 a11 a13  a a 23  , …….. , An   21  .... a33    a n1



a12 a 22 a32



x T Ax  0



A disebut Definit Negatif



x T Ax



0



a12 a 22 .... an 2



a1n  .... a 2 n  .... ....   .... a nn  ....



x  R n x  R n



A disebut Semi Definit Positip



x T Ax  0



x  R n



A disebut Semi Definit Negatif



x T Ax  0



x  R n



Karena pembuktian xTAx yang harus berlaku untuk semua x sangat sulit, ahli matematik telah membuktikan bahwa:



A disebut Definit Positip



det  Ai  > 0



A disebut Definit Negatif



i  1,2,......, n



  1 i det  Ai  < 0



i  1,2,......, n



A disebut Semi Definit Positip DASAR - DASAR MATEMATIKA OPTIMASI



det  Ai   0



i  1,2,......, n



3



A Definit Negatif



-A Definit Positip



0



x T Ax



- x T Ax  0 x T   A x  0



-A Definit Positip



Cara ini adalah untuk membuktikan A Definit Negatif dengan menggunakan pembuktian bahwa (-A) Definit Positip. A disebut Matrik tidak definit ( indefinite )



 ketentuan-ketentuan definit / semi definit positif / negatif tidak dipenuhi CONTOH : 6 H  4



4 4



det  H 1   6  6 > 0 det  H 2 







6



4



4



4



 24  16  8



>0



Jadi, H adalah Definit Positip 4. Syarat Perlu Keoptimalan Digunakan untuk mencari calon/kandidat titik-titik optimal x * . Bila x * adalah titik optimal dari f (x ) maka :



f  x *   0



CONTOH : 6 x  4 x 2  6  f  x    1   4 x1  4 x 2  8 f  x   0



6 x1  4 x 2  6  0. 4 x1  4 x 2  8  0



2 x1  2  0 x1  1



x2  3



Jadi,  1 x *    adalah titik optimal dari f  x  3



5. Syarat Cukup Keoptimalan f  x *   0 dan H  x *  definit positip



x * titik minimum



f  x *   0 dan H  x *  definit negatif



x * titik maksimum



CONTOH : DASAR - DASAR MATEMATIKA OPTIMASI



4



 1 x*    3



6 H (x* )   4



4 4



definit positip



Jadi,  1 x *    adalah titik minimum dengan f  x *   3  8  12  6  24  6  3 3



Misal: f ( x)  2 x13  3 x 22  12 x1 x 2



1. Kandidat titik-titik optimal, syarat perlu: f  x   0



6 x12  12 x 2  0 sehingga



6 x12  12 x 2



6 x 2  12 x1  0 sehingga



6 x 2  12 x1



x12  4 x1 x12  4 x1  0











x1 x1  4  0 x1  0, x 2  0 x1  4, x 2  8 0  x *1    , 0 



Kandidat:



 4 x *2    8 



2. Cek yang memenuhi syarat sebagai titik optimal: 12 x1 H ( x)     12



 12 6 



 0 H ( x *1 )    12



 12  det(H 1 )  0 , det(H 2 )  144  0  indefinit 6 



 48 H ( x *2 )    12



 12  det(H 1 )  48  0 , det(H 2 )  144  0  definit positif 6 



x



*2



 4 0     memenuhi syarat sebagai titik optimal, sedangkan x *1    tidak. 8  0 



6. Fungsi Konveks dan Fungsi Konkav x



1



,



x



2







Rn



;



x



1



dan



x



2



adalah vektor dengan dimensi yang sama. Secara



matematis vektor sama dengan titik dengan syarat titik referensinya sama. Titik adalah isitilah pada geometri sedangkan vektor adalah istilah pada space. Perbedaannya, titik selalu dinyatakan pada koordinat tetap sedangkan vektor dinyatakan dalam koordinat tertentu yang bisa berubah-ubah (tidak tetap).  x1   2 x     0   0



DASAR - DASAR MATEMATIKA OPTIMASI 



5



Kombinasi Konveks dari menghubungkan



x



1



x



1



dengan



dan x



2



x



2



adalah titik-titik yang terletak pada garis lurus yang



, yang dipenuhi dengan persamaan:



x      x  1    x 1



   0,1



2



x1 =1



=0.5



Vektor/titik konveks yang ada dalam cone x1 dan x2



=0



x1



x2



f  x  fungsi konveks



x2



 f  x     f  x1   1    f  x 2  f(x) konveks



f(x1) +(1-)f(x2)



f(x1)



x1



f  x  fungsi konkav



f(x2)



f(x())



x2



x()



 - f  x  adalah konveks 



 



 



f  x     f x  1    f x 1



2



f(x) konveks



g(x)=-f(x) konkav



Fungsi Linier adalah Fungsi konveks dan Fungsi konkav







 



 



f  x     f x  1    f x 1



DASAR - DASAR MATEMATIKA OPTIMASI



2



6



f(x) linier



x1



x2



x()



f  x  fungsi konveks



 matriks Hessiannya adalah Semi Definit Positip f  x  fungsi konkav



 matriks Hessiannya adalah Semi Definit Negatif Fungsi konveks dan konkav ini dapat menggantikan syarat cukup semi definit positif dan negatif. Suatu himpunan S disebut konveks   x1+(1-) x2  S  x1,x2  S dan    [0,1]



x1



x1 x2 x2 S



S konveks



bukan konveks



Contoh: 2



2



f ( x)  3 x1  2 x 2  4 x1 x 2  6 x1  8 x2  6 6 H ( x)   4



4  definit positif 4



f(x) konveks Contoh: S adalah himpunan penyelesaian yang layak dari suatu permasalahan optimasi dengan batasan-batasan: 2 x1  x 2  4 x12  x 22  16 x1  0 DASAR - DASAR MATEMATIKA OPTIMASI



7



Buktikan bahwa S adalah konveks x2



S



konveks x1



x12+x2216 x10



DASAR - DASAR MATEMATIKA OPTIMASI



2x1+x24



8