ANALISIS KOMPLEKSITAS MASALAH OPTIMASI LINEAR MENGGUNAKAN METODE INTERIOR PRIMAL-DUAL DENGAN LANGKAH FULL-NEWTON
RINI MAEDIANENGSIH
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
ABSTRAK RINI MAEDIANENGSIH. Analisis Kompleksitas Masalah Optimasi Linear Menggunakan Metode Interior Primal-Dual dengan Langkah Full-Newton. Dibimbing oleh BIB PARUHUM SILALAHI dan MUHAMMAD ILYAS. Metode interior primal-dual dengan langkah full-Newton adalah salah satu metode untuk menyelesaikan masalah optimasi linear. Metode ini dirancang sedemikian rupa sehingga solusi optimal diperoleh di dalam interior dari domain. Metode ini memiliki kompleksitas polinomial. Karya ilmiah ini membahas dan menganalisis kompleksitas algoritme masalah optimasi linear menggunakan metode interior primal-dual langkah full-Newton. Beberapa masalah optimasi linear diselesaikan dengan metode ini untuk melihat kesesuainnya dengan kompleksitas algoritme. Dari studi kasus yang telah dilakukan, dapat disimpulkan bahwa banyaknya iterasi sesuai dengan kompleksitas algoritme. Kata Kunci: metode interior, langkah full-Newton, kompleksitas algoritme.
ABSTRACT RINI MAEDIANENGSIH. Complexity Analysis of Linear Optimization Problems Using PrimalDual Interior Methods with Full-Newton Step. Supervised by BIB PARUHUM SILALAHI and MUHAMMAD ILYAS. Primal-dual interior method with full-Newton step is a method for solving linear optimization problems. This method is designed in such a way that an optimal solution is obtained an interior of the domain. It has polynomial complexity. This paper discusses and analyzes the complexity of linear optimization problems using primal-dual interior method with full-Newton steps. From the case studies that have been conducted, can be concluded that the number of iterations is in accordance with the complexity of the algorithm. Keywords: interior method, full-Newton step, complexity of the algorithm.
ANALISIS KOMPLEKSITAS MASALAH OPTIMASI LINEAR MENGGUNAKAN METODE INTERIOR PRIMALDUAL DENGAN LANGKAH FULL-NEWTON
RINI MAEDIANENGSIH
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
Judul Sripsi Nama NIM
: Analisis Kompleksitas Masalah Optimasi Linear Menggunakan Metode Interior Primal-Dual dengan Langkah Full-Newton. : RINI MAEDIANENGSIH : G54080044
Menyetujui, Pembimbing I
Pembimbing II
Dr. Ir. Bib Paruhum Silalahi, M.Kom. NIP. 19670101 199203 1 004
Muhammad Ilyas, S.Si, M.Sc.
Mengetahui: Ketua Departemen Matematika
Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004
Tanggal Lulus :
KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa atas segala rahmat dan karunia-Nya serta shalawat dan salam kepada Nabi Muhammad SAW sehingga karya ilmiah ini berhasil diselesaikan. Penyusunan karya ilmiah ini juga tidak lepas dari bantuan berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada: 1. Dr. Ir. Bib Paruhum Silalahi, M.Kom, selaku dosen pembimbing I (terima kasih atas semua ilmu, kesabaran, motivasi, dan bantuannya selama penulisan skripsi ini). 2. Muhammad Ilyas, S.Si, M.Sc, selaku dosen pembimbing II (terima kasih atas semua ilmu, saran dan motivasinya). 3. Dr. Ir. I Gusti Putu Purnaba, DEA, selaku dosen penguji (terima kasih atas semua ilmu dan sarannya). 4. Semua dosen Departemen Matematika (terima kasih atas semua ilmu yang telah diberikan). 5. Staf Departemen Matematika: Pak Yono, Bu Ade, Mas Heri, Bu Susi dan Mas Deni (terima kasih atas bantuan dan motivasinya). 6. Keluargaku tercinta: Bapak, Mamah, adikku Rena dan Adelia (terima kasih atas doa, dukungan, kesabaran, kepercayaan dan kasih sayangnya). 7. Teman-teman kosan: Yuli, Sri, Davi, Chacha, Kak Nurul, Kak Tanti, Kak Runi (terima kasih atas bantuan, doa dan dukungannya). 8. Teman-teman satu bimbingan: Haya, Bram, Irwan (terima kasih atas bantuan dan dukungannya). 9. Sahabat terdekat: Roni, Nova, Dina, Aisyah (terima kasih atas semangat, doa dan dukungannya). 10. Teman-teman Math 45: Herlan, Prama, Arbi, Dini, Rahma, Mya, Pipin, Tiwi, Mega, Fuka, Annisa, Ana, Dimas, Fina dan yang lainnya (terima kasih atas dukungan, bantuan dan doanya). 11. Adik-adik Math 46: Sefira, Fitria, Anne, Mirna, Andri dan yang lainnya (terima kasih atas dukungan, bantuan, dan doanya). Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, April 2013
Rini Maedianengsih
RIWAYAT HIDUP Penulis dilahirkan di Ciamis pada tanggal 5 Februari 1990 sebagai anak pertama dari tiga bersaudara. Anak dari pasangan Muhaemin dan Eros Saripah. Pada tahun 1996 penulis menyelesaikan pendidikan di TK LKMD Kuningan. Tahun 2002 penulis lulus dari SDN Tangkolo 1, Kuningan. Tahun 2005 penulis lulus dari SLTPN 3 Rancah, Ciamis. Tahun 2008 penulis lulus dari SMAN 2 Ciamis dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Ujian Saringan Masuk IPB (USMI). Penulis memilih Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi anggota Biro Kewirausahaan GUMATIKA IPB pada tahun 2009-2010. Kegiatan lain yang pernah diikuti oleh penulis yaitu sebagai pengajar Matematika untuk tingkat SMP di sebuah bimbingan belajar pada tahun 2012.
DAFTAR ISI Halaman DAFTAR TABEL ...........................................................................................................
ix
DAFTAR LAMPIRAN ....................................................................................................
ix
I. PENDAHULUAN ...................................................................................................... 1.1 Latar Belakang ................................................................................................... 1.2 Tujuan ............................................................................................................... 1.3 Sistematika Penulisan .........................................................................................
1 1 1 1
II. LANDASAN TEORI ................................................................................................. 2.1 Sistem Persamaan Linear.................................................................................... 2.2 Matriks dan Vektor ............................................................................................ 2.3 Optimasi Linear dan Dualitas ............................................................................. 2.4 Metode Newton ................................................................................................. 2.5 Kompleksitas .....................................................................................................
2 2 2 3 3 4
III. HASIL DAN PEMBAHASAN ................................................................................... 3.1 Kondisi Optimal ................................................................................................. 3.2 Central Path....................................................................................................... 3.3 Langkah Full-Newton ......................................................................................... 3.4 Ukuran Kedekatan .............................................................................................. 3.5 Kompleksitas Algoritme .....................................................................................
5 5 5 5 6 7
IV. STUDI KASUS ..........................................................................................................
11
V. SIMPULAN DAN SARAN ........................................................................................ 5.1 Simpulan............................................................................................................ 5.2 Saran..................................................................................................................
16 16 16
DAFTAR PUSTAKA ......................................................................................................
16
LAMPIRAN ....................................................................................................................
17
viii
DAFTAR TABEL Halaman 1 Hasil Iterasi pada Saat ๐ 2 Hasil Iterasi pada Saat ๐ 3 Hasil Iterasi pada Saat ๐ 4 Hasil Iterasi pada Saat ๐ 5 Hasil Iterasi pada Saat ๐ 6 Hasil Iterasi pada Saat ๐
= 4, ๐ = 2, ๐ = 10, dan ๐ = 10โ5 ......................................... = 4, ๐ = 2, ๐ = 100, dan ๐ = 10โ5 ...................................... = 4, ๐ = 2, ๐ = 10, dan ๐ = 10โ3 ........................................ = 6, ๐ = 3 ๐ = 10, dan ๐ = 10โ5 ......................................... = 6, ๐ = 3 ๐ = 100, dan ๐ = 10โ5 ....................................... = 6, ๐ = 3 ๐ = 10, dan ๐ = 10โ3 .........................................
11 12 12 13 14 15
DAFTAR LAMPIRAN Halaman 1 Program MATLAB untuk Fungsi Langkah Newton ....................................................... 2 Program MATLAB untuk Kasus Dua Dimensi (๐ = 4) ................................................. 3 Program MATLAB untuk Kasus Tiga Dimensi (๐ = 6).................................................
18 19 21
ix
I PENDAHULUAN 1.1 Latar Belakang Pengoptimuman merupakan salah satu cabang matematika terapan yang mempelajari masalah meminimumkan atau memaksimumkan. Dalam kehidupan sehari-hari banyak permasalahan yang memerlukan optimasi. Optimasi digunakan secara luas hampir di setiap aspek kehidupan, seperti di bidang teknik, ekonomi, manajemen dan industri. Banyak penelitian yang telah menghasilkan teknologi baru, dan metode baru dalam optimasi. Pada tahun 1947, Dantzig mengajukan penggunaan metode simpleks untuk memecahkan masalah optimasi linear (OL). Daerah fisibel dari masalah optimasi linear adalah suatu polihedron. Metode simpleks bergerak dari verteks ke verteks dari polihedron untuk memperoleh solusi optimal. Metode ini dirancang sehingga nilai dari fungsi tujuan berubah secara monoton ke arah nilai optimal. Penemuan Dantzig telah menginspirasi begitu banyak penelitian dalam matematika. Terdapat banyak varian dari metode simpleks, yang dibedakan oleh aturan untuk memilih verteks yang akan dikunjungi (dikenal dengan aturan pivot) (Silalahi 2011). Pada tahun 1972, Klee dan Minty memberikan suatu masalah dengan metode simpleks memerlukan 2๐ โ 1 iterasi untuk menyelesaikan suatu masalah optimasi linear dengan 2n pertidaksamaan. Klee-Minty juga menunjukkan bahwa metode simpleks memerlukan waktu eksponensial untuk menyelesaikan masalah optimasi linear. Contoh yang diberikan oleh Klee dan Minty kemudian dikenal dengan problem Klee-Minty (KM), yaitu min ๐ฆ๐ kendala ๐๐ฆ๐โ1 โค ๐ฆ๐ โค 1 โ ๐๐ฆ๐โ1 , k = 1,...,m 1 dengan ๐ฆ0 = 0, ๏ฒ ๏ฅ (0,2) (Silalahi 2011). Pada tahun 1979, Khachiyan mengusulkan metode elipsoid untuk memecahkan permasalahan optimasi linear secara polinomial. Walaupun metode elipsoid ini memiliki kompleksitas polinomial, namun dalam penerapan secara komputasional metode ini tidak efisien (Silalahi 2011). Pada tahun 1984, Karmarkar mengembangkan metode interior dan mempresentasikan suatu algoritme (algoritme Karmarkar) yang memiliki kompleksitas polinomial yang lebih baik dari metode
elipsoid. Sesuai dengan namanya, metode ini akan melalui daerah dalam (interior) dari daerah solusi yang mungkin (feasible) dalam mencari solusi optimal. Hal ini berlawanan dengan metode simpleks yang bergerak dari verteks ke verteks (Silalahi 2011). Dalam perkembangannya, metode ini telah dikembangkan dengan beberapa pendekatan. Secara umum metode ini dapat dikelompokkan menjadi tiga kategori, yaitu metode affine scaling, metode potential reduction (barrier) dan metode central trajectory (path-following). Selain itu, persoalan yang bisa diselesaikan dengan metode ini juga mengalami perkembangan. Awalnya metode ini dikembangkan untuk pemrograman linear dan sekarang sudah dikembangkan untuk masalah-masalah yang lain, seperti pemrograman integer, pemrograman jaringan, pemrograman semidefinit (Mitchell 1998). Dalam karya ilmiah ini akan digunakan metode interior primal-dual dengan langkah full-Newton dalam memecahkan masalah Klee-Minty tersebut. Selanjutnya akan dilakukan analisis kompleksitas algoritme dari masalah Klee-Minty dan menyelesaikan beberapa masalah optimasi linear untuk melihat kesesuaiannya dengan kompleksitas algoritme dengan bantuan software MATLAB R2008b. 1.2 Tujuan Berdasarkan latar belakang di atas, maka tujuan karya ilmiah ini adalah (i) Membahas metode interior primal-dual dengan langkah full-Newton. (ii) Menganalisis kompleksitas algoritme interior primal-dual dengan langkah full-Newton. (iii) Menyelesaikan beberapa masalah KleeMinty dan melihat kesesuaiannya dengan kompleksitas algoritme. 1.3 Sistematika Penulisan Karya ilmiah ini terdiri dari lima bab. Bab pertama merupakan pendahuluan yang berisi latar belakang dan tujuan penulisan. Bab kedua berupa landasan teori yang berisi konsep. Bab ketiga berisi penjelasan metode interior primal-dual dengan langkah fullNewton. Bab keempat merupakan studi kasus dan bab kelima berisi kesimpulan dan saran.
2
II LANDASAN TEORI 2.1 Sistem Persamaan Linear Definisi 1 (Sistem Persamaan Linear) Suatu persamaan linear dalam n peubah (variable) adalah persamaan dengan bentuk a1x1 + a2x2 + . . . + anxn = b di mana a1, a2, . . . , an dan b adalah bilanganbilangan real dan x1, x2, . . . ,xn adalah peubah. Dengan demikian maka suatu sistem linear dari m persamaan dalam n peubah adalah satu sistem berbentuk: a11x1 + a12x2 + . . . + a1nxn = b1 a21x1 + a22x2 + . . . + a2nxn = b2 . . . am1x1 + am2x2 + . . . + amnxn = bm dengan aij dan bi semuanya adalah bilanganbilangan real. Kita akan menyebut sistemsistem di atas sebagai sistem linear ๐ ร ๐. (Leon 2001)
dan notasi diag(x) adalah matriks diagonal dengan unsur diagonal utama ialah vektor x ๐ฅ1 0 โฏ 0 0 ๐ฅ2 โฏ 0 ๐ฟ = ๐๐๐๐ ๐ฑ = โฎ โฎ โฑ โฎ 0 0 โฏ ๐ฅ๐ ๐ฆ1 0 ๐ = ๐๐๐๐ ๐ฒ = โฎ 0
๐ฅ1 ๐ฅ2 โฎ ๐ฑ ๐ฅi ๐ฅ๐ = = ๐ 1 ๐ฌ ๐ ๐ ๐ 2 โฎ ๐ ๐
Definisi 2 (Ortogonal) Vektor โ vektor x dan y di dalam โ2 (atau โ3) dikatakan ortogonal jika xTy = 0. (Leon 2001) Definisi 3 (Hasil Kali Skalar di โ๐ ) Misalkan x,y โ โ๐ dengan ๐ฆ1 ๐ฆ2 . . . ๐ฆ๐
maka hasil kali skalar dari x dan y adalah ๐ฑ T ๐ฒ = ๐ฅ1 ๐ฆ1 + ๐ฅ2 ๐ฆ2 + . . . + ๐ฅ๐ ๐ฆ๐ (Leon 2001)
๐ฑ=
๐ฆ1 ๐ฅ1 ๐ฅ2 ๐ฆ2 x= โฎ , y= โฎ ๐ฅ๐ ๐ฆ๐
๐ฅ1 ๐ฅ2 ๐ฅi = โฎ ๐ฅ๐ (Roos et al. 2006)
Definisi 5 (Norm dari Suatu Vektor di โ๐ ) Misalkan x โ โ๐ dengan ๐ฅ1 ๐ฅ2 x= โฎ , ๐ฅ๐
Definisi 4 (Hadamard product) Misalkan vektor x, y โ โ๐ , X, Y โ โ๐ร๐ dengan n menyatakan banyak baris dan banyak kolom pada matriks. Vektor x dan y didefinisikan sebagai berikut
โฏ 0 โฏ 0 โฑ โฎ โฏ ๐ฆ๐
maka Hadamard product dari x dan y adalah xy = Xy = Yx = yx Dengan kata lain, Hadamard product adalah perkalian antara unsur dengan unsur yang seletak (componentwise) dari dua buah vektor yang berukuran sama. Componentwise juga berlaku pada operasi pembagian dan operasi akar untuk vektor x dan s sebagai berikut
2.2 Matriks dan Vektor
๐ฅ1 ๐ฅ2 . x= . , y= . ๐ฅ๐
0 ๐ฆ2 โฎ 0
maka norm dari vektor x di โ๐ adalah ๐ฑ =
๐ฑ๐ ๐ฑ =
๐ฅ12 + ๐ฅ22 + โฏ + ๐ฅ๐2 (Leon 2001)
3
Definisi 6 (Ruang Baris dan Ruang Kolom) Jika A adalah matriks ๐ ร ๐, maka ruang bagian dari โ1ร๐ yang direntang oleh vektorvektor baris dari A disebut ruang baris dari A. Ruang bagian dari โ๐ yang direntang oleh vektor-vektor kolom dari A disebut ruang kolom dari A. (Leon 2001) Definisi 7 (Ruang Nol) Misalkan A adalah matriks ๐ ร ๐. Misalkan N(A) menyatakan himpunan semua penyelesaian dari sistem homogen ๐๐ฑ = ๐. Jadi ๐ ๐ = {๐ฑ โ โ๐ |๐๐ฑ = ๐} Himpunan semua penyelesaian dari sistem homogen ๐๐ฑ = ๐ membentuk ruang bagian dari โ๐ . Ruang bagian N(A) disebut kernel (ruang nol atau nullspace) dari A. (Leon 2001) 2.3 Optimasi Linear dan Dualitas Masalah optimasi linear dalam bentuk standar diberikan sebagai berikut min{๐ T x : Ax = b, x โฅ 0} (P) ๐ ๐ ๐๐ฅ๐ dengan, c, x ๏ฅ โ , b ๏ฅ โ dan A ๏ฅ โ . Masalah (P) disebut masalah primal. Masalah dual dari masalah primal (P) diberikan sebagai berikut max {๐T y : ๐T y + s = c, s โฅ 0 } (D) dengan, s ๏ฅ โ๐ dan y ๏ฅ โ๐ . Masalah (D) disebut masalah dual. Daerah fisibel dari (P) dan (D) masingmasing adalah : ๏ := {x : Ax = b, x โฅ 0} ๏ := {(y,s) : ๐T y + s = c, s โฅ 0} Daerah interior masalah (P) dan (D) didefinisikan sebagai berikut ๏ 0 := {x : Ax = b, x > 0}, ๏0 := {(y,s) : ๐T y + s = c, s > ๐} (Silalahi 2011)
nilai fungsi objektif paling besar. Sedangkan solusi optimal untuk masalah minimisasi adalah suatu titik pada daerah fisibel dengan nilai fungsi objektif paling kecil. (Winston 2004) Proposisi 1 ( Dualitas Lemah) Misalkan x dan s masing-masing fisibel untuk (P) dan (D). Kemudian ๐ T x - ๐T y = ๐ฑ T s โฅ 0. Akibatnya, ๐ T x terbatas di atas untuk nilai optimal dari (D), dan ๐T y terbatas di bawah untuk nilai optimal dari (P). Selain itu, jika kesenjangan dualitas (duality gap) ๐ฑ T s bernilai nol maka x adalah solusi optimal untuk (P) dan (y,s) adalah solusi optimal untuk (D). (Roos et al. 2006)
Bukti :lihat Roos Teorema 1 (Dualitas) Jika (P) dan (D) fisibel maka kedua masalah tersebut mempunyai solusi optimal. Kemudian, x ๏ฅ ๏ dan (y,s) ๏ฅ ๏ adalah solusi optimal jika dan hanya jika ๐ฑ T s = 0. (Roos et al. 2006) Bukti : lihat Roos Definisi 10 (Kendala Redundant) Kendala redundant adalah kendala yang tidak mengubah daerah fisibel dari masalah optimasi linear. (Silalahi 2011) Definisi 11 (Central Path) Suatu kurva yang bergerak dari bagian dalam pada daerah fisibel menuju solusi optimal. (Silalahi 2011) 2.4 Metode Newton
Definisi 8 (Daerah Fisibel) Himpunan titik-titik yang memenuhi semua kendala dan pembatasan tanda pada optimasi linear. (Winston 2004) Definisi 9 (Solusi Optimal) Solusi optimal pada masalah maksimisasi adalah suatu titik pada daerah fisibel dengan
Metode Newton disebut juga metode Newton-Raphson. Metode Newton adalah suatu metode yang digunakan untuk menyelesaikan persamaan taklinear, yang dituliskan dalam bentuk : ๐๐ ๐ฑ = ๐, ๐ = 1,2, โฆ , ๐ ๐ฑ = (๐ฅ1 , ๐ฅ2 , โฆ , ๐ฅ๐ )T . Metode Newton Raphson dapat diturunkan dengan menggunakan orde pertama dari deret
4
Taylor. Sebagai contoh untuk fungsi satu peubah atau ๐ = 1, dan ๐ฑ = ๐ฅ1 โ โ, orde pertama deret Taylor ๐1 (๐ฅ1 ) sebagai berikut ๐1 ๐ฅ1 โ ๐ ๐ฅ1.0 + ๐ โฒ ๐ฅ1.0 ๐ฅ1 โ ๐ฅ1.0 = ๐ฃ(๐ฅ1 ) dengan ๐ฅ1.0 adalah hampiran awal (Munir 2003). Dengan menggunakan metode Newton, fungsi taklinear dapat diubah menjadi fungsi
linear. Untuk mencari solusi persamaan ๐1 ๐ฅ1 = 0, metode Newton melakukan pendekatan dengan cara mencari solusi ๐ฃ ๐ฅ1 = 0, dengan ๐ฃ adalah fungsi linear. Selain itu, untuk fungsi dua peubah atau ๐ = 2, dan ๐ฑ = (๐ฅ1 , ๐ฅ๐ )T โ โ. Deret Taylor orde pertama dapat dituliskan untuk masingmasing persamaan sebagai berikut
๐1 ๐ฅ1 , ๐ฅ2 โ ๐1 ๐ฅ1.0 , ๐ฅ2.0 + ๐ฅ1 โ ๐ฅ1.0
๐๐1 ๐ฅ1.0 , ๐ฅ2.0 ๐๐1 ๐ฅ1.0 , ๐ฅ2.0 + ๐ฅ2 โ ๐ฅ2.0 ๐๐ฅ1 ๐๐ฅ2
๐2 ๐ฅ1 , ๐ฅ2 โ ๐2 ๐ฅ1.0 , ๐ฅ2.0 + ๐ฅ1 โ ๐ฅ1.0
๐๐2 ๐ฅ1.0 , ๐ฅ2.0 ๐๐2 ๐ฅ1.0 , ๐ฅ2.0 + ๐ฅ2 โ ๐ฅ2.0 ๐๐ฅ1 ๐๐ฅ2
dengan ๐ฅ1.0 dan ๐ฅ2.0 adalah hampiran awal (Munir 2003). Contoh 1 Diketahui fungsi taklinear f ๐ฅ1 = ๐ ๐ฅ 1 โ 5๐ฅ1 dengan hampiran awal ๐ฅ1.0 = 0. ๐1 ๐ฅ1 โ ๐ ๐ฅ1.0 + ๐ โฒ ๐ฅ1.0 ๐ฅ1 โ ๐ฅ1.0 ๐1 ๐ฅ1 โ ๐ฃ ๐ฅ1 = 0 ๐ฃ ๐ฅ1 = ๐ 0 + ๐ โฒ 0 ๐ฅ1 โ 0 = ๐ 0 โ 5 0 + ๐ 0 โ 5 ๐ฅ1 โ 0 = 1 + โ4 ๐ฅ1 Pada saat ๐ฃ ๐ฅ1 = 0 maka 1 + โ4 ๐ฅ1 = 0 ๐ฅ1 = 1 4 Contoh 2 Diketahui fungsi taklinear variabel sebagai berikut
dengan
๐1 ๐ฅ1 , ๐ฅ2 = ๐ฅ1 2 โ ๐ฅ1 ๐ฅ2 + 1 ๐2 (๐ฅ1 , ๐ฅ2 ) = ๐ฅ2 2 โ ๐ฅ1 ๐ฅ2 โ 2
(1) (2)
dengan hampiran awal ๐ฅ1.0 = 0, ๐ฅ2.0 = 1 ๏ท Pelinearan untuk persamaan (1) ๐1 ๐ฅ1 , ๐ฅ2 โ ๐ฃ ๐ฅ1 , ๐ฅ2 = 0 ๐ฅ1 2 โ ๐ฅ1 ๐ฅ2 + 1
= 0
๐ฅ1 โ 0 ๐1 0,1 + โ1 0 ๐ฅ2 โ 1 1 + โ1 ๐ฅ1
= 0
๐ฅ1
= 1
= 0
dua
Jadi, persamaan baru setelah pelinearan adalah โ๐ฅ1 + 1 = 0 ๏ท Pelinearan untuk persamaan (2) ๐2 ๐ฅ1 , ๐ฅ2 โ ๐ฃ ๐ฅ1 , ๐ฅ2 = 0 ๐ฅ2 2 โ ๐ฅ1 ๐ฅ2 โ 2 ๐ฅ1 โ 0 ๐ฅ2 โ 1 โ1 + โ1 ๐ฅ1 + 2 ๐ฅ2 โ 1
๐2 0,1 + โ1 2
โ๐ฅ1 + 2๐ฅ2 โ 3
= 0 = 0 = 0 = 0
Jadi, persamaan baru setelah pelinearan adalah โ๐ฅ1 + 2๐ฅ2 = 3 Solusi dari ๐ฅ1 dan ๐ฅ2 dapat diperoleh dengan mensubstitusikan persamaan (1) ke persamaan (2) sebagai berikut โ 1 + 2๐ฅ2 = 3 2๐ฅ2 = 4 ๐ฅ2 = 2 Jadi, solusi dari ๐ฅ1 dan ๐ฅ2 setelah dilakukan pelinearan adalah ๐ฅ1 = 1dan ๐ฅ2 = 2. 2.5 Kompleksitas Definisi 12 (Kompleksitas) Fungsi kompleksitas waktu ๐(๐) adalah fungsi yang mengukur banyak operasi dalam suatu algoritme yang mempunyai variabel input n. (Grimaldi 2004)
III HASIL DAN PEMBAHASAN y(ยต), dan s(ยต) konvergen ke solusi optimal dari (P) dan (D).
3.1 Kondisi Optimal Berdasarkan teorema dualitas, mencari solusi optimal dari masalah primal (P) dan masalah dual (D) sama halnya dengan menyelesaikan sistem ๐๐ฑ = ๐, ๐ฑ โฅ ๐ (1) ๐๐ ๐ฒ + ๐ฌ = ๐, ๐ฌ โฅ ๐ ๐ฑ๐ฌ = ๐. dengan xs adalah Hadamard product. Sistem (1) merupakan kondisi optimal untuk masalah optimasi linear. Baris pertama merupakan kendala fisibel masalah primal (P) dan baris kedua merupakan kendala fisibel masalah dual (D). Sedangkan baris ketiga disebut dengan kondisi pelengkap.
3.3 Langkah Full-Newton Langkah full-Newton merupakan metode yang dapat digunakan untuk mencari solusi pendekatan sistem (2). Diberikan pasangan fisibel primal-dual (x,(y,s)), kita ingin mencari โ๐ฑ, โ๐ฒ, dan โ๐ฌ sehingga ๐ฑ + = ๐ฑ + โ๐ฑ, ๐ฒ + = ๐ฒ + โ๐ฒ, ๐ฌ+ = ๐ฌ + โ๐ฌ. memenuhi sistem (2), dengan kata lain ๐ ๐ฑ + โ๐ฑ = ๐, ๐T ๐ฒ + โ๐ฒ + ๐ฌ + โ๐ฌ = ๐, ๐ฑ + โ๐ฑ ๐ฌ + โ๐ฌ = ๐๐.
3.2 Central Path Central path merupakan aspek penting dari metode interior, yang akan membantu dalam membangun suatu algoritme umum untuk metode primal-dual. Secara geometrik, central path merupakan kurva analitik yang konvergen menuju solusi optimal. Untuk menyelesaikan sistem (1) kondisi pelengkap diubah menjadi xs = ยตe. Dengan, ยต adalah bilangan positif dan e adalah vektor semua satu. Kendala baru ini disebut kondisi pemusatan. Sistem yang dihasilkan adalah ๐๐ฑ = ๐, ๐ฑ โฅ ๐ ๐T ๐ฒ + ๐ฌ = ๐, ๐ฌ โฅ ๐ ๐ฑ๐ฌ = ๐๐.
Dari sistem (3) diperoleh sistem baru sebagai berikut ๐โ๐ฑ = ๐ โ ๐๐ฑ, ๐T โ๐ฒ + โ๐ฌ = ๐ โ ๐T ๐ฒ โ ๐ฌ, ๐ฌโ๐ฑ + ๐ฑโ๐ฌ + โ๐ฑโ๐ฌ = ๐๐ โ ๐ฑ๐ฌ.
๐โ๐ฑ = ๐, ๐T โ๐ฒ + โ๐ฌ = ๐, ๐ฌโ๐ฑ + ๐ฑโ๐ฌ + โ๐ฑโ๐ฌ = ๐๐ โ ๐ฑ๐ฌ.
๐ฅ1 โ๐ฅ1 ๐ฅ2 โ๐ฅ2 + โฎ โฎ ๐ฅ๐ โ๐ฅ๐
โ๐ 1 โ๐ฅ1 โ๐ 2 โ๐ฅ2 + โฎ โฎ โ๐ ๐ โ๐ฅ๐
(5)
Untuk mencari solusi sistem (5) digunakan metode Newton. Persamaan pertama dan persamaan kedua pada sistem (5) merupakan persamaan linear. Sedangkan, persamaan ketiga merupakan persamaan taklinear karena mengandung faktor kuadratik โ๐ฑโ๐ฌ. Untuk menyelesaikan sistem (5), persamaan ketiga dilinearkan dengan menggunakan metode Newton, sebagai berikut
sโx + xโs + โ๐ฑโ๐ฌ = ยตe โ xs ๐ 1 ๐ 2 โฎ ๐ ๐
(4)
karena ๐๐ฑ = ๐ dan ๐T ๐ฒ + ๐ฌ = ๐, maka sistem berikut setara dengan sistem (4)
(2)
Solusi dari sistem (2) dinotasikan dengan x(ยต), y(ยต), dan s(ยต). x(ยต) disebut ยต-center dari (P) dan (y(ยต), s(ยต)) disebut ยต-center dari (D). Himpunan semua x(ยต) disebut central path dari (P), demikian pula himpunan semua (y(ยต), s(ยต)) disebut central path dari (D). Ketika ยต berjalan menuju nol, maka x(ยต),
(3)
โ๐ 1 โ๐ 2 -๐ โฎ โ๐ ๐
๐ฅ1 1 1 + ๐ฅ2 โฎ โฎ ๐ฅ 1 ๐
๐ 1 0 ๐ 2 0 โฎ = โฎ ๐ ๐ 0
6
๐ 1 โ๐ฅ1 + ๐ฅ1 โ๐ 1 + โ๐ฅ1 โ๐ 1 โ ๐ + ๐ฅ1 ๐ 1 = 0 ๐ 2 โ๐ฅ2 + ๐ฅ2 โ๐ 2 + โ๐ฅ2 โ๐ 2 โ ๐ + ๐ฅ2 ๐ 2 = 0 โฎ ๐ ๐ โ๐ฅ๐ + ๐ฅ๐ โ๐ ๐ + โ๐ฅ๐ โ๐ ๐ โ ๐ + ๐ฅ๐ ๐ ๐ = 0 Misalnya, dilakukan pelinearan pada persamaan pertama sebagai berikut ๐1 โ๐ฅ1 , โ๐ 1 โ ๐1 โ๐ฅ1.0 , โ๐ 1.0 +
๐๐1 โ๐ฅ 1.0 ,โ๐ 1.0 ๐โ๐ฅ 1
โ๐ฅ1 โ โ๐ฅ1.0 +
๐๐1 โ๐ฅ 1.0 ,โ๐ 1.0 ๐โ๐ 1
โ๐ 1 โ โ๐ 1.0 = 0,
dengan hampiran awal โ๐ฅ1.0 = โ๐ 1.0 = 0, sehingga diperoleh
๐1 0,0 +
๐๐1 0,0 ๐๐1 0, 0 โ๐ฅ1 โ 0 + โ๐ 1 โ 0 = 0 ๐โ๐ 1 ๐โ๐ฅ1 โ๐ + ๐ฅ1 ๐ 1 + ๐ 1 โ๐ฅ1 + ๐ฅ1 โ๐ 1 = 0 ๐ 1 โ๐ฅ1 + ๐ฅ1 โ๐ 1 = ๐ โ ๐ฅ1 ๐ 1
Untuk persamaan kedua sampai dengan ke-n dilakukan pelinearan dengan cara yang sama, sehingga diperoleh ๐ 1 โ๐ฅ1 + ๐ฅ1 โ๐ 1 โ ๐ + ๐ฅ1 ๐ 1 = 0 ๐ 2 โ๐ฅ2 + ๐ฅ2 โ๐ 2 โ ๐ + ๐ฅ2 ๐ 2 = 0 โฎ ๐ ๐ โ๐ฅ๐ + ๐ฅ๐ โ๐ ๐ โ ๐ + ๐ฅ๐ ๐ ๐ = 0 Dapat juga ditulis ๐ 1 ๐ 2 โฎ ๐ ๐
๐ฅ1 โ๐ฅ1 ๐ฅ2 โ๐ฅ2 + โฎ โฎ ๐ฅ๐ โ๐ฅ๐
โ๐ 1 โ๐ 2 -๐ โฎ โ๐ ๐
๐ฅ1 1 ๐ฅ 1 + 2 โฎ โฎ ๐ฅ๐ 1
๐ 1 0 ๐ 2 0 โฎ = โฎ ๐ ๐ 0
sโ๐ฑ + ๐ฑโ๐ฌ โ ๐๐ + ๐ฑ๐ฌ = ๐
Sehingga diperoleh persamaan baru yang merupakan persamaan linear, sebagai berikut ๐โ๐ฑ = ๐ ๐T โ๐ฒ + โ๐ฌ = ๐ ๐ฌโ๐ฑ + ๐ฑโ๐ฌ = ๐๐ โ ๐ฑ๐ฌ
(6)
Sistem (6) dapat dinyatakan dalam bentuk matriks SPL sebagai berikut ๐ 0 0 ๐๐ ๐ 0
0 0 โ๐ฑ 0 = โ๐ฒ 1 ๐๐ โ ๐ฑ๐ฌ ๐ โ๐ฌ
Dengan X = diag (x) dan S = diag (s). Solusi โ๐ฑ, โ๐ฒ, dan โ๐ฌ dinamakan primal-dual langkah Newton. Dengan langkah fullNewton diperoleh ๐ฑ + = ๐ฑ + โ๐ฑ, ๐ฒ + = ๐ฒ + โ๐ฒ, ๐ฌ+ = ๐ฌ + โ๐ฌ.
3.4 Ukuran Kedekatan Pada proses mengikuti central path menuju solusi optimal dengan menggunakan langkah full-Newton, dihasilkan barisan titiktitik yang berada di sekitar central path. Diperlukan suatu ukuran untuk mengukur kedekatan (๐ฑ, (๐ฒ, ๐ฌ)) ke ๐-center dan central path. Sebelum mendefinisikan ukuran kedekatan, terlebih dahulu merumuskan sistem linear (6) yang mendefinisikan arah Newton dalam kasus primal-dual. Untuk tujuan ini, kita definisikan vektor sebagai berikut ๐ฎ โ๐ฑ ๐ฎ โ๐ฌ โ๐ฒ ๐x = , ๐s = , ๐y = ๐ฑ ๐ฌ ๐ dengan ๐ฎ :=
๐ฑ๐ฌ ๐
7
๐ฑ
jika didefinisikan ๐ซ = diag
๐ฌ
sistem (6) setara dengan ๐จ๐ซ๐x = ๐ T ๐จ๐ซ ๐y + ๐s = ๐ ๐x + ๐s = ๐ฎโ1 โ ๐ฎ Bukti :
(i) Persamaan pertama AD๐x = 0 AD
๐ฎ โ๐ฑ ๐ฑ
๐ฑ๐ฌ โ๐ฑ ๐
AD
๐ฑ ๐ฌ โ๐ฑ ๐ฑ
AD
๐
๐ฅ1 s1
0 โฎ 0 A
=0
=0
โฆ
(iii) Persamaan ketiga Ruas kiri ๐ฌโ๐ฑ + ๐ฑโ๐ฌ = s ๐ ๐x d + x ๐ ๐s ๐โ1 = ๐ (๐ฌ๐๐x + x๐โ1 ๐s ) = ๐ (๐ฎ ๐๐โ1 ๐๐x + ๐ฎ ๐๐๐โ1 ๐s ) = ๐๐ฎ (๐x + ๐s ) Ruas kanan ๐๐ โ ๐ฑ๐ฌ = ๐๐ โ ๐ฎ ๐ ๐ (๐ฎ ๐๐โ1 ) = ๐๐ โ ๐ฎ2 ๐๐๐โ1 = ๐๐ โ ๐ฎ2 ๐ = ๐๐ฎ๐ฎโ1 โ ๐๐ฎ2 = ๐๐ฎ ๐ฎโ1 โ ๐ฎ
Jadi, persamaan ketiga terbukti.โ
0 โฆ 0
๐ 1 ๐ฅ1
โ๐ฅ 1
0 โฎ
๐ 2 ๐ฅ2
โ๐ฅ 2
โฆ
๐ซT ๐T ๐y + ๐s = ๐ ๐๐ซ T ๐y + ๐s = ๐ Jadi, persamaan kedua terbukti.โ
๐ฌโ๐ฑ + ๐ฑโ๐ฌ = ๐๐ โ ๐ฑ๐ฌ ๐๐ฎ(๐x + ๐s ) = ๐๐ฎ ๐ฎโ1 โ ๐ฎ ๐x + ๐s = ๐ฎโ1 โ ๐ฎ
=0
๐ฅ2 ๐ 2
maka
โฑ โฎ ๐ฅ๐ ๐ ๐
โฆ
Persamaan dari sistem (6) menunjukkan bahwa vektor ๐x dan ๐s adalah ruang nol dan ruang baris dari matriks AD, ini berarti ๐x dan ๐s ortogonal. Ortogonalitas dari ๐x dan ๐s mengimplikasikan bahwa
โฎ ๐ ๐ ๐ฅ๐
๐
=0
โ๐ฅ1 โ๐ฅ2 โฎ โ๐ฅ๐ ๐ =๐ ๐ ๐ โ๐ฑ = ๐ Jadi, persamaan pertama terbukti.โ (ii) Persamaan kedua ๐T โ๐ฒ + โ๐ฌ = ๐ ๐ฌ ๐T ๐y ๐ + ๐s = ๐ ๐ฎ ๐ฌ ๐T ๐y ๐ + ๐s =๐ ๐ฑ๐ฌ ๐ ๐ฌ๐ ๐T ๐y ๐ + ๐s =๐ ๐ฑ ๐ฌ ๐ ๐T ๐y + ๐s =๐ ๐ฑ ๐ฌ ๐ซT ๐T ๐y + ๐s = ๐ซT ๐ ๐ฑ
2
2
= ๐x + ๐s 2 = ๐ฎโ1 โ ๐ฎ 2 Perhatikan bahwa ๐x , ๐s dan ๐y adalah nol jika dan hanya jika ๐ฎโ1 โ ๐ฎ = ๐. Untuk mengukur jarak (x, (y, s)) ke ๐-center, digunakan ukuran ๐ฟ ๐ฑ, ๐ฌ; ๐ yang didefinisikan sebagai berikut ๐x
โ๐ฅ ๐
๐ฟ ๐ฑ, ๐ฌ; ๐ := :=
+ ๐s
1
2 1 2
๐ฎโ1 โ ๐ฎ ๐ ๐ฑ๐ฌ
โ
๐ฑ๐ฌ ๐
(Roos et al. 2006) 3.5 Kompleksitas Algoritme Selanjutnya akan dibahas mengenai kompleksitas algoritme dari metode interior primal-dual dengan langkah full-Newton. Berikut ini adalah algoritmenya Langkah 1. Pilih nilai awal parameter akurasi ๐ > 0; parameter pendekatan ๐, 0 โค ๐ < 1;
8
strictly fisibel (๐ฑ 0 , ๐ฒ 0 , ๐ฌ0 ) dengan (๐ฑ 0 )T ๐ฌ0 = ๐๐0 dan ๐ฟ(๐ฑ 0 , ๐ฌ0 ; ๐0 ) โค ๐; parameter barrier ๐, 0 < ๐ < 1. Didefinisikan ๐ฑ โ ๐ฑ 0 ; ๐ฌ โ ๐ฌ0 ; ๐ฒ โ ๐ฒ 0; ๐ โ ๐0 ; Dengan penghitung iterasi awal ๐ = 0. Langkah 2. Selama ๐๐ โฅ ๐ lanjut ke langkah 4 Langkah 3. Selainnya, STOP. Langkah 4. Lakukan pencarian solusi baru ๐๐+1 = (1 โ ๐)๐ +1 ๐0 ๐ฑ ๐+1 = ๐ฑ ๐ + โ๐ฑ ๐ฒ ๐+1 = ๐ฒ ๐ + โ๐ฒ ๐ฌ๐+1 = ๐ฌ๐ + โ๐ฌ Langkah 5. ๐ = ๐ + 1, kembali ke langkah 2
1 ๐๐0 ln ๐ ๐ dan iterasi akan berhenti pada saat ๐๐ โค ๐. (Silalahi 2011) Bukti : Awalnya duality gap adalah n๐0 , sehingga dengan menggunakan Lema 1 diperoleh (๐ฑ 0 )T ๐ฌ0 = n๐0 Pada saat iterasi bertambah maka nilai ๐ dikalikan dengan faktor 1 โ ๐ sebagai berikut ๐+ = (1 โ ๐)๐ Untuk iterasi pertama diperoleh (๐ฑ1 )T ๐ฌ1 = (1 โ ๐) n๐0 Untuk iterasi ke-k diperoleh (๐ฑ ๐ )T ๐ฌ๐ = (1 โ ๐)๐ n๐0 Oleh karena itu, setelah iterasi ke-k duality gap lebih kecil dari ๐ jika : (1 โ ๐)๐ n๐0 โค ๐ Dengan menggunakan logaritma maka diperoleh ๐ ln 1 โ ๐ + ln ๐๐0 โค ln ๐ โ๐ ln 1 โ ๐ โ ln ๐๐0 โฅ โ ln ๐ ๐ (โln 1 โ ๐ ) โ ln ๐๐0 โฅ โ ln ๐ Karena โ ln 1 โ ๐ โฅ ๐, maka pertidaksamaan diatas tetap terpenuhi jika ๐๐ โ ln ๐๐0 โฅ โ ln ๐ ๐๐ โฅ ln ๐๐0 โ ln ๐ 1 1 ๐๐0 ๐ โฅ (ln ๐๐0 โ ln ๐ ) = ln ๐ ๐ ๐ Jadi, Lema 2 terbukti.โ
Lema 1 Jika langkah Newton primal-dual adalah fisibel maka (๐ฑ + )T ๐ฌ+ = ๐๐. (Roos et al. 2006) Bukti : lihat Roos Vektor ๐ฑ + dan ๐ฌ+ merupakan langkah fullNewton primal-dual dan n adalah banyaknya pertidaksamaan dari masalah primal-dual. Lema 2 Metode interior primal-dual dengan langkah full-Newton memiliki jumlah iterasi tidak lebih dari
Lema berikut ini memperlihatkan efek dari langkah Newton primal-dual.
Lema 3 Misal (๐ฑ, ๐ฌ) adalah pasangan primal-dual positif dan ๐ > 0 sedemikian rupa sehingga ๐ฑ T ๐ฌ = ๐๐. Selanjutnya, jika ๐2๐
๐ฟ โถ= ๐ฟ(๐ฑ, ๐ฌ; ๐) dan ๐+ = (1 โ ๐)๐ maka ๐ฟ(๐ฑ, ๐ฌ; ๐+ )2 = 1 โ ๐ ๐ฟ 2 + 4(1โ๐ ) (Silalahi 2011) Bukti : Didefinisikan ๐ฟ + โ ๐ฟ(๐ฑ, ๐ฌ; ๐ + ) dan ๐ฎ = 1
(๐ฟ +)2 = =
1
2
4
Karena ๐ฎ+ =
(๐ฎ+)โ1 โ ๐ฎ+ (๐ฎ+)โ1 โ ๐ฎ+ ๐ฑ๐ฌ ๐+
2
, diperoleh
2
๐ฑ๐ฌ ๐
, maka dapat dituliskan
9
๐ฎ+ =
๐ฑ๐ฌ ๐+
๐ฑ๐ฌ
=
(1โ๐)๐
1
๐ฑ๐ฌ
=
๐
1โ๐
=
๐ฎ 1โ๐
(๐ฎ+ )โ1 =
1โ๐ ๐ฎ
Sehingga diperoleh
๐ฟ
+ 2
1 = 4
2
2 1โ๐ ๐ฎ 1 ๐ฎ โ = 1 โ ๐ ๐ฎโ1 โ ๐ฎ 4 1โ๐ 1โ๐ ๐ฎ ๐๐ฎ ๐๐ฎ 2 1 1 โ ๐ ๐ฎโ1 โ โ + = 4 1โ๐ 1โ๐ 1โ๐ 2 1 ๐ฎ โ ๐๐ฎ ๐๐ฎ = 1 โ ๐ ๐ฎโ1 โ + 4 1โ๐ 1โ๐ 2 1 (1 โ ๐)๐ฎ ๐๐ฎ โ1 = 1โ๐ ๐ฎ โ + 4 1โ๐ 1โ๐ 2 1 1 โ ๐ ๐ฎโ1 โ (1 โ ๐)๐ฎ ๐๐ฎ = + 4 1โ๐ 1โ๐ 2 1 1 โ ๐ (๐ฎโ1 โ ๐ฎ) 1 ๐๐ฎ ๐๐ฎ = = + 1 โ ๐ (๐ฎโ1 โ ๐ฎ) + 4 4 1โ๐ 1โ๐ 1โ๐
Dari ๐ฑ T ๐ฌ = ๐๐ diperoleh ๐ฎ
2
= ๐, seperti berikut ๐ฅ1 ๐ 1 ๐
๐ฎ
2
=
๐ฎT ๐ฎ
2
T
= ๐ฎ ๐ฎ=
๐ฅ2 ๐ 2 โฆ ๐
๐ฅ1 ๐ 1 ๐
๐ฅ๐ ๐ ๐ ๐
๐ฅ2 ๐ 2 ๐ โฎ ๐ฅ๐ ๐ ๐ ๐
=
๐ฅ1 ๐ 1 ๐ฅ2 ๐ 2 ๐ฅ๐ ๐ ๐ ๐ฑT ๐ฌ + + โฏ+ = =๐ ๐ ๐ ๐ ๐
kemudian, ๐ ๐ฅ1 ๐ 1 ๐ฎT ๐ฎโ1 =
๐ฅ1 ๐ 1 ๐
๐ฅ2 ๐ 2 โฏ ๐
๐ฅ๐ ๐ ๐ ๐
๐ ๐ฅ2 ๐ 2
= 1 + 1 + โฏ + 1 = ๐. 1 = ๐
โฎ ๐ ๐ฅ๐ ๐ ๐ selanjutnya, ๐ฎT ๐ฎโ1 โ ๐ฎ = ๐ฎT ๐ฎโ1 โ ๐ฎT ๐ฎ = ๐ โ ๐ฎ Jadi u ortogonal terhadap ๐ฎโ1 โ ๐ฎ. Akibatnya, 1โ๐ (๐ฟ + )2 = ๐ฎโ1 โ ๐ฎ 4
2
=๐โ๐=0
2
+
๐2 ๐ฎ 2 4(1 โ ๐)
2
10
Karena ๐ฎโ1 โ ๐ฎ = 2๐ฟ dan ๐ฎ
2
= ๐, diperoleh (๐ฟ + )2 = 1 โ ๐ ๐ฟ 2 +
๐2๐ 4(1 โ ๐)
Jadi, Lema 3 terbukti.โ Untuk menjamin nilai ๐ฟ pada Lema 3 maka diperlukan Lema 4 dan akibat 1 sebagai berikut
Teorema berikut ini adalah batas atas iterasi untuk metode interior primal-dual dengan langkah full-Newton.
Lema 4 Jika ๐ฟ โ ๐ฟ(๐ฑ, ๐ฌ; ๐) โค 1, maka langkah Newton primal-dual fisibel yaitu ๐ฑ + dan ๐ฌ+ taknegatif. Selain itu, jika ๐ฟ < 1 maka ๐ฑ + dan ๐ฌ+ positif dan ๐ฟ2 ๐ฟ(๐ฑ + , ๐ฌ+ ; ๐) โค 2(1 โ ๐ฟ 2 ) (Roos et al. 2006)
Teorema 2
Bukti : lihat Roos
1
๐ฟ โถ= ๐ฟ ๐ฑ, ๐ฌ; ๐ โค
๐ฟ ๐ฑ + , ๐ฌ+ ; ๐ โค ๐ฟ 2.
1
, 2
maka
(Silalahi 2011)
, maka jumlah
๐๐0 ๐ Output dari primal-dual pasangan (x, s) yaitu ๐ฑ T ๐ฌ โค ๐. (Silalahi 2011)
1 2
. Dengan meng1
gunakan akibat 1 yaitu ๐ฟ ๐ฑ, ๐ฌ; ๐ โค 2, maka setelah langkah Newton primal-dual diperoleh 1 ๐ฟ ๐ฑ + , ๐ฌ+ ; ๐ โค 2. Setelah iterasinya bertambah, nilai ๐ menjadi ๐+ = (1 โ ๐)๐. 1 Dengan mengambil nilai ๐ = ๐ +1, diperoleh ๐ฟ ๐ฑ + , ๐ฌ+ ; ๐+
2
๐ +1
๐ + 1 ln
Misalkan dipilih ๐ =
๐ฟ ๐ฑ + , ๐ฌ+ ; ๐+
1
dan ๐ = iterasi tidak lebih dari 2
Bukti :
Akibat 1 Jika
Jika ๐ =
2
sebagai berikut
๐2๐ 1 โ ๐ 2 + ๐ 2 ๐ ๐ 2 โ 2๐ + 1 + ๐ 2 ๐ = = 1โ๐ 4 1โ๐ 4 1โ๐ 2 ๐ ๐+1 2 2 +1+๐+1 ๐+1โ +1 1โ +1 ๐+1 ๐+1 ๐+1 = = 1 1 1 1โ 4 1โ 4 1โ ๐+1 ๐+1 ๐+1 2 1 2โ 2 1โ 2 1 ๐+1 ๐+1 = = = = 1 1 4 2 4 1โ 4 1โ ๐+1 ๐+1 1โ๐ + 4 4 1 ๐+1โ = 4
โค
Dari penyelesaian di atas diperoleh 1 ๐ฟ ๐ฑ + , ๐ฌ+ ; ๐+ 2 โค 2 = ๐. Ini berarti bahwa ๐ฟ(๐ฑ, ๐ฌ; ๐) โค ๐ tetap dipertahankan pada setiap iterasi. Dengan menggabungkan penjelasan di
atas dengan Lema 2 maka diperoleh Teorema 2. Jadi, Teorema 2 terbukti.โ
IV STUDI KASUS Untuk studi kasus pada metode interior digunakan masalah Klee-Minty dengan 1
๐ = 3 dan ๐ฆ0 = 0 yang diberikan oleh : ๐ฆ๐ ,
Minimumkan Kendala
1 3
Dengan menggunakan software MATLAB R2008b diperoleh gambar sebagai berikut
1
๐ฆ๐โ1 โค ๐ฆ๐ โค 1 โ ๐ฆ๐โ1 3
๐ = 1, โฆ , ๐ Dengan ๐ menyatakan banyaknya pertidaksamaan dan ๐ menyatakan banyaknya variabel. 1) Pada saat ๐ = 4 dan ๐ = 2 Maksimumkan Dengan kendala
โ๐ฆ2 ๐ฆ1 โค 1 โ๐ฆ1 โค 0
Gambar 1 Masalah Klee-Minty pada saat ๐ = 4, ๐ = 10, dan ๐ = 10โ5 .
1 ๐ฆ โ ๐ฆ2 โค 0 3 1 1 ๐ฆ + ๐ฆ2 โค 1 3 1 Tabel 1 Hasil iterasi pada saat ๐ = 10, ๐ = 10โ5 Iterasi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
๐๐ 40 22.1115 12.2229 6.7567 3.7350 2.0647 1.1413 0.6309 0.3488 0.1928 0.1066 0.0589 0.0326 0.0180 0.0100 0.0055 0.0030 0.0017 9.2916e-004 5.1363e-004 2.8393e-004 1.5695e-004 8.6760e-005 4.7960e-005
๐ฅ1 31.5518 17.4458 9.6518 5.3499 2.9833 1.6947 1.0117 0.6669 0.4994 0.4189 0.3791 0.3583 0.3470 0.3409 0.3375 0.3356 0.3346 0.3340 0.3337 0.3335 0.3335 0.3334 0.3334 0.3334
๐ฆ1 0.3169 0.3169 0.3167 0.3162 0.3144 0.3088 0.2928 0.2557 0.1949 0.1279 0.0758 0.0430 0.0241 0.0134 0.0074 0.0041 0.0023 0.0013 0.6966e-003 0.3851e-003 0.2129e-003 0.1177e-003 0.6507e-004 0.3597e-004
๐ 1 0.3169 0.3169 0.3167 0.3162 0.3144 0.3088 0.2928 0.2557 0.1949 0.1279 0.0758 0.0430 0.0241 0.0134 0.0074 0.0041 0.0023 0.0013 0.0007 0.0004 0.0002 0.0001 0.0001 0.0000
12
24 25
2.6512e-005 1.4655e-005
0.3333 0.3333
0.1988e-004 0.1099e-004
0.0000 0.0000
Pada saat ๐ = 10, ๐ = 10โ5 , ๐ = 4, dan ๐ = 2 maka jumlah iterasinya sebanyak 25 iterasi. Banyaknya iterasi pada Tabel 1 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 34 iterasi. Tabel 2 Hasil iterasi pada saat ๐ = 100, ๐ = 10โ5 Iterasi ๐๐ ๐ฅ1 ๐ฆ1 0 400 315.4705 0.3170 1 221.1146 174.3883 0.3170 2 122.2291 96.4003 0.3170 3 67.5666 53.2902 0.3170 4 37.3499 29.4607 0.3170 5 20.6465 16.2903 0.3169 6 11.4131 9.0137 0.3167 7 6.3090 4.9982 0.3161 8 3.4875 2.7907 0.3140 9 1.9279 1.5911 0.3077 10 1.0657 0.9583 0.2898 11 0.5891 0.6407 0.2497 12 0.3256 0.4869 0.1870 13 0.1800 0.4128 0.1209 14 0.0995 0.3760 0.0711 15 0.0550 0.3566 0.0402 16 0.0304 0.3461 0.0225 17 0.0168 0.3404 0.0125 18 0.0093 0.3372 0.0069 19 0.0051 0.3355 0.0038 20 0.0028 0.3345 0.0021 21 0.0016 0.3340 0.0012 22 8.6760e-004 0.3337 0.6505e-003 23 4.7960e-004 0.3335 0.3596e-003 24 2.6512e-004 0.3334 0.1988e-003 25 1.4655e-004 0.3334 0.1099e-003 26 8.1012e-005 0.3334 0.6076e-004 27 4.4783e-005 0.3334 0.3359e-004 28 2.4755e-005 0.3333 0.1857e-004 29 1.3684e-005 0.3333 0.1026e-004
๐ 1 0.3170 0.3170 0.3170 0.3170 0.3170 0.3169 0.3167 0.3161 0.3140 0.3077 0.2898 0.2497 0.1870 0.1209 0.0711 0.0402 0.0225 0.0125 0.0069 0.0038 0.0021 0.0012 0.0007 0.0002 0.0001 0.0001 0.0000 0.0000 0.0000 0.0002
Pada saat ๐ = 100, ๐ = 10โ5 , ๐ = 4, dan ๐ = 2 maka jumlah iterasinya sebanyak 29 iterasi. Banyaknya iterasi pada Tabel 2 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 39 iterasi. Tabel 3 Hasil iterasi pada saat ๐ = 10, ๐ = 10โ3 Iterasi ๐๐ ๐ฅ1 ๐ฆ1 ๐ 1 0 40 31.5518 0.3169 0.3169 1 22.1115 17.4458 0.3169 0.3169 2 12.2229 9.6518 0.3167 0.3167 3 6.7567 5.3499 0.3162 0.3162 4 3.7350 2.9833 0.3144 0.3144 5 2.0647 1.6947 0.3088 0.3088 6 1.1413 1.0117 0.2928 0.2928 7 0.6309 0.6669 0.2557 0.2557 8 0.3488 0.4994 0.1949 0.1949 9 0.1928 0.4189 0.1279 0.1279
13
10 11 12 13 14 15 16 17
0.1066 0.0589 0.0326 0.0180 0.0100 0.0055 0.0030 0.0017
0.3791 0.3583 0.3470 0.3409 0.3375 0.3356 0.3346 0.3340
0.0758 0.0430 0.0241 0.0134 0.0074 0.0041 0.0023 0.0013
0.0758 0.0430 0.0241 0.0134 0.0074 0.0041 0.0023 0.0013
Pada saat ๐ = 10, ๐ = 10โ3 , ๐ = 4, dan ๐ = 2 maka jumlah iterasinya sebanyak 17 iterasi. Banyaknya iterasi pada Tabel 3 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 24 iterasi. 2) Pada saat ๐ = 6 dan ๐ = 3 Maksimumkan โ๐ฆ3 Dengan kendala ๐ฆ1 โค 1 โ๐ฆ1 โค 0 1 ๐ฆ1 โ ๐ฆ2 โค 0 3 1
3 1 3 1 3
๐ฆ1 + ๐ฆ2 โค 1 ๐ฆ2 โ ๐ฆ3 โค 0 ๐ฆ2 + ๐ฆ3 โค 1
Tabel 4 Hasil iterasi pada saat ๐ = 10, ๐ = 10โ5 Iterasi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
๐๐ 60 37.3221 23.2157 14.4410 8.9828 5.5876 3.4757 2.1620 1.3448 0.8365 0.5204 0.3237 0.2013 0.1252 0.0779 0.0485 0.0301 0.0188 0.0117 0.0073 0.0045 0.0028 0.0017 0.0011 6.7564e-004 4.2027e-004 2.6142e-004 1.6262e-004 1.0115e-004 6.2920e-005
๐ฅ1 32.9543 20.4994 12.7524 7.9342 4.9381 3.0761 1.9205 1.2053 0.7652 0.4969 0.3357 0.2408 0.1862 0.1551 0.1374 0.1270 0.1209 0.1171 0.1148 0.1134 0.1125 0.1120 0.1117 0.1115 0.1113 0.1112 0.1112 0.1112 0.1111 0.1111
๐ฆ1 0.3035 0.3034 0.3034 0.3034 0.3033 0.3029 0.3021 0.3001 0.2956 0.2859 0.2673 0.2362 0.1929 0.1443 0.1002 0.0663 0.0428 0.0272 0.0171 0.0107 0.0067 0.0042 0.0026 0.0016 0.0010 0.6299e-003 0.3920e-003 0.2439e-003 0.1517e-003 0.9437e-004
๐ 1 0.3035 0.3034 0.3034 0.3034 0.3033 0.3029 0.3021 0.3001 0.2956 0.2859 0.2673 0.2362 0.1929 0.1443 0.1002 0.0663 0.0428 0.0272 0.0171 0.0107 0.0067 0.0042 0.0026 0.0016 0.0010 0.0006 0.0004 0.0002 0.0002 0.0001
14
30 31 32
3.9139e-005 2.4346e-005 1.5144e-005
0.1111 0.1111 0.1111
0.5870e-004 0.3652e-004 0.2272e-004
0.0001 0.0000 0.0000
Pada saat ๐ = 10, ๐ = 10โ5 , ๐ = 6, dan ๐ = 3 maka jumlah iterasinya sebanyak 32 iterasi. Banyaknya iterasi pada Tabel 4 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 41 iterasi. Tabel 5 Hasil iterasi pada saat ๐ = 100, ๐ = 10โ5 Iterasi ๐๐ ๐ฅ1 ๐ฆ1 0 600 329.5349 0.3035 1 373.2213 204.9825 0.3035 2 232.1569 127.5065 0.3035 3 144.4099 79.3137 0.3035 4 89.8281 49.3362 0.3035 5 55.8762 30.6893 0.3035 6 34.7570 19.0906 0.3034 7 21.6201 11.8762 0.3034 8 13.4485 7.3893 0.3034 9 8.3654 4.5994 0.3032 10 5.2036 2.8657 0.3029 11 3.2368 1.7901 0.3019 12 2.0134 1.1248 0.2997 13 1.2524 0.7159 0.2945 14 0.7790 0.4671 0.2837 15 0.4846 0.3180 0.2635 16 0.3014 0.2306 0.2304 17 0.1875 0.1804 0.1857 18 0.1166 0.1518 0.1372 19 0.0726 0.1355 0.0944 20 0.0451 0.1259 0.0622 21 0.0281 0.1202 0.0400 22 0.0175 0.1167 0.0254 23 0.0109 0.1146 0.0160 24 0.0068 0.1133 0.0100 25 0.0042 0.1124 0.0063 26 0.0026 0.1119 0.0039 27 0.0016 0.1116 0.0024 28 0.0010 0.1114 0.0015 29 6.2920e-004 0.1113 0.9427e-003 30 3.9139e-004 0.1112 0.5867e-003 31 2.4346e-004 0.1112 0.3650e-003 32 1.5144e-004 0.1112 0.2271e-003 33 9.4200e-005 0.1111 0.1413e-003 34 5.8596e-005 0.1111 0.8788e-004 35 3.6449e-005 0.1111 0.5467e-004 36 2.2672e-005 0.1111 0.3401e-004 37 1.4103e-005 0.1111 0.2115e-004
๐ 1 0.3035 0.3035 0.3035 0.3035 0.3035 0.3035 0.3034 0.3034 0.3034 0.3032 0.3029 0.3019 0.2997 0.2945 0.2837 0.2635 0.2304 0.1857 0.1372 0.0944 0.0622 0.0400 0.0160 0.0100 0.0063 0.0160 0.0039 0.0024 0.0015 0.0009 0.0006 0.0004 0.0002 0.0001 0.0001 0.0001 0.0000 0.0000
Pada saat ๐ = 100, ๐ = 10โ5 , ๐ = 6, dan ๐ = 3 maka jumlah iterasinya sebanyak 37 iterasi. Banyaknya iterasi pada Tabel 5 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 47 iterasi.
15
Tabel 6 Hasil iterasi pada saat ๐ Iterasi ๐๐ ๐ฅ1 0 60 32.9543 1 37.3221 20.4994 2 23.2157 12.7524 3 14.4410 7.9342 4 8.9828 4.9381 5 5.5876 3.0761 6 3.4757 1.9205 7 2.1620 1.2053 8 1.3448 0.7652 9 0.8365 0.4969 10 0.5204 0.3357 11 0.3237 0.2408 12 0.2013 0.1862 13 0.1252 0.1551 14 0.0779 0.1374 15 0.0485 0.1270 16 0.0301 0.1209 17 0.0188 0.1171 18 0.0117 0.1148 19 0.0073 0.1134 20 0.0045 0.1125 21 0.0028 0.1120 22 0.0017 0.1117 23 0.0011 0.1115
= 10, ๐ = 10โ3 ๐ฆ1 ๐ 1 0.3035 0.3035 0.3034 0.3034 0.3034 0.3034 0.3034 0.3034 0.3033 0.3033 0.3029 0.3029 0.3021 0.3021 0.3001 0.3001 0.2956 0.2956 0.2859 0.2859 0.2673 0.2673 0.2362 0.2362 0.1929 0.1929 0.1443 0.1443 0.1002 0.1002 0.0663 0.0663 0.0428 0.0428 0.0272 0.0272 0.0171 0.0171 0.0107 0.0107 0.0067 0.0067 0.0042 0.0042 0.0026 0.0026 0.0016 0.0016
Pada saat ๐ = 10, ๐ = 10โ3 , ๐ = 6, dan ๐ = 3 maka jumlah iterasinya sebanyak 23 iterasi. Banyaknya iterasi pada Tabel 6 telah sesuai dengan Teorema 2 yaitu batas atas iterasinya sebanyak 29 iterasi.
2
V SIMPULAN DAN SARAN 5.1 Simpulan (i)
Metode interior primal-dual dengan langkah full-Newton dapat digunakan untuk menyelesaikan masalah optimasi linear. (ii) Dari hasil analisis kompleksitas algoritme interior primal-dual dengan langkah full-Newton diketahui bahwa banyaknya iterasi yang diperoleh tidak ๐๐ 0
lebih dari ๐ + 1 log . ๐ (iii) Dari hasil pengkajian dapat disimpulkan bahwa semakin besar nilai n dan ๐0 yang diberikan, maka jumlah iterasinya semakin meningkat. Sedangkan, semakin
besar nilai ๐ maka jumlah iterasinya semakin sedikit. Banyaknya iterasi yang diperoleh pada masing-masing nilai n, ๐0 , dan ๐ tidak lebih dari ๐ + 1 log
๐๐ 0 ๐
.
5.2 Saran Pada karya ilmiah ini telah dilakukakn analisis banyaknya iterasi untuk masalah optimasi linear dengan metode titik interior. Untuk penelitian lanjutan dapat dilakukan perbandingan banyaknya iterasi untuk kasus taklinear dengan metode titik interior.
DAFTAR PUSTAKA Grimaldi RP. 2004. Discrete and Combinatorial Mathematics: An Applied Introduction. Ed ke-5. New York: Pearson. Leon SJ. 2001. Aljabar Linear dan Aplikasinya. Ed ke-5. Bondan A, Penerjemah; Hardani HW, Editor. Jakarta: Erlangga. Terjemahan dari Linear Algebra with Aplications. Mitchell JE, P.M. Pardalos and M.G.C. Resende. 1998. Interior Point Methods for Combinatorial Optimization. Kluwer Academic Publishers.
Munir Rinaldi. 2003. Metode Bandung: Informatika.
Numerik.
Ross C, Terlaky T, and Vial J-Ph. 2006. Interior Point Methods for Linear Optimization. New York: Springer. Silalahi BP. 2011. On the Central Path of Redundant Klee-Minty Problems. PhD thesis. Roos C (promotor). Delft University of Technology. The Netherlands: TU Delft. Winston WL. 2004. Operation Research: Applications and Algorithms. Ed ke-4. New York: Duxbury.
2
LAMPIRAN
18
Lampiran 1 Program untuk Fungsi Langkah Newton function [x,y,s]= Newton_step(A,b,c,x,y,s,mu); rb = b - A*x; rc = c - A'*y - s; v = sqrt(x.*s/mu);
r = v.^(-1)-v; D = diag(sqrt(x./s)); AA=A*D; M=AA*AA'; rhs = rb/sqrt(mu)+AA*(diag(v./s)*rc - r); dy=M\rhs; Dy = sqrt(mu)*dy; ds dx Dx Ds
= diag(v./s)*rc - AA'*dy; = r - ds; = x.*dx./v; = s.*ds./v;
alpha = x = x + y = y + s = s + return
1; alpha*Dx; alpha*Dy; alpha*Ds;
19
Lampiran 2 Program untuk Kasus Dua Dimensi function [A,b,c,x,y,s,mu,opt] = zigzag_Nematollahi(n) n=4 A=[-1 1 1/3 1/3; 0 0 -1 1] c=[0;1;0;1]; b=[0;-1]; figure(3) clf y = [0.5 0.5]'; s = c - A'*y mu = 10 % mu = 100 % hilangkan tanda persen jika digunakan x = mu./s figure(3) axis([0 1 0 1]) line('color',[0 0 0],'linestyle','*','erase','none','xdata', y(1),'ydata',y(2),'markersize',5); for i = 1:250, [x,y,s] = Newton_step(A,b,c,x,y,s,mu); line('color',[0 0 0], 'linestyle','*','erase','none','xdata', y(1),'ydata',y(2),'markersize',5); end rb = A*x-b; rc = c - A'*y - s; [x s] x y x.*s mu=(x'*s)/(n); theta = 1/sqrt(5); % theta = 1/sqrt(n+1) % nilai theta bergantung pada n eps = 10^(-3); % eps = 10^(-5) % hilangkan tanda persen jika digunakan figure(3) line('color',[0 1 0],'linestyle','o','erase','none','xdata', y(1),'ydata',y(2),'markersize',2);
20
Lanjutan Lampiran 2 it=0 while n*mu>eps, nmu=n*mu mu = (1-theta)*mu x y s [x,y,s] = Newton_step(A,b,c,x,y,s,mu); line('color',[0 0 1],'linestyle','o','erase','none','xdata', y(1),'ydata',y(2),'markersize',2); it=it+1 end line('color',[1 0 0],'linestyle','*','erase','none','xdata',y(1), 'ydata',y(2),'markersize',4); axis([-0.3 0.3 0 1]) axis([-0.1 1.1 -0.3 1.4]) xx=[0 1 1 0 0] yy=[0 1/3 2/3 1 0] line('color',[1 0 0],'linestyle','-','erase','none','xdata',xx, 'ydata',yy,'markersize',4); y return
21
Lampiran 3 Program untuk Kasus Tiga Dimensi function [A,b,c,x,y,s,mu,opt] = zigzag_Nematollahi(n) n=6 A=[-1 1 1/3 1/3 0 0; 0 0 -1 1 1/3 1/3; 0 0 0 0 -1 1] c=[0;1;0;1;0;1]; b=[0;0;-1]; figure(3) clf y = [0.5 0.5 0.5]'; s = c - A'*y mu =10 % mu = 100 % hilangkan tanda persen jika digunakan x = mu./s figure(3) axis([0 1 0 1]) line('color',[0 0 0],'linestyle','*','erase','none','xdata', y(1),'ydata',y(2),'markersize',5); for i = 1:250, [x,y,s] = Newton_step(A,b,c,x,y,s,mu); line('color',[0 0 0], 'linestyle','*','erase','none','xdata', y(1),'ydata',y(2),'markersize',5); end rb = A*x-b; rc = c - A'*y - s; [x s] x y x.*s mu=(x'*s)/(n); theta = 1/sqrt(7); % theta = 1/sqrt(n+1) % nilai theta bergantung pada n eps = 10^(-3); % eps = 10^(-5) % hilangkan tanda persen jika digunakan figure(3) line('color',[0 1 0],'linestyle','o','erase','none','xdata',y(1), 'ydata',y(2),'markersize',2);
22
Lanjutan Lampiran 3 it=0 while n*mu>eps, nmu=n*mu mu = (1-theta)*mu x y s [x,y,s] = Newton_step(A,b,c,x,y,s,mu); line('color',[0 0 1],'linestyle','o','erase','none','xdata', y(1),'ydata',y(2),'markersize',2); it=it+1 %pause(0.2) %end end line('color',[1 0 0],'linestyle','*','erase','none','xdata',y(1), 'ydata',y(2),'markersize',4); axis([-0.3 0.3 0 1]) axis([-0.1 1.1 -0.3 1.4]) xx=[0 1 1 0 0] yy=[0 1/3 2/3 1 0] line('color',[1 0 0],'linestyle','-','erase','none','xdata',xx, 'ydata',yy,'markersize',4); y return