plagiat merupakan tindakan tidak terpuji … · satu syarat memperoleh gelar sarjana sains program...

PENYELESAIAN MASALAH

OPTIMISASI NONLINEAR BERKENDALA

DENGAN METODE FUNGSI PENALTI INTERIOR

Skripsi

Diajukan untuk Memenuhi Salah

Satu Syarat Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Disusun Oleh :

Daniel Teguh Kurniawan

NIM : 013114027

PROGRAM STUDI MATEMATIKA

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2008

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

THE SOLUTION

OF NONLINEAR CONSTRAINED OPTIMIZATION PROBLEMS

WITH INTERIOR PENALTY FUNCTION METHODS

THESIS

Presented as Partial Fulfillment of the Requirements

to Obtain the Sarjana Sains Degree

in Mathematics

By :


Student Number : 013114027

MATHEMATICS STUDY PROGRAM

MATHEMATICS DEPARTMENT

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2008

ii


HALAMAN PERSEMBAHAN

” PERIHAL WAKTU ”

Selama-lamanya bukan berarti kekal, namun kekal

adalah selama-lamanya.

Jangan biarkan waktu terbuang dengan sia-sia,

karena waktu terus berlalu.

Waktu sangatlah mahal dan singkat, sekali berlalu

tidak akan kembali.

MOTTO

” Tetapi carilah dahulu Kerajaan Allah dan kebenarannya, maka

semuanya itu akan ditambahkan kepadamu.” ( Matius 6:33 )

Skripsi punika kawula aturaken :

Konjuk dhumateng Gusti Yesus ingkang tansah paring sih rahmat lan

tentrem rahayu. Mekaten ugi Bapak lan Ibu ingkang tansah paring

panggulowenthah dhumateng kula saha Mas Danang lan Mas Aris ingkang

tansah paring daya panyengkuyung kagem mungkasi skripsi kula punika.

Kula tansah tresna dhumateng sadaya ingkang sampun mbiyantu murih

cekaping skripsi kula. Maturnuwun, Gusti berkahi.

v


ABSTRAK

Metode fungsi penalti interior merupakan metode yang digunakan untuk menyelesaikan masalah optimisasi nonlinear berkendala dengan mengubah masalah tersebut menjadi masalah optimisasi nonlinear tak berkendala. Dalam metode ini, pencarian penyelesaian optimalnya dimulai dari daerah layak

Bentuk umum dari fungsi penalti interior adalah

φ k = φ (x, kμ ) = f(x) + kμm

j 1=Σ B(x)

