METODE FUNGSI PENALTI EKSTERIOR. Skripsi. Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

METODE FUNGSI PENALTI EKSTERIOR

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun Oleh : Maria Martini Leto Kurniawan NIM : 013114019

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2008


METODE FUNGSI PENALTI EKSTERIOR

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun Oleh : Maria Martini Leto Kurniawan NIM : 013114019

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2008

i


EXTERIOR PENALTY FUNCTIONS METHOD

THESIS

Presented as Partial Fulfillment of the Requirements to Obtain the Sarjana Sains Degree in Mathematics

By : Maria Martini Leto Kurniawan Student Number : 013114019

MATHEMATICS STUDY PROGRAM MATHEMATICS DEPARTMENT FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2008

ii


iii


iv


TUHAN, PERISAIKU (Mzm 28 : 1-9)

Orang-orang yang menabur dengan mencucurkan air mata, akan menuai dengan bersorak sorai, (Mzm 126:5)

Segala sesuatu indah pada waktunya.

(Pengkotbah 3:11)

Bila selama ini aku masih bertahan ... Semua ini aku persembahkan hanya karena cintaku untuk : Tuhan Yesus dan Bunda Maria, Teman dan Bunda tersayang yang dengan setia mendengarkan semua kepedihan hatiku…

Bapa dan Mama tercinta.... Ini janji Rita....walaupun perjalanan ini masih panjang, tapi aku senang bisa membuat bapa dan mama tersenyum kembali…

No Ovik tercinta ...Kamu adalah pemberian terindah yang Tuhan berikan buat oncu, dan oncu tidak akan pernah menyerah berjuang dalam hidup ini karena “KAMU”…

Cece,

Ka

Nano,

Adeline,

Ati,

Ka

Tonce

&

No

Faldi....Aku sangat-sangat bersyukur dan bangga menjadi bagian dari kalian semua…I love u all....

Isto yang sudah hadir dan mewarnai hidupku... Aku mau kamu tahu bahwa semenjak ada dirimu semua terasa indah....Thanks for your love…

v


vi


KATA PENGANTAR

Puji syukur penulis panjatkan kepada Tuhan Yesus atas segala kasih dan perlindungan-Nya sehingga penulisan skripsi ini dapat terselesaikan. Skripsi ini berjudul : “ METODE FUNGSI PENALTI EKSTERIOR “, yang diajukan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika, Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma Yogyakarta. Penulisan skripsi ini tidak lepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin menyampaikan ucapan terima kasih kepada: 1. Ibu Lusia Krismiyati, S.Si, M.Si sebagai dosen pembimbing yang penuh perhatian dan kesabaran telah membimbing serta memberi saran dan kritik kepada penulis selama proses penulisan skripsi ini. 2. Bapak Y.G. Hartono, S.Si, M.Sc sebagai dosen pembimbing akademik. 3. Bapak Herry Pribawanto.S, S.Si, M.Si yang telah memberikan pinjaman buku-buku matematika yang sangat membantu penulis dalam menyelesaikan skripsi ini. 4. Bapak St. Eko Hari Parmadi, S.Si.,M.Kom sebagai dosen panguji. 5.

Ir. Greg. Heliarko, S.J., S.S., B.S.T., M.Sc., M.A., selaku Dekan FST-USD.

6.

Segenap dosen dan karyawan sekretariat FST yang telah mendidik dan meyediakan fasilitas yang sangat bermanfaat bagi penulis.

ix


7. Bapa, Mama, No Ovik, Cece, Ka Nano, Adeline, Ati, Ka Tonce, No Faldi dan seluruh keluarga besarku tercinta atas kasih sayang, doa, semangat, dukungan serta kesabarannya selama ini. 8. No Ie, atas segala bantuan, doa dan dorongan buat saya. Terima kasih untuk semuanya. 9. Isto untuk segala kasih dan kesabaran yang begitu tulus. Saya sangat bersyukur mengenal kamu dan menjadi bagian dari hidupmu karena kau telah mengajarkan saya begitu banyak hal 10. Sahabat-sahabatku seperjuangan angkatan 2001: Agnes, Alam, Fanya, Daniel, Teddi, Deta, Vrysca, Upik, Yuli, Dani, Tabita, Andre, Indah, Ariel, Erika, Wiwit, Maria, Very, Ray, dan April. 11. Mas Nadi yang selalu setia membantu dan menyemangati saya. Ma kasih mas. 12. Meggy atas segala bantuan dan dorongan semangat yang begitu tulus. Ma kasih Gy. 13. Semua pihak yang telah membantu penulis baik secara langsung maupun tidak langsung hingga selesainya penulisan skripsi ini. Penulis menyadari bahwa skripsi ini masih banyak kekurangannya. Oleh karena itu, penulis mengucapkan terima kasih bila ada kritik dan saran yang dapat membangun penulis. Penulis berharap semoga skripsi ini dapat bermanfaat dan menjadi referensi bagi pembaca. Yogyakarta, 26 Mei 2008

Penulis

x


PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam kutipan atau daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 26 Mei 2008 Penulis,

Maria Martini Leto Kurniawan

xi


DAFTAR ISI Halaman HALAMAN JUDUL .....................................................................................

i

HALAMAN PERSETUJUAN PEMBIMBING ...........................................

iii

HALAMAN PENGESAHAN .......................................................................

iv

HALAMAN PERSEMBAHAN ....................................................................

v

HALAMAN HAK CIPTA ...........................................................................

vi

ABSTRAK ....................................................................................................

vii

ABSTRACT ..................................................................................................

viii

KATA PENGANTAR ...................................................................................

ix

PERNYATAAN KEASLIAN KARYA ........................................................

xi

DAFTAR ISI ..................................................................................................

xii

DAFTAR GAMBAR .....................................................................................

xiv

DAFTAR TABEL ..........................................................................................

xv

BAB I

PENDAHULUAN ...........................................................................

1

A. Latar Belakang Masalah ....................................................................

1

B. Perumusan Masalah ...........................................................................

3

C. Batasan Masalah ................................................................................

4

D. Tujuan Penulisan ...............................................................................

4

E. Manfaat Penulisan .............................................................................

4

F. Metode Penulisan ...............................................................................

5

G. Sistematika Penulisan ........................................................................

5

xii


TOPOLOGI DI R n DAN TEORI OPTIMISASI .............................

7

A. Ruang Euclid dan Matriks ......................................................................

7

B. Topologi di R n ........................................................................................

8

BAB II

C. Fungsi Kontinu dan Fungsi Terdiferensial ................................................. 11 D. Himpunan Konveks dan Fungsi Konveks………………………………. 15 E. Syarat Optimalitas Masalah Tidak Berkendala…………………………. 21 F. Teori Optimisasi………………………………………………………… 25 G. Metode Newton………………………………………………………..

27

BAB III METODE FUNGSI PENALTI EKSTERIOR .................................

30

A. Konsep Fungsi Penalti ............................................................................

30

B. Interpretasi Geometris Fungsi Penalti ....................................................

37

C. Metode Fungsi Penalti Eksterior .............................................................

41

1. Bentuk Fungsi Penalti Eksterior……………………………………

41

2. Algoritma Metode Fungsi Penalti Eksterior……………………….

43

D. Konvergensi Metode fungsi Penalti Eksterior………………………… BAB IV

PENUTUP ......................................................................................

56 63

DAFTAR PUSTAKA ........................................................................................

65

LAMPIRAN .................................................................................................. ….

66

xiii


DAFTAR GAMBAR Halaman Gambar 1.1.1 Minimum

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

1

Gambar 2.4.1 Ilustrasi dari himpunan konveks dan tidak konveks................

15

Gambar 2.4.2 Lingkaran

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

16

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

16

Gambar 2.4.3 Parabola

sama dengan maksimum

Gambar 2.7.1 Diagram Alir Algoritma Metode Newton.....................................

29

Gambar 3.1.1 Grafik Penalti............................................................................

35

Gambar 3.1.2 Grafik Fungsi Tambahan...........................................................

35

Gambar 3.2.1 Geometri Fungsi Penalti.............................................................

39

Gambar 3.3.1 Diagram Alir Algoritma Metode Fungsi Penalti Eksterior.............. 44

xiv


DAFTAR TABEL

Halaman Tabel 3.3.1 Output penyelesaian contoh 3.3.2...................................................

50

Tabel 3.3.2 Output penyelesaian contoh 3.3.3...................................................

54

Tabel 3.3.3 Output penyelesaian contoh 3.3.4...................................................

55

xv


BAB I PENDAHULUAN

A. Latar Belakang Masalah Secara umum optimisasi merupakan tindakan untuk mendapatkan hasil yang terbaik terhadap situasi yang diberikan (sebagai suatu masalah). Sebagai contoh perusahaan sepatu yang ingin memberikan harga yang terbaik supaya perusahaan itu mendapatkan keuntungan yang terbanyak. Dalam berbagai macam situasi praktis tindakan tersebut dapat dibawa ke dalam perumusan matematika sebagai suatu fungsi dari variabel-variabel keputusan tertentu, sehingga optimisasi dapat didefinisikan sebagai proses mencari atau menemukan situasi yang memberikan nilai maksimum atau minimum dari suatu fungsi. Perhatikan gambar 1.1.1 di bawah ini :

f (x )

f (x ) x * pembuat minimum dari f ( x ) x*

0

x

x * pembuat maksimum dari − f ( x )

− f (x )

Gambar 1.1.1 Minimum f ( x ) sama dengan maksimum dari − f (x )

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 2

Dalam gambar 1.1.1 ( dalam hal ini sebagai contoh fungsi f ( x ) dengan satu variabel ) dapat dilihat bahwa jika suatu titik x * menunjukkan nilai pembuat minimum dari fungsi f ( x ) , titik yang sama itu juga menunjukkan nilai pembuat maksimum dari negatif fungsi tersebut yakni − f ( x ) . Berarti optimisasi dapat ditentukan dengan cara meminimalkan suatu fungsi karena maksimum dari fungsi tersebut dapat ditemukan dengan mencari minimum dari negatif dari fungsi yang sama. Secara matematis optimisasi merupakan proses menemukan nilai maksimum atau minimum dari suatu fungsi dengan cara meminimalkan fungsi tersebut. Secara umum masalah optimisasi dibagi menjadi dua bagian yakni, optimisasi berkendala dan optimisasi tidak berkendala. Optimisasi berkendala adalah optimisasi suatu fungsi yang disebut sebagai fungsi obyektif dengan kendala-kendala berupa pertidaksamaan atau persamaan, sedangkan optimisasi tidak berkendala adalah optimisasi suatu fungsi obyektif tanpa kendala. Pada optimisasi berkendala jika fungsi obyektif atau fungsi kendala adalah nonlinear maka masalah tersebut dinamakan masalah program nonlinear atau biasa disebut sebagai masalah optimisasi berkendala nonlinear. Ada beberapa teknik yang dapat digunakan untuk menyelesaikan suatu masalah program optimisasi berkendala nonlinear. Semua metode ini dapat diklasifikasikan ke dalam dua kategori yakni, metode langsung (direct method) dan metode tidak langsung (indirect method). Metode langsung meliputi metode Pencarian Heuristik, metode Pendekatan Kendala, dan metode Arah Layak.


Metode Arah Layak sendiri terbagi lagi menjadi dua metode yaitu metode Zoutendijk dan metode Proyeksi Gradien. Sedangkan metode tidak langsung meliputi Transformasi Variabel dan metode Fungsi Penalti, dimana metode Fungsi Penalti dibagi lagi menjadi dua metode yakni metode Fungsi Penalti Eksterior dan metode Fungsi Penalti Interior. Metode Fungsi Penalti merupakan salah satu metode numerik yang digunakan untuk mengubah masalah optimisasi dengan kendala menjadi masalah optimisasi tanpa kendala dengan menambahkan fungsi penalti dan parameter penalti pada fungsi obyektif. Dalam skripsi ini hanya membahas metode Fungsi Penalti Eksterior. Metode Fungsi Penalti Eksterior digunakan untuk menyelesaikan masalah optimisasi nonlinear berkendala, dimana pendekatan yang digunakan adalah dengan mengubah masalah optimisasi dengan kendala tersebut menjadi masalah optimisasi tanpa kendala yang ekuivalen. Pada metode Fungsi Penalti Eksterior, pencarian solusi optimal dimulai dari daerah tidak layak dan menghasilkan titik– titik tidak layak yang limitnya merupakan penyelesaian optimal dari masalah asli.

B. Perumusan Masalah Berdasarkan uraian yang dikemukakan dalam latar belakang, pokok permasalahan dalam skripsi ini dapat dirumuskan sebagai berikut : 1.

Apa itu metode Fungsi Penalti khususnya metode Fungsi Penalti Eksterior?

2.

Bagaimana bentuk umum dan algoritma metode Fungsi Penalti Eksterior?


3.

Bagaimana menyelesaikan masalah optimisasi nonlinear berkendala dengan metode Fungsi Penalti Eksterior dan implementasinya dengan program Matlab.

C. Batasan Masalah 1.

