OPTIMASI PEMROGRAMAN KUADRATIK DENGAN MENGGUNAKAN ALGORITMA PRIMAL-DUAL INTERIOR POINT

TUGAS AKHIR – CF 1380

OPTIMASI PEMROGRAMAN KUADRATIK DENGAN MENGGUNAKAN ALGORITMA PRIMAL-DUAL INTERIOR POINT NIKE DWI WINARTI NRP 5202 100 028 Dosen Pembimbing Rully Soelaiman, S.Kom, M.Kom

JURUSAN SISTEM INFORMASI Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2007

FINAL PROJECT – CF 1380

QUADRATIC PROGRAMMING OPTIMIZATION BY USING PRIMAL-DUAL INTERIOR POINT ALGORITHM NIKE DWI WINARTI NRP 5202 100 028 Supervisor Rully Soelaiman, S.Kom, M.Kom INFORMATION SYSTEM DEPARTMENT Information Technology Faculty Institut Teknologi Sepuluh Nopember Surabaya 2007

2

OPTIMASI PEMROGRAMAN KUADRATIK DENGAN MENGGUNAKAN ALGORITMA PRIMAL-DUAL INTERIOR POINT

TUGAS AKHIR Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer pada Jurusan Sistem Informasi Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Oleh : NIKE DWI WINARTI Nrp. 5202 100 028

Disetujui oleh Pembimbing Tugas Akhir : Rully Soelaiman, S.Kom, M.Kom

SURABAYA,

………...(Pembimbing I)

FEBRUARI, 2007

iii

OPTIMASI PEMROGRAMAN KUADRATIK DENGAN MENGGUNAKAN ALGORITMA PRIMAL-DUAL INTERIOR POINT Nama Mahasiswa : NIKE DWI WINARTI NRP : 5202 100 028 Jurusan : SISTEM INFORMASI FTIF-ITS Dosen Pembimbing : RULLY SOELAIMAN, S.Kom, M.Kom

Abstrak Pencarian solusi optimal pada pemrograman kuadratik dapat dilakukan dengan menggunakan modifikasi pada metode simpleks. Metode simpleks bergantung pada pencarian extreme point, yang kadang harus dilakukan pencarian seluruh extreme point yang ada sebelum mendapatkan solusi yang optimal. Terdapat metode interior-point yang tidak bergantung pada extreme point, karena pencarian dimulai dari daerah interior lalu menuju ke titik solusi. Pada tugas akhir ini diimplementasikan algoritma interior-point untuk menyelesaikan permasalahan pemrograman kuadatik dengan menggunakan dua metode pencarian nilai steplength multiplier yaitu, metode 1 yang umum digunakan dan metode 2 yang mempertimbangkan merit function. Pencarian solusi melalui beberapa tahap, yaitu pemberian titik awal yang berada di interior daerah batasan, menghitung move direction untuk titik x,y,z, menghitung nilai steplength multiplier dan perubahan (update) terhadap titik x,y,z. Uji coba dilakukan dengan menggunakan 16 contoh permasalahan pemrograman kuadratik dengan nilai titik awal (starting point) yang berbeda untuk setiap permasalahan. Berdasarkan hasil uji coba didapatkan bahwa kedua metode pencarian nilai steplength multiplier dapat menyelesaikan permasalahan kuadratik, dari titik awal yang berada di interior menuju ke titik solusi yang berada di batasan (boundary). Pada iv

penggunaan nilai pengali untuk pengurang parameter barrier yang kecil (0.005) dan terdapat beberapa nilai pada titik x,y,znya cukup kecil, metode 2 akan membutuhkan jumlah iterasi yang lebih sedikit, dengan penurunan jumlah iterasi sebanyak 18.5% apabila dibandingkan dengan menggunakan metode 1. Kata kunci : interior point, pemrograman kuadratik, optimasi, steplength selection

v

QUADRATIC PROGRAMMING OPTIMIZATION BY USING PRIMAL-DUAL INTERIOR POINT ALGORITHM Name NRP Departement Supervisor

: NIKE DWI WINARTI : 5202 100 028 : INFORMATION SYSTEM FTIF-ITS : RULLY SOELAIMAN, S.Kom, M.Kom

