PERANAN FUNGSI OBJEKTIF LINIER DALAM METODE BARRIER
TESIS
Oleh DAME IFA SIHOMBING 117021023/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI MAGISTER MATEMATIKA UNIVERSITAS SUMATERA UTARA 2013
Universitas Sumatera Utara
PERANAN FUNGSI OBJEKTIF LINIER DALAM METODE BARRIER
TESIS
Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh DAME IFA SIHOMBING 117021023/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI MAGISTER MATEMATIKA UNIVERSITAS SUMATERA UTARA 2013
2 Universitas Sumatera Utara
Judul Penelitian
: PERANAN FUNGSI OBJEKTIF LINIER DALAM METODE BARRIER
Nama Mahasiswa
:Dame Ifa Sihombing
NIM
:117021023
Program Studi
:Magister Matematika
Menyetujui, Komisi Pembimbing
( Prof. Dr. Herman Mawengkang ) Pembimbing I
Ketua Program Studi
(Prof. Dr. Herman Mawengkang ) Ketua Program Studi
( Prof.Dr. Opim Salim S.,M.Sc) Pembimbing II
Dekan Fakultas MIPA
( Dr. Sutarman M.Sc) Dekan
Universitas Sumatera Utara
Telah diuji pada Tanggal 5 Juni 2013
PANITIA PENGUJI TESIS Ketua
: Prof.Herman Mawengkang
Anggota
: Prof.Dr.Opim Salim S.,M.Sc Prof.Dr.Saib Suwilo,M.Sc Prof.Tulus M.Si
Universitas Sumatera Utara
ABSTRAK Metode Newton/log barrier dalam persoalan optimisasi non linier dengan fungsi objektif yang non linier, pengurangan parameter barrier sering tidak baik ditampilkan dalam mendapatkan solusi optimal. Dalam tesis ini akan dianalisa perilaku asimptotik dari metode logaritma barrier dengan kendala pertidaksamaan mengambil langkah yang efektif dari arah Newton setelah mereduksi paramater barrier dengan memanfaatkan fungsi objektif linier yang dapat menghasilkan konvergensi superlinier . Kata Kunci:Fungsi logaritma barrier, Metode Newton, Konvergensi Superlinier.
i Universitas Sumatera Utara
ABSTRACT Newton/log barrier method for non linear programming optimization,when the objective function is non linear, on reduction barrier parameter often performs more and more poorly. This thesis will analyze the asymptotic behavior of the Newton/log barrier with inequality constrained an effective step can be taken along Newton direction to get superlinear convergence with the case of a linear objective. Key words :Logarithmic barrier function, Newtons method, Superlinear convergence
ii Universitas Sumatera Utara
KATA PENGANTAR
Dengan kerendahan hati dan penuh ucapan syukur kepada Tuhan Yang Maha Esa untuk segala berkat dan penyertaanNya penulis dapat menyelesaikan tesis ini dengan judul : PERANAN FUNGSI OBJEKTIF LINIER DALAM METODE BARRIER. Tesis ini merupakan salah satu syarat untuk menyelesaikan studi pada Program Studi Magister Matematika Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada :
Prof. Dr.dr.Syahril Pasaribu, D.T.M.& H,M.Sc(C.T.M).Sp.A.(K) selaku Rektor Universitas Utara.
Dr.Sutarman,M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Universitas Sumatera Utara.
Prof.Herman Mawengkang Ketua Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara dan juga selaku pembimbing utama penyelesaian tesis ini.
Prof.Dr.Saib Suwilo,M.Sc selaku Sekretaris Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara dan juga selaku pembanding dalam penyelesaian tesis ini.
iii Universitas Sumatera Utara
Seluruh rekan-rekan Mahasiswa angkatan 2010/2011 Program Studi Magister Matematika Universitas Sumatera Utara yang telah memberikan bantuan moril dan dorongan kepada penulis dan tidak lupa kepada Saudari Misiani,S.Si selaku staf Administrasi Program Studi Magister Matematika Universitas Sumatera Utara yang telah banyak memberikan pelayanan yang baik kepada penulis selama mengikuti perkuliahan.
Secara khusus penulis menyampaikan terimakasih yang sebesar-besarnya untuk keluarga tercinta, Ayahanda Jaspiun Sihombing dan Ibunda Rasima Saragih, serta adik-adik dan sahabat terkasih Yani, Adi, Ita, Pran, Enita yang senantiasa memberikan dukungan dan mendoakan penulis dalam menyelesaikan pendidikan ini serta seluruh pihak yang tidak dapat disebutkan satu persatu, penulis berterimakasih atas dukungan doa dan semangat yang diberikan, semoga Tuhan yang Maha Esa membalas segala kebaikan yang telah diberikan. Penulis menyadari tesis ini masih jauh dari sempurna, namun demikian penulis berharap semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya.
Medan, 2013 Penulis,
Dame Ifa Sihombing
iv Universitas Sumatera Utara
RIWAYAT HIDUP
Dame Ifa Sihombing dilahirkan di Marjandi pada tanggal 16 Mei 1986 dari pasangan Bapak Jaspiun Sihombing dan Ibu Rasima Saragih dan merupakan anak pertama dari lima bersaudara. Penulis menamatkan pendidikan Sekolah Dasar Negeri 091292 Simpang Raya tahun 1998, Sekolah Menengah Pertama (SMP) RK. Bintang Timur Pematangsiantar 2001, Sekolah Menengah Atas (SMA) Negeri 1 Pematangsiantar tahun 2004. Pada tahun 2004 memasuki Perguruan Tinggi Universitas Sumatera Utara, Fakultas Matematika dan Ilmu Pengetahuan Alam, Program Studi Statistika pada Jenjang Diploma-3 dan lulus tahun 2007. Melanjutkan pendidikan pada Program Studi Matematika Ekstensi bidang Statistika Universitas Sumatera Utara dan lulus tahun 2009. Kemudian pada tahun 2011 penulis melanjutkan pendidikan pada Program Studi Magister Matematika Universitas Sumatera Utara.
vi Universitas Sumatera Utara
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
3
1.4 Manfaat Penelitian . . . . . . . . . . . . . . . . . . . .
3
1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . .
4
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .
5
2.1 Pemrograman Nonlinier . . . . . . . . . . . . . . . . . .
5
2.2 Optimisasi Nonlinier dengan kendala pertidaksamaan
. . .
7
. . . . . . . .
8
2.2.2 Konveksitas dan Kualifikasi kendala . . . . . . . . .
10
2.3 Metode Titik Interior . . . . . . . . . . . . . . . . . . .
11
BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .
14
3.1 Metode Barrier . . . . . . . . . . . . . . . . . . . . . .
14
3.2 Fungsi Logaritma Barrier . . . . . . . . . . . . . . . . .
14
3.3 Metode Newton dan Fungsi Barrier . . . . . . . . . . . .
15
2.2.1 Kondisi Karush Kuhn Tucker (KKT)
iii Universitas Sumatera Utara
3.4 Kondisi Optimal pada Persoalan Nonlinier . . . . . . . . .
16
3.5 Pecarian Arah Newton
. . . . . . . . . . . . . . . . . .
18
BAB 4 PERANAN FUNGSI OBJEKTIF LINIER . . . . . . . . . . .
22
4.1 Konvergensi Metode Newton dengan unit langkah terhadap log-barrier minimizer . . . . . . . . . . . . . . . . . . .
22
4.2 Konsistensi Strategi Newton Line Search
. . . . . . . . .
28
4.3 Kecepatan Konvergensi pada saat Fungsi Objektif Linier . .
29
4.4 Membatasi Perilaku arah Newton . . . . . . . . . . . . .
32
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
44
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
45
iv Universitas Sumatera Utara