Dalam skripsi ini metode yang digunakan dalam menyelesaikan masalah tidak berkendala adalah metode Newton, akan tetapi dalam skripsi ini hanya membahas kegunaan dan algoritma metode Newton.

2.

Program yang digunakan untuk perhitungan numeris adalah program Matlab.

D. Tujuan Penulisan Penyusunan skripsi ini bertujuan untuk membahas metode Fungsi Penalti Eksterior dan bagaimana algoritma metode Fungsi Penalti Eksterior dalam menyelesaikan masalah optimisasi nonlinear berkendala serta konvergensi metode Fungsi Penalti Eksterior .

E. Manfaat Penulisan Manfaat yang diharapkan dalam skripsi ini adalah dapat mengetahui dan memahami bagaimana bentuk metode Fungsi Penalti khususnya metode Fungsi Penalti Eksterior dan mengetahui bagaimana metode Fungsi Penalti Eksterior digunakan untuk menyelesaikan masalah optimisasi nonlinear berkendala.


F. Metode Penulisan Dalam penulisan skripsi ini penulis menggunakan metode studi pustaka yakni, mempelajari referensi-referensi yang berkaitan dengan masalah optimisasi nonlinear, khususnya mengenai metode Fungsi Penalti Eksterior dan referensireferensi mengenai dasar teori pendukung.

G. Sistematika Penulisan Sistematika penulisan skripsi ini terdiri dari empat bab dengan urutan sebagai berikut : BAB I

:

PENDAHULUAN Dalam bab I akan dibahas tentang latar belakang, perumusan masalah, batasan masalah, tujuan penulisan, manfaat penulisan, metode penulisan, dan sistematika penulisan.

BAB II

:

TOPOLOGI DI R n DAN TEORI OPTIMISASI Dalam bab ini akan dibahas konsep ruang Euclid dan matriks, topologi di R n , fungsi kontinu dan fungsi terdiferensial, himpunan konveks dan fungsi konveks, syarat optimalitas untuk masalah berkendala, teori optimisasi serta metode Newton yang nantinya akan digunakan untuk memahami metode Fungsi Penalti Eksterior.


BAB III

:

METODE FUNGSI PENALTI EKSTERIOR Dalam bab III akan dibahas tentang konsep fungsi penalti, interpretasi geometris fungsi penalti, pengertian metode Fungsi Penalti Eksterior, bentuk umum Fungsi Penalti Eksterior dan algoritma metode Fungsi Penalti Eksterior disertai beberapa contoh masalah optimisasi nonlinear berkendala yang diselesaikan dengan metode Fungsi Penalti Eksterior. Terakhir dibicarakan juga implementasinya dengan program matlab serta konvergensi metode Fungsi Penalti Eksterior.

BAB IV

:

PENUTUP Bab IV berisi kesimpulan dan saran.


BAB II TOPOLOGI DI R n DAN TEORI OPTIMISASI

Dalam bab ini akan dibahas konsep ruang Euclid dan matriks, topologi di R n , fungsi kontinu dan fungsi terdiferensial, himpunan konveks dan fungsi

konveks, syarat optimalitas untuk masalah berkendala, teori optimisasi serta metode Newton yang nantinya akan digunakan untuk memahami metode Fungsi Penalti Eksterior.

A.

Ruang Euclid dan Matriks Berikut akan didefinisikan mengenai hasilkali dalam Euclidean, ruang

Euclid, transpose matriks, dan matriks semidefinit positif.

Definisi 2.1.1 Jika u = (u1 , u 2 , K , u n ) dan v = (v1 , v2 , K vn ) adalah vektor-vektor sebarang pada R n , maka hasilkali dalam Euclid (Euclidean inner product) u.v didefinisikan

sebagai

u.v = u1v1 + u 2 v2 + K + u n v n . Definisi 2.1.2 Ruang R n dengan operasi-operasi penjumlahan, perkalian skalar dan hasilkali dalam Euclidean disebut ruang Euclid berdimensi n (n-dimensional Euclidean space) atau Ruang Euclid yang diberi notasi Ε n .


Definisi 2.1.3 Jika A adalah matriks m × n , maka transpose dari A dinyatakan dengan A t , didefinisikan sebagai matriks n × m yang didapatkan dengan mempertukarkan baris-baris dan kolom-kolom dari A ; sehingga kolom pertama dari A t adalah baris pertama dari A , kolom kedua dari A t adalah baris kedua dari A , dan seterusnya.

Definisi 2.1.4 Jika A adalah matriks simetris n × n , maka A dikatakan semidefinit positif ( positive semidefinite ) jika x t Ax ≥ 0 untuk setiap x ∈ Ε n dan ditulis A ≥ 0 .

B.

Topologi di R n

Definisi 2.2.1

{

Diberikan titik x ∈ R n dan ε > 0, N ε (x ) = y ∈ R n : y − x < ε

}

disebut suatu

persekitaran − ε dari x .

Definisi 2.2.2 Misalkan K ⊂ R n dan x ∈ K . Titik x disebut titik dalam atau titik interior dari K jika terdapat suatu persekitaran − ε dari x yang termuat di dalam K , yaitu jika ada ε > 0 sedemikian sehingga y − x < ε berakibat y ∈ K . Himpunan


semua titik interior dari K disebut interior K dan dinotasikan dengan int K . Selanjutnya, K disebut terbuka jika K = int K .

Definisi 2.2.3 Misalkan K ⊂ R n , x disebut titik limit dari K jika untuk setiap ε > 0

K ∩ N ε (x ) ≠ φ . Himpunan semua

anggota K beserta titik limitnya disebut

closure dari K dan dinotasikan dengan Cl K . Selanjutnya, K disebut tertutup jika K = Cl K .

Definisi 2.2.4 Suatu barisan vektor x1, x 2 , x 3 , K dikatakan konvergen ke titik limit x jika

x k − x → 0 untuk k → ∞ , yaitu jika untuk sembarang ε > 0 terdapat bilangan bulat positif N sedemikian sehingga x k − x < ε untuk semua k ≥ N . Barisan biasanya dinotasikan dengan

{x k }

dan x titik limit

{x k }

disajikan dengan

x k → x untuk k → ∞ atau dengan lim k →∞ x k = x .

Catat bahwa barisan konvergen mempunyai titik limit yang tunggal.


Definisi 2.2.5 Dengan menghapus elemen-elemen tertentu dari barisan {x k }, diperoleh subbarisan, yang biasanya dinotasikan dengan {x k }κ , dengan κ adalah subset dari semua bilangan bulat positif.

Semesta pembicaraan sekarang adalah bilangan real Barisan bilangan real adalah suatu fungsi dari Ν ke dalam R . Jadi, fungsi f : Ν → R atau f (n ) dengan n ∈ Ν adalah barisan bilangan real. Biasanya

f (n) dinyatakan dengan sn . Barisan dengan sn sebagai suku ke-n akan ditulis sn atau {sn }.

Definisi 2.2.6 Misalkan f adalah fungsi yang terdefinisi di dalam himpunan bilangan real R ; f dikatakan mempunyai limit L di x0 , dan ditulis lim x→ x0 f ( x ) = L , jika

diberikan sebuah bilangan ε > 0 , maka ada sebuah δ > 0 sedemikian sehingga f ( x ) − L < ε bila x ∈ X dan 0 < x − x0 < δ .

Definisi 2.2.7 Barisan

{sn }

dikatakan konvergen jika terdapat s ∈ R dengan sifat, untuk

sebarang ε > 0 yang diberikan, terdapat

N ∈ Ν sehingga untuk semua

n ∈ Ν dengan n ≥ N berlaku s − s n < ε . Bilangan s dinamakan limit {sn } untuk


n → ∞ dan ditulis lim n→∞ sn atau disingkat lim sn = s . Suatu barisan yang tidak mempunyai limit disebut divergen.

Definisi 2.2.8 Barisan {sn } dikatakan naik jika sn ≤ sn+1 dan turun jika sn ≥ sn+1 untuk semua n ∈ Ν . Barisan naik dan barisan turun dinamakan barisan monoton.

Contoh 2.2.8 1. Barisan 1,1,2,2,3,3, K adalah barisan naik. 1 1 1 1 2. Barisan 1,1, , , , , K adalah barisan turun. 2 2 3 3

Ke dua contoh di atas adalah barisan monoton.

C.

Fungsi Kontinu dan Fungsi Terdiferensial

Definisi 2.3.1 l

Misalkan f : K → T , dimana K ⊂ R n dan T ⊂ R . Fungsi f dikatakan kontinu di x ∈ K jika untuk setiap ε > 0 , terdapat δ > 0 sedemikian sehingga untuk y ∈ K dan y − x < δ berlaku f (y ) − f (x ) < ε .

Selanjutnya fungsi f dikatakan kontinu pada K jika f kontinu di setiap titik anggota K .


Definisi 2.3.2 Diberikan fungsi f : K → R, K ⊂ R . Fungsi f dikatakan : 1. Naik pada K jika untuk setiap x1 , x2 ∈ K , dengan x1 < x2 , maka

f (x1 ) < f ( x2 ) . 2. Turun pada K jika untuk setiap x1 , x2 ∈ K , dengan x1 > x2 , maka

f ( x1 ) > f (x2 ) . 3. Monoton pada K jika f naik pada K atau turun pada K .

Definisi 2.3.3 Misal

f : R n → R . Turunan orde satu dari

f , dinotasikan dengan Df ,

didefinisikan sebagai berikut:

⎛ ∂f ∂f ∂f ⎞ ⎟ Df = ⎜⎜ , ,L, ∂xn ⎟⎠ ⎝ ∂x1 ∂x2

Definisi 2.3.4

Misal f : R n → R, gradien dari fungsi f di x ditulis ∇f (x ) , adalah transpose dari Df , yaitu :

∇f (x ) = (Df )

t

⎛ ∂f (x ) ∂f (x ) ∂f (x ) ⎞ ⎟⎟ , ,L, = ⎜⎜ x x x ∂ ∂ ∂ 2 n ⎠ ⎝ 1

t

⎛ ∂f (x ) ⎞ ⎟ ⎜ ⎜ ∂x1 ⎟ ⎜ ∂f (x ) ⎟ = ⎜ ∂x2 ⎟ ⎟ ⎜ ⎜ M ⎟ ⎜ ∂f (x ) ⎟ ⎜ ∂x ⎟ ⎝ n ⎠


13

Definisi 2.3.5 Misalkan K himpunan tidak kosong di E n , x ∈ int K dan f : K → E . Matriks

()

Hessian dari fungsi f pada x , yang biasa dinotasikan dengan H x adalah matriks yang elemen-elemennya terdiri dari turunan-turunan parsial ke dua dari fungsi f yaitu :

⎡ ⎤ ⎢ 2 ⎥ 2 2 ⎢ ∂ f (x ) ∂ f (x ) ∂ f (x ) ⎥ ⎢ ∂x12 ∂x1∂x2 ∂x1∂xn ⎥ ⎢ 2 ⎥ ∂ f (x ) ∂ 2 f (x ) ∂ 2 f (x ) ⎥ . Hx =⎢ 2 ⎢ ∂x2 ∂x1 ∂x2 ∂xn ⎥ ∂x2 ⎢M ⎥ M M ⎢ ⎥ ⎢ ∂ 2 f (x ) ∂ 2 f (x ) ∂ 2 f (x ) ⎥ ⎢ 2 ⎥ ∂xn ⎦ ⎣ ∂xn ∂x1 ∂xn ∂x2

()

Definisi 2.3.6 Misalkan K himpunan tidak kosong di E n , dan f : K → E terdiferensial dua kali. Teorema Taylor orde dua adalah : untuk setiap x1 , x 2 ∈ K haruslah memenuhi : f (x 2 ) = f (x1 ) + ∇f (x1 ) (x 2 −x 1 ) + t

dimana

()

Hx

()

1 (x 2 − x1 )t H x (x 2 − x1 ) 2

adalah matriks Hessian dari fungsi

x = λx1 + (1 − λ )x 2 untuk λ ∈ (0,1) .

f

pada

x

dan


14

Definisi 2.3.7 Misalkan K himpunan tidak kosong di Ε n , x ∈ int K dan f : K → Ε . Maka

()

∇f x yang disebut vektor

jika ada vektor

f dikatakan terdiferensial di x

gradien, dan ada fungsi α : E → E 1 sedemikian sehingga :

()

( )(

)

(

f (x ) = f x + ∇f x x − x + x − x α x ; x − x t

(

)

)

untuk setiap x ∈ K , dimana lim x→x α x ; x − x = 0 .

Fungsi

f

dikatakan terdiferensial pada himpunan terbuka

L⊆K

jika

f terdiferensial pada setiap titik L .

Definisi 2.3.8 Misalkan K himpunan tidak kosong di E n , x ∈ int K dan f : K → Ε . Maka

()

cdikatakan terdiferensial dua kali di x jika terdapat suatu vektor ∇f x , dan

()

matriks simetris n × n H x yang disebut sebagai matriks Hessian, dan suatu fungsi α : E → E 1 sedemikian sehingga :

()

( )(

) 12 (x − x) H(x)(x − x) + x − x α (x ; x − x)

f (x ) = f x + ∇f x x − x + t