Abstract In quadratic programming, optimal solution can be found by using modified simplex method. Simplex method depend on finding extreme point, where all feasible extreme point are visited before the optimum solution is reached. Interior point method is not depend on extreme point, because the algorithm cuts across the interior of the solution space to optimal solution. In this final project, interior point algorithm is implemented to solve quadratic programming problems. This method uses two steplength multiplier methods, such as, the first common method and the second method which is use merit function. Searching optimal solution by several stage, such as, choose any starting feasible interior point solution, construct the next move direction for point x,y,z, choose steplength multiplier, update the new solution for point x,y,z. Experiments is done by 16 data quadratic programming with different starting point for each data. From the conclusion, both of steplength multplier strategies can solve quadratic programming problems form interior point into optimal solution point where is in boundary. By using small reducing value (0.005) and existing small value of point x,y,z, the number of iteration in second steplength multiplier method will decrease by 18.25% compared with the first method. Key Words : interior point, optimization, steplength selection vi

quadratic

programming,

KATA PENGANTAR

Tak ada kata yang terucap selain Syukur Alhamdulillah atas segala petunjuk, pertolongan, kasih sayang, dan ridho Allah SWT, sehingga penulis dapat menyelesaikan laporan tugas akhir dengan judul ” OPTIMASI PEMROGRAMAN KUADRATIK DENGAN MENGGUNAKAN ALGORITMA PRIMAL-DUAL INTERIOR-POINT”, yang merupakan salah satu syarat kelulusan pada Program Studi Sistem Informasi, Fakutas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya. Ucapan terima kasih penulis sampaikan kepada: •

Bapak Rully Soelaiman, S.Kom, M.Kom, selaku dosen pembimbing penulis yang telah banyak memberikan arahan, nasehat yang berharga, bimbingan, waktu, dan bantuan selama penyusunan tugas akhir.

•

Semua Bapak dan Ibu Dosen Pengajar serta seluruh staff dan karyawan di Program Studi Sistem Informasi, FTIF ITS Surabaya.

•

Ibu dan Bapak, Mbak Arie dan Mbah Kakung, yang selama ini tulus ikhlas membimbing dan memberikan kasih sayang, materi, nasehat, serta doa-doanya setiap saat tanpa pernah terputus. Semoga Allah selalu menyayangi dan menjaga mereka.

•

Serta semua pihak yang tidak dapat disebutkan satu persatu yang telah ikut membantu baik secara langsung maupun tidak langsung selama penulisan tugas akhir ini

Surabaya, Januari 2007 Penulis

vii

DAFTAR ISI

Abstrak ......................................................................................... iv KATA PENGANTAR.................................................................vii DAFTAR ISI ..............................................................................viii DAFTAR GAMBAR ..................................................................xii DAFTAR TABEL ....................................................................xviii DAFTAR TABEL ....................................................................xviii DAFTAR SIMBOL .................................................................... xix BAB I PENDAHULUAN ............................................................. 1 1.1 Latar Belakang ................................................................. 1 1.2 Tujuan .............................................................................. 3 1.3 Manfaat............................................................................. 3 1.4 Permasalahan.................................................................... 3 1.5 Batasan Permasalahan ...................................................... 3 1.6 Metodologi ....................................................................... 4 1.7 Sistematika Penulisan....................................................... 5 BAB II PERMASALAHAN PEMROGRAMAN KUADRATIK 7 2.1 Bentuk Umum Pemrograman Kuadratik ......................... 7 2.2 Kondisi Convex (Convexity)......................................... 10 2.2.1 Kondisi convex (convexity) secara umum ............... 10 2.2.2 Defferensial (derivatives) dan convexity.................. 12 2.3 Lagrange Multiplier........................................................ 15 2.4 Dualitas pada Pemrograman Kuadratik.......................... 17 2.5 Kondisi Karush-Kuhn-Tucker (KKT) ............................ 20 2.5.1 Kondisi Karush-Kuhn-Tucker (KKT) secara umum21 2.5.2 Kondisi KKT untuk permasalahan kuadratik .......... 23 2.6 Metode Barrier ............................................................... 27 BAB III OPTIMASI DENGAN MENGGUNAKAN ALGORITMA INTERIOR POINT............................................. 37 3.1 Algoritma Optimasi Umum ............................................ 37 3.2 Algoritma Interior Point ................................................. 38 3.3 Algoritma Interior Point untuk Pemrograman Kuadratik.... ............................................................................. 44

