BAB 2 KAJIAN PUSTAKA

BAB 2 KAJIAN PUSTAKA

2.1 Program Linier Penyelesaian program linear dengan algoritma interior point dapat merupakan sebuah penyelesaian persoalan yang kompleks. Permasalahan dalam program linier mungkin saja persoalan tersebut memiliki banyak kendala. Penggunaan metode interior point dilakukan melalui proses relaksasi sampai pada tahapan persoalan program linier memiliki solusi yang baik dan layak serta merupakan solusi optimal. Permasalahan program linier yang kompleks, untuk menemukan solusi optimal yang merupakan daerah jawab dapat diselesaikan dengan melakukan kombinasi antara metode simpleks dengan algoritma interior point, (Bixby & Gregory, 1992). Model interior point erat kaitannya dengan metode branch dan bound terutama yang berhubungan dengan permasalahan mencari solusi optimal dari persoalan optimisasi. Permasalahan yang dihadapi dalam menyelesaikan permasalahan program linier adalah menentukan sistem penyelesaian dengan menggunakan algoritma interior point untuk memperoleh solusi yang optimal. Kesulitan yang lain adalah bagaimana menggambarkan keseluruhan model dengan sebuah algoritma interior point. Model algoritma interior point yang dimaksud berfokus pada bagaimana teknik komputasi dilakukan dengan menggunakan beberapa referensi ataupun teori dasar yang berlaku. Persoalan program integer dengan menggunakan algoritma interior point yaitu branch dan cut method adalah pendekatan yang dilakukan dengan memadukan metode branch and bound dan cutting plane sebagai pendekatan model program integer yang dimaksud.

4 Universitas Sumatera Utara

5 Kedua pendekatan tersebut adalah sebuah kombinasi yang baik untuk dapat digunakan sebagai penyelesaian dalam persoalan program integer. Model deterministik adalah salah satu model yang telah digunakan untuk penyelesaian program integer. Model deterministik dapat didefinisikan sebagai sebuah formula yang berdasarkan pada penentuan sebuah solusi terbaik dari permasalahan yang memiliki konfigurasi atau karakteristik tertentu. Model deterministik dapat dipakai untuk menentukan maksimum atau minimum jarak dari suatu titik ke titik lain. Untuk menentukan maksimum atau minimum dari sebuah fungsi yang mempunyai kendala x dalam himpunan kendala X maka model deterministiknya dapat ditulis sebagai sebuah model maksimum atau minimum. Model deterministik dapat digunakan sebagai salah satu model pendekatan untuk persoalan program integer dengan teknik membagi-bagi data kedalam kelompok yang sama. Sehingga diperoleh suatu nilai bulat yang dipilih mewakili masingmasing kelompok. Data yang bulat diinput terdiri dari parameter ρij yang menunjukkan kesamaan dari setiap pasang data integer (i, j) untuk setiap kelompok program integer yang dimodelkan kepada bentuk interior point dengan algoritmanya. Model deterministik yang diperoleh akan lebih mudah digunakan karena memuat koefisien-koefisien korelasi sebagai parameter yang sama untuk setiap kelompok, tetapi masih terdapat kemungkinan faktor lain yang mempengaruhi pemodelan program integer pada masing-masing kelompok. Pendekatan dengan model deterministik tidak memberikan jaminan akan menghasilkan model serta penyelesaian yang efisien, tetapi pada dasarnya menghasilkan indeks lebih baik sebagai solusi optimal yang diinginkan untuk dicapai. Metode penyelesaian yang menggunakan algoritma interior point selalu berhubungan dengan segmen garis yang bersifat maksimum atau minimum. Persoalan interior point erat hubungannya dengan konveksitas yang mengarah kepada penyelesaian persoalan bersifat program integer.

Universitas Sumatera Utara

6 2.2 Program Integer Program integer banyak ditemukan dalam persoalan-persoalan yang berhubungan dengan keadaan yang sebenarnya yang terjadi dialam. Program integer menggunakan data yang bulat sesuai satuan data yang tidak dapat dipecah-pecah menjadi data yang lebih kecil lagi. Program integer banyak dipakai didunia pemrograman komputer untuk menentukan nilai maksimum ataupun minimum dari suatu proses yang akan dihitung. Program integer tergolong pemrograman yang sederhana jika ditinjau dari penggunaan satuan data yang digunakan. Hal ini membuat program integer menjadi program yang paling sering dijadikan program dasar untuk lebih memudahkan perhitungan dengan bentuk data yang bulat atau tidak adanya pembulatan sehingga dipastikan keseluruhan data dapat diolah sedemikian rupa menjadi lebih mudah. Penyelesaian persoalan program integer salah satunya dengan menggunakan algoritma interior point untuk menghitung nilai optimal dari sebuah persoalan optimisasi. Metode yang digunakan yaitu branch dan cut method yang merupakan sebuah pendekatan yang dilakukan dengan memadukan metode branch and bound dan cutting plane sebagai pendekatan model program integer yang dimaksud. Kedua pendekatan tersebut adalah sebuah kombinasi yang baik untuk dapat digunakan sebagai penyelesaian dalam persoalan program integer.