2

t

(

)

untuk setiap x ∈ K , dimana lim x→x α x ; x − x = 0 .

Fungsi

f dikatakan terdiferensial dua kali pada himpunan terbuka L ⊆ K jika

f terdiferensial dua kali pada setiap titik L .


15

Contoh 2.3.8 Misalkan f ( x1 , x2 ) = 2 x1 + 6 x2 − 2 x12 − 3 x2 + 4 x1 x2 . Diketahui x = (0,0 ) . Maka t

2

⎡ 2 − 4 x1 + 4 x 2 ⎤ ⎡− 4 4 ⎤ ∇f x = ⎢ ⎥ dan H x = ⎢ ⎥. ⎣ 4 − 6⎦ ⎣ 6 − 6 x 2 + 4 x1 ⎦

()

()

Sehingga : ⎛x ⎞ 1 ⎡− 4 4 ⎤⎛ x1 ⎞ f ( x1 , x2 ) = (2,6)⎜⎜ 1 ⎟⎟ + (x1 , x2 )⎢ ⎥⎜⎜ ⎟⎟ . ⎣ 4 − 6⎦ ⎝ x 2 ⎠ ⎝ x2 ⎠ 2

D.

Himpunan Konveks dan Fungsi Konveks Berikut akan diberikan definisi dari himpunan konveks dan fungsi konveks

serta teorema-teorema yang berkaitan dengan fungsi konveks.

Definisi 2.4.1 Himpunan K di R n dikatakan konveks jika setiap garis penghubung antara kedua titik yang ada di himpunan berada juga pada himpunan tersebut. Dengan kata lain, jika x1 dan x 2 ada di K , maka λx1 + (1 − λ )x 2

harus ada di K untuk setiap

λ ∈ [0,1] .

Gambar 2.4.1 . Ilustrasi dari himpunan konveks dan tidak konveks


16

Contoh 2.4.1 Beberapa contoh himpunan konveks.

{

}

1. K = ( x1 , x2 ) : x1 + x2 ≤ 4 ⊂ R 2 2

2

Himpunan ini merepresentasikan titik yang berada di dalam lingkaran dengan pusat (0,0) dan radius 2 seperti pada gambar 2.4.2

x2 + y2 = 4

2

2

Gambar 2.4.2 Lingkaran x1 + x2 = 4

{

}

2. K = ( x, y ) : y ≥ x 2 ⊂ R 2 Himpunan ini mempresentasikan semua titik yang berada di atas kurva

y = x 2 seperti pada gambar 2.4.3

Gambar 2.4.3 Parabola y = x 2


17

Definisi 2.4.2 Misalkan f : K → R , dimana K adalah himpunan konveks tidak kosong di R . Fungsi f dikatakan konveks pada K jika

f (λx1 + (1 − λ )x 2 ) ≤ λf (x1 ) + (1 − λ ) f (x 2 ), untuk setiap x1, x 2 ∈ K dan 0 ≤ λ ≤ 1 . Contoh 2.4.2 Buktikan bahwa f ( x ) = e x , x ∈ R adalah fungsi konveks Penyelesaian : Ambil x1 , x 2 ∈ R maka f (x1 ) = e x1 dan f (x 2 ) = e x2 , dan

f (λx1 + (1 − λ )x 2 ) = e(λx1 +(1−λ ) x2 ) = e λx1 • e (1−λ )x2 .

Sedangkan,

λf (x1 ) + (1 − λ ) f (x 2 ) = λe x + (1 − λ )e x . 1

2

Jadi untuk setiap x1 , x 2 ∈ R dan 0 ≤ λ ≤ 1 diperoleh : f (λx1 + (1 − λ )x 2 ) ≤ λf (x1 ) + (1 − λ ) f (x 2 ) .

Maka terbukti f ( x ) = e x adalah fungsi konveks.


18

Teorema 2.4.3 Jika suatu fungsi f : K → R adalah konveks maka, untuk setiap dua titik x1 dan x 2 memenuhi

f (x 2 ) ≥ f (x1 ) + ∇f t (x1 )(x 2 − x1 ) Bukti : Misalkan f (x ) adalah konveks, maka berdasarkan definisi (2.4.2) f (λx 2 + (1 − λ )x1 ) ≤ λf (x 2 ) + (1 − λ ) f (x1 )

atau dapat ditulis sebagai : f (x1 + λ (x 2 − x1 )) ≤ f (x1 ) + λ ( f (x 2 ) − fx1 )

(2.4.1)

Pertidaksamaan (2.4.1) dapat dibentuk menjadi : f (x1 ) + λ ( f (x 2 ) − f (x1 )) ≥ f (x1 + λ (x 2 − x1 )) ⇔ λ ( f (x 2 ) − f (x1 )) ≥ f (x1 + λ (x 2 − x1 )) − f (x1 ) f (x 2 ) − f (x1 ) ≥

f (x1 + λ (x 2 − x1 )) − f (x1 )

λ

Pada ruas kanan penyebutnya dikalikan dengan x 2 − x1 sehingga menjadi : ⎧ f (x1 + λ (x 2 − x1 )) − f (x1 ) ⎫ f (x 2 ) − f (x1 ) ≥ ⎨ ⎬(x 2 − x1 ) λ (x 2 − x1 ) ⎩ ⎭ Karena definisi

, maka pertidaksamaan (2.4.2) menjadi :

(2.4.2)


19

⎧ f (x1 + Δx ) − f (x1 ) ⎫ f (x 2 ) − f (x1 ) ≥ ⎨ ⎬(x 2 − x1 ) Δx ⎩ ⎭

(2.4.3)

Dengan pengambilan limit untuk Δx → ∞ , sehingga pertidaksamaan (2.4.3) menjadi :

f (x 2 ) ≥ f (x1 ) + ∇f t (x1 )(x 2 − x1 )

Teorema 2.4.4 Suatu fungsi f : K → R adalah

()

konveks jika matriks Hessian H x

adalah

semidefinit positif.

Bukti : Dari Teorema Taylor bahwa :

(

)

( )

n

f x * + h = f x * + ∑ hi i =1

∂f * 1 n n ∂2 f x + ∑∑ hi h j x = x * + θh ∂xi 2! i =1 j =1 ∂xi ∂x j

( )

(2.4.4)

dimana 0 < θ < 1 . Misalkan x* = x1 , x * + h = x 2 , dan h = x 2 − x1 , sehingga pertidaksamaan (2.4.4) menjadi : f (x 2 ) = f (x1 ) + ∇f t (x1 )(x 2 − x1 ) +

1 (x 2 − x1 )t H{x1 + θ(x 2 − x1 )}(x 2 − x1 ) 2

(2.4.5)

Dapat dilihat bahwa untuk memenuhi Teorema 2.4.3 dan karena f (x ) konveks,

()

maka pertidaksamaan (2.4.5) harus memberikan H x semidefinit positif.


20

Contoh 2.4.3 Misalkan fungsi f : K → R 2 dan f ( x1 , x2 ) = 3 x1 + 4 x2 ∈ R 2 . Buktikan bahwa 2

2

f ( x1 , x2 ) = 3 x1 + 4 x2 adalah fungsi konveks untuk setiap nilai . 2

2

Penyelesaian :

()

Berdasarkan Teorema 2.4.4 maka cukup menunjukkan bahwa H x semidefinit positif, ⎡ ∂2 f ⎢ 2 ∂x H x = ⎢ 21 ⎢ ∂ f ⎢ ∂x ∂x ⎣ 2 1

()

∂2 f ⎤ ∂x1∂x2 ⎥⎥ ⎡6 0⎤ = = 48 > 0 ∂ 2 f ⎥ ⎢⎣0 8⎥⎦ 2 ∂x2 ⎥⎦

Jadi terbukti f ( x1 , x2 ) = 3 x1 + 4 x2 adalah fungsi konveks untuk setiap nilai x . 2

2

Definisi 2.4.5 Misalkan K adalah himpunan terbuka tidak kosong di E n , dan misalkan f : K → E terdiferensial pada K . Fungsi f dikatakan pseudokonveks jika

untuk setiap x1 , x 2 ∈ K dengan ∇f (x 1 ) (x 2 − x 1 ) ≥ 0 , maka f (x 2 ) ≥ f (x1 ) atau t

ekuivalen

dengan

pernyataan

bahwa

jika

f (x 2 ) < f (x1 ) ,

maka

∇f (x1 ) (x 2 − x1 ) < 0 . t

Definisi 2.4.6 Pseudokonveksitas di x adalah : fungsi f dikatakan pseudokonveks pada

()

x ∈ K jika ∇f (x1 ) (x 2 − x1 ) ≥ 0 untuk x ∈ K maka f (x ) > f x . t


21

E.

Syarat Optimalitas Masalah Tidak Berkendala Berikut akan didefinisikan syarat perlu dan syarat cukup tingkat pertama

sebagai syarat optimalitas untuk suatu masalah tidak berkendala.

Definisi 2.5.1 Perhatikan masalah meminimalkan f (x ) pada E n , dan misalkan x ∈ E n .

()

Jika f x ≤ f (x ) untuk semua x ∈ E n , maka x dinamakan suatu peminimum

a.

global. Jika ada suatu persekitaran − ε

b.

()

Nε x

sekitar x

sedemikian hingga

()

()

f x ≤ f (x ) untuk semua x ∈ N ε x , maka x dinamakan suatu peminimum

lokal.

()

jika untuk semua x ∈ N ε x , x ≠ x , untuk ε > 0 , maka x dinamakan

c.

suatu peminimum lokal tegas. Suatu peminimum global juga merupakan peminimum lokal.

Teorema 2.5.2 Misalkan bahwa

f : E n → E terdiferensial di x . Jika ada sebuah vektor

()

t

d ∈ E n sedemikian hingga ∇f x d < 0 maka terdapat δ > 0 sedemikian sehingga

(

) ()

f x + λd < f x untuk setiap λ ∈ (0, δ ) . Maka d merupakan suatu arah turun

(descent direction) dari f di x .


22

Bukti : Dari Definisi 2.3.7 maka diperoleh :

(

) ()

()

(

t

f x + λd = f x + λ∇f x + λ d α x; λd

(

)

(2.5.1)

)

dengan α x; λd → 0 untuk λ → 0 . Selanjutnya persamaan (2.5.1) dibagi dengan λ dimana λ ≠ 0 , diperoleh :

(

) ( ) = ∇f (x) + d α (x; λd)

f x + λd − f x

λ

t

()

(

t

)

Karena ∇f x d < 0 dan α x; λd → 0 untuk λ → 0 maka terdapat suatu δ > 0

()

(

)

sedemikian sehingga ∇f x + d α x; λd < 0 untuk setiap λ ∈ (0, δ ) . Sehingga t

(

) ()

terbukti f x + λd < f x .

Akibat 2.5.3 Misalkan bahwa f : E n → E terdiferensial di x . Jika x peminimum lokal fungsi

()

f maka ∇f x = 0 .

Bukti :

()

Dibuktikan dengan kontradiksi . Andaikan bahwa ∇f x ≠ 0 .

()

()

()

t

Misalkan d = −∇f x , didapatkan ∇f x d = ∇f x

(

2

< 0 . Dari Teorema 2.5.2,

) ()

terdapat suatu δ > 0 sedemikian sehingga f x + λd < f x untuk λ ∈ (0, δ ) . Hal ini kontradiksi dengan asumsi bahwa

x merupakan suatu peminimum lokal.

()

Karena itu pengandaian salah, dan haruslah ∇f x = 0 .


23

Syarat perlu di atas menggunakan vektor gradien yang komponen-komponennya merupakan turunan parsial pertama dari f , sehingga disebut sebagai syarat perlu tingkat pertama.

Teorema 2.5.4 Misalkan bahwa f : E n → E terdiferensial dua kali di x . Jika x adalah

()

()

peminimum lokal, maka ∇f x = 0 dan H x semidefinit positif. Teorema ini disebut sebagai Teorema syarat perlu tingkat kedua.

Bukti : Dari Definisi 2.3.8, maka diperoleh :

(

) ()

()

t

f x + λ d = f x + λ ∇f x d +

(

()

(

1 2 t 2 λ d H x d + λ2 d α x; λd 2

)

(2.5.2)

)

dimana α x; λd → 0 untuk λ → 0 . Karena x peminimum lokal, maka dari Akibat 2.5.3

bahwa

()

∇f x = 0 . Selanjutnya pertidaksamaan (2.5.2) dibagi

dengan λ2 > 0 menghasilkan :

(

) ( ) = 1 d H(x)d + d α (x; λd) λ 2

f x + λd − f x

2

t

(2.5.3)

2

(

) ()

Karena x peminimum lokal, f x + λd ≥ f x pertidaksamaan (2.5.3) jelas bahwa

()

untuk λ cukup besar. Maka pada

(

)

1 t 2 d H x d + d α x; λd ≥ 0 untuk λ cukup 2

()

besar. Dengan pengambilan limit untuk λ → 0 maka d t H x d ≥ 0 . Karena itu maka

adalah semidefinit positif.


24

Teorema 2.5.5 Misalkan f : E n → E merupakan pseudokonveks di x . Titik x merupakan suatu