viii

3.4 Pencarian Steplength Multiplier .................................... 51 BAB IV PERANCANGAN DAN INPLEMENTASI PERANGKAT LUNAK .............................................................. 55 4.1 Perancangan Data ........................................................... 55 4.1.1 Data masukan........................................................... 55 4.1.2 Data proses............................................................... 56 4.1.3 Data luaran ............................................................... 57 4.2 Perancangan Algoritma .................................................. 57 4.2.1 Tahap pengujian data masukan ................................ 57 4.2.2 Tahap Pencarian Solusi Optimal.............................. 59 4.2.3 Tahap Menampilkan Hasil Proses ........................... 64 4.3 Implementasi Data.......................................................... 65 4.3.1 Data masukan........................................................... 65 4.3.2 Data proses............................................................... 67 4.3.3 Data luaran ............................................................... 68 4.4 Implementasi Proses ....................................................... 69 4.4.1 Tahap pengujian data masukan ................................ 69 4.4.1.1 Pengujian titik awal (starting point), titik solusi , dan pemenuhan kondisi primal – dual infeasibility ......... 69 4.4.1.2 Pengujian kondisi semidefinite positif .............. 71 4.4.2 Tahap pencarian solusi optimal ............................... 72 4.4.2.1 Pemberian nilai awal dan update nilai parameter barrier.... .......................................................................... 76 4.4.2.2 Pengujian kondisi optimal ................................. 77 4.4.2.3 Pencarian nilai move direction .......................... 78 4.4.2.4 Pencarian steplength multiplier ......................... 78 4.4.2.5 Update nilai solusi ............................................. 83 4.4.3 Tahap menampilkan hasil proses ............................. 83 4.4.3.1 Menampilkan solusi optimal ............................. 83 4.4.3.2 Menampilkan grafik perubahan nilai fungsi tujuan...... .......................................................................... 84 4.4.3.3 Menampilkan grafik perubahan titik x .............. 87 BAB V UJI COBA ..................................................................... 91 5.1 Lingkungan Uji Coba ..................................................... 91 5.2 Data Uji Coba ................................................................. 91

ix

5.3 Skenario Uji Coba .......................................................... 92 5.3.1 Skenario I : Uji kebenaran luaran aplikasi ............... 92 5.3.2 Skenario II : Uji pemberian nilai starting point ....... 92 5.3.3 Skenario III : Uji pencarian nilai pengurang parameter barrier ................................................................. 92 5.3.4 Skenario IV : Uji konsistensi terhadap permasalahan lain........................................................................................ 93 5.4 Pelaksanaan Uji Coba..................................................... 93 5.4.1 Uji coba kebenaran aplikasi ..................................... 95 5.4.1.1 Uji coba data 1................................................... 95 5.4.1.2 Uji coba data 2................................................... 99 5.4.1.3 Analisa hasil uji coba skenario I...................... 102 5.4.2 Uji pemberian nilai starting point .......................... 102 5.4.2.1 Uji coba data 1................................................. 102 5.4.2.2 Analisa hasil uji skenario II ............................. 112 5.4.3 Uji coba pencarian nilai pengurang parameter barrier. ............................................................................... 113 5.4.3.1 Uji coba data 1................................................. 113 5.4.3.2 Analisa hasil uji Coba skenario III .................. 122 5.4.4 Uji konsistensi terhadap permasalahan lain ........... 123 5.4.4.1 Uji coba data 2................................................. 123 5.4.4.2 Uji coba data 3................................................. 126 5.4.4.3 Uji coba data 4................................................. 130 5.4.4.4 Uji coba data 5................................................. 133 5.4.4.5 Uji Coba Data 6 ............................................... 136 5.4.4.6 Uji coba data 7................................................. 140 5.4.4.7 Uji coba data 8................................................. 143 5.4.4.8 Uji coba data 9................................................. 146 5.4.4.9 Uji coba data 10............................................... 148 5.4.4.10 Uji coba data 11 .......................................... 151 5.4.4.11 Uji coba data 12 .......................................... 153 5.4.4.12 Uji coba data 13 .......................................... 156 5.4.4.13 Uji coba data 14 .......................................... 159 5.4.4.14 Uji coba data 15 .......................................... 161 5.4.4.15 Uji coba data 16 .......................................... 164