2.3 Interior Point Interior point pada dasarnya adalah penggunaan metode cutting plane dan metode branch and bound untuk menyelesaikan persoalan optimisasi yang bersifat program integer. Beberapa permasalahan program linier diselesaikan dengan mengidentifikasi permasalahan menjadi zero variabel ataupun sampai tidak memiliki kendala lagi dalam penyelesaian persoalan program linier dengan menggunakan interior point, (El-Bakry et al, 1991). Algoritma interior point yang digunakan untuk menyelesaikan masalah optimisasi terlebih dahulu disederhanakan


7 dengan menghilangkan faktor-faktor ataupun kendala yang dapat dihilangkan dengan melakukan proses relaksasi dengan iterasi. Pendekatan metode cutting plane dan metode branch and bound dapat dikombinasikan menjadi sebuah algoritma yang disebut algoritma branch dan cut dengan menggunakan tahapan tertentu sehingga menghasilkan metode interior point. Algoritma branch and cut tersebut kemudian dinamakan algoritma interior point. Model awal dari program integer dinyatakan dengan : Min cT x Kendala

(2.1)

Ax ≥ b x∈Z

dimana x dan c adalah vektor berbasis n dan b adalah vector berbasis m dimana A adalah matriks m × n, dan solusi penyelesaian diperoleh dari variable yang bersifat biner. Untuk memperoleh penyelesaian yang layak dari persoalan diatas dapat diselesaikan dengan mencari solusi persoalan program linier dari sebuah polyhedron Q dengan min{cT x, x ∈ Q}. Model iterasi program linier dengan primal dual untuk menentukan sebuah titik sebagai solusi penyelesaian dapat ditentukan dengan pendekatan primal dual sebagai alat koreksi untuk menentukan daerah jawab yang optimal sebagai jawab akhir dari problema interior point (Lustig & Mehrota, 1992) Dari penyelesaian tersebut diatas akan diperoleh beberapa solusi optimal yang penyelesaiannya dapat menggunakan algoritma interior point. Kesulitan daripada penggunaan model yang diekspresikan dengan polyhedron Q adalah menjabarkannya menjadi metode cutting plane dengan menggunakan model relaksasi dengan program linier. Model relaksasi program linier dapat ditulis : Min cT x Kendala

(2.2)

Ax ≥ b 0≤x≤e


8 dimana e adalah sebuah vector dari salah satu solusi persoalan yang merupakan solusi layak model optimisasi tersebut. Kemudian daerah penyelesaian yang lain dapat ditentukan dengan : QLP P = {x ∈ Rn : Ax ≥ b, 0 ≤ x ≤ e}

(2.3)

Sehingga diperoleh model : Max Kendala

bT y − eT w AT y − w ≤ c

(2.4)

y, w ≥ 0 Dimana y adalah merupakan bagian dari m yaitu vektor baris dan w bagian dari n yaitu vektor kolom.Selanjutnya diperoleh variable s = Ax − b yang merupakan variabel slack dari primal program linier dan x = c − AT y + w dan x merupakan bagian vektor n dengan diagonal matriks n × n dari Xii = xi . Matriks diagonal Y, W, Z dan S kemudian dapat diperoleh dengan melakukan iterasi terhadap model : XZe − µe = 0, SY e − µe = 0, (I − X)W e − µe = 0

(2.5)

Pendekatan yang digunakan dengan memakai µ sebagai dasar dari proses iterasi yang dilakukan dengan menggunakan vector dan variable µ sebagai scalar.

2.4 Optimisasi dengan Algoritma Interior Point Persoalan optimisasi program integer dapat diselesaikan dengan menggunakan algoritma cutting plane yaitu relaksasi program linier dengan menentukan solusi optimal x yang ditentukan dengan model cutting plane adalah : aT0 x = b0

(2.6)

dimana a0 adalah n vector dan b0 adalah sebuah scalar. Penentuan solusi layak ditentukan dengan variable x ˆ dari ˆ < b0 aT0 x


9 selanjutnya nilai x ˆ yang memenuhi daerah jawab adalah ˆ ≥ b0 aT0 x Kendala aT0 x ˆ ≥ b0 dimuat dalam model program linear dengan menggunakan relaksasi program linear adalah : Min cT x Kendala