()

peminimum global jika dan hanya jika ∇f x = 0 . Teorema ini adalah Teorema syarat cukup tingkat pertama.

Bukti : Misalkan x adalah suatu peminimum global.

()

Akan ditunjukkan bahwa ∇f x = 0 .

()

Berdasarkan Akibat 2.5.3 bahwa jika x adalah peminimum lokal, maka ∇f x = 0 dan oleh karena suatu peminimum lokal sama dengan peminimum global maka

()

terbukti bahwa ∇f x = 0 .

()

Misalkan bahwa ∇f x = 0 Akan ditunjukkan bahwa x merupakan suatu peminimum global. Karena

()

∇f x = 0

maka

( )( t

∇f x x − x

)

untuk

setiap

()

x ∈ En .

Dengan

pseudokonveksitas dari f di x maka diperoleh f (x ) ≥ f x untuk setiap x ∈ E n . Sehingga terbukti x merupakan suatu peminimum global.


25

F.

Teori Optimisasi Secara umum masalah optimisasi dibagi menjadi dua bagian yakni,

optimisasi berkendala dan optimisasi tidak berkendala : 1. Bentuk umum masalah optimisasi berkendala Minimalkan

f (x )

dengan kendala

g i (x ) ≤ 0, i = 1,2, L , m

(2.6.1)

h j (x ) = 0, j = 1,2, L , l

dengan :

x

= Vektor di E n

f (x ) = Fungsi obyektif

g i (x ) = Kendala berupa pertidaksamaan sebanyak m h j (x ) = Kendala berupa persamaan sebanyak l

2. Bentuk umum masalah optimisasi tidak berkendala Minimalkan

f (x )

Jika fungsi obyektif atau fungsi kendala dalam persamaan (2.6.1) adalah nonlinear maka masalah tersebut dinamakan masalah program nonlinear atau biasa disebut sebagai masalah optimisasi nonlinear berkendala.


26

Definisi 2.6.1 Bentuk umum masalah optimisasi nonlinear berkendala adalah : Minimalkan

f (x )

dengan kendala

g i (x ) ≤ 0, untuk i = 1,2, L , m h j (x ) = 0, untuk j = 1,2, L , l

Dengan f , g1 , K , g m , h1 K , hl adalah fungsi-fungsi kontinu pada E n , X adalah subhimpunan dari E n dan x ∈ E n .

Definisi 2.6.2 Suatu vektor x ∈ X disebut penyelesaian layak masalah optimisasi nonlinear berkendala jika memenuhi semua kendala.

Definisi 2.6.3 Himpunan dari semua penyelesaian layak disebut daerah layak.

Definisi 2.6.4 Titik layak adalah titik yang menjadi anggota daerah layak.

Definisi 2.6.5

()

Titik layak x disebut penyelesaian optimal jika f (x ) ≥ f x untuk setiap titik layak x .


27

G.

Metode Newton Metode Newton merupakan salah satu metode yang paling terkenal dan

sering digunakan dalam menyelesaikan suatu sistem persamaan nonlinear. Metode ini merupakan perkembangan dari metode Newton-Raphson dan metode TitikTetap yang digunakan untuk menyelesaikan persamaan nonlinear. Syarat dalam menyelesaikan sistem persamaan nonlinear dengan metode Newton adalah sebagai berikut : a. Sistem persamaan nonlinear yang dimaksud adalah sistem persamaan nonlinear yang terdiri dari n persamaan dan n variabel. b. Semua fungsi yang terlibat dalam sistem persamaan nonlinear harus terdiferensial.

Metode Newton adalah suatu algoritma iterasi fungsional yang

(

membangkitkan x (k ) = x (k −1) − J x (k −1)

) F(x ( ) ) −1

k −1

dengan k ≥ 1 dan J(x ) adalah

matriks Jacobi dari sistem persamaan nonlinear. Metode Newton memiliki konvergensi yang bersifat q-kuadratik dengan relasi kesalahan e (k +1) ≤ e (k ) Metode Newton sangat populer karena bentuk iterasinya yang sederhana. Metode Newton dapat juga digunakan untuk menyelesaikan masalah optimisasi nonlinear tidak berkendala karena syarat dari optimisasi nonlinear adalah gradien dari fungsi obyektifnya sama dengan nol yang berarti bahwa, ada n turunan dari setiap n variabel dari fungsi obyektifnya sama dengan nol yang merupakan sistem persamaan nonlinear. Misalkan ada masalah optimisasi nonlinear tidak berkendala yakni :


28

Minimalkan f ( x1 , x2 , K , xn ) Selesaikan masalah optimisasi ini dengan menggunakan metode Newton. Penyelesaian : Dengan menggunakan syarat perlu bahwa, jika fungsi f fungsi terdiferensial maka syarat perlu tingkat pertama adalah ∇f (x ) = 0 . Sehingga dengan mencari gradien dari

f ( x1 , x2 ,K, xn )

menghasilkan :

∂f =0 ∂x1 ∂f =0 ∂x 2 M ∂f =0 ∂xn

(2.7.1)

Kumpulan semua persamaan yang ada di (2.7.1) berbentuk sistem persamaan nonlinear. Kemudian setelah membentuk sistem persamaan nonlinear maka masalah optimisasi tersebut dapat diselesaikan dengan metode Newton.


29

Diagram alir dari algoritma Metode Newton dalam menyelesaikan sistem persamaan nonlinear.

start

Nilai awal (x) Tol.error (error) Iterasi maksimum (N) k=1

while k<=N

fx=fungsi(x) jx=jacobian(x)

y=-inv(jx)*fx

if norm(y)
ya

x

tidak x=x+y' k=k+1

Gambar 2.7.1 Diagram alir algoritma metode newton

end


BAB III METODE FUNGSI PENALTI EKSTERIOR

Dalam bab ini akan dibahas mengenai metode Fungsi Penalti Eksterior dalam menyelesaikan masalah optimisasi nonlinear berkendala. Tetapi dalam pembahasan ini penulis akan menjelaskan terlebih dahulu tentang konsep fungsi penalti dan interpretasi geometris fungsi penalti. Kemudian dilanjutkan mengenai bentuk umum Fungsi Penalti Eksterior dan algoritma Metode Fungsi Penalti Eksterior serta contoh masalah yang diselesaikan dengan metode Fungsi Penalti Eksterior dan diimplementasikan dengan bahasa pemrograman Matlab. Dan yang terakhir adalah konvergensi metode Fungsi Penalti Eksterior.

A.

Konsep Fungsi Penalti Salah satu cara untuk mengubah masalah optimisasi dengan kendala

menjadi masalah optimisasi tanpa kendala adalah dengan menambahkan fungsi penalti pada fungsi obyektif yang pada beberapa metode, bergantung pada nilai kendala-kendalanya. Dalam kehidupan sehari-hari kita mengenal istilah penalti terjadi karena adanya pelanggaran. Demikian juga dalam masalah optimisasi ini fungsi penalti terjadi karena ada pelanggaran terhadap fungsi obyektif, yaitu dengan menghilangkan kendala pada permasalahan itu. Fungsi penalti dapat juga dipandang sebagai fungsi yang ditambahkan pada fungsi obyektif dengan parameter penalti.


Metode dengan menggunakan fungsi penalti mentransformasikan masalah dengan kendala ke dalam masalah tanpa kendala tunggal atau ke dalam barisan masalah tanpa kendala. Kendala-kendala dibentuk ke dalam fungsi obyektif melalui parameter penalti sedemikian hingga menghilangkan setiap hambatanhambatan dari kendala tersebut. Untuk membangun fungsi penalti perhatikan masalah-masalah dibawah ini.

Contoh 3.1.1 Perhatikan masalah dengan kendala tunggal h(x ) = 0 , yaitu : Minimalkan

f (x )

Dengan kendala

h(x ) = 0 .

Misalkan masalah tersebut diubah menjadi masalah tanpa kendala : Minimalkan Dengan

f (x ) + μh 2 (x ) x∈ En

μ > 0 suatu bilangan besar . Secara intuitif dapat dilihat bahwa penyelesaian optimal dari masalah tersebut haruslah h 2 (x ) mendekati nol, karena jika tidak

μh 2 (x ) akan terjadi.

maka suatu penalti besar


Contoh 3.1.2 Perhatikan masalah dengan kendala pertidaksamaan tunggal g (x ) ≤ 0 yakni : f (x )

Minimalkan

g (x ) ≤ 0 .

Dengan kendala

Andaikan masalah di atas diubah menjadi masalah tanpa kendala seperti berikut : Minimalkan Dengan

f (x ) + μg 2 (x ) x∈ En

μ > 0 suatu bilangan besar. Maka dapat dilihat bahwa dengan bentuk f (x ) + μg 2 (x ) mengakibatkan terjadinya penalti baik untuk g (x ) < 0 atau g (x ) > 0 . Dalam masalah di atas suatu penalti akan terjadi hanya jika titik x adalah tidak layak, yaitu g (x ) > 0 . Dengan demikian pengandaian di atas salah dan masalah tanpa kendala yang sesuai adalah Minimalkan

f (x ) + μ maks {0, g (x )}

Dengan

x∈ En

μ > 0 suatu bilangan besar. Jika g (x ) ≤ 0 , maka maksimum {0, g (x )} = 0 , dan tidak ada penalti yang terjadi, dan jika g (x ) > 0 , maka maksimum {0, g (x )} > 0 , dan bentuk penalti μg (x ) terjadi.

Secara umum, fungsi penalti yang sesuai harus memiliki suatu penalti positif untuk titik-titik tidak layak dan tidak ada penalti untuk titik layak. Jika


kendala-kendala tersebut dalam bentuk g i (x ) ≤ 0 untuk i = 1,K, m dan hi (x ) = 0 untuk i = 1,K, l maka fungsi penalti α yang sesuai diberikan oleh : m

l

i =1

i =1

α(x ) = ∑ Φ[g i (x )] + ∑ Ψ [hi (x )]

(3.1.1)

dengan Φ dan Ψ adalah fungsi-fungsi kontinu yang memenuhi : Φ ( y ) = 0 jika y ≤ 0 dan Φ ( y ) > 0 jika y > 0 Ψ ( y ) = 0 jika y = 0 dan Ψ ( y ) > 0 jika y ≠ 0

(3.1.2)

Secara khusus, Φ dan Ψ berbentuk : Φ ( y ) = [ maks {0, y} ]

Ψ( y ) = y

p

p

dengan p adalah bilangan bulat positif. Jadi fungsi penalti α yang biasa digunakan berbentuk p

m

l

α(x ) = ∑ [ maks { 0, g i (x ) } ] + ∑ hi (x ) i =1

p

i =1

Fungsi f (x ) + μα(x ) dinamakan fungsi tambahan.

Contoh 3.1.3

Selesaikan masalah optimisasi berikut : Minimalkan

x

Dengan kendala

−x+2≤0.

Misalkan α( x ) = [ maks { 0, g i ( x ) } ] , maka : 2

jika x ≥ 2 ⎧0 α( x ) = ⎨ . 2 ⎩(− x + 2) jika x < 2


34

Penyelesaian :

Misalkan masalah tersebut diubah menjadi masalah tanpa kendala : Minimalkan

x + μ (− x + 2 )

Dengan

x∈E

2

(3.1.3)

μ > 0 suatu bilangan besar. Selanjutnya penyelesaian optimal persamaan (3.1.3) dapat dicari dengan cara mencari turunannya. Titik optimal akan dicapai ketika turunannya sama dengan nol. Maka persamaan (3.1.3) setelah dicari turunannya menjadi: 1 + 2μ (− x + 2 )(− 1) ⇔ 2μ (− x + 2 )(− 1) = −1

⇔ 2μ ( x − 2 ) = −1

⇔ x−2=

−1 2μ

⇔ x = 2−

1 2μ

Nilai optimal x dapat dicari dengan cara mencari limitnya untuk μ yang mendekati ∞ , yaitu

⎛ 1 ⎞ lim ⎜⎜ 2 − ⎟⎟ = 2 . μ →∞ 2μ ⎠ ⎝ Selanjutnya penyelesaian masalah (3.1.3) dapat ditunjukkan dengan grafik di bawah ini :


35

μ 2α

μ 1 = 0 .5

α

μ 2 = 1 .5

μ 1α

Gambar 3.1.1 Grafik Penalti f + μ 2α

f + μ 1α

Gambar 3.1.2 Grafik Fungsi Tambahan

Contoh 3.1.4

Selesaikan masalah optimisasi berikut: 2

2

Minimalkan

x1 + x2

Dengan kendala

x1 + x2 − 1 = 0 .


36

Penyelesaian :

Perhatikan masalah penalti berikut, dengan μ > 0 suatu bilangan besar x1 + x2 + μ ( x1 + x2 − 1) 2

Minimalkan

2

2

(x1 , x2 )∈ E 2 .

Dengan kendala

Perhatikan bahwa untuk sembarang μ ≥ 0 , fungsi obyektif konveks. Jadi syarat perlu

dan

cukup

untuk

optimalitas

adalah

gradien

dari