x

5.4.4.16 Analisa hasil uji coba skenario IV .............. 167 BAB VI KESIMPULAN ........................................................... 169 DAFTAR PUSTAKA............................................................... 171 LAMPIRAN A GRAFIK TRAYEKTORI TITIK X HINGGA OPTIMAL .................................................................................A-1 A.1 Uji Coba Data 5 ............................................................A-1 A.2 Uji Coba Data 6 ............................................................A-3 A.3 Uji Coba Data 7 ............................................................A-3 A.4 Uji Coba Data 8 ............................................................A-6 A.5 Uji Coba Data 9 ............................................................A-8 A.6 Uji Coba Data 10 ..........................................................A-9 A.7 Uji Coba Data 11 ........................................................ A-11 A.8 Uji Coba Data 12 ........................................................ A-11 A.9 Uji Coba Data 13 ........................................................ A-12 A.10 Uji Coba Data 14 ........................................................ A-13 A.11 Uji Coba Data 15 ........................................................ A-14 A.12 Uji Coba Data 16 ........................................................ A-14 LAMPIRAN B HASIL UJI COBA UNTUK SETIAP ITERASI ................................................................................................... B-1 B.1 Uji Coba Data 1 ............................................................ B-1 B.2 Uji Coba Data 2 ............................................................ B-5 B.3 Uji Coba Data 3 ............................................................ B-6 B.4 Uji Coba Data 4 ............................................................ B-9 B.5 Uji Coba Data 5 .......................................................... B-11 B.6 Uji Coba Data 6 .......................................................... B-15 B.7 Uji Coba Data 7 .......................................................... B-18 B.8 Uji Coba Data 8 .......................................................... B-22 B.9 Uji Coba Data 9 .......................................................... B-24 B.10 Uji Coba Data 10 ........................................................ B-26 B.11 Uji Coba Data 11 ........................................................ B-28 B.12 Uji Coba Data 12 ........................................................ B-30 B.13 Uji Coba Data 13 ........................................................ B-31 B.14 Uji Coba Data 14 ........................................................ B-33 B.15 Uji Coba Data 15 ........................................................ B-35 B.16 Uji Coba Data 16 ........................................................ B-37

xi

