METODE INTERIOR PRIMAL-DUAL DENGAN LANGKAH FULL-NEWTON: STUDI KASUS MASALAH KLEE-MINTY DENGAN KENDALA REDUNDANT TAKNEGATIF
IRWAN NURSOLIH
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
ABSTRAK IRWAN NURSOLIH. Metode Interior Primal-Dual dengan Langkah Full-Newton: Studi Kasus Masalah Klee-Minty dengan Kendala Redundant Taknegatif. Dibimbing oleh BIB PARUHUM SILALAHI dan MUHAMMAD ILYAS. Masalah Klee-Minty merupakan masalah optimasi linear yang memerlukan iterasi eksponensial bila diselesaikan dengan metode simpleks. Kelemahan metode simpleks ini, memacu penelitian untuk mencari metode lain yang dapat menyelesaikan masalah optimasi linear dengan waktu polinomial. Terobosan yang efektif untuk menyelesaikan masalah optimasi linear terjadi dengan munculnya metode interior. Dalam penyelesaian masalah Klee-Minty menggunakan metode interior, proses menuju solusi optimal mengikuti apa yang disebut central path. Dalam karya ilmiah ini kita mengamati salah satu kasus terburuk penyelesaian masalah Klee-Minty, yaitu dengan penambahan kendala redundant taknegatif. Dari studi kasus yang telah dilakukan, diketahui bahwa kendala ini dapat mengakibatkan central path mengunjungi cukup dekat ke verteks-verteks pada daerah fisibel. Sehingga penyelesaian masalah Klee-Minty menggunakan metode interior menjadi lebih lama. Kata Kunci: central path, kendala redundant, masalah Klee-Minty, metode interior, metode simpleks.
i
ABSTRACT IRWAN NURSOLIH. Primal-Dual Interior-Point Method with Full-Newton Steps: Case Study Klee-Minty Problem with Redundant Non-Negative Constraints. Supervised by BIB PARUHUM SILALAHI and MUHAMMAD ILYAS. Klee-Minty problem is a linear optimization problem that requires exponential iteration when it is solved by simplex method. The weakness of this simplex method has stimulated research to find another method, that can solve linear optimization problem with polynomial time. Effective breakthrough to solve linear optimization problem has occurred with the appearance of interior-point method. In solving the Klee-Minty problem using interior-point method, the process leading to an optimal solution follows a central path. In this paper we examine one of the worst case of solving Klee-Minty problem, with the addition of redundant non-negative constraints. From the results of some case studies, it is known that these constraints lead the central path to visit the vertices in the feasible region closely enough. So solving the Klee-Minty problem using the interior-point method becomes longer. Keywords: central path, interior-point method, Klee-Minty problem, redundant constraints, simplex method.
ii
METODE INTERIOR PRIMAL-DUAL DENGAN LANGKAH FULL-NEWTON: STUDI KASUS MASALAH KLEE-MINTY DENGAN KENDALA REDUNDANT TAKNEGATIF
IRWAN NURSOLIH
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013 iii
Judul Nama NIM
: Metode Interior Primal-Dual dengan Langkah Full-Newton: Studi Kasus Masalah Klee-Minty dengan Kendala Redundant Taknegatif : Irwan Nursolih : G54080062
Menyetujui,
Pembimbing I
Pembimbing II
Dr. Ir. Bib Paruhum Silalahi, M.Kom. NIP. 19670101 199203 1 004
Muhammad Ilyas, S.Si, M.Sc.
Dra. Farida Hanum, M.Si.
Donny Citra Lesmana, S.Si., M.Fin.Math.
NIP 19651019 199103 2 002 NIP 19790227 200501 1 001
Mengetahui: Ketua Departemen
Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004
Tanggal Lulus :
iv
KATA PENGANTAR Puji dan syukur penulis panjatkan ke hadirat Allah SWT atas segala nikmat, karunia, izin, dan pertolongan-Nya sehingga penulisan skripsi ini berhasil diselesaikan. Sholawat dan salam semoga senantiasa tercurahkan kepada nabi besar Muhammad SAW. Terima kasih penulis ucapkan kepada : 1. Keluarga tercinta, mamahku Nanah Robianah dan apaku Misbah Munir atas segala doa, kasih sayang, dukungan, pengorbanan, dan nasihat yang senantiasa mengiringi perjalanan penulis selama ini, kakak-kakakku Pipit Nurliana, Dani Rahman Iskandar, Dini Apriani, Dadan Gumarna Perwira dan adikku Rahmi Solihah atas semangat, nasihat dan dukungannya, 2. Bapak Dr. Ir. Bib Paruhum Silalahi, M.Kom dan Bapak Muhammad Ilyas, S.Si, M.Sc selaku dosen pembimbing, atas segala kesabaran dan masukannya selama membimbing penulis, dan kepada Bapak Drs. Siswandi, M.Si. selaku dosen penguji, 3. Teman-teman satu bimbingan : Nurhayati, Rini, Brammanto atas dukungan, bantuan dan kerjasamanya selama ini, 4. Sahabat-sahabat: Ari, Ridwan, Ijun, Haryanto, Arbi, Khafizd, Beni, Herlan, Dono, Dahen, Fuka, Aci, Nurhadi, Chastro, Haerul, Isti, Deris, Tika atas dukungan, suka-duka, nasihat, bantuan dan semangat selama ini, 5. Teman-teman lorong 10: Yusak, Sona, Ibay, Jimbo, Hendro, Charis, Galer, Gentot, Gondrong, Cunduy, Jun, Irvan, Batak, Kamil, Elbi, Wahyu, Hendra, Roy, Ari, Heru, Oji, Syarif, Ksat, Ai, Blair, Ido, Stephen, Stevan, Irvan cantik, Jay, Adit Nugraha, Adit, Najif, Joni, Fika, Tomi atas kenangan, suka-duka, dukungan, nasihat selama ini. 6. Teman-teman mahasiswa Matematika angkatan 45: Bolo, Wahid, Wulan, Gita, Fenny, Isna, Santi, Yunda, Mega, Putri, Fitriyah, Prama, Dimas, Erik, Rian, James, Maya, Icong, Wijay, Edi, Fikri, Ali, Tiwi, Ade, Fina, Ito, Rianiko, Aisyah, Heru, Ana, Vivi, Risman, Nova, Rahma, Dewi, Mya, Dini, Dina atas segenap dukungan, suka-duka dan kebahagiaan selama penulis menempuh studi di Departemen Matematika IPB, 7. Kakak-kakak mahasiswa Matematika: Chabi, Deni, Amin, Ali, Peli, Tendi, Ihsan, Aswin, Della, Ima, Dora, Ndev, Pandi, Eni, Ruhiyat, Aze, Yuyun, Wewe, Denda, Dandi, Fajar, Agung, Cumi, Rofi, Aqil, Dian, Slamet, Adi, Apri, Pepi, Elly, Ucok, Wira, Kunto, Copi, Copa, Ririh, Imam, Abe, Selvi, Fani, Ayung, Mutya, Rachma, Olih, Lukman, Tyas atas segenap nasihat dan dukungan selama ini, 8. Adik-adik mahasiswa matematika: Dian, Bari, Andri, Ivonne, Danti, Fachri, Rudi, Desyi, Ipul, Amel, Mirna, Hendra, Chou, Rohmat, Jodi, Windi, Uwi, Dewi, Nia, Reni, Ami, Fenny, Dio, Rangga, Syahrul, Qowi, Dita, Widia atas dukungan dan bantuan selama ini, 9. Kakak-kakak mahasiswa Matematika angkatan 43 dan 44 yang tidak bisa disebutkan satu per satu, adik-adik mahasiswa Matematika angkatan 46 dan 47, dan seluruh pengajar, pegawai, dan staf Departemen Matematika IPB, 10. Pihak-pihak lain yang telah membantu penyusunan skripsi ini, yang tidak dapat disebutkan satu per satu. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat.
Bogor, Maret 2013
Irwan Nursolih
v
RIWAYAT HIDUP Penulis dilahirkan di Cianjur pada tanggal 8 Juni 1990 dari pasangan Misbah Munir dan Nanah Robianah. Penulis merupakan anak ketiga dari empat bersaudara. Pada tahun 2005 penulis lulus dari SMP Negeri 1 Cipanas. Tahun 2008 penulis lulus dari SMA Negeri 2 Cianjur dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih Program Studi Matematika, Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis pernah mengikuti beberapa kegiatan kemahasiswaan diantaranya organisasi Unit Kegiatan Kampus (UKM) Bola Voly IPB tahun 2008-2010 dan Gugus Mahasiswa Matematika (GUMATIKA) IPB. Penulis juga aktif pada beberapa kepanitiaan yaitu menjadi panitia Pesta Sains, SPIRIT, Bakti Sosial, Masa Perkenalan Fakultas (MPF), Masa Perkenalan Departemen (MPD).
vi
DAFTAR ISI Halaman DAFTAR TABEL .................................................................................................................... viii DAFTAR GAMBAR ................................................................................................................ viii DAFTAR LAMPIRAN ............................................................................................................ viii I PENDAHULUAN 1.1 Latar Belakang ............................................................................................................... 1 1.2 Tujuan ........................................................................................................................... 2 II LANDASAN TEORI .............................................................................................................. 2 III PEMBAHASAN 3.1 Kondisi Optimal bagi Optimasi Linear ........................................................................... 7 3.2 Central Path.................................................................................................................. 7 3.3 Langkah Newton ........................................................................................................... 8 3.3 Ukuran Kedekatan....................................................................................................... 10 IV STUDI KASUS .................................................................................................................... 12 V SIMPULAN DAN SARAN 5.1 Simpulan ..................................................................................................................... 16 5.2 Saran ........................................................................................................................... 16 DAFTAR PUSTAKA ................................................................................................................ 17 LAMPIRAN .............................................................................................................................. 18
vii
DAFTAR TABEL Halaman
Tipe-tipe kendala redundant .................................................................................................... 1
DAFTAR GAMBAR Halaman
1 Masalah KM tanpa penambahan kendala redundant .............................................................. 13 2 Masalah KM dengan penambahan kendala redundant ........................................................... 15
DAFTAR LAMPIRAN Halaman 1 Langkah full-Newton ............................................................................................................ 19 2 Pembangkitan gambar 1 ....................................................................................................... 19 3 Pembangkitan gambar 2. ...................................................................................................... 20
viii
1
I PENDAHULUAN 1.1 Latar Belakang Optimasi dalam matematika mengacu pada pemillihan elemen terbaik dari beberapa himpunan alternatif yang tersedia. Dalam kasus yang paling sederhana berarti memecahkan masalah-masalah dimana orang berusaha meminimumkan atau memaksimumkan fungsi yaitu dengan cara yang sistematis memilih nilai-nilai variabel integer atau real dari himpunan yang diperbolehkan (Nematollahi 2008). Salah satu bagian dari optimasi adalah optimasi linear yang mempelajari suatu masalah dimana seseorang ingin meminimumkan atau memaksimumkan suatu fungsi tujuan yang berbentuk linear, dengan kendala-kendala yang dinyatakan dalam persamaan dan/atau pertidaksamaan linear. Optimasi Linear (OL) muncul menjadi model matematika setelah perang dunia ke-2, yaitu ketika Dantzig memaparkan metode simpleks untuk menyelesaikan masalah optimasi linear. Daerah fisibel dari masalah OL adalah suatu polihedron. Untuk memperoleh solusi optimal, metode simpleks bergerak dari verteks ke verteks. Metode ini dirancang sedemikian rupa sehingga dalam pergerakan dari satu verteks ke verteks selanjutnya, nilai fungsi tujuan berubah secara monoton menuju nilai optimal. Kesuksesan metode simpleks telah menimbulkan beberapa pertanyaan. Salah satu pertanyaan pada saat itu adalah: apakah ada masalah optimasi linear yang memerlukan iterasi eksponensial bila diselesaikan dengan metode simpleks. Pertanyaan tersebut dijawab pada tahun 1972 oleh Klee dan Minty dengan memberikan contoh masalah OL dengan 2n pertidaksamaan, dimana metode simpleks memerlukan 2n 1 iterasi untuk menyelesaikan permasalahan Klee-Minty (Silalahi 2011). Kelemahan metode simpleks, memacu penelitian untuk mencari metode lain yang dapat menyelesaikan masalah OL dengan waktu polinomial seiring bertambahnya jumlah pertidaksamaan. Pada tahun 1978 Kachiyan mengusulkan metode ellipsoid. Metode ini merupakan algoritme waktu polinomial pertama untuk masalah OL. Tetapi hasil yang diperoleh tidak seperti yang diharapkan, dalam aplikasinya metode simpleks lebih baik dari metode ellipsoid.
Terobosan yang sungguh-sungguh efektif untuk menyelesaikan masalah OL terjadi pada tahun 1984, ketika Karmarkar mengusulkan metode waktu polinomial yang dikenal dengan metode projektif Karmarkar untuk menyelesaikan masalah OL. Secara teori waktu komputasi dan aplikasinya metode Karmarkar lebih baik dari metode ellipsoid. Karmarkar memulai revolusi dalam bidang optimasi, dengan munculnya penelitianpenelitian pengoptimuman dengan menggunakan metode interior (MI). Tidak seperti metode simpleks, metode interior bergerak di dalam interior dari domain secara monoton menuju solusi optimal (Silalahi 2011). Dalam perkembangannya Metode interior dikembangkan dengan beberapa pendekatan, yang dikelompokkan dalam tiga kategori,yaitu: metode affine scaling, metode potential reduction (barrier) dan metode central trajectory (path-following) (Mitchell 1998). Nematollahi dkk, kemudian memberikan contoh kasus-kasus terburuk untuk penyelesaian optimasi linear menggunakan metode interior, yaitu dengan menambahkan kendala-kendala redundant pada masalah Klee-Minty (KM). Penelitian-penelitian mereka dapat dilihat pada Tabel di bawah, kolom pertama menyatakan jenis kendala redundant yang digunakan dan kolom kedua menyatakan jumlah kendala redundant. Dengan adanya penambahan kendala redundant ini dapat mengubah central path dan analytic center. Tipe kendala redundant
Jumlah pertidaksam aan
Referensi
yk 1 yk d
O(n2 26n )
Deza dkk. 2006
yk 1 yk d
O(n23n )
Deza dkk. 2009
yk 1 yk dk
O(n3 22n )
Deza dkk. 2008
yk d
Nematollahi dkk. 2008a 2 Nematollahi n yk 0 O(2 ) dkk. 2008b Tabel tipe-tipe kendala redundant
O( n 2 2 n )
2
Dalam karya ilmiah ini akan diamati kendala redundant Klee-Minty tipe yk 0 (kendala redundant tipe lima pada Tabel), yaitu semua kendala redundantnya menyentuh daerah fisibel, yang akan di analisa menggunakan metode interior (MI) dengan pendekatan central trajectory (pathfollowing). Dalam pengamatan masalah KleeMinty beserta kendala redundantnya digunakan bantuan MATLAB R2008b.
1.2 Tujuan Penulisan karya ilmiah ini bertujuan untuk: (i) Membahas metode interior primaldual dengan langkah full-Newton (ii) Mengamati pergerakan central path pada masalah KM bila ditambahkan kendala redundant tipe yk 0 , berdasarkan metode interior primaldual dengan langkah full-Newton menggunakan bantuan MATLAB R2008b.
II LANDASAN TEORI 2.1 Sistem Persamaan Linear Definisi 1 (Fungsi Linear) Suatu fungsi f dalam variabel-variabel
x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c2 ,..., cn , f dapat ditulis sebagai
f ( x1 , x2 ,..., xn ) c1 x1 c2 x2
... cn xn . (Winston 2004)
dengan 𝑎𝑖𝑗 dan 𝑏𝑖 (1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛) adalah bilangan-bilangan real dan 𝑥1 , 𝑥2 ,…, 𝑥𝑛 adalah variabel. SPL ini disebut SPL berukuran 𝑚 × 𝑛. (Leon 2001) Selain itu SPL juga dapat ditulis dalam bentuk 𝑨𝐱 = 𝐛 dengan matriks 𝑨 berukuran 𝑚 × 𝑛 dan vektor kolom b berukuran 𝑚 × 1, seperti berikut ini: 𝑎11 𝑎12 ⋯ 𝑎1𝑛 𝑎21 𝑎22 ⋯ 𝑎2𝑛 𝑨= ⋯ ⋯ ⋱ ⋮ 𝑎𝑚1 𝑎𝑚2 ⋯ 𝑎𝑚𝑛
Definisi 2 (Pertidaksamaan dan Persamaan Linear) Untuk sebarang fungsi linear f dan sembarang bilangan c , pertidaksamaan
f ( x1 , x2 ,..., xn ) c
, xn ) c
adalah
dan
f ( x1 , x2 ,...
pertidaksamaan
sedangkan suatu persamaan
linear,
f ( x1 , x2 ,...
, xn ) c merupakan persamaan linear. (Winston 2004) Definisi 3 (Sistem Persamaan Linear) Suatu sistem persamaan linear (SPL) dari 𝑚 persamaan dan 𝑛 variabel adalah sistem dengan bentuk 𝑎11 𝑥1 + 𝑎12 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1 , 𝑎21 𝑥1 + 𝑎22 𝑥1 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏2 , ⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚 .
dan 𝑏1 𝑏2 b= , ⋮ 𝑏𝑚 matriks 𝑨 disebut matriks koefisien dan vektor 𝐛 disebut vektor konstanta. Penyelesaian SPL tersebut adalah vektor kolom 𝐱 berukuran 𝑛 × 1 yaitu 𝑥1 𝑥2 x= ⋮ , 𝑥𝑛 yang memenuhi semua persamaan linear dalam sistem. Vektor yang demikian disebut vektor penyelesaian. (Leon 2001)
3
2.2 Optimasi Linear Definisi 4 (Optimasi linear) Optimasi linear adalah kegiatan merencanakan untuk mendapatkan hasil yang optimal. Model optimasi linear (OL) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear. (Nash & Sofer 1996) Suatu OL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut: Definisi 5 (Bentuk Standar suatu OL) Suatu optimasi linear dikatakan berbentuk standar jika dapat dituliskan sebagai: Minimumkan z = cTx terhadap Ax = b x ≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n, yang disebut juga sebagai matriks kendala. (Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. Definisi 6 (Daerah Fisibel) Daerah fisibel suatu OL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada OL tersebut. (Winston 2004) Definisi 7 (Solusi Optimal) Untuk masalah maksimisasi, solusi optimal suatu OL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. untuk masalah minimisasi, solusi optimal suatu OL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.3 Dualitas Terkait dengan suatu masalah optimasi linear, terdapat masalah optimasi linear lain yang berpadanan. Kedua masalah ini dikenal dengan masalah primal dan masalah dual dari optimasi linear. Berikut ini adalah contoh bentuk normal dari masalah primal untuk kasus maksimisasi Fungsi objektif maks 𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 .
Kendala 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 , ⋮ 𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚 , 𝑥𝑗 ≥ 0
𝑗 = 1,2, … , 𝑛 .
Berikut ini adalah bentuk normal dari masalah dual untuk kasus maksimisasi di atas: Fungsi objektif min 𝑤 = 𝑏1 𝑦1 + 𝑏2 𝑦2 + ⋯ + 𝑏𝑚 𝑦𝑚 . Kendala 𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≥ 𝑐1 , ⋮ 𝑎1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + ⋯ + 𝑎𝑚𝑛 𝑦𝑚 ≥ 𝑐𝑛 , 𝑦𝑖 ≥ 0
𝑖 = 1,2, … , 𝑚 . (Winston 2003)
Semua masalah optimasi linear bisa ditransformasikan menjadi bentuk standar dengan cara menambahkan variabel baru. Bentuk standar dari masalah primal (P) adalah : min 𝐜 𝑻 𝐱: 𝑨𝐱 = 𝐛, 𝐱 ≥ 0 ….. (P) dengan 𝐜 ∈ ℝ𝒏 , 𝑨 ∈ ℝ𝑚×𝑛 .
𝐱 ∈ ℝ𝑛 ,
𝐛 ∈ ℝ𝑚
dan
Bentuk standar dari masalah dual (D) adalah: maks 𝐛𝑇 𝐲 ∶ 𝑨𝑇 𝐲 + 𝐬 = 𝐜, 𝐬 ≥ 0 …..(D) dengan 𝐬 ∈ ℝ𝑛 dan 𝐲 ∈ ℝ𝑚 . Proposisi 2.1 Jika x dan (y,s) masing-masing fisibel untuk (P) dan (D), maka 𝐜 𝑻 𝐱 − 𝐛𝑻 𝐲 = 𝐱 𝑻 𝐬 ≥ 0. 𝐱 𝑻 𝐬 disebut kesenjangan dualitas, berakibat 𝐜 𝑻 𝐱 adalah batas atas untuk nilai optimal dari (D), jika ada, serta 𝐛𝑻 𝐲 adalah batas bawah untuk nilai optimal dari (P), jika ada. Selanjutnya, jika kesenjangan dualitas adalah nol maka x adalah solusi optimal dari (P) dan (y,s) adalah solusi optimal dari (D). Bukti dapat dilihat di Roos (2006). (Roos et al. 2006)
4
kolom. Vektor x dan s didefinisikan sebagai berikut
2.4 Matriks Definisi 8 (Ortogonalitas di n ) Misalkan x dan y dua vektor didalam n dan dipandang sebagai matriks n1 , x dan y disebut ortogonal jika xT y 0 . (Leon 1998)
Definisi 9 (Hasil Kali Skalar di n ) Misalkan x, y n dengan x1 y1 x y x 2 y 2, xn yn maka hasil kali skalar dari x dan y adalah
xT y x1 y1 x2 y2 ... xn yn . (Leon 1998) Definisi 10 (Ruang Nol) Misalkan 𝑨 adalah matriks 𝑚 × 𝑛, dan 𝑁(𝑨) menyatakan himpunan semua penyelesaian dari sistem homogen 𝑨𝐱 = 𝟎. Jadi: 𝑁 𝑨 = 𝐱 ∈ ℝ𝑛 𝑨𝐱 = 𝟎 Dengan tujuan untuk memperlihatkan bahwa 𝑁 𝑨 adalah ruang bagian dari ℝ𝑛 jika 𝐱 ∈ 𝑁 𝑨 dan 𝛼 suatu scalar, maka: 𝑨 𝛼𝐱 = 𝛼𝑨𝐱 = 𝛼𝟎 = 𝟎 Sehingga 𝛼𝐱 ∈ 𝑁 𝑨 , jika 𝐱 dan 𝐲 adalah elemen-elemen dari 𝑁 𝑨 , maka: 𝑨 𝐱 + 𝐲 = 𝑨𝐱 + 𝑨𝐲 = 𝟎 + 𝟎 = 𝟎 Oleh karena itu 𝐱 + 𝐲 ∈ 𝑁 𝑨 . Ini berarti bahwa 𝑁 𝑨 adalah ruang bagian dari ℝ𝑛 . Himpunan semua penyelesaian dari sistem homogen 𝑨𝐱 = 𝟎 membentuk ruang bagian dari ℝ𝑛 . Ruang bagian 𝑁 𝑨 disebut kernel (ruang nol atau null space) dari 𝑨. (Leon 2001) Definisi 11 (Ruang Baris) Jika 𝑨 adalah matriks 𝑚 × 𝑛, maka ruang bagian dari ℝ1×𝑛 yang direntang oleh vektorvektor baris dari 𝑨 disebut ruang baris dari 𝑨. (Leon 2001)
𝑥1 𝑠1 𝑥2 𝑠2 x= ⋮ , s= ⋮ 𝑥𝑛 𝑠𝑛 dan notasi diag(x) adalah matriks diagonal dengan unsur diagonal utama ialah vektor x, begitu juga dengan diag(s). 𝑥1 0 𝑿 = diag 𝐱 = ⋮ 0
0 𝑥2 ⋯ ⋯
𝑠1 0 𝑺 = diag 𝐬 = ⋮ 0
0 ⋯ 0 𝑠2 0 ⋮ ⋯ ⋱ 0 ⋯ 0 𝑠𝑛
⋯ 0 0 ⋮ ⋱ 0 0 𝑥𝑛
Maka hadamard product dari x dan s adalah 𝒙𝟏 𝒔𝟏 𝒙 𝒔 𝐱𝐬 = 𝑿𝐬 = 𝑺𝐱 = 𝟐 𝟐 . ⋮ 𝒙𝒏 𝒔𝒏 Dengan kata lain, hadamard product adalah perkalian antara unsur dengan unsur yang seletak (componentwise) dari dua buah vektor yang berukuran sama, tetapi tidak harus persegi. Componentwise berlaku juga pada operasi pembagian 𝐱 𝐬 dan operasi akar untuk vektor x dan vektor s. x1 s 1 x 𝐱 2 = s2 𝐬 xn s n
𝐱 = 𝑥𝑖 =
x1 x2 xn
(Roos et al. 2006) Definisi 12 (Hadamard Product) Misalkan Vektor 𝐱, 𝐬 ∈ ℝ𝑛 , dan matriks 𝑿, 𝑺 adalah matriks m n dengan 𝑚 menyatakan banyak baris dan 𝑛 menyatakan banyak
5
2.5 Masalah Redundant Klee-Minty (KM)
2.7 Metode Newton
Definisi 13 Masalah Klee-Minty (KM) Suatu permasalah yang diberikan oleh Klee dan Minty yang kemudian dikenal dengan masalah Klee-Minty (KM) yaitu :
Metode Newton adalah salah satu prosedur iteratif untuk menyelesaikan masalah taklinear. Misalkan akan dicari solusi persamaan f x 0 , dengan f x taklinear, x x1 , x2 ,, xn dan fungsi f adalah fungsi
min 𝑦𝑛 kendala 𝑦𝑘−1 ≤ 𝑦𝑘 ≤ 1 − 𝑦𝑘−1 , 𝑘 = 1,2, … … . . , 𝑛.
yang kontinu dan terdiferensialkan. Metode Newton diturunkan dari ekspansi deret Taylor orde pertama, sebagai berikut.
f x
1
dimana 𝑦0 = 0, ∈ (0, 2 ) (Klee & Minty 1972) Definisi 14 (Kendala Redundant) Kendala redundant adalah kendala yang tidak mengubah daerah fisibel dari masalah optimasi linear.
k 1
f x x k
x
k
f ' xk 1!
Sehingga
f xk 1 f xk xk 1 xk f ' xk k
dengan x adalah hampiran awal. Kemudian
2.6 Kompleksitas dan Estimasi Order
k 1
0,
f x
k 1
untuk
mencari
dilakukan
hampiran
dengan
mencari
Definisi 15 (Kompleksitas) Fungsi kompleksitas waktu f (n) adalah fungsi yang mengukur banyaknya operasi dalam suatu algoritma yang mempunyai variabel input n . (Guritman & Supriyo 2004)
solusi
Definisi 16 (Dominasi Fungsi)
Metode Newton dapat juga digunakan untuk mencari solusi hampiran dari suatu sistem fi x 0, i 1, 2,, n, dimana f i suatu fungsi taklinear.
Misalkan f , g : . Dapat dikatakan bahwa g mendominasi f (atau f didominasi g ), jika ada konstanta m
dan konstanta k sedemikian rupa f (n) m g (n) , sehingga dimana
Dari persamaan di atas diperoleh x
Misal
(Guritman & Supriyo 2004)
dengan daaerah asal dan daerah hasil yang didominasi oleh g . (Guritman & Supriyo 2004)
k 1
. f 'x f xk
x
matriks
k
k
J x k adalah
Jacobi seperti berikut ini:
n k , n .
Big-O f didominasi oleh g , dapat dikatakan f berorder g dan ditulis sebagai f O( g ) . O( g ) dibaca order atau big-O g merepresentasikan himpunan semua fungsi
f xk xk 1 xk f ' xk 0.
J x
k
f1 x 1 f 2 y1 f n x 1
f1 x2 f 2 x2 f n x2
f1 xn f 2 xn . f n xn
matriks
6
Kemudian dengan menggunakan deret Taylor orde pertama di sekitar titik x k diperoleh
Contoh 1 Akan dicari solusi hampiran dari suatu sistem fi x 0 , untuk i 1,2, dengan
f1 x, y x 2 xy dan f 2 x, y x xy adalah fungsi taklinear. Metode yang digunakan adalah metode Newton dengan 1 kali iterasi.
f xk 1 f xk J xk d 0
dengan d xk 1 xk iterasi.
dan k
menyatakan
(Jensen & Bard 2002)
Penyelesaian: Dengan hampiran awal x0 y 0 1 diperoleh
f1 x1 , y1 f x 0 , y 0 J x 0 , y 0 d
x1
x
1
x1
2
2
2
x1 y1 x 0
2
x0 y 0 2 x0 y 0
x1 x 0 0 x0 y1 y 0
x1 1 0 x y 1 1 3 1 y1 1 1 1
x1 y1 3x1 y1 2 0 3 x1 y1 2.
f 2 x1 , y1 f x 0 , y 0 J x 0 , y 0 d x1 x 0 0 x0 y1 y 0 1 x 1 0 x x1 y1 1 1 2 1 y1 1
x x1 y1 x x 0 y 0 1 y 0
x x1 y1 2 x1 y1 1 0 2 x1 y1 1.
Kedua persamaan taklinear di atas telah menjadi persamaan linear. Kemudian eliminasikan kedua persamaan tersebut sehingga diperoleh nilai x1 1 dan y1 1 .
7
III PEMBAHASAN 3.1 Kondisi Optimal bagi Optimasi Linear Daerah fisibel dari masalah primal ( P) dan masalah dual dan :
D
: x : Ax b, x 0 ,
dinotasikan oleh
: (y, s) : AT y s c, s 0 .
Jika adalah himpunan kosong maka ( P) infisibel, selainnya fisibel. Selanjutnya akan digunakan istilah yang sama untuk masalah dual ( D) . Daerah interior dari dan dinotasikan oleh o dan o : o : x : Ax b, x 0 ,
o : (y, s) : AT y s c, s 0 .
Teorema 3.1 Jika P dan D fisibel maka kedua masalah memiliki solusi optimal; kemudian x dan y, s , merupakan solusi optimal jika dan hanya jika xT s 0 . Bukti : Mengacu pada proposisi (2.1), x fisibel untuk (P) dan (y,s) fisibel untuk (D), maka 𝐜 𝑻 𝐱 − 𝐛𝑻 𝐲 = 𝐱 𝑻 𝐬 ≥ 0. Dimana 𝐜 𝑻 𝐱 batas atas untuk nilai optimal dari (D) dan 𝐛𝑻 𝐲 batas bawah untuk nilai optimal dari (P), untuk memperoleh solusi optimal haruslah 𝐜 𝑻 𝐱 = 𝐛𝑻 𝐲 sehingga 𝐱 𝑻 𝐬 = 0. Berdasarkan pada Teorema 3.1, menemukan solusi optimal dari ( P) dan ( D) adalah setara dengan menyelesaikan sistem :
Ax b, T A y s c, xs 0.
x 0, s 0,
(3.1)
masalah primal ( P) dan baris kedua menunjukkan kendala fisibel untuk masalah dual ( D) . Persamaan terakhir merupakan kondisi pelengkap. Kondisi pelengkap adalah taklinier dan mengakibatkan sistem (3.1) sulit untuk diselesaikan. 3.2 Central path Agar sistem (3.1) dapat diselesaikan, kondisi pelengkap dapat diganti dengan xs e , dimana adalah sebarang bilangan positif dan e adalah vektor yang semua unsurnya bernilai satu. Kendala baru ini disebut kondisi pemusatan pada . Sehingga dihasilkan sistem: Ax b, x 0, T A y s c, s 0, xs e.
Jika sistem (3.2) memiliki sebuah solusi untuk suatu > 0, maka 0 dan 0 adalah himpunan tak kosong. Pada kondisi ini dan memenuhi kondisi titik interior. Jika dan memenuhi kondisi titik interior maka sistem (3.2) memiliki sebuah solusi untuk sebarang > 0. Oleh karena itu jika sistem (3.2) memiliki sebuah solusi untuk suatu > 0, maka sistem (3.2) memiliki solusi untuk semua > 0. Dan ini terjadi jika dan hanya jika kondisi titik interior terpenuhi. Ulasan yang lebih lengkap dan pembuktian pernyataan di atas dapat dilihat pada buku (Roos 2006). Solusi untuk setiap dinotasikan dengan x( ) , y ( ) , dan s( ). solusi dari x( disebut -center dari ( P) dan solusi dari (y( ), s( )) disebut -center dari ( D) . Jika bergerak sepanjang (0, ) maka
x( membentuk suatu kurva pada 0 yang disebut central path dari ( P) dan ditulis dengan
Dengan xs adalah perkalian komponen (Hadamard product) dari vektor x dan s dan 0 adalah vektor nol. Ketiga persamaan pada sistem (3.1) adalah kondisi optimal untuk optimasi linear. Baris pertama adalah kendala fisibel untuk
(3.2)
x : 0, .
Dengan cara
yang sama, (y( ), s( )) membentuk suatu kurva pada 0 yang disebut central path dari dan ditulis dengan D
{(y( ), s( )) : } .
8
Jika maka x( ) , y ( ) dan s( )
Ax Ax b,
konvergen ke solusi dari sistem (3.1), artinya central path konvergen ke himpunan solusi optimal ( P) dan ( D) . Pada sisi lain, jika
b Ax b,
x( ) dan (y( ), s( ))
maka
konvergen ke apa yang disebut analytic center ( P) dan ( D) . Definisi formal dari analytic
Ax b b,
Ax 0,
3.3
kemudian untuk persamaan kedua menjadi:
center ( P) dan ( D) adalah sebagai berikut.
AT (y y) s s c, Jika kondisi titik interior dipenuhi maka:
AT y AT y s s c, (i) Analytic
center
primal
argmaksx ℯ log 𝐱 : 𝐱 ∈ 𝑇
(ii) Analytic
center
0
dual
adalah dan adalah
argmakss ℯ 𝑇 log 𝐬 : 𝐬 ∈ 0 . 3.3 Langkah Newton Diberikan pasangan primal-dual fisibel (x, (y , s)) , ingin ditetapkan arah pencarian x , y , dan s sehingga (x x , y y,
s s) memenuhi sistem (3.2). Dengan kata lain, A(x x) b, T A (y y ) s s c, (x x)(s s) e.
Karena Ax b dan AT y s c , jika dijelaskan secara eksplisit maka sistem ini akan menjadi : Untuk persamaan pertama dari sistem tersebut akan menjadi:
A(x x) b,
AT y s AT y s c, c AT y s c, AT y s 0.
3.4
selanjutnya persamaan terakhir dari sistem tersebut akan menjadi: (x x)(s s) e, xs xs sx xs e, xs sx xs e xs. 3.5 Dari persamaan (3.3), (3.4), dan (3.5) diperoleh sistem: Ax 0, T A y s 0, sx xs xs e xs. Persamaan ketiga pada sistem di atas merupakan persamaan taklinear, karena faktor kuadrat ΔxΔs . Untuk menyelesaikan sistem di atas, persamaan ketiga dilinearkan menggunakan metode Newton sebagai berikut:
9
f x, s sx xs xs e xs
dengan J x0 , s0 s s0 x x0
x1 x0 dan d s1 s0
saat k 0
sehingga
f x1 , s1 f x0 , s0 J x0 , s0 d 0 x1 x0 sx1 xs1 x1s1 e xs sx0 xs 0 x 0 s 0 e xs s s 0 x x 0 0 s1 s0
dengan hampiran awal x0 s0 0 x1 sx1 xs1 x1s1 e xs e xs s x 0 s1 sx1 xs1 x1s1 e xs sx1 xs1 e xs 0 sx1 xs1 e xs 0 sx1 xs1 e xs setelah dilinearkan persamaan ketiga menjadi sx xs e xs
Sehingga diperoleh sistem linear sebagai berikut: Ax 0, T A y s 0, sx xs e xs.
3.6
Metode interior primal-dual dengan langkah full-Newton disajikan seperti di bawah ini: Input: parameter akurasi ϵ > 0;
Matriks koefisien dari sistem linear tersebut adalah:
parameter kedekatan 1;
x , y , s fisibel, x 0
A 0 T 0 A S 0
0 x 0 I y 0 X s e xs
dengan X diag (x) dan S diag (s), serta vektor x dan s positif. Solusi dari sistem persamaan linear x, y, s dinamakan arah primal-dual langkah Newton. Dengan mengambil langkah disekitar arah ini,
ditemukan iterasi baru (x ,(y, s )) . Iterasi baru ini diberikan oleh x x x, 3.7 y y y , s s s. Iterasi (3.7) disebut dengan langkah fullNewton.
0
0
0
T
s 0 n 0
dan x0 , y 0 ; 0 ; parameter update barrier , 0 1. begin
x : x0 ; s : s0 ; y : y0 ; 0 ; while n ϵ do
: 1 ; x : x x; y : y y; s : s s;
endwhile end
10
Pada subbab selanjutnya akan dibahas mengenai ukuran kedekatan. Ukuran kedekatan ini digunakan pada pemrograman, untuk memperoleh ukuran kedekatan sistem (3.6) dinyatakan dalam sistem lain yang setara. Ukuran kedekatan digunakan untuk menjamin bahwasanya pada setiap iterasi
selalu diperoleh (x ,(y , s )) yang fisibel dan juga digunakan untuk menganalisis kompleksitas algoritme. Pembahasan mengenai analisis kompleksitas algoritme, di luar cakupan karya ilmiah ini. 3.4 Ukuran Kedekatan Dalam proses menuju solusi optimal, dengan menggunakan langkah full-Newton, dibangkitkan barisan titik-titik di sekitar central path. Diperlukan suatu alat untuk mengukur kedekatan dari (x,(y, s)) ke center . Sebelum mendefinisikan ukuran kedekatan ini, sistem linear (3.6) diubah, dengan penskalaan x, y, dan s ke d x , d y dan ds sebagai berikut: dx
vx y vs , dy , ds , x s
3.8
ADd x 0,
kemudian persamaan kedua dari sistem (3.6) menjadi
AT y s 0, s AT d y d s 0, v v AT diag d y d s 0, s
xs AT diag d y d s 0, s 1
xs AT diag s2
d y d s 0,
x AT diag d d s 0, s y AD d y ds 0,
3.9
T
selanjutnya persamaan terakhir sistem (3.6) sama dengan
dengan v
xs
.
sx xs e xs,
Jika didefinisikan D diag( x / s ) maka bila dipaparkan secara eksplisit persamaan pertama dari sistem (3.6) sama dengan Ax 0,
x A diag d x 0, v
x A diag 1 d x 0, xs
x A diag d 0, s x
x s s d x x d s e xs, v v
s x d x s d e xs, xs x xs s xs d x xs ds e xs,
xs d x d s e xs, d x ds
d x ds
e xs , xs
xs
xs
,
11
d x ds v 1 v.
3.10
Setelah didapatkan hasilnya, maka dari persamaan 3.8 , 3.9 , dan 3.10 diperoleh sistem:
ADd x 0, T ( AD) d y d s 0, d x d s v 1 v.
(3.11)
Dua persamaan pertama dari sistem (3.11) menunjukkan bahwa vektor d x dan ds merupakan ruang nol dan ruang baris dari matriks AD . Kedua ruang ini adalah ortogonal, sehingga d x dan ds orthogonal, yang berimplikasi
dx
2
ds
2
d x ds
2 2
= v 1 v . Perhatikan bahwa d x , d s ,(dan juga d y ) adalah nol jika dan hanya jika v-1 - v 0 , yang hanya terjadi jika v = e , dan kemudian x, y dan s bertepatan dengan center masing-masing. Oleh karena itu untuk mengukur jarak dari (x,(y, s)) ke center , digunakan x, s; yang didefinisikan oleh
x, s; : v) :
2 1 1 v v . 2
(3.12)
Untuk sebarang 0 , neighborhood dari center diberikan oleh himpunan
x, y, s : x P, (y, s) D, (x, s; ) .
12
IV STUDI KASUS Pada bagian ini akan diberikan dua Contoh kasus pertama untuk kasus tanpa contoh kasus yang berbeda pada masalah kendala redundant: 1 Klee-Minty (KM), dengan mengambil , min y2 3 kendala 0 y1 1, n 2 dan y0 0 . Kedua contoh kasus ini telah dijamin oleh ukuran kedekatan, sehingga 1 1 y1 y2 1 y1. hasil yang didapatkan akan selalu berada di 3 3 daerah fisibel. Dengan menggunakan definisi analytic center, untuk menentukan analytic center maka kendala masalah KM tersebut dinyatakan sebagai berikut: y1 0, 1 y1 0, y2 1
1 y1 0, 3
1 y1 y2 0. 3
Kemudian digunakan rumus untuk mencari analytic center: log y1 log1 y 1 1 A1 =argmaks y 1 1 1 1 log y2 y1 3 1 log1 y1 y2 3 1 1 A1 argmaks y log y1 log 1 y1 log y2 y1 log 1 y1 y2 3 3
4.1
Untuk memperoleh titik analytic center turunkan persamaan (4.1) terhadap y1 dan y2 A1 0 y1
1 1 1 1 3 3 0, y1 1 y1 y 1 y 1 1 y y 2 1 1 2 3 3 A1 0 y2 1 1 0. 1 1 y2 y1 1 y1 y2 3 3
Dengan menyelesaikan persamaan (4.1) diperoleh titik analytic center y1 0.317, y2 0.5 .
13
Gambar 1 menunjukkan masalah KM tanpa penambahan kendala redundant. Gambar 1 diperoleh dengan menggunakan MATLAB R2008b dan memperlihatkan central path bergerak sepanjang 0, , ketika central path konvergen ke analytic center di titik (0.317, 0.5) dan jika 0 maka central path konvergen ke solusi optimal di titik (0,0). 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Gambar 1. Masalah KM tanpa penambahan kendala redundant
Untuk contoh kasus kedua akan diberikan penambahan kendala redundant y1 0 dan y2 0 , dengan besarnya pengulangan ditentukan menggunakan parameter 1 , : 4 n 1 2 4 2n h : , ,, n( n 1)/2 n . 2 Parameter di atas digunakan oleh Nematollahi dkk dalam jurnalnya (Nematollahi dkk. 2008), dengan menggunakan parameter tersebut Nematollahi dkk. membuktikan bahwa central path akan mengunjungi cukup dekat ke semua verteks dari daerah fisibel, namun penggunaan parameter tersebut masih secara teori. Pada T
contoh kasus kedua ini akan ditunjukkan penggunaan parameter tersebut secara terapan. Setelah dilakukan penghitungan didapatkan besarnya pengulangan kendala redundant h 24, 1728 , sehingga masalah KM yang diperoleh sebagai berikut: T
min kendala
y2 0 y1 1
1 1 y1 y2 1 y1 3 3 y1 0 diulang 24 kali, y2 0 diulang 1728 kali.
14
Dengan menggunakan definisi analytic center, untuk menentukan analytic center maka kendala masalah KM tersebut dinyatakan sebagai berikut: y1 0, 1 y1 0,
y2 1
1 y1 0, 3
1 y1 y2 0, 3 y1 0, y2 0.
(24 kali) (1728 kali)
Kemudian digunakan rumus untuk mencari analytic center: log y1 log1 y1 1 log y2 y1 3 1 log1 y1 y2 3 A 2 =argmaks y 1 1 1 log y 1 24 log y1 log y2 1728 log y2
1 1 A2 argmaks y (log y1 log 1 y1 log y2 y1 log 1 y1 y2 24log y1 3 3 1728log( y2 ))
4.2
untuk memperoleh titik analytic center turunkan persamaan (4.2) terhadap y1 dan y2 A2 0 y1
1 1 1 1 24 3 3 0 1 1 y1 1 y1 y y 1 y y y1 2 1 1 2 3 3 A2 0 y2 1 1 1728 0. 1 1 y2 y2 y1 1 y1 y2 3 3
Dengan menyelesaikan persamaan (4.2) diperoleh titik analytic center y1 0.043, y2 0.985 .
15
Gambar 2 menunjukkan masalah KM dengan penambahan kendala redundant y1 0 (24 kali) dan y2 0 (1728 kali).
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Gambar 2. Masalah KM dengan penambahan kendala redundant. Dapat dilihat pada Gambar 2 semua kendala redundant masalah KM tersebut menyentuh daerah fisibel dan terjadi perubahan pada central path sehingga central
path mengunjungi cukup dekat ke semua verteks dari daerah fisibel, yang diakibatkan adanya penambahan kendala redundant y1 0 (24 kali) dan y2 0 (1728 kali).
16
V SIMPULAN DAN SARAN 5.1 Simpulan Metode interior primal-dual dengan langkah full-Newton adalah salah satu metode untuk menyelesaikan masalah optimasi linear. Metode ini bergerak di dalam interior dari domain secara monoton menuju solusi optimal. Central path merupakan kurva yang bergerak dari analytic center menuju solusi optimal. Dengan adanya penambahan kendala redundant y1 0 (24 kali) dan y2 0 (1728 kali) pada masalah Klee-Minty, central path mengunjungi cukup dekat ke semua verteks dari daerah fisibel.
5.2 Saran Untuk penelitian selanjutnya dapat dilakukan analisis kompleksitas terhadap metode interior primal-dual dengan langkah full-Newton dan melakukan perbandingan waktu secara terapan dalam menyelesaikan masalah optimasi linear antara metode simpleks dan metode interior primal-dual dengan langkah full-Newton. Dikarenakan keterbatasan waktu penulis belum dapat melakukan hal tersebut.
DAFTAR PUSTAKA Deza A, Nematollahi E, Peyghami R, and Terlaky T. 2006. The central path visits all the vertices of the Klee-Minty cube. Optimization Methods & Software, 21(5):851–865. Deza A, Terlaky T, and Zinchenko Y. 2009. Central Path Curvature and IterationComplexity for Redundant Klee-Minty Cubes. In Advance in applied mathematics and global optimization, volume 17 of Adv. Mech. Math., pages 223-256. Springer, New York. Deza A. Nematollahi E, and Terlaky T. 2008. How Good are Interior Point Methods? Klee-Minty Cubes Tighten Iteration-Complexity Bounds. Mathematical Programming, 113 (1, Ser. A): 114.
Mitchell JE, P.M. Pardalos and M.G.C. Resende. 1998. Interior Point Methods for Combinatorial Optimazation. Kluwer Academic Publishers. Nash SG and Sofer A. 1996. Linear and Nonlinear Programming. McGraw-Hill, New York. Nematollahi E. and Terlaky T. 2008a. A Simpler and Tighter redundant Klee-Minty Construction. Optimization Letters, 2(3): 403-414. Nematollahi E. and Terlaky T. 2008b. A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region. Mcmaster University, Canada.
Guritman S, dan Supriyo P.T. 2004. Diktat Kuliah Matematika Diskret. Bogor: Dep. Matematika IPB.
Roos C, Terlaky T, and Vial J.-Ph. 2006. Interior Point Methods for Linear Optimization. Ed ke-2. Springer, New York.
Jensen P.A, Bard J.F. 2002. Operations Research Models and Methods. John Wiley and Sons. New York.
Silalahi B.P. 2011. On the Central Path of Redundant Klee-Minty Problems. Delft University, Netherland.
Leon, S.J. 1998. Linear Algebra with Aplications. Ed ke-4. Prentice Hall, New York.
Winston W.L. 2004. Operations Research: Applications and Algorithms. Ed ke-4. Duxbury, New York.
18
LAMPIRAN
19
Langkah full 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
= + + +
1; alpha*Dx; alpha*Dy; alpha*Ds;
Pembangkitan Gambar 1 function [A,b,c,x,y,s,mu,opt] =irwan_nursolih 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.4 0.5]'; s = c -A'*y mu = 1000; x = mu./s -1/(11*10^(n-5)) rb = A*x-b figure (3) axis ([0 1 0 1]) for i = 1:250, [x,y,s] = Newton_step(A,b,c,x,y,s,mu); end rb = A*x-b
20
rc = -c+A'*y+s [x s] x y x.*s mu=(x'*s)/(n); theta = 1/100; eps = 10^(-10); figure(3) line('color',[0 1 0],'linestyle','o','erase','none','xdata',y(1),'ydata',y(2),'marke rsize',2); % it=0 while n*mu>eps, mu = (1-theta)*mu; [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),'marke rsize',1); % it=it+1 end line('color',[1 0 0],'linestyle','*','erase','none','xdata',y(1),'ydata',y(2),'marke rsize',4); axis([-0.02 0.02 0 10^(0)]) axis([0 1 0 1]) axis([0 1 0 1]) xx=[0 1 1 0 0] yy=[0 0.3 0.7 1 0] line('color',[1 0 0],'linestyle','','erase','none','xdata',xx,'ydata',yy,'markersize',4); y return
Pembangkitan Gambar 2 function [A,b,c,x,y,s,mu,opt] = gambar_kasus(n) n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1 ] m=1 c=[0;1;0;1] for i=1:m A=[A,[-1;0]] c=[c;0] end n=n+m p=1 for i=1:p A=[A,[0;-1]]
21
c=[c;0] end n=n+p b=[0;-1] figure(3) clf y = [0.1 0.9]'; A' d=A'*y d(1) d(2) s = c - A'*y mu =1000; x = mu./s opt = -1/(11*10^(n-5)) rb = A*x-b % compute (feasible!) 1-center for i = 1:250, [x,y,s] = Newton_step(A,b,c,x,y,s,mu); end rb = A*x-b rc = c - A'*y - s [x s] x y x.*s
mu=(x'*s)/(n); xsu=(sqrt(x.*s/mu)-sqrt(ones(size(x))*mu./(x.*s))); delta=normest(xsu)/2 theta = 0.01; eps = 10^(-10); figure(3) line('color',[0 1 0],'linestyle','o','erase','none','xdata',y(1),'ydata',y(2)opt,'markersize',2); while 4*mu>eps, mu = (1-theta)*mu; [x,y,s] = Newton_step(A,b,c,x,y,s,mu); line('color',[0 0 1],'linestyle','','erase','none','xdata',y(1),'ydata',y(2)-opt,'markersize',2); end line('color',[1 0 0],'linestyle','*','erase','none','xdata',y(1),'ydata',y(2)opt,'markersize',4); axis([-0.02 0.02 0 10^(0)]) axis([-0.3 0.3 0 1]) axis([0 1 0 1])
22
% ini yg bwt KM-cube xx=[0 1 1 0] yy=[0 0.3 0.7 1] line('color',[1 0 0],'linestyle','','erase','none','xdata',xx,'ydata',yy,'linewidth',1); xx=[0 0 ] yy=[0 1 ] line('color',[0 1 0],'linestyle','','erase','none','xdata',xx,'ydata',yy,'linewidth',2); xx=[0 1 ] yy=[0 0 ] line('color',[0 1 0],'linestyle','','erase','none','xdata',xx,'ydata',yy,'linewidth',2); xx=[0.083 0.917 0.917 0.083 0.083] yy=[0.083 0.383 0.617 0.917 0.083] line('color',[1 0 1],'linestyle','','erase','none','xdata',xx,'ydata',yy,'linewidth',2); return