x1 + x2 + μ ( x1 + x2 − 1) sama dengan nol yang menghasilkan : 2

2

2

x1 + μ ( x1 + x2 − 1) = 0 ⇔ x1 + μx1 + μx2 − μ = 0

(3.1.4)

dan x2 + μ ( x1 + x2 )

(3.1.5) Persamaan (3.1.4) dan (3.1.5) diselesaikan dengan menggunakan metode Gauss Jordan menjadi :

μ μ⎤ ⎡1 + μ ⎢ μ 1 + μ μ⎥ ⎣ ⎦

μ ⎡ ⎢1 1 + μ ⎢ ⎢0 1 ⎢⎣

1 B1 1+ μ

μ ⎤ 1+ μ ⎥ ⎥ μ ⎥ 1 + 2μ ⎥⎦

B1 −

μ ⎡ ⎢1 1 + μ ⎢ ⎣μ 1 + μ μ B2 1+ μ

μ ⎤ 1+ μ ⎥ ⎥ μ ⎦

B2 −μB1

μ ⎡ ⎢1 1 + μ ⎢ ⎢0 1 + 2μ 1+ μ ⎣⎢

μ ⎤ ⎡ ⎢1 0 1 + 2μ ⎥ ⎢ ⎥ μ ⎥ ⎢0 1 ⎢⎣ 1 + 2μ ⎥⎦

Ditulis ke dalam bentuk persamaan menjadi :

1+μ

μ ⎤ 1+ 2μ 1+ μ ⎥ ⎥ μ ⎥ 1 + μ ⎦⎥

B2


37

x1 =

μ 1 + 2μ

x2 =

μ 1 + 2μ

Jadi diperoleh : x1 = x2 =

μ . 1 + 2μ

Selanjutnya nilai dari x1 dan x2 dapat dicari dengan cara mencari nilai limitnya untuk μ → ∞ , yaitu μ lim 1 + 2μ μ →∞

sehingga diperoleh x1 = x2 =

1 . 2

Jadi penyelesaian optimal dari masalah penalti dapat dibuat sedekat-dekatnya dengan penyelesaian dari masalah asli dengan menentukan μ cukup besar.

B.

Interpretasi Geometris Fungsi Penalti

Untuk menggambarkan fungsi penalti secara geometri, digunakan contoh 3.1.4. Misalkan bahwa kendala

h(x ) = 0 dipertubasi sedemikian sehingga

h(x ) = ε yaitu x1 + x2 − 1 = ε . Misalkan v(ε ) merupakan fungsi objektif maka akan

diperoleh masalah berikut : v(ε ) ≡ Minimalkan

Dengan kendala

2

x1 + x2

2

x1 + x2 − 1 = ε


38

x1 + x2 − 1 = ε , dapat diganti menjadi

Perhatikan kendala

x2 = 1 + ε − x1 .

Selanjutnya subsitusikan x 2 ke dalam fungsi obyektif sehingga menjadi : x1 + (1 + ε − x1 ) 2

2

(3.2.1)

Nilai optimal akan dicapai ketika turunannya sama dengan nol, maka fungsi pada (3.2.1) setelah dicari turunannya dapat ditulis sebagai : 2 x1 + 2(1 + ε − x1 )(− 1) = 0 ⇔ 2 x1 − 2(1 + ε − x1 ) = 0 ⇔ 2 x1 − 2 − 2ε + 2 x1 = 0 4 x1 − 2 − 2ε = 0 .

Masing-masing ruas dibagi dengan 2 menjadi : 2 x1 − 1 − ε = 0 ⇔ 2 x1 = 1 + ε

⇔ x1 =

1+ ε . 2

Subsitusikan x1 ke dalam persamaan kendala sehingga menjadi : 1+ ε + x2 − 1 = ε 2 ⎛1+ ε ⎞ ⇔ x2 = 1 + ε − ⎜ ⎟ ⎝ 2 ⎠

⇔ x2 = ⇔x 2 =

2 + 2ε − 1 − ε 2

1+ ε . 2

Jadi diperoleh nilai optimal yaitu :


39

x1 = x2 =

1+ ε 2

dan mempunyai nilai obyektif :

(1 + ε )2 . 2

Oleh karena itu, untuk sembarang ε yang diberikan, supremum dari x1 + x2 2

2

dengan kendala x1 + x2 − 1 = ε sama dengan ∞ . Oleh karena itu, jika diberikan sembarang titik (x1 , x2 ) di E 2 dengan x1 + x2 − 1 = ε , nilai obyektifnya berada

⎡ (1 + ε )2 ⎤ , ∞ ⎥ . Dengan kata lain, nilai obyektif dari semua x di E 2 pada interval ⎢ ⎣ 2 ⎦ yang memenuhi h( x ) = ε , terletak diantara

E2

Pemetaan (h, f

)

x

(1 + ε )2 2

dan ∞ .

f (x )

Titik layak untuk masalah primal

[h(x ). f (x )] Batas bawah terbesar parabola v(ε )

Penyelesaian optimal untuk masalah penalti dengan parameter

Penyelesaian optimal untuk masalah primal

μ' > μ

h(x ) = ε

Penyelesaian optimal untuk masalah penalti dengan parameter μ

[h(x ). f (x )] μ

μ

εμ f + μh 2 f + μ 'h 2

Gambar 3.2.1 Geometri fungsi penalti pada ruang (h,f)


40

{[h(x), f (x)]: x ∈ E } 2

Secara khusus, himpunan 3.2.1

Batas

bawah

(1 + h )2 = (1 + ε )2 2

2

meminimalkan

dari

himpunan

ini

ditunjukkan pada gambar

dinyatakan

oleh

parabola

≡ v(ε ) . Untuk suatu nilai tertentu μ > 0 , masalah penalti adalah

f (x ) + μh 2 (x )

dengan

x∈ E2 .

Kontur

dari

f + μh 2 = k diilustrasikan dalam ruang (h, f ) yang ditunjukkan dalam gambar 3.2.1 dengan parabola putus-putus. Irisan dari parabola tersebut dengan sumbu

f sama dengan k . Jadi jika f + μh 2 diminimalkan, maka parabola tersebut harus digeser mengarah ke bawah sebanyak mungkin, sedemikian sehingga parabola tersebut masih mempunyai sekurang-kurangnya satu titik yang sama dengan himpunan yang diarsir. Proses ini dilanjutkan sampai parabola tersebut menyinggung himpunan yang diarsir, seperti ditunjukkan pada gambar 3.2.1. Hal ini berarti bahwa untuk nilai

μ yang diberikan, nilai optimum dari masalah

penalti merupakan perpotongan parabola pada sumbu f . Perhatikan bahwa penyelesaian optimal masalah penalti sedikit tidak layak dari masalah asli, karena

h ≠ 0 di titik singgung. Selanjutnya, nilai obyektif optimal dari masalah penalti adalah sedikit lebih kecil dari nilai obyektif optimal primal. Dan perhatikan juga bahwa jika nilai μ bertambah, parabola f + μh 2 menjadi makin curam, dan titik singgung mendekati penyelesaian optimal sebenarnya dari masalah asli.


41

C.

Metode Fungsi Penalti Eksterior

Metode Fungsi Penalti Eksterior adalah metode yang digunakan untuk menyelesaikan masalah optimisasi nonlinear berkendala menjadi masalah tidak berkendala dengan menambahkan fungsi penalti dan parameter penalti pada fungsi obyektifnya. Proses pencarian penyelesaian optimal dimulai dari luar daerah layak, oleh karena itu disebut metode Fungsi Penalti Eksterior. Kendalakendala akan ditambahkan pada fungsi obyektif dengan parameter penalti.

1.

Bentuk Umum Fungsi Penalti Eksterior

Fungsi Penalti Eksterior merupakan bentuk fungsi tambahan yakni, fungsi obyektif ditambah fungsi penalti. Misalkan fungsi

merupakan fungsi tambahan,

dan f (x ) merupakan fungsi obyektif, maka dengan mengambil : p

m

l

α(x ) = ∑ [ maks {0, g i (x )} ] + ∑ hi (x ) i =1

p

i =1

didapatkan fungsi tambahan m

p

l

z = f (x ) + μ k ∑ [ maks {0, g i (x )} ] + μ k ∑ hi (x ) i =1

p

i =1

yang disebut sebagai Fungsi Penalti Eksterior. Jadi bentuk umum masalah Fungsi Penalti Eksterior adalah : Minimalkan m

p

l

p

z = f (x ) + μ k ∑ [ maks {0, g i (x )} ] + μ k ∑ hi (x ) . i =1

i =1


42

Contoh 3.3.1

Ubalah masalah berikut menjadi masalah Fungsi Penalti Eksterior :

f ( x1 , x2 ) =

Minimalkan

1 (x1 + 1)3 + x2 3

(3.3.1)

1 − x1 ≤ 0

Dengan kendala

− x2 ≤ 0 .

Penyelesaian :

Pertama

akan

dibentuk

fungsi

penalti

dari

masalah

(3.3.1)

yaitu

α(x ) = [maks (0, 1 − x1 )] + [maks (0, − x 2 )] 2

2

kemudian di bentuk fungsi z = f (x ) + μ k α(x ) , menjadi

z=

1 (x1 + 1)3 + x2 + μ k [maks (0, 1 − x1 )]2 + μ k [maks (0, − x2 )]2 3

Maka masalah (3.3.1) dapat dibentuk menjadi masalah Fungsi Penalti Eksterior yakni Minimalkan z =

1 (x1 + 1)3 + x2 + μ k [maks (0, 1 − x1 )]2 + μ k [maks (0, − x2 )]2 . 3


43

2.

Algoritma Metode Fungsi Penalti Eksterior

Berikut akan diberikan algoritma dari metode Fungsi Penalti Eksterior untuk menyelesaikan masalah Minimalkan

f (x )

Dengan kendala

g(x ) ≤ 0 h (x ) = 0

x∈ X

dan

1. Tentukan titik awal x1 , parameter penalti μ 1 > 0 , skalar penalti β > 1 ,

ε > 0 dan k = 1 . 2. Bentuk fungsi obyektif untuk masalah optimisasi tidak berkendala

z = f (x ) + μ k α(x ) , dengan m

p

l

α(x ) = ∑ [ maks {0, g i (x )} ] + ∑ hi (x ) i =1

p

i =1

3. Tentukan penyelesaian dari masalah minimalkan z , yakni x* k . 4. Jika μ k α(x ) < ε langkah dihentikan dan diperoleh x* k . Jika tidak,

lanjutkan ke langkah 2 dengan μ k +1 = βμ k .

Perhatikan langkah 3, bahwa ketika masalah optimisasi nonlinear berkendala setelah diubah menjadi masalah optimisasi nonlinear tidak berkendala dengan metode Fungsi Penalti Eksterior maka penyelesaian dari masalah minimalkan z , yakni x* k dapat diselesaikan dengan metode Newton.


44

Diagram alir dari algoritma metode Fungsi Penalti Eksterior dalam menyelesaikan masalah optimisasi nonlinear berkendala

Mulai

Tentukan titik awal x1 ,

ε > 0 parameter penalti μ 1 > 0 , skalar β > 1 dan k = 1

Bentuk fungsi z = f (x ) + μ k α(x ) dengan p

m

l

α(x ) = ∑ [ maks {0, g i (x )} ] + ∑ hi (x ) i =1

p

i =1

Tentukan penyelesaian dari masalah minimalkan z yakni x * k

μ k α(x ) < ε

YA

Selesai

TIDAK

μ k +1 = βμ k

Gambar 3.3.1 Diagram alir algoritma metode Fungsi Penalti Eksterior


45

Dalam menyelesaikan masalah optimisasi nonlinear berkendala dengan metode Fungsi Penalti Eksterior ditemukan dua kasus yakni, kasus umum dan kasus khusus. Kasus umum adalah masalah yang dalam penyelesaiannya memerlukan titik awal, sedangkan kasus khusus adalah masalah yang dalam penyelesaiannya tidak memerlukan titik awal. Berikut ini akan diberikan beberapa contoh kasus umum dan kasus khusus masalah optimisasi nonlinear berkendala yang diselesaikan dengan metode Fungsi Penalti Eksterior.

Contoh 3.3.2

Selesaikan masalah berikut : Minimalkan

f ( x1 , x2 ) =

Dengan kendala

1 − x1 ≤ 0

1 (x1 + 1)3 + x2 3

(3.3.3)

− x2 ≤ 0

(3.3.4)

Penyelesaian : ITERASI 1 Langkah 1

Menentukan μ 1 = 0.001 , skalar β = 10 , ε = 0.00001 dan k = 1 . Langkah 2

Bentuk fungsi z = f (x ) + 0.001 α(x ) dimana α(x ) = [maks (0, 1 − x1 )] + [maks (0, − x2 )] . 2

(3.3.2)

2


46

Langkah 3

Menentukan penyelesaian dari masalah Minimalkan

z=

1 (x1 + 1)3 + x2 + μ k [maks (0, 1 − x1 )]2 + μ k [maks (0, − x2 )]2 3

(3.3.5)

