ANALISIS PERUBAHAN ANALYTIC CENTER DALAM MASALAH OPTIMASI LINEAR DENGAN METODE INTERIOR PRIMAL-DUAL LANGKAH FULL-NEWTON
NURHAYATI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2013
ABSTRAK NURHAYATI. Analisis Perubahan Analytic Center dalam Masalah Optimasi Linear dengan Metode Interior Primal-Dual Langkah Full-Newton. Dibimbing oleh BIB PARUHUM SILALAHI dan PRAPTO TRI SUPRIYO. Metode interior primal-dual langkah Full-Newton adalah suatu metode untuk menyelesaikan masalah optimasi linear. Titik awal metode interior konvergen ke suatu titik disebut analytic center. Karya ilmiah ini membahas dan menjelaskan metode interior primal-dual langkah fullNewton, serta menganalisis perubahan analytic center pada masalah optimasi linear dengan penambahan kendala-kendala redundant. Penambahan tak berhingga kendala-kendala redundant dapat menyebabkan analytic center konvergen menuju solusi lain. Kata kunci: Optimasi, metode interior, analytic center
ABSTRACT NURHAYATI. Analysis of Changes in Analytic Center Linear Optimization Problems with Primal-Dual Full-Newton Step Interior-Point Methods. Supervised by BIB PARUHUM SILALAHI and PRAPTO TRI SUPRIYO. Primal-dual interior-point method with full-Newton steps is a method for solving optimization problems. The initial point of the interior-point method converges to the so called analytic center. In this paper we discuss and explain the primal-dual interior-point method using the full-Newton step interior method and analyze changes of the analytic center of linear optimization problems with redundant constraints. The addition of infinite redundant constraints cause that the analytic center converges to another optimal solution. Key words: Optimization, interior-point methods, analytic center
ANALISIS PERUBAHAN ANALYTIC CENTER DALAM MASALAH OPTIMASI LINEAR DENGAN METODE INTERIOR PRIMAL-DUAL LANGKAH FULL-NEWTON
NURHAYATI
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 Skripsi : Analisis Perubahan Analytic Center dalam Masalah Optimasi Linear dengan Metode Interior Primal-Dual Langkah Full-Newton Nama : NURHAYATI NIM : G54080057
Menyetujui,
Pembimbing I
Pembimbing II
Dr. Ir. Bib Paruhum Silalahi, M.Kom NIP. 19670101 199203 1 004
Drs. Prapto Tri Supriyo, M.Kom NIP. 19630715 199002 1 002
Mengetahui,
Ketua Departemen Matematika
Dr. Berlian Setiawaty, MS. NIP. 19650505 198903 2 004
Tanggal Lulus :
KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Allah SWT 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 terlepas dari bantuan berbagai pihak. Untuk itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada Bapak dan Ibu tersayang, terima kasih atas kasih sayang, didikan, nasihat, semangat serta doa yang tiada henti-hentinya untuk penulis. Kepada Bapak Dr. Ir. Bib Paruhum Silalahi, M.Kom. dan Bapak Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing, terima kasih atas waktu, ilmu yang diberikan dan kesabaran dalam membimbing penulis serta Bapak Drs. Siswandi, M.Si. selaku dosen penguji terima kasih atas waktu, ilmu dan saran yang bermanfaat bagi penulis. Di samping itu, penghargaan penulis sampaikan kepada Bapak dan Ibu dosen Departemen Matematika yang telah mengajar dan memberikan bekal ilmu pengetahuan kepada penulis. Tidak lupa ungkapan terima kasih kepada seluruh keluarga atas doa dan kasih sayangnya. Terima kasih kepada Riki Firdaus atas semangat, kesabaran, doa dukungan dan bantuannya selama ini. Terima kasih pula kepada teman-teman satu bimbingan: Bramanto, Irwan Nursolih dan Rini Maedianingsih atas bantuan dan dukungannya, serta terima kasih sahabat terdekat: Annisa, Suwaibatul Aslamyah, Yeni Rahmawati, Friesgina Wiska, Lya, Agustina atas semangat, doa dan dukungannya. Terima kasih kepada Teman-teman Math 45, adik kelas angkatan 46, dan teman-teman Wisma Ayu atas dukungan, bantuan, doa dan kebersamaannya. Penulis menyadari bahwa karya ilmiah ini masih jauh dari sempurna, oleh karena itu penulis mengharapkan saran dan kritik yang bersifat membangun demi penyempurnaan karya ilmiah ini, Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Maret 2013
Nurhayati
1
RIWAYAT HIDUP Penulis dilahirkan di Pandeglang pada tanggal 2 Oktober 1990 sebagai anak pertama dari tiga bersaudara. Anak dari pasangan Nurhadi dan Hamdiyatu Soliha. Pada tahun 1996 penulis menyelesaikan pendidikan di TK Tunas Merak Pandeglang. Tahun 2002 penulis menyelesaikan pendidikan di SDN Cigadung 3 Pandeglang. Tahun 2005 penulis menyelesaikan pendidikan di SLTPN 1 Karang Tanjung Pandeglang. Tahun 2008 penulis menyelesaikan pendidikan di SMAN 1 Pandeglang dan pada tahun yang sama penulis diterima di Departemen Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor (IPB) malalui jalur Undangan Seleksi Masuk IPB (USMI). Selama mengikuti perkuliahan, penulis aktif di berbagai kegiatan mahasiswa yaitu sebagai anggota Biro Kesekertariatan GUMATIKA IPB pada tahun 2009-2010, sebagai anggota Biro Kewirausahaan GUMATIKA IPB pada tahun 2010-2011. Kegiatan lain yang pernah diikuti oleh penulis yaitu sebagai panitia acara Matematika Ria 2010, bendahara acara “Seminar Kewirausahaan” pada tahun 2011, serta sebagai pengajar Matematika untuk tingkat TPB di sebuah bimbingan belajar pada tahun 2011-2012.
2
DAFTAR ISI Halaman ..........................................................................................................
ix
................................................................................................................
ix
DAFTAR LAMPIRAN ..........................................................................................................
ix
I
PENDAHULUAN ............................................................................................................ 1.1 Latar Belakang ......................................................................................................... 1.2 Tujuan ..........................................................................................................
1 1 1
II LANDASAN TEORI ........................................................................................................ 2.1 Matriks ............................................................................................................... 2.2 Sistem Persamaan Linear .......................................................................................... 2.3 Optimasi Linear ........................................................................................................ 2.4 Dualitas ................................................................................................................ 2.5 Masalah Redundant Klee-Minty (KM) ...................................................................... 2.6 Metode Newton ..........................................................................................................
2 2 2 2 3 3 3
III HASIL DAN PEMBAHASAN ......................................................................................... 3.1 Kondisi Optimal bagi Optimasi Linear ................................................................... 3.2 Central Path .......................................................................................................... 3.3 Langkah Full-Newton ............................................................................................... 3.4 Central Path pada Masalah Redundant Optimasi Linear ..........................................
6 6 6 7 8
DAFTAR GAMBAR DAFTAR TABEL
IV CONTOH KASUS
..........................................................................................................
10
.............................................................................................................
20
DAFTAR PUSTAKA .............................................................................................................
21
LAMPIRAN ...........................................................................................................................
22
V KESIMPULAN
3
DAFTAR GAMBAR Halaman Gambar 1 Masalah KM tanpa redundant ............................................................................... Gambar 2 Masalah KM untuk kendala dengan kali ................................... Gambar 3 Masalah KM untuk kendala dengan kali .................................. Gambar 4 Masalah KM untuk kendala dengan kali ................................ Gambar 5 Masalah KM untuk kendala dengan kali ....................................... Gambar 6 Masalah KM untuk kendala dengan kali ..................................... Gambar 7 Masalah KM untuk kendala dengan kali ...................................
10 12 12 12 14 14 14
Gambar 8 Masalah KM untuk kendala
dengan
kali ...................
16
Gambar 9 Masalah KM untuk kendala
dengan
kali .................
16
kali ............
17
Gambar 10 Masalah KM untuk kendala
dengan
Gambar 11 Masalah KM untuk kendala
dengan
kali ......................
18
Gambar 12 Masalah KM untuk kendala
dengan
kali ....................
19
Gambar 13 Masalah KM untuk kendala
dengan
kali ..................
19
DAFTAR TABEL Halaman Tabel Perubahan masalah dualitas ..........................................................................................
3
DAFTAR LAMPIRAN Halaman Lampiran 1 Program MATLAB untuk Newton step ............................................................ Lampiran 2 Program MATLAB untuk gambar 1 ................................................................ Lampiran 3 Program MATLAB untuk gambar 2 ................................................................ Lampiran 4 Program MATLAB untuk gambar 3 ................................................................ Lampiran 5 Program MATLAB untuk gambar 4 ................................................................ Lampiran 6 Program MATLAB untuk gambar 5 ................................................................ Lampiran 7 Program MATLAB untuk gambar 6 ................................................................ Lampiran 8 Program MATLAB untuk gambar 7 ................................................................ Lampiran 9 Program MATLAB untuk gambar 8 ................................................................ Lampiran 10 Program MATLAB untuk gambar 9 ................................................................ Lampiran 11 Program MATLAB untuk gambar 10 ................................................................ Lampiran 12 Program MATLAB untuk gambar 11 ................................................................ Lampiran 13 Program MATLAB untuk gambar 12 ................................................................ Lampiran 14 Program MATLAB untuk gambar 13 ................................................................
23 24 26 28 30 32 34 36 38 40 42 44 46 48
ix
1
I PENDAHULUAN 1.1 Latar Belakang Optimasi adalah salah satu cabang ilmu matematika terapan yang mempelajari masalah untuk meminimumkan atau memaksimumkan fungsi real dari variabel real dengan kendala-kendala pada setiap variabel. Optimasi digunakan hampir di setiap aspek kehidupan, termasuk dalam ilmu pengetahuan, ekonomi, teknik, manajemen dan industri. Salah satu bagian dari optimasi adalah optimasi linear, yang mempelajari masalah untuk meminimumkan atau memaksimumkan fungsi linear dengan kendala yang dinyatakan dalam persamaan linear dan/atau pertaksamaan linear. Optimasi Linear (OL) muncul sebagai sebuah model matematika setelah Perang Dunia II. Pada tahun 1947 Danzig mengusulkan metode simpleks untuk memecahkan masalah “pemrograman linear“. Daerah fisibel dari OL adalah suatu polihedron. Untuk memperoleh solusi optimalnya, metode simpleks bergerak dari verteks ke verteks dari suatu polihedron (Silalahi 2011). Pada tahun 1972 Klee dan Minty menyatakan bahwa metode simpleks memerlukan iterasi untuk menyelesaikan suatu masalah OL dengan 2n pertaksamaan (Silalahi 2011). Pada tahun 1978 Khachiyan mengusulkan metode elipsoid. Metode ini merupakan algoritma polinomial pertama untuk masalah OL, tetapi di dalam praktek laju konvergensi dari metode elipsoid agak lambat dibandingkan dengan metode simpleks (Silalahi 2011). Sebuah terobosan yang benar-benar efektif terjadi pada tahun 1984 ketika Karmarkar mengusulkan metode polynomial–time yang berbeda, yang dikenal dengan metode proyektif Karmarkar untuk masalah OL. Metode ini memiliki kompleksitas yang lebih baik dari metode elipsoid dan juga efisien dalam penerapannya. Metode proyektif
Karmarkar memacu revolusi dalam bidang optimasi, dengan munculnya penelitianpenelitian mengenai pengoptimuman menggunakan metode interior. Tidak seperti metode simpleks yang bergerak dari verteks ke verteks dalam mencari solusi optimalnya, metode interior bergerak di dalam interior dari domain secara monoton menuju solusi optimal (Silalahi 2011). Secara umum metode interior dapat dikelompokkan menjadi tiga kategori, yaitu: metode affine scaling, metode potential reduction (barrier) dan metode central trajectory (path-following) (Mitchell 1998). Deza dkk, memberikan suatu contoh kasus terburuk (pada saat itu) untuk kasus penyelesaian optimasi linear dengan metode interior. Kasus mereka adalah dengan menambahkan kendala-kendala redundant pada masalah Klee-Minty (KM). Secara teoritis diperlihatkan bahwa central path dan analytic center dapat berubah dengan penambahan kendala redundant (Deza et al. 2006). Dalam karya ilmiah ini, akan dibahas tentang perubahan analytic center pada masalah Klee-Minty (KM) dengan penambahan kendala redundant yang akan dianalisis menggunakan metode interior dengan pendekatan central trajectory (pathfollowing) dengan bantuan software MATLAB R2008b. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah untuk: (i) Membahas dan menjelaskan metode interior primal-dual langkah full-Newton. (ii) Menganalisis perubahan analytic center pada penambahan kendala redundant untuk masalah Klee-Minty (KM), berdasarkan metode interior primal-dual langkah full-Newton, menggunakan bantuan software MATLAB R2008b.
2
II LANDASAN TEORI 2.2 Sistem Persamaan Linear Suatu sistem persamaan linear (SPL) dari persamaan dan variabel adalah sistem dengan bentuk:
2.1 Matriks Definisi 1 (Hadamard Product) Misalkan vektor , dengan:
x
[
]
s
[ ]
Misalkan pula adalah matriks diagonal dengan unsur diagonal utama ialah vektor x, dan adalah matriks diagonal dengan unsur diagonal utama ialah vektor s, yaitu:
dengan dan ( adalah bilangan-bilangan real dan … adalah variabel. SPL ini disebut SPL berukuran . (Leon 2001) SPL juga dapat ditulis dalam bentuk:
[
] dengan adalah matriks berukuran dan b berukuran yaitu: ]
[
]
[ 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. (Roos et al. 2006) Definisi 2 (Hasil Kali Skalar di Misalkan x, y dengan
x
[
],
s
b =[
]
matriks disebut juga matriks koefisien dan vektor disebut vektor konstanta. Penyelesaian SPL tersebut adalah vektor kolom berukuran yaitu:
) x =[
[ ]
]
yang memenuhi semua persamaan linear dalam sistem. Vektor yang demikian disebut vektor penyelesaian (Leon 2001).
maka hasil kali skalar dari x dan s adalah 2.3 Optimasi Linear (Leon 2001)
Definisi 3 (Daerah Fisibel) Daerah fisibel adalah himpunan titik-titik yang memenuhi semua kendala dan pembatasan tanda pada optimasi linear. (Winston 2004)
3
Definisi 4 (Solusi Optimal) Solusi optimal pada masalah maksimisasi adalah suatu titik pada daerah fisibel dengan 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)
Bentuk standar dari masalah primal (P) adalah: { }….. (P) dimana
, , dan . Bentuk standar dari masalah dual (D) adalah: {
2.4 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. Bentuk normal dari masalah primal untuk kasus maksimisasi adalah: Fungsi objektif
Kendala
}…..(D)
Dimana
dan
Proposisi 1 Jika x dan (y,s) masing-masing fisibel untuk (P) dan (D) maka , 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). (Roos et al. 2006) Bukti dapat dilihat di Roos (2006)
Bentuk normal dari masalah dual untuk kasus maksimisasi di atas adalah: Fungsi objektif
2.5 Masalah Redundant Klee-Minty (KM)
Kendala
Definisi 5 (Masalah Klee-Minty (KM)) Suatu permasalah yang diberikan oleh Klee dan Minty yang kemudian dikenal dengan masalah Klee-Minty (KM) yaitu: min kendala
Perubahan masalah primal menjadi dual tersebut dilihat dari tabel berikut: Tabel Perubahan masalah dualitas Maks z Min w
dimana
, , (Klee & Minty 1972)
Definisi 6 (Kendala Redundant) Kendala redundant adalah kendala yang tidak mengubah daerah fisibel dari masalah optimasi linear. (Silalahi 2011) 2.6 Metode Newton Metode Newton atau metode NewtonRapson adalah suatu metode yang digunakan untuk menyelesaikan persamaan taklinear, yang dituliskan dalam bentuk:
(Winston 2003) Semua masalah optimasi linear bisa ditransformasikan menjadi bentuk standar dengan cara menambahkan variabel baru.
Metode Newton-Rapson dapat diturunkan dari ekspansi deret Taylor orde pertama. Berikut ini adalah contoh untuk persamaan
4
satu variabel, persamaan dapat ditulis sebagai berikut:
persamaan .
dimana 2003).
Penyelesaian: Untuk mencari solusi dari pendekatan terhadap .
adalah hampiran awal (Munir
dengan hampiran awal
, lakukan
Dengan menggunakan metode NewtonRapson, fungsi taklinear dapat didekati dengan fungsi linear. Untuk mencari solusi persamaan , metode Newton melakukan pendekatan dengan cara mencari solusi persamaan: Apabila iterasinya diteruskan maka nilai akan konvergen ke akar persamaan . dimana linear.
adalah fungsi
Contoh 1 Diketahui suatu fungsi taklinear untuk satu variabel . Gunakan metode Newton-Rapson untuk mencari akar-akar
Contoh untuk dua variabel, deret Taylor orde pertama dapat dituliskan untuk masingmasing persamaan sebagai berikut:
adalah hampiran awal
mencari solusi persamaan dan , metode Newton-Rapson melakukan pendekatan dengan cara mencari solusi persamaan:
dimana kedua persamaan adalah fungsi linear. Dengan mengeliminasi kedua persamaan diperoleh nilai dan . Kemudian nilai tersebut menjadi hampiran awal untuk iterasi berikutnya sampai diperoleh nilai dan yang konvergen ke nilai dan sesungguhnya.
Contoh 2 Gunakan metode Newton-Rapson untuk mencari akar-akar persamaan bila diketahui suatu fungsi taklinear untuk dua variabel adalah:
dimana dan (Munir 2003).
Untuk
dan
dengan hampiran awal
5
Penyelesaian:
Eliminasi persamaan (2.1) dan persamaan (2.2) untuk memperoleh nilai dan , sehingga diperoleh nilai dan . Kemudian iterasi diteruskan dengan nilai dan menjadi nilai hampiran awal yang baru, sehingga dan akan konvergen ke akar sesungguhnya yaitu dan .
III HASIL DAN PEMBAHASAN Pada bab ini akan dibahas tentang metode interior primal-dual langkah full-Newton serta perubahan analytic center terhadap penambahan kendala redundant. 3.1 Kondisi Optimal bagi Optimasi Linear Daerah fisibel dari masalah primal (P) dinotasikan oleh dan daerah fisibel dari masalah dual (D) dinotasikan oleh adalah: { {
} }
Jika merupakan himpunan kosong maka (P) takfisibel, lainnya fisibel. Jika merupakan himpunan kosong maka (D) takfisibel, lainnya fisibel. Daerah interior untuk dinotasikan oleh dan daerah interior untuk dinotasikan dengan , yaitu: { {
} }
Jika merupakan himpunan takkosong maka (P) adalah strictly feasible, jika merupakan himpunan takkosong maka (D) adalah strictly feasible. Teorema 1 Jika (P) dan (D) fisibel maka kedua masalah tersebut mempunyai solusi optimal, kemudian dan adalah solusi optimal jika dan hanya jika . Bukti : Mengacu pada proposisi 1, x fisibel untuk (P) dan (y,s) fisibel untuk (D), maka . Dimana batas atas untuk nilai optimal dari (D) dan batas bawah untuk nilai optimal dari (P), untuk memperoleh solusi optimal haruslah sehingga maka teorema 1 terbukti. Berdasarkan teorema 1, mencari solusi optimal dari masalah primal (P) dan masalah dual (D) setara dengan memecahkan sistem berikut:
(3.1)
Dimana xs adalah hadamard product dari vektor x dan s dan 0 adalah vektor nol. Diketahui bahwa x dan s adalah vektor taknegatif maka berlaku jika dan hanya jika (Roos et al. 2006). Sistem (3.1) adalah kondisi optimal untuk optimasi linear. Baris pertama sistem (3.1) adalah kendala fisibel untuk masalah primal (P) dan baris kedua merupakan kendala fisibel untuk masalah dual (D). Persamaan terakhir adalah kondisi complementary. 3.2 Central Path Secara geometrik, central path merupakan kurva analitik yang konvergen menuju solusi optimal. Untuk menyelesaikan sistem (3.1) kondisi complementary diganti dengan , dimana adalah bilangan positif dan adalah vektor yang semua unsurunsurnya satu. Kendala baru ini disebut sebagai kondisi centering dengan memperhatikan . Sistem yang dihasilkan adalah:
(3.2) Jika sistem (3.2) mempunyai solusi untuk beberapa , maka dan merupakan himpunan takkosong. Kondisi dimana dan takkosong disebut dengan kondisi interior. Selanjutnya jika kondisi interior terpenuhi maka sistem (3.2) mempunyai solusi untuk setiap (Roos et al. 2006). Solusi untuk setiap dinotasikan , , dan . Solusi dari disebut dari (P) dan solusi dari ( ) disebut dari (D). Central path dari (P) adalah kurva , dengan yang ditulis dengan { }. Sedangkan central path dari (D) adalah kurva dengan yang ditulis dengan { }. Jika maka , dan konvergen ke solusi dari sistem (3.1), artinya central path konvergen ke himpunan solusi optimal dari (P) dan (D). Di sisi lain, jika maka dan konvergen ke analytic center dari (P) dan (D) (Roos et al. 2006). Definisi formal dari analytic center (P) dan (D) adalah sebagai berikut:
7
Jika kondisi interior terpenuhi maka: (i) Analytic center primal adalah { } dan (ii) Analytic center dual adalah { }.
Karena dan tersebut setara dengan:
, sistem
(3.4)
3.3 Langkah Full-Newton Langkah full-Newton dapat digunakan untuk memperoleh solusi pendekatan sistem (3.2) untuk tetap. Diberikan pasangan fisibel primal-dual , akan dicari dan , sehingga memenuhi sistem (3.2), dengan kata lain:
Persamaan pertama dan persamaan kedua merupakan persamaan linear. Sedangkan, persamaan ketiga merupakan persamaan taklinear karena mengandung faktor kuadrat . Untuk menyelesaikan sistem (3.4), persamaan ketiga dilinearkan dengan menggunakan metode Newton sebagai berikut:
(3.3)
[ ][
]
[
][
]
[
][
]
[
][ ]
[ ]
[ ]
Metode Newton untuk persamaan pertama dengan hampiran awal
untuk persamaan kedua sampai persamaan ke- dilakukan cara yang sama, sehingga diperoleh:
dapat juga ditulis sebagai bentuk:
[ ][
]
[
][
]
[ ]
[
][ ]
8
Sehingga diperoleh persamaan baru sebagai berikut: (3.7) (3.5) Matriks koefisien dari (3.5) adalah: [
][
]
[
]
Dimana diag(x) dan diag(s), serta vektor x dan vektor s adalah vektor positif. Solusi dari sistem persamaan linear dinamakan primal-dual langkah Newton. Dengan mengambil langkah sepanjang arah primal-dual langkah Newton, ditemukan iterasi baru yaitu ( ). Iterasi baru diberikan oleh :
(3.6) Iterasi (3.6) disebut dengan langkah fullNewton. 3.4 Central Path pada Masalah Redundant Optimasi Linear Pada bagian ini akan ditunjukkan bahwa central path untuk masalah optimasi linear bergantung pada representasi dari masalah yang diberikan. Masalah optimasi linear dengan tambahan kendala redundant ini disebut masalah redundant pada masalah optimasi linear. Kemudian akan ditunjukkan bagaimana perubahan central path saat ditambahkan kendala redundant pada masalah optimasi linear. Nilai optimal dari masalah optimasi linear dan masalah redundant harus sama. Ini menunjukkan bahwa masalah optimasi hanya memiliki satu solusi yang optimal, jika maka central path kedua masalah konvergen ke solusi yang sama. Di sisi lain, jika maka central path menuju ke analytic center. Teori berikut menunjukkan bagaimana perubahan analytic center ketika terjadi penambahan kendala redundant terhadap masalah (D). Lema 1 Jika kondisi interior terpenuhi, maka analytic center dari (D) adalah solusi yang unik dari sistem:
(Silalahi 2011) Bukti : Mengacu pada bagian 3.2 tentang central path, dapat disimpulkan bahwa jika kondisi interior terpenuhi maka dari (D) adalah solusi unik dari sistem berikut:
Dengan mendefinisikan ulang x sesuai dengan dan sehingga lema 1 terbukti. Teorema 2 Diberikan , , menjadi kendala redundant untuk (D). Jika ditambahkan kendala untuk (D) sebanyak kali, kemudian menuju tak hingga maka analytic center dari masalah baru, dilambangkan sebagai (DR), konvergen ke solusi optimal. {
}
(3.8)
(Silalahi 2011) Bukti: Ketika menambahkan kendala redundant sebanyak h kali untuk masalah (D), didapatkan masalah redundant berikut: {
} (DR) Masalah dual dari (DR) diberikan oleh { ̅
̅
}
̅
(PR) Dimana ̅ , dikarenakan lema 1, analytic center dari (DR) secara unik ditentukan oleh sistem: ̅
̅ ̅ ̅ ̅
̅
9
Dengan membagi persamaan (3.9) dan (3.12) oleh ̅ dan mendefinisikan ulang x sehingga maka: ̅
̅ ̅ ̅
̅ ̅ ̅ ̅ ̅
̅ ̅
Dengan (3.17) diperoleh: ̅
̅ ̅
̅
(3.15) (3.16) (3.17) (3.18)
pada sistem persamaan
(3.19) ̅
Karena (3.14), (3.15) dan (3.19) adalah kondisi optimal untuk (3.8) maka teorema 2 terbukti.
Sehingga diperoleh sistem: (3.14)
10
IV CONTOH KASUS Pada bagian ini akan diberikan beberapa contoh kasus penambahan kendala redundant yang berbeda untuk masalah Klee-Minty (KM) 2 dimensi dengan . Kemudian akan diperlihatkan kurva daerah fisibel untuk masalah Klee-Minty (KM), serta perubahan titik analytic center ketika ditambahkan kendala redundant.
kendala
Berdasarkan definisi analytic center, untuk memperoleh analytic center maka semua kendala diubah menjadi:
Kasus 1 (Masalah Klee-Minty (KM) tanpa kendala redundant) Masalah Klee-Minty (KM) menjadi: maks { dimana
}
[
]
[
)]
(
)
(
sehingga (
)
(
(
))
Untuk memperoleh titik analytic center maka turunkan persamaa
⁄
terhadap
dan
.
⁄
Dengan menyelesaikan persamaan (4.1) dan (4.2) maka diperoleh titik analytic center { 0.317, 0.5}.
1
0.8
y2
0.6
0.4
0.2
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 1 Masalah KM tanpa redundant.
11
Pada contoh kasus 2, 3, 4, dan 5 berikut akan dicari titik analytic center untuk pengulangan kendala redundant sebanyak 10 kali, 100 kali, dan 1000 kali.
Berdasarkan definisi analytic center, untuk memperoleh analytic center maka semua kendala diubah menjadi:
Kasus 2 (Masalah Klee-Minty (KM) untuk kendala redundant ) Masalah Klee-Minty (KM) dengan pengulangan kendala sebanyak kali menjadi: maks kendala
{ dimana
}
[
]
[ ] sehingga ( )
Untuk memperoleh titik analytic center maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 10 kali.
⁄
⁄
(
terhadap
dan
terhadap
dan
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 100 kali.
12
⁄
⁄
(
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 1000 kali.
⁄
(
Titik analytic center untuk adalah { 0.764869, 0.5}, diperoleh dari menyelesaikan persamaan (4.3) dan (4.4). Titik analytic center untuk adalah { 0.979041, 0.5}, diperoleh dari menyelesaikan persamaan (4.5) dan (4.6). Titik analytic center untuk adalah { 0.99799, 0.5}, diperoleh dari menyelesaikan persamaan (4.7) dan (4.8).
dan
)
1
0.8
0.6
y2
⁄
terhadap
0.4
0.2
0
-0.2 1
-1
-0.6
-0.4
-0.2
0 y1
0.2
0.4
0.6
0.8
1
Gambar 3 Masalah KM untuk kendala redundant dengan kali.
0.8
0.6
y2
-0.8
0.4 1 0.2 0.8 0 0.6
-1
-0.8
-0.6
-0.4
-0.2
0 y1
0.2
0.4
0.6
0.8
1
y2
-0.2 0.4
0.2
Gambar 2 Masalah KM untuk kendala redundant dengan kali.
0
-0.2 -1
-0.8
-0.6
-0.4
-0.2
0 y1
0.2
0.4
0.6
0.8
1
Gambar 4 Masalah KM untuk kendala redundant dengan kali.
13
Gambar 2, gambar 3 dan gambar 4 menunjukkan perubahan titik analytic center dengan banyaknya pengulangan kendala redundant yang berbeda. Pada contoh kendala redundant semakin besar pengulangan kendala redundant maka titik analytic center akan konvergen ke minimum dari yaitu nilai mendekati 1.
Berdasarkan definisi analytic center, untuk memperoleh analytic center maka semua kendala diubah menjadi:
Kasus 3 (Masalah Kee-Minty (KM) untuk kendala redundant ) Masalah Klee-Minty (KM) dengan pengulangan kendala sebanyak menjadi: maks kendala { dimana
}
[ [
] )
(
(
)
(
)
] sehingga (
)
( )
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 10 kali.
⁄
⁄
(
terhadap
dan
terhadap
dan
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 100 kali.
14
⁄
⁄
(
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 1000 kali.
⁄
(
Titik analytic center untuk adalah { 0.0751984, 0.5}, diperoleh dari menyelesaikan persamaan (4.9) dan (4.10). Titik analytic center untuk adalah { 0.00967782, 0.5}, diperoleh dari menyelesaikan persamaan (4.11) dan (4.12). Titik analytic center untuk adalah { 0.000996678, 0.5}, diperoleh dari menyelesaikan persamaan (4.13) dan (4.14).
dan
)
1
0.8
0.6
y2
⁄
terhadap
0.4
0.2
0
-0.2 1
0
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 6 Masalah KM untuk kendala redundant dengan kali.
0.8
0.6
y2
0.1
0.4 1 0.2 0.8 0 0.6
0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
y2
-0.2 0.4
0.2
Gambar 5 Masalah KM untuk kendala redundant dengan kali.
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 7 Masalah KM untuk kendala redundant dengan kali.
15
Gambar 5, gambar 6 dan gambar 7 menunjukkan perubahan titik analytic center dengan banyaknya pengulangan kendala redundant yang berbeda. Pada contoh kendala redundant semakin besar pengulangan kendala redundant maka titik analytic center akan konvergen ke minimum dari yaitu nilai mendekati 0.
Berdasarkan definisi analytic center, untuk memperoleh analytic center maka semua kendala diubah menjadi:
Kasus 4 (Masalah Klee-Minty (KM) untuk kendala redundant ) Masalah Klee-Minty (KM) dengan pengulangan sebanyak menjadi: maks kendala
{ dimana
}
[ [
] )
( )
(
)
(
)
(
( )]
sehingga (
)
(
(
)
(
)
( (
))
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 10 kali.
⁄
⁄
(
(
⁄
)
terhadap
dan
terhadap
dan
)
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 100 kali.
16
⁄
⁄
⁄
(
)
(
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 1000 kali.
⁄
⁄
⁄
(
dan
)
(
)
1
0.8
0.6
y2
Titik analytic center untuk adalah { 0.11111, 0.878308}, diperoleh dari menyelesaikan persamaan (4.15) dan (4.16). Titik analytic center untuk adalah { 0.015749, 0.98407}, diperoleh dari menyelesaikan persamaan (4.17) dan (4.18). Titik analytic center untuk adalah { 0.0016422, 0.998356}, diperoleh dari menyelesaikan persamaan (4.19) dan (4.20).
terhadap
0.4
0.2
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
1
Gambar 9 Masalah KM untuk kendala redundant dengan kali.
0.8
y2
0.6
0.4
0.2
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 8 Masalah KM untuk kendala redundant dengan kali.
17
Kasus 5 (Masalah Klee-Minty (KM) untuk kendala redundant ) Masalah Klee-Minty (KM) dengan pengulangan kendala sebanyak menjadi:
1
0.8
y2
0.6
0.4
maks kendala
0.2
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 10 Masalah KM untuk kendala redundant dengan kali.
Berdasarkan definisi analytic center, untuk memperoleh analytic center maka semua kendala diubah menjadi:
Gambar 8, gambar 9 dan gambar 10 menunjukkan perubahan titik analytic center dengan banyaknya pengulangan kendala redundant yang berbeda. Pada contoh kendala redundant semakin besar pengulangan kendala redundant maka titik analytic center akan konvergen ke minimum dari yaitu nilai mendekati 0 dan mendekati 1 .
{ dimana
}
[ [
] )
( )
(
(
)
)
(
( )]
sehingga (
(
(
)
)
(
)
( (
))
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 10 kali.
⁄
⁄
(
⁄
)
)
terhadap
dan
18
(
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 100 kali.
⁄
⁄
⁄
(
⁄
(
dan
)
(
)
1
0.8
0.6
y2
Titik analytic center untuk adalah { 0.11111, 0.121692}, diperoleh dari menyelesaikan persamaan (4.21) dan (4.22). Titik analytic center untuk adalah { 0.0157499, 0.0159207}, diperoleh dari menyelesaikan persamaan (4.23) dan (4.24). Titik analytic center untuk adalah { 0.0016422, 0.001644}, diperoleh dari menyelesaikan persamaan (4.25) dan (4.26).
terhadap
)
Untuk memperoleh titik analytic center, maka turunkan persamaan dengan pengulangan kendala redundant sebanyak 1000 kali.
⁄
dan
)
(
⁄
terhadap
0.4
0.2
0
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 11 Masalah KM untuk kendala redundant dengan kali.
1
1
0.8
0.8
0.6
0.6
0.4
0.4
y2
y2
19
0.2
0.2
0
0
-0.2
-0.2 0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 12 Masalah KM untuk kendala redundant dengan kali.
0
0.1
0.2
0.3
0.4
0.5 y1
0.6
0.7
0.8
0.9
1
Gambar 13 Masalah KM untuk kendala redundant dengan kali. Gambar 11, gambar 12 dan gambar 13 menunjukkan perubahan titik analytic center dengan banyaknya pengulangan kendala redundant yang berbeda. Pada contoh kendala redundant semakin besar pengulangan kendala redundant maka titik analytic center akan konvergen ke minimum dari yaitu nilai mendekati 0 dan mendekati 0.
20
V KESIMPULAN Berdasarkan beberapa contoh penambahan kendala redundant pada masalah Klee-Minty (KM) 2 dimensi, terjadi perubahan titik analytic center untuk pengulangan kendala redundant yang berbeda. Semakin besar pengulangan kendala redundant maka analytic center akan konvergen ke nilai
minimum dari kendala redundant tersebut. Secara matematis dapat dikatakan bila maka analytic center dari masalah baru akan konvergen ke solusi optimal dari { }.
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. Klee. V and G.J. Minty. 1972. How Good is the Simplex Algorithm ? In Inequalities, III (Proc. Third Sympos, Univ. California, Los Angeles, Calif, 1969; dedicated to the memory of Theodore S. Motzkin), pages 159-175. New York: Academic Press. 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 Optimazation. Kluwer Academic Publishers. Munir Rinaldi. 2003. Metode Numerik. Bandung : Informatika. Roos 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.
LAMPIRAN
23
Lampiran 1 Program MATLAB untuk Newton Step 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;
24
Lampiran 2 Program MATLAB untuk Gambar 1 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi 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 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 1 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),’marke rsize’,4); axis([-0.02 0.02 0 10^(0)]) axis([-0.3 0.3 0 1]) axis([0 1.01 -0.3 1.01]) xx=[0 1 1 0 0]
25
yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
26
Lampiran 3 Program MATLAB untuk gambar 2 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] m=10 for i=1:m A=[A,[-1;0]] c=[c;1] end n=n+m b=[0;-1] figure (3) clf y = [0.9 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
27
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 0 0] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[-1 -1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
28
Lampiran 4 Program MATLAB untuk gambar 3 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] m=100 for i=1:m A=[A,[-1;0]] c=[c;1] end n=n+m b=[0;-1] figure (3) clf y = [0.9 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
29
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[-1 -1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
30
Lampiran 5 Program MATLAB untuk gambar 4 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] m=1000 for i=1:m A=[A,[-1;0]] c=[c;1] end n=n+m b=[0;-1] figure (3) clf y = [0.9 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
31
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[-1 -1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
32
Lampiran 6 Program MATLAB untuk gambar 5 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] w=10 for i=1:w A=[A,[1;0]] c=[c;1] end n=n+w b=[0;-1] figure (3) clf y = [0.2 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
33
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[1 1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
34
Lampiran 7 Program MATLAB untuk gambar 6 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] w=100 for i=1:w A=[A,[1;0]] c=[c;1] end n=n+w b=[0;-1] figure (3) clf y = [0.2 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
35
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[1 1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
36
Lampiran 8 Program MATLAB untuk gambar 7 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] w=1000 for i=1:w A=[A,[1;0]] c=[c;1] end n=n+w b=[0;-1] figure (3) clf y = [0.2 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
37
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[1 1] yy=[0 1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
38
Lampiran 9 Program MATLAB untuk gambar 8 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] p=10 for i=1:p A=[A,[1/3;-1]] c=[c;0.1] end n=n+p b=[0;-1] figure (3) clf y = [0.6 0.4]’; 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
39
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.3 0.3 0 1]) axis([0 1.01 -0.3 1.01]) xx=[0 1 1 0 0] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[-0.1 0.1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
40
Lampiran 10 Program MATLAB untuk gambar 9 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] p=100 for i=1:p A=[A,[1/3;-1]] c=[c;0.1] end n=n+p b=[0;-1] figure (3) clf y = [0.6 0.4]’; 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
41
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.3 0.3 0 1]) axis([0 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[-0.3 0.1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
42
Lampiran 11 Program MATLAB untuk gambar 10 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] p=1000 for i=1:p A=[A,[1/3;-1]] c=[c;0.1] end n=n+p b=[0;-1] figure (3) clf y = [0.6 0.4]’; 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
43
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.3 0.3 0 1]) axis([0 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[-0.3 0.1] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
44
Lampiran 12 Program MATLAB untuk gambar 11 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] f=10 for i=1:f A=[A,[1/3;1]] c=[c;1.1] end n=n+f b=[0;-1] figure (3) clf y = [0.2 0.2]’; 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 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 1 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),’marke rsize’,4);
45
axis([-0.02 0.02 0 10^(0)]) axis([-0.3 0.3 0 1]) axis([0 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[1.1 0.9] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
46
Lampiran 13 Program MATLAB untuk gambar 12 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] f=100 for i=1:f A=[A,[1/3;1]] c=[c;1.1] end n=n+f b=[0;-1] figure (3) clf y = [0.2 0.2]’; 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
47
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[1.1 0.9] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
48
Lampiran 14 Program MATLAB untuk gambar 13 function [A,b,c,x,y,s,mu,opt] =zigzag_nematollahi n=4 A=[-1 1 1/3 1/3 ; 0 0 -1 1] c=[0;1;0;1] f=1000 for i=1:f A=[A,[1/3;1]] c=[c;1.1] end n=n+f b=[0;-1] figure (3) clf y = [0.2 0.2]’; 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 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 1 1],’linestyle’,’o’,’erase’,’none’,’xdata’,y(1),’ydata’,y(2), ’markersize’,2); it=it+1 end
49
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.3 0.3 0 1]) axis([-1 1.01 -0.3 1.01]) xx=[0 1 1 00] yy=[0 0.3 0.7 1 0] line(‘color’,[0 0 1],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xx=[0 1] yy=[1.1 0.9] line(‘color’,[0 1 0],’linestyle’,’’,’erase’,’none’,’xdata’,xx,’ydata’,yy,’markersize’,4); xlabel(‘y1’) ylabel(‘y2’) y return
