Makalah Seminar Tugas Akhir Periode Januari 2010
PENCARIAN HIMPUNAN SOLUSI ALTERNATIF PADA PERMASALAHAN GENERAL INTEGER LINEAR PROGRAMS MEMANFAATKAN GENERAL INTEGER CUT Ade Vicidian S. P. – Yudhi Purwananto, S.Kom, M.Kom. - Victor Hariadi, S.Si, M.Kom. Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya, Email:
[email protected] Abstrak Banyaknya permasalahan yang terjadi dalam hal pengalokasian sumber-sumber yang terbatas diantara beberapa aktivitas yang bersaing, seperti permasalahan pengalokasian fasilitas produksi, permasalahan pengalokasian sumber daya nasional untuk kebutuhan domestik, penjadwalan produksi, solusi permainan (game), dan pemilihan pola pengiriman (shipping), harus diselesaikan dengan cara yang terbaik (optimal) yang mungkin untuk dilakukan. Salah satu cara untuk menyelesaikan permasalahan tersebut digunakanlah linier programming (LP). Beberapa riset telah dilakukan untuk menyelesaikan permasalahan-permasalahan linier programming. Untuk permasalahan tertentu, seperti jika suatu permasalahan yang seluruh variabelnya adalah integer maka harus digunakan integer linier programming (ILP) untuk menyelesaikannya yaitu untuk mendapatkan solusi optimal dan nilai objektif. Setelah didapatkan solusi optimal maka dapat dicari solusi optimal yang lain atau solusi alternatif lain diluar solusi optimal awal, salah satu cara yang digunakan adalah menggunakan model general integer cut. Dimana general integer cut tersebut didapatkan dengan cara menambahkan fungsi kendala baru yang berisi formulasi ulang solusi optimal yang didapat sebelumnya sehingga menghasilkan solusi alternatif baru dengan menghilangkan kemungkinan kemunculan solusi optimal yang sudah ada sebelumnya dengan tetap menghasilkan nilai objektif yang sama. Kata Kunci : linier programming, integer linier programming, model general integer cut, solusi alternatif general integer cut dikembangkan sehingga solusi 1. PENDAHULUAN alternatif dari masalah ILP dapat ditemukan jika Program linier yang diterjemahkan dari Linear lebih dari satu solusi dapat memenuhi nilai optimal Programing (LP) adalah suatu cara untuk yang sama dari fungsi objektif, karena menyelesaikan masalah pengalokasian sumbermemungkinkan pembuat keputusan untuk memilih sumber yang terbatas diantara beberapa aktivitas dari banyak solusi tanpa mencoba berbagai yang bersaing, dengan cara yang terbaik yang kelemahan/keburukan pada fungsi objektif. mungkin dilakukan. Permasalahan pengalokasian ini akan muncul manakala sesorang harus memilih 2. PROGRAM LINIER tingkat aktivitas-aktivitas tersebut. Beberapa Program linier (Linear Programming/LP), kadangcontoh situasi dari uraian diatas antara lain adalah kadang dikenal sebagai optimasi linear, adalah permasalahan pengalokasian fasilitas produksi, masalah memaksimalkan atau meminimalkan permasalahan pengalokasian sumber daya nasional fungsi linear atas convex polyhedron yang untuk kebutuhan domestik, penjadwalan produksi, ditentukan oleh linier dan non-negativitas kendala. solusi permainan (game), dan pemilihan pola Secara khusus, permasalahan program linier adalah pengiriman (shipping). Satu hal yang menjadi ciri suatu permasalahan untuk menentukan besarnya situasi diatas ialah adanya keharusan untuk masing-masing nilai variabel (variabel mengalokasikan sumber terhadap aktivitas. pengambilan keputusan) sedemikian rupa sehingga Program linier ini menggunakan model matematis nilai fungsi tujuan atau objektif (objective untuk menjelaskan permasalahan yang function) yang linier menjadi optimal (maksimum dihadapinya. Sifat “Linier” disini memberi arti atau minimum) dengan memperhatikan bahwa seluruh fungsi matematis dalam model ini pembatasan-pembatasan (kendala-kendala) yang merupakan fungsi yang linier, sedangkan kata ada yaitu pembatasan ini harus dinyatakan dengan “Program” merupakan sinonim untuk perencanaan. ketidaksamaan yang linier (linear inequalities). Dengan demikian, Program Linier adalah perencanaan aktivitas-aktivitas untuk memperoleh 2.1. Perumusan Model Permasalahan hasil yang optimal, yaitu suatu hasil yang Program Linier mencapai tujuan terbaik diantara seluruh alternatif Pada dasarnya secara umum, permasalahan yang layak (feasible). program linier dapat dirumuskan dalam suatu Program Linier berhubungan dengan variabel model dasar/model baku/model matematika kontinyu (pecahan) dan variabel diskrit (bulat), dibawah ini. Menentukan nilai dari dalam kasus ini menggunakan masalah Integer 𝑋 , 𝑋 , 𝑋 , ⋯ , 𝑋 sedemikian rupa sehingga : 1 2 3 𝑛 Linear Programming (ILP) yang masih murni dimana semua variabelnya adalah integer. Model
Ade Vicidian S. P. - 5107100615
1
Makalah Seminar Tugas Akhir Periode Januari 2010
𝑍 = 𝐶1 𝑋1 + 𝐶2 𝑋2 + ⋯ + 𝐶𝑗 𝑋𝑗 + ⋯ + 𝐶𝑛 𝑋𝑛 = 𝑛 𝑗 =1 𝐶𝑗 𝑋𝑗 (optimal [maksimum/minimum]) Yang kemudian disebut sebagai Fungsi Tujuan (Objective Function) dengan pembatasan (Fungsi Kendala/Syarat Ikatan) : 𝑎11 𝑋1 + 𝑎12 𝑋2 + ⋯ + 𝑎1𝑛 𝑋𝑛 ≤ atau ≥ 𝑏1 𝑎21 𝑋1 + 𝑎22 𝑋2 + ⋯ + 𝑎2𝑛 𝑋𝑛 ≤ atau ≥ 𝑏2 ⋯ ⋯ ⋯ 𝑎𝑚1 𝑋1 + 𝑎𝑚2 𝑋2 + ⋯ + 𝑎𝑚𝑛 𝑋𝑛 ≤ atau ≥ 𝑏𝑚 𝑛 atau 𝑗 =1 𝑎𝑖𝑗 𝑋𝑗 ≤ atau ≥ 𝑏𝑖 untuk 𝑖 = 1,2,3, … , 𝑚. dan 𝑋1 ≥ 0, 𝑋2 ≥ 0, ⋯ , 𝑋𝑛 ≥ 0 atau 𝑋𝑗 ≥ 0, dimana j = 1, 2, 3,...., n (syarat non-negatif). Keterangan : Z adalah nilai fungsi tujuan. Ada n macam barang yang akan diproduksi masing-masing sebanyak 𝑋1 , 𝑋2 , 𝑋3 , ⋯ , 𝑋𝑛 unit. Cj merupakan parameter yang dijadikan kriteria optimasi atau koefisien variabel pengambilan keputusan dalam fungsi tujuan (misalnya harga per satuan barang ke-j). Xj merupakan variabel pengambilan keputusan atau kegiatan yang ingin dicari (misalnya banyaknya produksi barang yang ke-j, dimana j = 1, 2, ...,n ). 𝑏𝑖 merupakan sumber daya yang terbatas, yang membatasi kegiatan atau usaha yang bersangkutan disebut juga konstanta atau “nilai sebelah kanan (nsk)” dari kendala kei (misalnya banyaknya bahan mentah ke-i, I = 1, 2, .., m). Ada m macam bahan mentah, yang masing-masing tersedia 𝑏1 , 𝑏2 ,⋯, 𝑏𝑚 . 𝑎𝑖𝑗 merupakan koefisien teknologi variabel pengambilan keputusan (kegiatan yang bersangkutan) dalam kendala ke-I (misalnya banyaknya bahan mentah ke-i yang digunakan untuk memproduksi 1 satuan barang ke-j). Suatu permasalahan disebut permasalahan program linier apabila memenuhi hal-hal sebagai berikut : 1. Tujuan (objective) Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang disebut fungsi tujuan (objective function). Fungsi tujuan tersebut dapat berupa dampak positip, manfaatmanfaat, atau dampak negatip, kerugiankerugian, resiko-resiko, biaya-biaya, jarak, waktu yang ingin diminimumkan. 2. Alternatif perbandingan.
Harus ada sesuatu atau alternatif yang ingin diperbandingkan, misalnya antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat dan biaya terendah, atau alternatif padat modal dengan padat karya, proyeksi permintaan tinggi dengan rendah, dan seterusnya. 3. Sumber Daya Sumber daya yang dianalisis harus berada dalam keadaan terbatas. Misalnya keterbatasan tenaga, bahan mentah terbatas, modal terbatas, ruangan untuk menyimpan barang terbatas, dan lain-lain. Pembatasan harus dalam ketidaksamaan linier (linier inequality). Keterbatasan dalam sumber daya tersebut dinamakan sebagai fungsi kendala atau syarat ikatan. 4. Perumusan Kuantitatif. Fungsi tujuan dan kendala tersebut harus dapat dirumuskan secara kuantitatif dalam model matematika. 5. Keterikatan Perubah. Perubah-perubah yang membentuk fungsi tujuan dan fungsi kendala tersebut harus memiliki hubungan keterikatan atau hubungan fungsional. 3. INTEGER LINIER PROGRAMMING Integer linier programming (ILP) merupakan bagian dari linier programming dimana dibutuhkan keputusan yang harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila menggunakan model simpleks). Model matematis dari ILP sebenarnya sama dengan model linear programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat. Terdapat 3 macam permasalahan dalam ILP, yaitu: 1. ILP murni, yaitu kasus dimana semua variabel keputusan harus berupa bilangan bulat. 2. ILP campuran (mixed integer linear programs), yaitu kasus dimana beberapa, tapi tidak semua, variabel keputusan harus berupa bilangan bulat. 3. ILP biner, kasus dengan permasalahan khusus dimana semua variabel keputusan harus bernilai 0 dan 1. Salah satu cara yang digunakan untuk menyelesaikan permasalahan ILP yaitu dengan model branch and bound. 4. MODEL BRANCH AND BOUND Model branch and bound telah menjadi kode komputer standar untuk integer programming, dan penerapan-penerapan dalam praktek tampaknya menyarankan bahwa model ini lebih efektif dibandingkan dengan model pembulatan. Teknik ini dapat diterapkan baik untuk masalah pure
Ade Vicidian S. P. - 5107100615
2
Makalah Seminar Tugas Akhir Periode Januari 2010
integer programming maupun mixed integer programming. Langkah-langkah model branch and bound untuk masalah maksimasi dapat dilakukan seperti berikut : 1. Selesaikan LP dengan model simpleks biasa. 2. Teliti solusi optimalnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimal bulat telah tercapai. 3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu. 4. Untuk setiap sub-masalah, nilai solusi optimal kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.
ILP yang berisi variabel binary dan non binary, dengan cara sebuah general integer cut ditambahkan pada model asli untuk membuat model sebelumnya menjadi tidak layak (infeasible) sehingga menghasilkan model baru dengan nilai objektif yang sama. 5.1. Model 1 Mengingat sebuah masalah ILP dengan sebuah solusi yang optimal 𝑥10 , 𝑥20 , … , 𝑥𝑛0 dan mengharapkan nilai objektif Q, dikembangkanlah model berikut untuk menghasilkan solusi lain yang optimal: Model 1: Minimalkan / Maksimalkan : 𝑓 𝑋 = 𝑄 Fungsi Kendala : 𝑛 0 𝑧=1 |𝑥𝑧 − 𝑥𝑧 | ≥ 1 Dimana :
1 .
𝑓 𝑋 : fungsi objektif 𝑄 : nilai dari fungsi objektif z : jumlah variabel, z = 1, 2, 3, ..., n. 𝑥𝑧 : variabel yang diinginkan/dicari 𝑥𝑧0 : variabel yang telah didapatkan sebelumnya. Berdasarkan Model (1) diatas, nilai absolut harus dilinierkan sehingga Model 1 dapat ditransfer kedalam masalah (Mixed Integer Linear Programs) MILP. Perhatikan proposisi berikut untuk melinierkan Model (1):
5. MODEL GENERAL INTEGER CUT Model general integer cut digunakan untuk menemukan semua solusi alternatif dari masalah Proposisi 1 : berikan 𝛼𝑧 ∈ 0,1 , 𝑊𝑧 ≥ 0, 0 ≤ 𝜃 ≤ 1, dan 𝑀(sebuah konstanta besar) 𝑛
|𝑥𝑧 − 𝑥𝑧0 | ≥ 1 𝑧=1
𝑖 0 ≤ 𝑊𝑧 − 𝑥𝑧 + 𝑥𝑧0 ≤ 𝑀 1 − 𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, ⋯ , 𝑛, 𝑖𝑖 0 ≤ 𝑊𝑧 − 𝑥𝑧0 + 𝑥𝑧 ≤ 𝑀𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, … , 𝑛, 𝑛
↔
𝑖𝑖𝑖
𝑊𝑧 + 𝜃 ≥ 1, 𝑧=𝑚 +1
𝑖𝑣
𝑥𝑖 − 𝑖∈𝐵
𝑥𝑖 ≤ 𝐵 − 𝜃, 𝐵 = 𝑖 𝑥𝑖 = 1, 1 ≤ 𝑖 ≤ 𝑚 , 𝑁 = 𝑖 𝑥𝑖 = 0, 1 ≤ 𝑖 ≤ 𝑚 . 𝑖∈𝑁
Pembuktian dari proposisi 1 diatas adalah : a. Jika 𝑥𝑧 − 𝑥𝑧0 > 0 untuk sebuah z dan m + 1 ≤ 𝑧 ≤ 𝑛 maka 𝛼𝑧 = 1 berdasarkan pada (i) dan (ii) yang menghasilkan : 𝑥𝑧 − 𝑥𝑧0 = 𝑊𝑧 b. Jika 𝑥𝑧 − 𝑥𝑧0 < 0 untuk sebuah z dan m + 1 ≤ 𝑧 ≤ 𝑛 maka 𝛼𝑧 = 0 berdasarkan pada (i) dan (ii) yang menghasilkan : 𝑥𝑧 − 𝑥𝑧0 = 𝑊𝑧 c. Berdasarkan pada (a) dan (b) maka : 𝑛 𝑛 0 𝑧=𝑚 +1 𝑥𝑧 − 𝑥𝑧 = 𝑧=𝑚 +1 𝑊𝑧 . 𝑚 0 d.Jika 𝑧=1 𝑥𝑧 − 𝑥𝑧 = 0 maka 𝜃 = 0 berdasarkan pada iv yang
menghasilkan 𝑛𝑧=𝑚 +1 𝑊𝑧 = 𝑛𝑧=𝑚 +1 𝑥𝑧 − 𝑥𝑧0 ≥ 1 oleh pembuktian (a) dan (b) tanpa melanggar (iii). 𝑚 0 e. Jika maka 𝑧=𝑚 +1 𝑥𝑧 − 𝑥𝑧 = 0 𝑛 𝑧=𝑚 +1 𝑊𝑧 = 0 oleh (a) dan (b), dan 𝜃 = 1 berdasarkan pada (iii) yang menghasilkan 𝑚 0 𝑧=1 𝑥𝑧 − 𝑥𝑧 ≥ 1 tanpa melanggar (iv). Dari pemmbuktian diatas maka 𝑛𝑧=1 |𝑥𝑧 − 𝑥𝑧0 | ≥ 1 dapat diganti dengan formula (i), (ii), (iii) dan (iv). Dengan catatan proposisi (1) diatas digunakan menemukan sebuah solusi alternatif dari sebuah masalah ILP yang mengandung variabel biner (0
Ade Vicidian S. P. - 5107100615
3
Makalah Seminar Tugas Akhir Periode Januari 2010
dan 1) untuk fungsi objektifnya (𝑥𝑖 ∊ Z untuk semua i). 5.2. Model 2 Dengan Proposisi (1) maka Model (1) dapat diubah menjadi model lain seperti berikut : Model 2-1: Minimalkan / Maksimalkan : 𝑓 𝑋 = 𝑄 Fungsi Kendala : 0 ≤ 𝑊𝑧 − 𝑥𝑧 + 𝑥𝑧0 ≤ 𝑀 1 − 𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, ⋯ , 𝑛, (2) 0 ≤ 𝑊𝑧 − 𝑥𝑧0 + 𝑥𝑧 ≤ 𝑀𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, … , 𝑛, (3) 𝑛 (4) 𝑧=𝑚 +1 𝑊𝑧 + 𝜃 ≥ 1, (5). 𝑖∈𝐵 𝑥𝑖 − 𝑖∈𝑁 𝑥𝑖 ≤ 𝐵 − 𝜃, 𝐵 = 𝑖 𝑥𝑖 = 1, 1 ≤ 𝑖 ≤ 𝑚 , 𝑁 = 𝑖 𝑥𝑖 = 0, 1 ≤ 𝑖 ≤ 𝑚 Dimana: programming yang konvensional (teknik IP konvensional). 𝛼𝑧 : merupakan variabel biner (0 dan 1), untuk melinierkan kendala 𝑊𝑧 : merupakan variabel kontinyu dengan Sehingga pertidaksamaan dengan total nilai dari absolut syarat 𝑊𝑧 ≥ 0, 𝑛 0 𝑧=1 |𝑥𝑧 − 𝑥𝑧 | ≥ 1dimana 𝑥𝑖 ∊ {0,1} untuk 1 ≤ 𝜃 : merupakan variabel kontinyu dengan i ≤ m dan 𝑥𝑖 ∊ Z untuk m + 1 ≤ i ≤ n , formula syarat 0 ≤ 𝜃 ≤ 1, M : merupakan sebuah konstanta yang pada Proposisi (1) membutuhkan n – m tambahan variabel 0–1, n – m + 1 tambahan variabel besar, B : himpunan indeks variabel yang kontinyu dan 4 ( n – m ) + 2 tambahan fungsi kendala. bernilai 1, N : himpunan indeks variabel yang Sedangkan untuk menemukan sebuah solusi alternatif dari sebuah masalah ILP yang hanya bernilai 0. Setelah memformulasi ulang absolut dalam fungsi mengandung variabel non-biner pada fungsi kendala (1) dengan metode yang diusulkan, objektifnya (𝑥𝑖 ∊ Z untuk semua i), proposisi (1) masalah awal menjadi masalah MILP lain yang dapat disederhanakan menjadi proposisi (2) dapat diselesaikan menggunakan teknik integer sebagai berikut: Proposisi 2 : berikan 𝛼𝑧 ∈ 0,1 , 𝑊𝑧 ≥ 0, dan 𝑀(sebuah konstanta besar) 𝑖 0 ≤ 𝑊𝑧 − 𝑥𝑧 + 𝑥𝑧0 ≤ 𝑀 1 − 𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, ⋯ , 𝑛, 𝑛 𝑖𝑖 0 ≤ 𝑊𝑧 − 𝑥𝑧0 + 𝑥𝑧 ≤ 𝑀𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, … , 𝑛, 0 𝑛 |𝑥𝑧 − 𝑥𝑧 | ≥ 1 ↔ 𝑧=1 𝑖𝑖𝑖 𝑊𝑧 ≥ 1. 𝑧=1
Berdasarkan proposisi (2) maka model (2) pun non-biner pada fungsi objektifnya menjadi seperti dapat disederhanakan untuk menyelesaikan berikut : masalah ILP yang hanya mengandung variabel Model 2-2: Minimalkan / Maksimalkan : 𝑓 𝑋 = 𝑄 Fungsi Kendala : 0 ≤ 𝑊𝑧 − 𝑥𝑧 + 𝑥𝑧0 ≤ 𝑀 1 − 𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, ⋯ , 𝑛, (6) 0 ≤ 𝑊𝑧 − 𝑥𝑧0 + 𝑥𝑧 ≤ 𝑀𝛼𝑧 , 𝑧 = 𝑚 + 1, 𝑚 + 2, … , 𝑛, (7) 𝑛 𝑊 ≥ 1, (8). 𝑧=𝑚 +1 𝑧 6. ALGORITMA OPTIMASI GENERAL INTEGER CUT 6.1. Langkah 1 Sama seperti menentukan solusi permasalahan ILP pada umumnya, langkah 1 yaitu menentukan sebuah solusi optimal dari permasalahan ILP, misalkan j = 0, selesaikan ILP untuk mendapatkan solusi yang optimal 𝑗 𝑗 𝑗 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 dan nilai obyektif Q.
6.2. Langkah 2 Pada langkah 2 ini adalah langkah untuk menemukan semua solusi optimal. Misalkan j = j + 1, pada fungsi kendala yang sudah ada tambahkan 𝑗 −1 fungsi kendala baru 𝑛𝑧=1 |𝑥𝑧 − 𝑥𝑧 | ≥ 1 untuk menemukan solusi alternatif 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 𝑗 𝑗 𝑗 𝑥1 , 𝑥2 , … , 𝑥𝑛 . Minimalkan / Maksimalkan : 𝑓 𝑋 = 𝑄 Fungsi
Kendala
:
𝑛 𝑧=1 |𝑥𝑧
𝑗 −1
− 𝑥𝑧
Ade Vicidian S. P. - 5107100615
4
| ≥ 1,
Makalah Seminar Tugas Akhir Periode Januari 2010
untuk seluruh 𝑗 𝑗 ≥ 1
(9).
Fungsi kendala (9) harus diubah menjadi model 2 sehingga dapat diselesaikan menggunakan teknik integer programming yang konvensional. Ulangi terus langkah 2 selama kondisi 𝑓 𝑋 = 𝑄 (nilai objektif yang baru dihasilkan masih sama dengan nilai objektif awal), dan jika kondisi 𝑓 𝑋 ≠ 𝑄 (nilai objektif baru tidak sama dengan nilai objektif awal) maka lakukan j = j – 1 yaitu solusi optimal yang digunakan sampai pada solusi optimal sebelumnya dan langsung menuju langkah 3. 6.3. Langkah 3 Yang harus dilakukan pada langkah 3 ini adalah 𝑝 𝑝 𝑝 menulis seluruh solusi optimal : 𝑥1 , 𝑥2 , … , 𝑥𝑛 , dimana p=0,1,2,...,j. 6.4. Alur Sistem Start
Mencari solusi Optimal & nilai objektif
Permasalah an ILP
Solusi optimal & nilai objektif ditemukan ?
tidak
Tambahkan general integer cut
ya
Solusi optimal = integer
ya tidak
ya
Nilai objektif = nilai objektif awal
tidak
End
Gambar 1 Alur proses algoritma general integer cut 7.
IMPLEMENTASI, UJI COBA DAN ANALISIS Uji coba dilakukan pada sebuah PC dengan prosesor Intel(R) Core(TM) 2 Duo CPU T5550 @1.83GHz (2 CPUs) dengan memori sebesar 2024 MB RAM. Sistem operasi yang digunakan adalah Windows Vista Home Premium dan bahasa komputasi yang digunakan untuk implementasi metode adalah Lingo v8.0. Uji coba solusi alternatif dengan general integer cut ini akan dilakukan dengan 2 skenario, yaitu ujicoba pada dua contoh permasalahan dengan menambahkan dua model general integer cut dan juga dengan mengkombinasikan model (2) dengan besarnya M yang berbeda-beda yang merupakan konstanta yang besar. Mengkombinasikan model (2) dengan M yang berbeda-beda dimaksudkan untuk mengetahui fungsi dari M tersebut dan apa saja yang diakibatkan olehnya. Data yang akan dipakai bersumber dari paper “Finding multiple solutions to general integer linear programs”.
7.1. Data Ujicoba Data ujicoba terdiri atas data ujicoba 1 dan data ujicoba 2. 7.1.1 Data Ujicoba 1 Data ujicoba permasalahan 1 berasal dari Zionts (1974) tentang permasalahan biaya tetap dimana data ini mengandung kombinasi antara variabel integer dan biner. Untuk mempermudah perhitungan, permasalahan tersebut diubah dahulu menjadi model matematis seperti dibawah ini : Maksimumkan : 𝑧 = 𝑥1 + 𝑥2 + 𝑥3 Fungsi kendala : 20𝑦1 + 30𝑦2 + 𝑥1 + 2𝑥2 + 2𝑥3 ≤ 180, 30𝑦1 + 20𝑦2 + 2𝑥1 + 𝑥2 + 2𝑥3 ≤ 150, −60𝑦1 + 𝑥1 ≤ 0, −75𝑦2 + 𝑥2 ≤ 0, 𝑥1 , 𝑥2 , 𝑥3 ≥ 0, 𝑥1 , 𝑥2 , 𝑥3 ∈ 𝑍, 𝑦1 , 𝑦2 ∈ {0,1}. 7.1.2 Data Ujicoba 2 Data ujicoba permasalahan 2 berasal dari teknik aplikasi pencampuran bahan dimana data ini hanya mengandung variabel non-biner. Sebuah perusahaan kimia menghasilkan dua jenis zat (A dan B) yang terdiri dari tiga jenis bahan baku (I, II dan III). Kedua zat mempunyai keuntungan dan persyaratan yang berbeda pada komposisi dari tiga bahan baku. Perusahaan harus juga mempertimbangkan jumlah yang tersedia dan biaya perawatan dari setiap bahan (I, II dan III). Untuk mempermudah perhitungan, permasalahan tersebut diubah dahulu menjadi model matematis seperti dibawah ini : Maksimumkan : 𝑧 = 10 𝑥1 + 𝑥2 + 𝑥3 + 8 𝑦1 + 𝑦2 + 𝑦3 − 4 𝑥1 + 𝑦1 − 5 𝑥2 + 𝑦2 − 6 𝑥3 + 𝑦3 Fungsi kendala : 𝑥1 + 𝑦1 ≤ 400, 𝑥2 + 𝑦2 ≤ 500, 𝑥3 + 𝑦3 ≤ 300, 0,2 𝑥1 + 𝑥2 + 𝑥3 ≥ 𝑥1 , 0,1 𝑥1 + 𝑥2 + 𝑥3 ≥ 𝑥2 , 0,2 𝑥1 + 𝑥2 + 𝑥3 ≤ 𝑥3 , 0,4 𝑦1 + 𝑦2 + 𝑦3 ≥ 𝑦1 , 0,5 𝑦1 + 𝑦2 + 𝑦3 ≥ 𝑦3 , 𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 ≥ 0, 𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 ∈ 𝑍 7.2. Implementasi Pada bagian ini akan diberikan gambaran mengenai implementasi dari Model (1) dan Model (2) secara umum yang akan digunakan untuk mendapatkan solusi optimal dan nilai objektif dengan contoh menggunakan Data Ujicoba 1.
Ade Vicidian S. P. - 5107100615
5
Makalah Seminar Tugas Akhir Periode Januari 2010
Berikut adalah implementasi general integer cut dengan teknik absolut: 1
@ABS (x1 - 23) + @ABS (x2 - 53) + @ABS (x3 - 0) + @ABS (y1 - 1) + @ABS (y2 - 1) >= 1;
Gambar 2 Kode program implementasi general integer cut teknik absolut, contoh menggunakan Data Ujicoba 1 Untuk penjelasan tentang kode program pada gambar 2 adalah sebagai berikut: Baris 1 adalah implementasi Model 1 formula 1 @ABS : merupakan fungsi lingo untuk mengabsolutkan suatu bilangan. Nilai 23, 53, 0, 1 dan 1 adalah solusi optimal yang telah dihasilkan sebelumnya. Berikut adalah implementasi general integer cut dengan teknik IP konvensional: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
M = 100000; 0 <= W1 - x1 + 23; W1 - x1 + 23 <= M - M*A1; 0 <= W2 - x2 + 53; W2 - x2 + 53 <= M - M*A2; 0 <=W3-x3; W3 - x3 <= M - M*A3; 0 <= W1 – 23 + x1; W1 – 23 + x1 <= M*A1; 0 <= W2 – 53 + x2; W2 - 53 + x2 <= M*A2; 0 <= W3 + x3; W3 + x3 <= M*A3; W1 + W2 + W3 + T >= 1; y1 + y2 <= 2 - T ; @GIN(A1); @GIN(A2); @GIN(A3);
Gambar 3 Kode program implementasi general integer cut teknik IP konvensional, contoh menggunakan Data Ujicoba 1 Untuk penjelasan tentang kode program pada gambar 3 adalah sebagai berikut: M : merupakan sebuah konstanta besar. Baris 2-7 adalah implementasi Model 2-1 formula 2 Baris 8-13 adalah implementasi Model 2-1 formula 3 Baris 14 adalah implementasi Model 2-1 formula 4 Baris 15 adalah implementasi Model 2-1 formula 5 Baris 16-18 adalah syarat variabel biner yang akan di-integerkan Nilai 23, 53, 0, 1 dan 1 adalah solusi optimal yang telah dihasilkan sebelumnya. W1, W2, W3 dan T : merupakan variabel kontinyu, pada model dilambangkan dengan 𝑊𝑧 dan θ, A1, A2, A3 : merupakan variabel biner (0 dan 1) pada model dilambangkan dengan 𝛼𝑧 . 7.3. Skenario 1 Dan Analisis Skenario 1 Untuk skenario 1 dilakukan tiga kali ujicoba pada data permasalahan 1, yaitu ujicoba pertama menambahkan general integer cut dengan fungsi kendala teknik absolut, ujicoba kedua menambahkan general integer cut dengan fungsi kendala teknik IP konvensional dengan nilai M=100, dan ujicoba ketiga menambahkan general integer cut dengan fungsi kendala teknik IP konvensional dengan nilai M=100000. Berikut daftar solusi alternatif (termasuk juga solusi optimal awal) dari ketiga ujicoba:
Fungsi
Variabel
Variabel
Variabel
Solusi
X1
X2
X3
Y1
Y2
1
23
53
0
1
1
4
5
5
-
2
22
54
0
1
1
20
20
5
-
3
24
52
0
1
1
40
40
10
-
4
22
53
1
1
1
60
60
15
-
5
23
52
1
1
1
80
80
20
-
6
22
52
2
1
1
100
100
25
-
Kendala
Integer
Kontinyu
Tabel 1 Daftar Solusi Alternatif Ujicoba 1 Skenario 1 Fungsi Variabel
Variabel
Variabel
Integer
Kontinyu
Solusi
X1
X2
X3
Y1
Y2
1
23
53
0
1
1
4
5
5
-
2
24
52
0
1
1
18
12
8
4
3
22
54
0
1
1
32
19
11
8
4
22
52
2
1
1
46
26
14
12
5
22
53
1
1
1
60
33
17
16
6
23
52
1
1
1
74
40
20
20
Kendala
Tabel 2 Daftar Solusi Alternatif Ujicoba 2 Skenario 1
Ade Vicidian S. P. - 5107100615
6
Makalah Seminar Tugas Akhir Periode Januari 2010 Fungsi
Variabel
Variabel
Variabel
Integer
Kontinyu
Solusi
X1
X2
X3
Y1
Y2
1
23
53
0
1
1
4
5
5
-
2
22
53
1
1
1
18
12
8
4
3
22
54
0
1
1
32
19
11
8
4
24
52
0
1
1
46
26
14
12
5
23
52
1
1
1
60
33
17
16
6
22
52
2
1
1
74
40
20
20
Kendala
Tabel 3 Daftar Solusi Alternatif Ujicoba 3 Skenario 1 Dari hasil optimasi skenario 1 dapat ditarik beberapa kesimpulan bahwa : 1. Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang mengandung variabel integer dan variabel biner. 2. Hasil ujicoba 2 dan ujicoba 3 menunjukkan bahwa dengan dengan dilakukannya penambahan general integer cut dapat menghasilkan jumlah solusi alternatif yang sama namun berbeda urutan solusi Solusi 1 2
X1 85 85
Solusi
X1
1 2
85 85
Solusi
X1
1 2
85 85
optimalnya bergantung pada besarnya M yang diinputkan. 7.4. Skenario 2 Dan Analisis Skenario 2 Untuk skenario 2 dilakukan tiga kali ujicoba pada data permasalahan 2 sama seperti skenario 1, yaitu ujicoba pertama menambahkan general integer cut dengan fungsi kendala teknik absolut, ujicoba kedua menambahkan general integer cut dengan fungsi kendala teknik IP konvensional dengan nilai M=100, dan ujicoba ketiga menambahkan general integer cut dengan fungsi kendala teknik IP konvensional dengan nilai M=100000. Berikut daftar solusi alternatif (termasuk juga solusi optimal awal) dari ketiga ujicoba:
Fungsi Variabel Variabel Kendala Integer 41 300 306 459 0 8 6 6 42 299 306 458 1 24 24 6 Tabel 4 Daftar Solusi Alternatif Ujicoba 1 Skenario 2
Variabel Kontinyu -
Fungsi Variabel Variabel Kendala Integer 41 300 306 459 0 8 6 6 42 299 306 458 1 33 18 6 Tabel 5 Daftar Solusi Alternatif Ujicoba 2 Skenario 2
Variabel Kontinyu 12
Fungsi Variabel Variabel Kendala Integer 41 300 306 459 0 8 6 6 42 299 306 458 1 33 18 6 Tabel 6 Daftar Solusi Alternatif Ujicoba 3 Skenario 2
Variabel Kontinyu 12
X2
X2
X2
X3
X3
X3
Y1
Y1
Y1
Y2
Y2
Y2
Y3
Y3
Y3
Dari hasil optimasi skenario 1 dapat ditarik beberapa kesimpulan bahwa : 1. Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang hanya mengandung variabel non-biner. 2. Perbedaan besarnya M yang diinputkan tidak terlihat pada ujicoba 2 dan 3 dikarenakan data permasalahan tersebut jika diselesaikan menggunakan general integer
cut hanya menghasilkan dua buah solusi optimal. 8. KESIMPULAN Kesimpulan yang bisa diambil dari serangkaian uji coba dan analisis yang dilakukan terhadap model general integer cut adalah sebagai berikut: 1. Model general integer cut dapat digunakan untuk mencari solusi alternatif lain diluar solusi optimal awal, dimana general integer cut tersebut didapatkan dengan cara memformulasikan ulang solusi optimal
Ade Vicidian S. P. - 5107100615
7
Makalah Seminar Tugas Akhir Periode Januari 2010
2.
3.
4.
5.
yang didapat sebelumnya sehingga menghasilkan solusi alternatif baru dengan menghilangkan kemungkinan kemunculan solusi yang sudah ada sebelumnya. Solusi alternatif dari sebuah permasalahan ILP yang didapatkan dengan menggunakan model general integer cut haruslah solusi optimal yang memiliki nilai objektif yang sama dengan solusi optimal awal yaitu pada saat sebelum ditambahkannya fungsi kendala baru yang berupa general integer cut. Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang hanya mengandung variabel non-biner maupun juga permasalahan ILP yang mengandung variabel biner. Pada model general integer cut, perbedaan besarnya M yang diinputkan akan terlihat jika suatu permasalahan ILP dapat menghasilkan lebih dari 1 solusi alternatif. Karena besarnya M akan mengakibatkan perbedaan urutan solusi alternatif optimal yang ditemukan. Model general integer cut ini dapat membantu pengambil keputusan pada suatu badan atau perusahaan untuk mengkombinasikan variabel-variabel keputusan yang berbeda komposisinya yang dianggap sesuai dengan kondisi teraktual perusahaan namun tetap menghasilkan keuntungan yang sama optimalnya, hal ini dikarenakan kemampuan general integer cut dalam memberikan banyak pilihan solusi alternatif.
9. DAFTAR PUSTAKA Asror, Mustaghfiri. “Linier Programming”.
D. Yusup. “Program Linier”.
Dimyati, Tjutju Tarliah, Dimyati, Ahmad. 2003. “Operation Research Model-Model Pengambilan Keputusan”. Sinar Baru Algensindo. Hartanto, Eko. “Integer Linier Programming”. Masteran Program. Tsai, Jung-Fa, Lin, Ming-Hua, Hu, Yi-Chung. 2006. “Finding multiple solutions to general integer linear programs”. European Journal of Operational Research 184, 802–809. Wahyujati, Ajie. “Operation Research 2 : Integer Programming”.
Ade Vicidian S. P. - 5107100615
8