Penyelesaian dimulai dari mencari turunan parsial terhadap x1 dan x 2 yaitu : ∂z 2 = ( x1 + 1) − 2 μ k [maks (0, 1 − x1 )] ∂x1

(3.3.6)

dan ∂z = 1 − 2μ k [maks (0, − x2 )] ∂x2

(3.3.7)

Perhatikan persamaan (3.3.6) : ∂z 2 = ( x1 + 1) ∂x1

i.)

Jika maks (0, 1 − x1 ) = 0 maka

ii.)

Jika maks (0, 1 − x1 ) = 1 − x1 maka

∂z 2 = ( x1 + 1) − 2μ k (1 − x1 ) ∂x1

Sehingga persamaan (3.3.6) dapat ditulis sebagai :

[

]

min ( x1 + 1) , ( x1 + 1) − 2μ k (1 − x1 ) 2

2

(3.3.8)

Jika min = 0 , maka didapatkan ( x1 + 1) = 0 , sehingga diperoleh x1 = −1 . Kondisi 2

ini tidak mungkin karena tidak memenuhi kendala pada persamaan (3.3.4). Selanjutnya jika min = ( x1 + 1) − 2μ k (1 − x1 ) , maka 2

(x1 + 1)2 − 2μ k (1 − x1 ) 2

⇔ x1 + 2 x1 + 1 − 2μ k + 2μ k x1 = 0


47

⇔ x1 + x1 (2 + 2μ k ) − 2μ k + 1 = 0 2

⎛ 4 ⇔ x1 = −1 − μ k + μ k ⎜⎜1 + ⎝ μk

1

⎞2 ⎟⎟ . ⎠

⎛ 4 Jadi x * 1 = −1 − μ k + μ k ⎜⎜1 + ⎝ μk

1

⎞2 ⎟⎟ ⎠

(3.3.9)

Dari persamaan (3.3.7) : i). Jika maks (0, − x2 ) = 0 maka

∂z =1 ∂x2

ii). Jika maks (0, − x2 ) = − x2 maka

∂z = 1 + 2μ k x2 ∂x2

Sehingga persamaan (3.3.7) dapat ditulis sebagai :

min [1, (1 + 2μ k x2 )]

(3.3.10)

persamaan (3.3.10) hanya mempunyai satu kemungkinan yaitu : 1 + 2μ k x2 = 0 , maka x2 =

Jad x * 2 =

−1 . 2μ k

−1 2μ k

(3.3.11)

Langkah 4

Berdasarkan persamaan (3.3.9), (3.3.11), (3.3.5) dan (3.3.2) diperoleh :

x*1 = −0.93775 x * 2 = −500

z = −249.99616 f = −500


48

( )

Karena μ 1α x*1 > ε maka tetapkan μ 2 = βμ 1 = 0.01 dan lanjutkan ke iterasi berikutnya.

ITERASI 2 Langkah 2

Bentuk fungsi z dengan μ 2 = βμ 1 , yakni z = f (x ) + 0.01 α(x ) . Langkah 3

Menentukan penyelesaian dari masalah meminimalkan z seperti pada langkah 3, iterasi pertama. Langkah 4


x *1 = −0.80975 x * 2 = −50

z = −24.96495 f = −49.99770

( )

μ 2 α x* 2 = 25.03275 .

( )

Karena μ 2 α x* 2 berikutnya.

maka tetapkan μ 3 = βμ 2 = 0.1 dan lanjutkan ke iterasi


49

ITERASI 3 Langkah 2

Bentuk fungsi z dengan μ 3 = βμ 2 , yaitu z = f (x ) + 0.1 α(x ) Langkah 3



x *1 = −0.45969 x * 2 = −5

z = −2.23435 f = −4.94742

Karena μ 3 α(x *3 ) = 2.71307 maka tetapkan μ 4 = βμ 3 = 1 dan lanjutkan ke iterasi berikutnya.

Dan seterusnya dilakukan iterasi sampai pada μ k α (x * k ) < ε , maka iterasi dihentikan dan penyelesaian optimal diperoleh. Berikut akan diberikan tabel penyelesaian contoh 3.3.2 dengan program Matlab :


50

Tabel 3.3.1 Output penyelesaian contoh 3.3.2 dengan Matlab ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 0.001 -0.93775 -500.00000 -499.99992 -249.99616 250000.00375 2 0.010 -0.80975 -50.00000 -49.99770 -24.96495 2500.03275 3 0.100 -0.45969 -5.00000 -4.94742 -2.23435 25.21307 4 1.000 0.23607 -0.50000 0.12951 0.96311 0.83359 5 10.000 0.83216 -0.05000 2.00007 2.30677 0.28420 6 100.000 0.98039 -0.00500 2.58399 2.62495 0.03848 7 1000.000 0.99800 -0.00050 2.65819 2.66242 0.00398 8 10000.000 0.99980 -0.00005 2.66582 2.66624 0.00040 9 100000.000 0.99998 -0.00001 2.66658 2.66662 0.00004 10 1000000.000 1.00000 -0.00000 2.66666 2.66666 0.00000

Jadi penyelesaian optimal masalah 3.3.2 adalah x1 = 1 dan x2 = 0 , yang menyebabkan nilai f minimum pada 2.66666 .

Contoh 3.3.3


f ( x1 , x 2 ) = x1 + x 2 − 4 x1 − 4 x 2 + 8

(3.3.12)

Dengan kendala

x1 + 2 x2 − 4 = 0

(3.3.13)

2

2

Penyelesaian : ITERASI 1 Langkah 1

Menentukan μ 1 = 0.001 , skalar β = 10 , ε = 0.00001 dan k = 1 . Langkah 2

Bentuk fungsi z = f (x ) + 0.001 α(x ) dimana α(x ) = ( x1 + 2 x2 − 4 ) . 2


51

Langkah 3

Menentukan penyelesaian dari masalah Minimalkan z = x1 + x2 − 4 x1 − 4 x2 + 8 + μ k ( x1 + 2 x2 − 4) 2

2

2

(3.3.14)

Penyelesaian dimulai dari mencari turunan parsial terhadap x1 dan x 2 yaitu : ∂z = 2 x1 − 4 + 2μ k ( x1 + 2 x2 − 4 ) ∂x1

(3.3.15)

∂z = 2 x2 − 4 + 4μ k (x1 + 2 x 2 −4 ) . ∂x2

(3.3.16)

dan

Persamaan (3.3.15) dan persamaan

(3.3.16) dapat ditulis ke dalam bentuk :

(2 + 2μ k )x1 + 4μ k x2 − 8μ k − 4 = 0

(3.3.17)

4μ k x1 + (2 + 8μ k )x2 − 16μ k − 4 = 0

(3.3.18)

dan

Sehingga persamaan (3.3.17) dan (3.3.18) diselesaikan dengan metode Gauss Jordan menjadi :

⎡2 + 2μ k ⎢ 4μ k ⎣ ⎡ ⎢1 ⎢ ⎢0 ⎢⎣

4μ k 2 + 8μ k

4μ k 2 + 2μ k 20μ k + 4 2 + 2μ k

⎡ ⎢1 0 ⎢ ⎢0 1 ⎢⎣

32μ k 20μ k 24μ k 20μ k

8μ k + 4 ⎤ 16μ k + 4⎥⎦

1 2+ 2μ k

2+ 2μ k

8μ k + 4 ⎤ 20μ k + 4 2 + 2μ k ⎥ ⎥ 24μ k + 8 ⎥ 2 + 2μ k ⎥⎦ +8⎤ + 4⎥ ⎥ +8⎥ + 4 ⎥⎦

B2

⎡ ⎢ 1 ⎢ ⎣4μ k

⎡ ⎢1 ⎢ ⎢0 ⎢⎣

4μ k 2 + 2μ k 2 + 8μ k

4μ k 2 + 2μ k 1

8μ k + 4 ⎤ 2 + 2μ k ⎥ ⎥ 16μ k +4 ⎦

8μ k + 4 ⎤ 2 + 2μ k ⎥ ⎥ 24μ k + 8 ⎥ 20μ k + 4 ⎥⎦

B2 −

B2 − 4 μ k B1

4μ k 2+ 2μ k


52

Ditulis ke dalam persamaan menjadi : x1 =

32μ k + 8 20μ k + 4

x2 =

24μ k + 8 20μ k + 4

Maka : x *1 =

32μ k + 8 20μ k + 4

x*2 =

24μ k + 8 20μ k + 4

Langkah 4


x *1 = 1.99801 x * 2 = 1.99602

z = 0.00398 f = 0.00002

( )

μ 1 α x*1 = 0.00396 Karena

( )

μ 1 α x *1 > ε maka tetapkan μ 2 = βμ 1 = 0.01 dan lanjutkan ke iterasi

berikutnya.

ITERASI 2 Langkah 2

Bentuk fungsi z dengan μ 2 = βμ 1 , yakni z = f (x ) + 0.01 α(x )


53

Langkah 3



x *1 = 1.98095 x * 2 = 1.96190

z = 0.03810 f = 0.00181

( )

μ 2 α x* 2 = 0.00396 .

( )

Karena μ 2 α x *3

maka tetapkan μ 3 = βμ 2 = 0.1 dan lanjutkan ke iterasi

berikutnya.

ITERASI 3 Langkah 2

Bentuk fungsi z dengan μ 3 = βμ 2 , yaitu z = f (x ) + 0.1 α(x ) Langkah 3



x*1 = 1.86667


54

x * 2 = 1.73333

z = 0.26667 f = 0.08889 μ 3 α (x * 3 ) = 0.17778

Karena μ 3 α (x * 3 ) > ε

maka tetapkan μ 4 = βμ 3 = 1 dan lanjutkan ke iterasi

berikutnya.

Dan seterusnya dilakukan iterasi sampai pada μ k α (x * k ) < ε , maka iterasi dihentikan dan penyelesaian optimal diperoleh. Berikut akan diberikan tabel penyelesaian contoh 3.3.3 dengan menggunakan program Matlab :

Tabel 3.3.2 Output penyelesaian contoh 3.3.3 dengan Matlab ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 0.001 1.99801 1.99602 0.00002 0.00398 0.00396 2 0.010 1.98095 1.96190 0.00181 0.03810 0.03628 3 0.100 1.86667 1.73333 0.08889 0.26667 0.17778 4 1.000 1.66667 1.33333 0.55556 0.66667 0.11111 5 10.000 1.60784 1.21569 0.76894 0.78431 0.01538 6 100.000 1.60080 1.20160 0.79681 0.79840 0.00159 7 1000.000 1.60008 1.20016 0.79968 0.79984 0.00016 8 10000.000 1.60001 1.20002 0.79997 0.79998 0.00002 9 100000.000 1.60000 1.20000 0.80000 0.80000 0.00000

Maka penyelesaian optimal masalah 3.3.3 adalah x1 = 1.6 dan x2 = 1.2 , yang menyebabkan nilai f minimum pada 0.8 .


55

Contoh 3.3.4


f ( x1 , x2 ) = x1 + x2

Dengan kendala

2 x1 + x2 − 2 ≤ 0

2

2

− x2 + 1 = 0

Penyelesaian :

Tahap awal adalah menentukan titik awal yakni x1 = (2,6) , μ 1 = 1 , β = 10 ,

ε = 10 −8 dan k = 1 . Kemudian dilanjutkan dengan membentuk masalah berkendala dari contoh 3.3.4 menjadi masalah tidak berkendala dengan menggunakan metode Fungsi Penalti Eksterior yakni,

(

)

z = x1 + x2 + μ k [maks (0, (2 x1 + x2 − 2))] + μ k (− x2 + 1) . 2

2

2

2

Tahap selanjutnya adalah mencari penyelesaian dari masalah minimalkan z , yakni x* k dengan menggunakan metode Newton. Penyelesaian dari contoh 3.3.4 dengan menggunakan program Matlab dapat diperlihatkan sebagai berikut :

Tabel 3.3.3 Output penyelesaian contoh 3.3.4 dengan Matlab ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 1 2.000000 6.000000 40.000000 129.000000 89.000000 2 10 0.545455 0.636364 0.702479 2.024793 1.322314 3 100 0.390456 0.926839 1.011486 1.546741 0.535255 4 1000 0.357049 0.991867 1.111283 1.177436 0.066153 5 10000 0.353305 0.999177 1.123180 1.129946 0.006765 6 100000 0.352926 0.999918 1.124392 1.125070 0.000678 7 1000000 0.352888 0.999992 1.124514 1.124582 0.000068 8 10000000 0.352885 0.999999 1.124526 1.124533 0.000007 9 100000000 0.352884 1.000000 1.124527 1.124528 0.000001 10 1000000000 0.352884 1.000000 1.124527 1.124527 0.000000 ======================================================================


56

Maka penyelesaian optimal masalah 3.3.4 adalah x1 = 0.352884 dan x2 = 1 , yang membuat nilai f minimum pada 1.124527 .

Masalah optimisasi pada contoh 3.3.4 adalah kasus umum yakni yang memerlukan titik awal. Dalam tabel penyelesaiannya dapat dilihat bahwa metode Fungsi penalti Eksterior konvergen ke penyelesaian yang sebenarnya. Akan tetapi dalam kasus umum masalah optimisasi yang diselesaikan dengan metode Fungsi Penalti Eksterior tidak selalu mudah menentukan nilai awal μ , apabila nilai awal μ dipilih sangat besar maka akan mengakibatkan penyelesaian tidak optimal.