dengan B(x) = )(

1xjg

− , g (x) merupakan kendala dan parameter penalti .

Dalam penulisan ini metode yang digunakan untuk meminimalkan

j 0>μ k

φ (x, kμ ) adalah Metode Newton. Penyelesaian optimal didapatkan jika nilai φ (x, kμ ) konvergen ke f(x) dengan 1+μ≥μ kk dan 0→μ k , ∞→k .

vi


ABSTRACT

Interior penalty function methods is a method which is used to solve the constrained nonlinear optimization problem by changing the problem become the unconstrained nonlinear optimization. In this method, the optimal solution searching is begun from the feasible region.

The general expression of the interior penalty function is

φ k = φ (x, kμ ) = f(x) + kμm

j 1=Σ B(x)

where B(x) = )(

1xjg

− , g (x) is the constraints and penalty parameters . j 0>μ k

In this thesis, the method that is used for minimizing φ (x, kμ ) is a Newton methods. The optimal solution is obtained if φ (x, kμ ) converge to f(x) as

and 1+μ≥μ kk 0→μ k , ∞→k .

vii


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, 12 Juni 2008

Penulis,


viii


LEMBAR PERNYATAAN PERSETUJUAN

PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Daniel Teguh Kurniawan

Nomor : 013114027

Demi pengembangan ilmu pengetahuan, saya memberikan kepada perpustakaan

Universitas Sanata Dharma karya ilmiah saya yamg berjudul:

“ Penyelesaian Masalah Optimasi Nonlinear Berkendala

Dengan Metode Fungsi Penalti Interior ”

Dengan demikian saya memberikan kepada perpustakaan Universitas Sanata

Dharma hak untuk menyimpan, mengalihkan dalam bentuk media lain,

mengelolanya dalam bentuk pangkalan data, mendistribusikannya secara terbatas

dan mempublikasikannya di internet atau media lain untuk kepentingan akademis

tanpa perlu meminta ijin dari saya maupun memberikan royalti kepada saya

selama tetap mencantumkan nama saya sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di Yogyakarta

Pada tanggal 12 Juni 2008

Yang menyatakan, ( Daniel Teguh Kurniawan )

ix


KATA PENGANTAR

Segala puji dan syukur, penulis panjatkan kepada Tuhan Yesus Kristus,

sang Juru Selamat. Karena kasih dan karunia-Nya maka skripsi ini dapat

terselesaikan dengan baik.

Dalam penyusunan skripsi ini penulis meminta bantuan dari berbagai

pihak. Oleh karena itu, dengan segala kerendahan hati penulis ingin

menyampaikan ucapan terima kasih kepada :

1. Ibu Lusia Krismiyati Budiasih, S.Si., M.Si., selaku dosen pembimbing dan

Kaprodi Matematika FST-USD yang dengan rendah hati mau meluangkan

banyak waktu luang dan penuh kesabaran telah membimbing selama

penyusunan skripsi ini walaupun penulis sering terlambat bahkan kabur dari

jadwal bimbingan dengan waktu yang cukup lama.

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

3. Kakak-kakakku, Danang dan Aris, yang selalu mendorong untuk dapat

menyelesaikan skripsi tepat waktu tapi tidak bisa sesuai dengan yang

diharapkan. .

4. Teman-teman “ Penghuni Terakhir “ : Tedy “ Bear “, Rita “ poco-poco “,

Zefanya, Yuli, yang bersama-sama berjuang keluar dari “selingan hidup” ini

dan yang saling memberikan semangat, motivasi supaya lulus sama-sama.

5. Keluarga Besar Rakiman di Klaten atas dukungan doanya..

6. Teman-teman pemuda remaja GKJ Gondangwinangun Klaten dan Teman-

teman pemuda remaja GKJ Ketandan, terima kasih atas dukungan doanya.

x


7. Sahabat-sahabatku di Matematika Angkatan’01, Ariel, Ray, Andre, Indah,

Deta, Maria, Erika, Ajeng, Very, Yuli, Wiwit, Vrysca, April, Alam, Dani,

Tabitha, Upik. Tidak akan pernah ku lupakan semua waktu yang pernah kita

lewati.

8. Mas Nadi “ sebagai pembimbing skripsi di kos”, Ridwan ” Sahabat dan

saudaraku ” terima kasih atas tumpangan kostnya.

9. Teman-teman PMK “ OIKUMENE “ yang selalu berbagi suka duka dalam

hidup. Maxi dan Tata “ Maranatha Family “ atas dukungan doanya.

10. Teman-teman pemuda Karang Taruna “ Mekar Sari “ di desa tempat saya

tinggal, terima kasih atas dukungan doanya.

11. Teman-teman SMU 2 Klaten, Seka dan Okie terima kasih atas petuah bijaknya.

12. Semua pihak yang telah membantu yang tidak dapat disebutkan satu persatu.

Tak ada gading yang tak retak, penulis menyadari kekurangan dalam

skripsi ini, untuk itu saran dan kritik sangat diharapkan dalam peningkatan

kualitas skripsi ini.Akhirnya penulis berharap semoga skripsi ini dapat bermanfaat

bagi semua pihak.

Yogyakarta, 12 Juni 2008

Penulis,


xi


DAFTAR ISI

Halaman

HALAMAN JUDUL INDONESIA ............................................................... i

HALAMAN JUDUL INGGRIS..... ............................................................... ii

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

HALAMAN PENGESAHAN ....................................................................... iv

HALAMAN PERSEMBAHAN .................................................................... v

ABSTRAK .................................................................................................... vi

ABSTRACT .................................................................................................. vii

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

LEMBAR PERNYATAAN.......................................................................... ix

KATA PENGANTAR ................................................................................... x

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 ................................................................................ 3

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

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

F. Metode Penelitian ................................................................................ 4

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

xii


BAB II DASAR TEORI ............................................................................. 6

A. Ruang Vektor dan Ruang Euclid ..................................................... 6

B. Barisan Konvergen dan Barisan Monoton ....................................... 7

C. Fungsi Kontinu ................................................................................ 9

D. Turunan parsial ................................................................................ 10

E. Metode newton ................................................................................ 10

F. Optimisasi ....................................................................................... 12

1. Masalah Optimasi........................................................................ 12

2. Penyelesaian Masalah Optimasi.................................................. 14

BAB III METODE FUNGSI PENALTI INTERIOR................................. 15

A. Konsep Dasar Fungsi Penalti ........................................................... 15

B. Bentuk Umum Fungsi Penalti Interior ............................................. 19

C. Algoritma Metode Fungsi Penalti Interior ....................................... 20

D. Konvergensi Metode Fungsi Penalti Interior ................................... 54

BAB IV PENUTUP ..................................................................................... 57

A. Kesimpulan ...................................................................................... 57

B. Saran ................................................................................................ 58

DAFTAR PUSTAKA .................................................................................. 59

LAMPIRAN ................................................................................................ 60

xiii


DAFTAR GAMBAR

Halaman

Gambar 2.1 Flowchart Algoritma Metode Newton................................... 11

Gambar 2.2 Peminimum f(x) sama dengan Pemaksimum -f(x)............... 12

Gambar 3.1.1 Ilustrasi Metode Fungi Penalti Eksterior................................ 18

Gambar 3.1.2 Ilustrasi Metode Fungsi Penalti Interior................................. 18

Gambar 3.2 Flowchart Algoritma Metode Fungsi Penalti Interior............. 21

xiv


DAFTAR TABEL

Halaman

Tabel 3.3.1 Output penyelesaian contoh 3.3.1................................................... 40



xv


1

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Optimisasi adalah tindakan yang dilakukan untuk mendapatkan hasil

terbaik dari kondisi-kondisi yang diberikan ( sebagai suatu masalah ). Optimisasi

sering kita jumpai dalam kehidupan sehari-hari seperti pada bidang ekonomi

maupun manajemen. Sebagai contoh perusahaan pakaian 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, dengan demikian optimisasi dapat didefinisikan sebagai proses

untuk menemukan nilai maksimum dan minimum dari suatu fungsi.

Bidang ilmu matematika yang secara umum mempelajari tentang

optimisasi adalah Riset Operasi. Riset Operasi sendiri terbagi menjadi 3 jenis

metode, yang secara khusus mempelajari tentang masalah optimisasi tersebut

yaitu : Pemrograman Matematika, Proses Stokhastik dan Metode Statistika.

Pemrograman Matematika digunakan untuk menemukan nilai fungsi dengan

beberapa variabel dari suatu himpunan yang sudah ditentukan dengan kendala-

kendalanya. Pemrograman Matematika terbagi lagi dalam beberapa bagian,

diantaranya adalah Program Linear dan Program Nonlinear.

Dalam Program Nonlinear masalah optimisasi dibedakan menjadi dua,

yaitu masalah optimisasi tanpa kendala dan masalah optimisasi dengan kendala.


2

Masalah optimisasi dengan kendala merupakan masalah mengoptimalkan fungsi

sasaran dengan kendala-kendalanya, dimana fungsi sasaran dan kendala-

kendalanya tersebut adalah fungsi nonlinear. Ada beberapa metode yang

digunakan dalam menyelesaikan masalah optimisasi program nonlinear dengan

kendala yaitu ; Metode Primal, Metode Penalti, Metode Dual dan Metode

Pemotongan Kurva serta Metode Lagrange.

Pada skripsi ini akan dibahas pendekatan numeris untuk menyelesaikan

masalah optimisasi Program Nonlinear dengan kendala berupa persamaan dan

pertidaksamaan. Pendekatan yang digunakan adalah Metode Fungsi Penalti.

Metode Fungsi Penalti merupakan salah satu Metode Numerik yang digunakan

untuk mengubah masalah optimisasi dengan kendala menjadi masalah tanpa

kendala dengan menambahkan fungsi penalti pada fungsi sasaran. Istilah penalti

dipilih sedemikian hingga nilainya akan kecil untuk titik yang jauh dari batas

kendala, dimulai dari titik layak x , yaitu sembarang titik yang memenuhi semua

kendala, titik subbarisan yang dibangun akan selalu terletak di daerah layak

karena batas kendala bertindak sebagai penghalang sepanjang proses minimasasi.

Inilah alasan mengapa Metode Fungsi Penalti juga dikenal sebagai metode

penghalang.

Pada dasarnya Metode Penalti terbagi menjadi 2 yaitu Metode Fungsi

Penalti Eksterior dan Metode Fungsi Penalti Interior. Akan tetapi, skripsi ini

hanya membahas Metode Fungsi Penalti Interior, dimana penalti ditambahkan

pada fungsi sasaran. Metode ini menghasilkan barisan titik-titik layak yang

limitnya merupakan penyelesaian optimal dari masalah asli.


3

B. Perumusan Masalah

Pokok masalah yang akan dibahas dalam skripsi ini sebagai berikut :

1. Apa itu Metode Fungsi Penalti Interior ?

2. Bagaimana menyelesaikan masalah optimisasi dengan kendala berupa

pertidaksamaan dengan Metode Fungsi Penalti Interior ?

C. Batasan Masalah

Pada penulisan skripsi ini hanya akan dibahas tentang Metode Fungsi

Penalti Interior untuk menyelesaikan masalah optimisasi Program Nonlinear

dengan kendala-kendala berupa pertidaksamaan dan teknik yang digunakan dalam

menyelesaikan masalah optimisasi tak berkendala menggunakan metode newton.

D. Tujuan Penulisan

Penulisan ini bertujuan untuk memberi wawasan dan pengetahuan kepada

pembaca dengan pengertian dasar tentang bagaimana cara menyelesaikan masalah

optimisasi Program Nonlinear dengan kendala dengan Metode Fungsi Penalti

Interior.


4

E. Manfaat Penulisan

Manfaat dari penulisan skripsi ini yang sangat diharapkan adalah penulis

dapat mengetahui dan memahami bagaimana bentuk Metode Fungsi Penalti

Interior dan bagaimana cara menyelesaikan masalah optimisasi dengan kendala

dengan Metode Fungsi Penalti Interior dengan kendala-kendala berupa

pertidaksamaan.

F. Metode Penulisan

Metode penulisan yang digunakan dalam penulisan skripsi ini adalah

metode studi literatur atau studi pustaka, yaitu dengan membaca dan mempelajari

materi dari buku-buku acuan yang berkaitan dengan masalah ini. Jadi, dalam

skripsi ini tidak ada penemuan-penemuan yang baru.

G. Sistematika Penulisan

BAB I : PENDAHULUAN

Dalam bab I akan dibahas tentang latar belakang, perumusan

masalah, batasan masalah, tujuan penulisan, manfaat penulisan,

metode penulisan dan sistematika penulisan.


5

BAB II : DASAR TEORI

Dalam bab ini akan dibahas konsep ruang vektor dan ruang Euclid,

fungsi kontinu dan fungsi terdiferensial, Barisan Konvergen dan

Barisan Monoton, turunan parsial, syarat optimalitas untuk masalah

berkendala, Metode Newton serta teori optimisasi yang nantinya

akan digunakan untuk memahami metode Fungsi Penalti Interior.

BAB III : METODE FUNGSI PENALTI INTERIOR

Dalam bab III akan dibahas tentang konsep fungsi penalti,

interpretasi geometris fungsi penalti, pengertian metode Fungsi

Penalti Interior, bentuk umum Fungsi Penalti Interior dan algoritma

metode Fungsi Penalti Interior disertai beberapa contoh masalah

optimisasi nonlinear berkendala yang diselesaikan dengan metode

Fungsi Penalti Interior, implementasi dengan program matlab serta

konvergensi Metode Fungsi Penalti Interior.

BAB IV : PENUTUP

Bab IV berisi kesimpulan dan saran.


15

BAB III

METODE FUNGSI PENALTI INTERIOR

Pada bab ini akan dipaparkan tentang metode fungsi penalti interior

sebagai salah satu cara untuk menyelesaikan masalah program nonlinear, yakni

masalah optimisasi berkendala. Proses pencarian dalam menemukan penyelesaian

optimal dengan menggunakan metode fungsi penalti interior akan dimulai dari

daerah layak. Tetapi sebelum membahas lebih jauh tentang metode tersebut, akan

dibahas terlebih dahulu tentang konsep dasar metode tersebut.

A. Konsep Dasar Fungsi Penalti

Salah satu cara untuk mengubah masalah optimisasi berkendala menjadi

masalah optimisasi tak berkendala adalah dengan metode fungsi penalti. Dalam

kehidupan sehari-hari penalti yang berarti hukuman terjadi karena adanya

pelanggaran. Dengan demikian, dalam masalah optimisasi berkendala fungsi

penalti terjadi karena adanya pelanggaran, yaitu dengan menghilangkan kendala

pada masalah optimisasi tersebut.

Masalah optimisasi dasar dapat dinyatakan dalam bentuk

meminimalkan f (x)

dengan kendala g j (x) ≤ 0 , j = 1, 2, Κ , m ( 3.1 )

x ∈ X


16

dengan fungsi f, g j merupakan fungsi kontinu pada nℜ dan X himpunan tidak

kosong di nℜ . Perhatikan bahwa jika ada sembarang kendala yang diberikan

maka persamaan tersebut dipenuhi oleh x ∈ X . Masalah optimisasi berkendala

tersebut diubah ke dalam sebuah masalah minimisasi tak berkendala dengan

membangun sebuah fungsi yang berbentuk

φ k = φ (x, kμ ) = f(x) + kμm

j 1=Σ B(x) ( 3.2 )

dimana B(x) adalah suatu fungsi dari kendala g j dan kμ adalah konstanta positif

yang dinamakan parameter penalti. Suku kedua pada ruas kanan dari persamaan

( 3.2 ) disebut syarat penalti. Jika minimisasi tak berkendala dari fungsi φ diulang

untuk suatu barisan dari nilai-nilai parameter penalti kμ untuk k = 1, 2, Κ maka

penyelesaiannya akan konvergen ke masalah optimisasi dasar yang dinyatakan

dalam persamaan ( 3.1 ). Jadi, penalti dapat diartikan sebagai fungsi yang

ditambahkan pada fungsi obyektif dengan parameter penalti. Metode penambahan

fungsi penalti ini disebut sebagai Metode Fungsi Penalti.

Rumus Metode Fungsi Penalti untuk masalah berkendala dengan kendala

berbentuk pertidaksamaan dapat dibagi menjadi dua kategori yaitu metode fungsi

penalti interior dan metode fungsi penalti eksterior. Rumus metode fungsi penalti

interior yang sering digunakan berbentuk

B(x) = Σ=

m

j 1 -

)(1

xjg

atau B(x) =Σ=

m

j 1 ln [- g j (x) ]


17

Rumus metode fungsi penalti eksterior yang sering digunakan berbentuk

B(x) = max[0, g j (x)]

atau

B(x) = [ ]{ }2)(,0max xjg

Di dalam metode fungsi penalti interior minimal tak berkendala dari φ k

berada dalam daerah layak dan konvergen ke penyelesaian persamaan ( 3.1 )

dengan kμ berbeda dalam aturan tertentu. Dalam metode fungsi penalti eksterior

titik yang membuat nilai minimum dari masalah tak berkendala φ k berada dalam

daerah tak layak dan konvergen ke penyelesaian yang diinginkan dari luar dengan

kμ berbeda dalam aturan khusus. Untuk masalah penalti interior dan eksterior,

konvergensi dari masalah optimisasi tak berkendala φ k diilustrasikan pada

Gambar 2a dan Gambar 2b untuk masalah mencari nilai x yang

meminimalkan f(x) = α x 1

dengan kendala g 1 (x) = 1x−β ≤ 0


18

Gambar 3.1.1 Ilustrasi Metode Fungsi Penalti Eksterior

Gambar 3.1.2 Ilustrasi Metode Fungsi Penalti Interior


19

Untuk menggambarkan secara geometris metode fungsi penalti interior,

dibuat terlebih dahulu grafik fungsi f(x) = α x 1 dan kendala g 1 (x) = 1x−β ≤ 0.

selanjutnya masalah optimasi berkendala tersebut dibawa ke dalam masalah

optimisasi tak berkendala dengan membentuk sebuah fungsi

β1

μα=1

1 xxφ k dengan B(x) = -

1

1x−β

dan kμ sebagai parameter penalti.

Pencarian optimum dimulai dari daerah layak 1x yang berada di daerah layak dan

titik berikutnya yang dihasilkan selalu berada dalam daerah layak karena ada

batas-batasnya. Karena pemilihan kμ yang besar maka mengakibatkan kφ masih

jauh dari optimum. Dengan cara yang sama, jika minimasi tak berkendala dari

fungsi kφ diulang untuk suatu barisan nilai-nilai parameter penalti k = 1, 2, ....

dimana 1+μ>μ kk maka penyelesaian akan konvergen ke masalah optimisasi dasar

dan akan mendekati optimum.

B. Bentuk Umum Fungsi Penalti Interior

Dari Sub bab sebelumnya, dalam metode fungsi penalti interior sebuah

fungsi baru φ yang dibentuk dengan menambahkan syarat penalti ke fungsi

obyektif. Syarat penalti dipilih sedemikian hingga nilainya mengecil sehingga

nilai fungsi φ akan menuju optimum. Kejadian ini bisa dilihat pada Gambar

3.1.2. Minimisasi tak berkendala dari fungsi φ (x, kμ ) dimulai dari sembarang

titik layak 1x dan titik berikutnya yang dihasilkan selalu pada daerah layak. Hal

ini disebabkan karena batas-batas kendala menjadi palang atau rintangan (barrier)


20

selama proses minimisasi. Inilah alasan mengapa metode fungsi penalti interior

juga disebut sebagai metode barrier.

Fungsi φ (x, kμ ) didefinisikan sebagai

φ (x, kμ ) = f(x) - kμ Σ=

m

j 1 )(1

xjg ( 3.3 )

Terlihat bahwa nilai fungsi φ (x, kμ ) akan selalu lebih besar dari f(x)

ketika g j (x) negatif untuk semua titik layak x. Jika semua kendala g j (x)

dipenuhi dengan tanda persamaan maka nilai φ menuju tak hingga dan syarat

penalti di ( 3.3 ) tidak terdefinisi jika x tak layak. Karena persamaan ini tidak

diperbolehkannya adanya kendala yang dilanggar maka titik awal layak harus

dicari dalam proses pencarian menuju ke titik optimum. Sebagian besar masalah

optimisasi nonlinear berkendala tidaklah sulit untuk menemukan sebuah titik yang

memenuhi semua kendala g j (x) ≤ 0 karena pemilihan titik x yang bebas.

C. Algoritma Metode Fungsi Penalti Interior

Berikut akan diberikan algoritma dari metode fungsi penalti interior untuk

menyelesaikan masalah optimisasi dasar :

meminimalkan f (x)

kendala g j (x) ≤ 0 , j = 1, 2, Κ , m

x ∈ X


21

Algoritma metode fungsi penalti interior dapat diperlihatkan sebagai berikut :

Gambar 3.2 Flowchart Algoritma Metode Fungsi Penalti Interior

Masukkan titik awal x 1 ,ε > 0, 1μ > 0 , dan skalar β >1

Mulai

Tentukan k = 1

x *k penyelesaian layak, langkah

dihentikan

Bentuklah fungsi φ (x,μ ) = f(x) + kμ B(x)

dengan

B(x) = m

j 1=Σ

)(1xjg

−

Menentukan penyelesaian optimum dari masalah tidak berkendala x *

k dari φ (x,μ )

Selesai

kμ B(x *k ) < ε

1+kμ = kβμ dengan k = k +1

YA

TIDAK


22

Secara umum langkah-langkah penyelesaian dengan metode fungsi penalti interior

adalah :

Langkah 1

Menentukan nilai awal x 1 , parameter penalti 1μ > 0 dan skalar )1,0(∈β

dan diberikan ε > 0 dan k = 1.

Langkah 2

Membentuk fungsi φ (x, kμ ) = f(x) + kμ B(x)

dengan B(x) =Σ=

m

j 1 -

)(1

xjg

Langkah 3

Mencari penyelesaian optimum x *k dari masalah optimisasi tidak

berkendala φ (x, kμ ) = f(x) + kμ B(x).

Langkah 4

Jika kμ B(x k ) < ε langkah dihentikan, maka x 1+k merupakan

penyelesaian layak. Sebaliknya jika kμ B(x k ) > ε , maka tetapkan 1+kμ = β kμ ,

ganti k dengan k + 1 dan ulangi Langkah 2.

Ada hal-hal yang perlu dipertimbangkan dalam menerapkan metode ini :

1 Proses iterasi dimulai dengan titik awal x1 tetapi mungkin dalam

beberapa kasus titik awal x 1 ini tidak perlu dipersiapkan

Tidaklah sulit untuk menentukan titik awal x 1 dalam masalah optimisasi

nonlinear berkendala yang memenuhi semua kendala 0)( 1 <xjg . Dalam


23

kasus khusus titik awal tidak diperlukan dalam menyelesaikan masalah

optimisasi berkendala yang dapat dilihat dari fungsi kendalanya yang hanya

terdapat satu variabel. Jika fungsi kendalanya terdapat beberapa variabel

maka titik awal perlu dipersiapkan. Tetapi, ada beberapa keadaan sedemikian

hingga titik layak tidak bisa ditemukan dengan mudah. Dalam kasus seperti

ini, titik layak awal yang diminta dapat ditemukan dengan menggunakan

metode fungsi penalti interior itu sendiri. Dengan memperhatikan hal-hal

sebagai berikut :

Langkah i

Pilih sembarang titik x 1 dan evaluasi g j (x) di titik x 1 . Karena titik x 1

sembarang maka tidak semua titik memenuhi semua kendala pertidaksamaan.

Jika ada r dari m kendala yang dilanggar, maka kendala-kendala tersebut

dikelompokkan kembali sedemikian hingga r kendala yang dilanggar akan

menjadi satu kelompok yang terakhir yaitu

0)( 1 <xjg , j =1,2, Κ , m-r

dan 0)( 1 ≥xjg , j = m-r+1, m-r +2, Κ , m ( 3.4 )

Langkah ii

Identifikasi kendala yang memiliki kesalahan terbesar di titik x 1 yaitu

dengan mencari bilangan bulat k sedemikian hingga

[ ])()( 11 xx jk gmaksg = untuk j = m-r+1, m-r +2, Κ , m ( 3.5 )


24

Langkah iii

Selesaikan masalah optimasi yang dibuat dalam langkah 3 dengan

mengambil titik x 1 sebagai titik awal. Rumuskan masalah optimisasi yang

baru seperti mencari x yang meminimalkan g k (x) dengan kendala

0)( 1 ≤xjg j =1,2, Κ , m-r ( 3.6 )

dan 0)()( 11 ≤− xx kj gg , j = m-r+1, m-r +2, Κ , k-1, k+1, Κ , m

Langkah iv

Selesaikan masalah optimisasi pada langkah (iii) dengan mengambil titik

x 1 sebagai titik awal menggunakan metode fungsi penalti interior. Metode

ini dapat diakhiri ketika nilai fungsi g k (x) 0≤ . Jadi penyelesaian akan

menghasilkan x k yang memenuhi sedikitnya satu kendala dari himpunan

kendala yang dilanggar oleh x 1 .

Langkah v

Jika semua kendala tidak dipenuhi oleh titik x k , ambil titik baru x1 = x k

dan kendala dikelompokkan kembali sedemikian hingga r pada kendala yang

terakhir tidak akan dipenuhi dan ulangi langkah ii.

Langkah ini dapat diulangi sampai semua kendala terpenuhi dan didapat

0)( 1 <xjg , j =1,2, ... , m-r


25

2 Dengan mencari parameter penalti awal ( 1μ ) yang sesuai

Jika minimisasi tak berkendala φ (x, kμ ) dikerjakan untuk suatu barisan

turun kμ , dengan memilih sebuah nilai 1μ yang sangat kecil maka nilai

optimum dari fungsi φ akan konvergen ke penyelesaian masalah optimisasi

dasar. Namun dari segi penghitungan, untuk minimisasi fungsi φ akan lebih

mudah jika kμ besar. Hal ini dapat dilihat pada Gambar 3.1.2. Terlihat

bahwa jika nilai kμ menjadi semakin kecil, nilai fungsi φ berubah dengan

lebih cepat di sekitar minimum ∗kφ . Pencarian minimum dari suatu fungsi

lebih mudah bila grafiknya lebih mulus karena fungsinya kontinu dan dapat

diturunkan. Jika kμ besar maka minimisasi tak berkendala φ akan menjadi

lebih mudah dan minimum dari kφ , *kx , akan menjadi lebih jauh dari

minimum x ∗ .

3 Nilai perkalian faktor β yang dipilih haruslah tepat

Jika nilai awal kμ sudah dipilih maka nilai-nilai kμ berikutnya harus

dipilih sedemikian hingga 1+kμ < kμ . Nilai kμ dipilih dengan 1+kμ =β kμ

dimana β < 1. Nilai β dapat diambil sebagai 0,1 atau 0,2 atau 0,5 dan

seterusnya.


26

4 Kriteria kekonvergenan yang sesuai harus dipilih untuk menentukan

nilai optimum

Karena minimisasi tak berkendala dari φ (x, kμ ) harus dikerjakan

menurut suatu barisan turun nilai kμ maka perlu menggunakan kriteria

konvergensi yang sesuai untuk mengidentifikasikan titik optimum. Proses

dapat dihentikan pada saat syarat berikut dipenuhi.

a. Selisih relatif antara nilai fungsi obyektif yang dihasilkan pada akhir dari

sembarang dua minimisasi tak berkendala yang berurutan berada dibawah

sebuah bilangan yang kecil 1ε , yaitu

1*

*1-k

*

)()()(

ε≤−

k

k

fff

xxx

.

b. Selisih antara titik optimum *kx - *

1−kx menjadi sangat kecil. Ini dapat

dinyatakan dalam beberapa cara. Yang biasa digunakan adalah

2)( ε≤Δ ix .

Dengan xΔ = *kx - *

1−kx

( xΔ ) i adalah anggota ke - i dari vektor xΔ

Max |( xΔ ) i | ≤ 3ε

| xΔ | = [ ] 2122

221 )()()( nxxx Δ++Δ+Δ Κ ≤ 4ε


27

Nilai dari 1ε sampai 4ε harus dipilih bergantung pada karakteristik dari

masalah yang ditangani.

Berikut ini akan diberikan contoh masalah minimisasi yang tidak

menggunakan titik awal.

Contoh 3.1.1

Selesaikan masalah optimisasi berkendala berikut :

Minimalkan f ( x 1 , x 2 ) = 31 (x 1 + 3 ) 3 + x 2

Kendala g 1 ( x 1 , x 2 ) = - x 1 + 1 ≤ 0

g 2 ( x 1 , x 2 ) = - x 2 ≤ 0

Penyelesaiannya :

Dalam kasus di atas titik awal tidak diperlukan karena fungsi kendalanya

hanya terdapat satu variabel. Untuk mencari penyelesaian optimumnya maka

dibutuhkan parameter penalti awal ( 1μ ) yang sesuai.

Langkah 1

Misalkan ε = 0,00001

β = 0,1 1μ = 1000

Ditentukan k = 1


28

Langkah 2

Membentuk fungsi φ (x,μ ) = f(x) + kμ B(x)

B(x) dipilih dengan B(x) = Σ=

2

1j )(1xjg

−

= ⎥⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

Sehingga diperoleh

φ (x,μ ) = f(x) + kμ B(x)

= 31 (x 1 + 3 ) 3 + x 2 - kμ ⎥

⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

Langkah 3

Untuk mencari penyelesaian optimum dari masalah optimisasi tak berkendala,

dibutuhkan penurunan parsial φ terhadap 1x dan 2x :

Turunan parsial φ terhadap x 1 diperoleh :

1x∂∂φ = (x 1 + 1 ) 2 - 2

1 )1( xk

−μ

= 0

atau (x 1 + 1 ) 2 = 21 )1( x

k

−μ

(x 1 + 1 ) 2 (1 - x 1 ) 2 = kμ

( x 12 + 2x 1 +1 ) ( 1 - 2x 1 + x 1

2 ) = kμ

x 14 - 2 x 1

2 + 1 = kμ

atau (x 21 - 1 ) 2 = kμ


29

x 21 - 1 = kμ

21

x 1 = ( kμ2

1

+1 ) 21

(3.1.1)

Turunan parsialφ terhadap x 2 diperoleh :

2x∂∂φ = 1 - 2

2xkμ = 0

x 22 = kμ

atau x 2 = kμ 21

(3.1.2)

Dari persamaan (3.1.1) dan (3.1.2) diperoleh penyelesaian optimum tak

berkendala dan

x *1 ( kμ ) = ( kμ

21

+1 ) 21

x *2 ( kμ ) = kμ 2

1

Dalam masalah ini tidak diperlukan titik awal karena setelah melakukan

penghitungan secara kalkulus, titik x *k bergantung pada parameter penalti ( 1μ ).

Apabila penyelesaian optimum tersebut disubstitusikan ke fungsi φ maka

didapatkan :

)(min kμφ = 31 (x 1 + 3 ) 3 + x 2 - kμ ⎥

⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

= 31 [( kμ 2

1 +1 ) 21 + 1] 3 + kμ 2

1 - kμ { [1)1(

12

12

1++− kμ

] – [2

1

1

kμ] }


30

= 31 [( kμ 2

1 +1 ) 21 + 1] 3 + kμ 2

1 + [1)1( 2

12

1++−

−

k

k

μ

μ ] +

21

k

k

μ

μ

= 31 [( kμ 2

1 +1 ) 21 + 1] 3 + kμ 2

1 + )1)()1(1(

)1(

21

21

kk

kk

μμ

μμ

+− + kμ 2

1

= 31 [( kμ 2

1 +1 ) 21 + 1] 3 + 2 kμ 2

1 - 2

12

1)1(11

1

+− kkk

μμμ

= 31 [( kμ 2

1 +1 ) 21 + 1] 3 + 2 kμ 2

1 - 2

12

1

2 ))1(1(11

+− kkk

μμμ

)(min kμφ = 31 [( kμ 2

1 +1 ) 21 + 1] 3 + 2 kμ 2

1 - 2

1

23 2

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−

kkk μμμ

Untuk mendapatkan penyelesaian dari masalah optimasi dasar dicari melalui :

f min = 0

lim→kμ

minφ ( kμ )

= 0

lim→kμ

{ 31 [( kμ 2

1 +1 ) 21 + 1] 3 + 2 kμ 2

1 - 2

1

23 2

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−

kkk μμμ

}

= 38 = 2,66667

Iterasi 1

Untuk k = 1

x *1 ( 1μ ) = ( 1μ

21

+1 ) 21


31

= ( 1000 21 + 1 ) 2

1

= 5,71164

dan

x *2 ( 1μ ) = kμ 2

1

= 1000 21

= 31,62278

Sehingga diperoleh :

)( 1min μφ = 31 [( 1μ 2

1 +1 ) 21 + 1] 3 + 2 1μ 2

1 - 2

1

23 2

111

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

= 31 [(1000 2

1 +1 ) 21 + 1] 3 + 2(1000 ) 2

1 - 2

1

23 21000

11000

11000

11

⎥⎦⎤

⎢⎣⎡ +−

= 100,777761 + 63,245554 + 210,748156

= 374,77147

dan f( 1μ ) = 31 ( )31 1 +x + x 2

= 31 ( 5,71164 + 1 ) 3 + 31,62278

= 100,777761 + 31,62278

= 132,400541

1μ B(x *1 ) = kμ ⎥

⎦

⎤⎢⎣

⎡−

+− 2

11

1xx


32

= 1μ 21 -

21

23 2

111

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

= 31,62278 + 210,74816

= 242,37094 > ε

Penyelesaian belum optimal karena 1μ B(x *1 ) > ε maka langkah diteruskan.

Langkah 4

Tetapkan 2μ = β 1μ

= (0,1)1000 = 100

Iterasi 2

Untuk k = 2

Langkah 3

Berdasarkan iterasi sebelumnya, nilai φ minimum dicari jika

x *1 ( 2μ ) = ( 2μ 2

1 + 1 ) 21

= ( 100 21 + 1 ) 2

1

= 3,31662

dan x *2 ( 2μ ) = 2μ 2

1

= 100 21 = 10


)( 2min μφ = { 31 [( 2μ 2

1 +1 ) 21 + 1] 3 + 2


33

2μ 21 -

21

23 2

222

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}

= 31 [(100 2

1 +1 ) 21 + 1] 3 + 2(100 ) 2

1 - 2

1

23 2100

1100

1100

11

⎥⎦⎤

⎢⎣⎡ +−

= 89,9776

dan f( 2μ ) = 31 ( )31 1 +x + x 2

= 31 [(100 2

1 +1 ) 21 + 1] 3 + 100 2

1

= 36, 8109

2μ B(x *2 ) = 10 + 43,16671

= 53,16671 > ε


Langkah 4

Tetapkan 3μ = 2.μβ

= (0,1).100

= 10

Iterasi 3

Untuk k = 3



34

x *1 ( 3μ ) = ( 3μ 2

1 + 1 ) 21

= ( 10 21 +1 ) 2

1

= 2,04017

dan x *2 ( 3μ ) = 3μ 2

1

= 10 21

= 3,16228


)( 3min μφ = { 31 [( 3μ 2

1 +1 ) 21 + 1] 3 + 2 3μ 2

1 - 2

1

23 2

333

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}

= 31 [ 2,04017 + 1 ] 3 + 2 ( 3,16228 ) -

21

23 210

110

1101

1

⎥⎦⎤

⎢⎣⎡ +−

= 25,3048

dan f( 3μ ) = 31 ( )31 1 +x + x 2

= 9, 36636 + 3,16228

= 12,5286

3μ B(x *3 ) = 3,16228 + 9, 61381

= 12,77609 > ε



35

Langkah 4


= (0,1).10 = 1

Iterasi 4

Untuk k = 4


x *1 ( 4μ ) = ( 4μ 2

1 + 1 ) 21

= ( 2 ) 21

= 1,41421

dan x *2 ( 4μ ) = 4μ 2

1 = 1


)( 4min μφ = { 31 [( 4μ 2

1 +1 ) 21 + 1] 3 + 2 4μ 2

1 - 2

1

23 2

444

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}

= { 31 [(1 2

1 +1 ) 21 + 1] 3 + 2(1) 2

1 - 2

1

23 21

111

11

1

⎟⎠⎞

⎜⎝⎛ +−

}

= 31 (1,41421 + 1) 3 + 2 + 2,41421

= 4,69036+ 2 + 2,41421 = 9,10457

dan f( 4μ ) = 31 ( )31 1 +x + x 2

= 4,69036+ 1 = 5,69036


36

4μ B(x *4 ) = 1 + 2,41421

= 3,41421 > ε


Langkah 4


= (0,1).1 = 0,1

Iterasi 5

Untuk k = 5


x *1 ( 5μ ) = ( 5μ 2

1 + 1 ) 21

= (0,1 21 + 1 ) 2

1

= 1,14727

dan x *2 ( 5μ ) = μ 2

1

= 0,1 21

= 0,31623


)( 5min μφ = { 31 [( 5μ 2

1 +1 ) 21 + 1] 3 + 2 5μ 2

1 - 2

1

23 2

555

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}


37

= { 31 [( 1,0 2

1 +1 ) 21 + 1] 3 + 2( 1,0 ) 2

1 - 2

1

23 21,0

11,01

1,01

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−

}

= 3,300188 + 0,632456 + 0,06899

= 4,00163

dan f( 5μ ) = 31 ( )31 1 +x + x 2

= 3,300188 + 0,31623

= 3,61642

5μ B(x *5 ) = 0,31623 + 0,06899

= 0,38522 > ε


Langkah 4


= (0,1).(0,1) = 0,01

Iterasi 6

Untuk k = 6


x *1 ( 6μ ) = ( 6μ 2

1 + 1 ) 21

= 1,04881


38

dan x *2 ( 6μ ) = 6μ 2

1 = 0,1


)( 6min μφ = { 31 [( 6μ 2

1 +1 ) 21 + 1] 3 + 2 6μ 2

1 - 2

1

23 2

666

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}

= { 31 [( 01,0 2

1 +1 ) 21 + 1] 3 + 2( 01,0 ) 2

1 - 2

1

23 201,0

101,01

01,01

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−

}

= 2,86671 + 0,2 + 0,20488

= 3,27159

dan f( 6μ ) = 31 ( )31 1 +x + x 2

= 2,86671 + 0,1

= 2,96671

6μ B(x *6 ) = 0,1 + 0,20488

= 0,30488 > ε


Analog dengan langkah-langkah sebelumnya, titik optimal yang merupakan

penyelesaian optimal didapatkan pada iterasi yang ke-15, yakni

Langkah 4

15μ = 14.μβ

= (0,1).(10 10− ) = 10 11−


39

Iterasi 15

Untuk k = 15


x *1 ( 15μ ) = ( 15μ 2

1 + 1 ) 21

= 1,00000

dan x *2 ( 15μ ) = 15μ 2

1

= 0,00000


)( 15min μφ = { 31 [( 15μ 2

1 +1 ) 21 + 1] 3 + 2 15μ 2

1 - 2

1

23 2

151515

111

1

⎟⎟⎠

⎞⎜⎜⎝

⎛+−μμμ

}

= 2,66669

dan

f( 15μ ) = 31 ( )31 1 +x + x 2

= 2,66668

15μ B(x *15 ) = 0,000009

Karena 15μ B(x *15 ) = 0,000009 < ε maka langkah dihentikan.

Maka diperoleh penyelesaian dari masalah di atas dengan x *1 = 1, x *

2 = 0.

Pada iterasi ke-15 penyelesaian sudah optimum karena sudah memenuhi

syarat 15μ B(x *15 ) = 0,000009 < ε .


40

Berikut akan diberikan penyelesaian dengan menggunakan program

MATLAB. ( lampiran 1 )

Tabel 3.1.1 Output penyelesaian Contoh 3.1.1 dengan Matlab

Taksiran awal miu : 1000.00000

==============================================================

Iterasi miu x1 x2 min(miu) f(miu) miu_Bx

==============================================================

1 1000.00000 5.71164 31.62278 376.26364 132.40032 243.86332

2 100.00000 3.31662 10.00000 89.97716 36.81092 53.16625

3 10.00000 2.04017 3.16228 25.30476 12.52863 12.77613

4 1.00000 1.41421 1.00000 9.10457 5.69036 3.41421

5 0.10000 1.14727 0.31623 4.61167 3.61641 0.99525

6 0.01000 1.04881 0.10000 3.27159 2.96671 0.30488

7 0.00100 1.01569 0.03162 2.85690 2.76154 0.09536

8 0.00010 1.00499 0.01000 2.72672 2.69667 0.03005

9 0.00001 1.00158 0.00316 2.68565 2.67615 0.00949

10 0.00000 1.00050 0.00100 2.67267 2.66967 0.00300

11 0.00000 1.00016 0.00032 2.66856 2.66762 0.00095

12 0.00000 1.00005 0.00010 2.66727 2.66697 0.00030

13 0.00000 1.00002 0.00003 2.66686 2.66676 0.00009

14 0.00000 1.00000 0.00001 2.66673 2.66670 0.00003

15 0.00000 1.00000 0.00000 2.66669 2.66668 0.00001

==============================================================

Pada saat iterasi ke -15,miu_Bx<0.00001.

Jadi nilai miu yang meminimalkan min(miu) adalah :

x1 = 1.00000 dan x2 = 0.00000


41

Berikut akan diberikan contoh masalah optimisasi nonlinear berkendala

yang menggunakan titik awal.

Contoh 3.1.2

Selesaikan masalah kendala berikut :

Minimalkan f ( x 1 , x 2 ) = ( ) ( )22

21 35 −+− xx

Kendala g 1 ( x 1 , x 2 ) = - x 1 + x 2 - 3 ≤ 0

g 2 ( x 1 , x 2 ) = - x 1 + 2x 2 - 4 ≤ 0

Penyelesaiannya :

Langkah 1

Misalkan ε = 0,00001 ⎭⎬⎫

⎩⎨⎧

=00

0x

β = 0,1 1μ = 1

Ditentukan k = 1

Langkah 2



2

1i )(1xig

−

= - ⎥⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

Sehingga diperoleh

φ (x,μ ) = f(x) + kμ B(x)


42

= ( ) ( )22

21 35 −+− xx - kμ ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

Langkah 3

Untuk mencari penyelesaian optimum dari masalah tak berkendala

dibutuhkan suatu titik awal sehingga diperlukan metode yang sesuai. Untuk

memudahkan penghitungan dalam mencari penyelesaian optimum akan digunakan

program Matlab.

Iterasi 1

Untuk k = 1

x )1(1 = 0 dan x ( )1

2 = 0

Dari perhitungan dengan menggunakan Program Matlab diperoleh

)( 1min μφ = f(x) + 1μ B(x)

= ( ) ( )22

21 35 −+− xx - ( 1 ) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 34,583333

f( 1μ ) = ( ) ( )22

21 35 −+− xx

= 34

1μ B(x *1 ) = - 1 ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,583333 > ε



43

Langkah 4

Tetapkan 2μ =β 1μ

= (0,1).1 = 0,1

Iterasi 2

Untuk k = 2

Langkah 3


( )21x = 5,180705

( )22x = 2,942802

)( 2min μφ = f(x) + 2μ B(x)

= ( ) ( )22

21 35 −+− xx - (0,1) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,085366

f( 2μ ) = ( ) ( )22

21 35 −+− xx

= 0,035926

2μ B(x *2 ) = - (0,1) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,049440 > ε



44

Langkah 4


= (0,1) (0,1) = 0,01

Iterasi 3

Untuk k = 3

Langkah 3


( )31x = 5,007010

( )32x = 2,987347

)( 3min μφ = f(x) + 3μ B(x)

= ( ) ( )22

21 35 −+− xx - (0,01) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,005499

f( 3μ ) = ( ) ( )22

21 35 −+− xx

= 0,000209

3μ B(x *3 ) = - (0,01) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,005290 > ε



45

Langkah 4


= 0,1 (0,01) = 0,001

Iterasi 4

Untuk k = 4

Langkah 3


( )41x = 5,000751

( )42x = 2,998692

)( 4min μφ = f(x) + 4μ B(x)

= ( ) ( )22

21 35 −+− xx - (0,001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,000535

f( 4μ ) = ( ) ( )22

21 35 −+− xx

= 0,000002

4μ B(x *4 ) = - (0,001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,000533



46

Langkah 4


= 0,1 (0,001) = 0,0001

Iterasi 5

Untuk k = 5

Langkah 3


( )51x = 5,000076

( )52x = 2,999869

)( 5min μφ = f(x) + 5μ B(x)

= ( ) ( )22

21 35 −+− xx - (0,0001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,000053

f( 5μ ) = ( ) ( )22

21 35 −+− xx

= 0,000000

5μ B(x *5 ) = - (0,0001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= - (0,0001) (-0,53333)

= 0,000053



47

Langkah 4


= 0,1 (0,0001) = 0,00001

Iterasi 6

Untuk k = 6

Langkah 3


( )61x = 5,000008

( )62x = 2,999987

)( 6min μφ = f(x) + 6μ B(x)

= ( ) ( )22

21 35 −+− xx - (0,00001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,000005

f( 6μ ) = ( ) ( )22

21 35 −+− xx

= 0,000000

6μ B(x *6 ) = - (0,00001) ⎥

⎦

⎤⎢⎣

⎡−+−

+−+− 42

13

1

2121 xxxx

= 0,000005 < ε

Penyelesaian sudah optimal karena 6μ B(x *6 ) < ε maka langkah dihentikan.


48

Dari permasalahan di atas maka diperoleh penyelesaian dengan *1x = 5,00000 dan

*2x = 2,99999. Pada iterasi ke-6 penyelesaian sudah optimum karena sudah

memenuhi syarat bahwa kμ B(x *k ) < ε .

Berikut akan diberikan penyelesaian dengan menggunakan program

Matlab pada contoh 3.1.2 di atas.

Tabel 3.1.2 Output penyelesaian contoh 3.1.2 dengan Matlab

Masukkan data yang dibutuhkan

x1 = [0 0]

Taksiran awal mu : 1

Toleransi error = 0.00001

Max.iterasi newton = 10

===============================================================

Iterasi Nilai mu x1 x2 f z mu_Bx

===============================================================

0 1.000000 0.000000 0.000000 34.000000 34.583333 0.583333

1 0.100000 5.180705 2.942802 0.035926 0.085366 0.049440

2 0.010000 5.007010 2.987347 0.000209 0.005499 0.005290

3 0.001000 5.000751 2.998692 0.000002 0.000535 0.000533

4 0.000100 5.000076 2.999869 0.000000 0.000053 0.000053

5 0.000010 5.000008 2.999987 0.000000 0.000005 0.000005


49

Metode fungsi penalti interior dapat juga diterapkan ke dalam masalah

optimasi berkendala linear. Berikut contohnya :

Contoh 3.1.3

Selesaikan masalah optimisasi berkendala berikut :

Minimalkan f ( x 1 , x 2 ) = x 1 + 2x 2 +1

Kendala g 1 ( x 1 , x 2 ) = - x 1 + 1 ≤ 0

g 2 ( x 1 , x 2 ) = - x 2 ≤ 0

Penyelesaiannya :

Langkah 1

Misalkan ε = 0,00001

β = 0,1 1μ = 1000

Ditentukan k = 1

Langkah 2



2

1j )(1xjg

−

= ⎥⎦

⎤⎢⎣

⎡−

+− 2

11

1xx


50

Sehingga diperoleh

φ (x,μ ) = f(x) + kμ B(x)

= x 1 +2 x 2 +1 - kμ ⎥⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

Langkah 3

Untuk mencari penyelesaian optimum dari masalah optimisasi tak berkendala,

dibutuhkan penurunan parsial φ terhadap 1x dan 2x :

Turunan parsial φ terhadap x 1 diperoleh :

1x∂∂φ = 1 - 2

1 )1( xk

−μ

= 0

atau (x 1 + 1 ) 2 = kμ

x 1 = kμ2

1

-1 (3.3.1)

Turunan parsialφ terhadap x 2 diperoleh :

2x∂∂φ = 2 - 2

2xkμ = 0

x 22 =

2μ k

atau x 2 = 21)

2μ

( k (3.3.2)

Dari persamaan (3.3.1) dan (3.3.2) diperoleh penyelesaian optimum tak

berkendala dan

x *1 ( kμ ) = kμ

21

-1 dan x *2 ( kμ ) = 2

1)2μ

( k


51

Iterasi 1

Untuk k = 1

x *1 ( kμ ) = kμ

21

-1

= 30,62278

x *2 ( kμ ) = 2

1)2μ

( k

= 22,36068


)(min kμφ = x 1 + 2x 2 +1 - kμ ⎥⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

= ( kμ2

1

+1 ) 21

+2 21)

2μ

( k +1 - kμ [2

12

1

)(1

-2+)μ(-

1

2μ

k

]

= 1,88103

dan f( 1μ ) = ( )21 2+ xx + 1

= { kμ2

1

-1}+2 21)

2μ

( k +1

= 10563,28621

1μ B(x *1 ) = - kμ ⎥

⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

= 74,46310



52

Analog dengan langkah-langkah sebelumnya, titik optimal yang merupakan

penyelesaian optimal didapatkan pada iterasi yang ke-15, yakni

Langkah 4

15μ = 14.μβ

= (0,1).(10 10− ) = 10 11−

Iterasi 15

Untuk k = 15


x *1 ( 15μ ) = 15μ 2

1

-1

= -1,00000

dan x *2 ( 15μ ) = 2

1)2μ

( 15

= 0,00000


)( 15min μφ = x 1 + 2x 2 +1 - 15μ ⎥⎦

⎤⎢⎣

⎡−

+− 2

11

1xx

= 0,00000

dan f( 15μ ) = ( )21 2+ xx + 1

= 0,00000

15μ B(x *15 ) = 0,00000

Karena 15μ B(x *15 ) = 0,00000 < ε maka langkah dihentikan.


53

Maka diperoleh penyelesaian dari masalah di atas dengan x *1 = -1, x *

2 = 0.

Pada iterasi ke-15 penyelesaian sudah optimum karena sudah memenuhi

syarat 15μ B(x *15 ) < ε .

Berikut akan diberikan penyelesaian dengan menggunakan program MATLAB.

Tabel 3.1.3 Output penyelesaian contoh 3.1.3 dengan Matlab

Taksiran awal miu : 1000.00000

==============================================================

Iterasi miu x1 x2 min(miu) f(miu) miu_Bx

==============================================================

1 1000.00000 30.62278 22.36068 1.88103 10563.28621 74.46310

2 100.00000 9.00000 7.07107 1.66667 340.40440 22.47547

3 10.00000 2.16228 2.23607 1.22515 12.77699 6.40927

4 1.00000 0.00000 0.70711 0.66667 1.04044 1.74755

5 0.10000 -0.68377 0.22361 0.27305 0.23415 0.49039

6 0.01000 -0.90000 0.07071 0.09524 0.07104 0.14618

7 0.00100 -0.96838 0.02236 0.03113 0.02237 0.04521

8 0.00010 -0.99000 0.00707 0.00995 0.00707 0.01419

9 0.00001 -0.99684 0.00224 0.00316 0.00224 0.00448

10 0.00000 -0.99900 0.00071 0.00100 0.00071 0.00141

11 0.00000 -0.99968 0.00022 0.00032 0.00022 0.00045

12 0.00000 -0.99990 0.00007 0.00010 0.00007 0.00014

13 0.00000 -0.99997 0.00002 0.00003 0.00002 0.00004

14 0.00000 -0.99999 0.00001 0.00001 0.00001 0.00001

15 0.00000 -1.00000 0.00000 0.00000 0.00000 0.00000

=============================================================

Pada saat iterasi ke -15,miu_Bx<0.00001.

Jadi nilai miu yang meminimalkan min(miu) adalah : x1 = -1.00000 dan x2 = 0.000002


54

D. Konvergensi Metode Fungsi Penalti Interior

Teorema 3.2 Teorema Konvergensi Metode Fungsi Penalti Interior

Jika fungsi φ ( x, kμ ) = f(x) - kμ Σ=

m

j 1 )(1

xjg (3.2.1)

suatu barisan turun terhadap kμ , maka penyelesaian dari masalah minimisasi tak

berkendala akan konvergen ke penyelesaian optimal dari masalah berkendala

Minimumkan f(x)

Kendala g j ( x) ≤ 0

dengan g j ( x) ≤ 0 , j =1,2,Κ , m untuk kμ →0

Bukti :

Jika x * adalah penyelesaian optimum dari masalah berkendala maka akan

dibuktikan bahwa0

lim→kμ

[min φ ( x, kμ ) ] = φ ( x *k , kμ ) = f (x * )

karena f(x) kontinu dan f (x * ) ≤ f(x) untuk setiap titik layak x maka dapat dipilih

titik layak x~ sedemikian hingga f ( x~ ) < f (x * ) + 2ε ,∀ ε >0 (3.2.2)

Perhatikan untuk titik layak x~ didapatkan

φ ( x~ , kμ ) = f( x~ ) - kμ Σ=

m

j 1 )~(1

xjg

= f( x~ ) + kμ Σ=

m

j 1 )~(1xjg

−

f( x~ ) + kμ Σ=

m

j 1 )~(1xjg

−≤ f (x * ) +

2ε


55

Pilih k yang sesuai, misalnya K sedemikian hingga

Kμ Σ=

m

j 1 )~(1xjg

− ≤ 2ε

Jadi Kμ ≤ ∑=

−m

j jg1 )~(1

2

x

ε

(3.2.3)

Dari (3.2.1) didapat f (x * ) ≤ min φ ( x, kμ ) = φ ( x *k , kμ ) (3.2.4)

dimana x *k adalah penyelesaian minimum masalah tak berkendala φ ( x, kμ )

Selanjutnya φ ( x *k , kμ ) ≤ φ ( x *

K , kμ ) (3.2.5)

Karena x *k minimum dari φ ( x, kμ ) dan ada x lain dari x *

k sebagai petunjuk suatu

nilai dari φ ≥ φ ( x *k , kμ ).

Pilih kμ < Kμ dan didapatkan

φ ( x *K , Kμ ) = f (x *

K ) - Kμ Σ=

m

j 1 )(1

Kjg x

> f (x *K ) - kμ Σ

=

m

j 1 )(1

Kjg x

> φ ( x *k , kμ ) (3.2.6)

dimana x *k adalah minimum tak berkendala dari φ ( x, kμ )

Jadi f (x * ) ≤ φ ( x *k , kμ ) ≤ φ ( x *

K , kμ ) < φ ( x *K , Kμ ) (3.2.7)

Tetapi φ ( x *K , Kμ ) ≤ φ ( Kx~ , Kμ ) = f ( x~ ) - Kμ Σ

=

m

j 1 )~(1

xjg (3.2.8)


56

Dari pertidaksamaan (3.2.7) dan (3.2.8) didapatkan

f (x * )≤ φ ( x *k , kμ ) ≤ f ( x~ ) - Kμ Σ

=

m

j 1 )~(1

xjg (3.2.9)

Pertidaksamaan (3.2.2) memberikan - Kμ Σ=

m

j 1 )~(1

xjg <

2ε (3.2.10)

Dengan menggunakan pertidaksamaan (3.2.2) dan (3.2.9) pertidaksamaan (3.2.8)

menjadi f (x * ) ≤ φ ( x *k , kμ ) < f (x * ) +

2ε +

2ε = f (x * ) + ε atau

φ ( x *k , kμ ) - f (x * ) < ε (3.2.11)

Diberikan suatu ε > 0 , ini memungkinkan untuk memilih suatu nilai k supaya

memenuhi pertidaksamaan (3.2.10)

Untuk k→ ∞ dan kμ → 0 didapatkan 0

lim→kμ

φ ( x *k , kμ ) = )( ∗xf

∴Terbukti bahwa 0

lim→kμ

[min φ ( x, kμ ) ] = φ ( x *k , kμ ) = f (x * )


57

BAB IV

PENUTUP

A. Kesimpulan

Metode fungsi penalti interior merupakan metode yang digunakan untuk

mengubah masalah optimisasi berkendala nonlinear menjadi masalah optimisasi

tak berkendala, yakni membentuk fungsi ( )kφ μ,x dari masalah optimisasi dasar

ditambah dengan fungsi kendala-kendalanya dikalikan dengan parameter penalti.

Karena masalah optimisasi berkendala menjadi tak berkendala maka masalah

tersebut dapat diselesaikan menggunakan metode optimisasi tak berkendala

nonlinear. Salah satunya adalah metode newton.

Pencarian penyelesaian optimal yaitu dengan menemukan titik optimal

yang dimulai dari daerah layak dan konvergen ke masalah optimisasi dasar

berkendala nonlinear, artinya bahwa nilai dari

∗x

( )kφ μ,x mendekati nilai saat

dengan .

)(xf

0→μ k ∞→k

Syarat-syarat dalam menggunakan metode fungsi penalti interior :

1. Titik awal x 1 harus berada di dalam daerah layak

2. harus turun dengan aturan kμ kμ 1+μ≥ k dan kk βμ=μ +1

3. Fungsi diferensiabel )(xf

Kelebihan dari metode fungsi penalti interior ini adalah titik awalnya

berada dalam daerah layak sehingga pencarian nilai optimum akan lebih

mudah karena berada dalam daerah layak

∗x


58

Kekurangan dari metode fungsi penalti interior ini adalah

penghitungannya akan sulit jika nilai kμ mengecil. Dalam kasus tertentu titik

awal tidak diperlukan sehingga tidak sesuai dengan algoritma metode fungsi

penalti interior.

B. Saran

1. Metode tidak langsung yang lain untuk menyelesaikan masalah program

optimasi nonlinear berkendala yang dapat digunakan, contohnya Transformasi

Variabel

2. Selain metode Newton, masih banyak metode yang digunakan dalam

menyelesaikan masalah program optimasi nonlinear tak berkendala. Salah

satunya dengan metode Steepest Descent.

3. Masih banyak terdapat metode optimisasi yang dapat digunakan untuk

menyelesaikan sistem persamaan nonlinear baik dengan metode langsung

maupun metode tak langsung.


59

DAFTAR PUSTAKA

Anton, Howard. (1988). Aljabar Linear Elementer (Terjemahan). Edisi kelima.

Jakarta : Erlangga.

Bazaraa M, Sherali H, Shetty C. (1993). Nonlinear Programming, Theory and

Algorithms. Second Edition. Singapore : John Wiley & Sons, Inc.

Purcell, Edwin J. (1988). Kalkulus dan Geometri Analitis (Terjemahan). Edisi

ketiga : Jilid II. Jakarta : Erlangga.

Rao S S. (1984). Optimization Theory and Application. Second Edition. India :

Wiley Eastern Limited.

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

USD.


Lampiran 1 60

Listing Program :

miu = input('Taksiran awal miu : ');

n = input('Iterasi maksimum : ');

beta = 0.1;

k=1;

e = 0.00001;

miu = 1000;

clc;

fprintf('Taksiran awal miu : %10.5f\n',miu);

fprintf('\n CONTOH METODE FUNGSI PENALTI INTERIOR \n\n');

fprintf('===================================================================== \n');

fprintf(' Iterasi miu x1 x2 min(miu) f(miu) miu_Bx \n');

fprintf('===================================================================== \n');

while k <= n

x1 = power( (power(miu,0.5)+1), 0.5 );

x2 = power(miu,0.5);

miu_Bx = power(miu,0.5) - ( 1 / ( (1/miu) - power ( ( (1 / power(miu, 3/2)) + ( 1 / power(miu, 2) ) ), 0.5 )));

min_miu_depan = ( (1/3) * power((x1 + 1), 3) ) + 2*x2;

min_miu_blkng = 1 / ( (1/miu) - power ( ( (1 / power(miu, 3/2)) + ( 1 / power(miu, 2) ) ), 0.5 ) );

min_miu = min_miu_depan - min_miu_blkng;

f_miu = ( (1/3) * power((x1 + 1), 3) ) + x2;

fprintf('%3d %10.5f %8.5f %8.5f %9.5f %9.5f %9.5f\n', k,miu,x1,x2,min_miu,f_miu,miu_Bx);

if miu_Bx < e

break

end

k=k+1;

miu = beta * miu;

end

fprintf('============================================================= \n');

fprintf('Pada saat iterasi ke -%d,miu_Bx<%5.5f.\n',k,e);

fprintf('Jadi nilai miu yang meminimalkan min(miu) adalah : x1 x2 =%8.5 f\n',x1,x2);

end


lampiran 2 61

function in1 clc %memasukkan beberapa data seperti x1,tol dan iterasi maksimum. fprintf('Metode Newton\n\n'); fprintf('Masukkan data yang dibutuhkan\n\n'); x=input('x1 = '); mu=input('Taksiran awal mu : '); beta=0.1; e=0.00001; tol=input('Toleransi error = '); N=input('Max.iterasi newton = '); k=1; x1=x(1);x2=x(2); f=(x1-5).^2+(x2-3).^2; z=((x1-5).^2+(x2-3).^2)-(mu/(-x1+x2-3))-(mu/(-x1+2*x2-4)); fprintf('=============================================================\n'); fprintf(' Iterasi Nilai mu x1 x2 f z mu_Bx\n'); fprintf('=============================================================\n'); tic while k <= N x1=x(1); x2=x(2); f1=2*(x1-5)-((mu)/((-x1+x2-3).^2))-(mu/(-x1+2*x2-4).^2); f2=(2*(x2-3))+((mu)/((-x1+x2-3).^2))+(2*mu/(-x1+2*x2-4).^2); fx=[f1;f2]; j11=2+((2*mu*(-x1+x2-3))/((-x1+x2-3).^4))-(2*mu*(-x1+2*x2-4)/(-x1+2*x2-4).^4); j12=-((2*mu*(-x1+x2-3))/((-x1+x2-3).^4))+(4*mu*(-x1+2*x2-4)/(-x1+2*x2-4).^4); j21=((2*mu*(-x1+x2-3))/((-x1+x2-3).^4))+(4*mu*(-x1+2*x2-4)/(-x1+2*x2-4).^4); j22=2-((2*mu*(-x1+x2-3))/((-x1+x2-3).^4))-(8*mu*(-x1+2*x2-4)/(-x1+2*x2-4).^4); jx=[j11 j12;j21 j22]; %j(ik)=turunan fungsi ke-i terhadap variabel ke-k y=-inv(jx)*fx; f=(x1-5).^2+(x2-3).^2; z=((x1-5).^2+(x2-3).^2)-(mu/(-x1+x2-3))-(mu/(-x1+2*x2-4)); mu_Bx=-mu*((1/(-x1+x2-3))+(1/(-x1+2*x2-4))); fprintf('\n%4.0f %12f %12f %12f %12f %12f %12f',k-1,mu,x,f,z,mu_Bx); if norm(y)<tol %fprintf('\n%4.0f %12f %12f %12f %12f %12f',k-1,mu,x,f,z,mu_Bx); break end if mu_Bx<e break end %mengecek apakah iterasi akan berhenti atau dilanjutkan.


lampiran 2 62

x=x+y'; %fprintf('\n%4.0f %12f %12f %12f %12f %12f',k-1,mu,x,f,z) k=k+1; mu=beta*mu end toc if k>=N fprintf('\nIterasi Maksimum Terlewati'); %pemberitahuan bahwa iterasi maksimum sudah terlampaui. end


Lampiran 3 63

function contoh3 clc %memasukkan beberapa data seperti x1,tol dan iterasi maksimum. miu = input('Taksiran awal miu : '); n = input('Iterasi maksimum : '); beta = 0.1; k=1; e = 0.00001; clc; fprintf('Taksiran awal miu : %10.5f\n',miu); fprintf('\n CONTOH METODE FUNGSI PENALTI INTERIOR \n\n'); fprintf('======================================================= \n'); fprintf(' Iterasi miu x1 x2 min(miu) f(miu) miu_Bx \n'); fprintf('=======================================================\n'); while k <= n x1 = sqrt(miu)-1; x2 = sqrt(miu/2); miu_Bx=-miu*((1/(-(sqrt(miu)+2)))-(1/(sqrt(miu/2)))); min_miu_depan = (sqrt(miu)-1)+2*(sqrt(miu/2))+1; min_miu_blkng =miu_Bx; min_miu = min_miu_depan - min_miu_blkng; f_miu = ( (1/3) * power((x1 + 1), 3) ) + x2; fprintf('%3d %10.5f %8.5f %8.5f %9.5f %9.5f %9.5f\n', k,miu,x1,x2,min_miu,f_miu,miu_Bx); if miu_Bx < e break end k=k+1; miu = beta * miu; end fprintf('====================================================== \n'); fprintf('Pada saat iterasi ke -%d,miu_Bx<%5.5f.\n',k,e); fprintf(' Jadi nilai miu yang meminimalkan min(miu) adalah : x1 = %8.5f dan x2 = %12f\n',x1,x2); end


plagiat merupakan tindakan tidak terpuji … · satu syarat memperoleh gelar sarjana sains program...

Documents