DAFTAR GAMBAR Gambar 2.1 Garis Penghubung titik x dan y ............................... 11 Gambar 2.2 Convex dan Non-convex set ..................................... 11 Gambar 2.3 Fungsi Convex ......................................................... 12 Gambar 2.4 Perubahan Nilai Gap Fungsi Tujuan Bentuk PrimalDual ............................................................................................. 19 Gambar 2. 5 Nilai Gap Bentuk Primal-Dual ............................... 19 Gambar 2.6 Solusi Permasalahan Unbounded dengan Metode Interior Point ............................................................................... 26 Gambar 2.7 Solusi optimal yang bersifat unbounded ................ 27 Gambar 2.8 Pengaruh dari Barrier Term .................................... 29 Gambar 2.9 Pencapaian Fungsi Tujuan dgn μ+ = (x+'*z+)/n ........ 32 Gambar 2.10 Pencapaian Fungsi Tujuan dgn α Metode 1 dan Untuk Setiap Iterasi μ+ = 0.005*μ ........................................... 33 Gambar 2.11 Pencapaian Fungsi Tujuan dgn α Metode 2 dan Untuk Setiap Iterasi μ+ = 0.005*μ ........................................... 33 Gambar 2.12 Pencapaian Fungsi Tujuan dgn α Metode 1 dan Jika (abs(gap1-gap2)
xii

Gambar 4.5a Pseudocode Pencarian Steplength Multiplier Metode2....................................................................................... 62 Gambar 4.5b Lanjutan Pseudocode Pencarian Steplength Multiplier Metode2 ..................................................................... 63 Gambar 4.6 Pseudocode Menampilkan Hasil Proses .................. 64 Gambar 4.7 Variabel Data Masukan ........................................... 65 Gambar 4.8 Kode Program Pengujian Titik Awal ..................... 70 Gambar 4.9 Kode Program Pengujian Kondisi Semidefinite Positif .......................................................................................... 71 Gambar 4.10a Kode Program Utama Interior_Point.m .......... 72 Gambar 4.10b Lanjutan Kode Program Utama Interior_Point.m...................................................................... 73 Gambar 4.10c Lanjutan Kode Program Utama Interior_Point.m...................................................................... 74 Gambar 4.10d Lanjutan Kode Program Utama Interior_Point.m...................................................................... 75 Gambar 4.11 Kode Program Nilai Awal Parameter Barrier ...... 76 Gambar 4.12 Kode Program Update Parameter Barrier ............ 77 Gambar 4.13 Kode Program Pengujian Kondisi Optimal .......... 77 Gambar 4.14 Kode Program Pencarian Nilai Move Direction ... 78 Gambar 4.15 Kode Program Pemanggilan Program steplength .. 79 Gambar 4.16 Kode Program Pencarian Steplength Multiplier Metode 1...................................................................................... 80 Gambar 4.18 Kode Program Update Nilai Solusi ...................... 83 Gambar 4.19 Kode Program Menampilkan Solusi Optimal....... 84 Gambar 4.20 Kode Program Pengisian Data Grafik dan Pemanggilan Program plotline.m ............................................. 85 Gambar 4.21 Kode Program Pembuatan Grafik Garis ............... 86 Gambar 4.22 Kode Program Pengisian Data Grafik dan Pemanggilan Program plotTitikX.m ........................................ 87 Gambar 4.23 Kode Program untuk Kelayakan Grafik Titik x ... 88 Gambar 4.24 Kode Program Pembuatan Grafik Perubahan Titik x .......................................................................................... 89 Gambar 5.1 Pencapaian Fungsi Tujuan data-1 dgn α Metode1...97 Gambar 5.2 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1..... 97

xiii

Gambar 5.3 Pencapaian Fungsi Tujuan data-1 dgn α Metode2.. 98 Gambar 5.4 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2..... 98 Gambar 5.5 Pencapaian Fungsi Tujuan data-2 dgn α Metode1. 100 Gambar 5.6 Grafik Trayektori (x 1 ,x 2 ) data-2 dgn α Metode1.. 100 Gambar 5.7 Pencapaian Fungsi Tujuan data-2 dgn α Metode2. 101 Gambar 5.8 Grafik Trayektori (x 1 ,x 2 ) data-2 dgn α Metode2.. 101 Gambar 5.9 Pencapaian Fungsi Tujuan data-1b dgn α Metode1 dan θ = 0.005 ............................................................................. 103 Gambar 5.10 Grafik Trayektori (x 1 ,x 2 ) data-1b dgn α Metode1 dan θ = 0.005 ............................................................................. 103 Gambar 5.11 Pencapaian Tungsi Tujuan data 1b dgn α Metode2 dan θ = 0.005 ............................................................................. 104 Gambar 5.12 Grafik Trayektori (x 1 ,x 2 ) data-1b dgn α Metode2 dan θ = 0.005 ............................................................................. 105 Gambar 5.13 Pencapaian Fungsi Tujuan data-1b dgn α Metode1 dan θ = 0.5 ................................................................................. 105 Gambar 5.14 Grafik Trayektori (x 1 ,x 2 ) data-1b dgn α Metode1 dan θ = 0.5 ................................................................................. 106 Gambar 5.15 Pencapaian Fungsi Tujuan data-1b dgn α Metode2 dan θ = 0.5 ................................................................................. 106 Gambar 5.16 Grafik Trayektori (x 1 ,x 2 ) data-1b dgn α Metode2 dan θ = 0.5 ................................................................................. 107 Gambar 5.17 Pencapaian Fungsi Tujuan data-1 dgn α Metode1 dan θ = 0.005 ............................................................................. 108 Gambar 5.18 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1 dan θ = 0.005 ............................................................................. 108 Gambar 5.19 Pencapaian Fungsi Tujuan data-1 dgn α Metode2 dan θ = 0.005 ............................................................................. 109 Gambar 5.20 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2 dan θ = 0.005 ............................................................................. 109 Gambar 5.21 Pencapaian Fungsi Tujuan data-1 dgn α Metode1 dan θ = 0.5 ................................................................................. 110 Gambar 5.22 Grafik Trayektori (x 1 ,x 2 ) data-1 dengan α Metode1 dan θ = 0.5 ................................................................................. 110

xiv

Gambar 5.23 Pencapaian Fungsi Tujuan data-1 dgn α Metode2 dan θ = 0.5 ................................................................................. 111 Gambar 5.24 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α metode2 dan θ = 0.5 ........................................................................................ 112 Gambar 5.25 Pencapaian Fungsi Tujuan data-1 dgn α Metode1 dan θ = 0.5 ................................................................................. 114 Gambar 5.26 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1 dan θ = 0.5 ........................................................................................ 114 Gambar 5.27 Pencapaian Fungsi Tujuan data-1 dgn α Metode2 dan θ = 0.5 ................................................................................. 115 Gambar 5.28 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2 dan θ = 0.5 ........................................................................................ 115 Gambar 5.29 Pencapaian Fungsi Tujuan data-1 dgn α Metode1 dan θ = 0.05 ............................................................................... 116 Gambar 5.30 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1 dan θ = 0.05 ...................................................................................... 116 Gambar 5.31 Pencapaian Fungsi Tujuan data-1 dgn α Metode2 dan θ = 0.05 ............................................................................... 117 Gambar 5.32 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2 dan θ= 0.05 ................................................................................ 117 Gambar 5.33 Pencapaian Fungsi Tujuan data-1 dgn α Metode1 dan θ = 0.005 ............................................................................. 118 Gambar 5.34 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1 dan θ = 0.005 ............................................................................. 119 Gambar 5.35 Pencapaian fFungsi Tujuan data-1 dgn α Metode2 dan θ = 0.005 ............................................................................. 119 Gambar 5.36 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2 dan θ = 0.005 ............................................................................. 120 Gambar 5.37 Pencapaian fungsi tujuan data 1 dgn α metode1 dan θ = 0.0005 .................................................................................. 120 Gambar 5.38 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode1 dan θ = 0.0005 ........................................................................... 121 Gambar 5.39 Pencapaian Fungsi Tujuan data-1 dgn α Metode2 dan θ = 0.0005 ........................................................................... 121

xv

Gambar 5.40 Grafik Trayektori (x 1 ,x 2 ) data-1 dgn α Metode2 dan θ = 0.0005 ........................................................................... 122 Gambar 5.41 Pencapaian Fungsi Tujuan data-2 dgn α Metode1 ................................................................................................... 124 Gambar 5.42 Grafik Trayektori (x 1 ,x 2 ) data-2 dgn α Metode1. 125 Gambar 5.43 Pencapaian Fungsi Tujuan data-2 dgn α Metode2 ................................................................................................... 126 Gambar 5.44 Grafik Trayektori (x 1 ,x 2 ) data-2 dgn α Metode2. 126 Gambar 5.45 Pencapaian Fungsi Tujuan data-3 dgn α Metode1 ................................................................................................... 128 Gambar 5.46 Grafik Trayektori (x 1 ,x 2 ) data-3 dgn α Metode1. 128 Gambar 5.47 Pencapaian Fungsi Tujuan data-3 dgn α Metode2 ................................................................................................... 129 Gambar 5.48 Grafik Trayektori (x 1 ,x 2 ) data-3 dgn α Metode2. 129 Gambar 5.49 Pencapaian Fungsi Tujuan data-4 dgn α Metode1 ................................................................................................... 131 Gambar 5.50 Grafik Trayektori (x 1 ,x 2 ) data-4 dgn α Metode1. 132 Gambar 5.51 Pencapaian Fungsi Tujuan data-4 dgn α Metode2 ................................................................................................... 133 Gambar 5.52 Grafik Trayektori (x 1 ,x 2 ) data-4 dgn α Metode2. 133 Gambar 5.53 Pencapaian Fungsi Tujuan data-5 dgn α Metode1 ................................................................................................... 135 Gambar 5.54 Pencapaian Fungsi Tujuan data-5 dgn α Metode2 ................................................................................................... 136 Gambar 5.55 Pencapaian Fungsi Tujuan data-6 dgn α Metode1 ................................................................................................... 138 Gambar 5.56 Pencapaian Fungsi Tujuan data-6 dgn α Metode2 ................................................................................................... 139 Gambar 5.57 Pencapaian Fungsi Tujuan data-7 dgn α Metode1 ................................................................................................... 142 Gambar 5.58 Pencapaian Fungsi Tujuan data-7 dgn α Metode2 ................................................................................................... 143 Gambar 5.59 Pencapaian Fungsi Tujuan data-8 dgn α Metode1 ................................................................................................... 144

xvi

Gambar 5.60 Pencapaian Fungsi Tujuan data-8 dgn α Metode2 ................................................................................................... 145 Gambar 5.61 Pencapaian Fungsi Tujuan data-9 dgn α Metode1 ................................................................................................... 147 Gambar 5.62 Pencapaian Fungsi Tujuan data-9 dgn α Metode2 ................................................................................................... 148 Gambar 5.63 Pencapaian Fungsi Tujuan data-10 dgn α Metode1 ................................................................................................... 150 Gambar 5.64 Pencapaian Fungsi Tujuan data-10 dgn α Metode2 ................................................................................................... 151 Gambar 5.65 Pencapaian Fungsi Tujuan data-11 dgn α Metode1 ................................................................................................... 152 Gambar 5.66 Pencapaian Fungsi Tujuan data-11 dgn α Metode2 ................................................................................................... 153 Gambar 5.67 Pencapaian Fungsi Tujuan data-12 dgn α Metode1 ................................................................................................... 155 Gambar 5.68 Pencapaian Fungsi Tujuan data-12 dgn α Metode2 ................................................................................................... 155 Gambar 5.69 Pencapaian Fungsi Tujuan data-13 dgn α Metode1 ................................................................................................... 157 Gambar 5.70 Pencapaian Fungsi Tujuan data-13 dgn α Metode2 ................................................................................................... 158 Gambar 5.71 Pencapaian Fungsi Tujuan data-14 dgn α Metode1 ................................................................................................... 160 Gambar 5.72 Pencapaian Fungsi Tujuan data-14 dgn α Metode2 ................................................................................................... 161 Gambar 5.73 Pencapaian Fungsi Tujuan data-15 dgn α Metode1 ................................................................................................... 163 Gambar 5.74 Pencapaian Fungsi Tujuan data-15 dgn α Metode2 ................................................................................................... 164 Gambar 5.75 Pencapaian Fungsi Tujuan data-16 dgn α Metode1 ................................................................................................... 165 Gambar 5.76 Pencapaian Fungsi Tujuan data-16 dgn α Metode2 ................................................................................................... 166

xvii

DAFTAR TABEL Tabel 2.1 Kondisi Perlu dan Cukup Untuk Optimal ................... 21 Tabel 4.1 Data Masukan.............................................................. 65 Tabel 4.2 Contoh Data Masukan ................................................ 67 Tabel 4.3 Data Proses .................................................................. 67 Tabel 4.4 Contoh Data Proses .................................................... 68 Tabel 4.5 Data Luaran ................................................................. 68 Tabel 4.6 Contoh Data Luaran ................................................... 69 Tabel 5.1 Lingkungan Pengujian Aplikasi .................................. 91

xviii

DAFTAR SIMBOL φ (x ) μ µφ (x ) θ λ ZP

: : : : : :

Fungsi barrier Parameter barrier Fungsi barrier term Nilai pengali untuk pengurang paramater barrier Lagrange Multiplier Nilai fungsi tujuan untuk permasalahan bentuk primal ZD : Nilai fungsi tujuan untuk permasalahan bentuk dual Δx : Move Direction untuk titik x Δy : Move Direction untuk titik y Δz : Move Direction untuk titik z e : Vektor yang seluruh nilai elemennya adalah 0 α : Steplength Multiplier secara umum β : Nilai pengali untuk pencarian steplength multiplier αx : Steplength Multiplier untuk titik x αy : Steplength Multiplier untuk titik y αz : Steplength Multiplier untuk titik z gap : Selisih nilai fungsi tujuan untuk permasalahan bentuk primal dan dual x,y,z,c,b,Q, dan A : Vektor pembentuk permasalahan kuadratik n : Jumlah banyaknya variabel x m : Jumlah banyaknya persamaan pembatas/batasan (constraint) t : Menunjukkan jumlah iterasi

xix