Sebagai perbandingannya akan diberikan contoh nilai awal μ yang sangat besar yang tidak menghasilkan penyelesaian yang optimal yakni μ 1 = 100000 . Hasil penyelesaian dengan Metode Fungsi penalti Eksterior : ====================================================================== Iterasi Nilai mu

x1

x2

f

z

mua

====================================================================== 1

100000

2.000000

6.000000 40.000000

8900040.000000

8900000.000000

2

1000000

0.500002

0.999993

1.249988

1.250044

0.000056

3

10000000

0.499999

0.999999

1.249997

1.250003

0.000006

4

100000000

0.499999

1.000000

1.249998

1.249999

0.000001

5

1000000000

0.499999

1.000000

1.249999

1 .249999

0.000000

Dari tabel di atas dapat dilihat bahwa dengan suatu nilai awal μ yang sangat besar proses optimisasi dapat terhenti pada waktu yang seharusnya belum terhenti, karena sekalipun penyelesaiannya konvergen tetapi titik layak yang dihasilkan bukanlah titik optimal, sehingga penyelesaiannya bukanlah penyelesaian optimal.


57

Metode Fungsi Penalti Eksterior memiliki kelebihan dan kekurangan. Kelebihan dari metode Fungsi Penalti Eksterior adalah masalah optimisasi berkendala menjadi mudah diselesaikan karena metode Fungsi Penalti Eksterior mengubah masalah optimisasi berkendala tersebut menjadi masalah optimisasi tidak berkendala. Sedangkan kekurangan dari metode Fungsi Penalti Eksterior adalah pada kasus umum masalah optimisasi nonlinear yakni masalah yang memerlukan titik awal, dalam pemilihan

yang sangat besar akan mengakibatkan

kesulitan perhitungan artinya bahwa proses optimisasi dapat terhenti pada waktu yang seharusnya belum berhenti. Dengan suatu nilai

yang sangat besar pada

umumnya prosedur optimisasi tidak berkendala akan bergerak cepat menuju titik layak sekalipun titik ini mungkin jauh dari titik optimal.

D.

Konvergensi Metode Fungsi Penalti Eksterior

Untuk membuktikan konvergensi dari algoritma metode Fungsi Penalti Eksterior, terlebih dahulu dibentuk fungsi tambahan sama yakni : m

z = φ (x, μ k ) = f (x ) + μ k ∑ [ maks { 0, g i (x ) }]

p

i =1

= f (x ) + μ k G[g(x )] dengan p bilangan bulat positif dan μ k parameter penalti.


58

Lemma 3.4.1

Jika φ (x, μ k ) = f (x ) + μ k G[g(x )]

(3.4.1)

Maka relasi-relasi berikut akan benar untuk setiap 0 < μ k < μ k +1 : (i)

φ (x * k , μ k ) ≤ φ (x * k +1 , μ k +1 )

(ii)

G g x* k ≥ G g x* k +1

(iii)

f x* k ≤ f x* k +1

(iv)

f x* ≥ φ x* k , μ ≥ f x* k .

[ ( )] [ (

)]

( ) (

)

( ) (

) ( )

Bukti :

(i) Karena μ k ≤ μ k +1 dan G[g (x )] ≥ 0 maka

[(

)]

[(

μ k G g x * k +1 ≤ μ k +1G g x * k +1

)]

Sehingga

[

]

[

]

f (x * k +1 ) + μ k G g (x * k +1 ) ≤ f (x * k +1 ) + μ k +1G g (x * k +1 )

(

= φ x * k +1, μ k +1

)

Selanjutnya, karena x* k meminimalkan φ (x, μ k ) , maka :

φ (x * k , μ k ) = f (x * k ) + μ k G [g (x * k )] ≤ f (x * k +1 ) + μ k G [g (x * k +1 )] ≤ φ (x * k +1, μ k +1 )

(3.4.2)

Jadi terbukti bahwa φ (x * k , μ k ) ≤ φ (x * k +1 , μ k +1 ) . (ii) Karena x* k dan x* k +1 masing-masing meminimalkan φ (x, μ k ) dan φ (x, μ k +1 ) maka dapat ditulis :


59

[ ( )] (

( )

[(

)

)]

f x * k + μ k G g x * k ≤ f x * k +1 + μ k G g x * k +1

[

]

[

(3.4.3)

]

f (x k +1 ) + μ k +1G g (x * k +1 ) ≤ f (x * k ) + μ k +1G g (x * k )

(3.4.4)

Dengan menjumlahkan persamaan (3.4.3) dan (3.4.4) akan diperoleh :

[ ( )]

[(

)]

[(

)]

[ ( )]

μ k G g x * k + μ k +1G g x * k +1 ≤ μ k G g x * k +1 + μ k +1G g x * k

[

]

[

]

[

]

[

] [

[

]

⇔ μ k G g (x * k ) − μ k G g (x * k +1 ) ≤μ k +1 G g (x * k ) − μ k +1G g (x * k +1 )

[

] [

]

]

⇔ μ k {G g (x * k ) − G g (x * k +1 ) }≤ μ k +1 {G g (x * k ) − G g (x * k +1 ) }

(3.4.5)

Tetapi karena μ k ≤ μ k +1 , maka pertidaksamaan (3.4.5) akan berlaku jika :

[ ( )] [ (

)]

[ ( )] [ (

)]

G g x * k − G g x* k +1 ≥ 0 atau G g x* k ≥ G g x* k +1 .

[ ( )] [ (

)]

Jadi terbukti bahwa G g x* k ≥ G g x* k +1 . (iii) Dari pertidaksamaan (3.4.2) diperoleh :

[

] [

]

f (x * k ) − f (x * k +1 ) ≤ μ k {G g (x * k +1 ) − G g (x * k ) }

[(

)] [ ( )]

Karena G g x* k +1 ≤ G g x* k

( ) (

(3.4.6)

dan μ k > 0 , maka pertidaksamaan (3.4.6)

)

memberikan f x* k ≤ f x* k +1 . (iv) Karena x* k meminimalkan φ (x, μ k ) , maka :

[

]

f (x * ) + μ k G g (x * ) ≥ φ (x * k , μ k )

Sedangkan

(3.4.7)

φ (x * k , μ k ) = f (x * k ) + μ k G [g (x * k )]maka pertidaksamaan (3.4.7)

dapat dibentuk menjadi :

[

]

[

]

f (x * ) + μ k G g (x * k ) ≥ f (x * k ) + μ k G g (x * k )

Karena x * adalah minimum untuk masalah optimisasi berkendala, maka

[ ( )]

G g x* = 0 . Sehingga :


60

[ ( )]

( ) ( )

f x* ≥ f x*k + μ k G g x*k

[ ( )]

Karena G g x* k ≥ 0 dan μ k ≥ 0 mengakibatkan :

( ) (

) ( )

f x* ≥ φ x*k , μ k ≥ f x*k .

Teorema 3.4.2

Jika barisan naik dari nilai-nilai μ k meminimalkan fungsi φ (x, μ k ) yang diberikan pada persamaan (3.4.1), maka x* k , yakni pembuat minimum fungsi obyektif pada masalah berkendala akan konvergen ke penyelesaian optimal

(x ) *

masalah

berkendala untuk μ k → ∞ . Bukti :

Misalkan x * penyelesaian optimal masalah berkendala, maka akan ditunjukkan bahwa : lim { min φ (x, μ k )} = φ (x * k ) = f (x* )

μ k →∞

( )

Karena f (x ) kontinu dan f x* ≤ f (x ) untuk setiap titik layak x , maka dapat dipilih titik layak x sedemikian sehingga :

() ( )

f x < f x* +

ε 2

,

(3.4.8)

untuk sembarang nilai ε > 0 . Selanjutnya, pilih k yang sesuai yang disebut k + 1 , sedemikian sehingga :

⎧ ε ⎪ μk < ⎨ 2 ⎪G g x ⎩

⎫ ⎪ ⎬. ⎪ ⎭

[ ( )]

(3.4.9)


61

Dari Lemma 3.4.1 bagian (iv) diketahui bahwa

( ) (

) ( )

f x* k ≤ φ x*k , μ k ≤ f x* ,

(3.4.10)

sedangkan berdasarkan Lemma 3.4.1 bagian (i) diperoleh

φ (x * k , μ k ) ≤ φ (x * k +1 , μ k +1 ) .

(3.4.11)

Tetapi karena x* k +1 meminimalkan φ (x, μ k +1 ) maka :

(

φ (x* k , μ k ) ≤ φ x, μ k +1

)

(3.4.12)

Sehingga dengan mengkombinasikan pertidaksamaan (3.4.10), (3.4.11) dan (3.4.12) diperoleh

) (

( ) (

)

f x* k ≤ φ x* k , μ k ≤ φ x, μ k +1

(3.4.13)

Karena

(

[ ( )]

) ()

φ x, μ k +1 = f x + μ k +1G g x

maka pertidaksamaan (3.4.13) menjadi

[ ( )]

) ()