(2.7)

Aˆ x≥b ˆ ≥ b0 aT0 x 0≤x ˆ≤e

Dengan menggunakan metode dual problem model optmisasi (2.7) dapat ditulis menjadi : Max Kendala

bT y + b0y0 − eT w AT y + a0y0 − w ≤ c y, y0, w ≥ 0

dimana y0 adalah sebuah scalar dan proses iterasi dilakukan sehingga diperoleh x ˆ sebagai jawab solusi awal. Pengembangan model cutting plane sebagai bagian dari algoritma interior point dapat menggunakan metode analisis solusi daerah penyelesaian tertentu yaitu menentukan daerah jawab berdasarkan persoalan optimisasi yang diselesaikan secara relaksasi. (Atkinson & Vaidya, 1992) Metode yang sederhana untuk menyelesaikan persoalan optimisasi program linier dengan menggunakan algoritma cutting plane adalah dengan menggunakan algoritma dual simpleks. Untuk menyelesaikan persoalan optimisasi program linier dengan interior point, langkah pertama yang dilakukan adalah menentukan nilai interior yang memenuhi daerah jawab dari variable x sebagai solusi yang diinginkan setelah melakukan iterasi dengan kendala yang telah ditetapkan. Kesulitan yang dihadapi adalah menentukan nilai variable y0 menjadi nilai positif yang semakin kecil walaupun iterasi dual yang dilakukan mungkin tidak layak.


10 Solusi layak dari persoalan interior point dapat digunakan untuk menyelesaikan persoalan optimisasi program linier dengan melakukan primal atau dual iterasi. Metode interior point diselesaikan dengan cara terlebih dahulu menentukan primal dan dual slack. Persoalan yang kompleks untuk optimisasi program linier diselesaikan dengan melakukan iterasi secara primal atau dual. Dengan melakukan proses iterasi primal dan dual maka diperoleh solusi yang layak berupa daerah jawab sebagai solusi yang merupakan nilai optimal yang disebut dengan titik optimal sebagai jawab untuk interior point yang diinginkan dari persoalan optmisasi program integer. Dalam beberapa kasus persoalan optimisasi program integer yang kompleks, jika penyelesaian optimisasi dengan melakukan iterasi tidak memperoleh solusi optimal, maka dapat digunakan metode cutting plane pada daerah jawab yang mungkin belum memiliki solusi optimal. Jika solusi optimal belum diperoleh maka tahapan iterasi program integer dengan menggunakan konsep interior point dari algoritma cutting plane dilakukan dengan tahapan sebagai berikut: Lakukan proses inisialisasi, tentukan variable slack dan model primal dual yang akan dilakukan, selanjutnya lakukan proses relaksasi, dimana solusi yang layak diperoleh dengan beberapa kali melakukan iterasi dengan menggunakan algoritma interior point. Jika proses iterasi dilakukan sudah pada tahapan yang maksimal maka solusi yang akurat dan diinginkan sudah diperoleh sehingga proses iterasi berhenti. Implementasi selanjutnya adalah dengan menggunakan metode cutting plane, perhatikan beberapa kendala yang mungkin belum dipenuhi ketika sudah diperoleh solusi optimal, jika memang terdapat kendala yang belum terpenuhi maka tahapan penggunaan metode cutting plane harus dilakukan. Proses penyelesaian akhir yang dilakukan adalah proses relaksasi kembali seperti tahapan dua jika persoalan optimisasi program integer belum mempunyai daerah jawab sebagai solusi optimal.


11 Tahapan yang paling baik untuk menyelesaikan persoalan optimisasi program integer adalah dengan menggunakan primal dual yang dilakukan dengan tahapan relaksasi melalui iterasi-iterasi dengan algoritma cutting plane. Beberapa persoalan algoritma interior point menggunakan iterasi primal dual seperti yang dilakukan dalam penyelesaian optimisasi dengan menggunakan algoritma cutting plane. Algoritma cutting plane dimulai dengan melakukan pemisahan secara bertahap dengan menyederhanakan variable-variabel yang kompleks menjadi penyelesaian yang sederhana untuk mendapatkan hasil yang optimal. Model penyelesaian yang paling penting adalah memperhatikan kendalakendala yang muncul pada tahapan relaksasi dengan melakukan iterasi untuk memperoleh solusi optimal. Solusi yang diperoleh mungkin saja tidak menemukan titik cutting plane, walaupun secara teknis diupayakan menemukan titik cutting plane sebagai jawab layak dari permasalahan program integer yang diselesaikan.


BAB 2 KAJIAN PUSTAKA

Recommend Documents