( ) (

f x* k ≤ φ x* k , μ k ≤ f x + μ k +1G g x Pertidaksamaan (3.4.9) memberikan

[ ( )]

μ k +1G g x <

ε

(3.4.15)

2

Berdasarkan pertidaksamaan (3.4.8) dan (3.4.15) maka pertidaksamaan (3.4.14) menjadi :

( ) (

) ( )

f x* k ≤ φ x* k , μ k < f x* +

ε 2

+

ε 2

( )

= f x* + ε

atau

φ (x * k , μ k ) − f (x * ) < ε .

(3.4.16)


62

Untuk setiap ε > 0 dapat dipilih suatu nilai k untuk memenuhi pertidaksamaan (3.4.16) sedemikian sehingga untuk k → ∞(μ k → ∞ ) , diperoleh : lim φ (x* k , μ k ) = f (x* ).

μ k →∞

Dari Teorema 3.4.2 di atas, dinyatakan bahwa penyelesaian optimal x * dari masalah

berkendala dapat dibuat sedekat-dekatnya dengan daerah layak

{ }

dengan memilih μ cukup besar. Titik-titik optimal x* umumnya tidak layak. Tetapi sebagaimana ditunjukan oleh bukti Teorema 3.4.2, jika parameter penalti μ dibuat besar, titik-titik tersebut akan mendekati penyelesaian optimal dari arah

luar daerah layak.


BAB IV PENUTUP

A. Kesimpulan Berdasarkan uraian dari bab-bab sebelumnya, maka dapat disimpulkan beberapa hal berikut ini : Metode

fungsi

penalti

adalah

metode

yang

digunakan

untuk

mentransformasikan masalah optimisasi nonlinear berkendala menjadi masalah tidak berkendala. Metode fungsi penalti sendiri terdiri atas dua metode yaitu metode fungsi penalti eksterior dan interior. Bentuk umum dari masalah fungsi penalti eksterior adalah : Minimalkan z = f (x ) + μ k α(x ) dengan m

p

l

α(x ) = ∑ [ maks {0, g i (x )}] + ∑ hi (x ) i =1

p

i =1

μ k merupakan parameter penalti, g i (x ) dan hi (x ) adalah fungsi-fungsi kendala. Titik optimal tercapai bila nilai fungsi z konvergen ke fungsi f (x ) dengan μ k mendekati tak hingga dan α(x ) mendekati nol. Proses pencarian penyelesaian optimal dengan metode fungsi penalti eksterior dimulai dari daerah tidak layak. Untuk meminimalkan fungsi

dalam penulisan ini digunakan metode Newton.

Dalam menyelesaikan masalah optimisasi nonlinear berkendala dengan metode Fungsi Penalti Eksterior ditemukan dua kasus yakni, kasus umum dan kasus khusus. Kasus umum adalah masalah yang dalam penyelesaiannya


memerlukan titik awal, sedangkan kasus khusus adalah masalah yang dalam penyelesaiannya tidak memerlukan titik awal. Metode Fungsi Penalti Eksterior memiliki kelebihan dan kekurangan. Kelebihan dari metode Fungsi Penalti Eksterior adalah masalah optimisasi berkendala menjadi mudah diselesaikan karena metode Fungsi Penalti Eksterior mengubah masalah optimisasi berkendala tersebut menjadi masalah optimisasi tidak berkendala. Sedangkan kekurangan dari metode Fungsi Penalti Eksterior adalah pada kasus umum masalah optimisasi nonlinear yakni masalah yang memerlukan titik awal, dalam pemilihan

yang sangat besar akan mengakibatkan

kesulitan perhitungan artinya bahwa proses optimisasi dapat terhenti pada waktu yang seharusnya belum berhenti. Dengan suatu nilai

yang sangat besar pada

umumnya prosedur optimisasi tidak berkendala akan bergerak cepat menuju titik layak sekalipun titik ini mungkin jauh dari titik optimal.

B.

Saran Metode newton bukan satu-satunya metode yang dapat digunakan dalam

menyelesaikan masalah meminimalkan z , tetapi masih ada metode-metode tidak berkendala lainnya seperti metode Turun-tercuram, metode Davidon dan beberapa metode lainnya. Metode Fungsi Penalti tidak hanya metode Fungsi Penalti Eksterior akan tetapi masih ada metode Fungsi Penalti Interior yang dapat digunakan untuk menyelesaikan masalah optimisasi nonlinear berkendala.


DAFTAR PUSTAKA

Anggi, M. N. (2007). Penyelesaian Sistem Persamaan Non-linear dengan Metode Newton dan Terapannya. Skripsi. Yogyakarta : FST USD.

Anton, H and Rorres, C (2004). Aljabar Linear Elementer, Versi Aplikasi (Terjemahan). Edisi kedelapan-jilid 1. Jakarta : Penerbit Erlangga.

Bazaraa M, Sherali H, Shetty C. (1993). Nonlinear Programming, theory and algorithms, second edition, New York : John Wiley & Sons, Inc.

Chong, P. E, and Zak, H. Stanislaw. (1996). An Introduction to Optimization. New York : John Wiley & Sons, Inc.

Luenberger, D (1989). Linear and Nonlinear Programing, second edition, Canada : Addison-Wesley Publishing.

Linfield, G, and Penny, J. (2000). Numerical Methods Using Matlab. Upper Saddle River: Prentice Hall.

Purcell, J, E and Varberg D. Kalkulus dan Geometri Analitik. (Terjemahan). Jilid 1. Jakarta : Penerbit Erlangga.

Rao S S. (1984). Optimization Theory and Applications, second edition. India : Wiley Eastern Limited.

Soemantri, R, dkk. (2006). Diktat Pengantar Analisis Real. Yogyakarta : FMIPA USD.

Sundaram, K. R (1996). A First Course in Optimization Theory. New York : Cambridge University Press.


LAMPIRAN 1

Program Menu Utama : function utama pilih=0; while pilih~=4 fprintf('\n\n\n\n'); disp('Program Penyelesaian Masalah Optimisasi Nonlinear Berkendala Dengan Metode Fungsi Penalti Eksterior'); disp('oleh Maria Martini Leto Kurniawan (013114019)'); disp('sebagai syarat memperoleh gelar S.Si'); fprintf('\n\n\n\n'); disp('------------------------------------------------------------------------------------------------------'); disp(' Menu Utama'); disp(' Penyelesaian Masalah Optimisasi Nonlinear Berkendala Dengan Metode Fungsi Penalti Eksterior'); disp('-------------------------------------------------------------------------------------------------------'); disp(' 1. Masalah Optimisasi Nonlinear Dengan Kendala Pertidaksamaan'); disp(' 2. Masalah Optimisasi Nonlinear Dengan Kendala Persamaan'); disp(' 3. Masalah Optimisasi Nonlinear Dengan Kendala Pertidaksamaan dan Persamaan'); disp(' 4. Keluar'); fprintf('\n\n'); pilih=input('Masukkan menu pilihan anda='); switch pilih case 1 contoh; case 2 contoh2; case 3 gabung ; case 4 disp('Keluar'); otherwise disp('Masukkan anda salah'); end end disp('Terimakasih anda telah menggunakan program ini.');

Output Program Penyelesaian Masalah Optimisasi Nonlinear Berkendala Dengan Metode Fungsi Penalti Eksterior oleh Maria Martini Leto Kurniawan (013114019) sebagai syarat memperoleh gelar S.Si

----------------------------------------------------------------------------------------------------------Menu Utama Penyelesaian Masalah Optimisasi Nonlinear Berkendala Dengan Metode Fungsi Penalti Eksterior ----------------------------------------------------------------------------------------------------------1. Masalah Optimisasi Nonlinear Dengan Kendala Pertidaksamaan 2. Masalah Optimisasi Nonlinear Dengan Kendala Persamaan


3. Masalah Optimisasi Nonlinear Dengan Kendala Pertidaksamaan dan Persamaan 4. Keluar

Masukkan menu pilihan anda=

LAMPIRAN 2 PROGRAM UNTUK MASALAH DENGAN KENDALA PERTIDAKSAMAAN

Listing program : function contoh clear; clc; mu=input('Masukkan nilai parameter penalti :'); err=input('Masukkan nilai toleransi :'); b=input('Masukkan nilai beta : '); n=input('Masukkan iterasi maksimum : '); k=1; clc; fprintf('Program untuk meminimumkan f=(1/3*(x1+1)^3)+x2\n'); fprintf('Dengan kendala 1-x1<=0 dan -x2=0\n'); fprintf('==============================================================\n'); fprintf(' Iterasi Nilai mu x1 x2 f z mua\n'); fprintf('==============================================================\n'); while k<=n x3=-1-mu+mu*(sqrt(1+(4/mu))); x4=(-1/(2*mu)); x1=x3; x2=x4; z=(1/3*(x1+1)^3)+x2+mu*(max(0,(1-x1)))^2+mu*(max(0,(-x2)))^2; f=(1/3*(x1+1)^3)+x2; mua=mu*((max(0,(1-x1))))^2+(max(0,(-x2)))^2; fprintf(' %3d if mua < err break end k=k+1; mu=b*mu; end

%.3f

%8.5f

%8.5f

%8.5f

%8.5f %8.5f\n',k,mu,x1,x2,f,z,mua);

fprintf('==============================================================\n'); fprintf(' Pada saat iterasi ke - %d, mua < %5.5f.\n',k,err); fprintf(' Jadi nilai x yang meminimalkan z adalah : x1 = %7.5f dan x2 = %7.5f.\n',x1,x2); end


Output >> contoh Masukkan nilai parameter penalti :0.001 Masukkan nilai toleransi :0.00001 Masukkan nilai beta : 10 Masukkan iterasi maksimum : 15

Tampilan hasil : Program untuk meminimumkan f=(1/3*(x1+1)^3)+x2 Dengan kendala 1-x1<=0 dan -x2=0 ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 0.001 -0.93775 -500.00000 -499.99992 -249.99616 250000.00375 2 0.010 -0.80975 -50.00000 -49.99770 -24.96495 2500.03275 3 0.100 -0.45969 -5.00000 -4.94742 -2.23435 25.21307 4 1.000 0.23607 -0.50000 0.12951 0.96311 0.83359 5 10.000 0.83216 -0.05000 2.00007 2.30677 0.28420 6 100.000 0.98039 -0.00500 2.58399 2.62495 0.03848 7 1000.000 0.99800 -0.00050 2.65819 2.66242 0.00398 8 10000.000 0.99980 -0.00005 2.66582 2.66624 0.00040 9 100000.000 0.99998 -0.00001 2.66658 2.66662 0.00004 10 1000000.000 1.00000 -0.00000 2.66666 2.66666 0.00000 ====================================================================== Pada saat iterasi ke - 10, mua < 0.00001. Jadi nilai x yang meminimalkan z adalah : x1 = 1.00000 dan x2 = -0.000000

LAMPIRAN 3 PROGRAM DENGAN KENDALA PERSAMAAN Listing Program : function contoh2 clear; clc; mu=input('Masukkan nilai parameter penalti :'); err=input('Masukkan nilai toleransi :'); b=input('Masukkan nilai beta : '); n=input('Masukkan iterasi maksimum : '); k=1; clc; fprintf('Program untuk meminimumkan f=x1.^2+x2.^2-4*x1-4*x2+8\n'); fprintf('Dengan kendala x1+2*x2-4=0\n'); fprintf('============================================================= \n'); fprintf(' Iterasi Nilai mu x1 x2 f z mua\n'); fprintf('==============================================================\n');


while k<=n x3=(32*mu+8)/(20*mu+4); x4=(24*mu+8)/(20*mu+4); x1=x3; x2=x4; z=x1.^2+x2.^2-4*x1-4*x2+8+mu*((x1+2*x2-4).^2); f=x1.^2+x2.^2-4*x1-4*x2+8; mua=mu*((x1+2*x2-4).^2); fprintf(' %3d if mua < err break end k=k+1; mu=b*mu; end

%.3f

%8.5f

%8.5f %8.5f %8.5f

%8.5f\n',k,mu,x1,x2,f,z,mua);

fprintf('============================================================= \n'); fprintf(' Pada saat iterasi ke - %d, mua < %5.5f.\n',k,err); fprintf(' Jadi nilai x yang meminimalkan z adalah : x1 = %7.5f dan x2 = %7.5f.\n',x1,x2); end

Output >> contoh2 Masukkan nilai parameter penalti :0.001 Masukkan nilai toleransi :0.00001 Masukkan nilai beta : 10 Masukkan iterasi maksimum : 15

Tampilan hasil : Program untuk meminimumkan f=x1.^2+x2.^2-4*x1-4*x2+8 Dengan kendala x1+2*x2-4=0 ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 0.001 1.99801 1.99602 0.00002 0.00398 0.00396 2 0.010 1.98095 1.96190 0.00181 0.03810 0.03628 3 0.100 1.86667 1.73333 0.08889 0.26667 0.17778 4 1.000 1.66667 1.33333 0.55556 0.66667 0.11111 5 10.000 1.60784 1.21569 0.76894 0.78431 0.01538 6 100.000 1.60080 1.20160 0.79681 0.79840 0.00159 7 1000.000 1.60008 1.20016 0.79968 0.79984 0.00016 8 10000.000 1.60001 1.20002 0.79997 0.79998 0.00002 9 100000.000 1.60000 1.20000 0.80000 0.80000 0.00000 ====================================================================== Pada saat iterasi ke - 9, mua < 0.00001. Jadi nilai x yang meminimalkan z adalah : x1 = 1.60000 dan x2 = 1.20000


LAMPIRAN 4 PROGRAM UNTUK KENDALA PERTIDAKSAMAAN DAN PERSAMAAN Listing Program : function gabung clear; clc; fprintf('Metode Eksterior dan Metode Newton\n\n'); fprintf('Masukkan data yang dibutuhkan\n\n'); x=input('x0 = '); mu=input('Masukkan nilai parameter penalti :'); tol=input('Masukkan nilai toleransi :'); b=input('Masukkan nilai beta : '); N=input('Max.iterasi = '); k=1; fprintf('Program untuk meminimumkan f=x1.^2+x2.^2\n'); fprintf('Dengan kendala 2*x1+x2-2<=0 dan -x2+1=0\n'); fprintf('==============================================================\n'); fprintf(' Iterasi Nilai mu x1 x2 f z mua\n'); fprintf('==============================================================\n'); while k <= N x1=x(1);x2=x(2); f1=2*x1+4*mu*(max(0,(2*x1+x2-2))); f2=2*x2-2*mu*(-x2+1)+2*mu*(max(0,(2*x1+x2-2))); fx=[f1;f2]; j11=2+8*mu; j12=4*mu; j21=4*mu; j22=2+4*mu; jx=[j11 j12;j21 j22]; %j(ik)=turunan fungsi ke-i terhadap variabel ke-k y=-inv(jx)*fx; f=x1.^2+x2.^2; z=(x1.^2+x2.^2)+mu*(-x2+1).^2+mu*(max(0,(2*x1+x2-2))).^2; mua=mu*(-x2+1).^2+mu*(max(0,(2*x1+x2-2))).^2; fprintf(' %4.0d %11.0d %12f %12f %12f %12f %12f\n',k,mu,x,f,z,mua); if mua

end fprintf('==============================================================\n'); fprintf(' Pada saat iterasi ke - %4.0d, mua < %8.8f.\n',k,tol); fprintf(' Jadi nilai x yang meminimalkan z adalah : x1 = %12f dan x2 = %12f\n',x1,x2); end

Output >> gabung Metode Eksterior dan Metode Newton Masukkan data yang dibutuhkan x0 = [2 6] Masukkan nilai parameter penalti :1 Masukkan nilai toleransi :0.00000001 Masukkan nilai beta : 10 Max.iterasi = 100 Tampilan Hasil Program untuk meminimumkan f=x1.^2+x2.^2 Dengan kendala 2*x1+x2-2<=0 dan -x2+1=0 ====================================================================== Iterasi Nilai mu x1 x2 f z mua ====================================================================== 1 1 2.000000 6.000000 40.000000 129.000000 89.000000 2 10 0.545455 0.636364 0.702479 2.024793 1.322314 3 100 0.390456 0.926839 1.011486 1.546741 0.535255 4 1000 0.357049 0.991867 1.111283 1.177436 0.066153 5 10000 0.353305 0.999177 1.123180 1.129946 0.006765 6 100000 0.352926 0.999918 1.124392 1.125070 0.000678 7 1000000 0.352888 0.999992 1.124514 1.124582 0.000068 8 10000000 0.352885 0.999999 1.124526 1.124533 0.000007 9 100000000 0.352884 1.000000 1.124527 1.124528 0.000001 10 1000000000 0.352884 1.000000 1.124527 1.124527 0.000000 ====================================================================== Pada saat iterasi ke - 10, mua < 0.00000001. Jadi nilai x yang meminimalkan z adalah : x1 = 0.352884 dan x2 = 1.000000

METODE FUNGSI PENALTI EKSTERIOR. Skripsi. Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Recommend Documents