PENYELESAIAN ROBUST KNAPSACK PROBLEM (RKP) MENGGUNAKAN PEMROGRAMAN DINAMIK

PENYELESAIAN ROBUST KNAPSACK PROBLEM (RKP) MENGGUNAKAN PEMROGRAMAN DINAMIK Kinanti Wening Ati, Dhian Widya, Rahmi Rusin Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia E-mail : [email protected] ABSTRAK Robust Knapsack Problem (RKP) adalah variasi dari masalah Knapsack, dimana dalam hal ini bobot dari setiap item belum diketahui secara pasti, dan hanya diketahui terletak dalam sebuah interval tentu. Pada RKP akan dicari solusi optimal yang merupakan keuntungan optimal yang akan didapatkan, dan item-item mana saja yang diletakkan ke dalam Knapsack sehingga menghasilkan solusi optimal. Terdapat dua metode yang akan dijelaskan untuk mencari solusi optimal pada RKP. Sedangkan untuk mencari himpunan item-item yang menghasilkan solusi optimal pada RKP akan digunakan metode partisi rekursif, dimana ide awalnya adalah dengan mempartisi himpunan item menjadi dua subhimpunan item. Solving Robust Knapsack Problem (RKP) using Dynamic Programming ABSTRACT Robust Knapsack Problem (RKP) is a variation of the Knapsack Problem, where in this case the weight of each item is not exactly known in advance, but belongs to a given interval. On RKP, it will be sought optimal solution, which is the optimal benefit to be gained, and set of items placed into the Knapsack. There are two methods that will be discussed to find optimal solution in RKP. Whereas, to search the set of items that build optimal solutions in the RKP will be used recursive partitioning method. The main idea of this method is dividing the set of items into two subsets of items. Keywords

: Knapsack Problem, Robust Oprimization, Dynamic Programming

Penyelesaian robust knapsack..., Kinanti Wening Ati, FMIPA UI, 2015

1. PENDAHULUAN Salah satu masalah optimisasi yang sering dijumpai di kehidupan sehari-hari ini adalah Knapsack Problem (KP). KP merupakan masalah optimisasi dalam penempatan item (barang). Secara umum, KP adalah masalah penempatan beberapa item ke dalam satu atau lebih tempat (biasa disebut Knapsack) yang mempunyai kapasitas tertentu, dimana setiap item memiliki bobot dan keuntungan masing-masing, sehingga jumlah bobot dari item-item yang ditempatkan tidak melebihi kapasitas Knapsack, dan jumlah keuntungan yang didapatkan maksimum (Pisinger, 1995). Terdapat beberapa variasi dari KP, namun dalam hal ini yang menjadi fokus penelitian adalah {0,1}-KP. {0,1}-KP adalah masalah KP dimana variabel item akan bernilai 1 jika jenis item tersebut ditempatkan dalam Knapsack dan bernilai 0 jika tidak ditempatkan dalam Knapsack (Pisinger, 1995). Dalam masalah optimisasi, pada umumnya model matematika yang dibuat adalah model dengan asumsi nilai pada input data yang digunakan tetap atau sudah ditentukan dalam suatu nilai tertentu. Sedangkan input data dengan nilai yang tidak pasti tidak diperhitungkan pada model. Oleh karena itu, timbul masalah jika input data yang digunakan memiliki nilai yang tidak diketahui secara pasti namun diketahui berada dalam suatu interval. Hal tersebut akan mengakibatkan beberapa kendala mungkin akan tidak terpenuhi (tidak layak), solusi optimal yang didapat pun mungkin bukan merupakan solusi optimal lagi. Pendekatan untuk mencari solusi optimal dari masalah yang mencakup dan memperhitungkan data-data yang nilainya tidak pasti disebut optimisasi robust (Bertsimas & Sim, 2002). Pada jurnal ini, akan dijelaskan formulasi dan penyelesaian masalah optimisasi robust pada {0,1}-KP. Untuk selanjutnya akan disebut sebagai Robust Knapsack Problem (RKP). Nilai dari input data dalam masalah ini adalah nilai yang tidak pasti namun diketahui berada dalam sebuah interval tertentu, hal ini mungkin terjadi pada kapasitas Knapsack, nilai bobot, atau nilai keuntungan dari setiap item. Namun dalam tugas akhir ini hanya bobot setiap item yang memiliki nilai input yang berada dalam sebuah interval. Sedangkan nilai keuntungan dari setiap item dan kapasitas Knapsack sudah diketahui dalam sebuah nilai tertentu. Selanjutnya akan digunakan metode Pemrograman Dinamik untuk menyelesaikan RKP.


2. TINJAUAN TEORITIS 2.1 {0,1}-Knapsack Problem {0,1}-Knapsack Problem atau disingkat {0,1}-KP, adalah salah satu variasi dari KP dimana dimisalkan !! adalah variabel item !, maka !! akan bernilai 1 jika item ! ditempatkan dalam Knapsack dan bernilai 0 jika tidak ditempatkan dalam Knapsack (Pisinger, 1995). Dalam {0,1}-KP diasumsikan Knapsack hanya ada satu saja. {0,1}-KP dapat diformulasikan sebagai berikut, misal diberikan himpunan item-item ! = {1, … , ! }, dimana masing-masing item ! ∈ ! memiliki keuntungan !! dan bobot positif !! dan c adalah kapasitas Knapsack, maka fungsi objektifnya maks

!! !! !∈!

Dengan kendala, !! !! ≤ ! ,

!! ∈ 0,1 , ! ∈ !

!∈!

K-Item Knapsack Problem (KKP) K-item Knapsack Problem (KKP) juga merupakan variasi dari KP dengan ditambahkan sebuah asumsi baru yaitu maksimum banyaknya item yang ditempatkan dalam Knapsack adalah ! item. KKP dapat diformulasikan sebagai berikut, maks

!! !! (2.3) !∈!

dengan kendala

!! !! ≤ ! (2.4)

!∈!

!! ≤ ! dengan 1 ≤ ! ≤ ! (2.5) !∈!

dan ! adalah banyaknya item yang tersedia. Sedangkan Exact K-item Knapsack Problem (E-KKP) adalah salah satu jenis dari KKP dimana banyaknya item dalam solusi layak harus sama dengan !. Sehingga, E-EKP dapat dirumuskan sebagai KKP dengan mengganti kendala (2.5) dengan


!! = ! dengan 1 ≤ ! ≤ ! (2.6) !∈!

2.2 Graf Berarah Definisi Graf berarah G adalah pasangan himpunan berhingga tak kosong (V,E) dengan V adalah himpunan simpul dan E adalah himpunan busur. Secara umum graf berarah G dengan n simpul terdiri dari himpunan simpul V(G)={!! , !! , … , !! } dan himpunan busur yang dinotasikan dengan !! , !! dengan !, ! = 1,2, … , ! dimana (!! , !! ) ≠ (!! , !! ). Jika busur menunjukkan pasangan terurut (!! , !! ) ∈ !, {!! , !! } ⊆ ! maka !! disebut ekor dan !! disebut kepala dari busur tersebut, atau biasa disebut ‘busur dari !! menuju !! ’. (West, 1996) 2.3 Pelabelan Graf Pemberian label pada simpul pada graf G adalah sebuah pemetaan α: V(G) → N, dimana N disebut himpunan label simpul. Demikian pula, pemberian label pada busur adalah pemetaan β: A(G) → M, dimana M adalah himpunan label busur (Ruohonen,2013). 2.4 Pemrograman Dinamik Pemrograman Dinamik merupakan sebuah metode untuk menyelesaikan masalah optimisasi dengan cara menguraikan masalah menjadi sekumpulan submasalah yang lebih kecil agar lebih mudah untuk diselesaikan (Cooper,1981). Permasalahan Pemrograman Dinamik dapat dibagi menjadi sub-masalah (stage) yang lebih kecil dan berurutan dengan membutuhkan keputusan di setiap stage. Pada setiap stage memiliki sejumlah state yang bersesuaian dengan permulaan dari tahapan tersebut. State merupakan informasi yang dibutuhkan pada setiap stage untuk membuat keputusan optimal. Maka terdapat hubungan rekursif yang mengidentifikasikan solusi optimal untuk tahap ! jika diberikan solusi optimal untuk tahap ke ! − 1. Ketika hubungan rekursif digunakan, prosedur solusi dimulai dari awal dan bergerak tahap demi tahap hingga tahap akhir. Kemudian solusi optimal ditentukan dimulai dari tahap akhir.


3. PEMBAHASAN RKP adalah masalah {0,1}-KP yang memiliki nilai input data yang belum pasti namun diketahui berada dalam sebuah interval tertentu, hal ini mungkin terjadi pada kapasitas Knapsack, dan nilai bobot atau nilai keuntungan dari setiap item. Dalam tugas akhir ini yang akan menjadi fokus penelitian adalah ketika hanya nilai bobot setiap item saja yang diasumsikan memiliki nilai input tidak pasti dan ditetapkan dalam sebuah interval. Sedangkan keuntungan dari setiap item dan kapasitas Knapsack sudah ditentukan pada suatu nilai. Formulasi untuk RKP tak jauh berbeda dengan {0,1}-KP yang telah dijelaskan pada tinjauan teori, misal diberikan himpunan item-item ! = {1, … , !}, dimana masing-masing item ! ∈ ! memiliki keuntungan !! , bobot positif !! dan Knapsack yang mempunyai kapasitas tertentu !. Namun dalam RKP bobot dari setiap item hanya diketahui berada dalam suatu interval berikut [!! − !! , !! + !! ] Bobot item mungkin bertambah atau berkurang dari nilai !! . Dengan !! adalah maksimum besarnya pengurangan bobot pada item !, dan !! adalah maksimum besarnya penambahan bobot pada item !. RKP secara umum adalah mencari himpunan ! ⊆ !, sedemikian sehingga total keuntungan yang didapatkan dari item-item dalam himpunan ! maksimum, dan total bobot dari himpunan ! tidak melebihi kapasitas Knapsack. Ketika dalam himpunan ! terdapat bobot item yang ternyata nilainya berada di bawah nilai !! , hal tersebut tidak memengaruhi kelayakan. Karena masih memenuhi kendala !∈! !!

≤ ! . Sedangkan ketika terdapat item dengan nilai bobot lebih dari !! , hal ini dapat

memengaruhi kelayakan. Hal tersebut dikarenakan mungkin saja kendala

!∈! !!

≤ ! tidak lagi

terpenuhi, yaitu total bobot yang didapat melebihi kapasitas dari Knapsack. Maka selanjutnya yang akan diperhatikan adalah kemungkinan nilai bobot item yang bertambah dari nilai !! . Dalam karya ilmiah ini yang akan dicari adalah solusi eksak dari RKP, namun karena informasi yang dimiliki untuk nilai bobot hanya perkiraan nilai !! dan intervalnya saja, maka untuk kemungkinan nilai bobot item yang bertambah dari !! , diasumsikan penambahannya


adalah sebesar !! , atau penambahan nilai bobot mencapai batas atas interval, dinotasikan batas atas interval bobot adalah !! , dengan !! = !! + !! . Dalam RKP terdapat parameter !, sebuah bilangan bulat yang menyatakan maksimum banyaknya item yang memiliki nilai bobot mencapai batas atas interval !! . Sebelum menyelesaikan RKP, diasumsikan item-item yang tersedia sudah terurut berdasarkan urutan maksimum kenaikan bobot (!! ) secara tidak naik. Untuk himpunan solusi layak ! ⊆ !, dinotasikan !! merupakan indeks dari item ke-! (bilangan bulat yang menyatakan maksimum banyaknya item yang memiliki nilai bobot mencapai batas atas interval !! ) di ! jika ! ≥ !. Maka RKP secara umum mencari himpunan ! ⊆ ! dengan keuntungan yang maksimal, secara matematis dapat diformulasikan sebagai berikut !!

maks !∈!

dengan kendala !! + !∈! | !!!!

!! ≤ ! !∈! | !!!!

3.1 Penyelesaian RKP dengan Pemrograman Dinamik Dalam penyelesaian RKP, hasil yang ingin didapatkan adalah solusi optimal serta himpunan solusi optimal. Solusi optimal menyatakan berapa besar keuntungan maksimal yang akan didapatkan, sedangkan himpunan solusi optimal adalah himpunan yang anggotanya merupakan item-item mana saja yang dimasukkan ke dalam Knapsack sehingga menghasilkan solusi optimal. 3.1.1 Pencarian solusi optimal dalam RKP Untuk mencari solusi optimal dari RKP dengan menggunakan Pemrograman Dinamik, masalah keseluruhan akan dibagi menjadi ! stage (! ≤ !), dimana stage ke-! menyatakan bahwa sebanyak ! item dengan bobot mencapai !! telah dimasukkan ke dalam Knapsack. Terdapat dua alternatif metode untuk mencari solusi optimal untuk RKP yang akan dijelaskan pada Teorema


3.2 dan Teorema 3.3. Pertama yang akan dijelaskan adalah Teorema 3.2, yang berbunyi seperti berikut Teorema 3.2 Untuk menyelesaikan RKP dengan Pemrograman Dinamik, fungsi rekursif berikut dapat digunakan untuk mencari nilai keputusan pada setiap stage, ! !, !, ! = maks ! !, !, ! − 1 , ! ! − !! , ! − 1, ! − 1 + !! untuk ! = 0, … , !, ! = 1, … , !, ! = 1, … , !

(3.1)

! !, !, ! = maks ! !, !, ! − 1 , ! ! − !! , !, ! − 1 + !! untuk ! = 0, … , !, ! = ! + 1, … , !

(3.2)

dan nilai keputusan yang paling maksimal akan menjadi solusi optimal dari RKP, yang dapat dicari dengan persamaan berikut, ! ∗ = maks

maks ! !, !, ! ! = 1, … , ! maks {!(!, !, !)|! = 1, … , !, ! = 1, … , ! − 1

(3.3)

Dari Teorema 3.2 fungsi ! !, !, ! menyatakan keuntungan maksimum untuk solusi layak dengan total bobot pada Knapsack sebesar !, dan untuk himpunan 1, … , ! ⊆ ! terdapat ! item yang bobotnya yang mencapai !! yang telah dimasukkan ke dalam Knapsack, dimana ! = 0, … , !, ! = 1, … , !, ! = 1, … , !. Sedangkan fungsi ! !, !, ! menyatakan keuntungan maksimum untuk solusi layak dengan total bobot pada Knapsack sebesar !, dan untuk himpunan 1, … , ! ⊆ ! dan terdapat tepat !item yang bobotnya mencapai !! yang telah dimasukkan ke dalam Knapsack, dimana ! = 0, … , !, ! = ! + 1, … , !. Notasi !! menyatakan keuntungan dari item ke-j. Notasi ! ∗ menyatakan solusi optimal untuk RKP. Nilai-nilai inisialisasi pada Teorema 3.2 adalah ! !, !, ! yang bernilai −∞ kecuali untuk ! 0,0,0 bernilai 0. Asumsi-asumsi dari Teorema 3.2 adalah nilai ! > !! yang juga otomatis ! > !! , hubungan fungsi ! dengan ! adalah ! !, Γ, ! = !(!, Γ, !), dan item-item telah terurut sesuai dengan urutan kenaikan bobot !! dari setiap item secara tidak naik.


Dari Teorema 3.2, penyelesaian RKP salah satunya dapat digambarkan dalam suatu graf berlabel berarah yang tidak membentuk lingkaran (cycle). Graf tersebut menjelaskan bahwa menyelesaikan persamaan (3.1), (3.2) dan (3.3) ekivalen dengan mencari lintasan terpanjang dari graf yang dapat dinyatakan sebagai keuntungan maksimum yang ingin didapatkan. Simpul pada graf dinotasikan dengan (!, !, !) dengan ! = 0, … , !, ! = 0, … , !, dan ! = 0, … , !. Simpul 0,0,0 merupakan simpul awal dari graf, dan terdapat simpul ! yang merupakan simpul akhir atau simpul tujuan dari graf. Adapun busur-busur pada graf yang akan menggambarkan Teorema 3.2, dibagi menjadi 3 jenis, yaitu 1. Busur kosong (Empty arc) Busur yang menghubungkan simpul pada stage yang sama, !, !, ! − 1 → !, !, ! busur ini menyatakan tidak ada penambahan item ke ! ke dalam Knapsack, sehingga tidak ada keuntungan yang didapat. Busur ini memiliki label yang bernilai nol. 2. Busur tebal (Heavy arc) Busur yang menghubungkan dari simpul yang satu menuju simpul yang lain dengan stage lebih tinggi, ! − !! , ! − 1, ! − 1 → !, !, ! busur ini menyatakan ada item ! yang dimasukkan ke dalam Knapsack dengan bobot mencapai batas atas interval !! . Busur ini memiliki label sebesar !! . 3. Busur tipis (Light arc) Busur yang menghubungkan simpul pada stage ke- !, atau pada saat ! = !, ! − !! , !, ! − 1 → !, !, ! busur ini menyatakan ada item ke-! yang dimasukkan ke dalam Knapsack dengan bobot !! . Busur ini memiliki label !! . 4. Busur ujung


Busur yang menghubungkan antara simpul ujung pada setiap stage (ketika ! = !) dengan simpul akhir !. Dimana simpul ! berada di luar dari koordinat simpul-simpul (!, !, !). Sehingga untuk setiap simpul (!, !, !) pada setiap stage, langsung dihubungkan dengan suatu busur menuju simpul akhir !. !, !, ! → ! Busur tersebut memiliki label nol. Dari himpunan simpul-simpul yang mungkin pada graf, simpul-simpul yang dihubungkan oleh macam-macam jenis busur di atas adalah simpul-simpul yang memenuhi kendala (layak), dan untuk simpul-simpul yang tidak dihubungkan oleh busur maka simpul-simpul tersebut tidak memenuhi kendala. Dalam RKP, label dari simpul (!, !, !) adalah jumlah dari label-label pada busur dari simpul awal (0,0,0) sampai simpul (!, !, !). Label simpul (!, !, !) diinterpretasikan sebagai total keuntungan maksimum yang didapat saat item ke-! dimasukkan ke dalam Knapsack, sehingga Knapsack memiliki total bobot sebesar ! dengan sebanyak ! item telah dimasukkan ke dalam Knapsack dengan bobot mencapai !! . Label untuk setiap simpul pada graf adalah nilai fungsi ! yang dapat dicari dengan menggunakan persamaan (3.1) untuk simpul di stage 0 sampai stage !, dan nilai fungsi ! yang dapat dicari menggunakan persamaan (3.2) untuk simpul di stage ! saja. Setelah diberikan aturan untuk busur pada graf, gabungan busur yang menghubungkan simpul-simpul yang dimulai dari simpul awal (0,0,0) menuju simpul akhir ! disebut sebuah lintasan. Label dari suatu lintasan diinterpretasikan sebagai total keuntungan yang didapat sesuai dengan item-item yang telah dimasukkan ke dalam Knapsack. maka akan dicari adalah lintasan terpanjang dari graf. Dengan kata lain akan dicari lintasan pada graf yang mempunyai nilai label lintasan paling maksimum. Contoh 1 Terdapat 4 item yang akan ditempatkan ke dalam Knapsack yang memiliki kapasitas sebanyak 8 satuan berat, dan nilai ! yang ditentukan adalah 2 item. Diketahui item-item telah


diurutkan sesuai urutan besar nilai !! secara tidak naik. Berikut daftar nilai bobot !! , !! , dan !! dari setiap item Tabel 3.1 Input Data untuk Contoh 1 Item 1 2 3 4

!! 1 1 3 1

!! 5 3 4 2

!! 4 2 1 1

!! 1 2 3 4

Maka dari informasi yang ada didapatkan ! = 4, ! = 8, dan ! = 2. Jika digambar dalam bentuk graf akan seperti berikut.

Gambar 3.1 Himpunan Simpul untuk Contoh 1 Setelah dibuat himpunan simpul yang mungkin pada graf, akan dibuat busur yang akan menghubungkan simpul-simpul yang memenuhi kelayakan. Pertama, busur dibuat dari simpul awal graf yaitu simpul (!, !, !) yang labelnya nol, Kemudian, dibuat busur yang akan menghubungkan simpul awal dengan simpul-simpul yang lain pada graf sesuai dengan macammacam busur yang telah dijelaskan sebelumnya. Untuk Contoh 1 secara lengkap dapat digambarkan dengan graf pada Gambar 3.2 berikut,


Gambar 3.2 Graf Keseluruhan yang Terbentuk untuk Contoh 1 Tabel 3.2 Daftar Nilai Keputusan pada Setiap Stage untuk Contoh 1 Stage 0

Stage 1

Himpunan nilai keputusan: • ! 0,0,0 = 0 • ! 0,0,1 = 0 • ! 0,0,2 = 0 • ! 0,0,3 = 0 • ! 0,0,4 = 0

Himpunan nilai keputusan: ! 5,1,1 = 1 ! 5,1,2 = 1 ! 5,1,3 = 1 ! 5,1,4 = 1 ! 3,1,2 = 2 ! 3,1,3 = 2 ! 3,1,4 = 2 ! 4,1,3 = 3 ! 4,1,4 = 3 ! 2,1,4 = 4

• • • • • • • • • •

Stage 2

• • • • • • • • • • • • • •

Himpunan nilai keputusan: ! 8,2,2 = 3 ! 8,2,3 = 3 ! 8,2,4 = 3 ! 7,2,3 = 5 ! 7,2,4 = 7 ! 5,2,4 = 6 ! 6,2,4 = 7 !(8,2,3) = 3 ! 7,2,3 = 5 ! 8,2,4 = 3 ! 7,2,4 = 7 ! 5,2,4 = 6 ! 6,2,4 = 7 ! 8,2.4 = 9

Untuk contoh ini, solusi optimal yang didapatkan adalah sebesar 9, yang merujuk pada simpul (8,2,4), dan nilai ! dari simpul tersebut menunjukkan total bobot yang dimasukkan ke dalam Knapsack, atau kapasitas dari Knapsack yang terpakai untuk mendapatkan solusi optimal, yaitu sebesar 8 satuan bobot. Selain Teorema 3.2, terdapat alternatif lain untuk mencari solusi optimal pada RKP, alternatif lain tersebut dijelaskan dalam Teorema 3.3, dimana perbedaannya dengan Teorema 3.2 adalah saat perepresentasian masalah ke dalam sebuah graf. Teorema 3.3 Untuk menyelesaikan RKP dengan Pemrograman Dinamik, fungsi rekursif berikut dapat digunakan untuk mencari nilai keputusan pada setiap stage,


! !, !, ! = min ! !, !, ! − 1 , ! ! − !! , ! − 1, ! − 1 + !! untuk ! = 0, … ,

! !!! !!

, ! = 1, … , !, ! = 1, … , !

(3.4)

! !, !, ! = min ! !, !, ! − 1 , ! ! − !! , !, ! − 1 + !! untuk ! = 0, … ,

! !!! !!

, ! = ! + 1, … , !

(3.5)

dan dengan nilai ! adalah kemungkinan total keuntungan yang didapatkan (! = 0, … ,

! !!! !! ),

maka untuk mencari solusi optimal adalah dengan mencari nilai p yang maksmal dengan total bobot pada Knapsack tidak melebihi kapasitas Knapsack (!). Atau memenuhi persamaan berikut, ! ∗ = maks !

! !, !, ! ≤ !, ! = 1, . . Γ − 1 ! !, Γ, ! ≤ !

(3.6)

Dalam Teorema 3.3, fungsi ! !, !, ! menyatakan total bobot minimum untuk solusi layak dengan total keuntungan yang didapatkan sebesar ! dan untuk himpunan 1, … , ! ⊆ ! terdapat ! item dengan bobotnya mencapai !! yang telah dimasukkan ke dalam Knapsack, dimana ! = 0, … ,

! !!! !! ,

! = 1, … , !, dan ! = 1, … , ! .

Sedangkan fungsi ! !, !, ! menyatakan total bobot minimum untuk solusi layak dengan total keuntungan yang didapatkan sebesar !, dan untuk himpunan 1, … , ! ⊆ ! dan terdapat tepat ! item yang bobotnya mencapai !! yang telah dimasukkan ke dalam Knapsack, dimana ! = 0, … ,

! !!! !!

, ! = ! + 1, … , !.

Nilai-nilai inisialisasi pada Teorema 3.3 adalah ! !, !, ! akan bernilai ∞ kecuali untuk ! 0,0,0 akan bernilai 0. Asumsi-asumsi dari Teorema 3.3 adalah nilai ! !, !, ! dan ! !, !, ! tidak boleh lebih dari kapasitas Knapsack (!), hubungan fungsi ! dengan ! adalah ! !, !, ! = !(!, !, !), dan item-item telah terurut sesuai dengan urutan kenaikan bobot !! dari setiap item secara tidak naik. Teorema 3.3 di atas adalah cara yang lain untuk menyelesaikan RKP, yang similar dengan Teorema 3.2. Perbedaannya, simpul pada graf pada Teorema 3.3 ini dinotasikan (!, !, !) dengan ! = 0, … ,

! !!! !! ,

! = 0, … , !, dan ! = 0, … , !.

Adapun busur-busur pada graf yang akan menggambarkan Teorema 3.3 hampir sama dengan macam busur pada Teorema 3.2, dibagi menjadi 4 jenis, yaitu, busur kosong, busur tebal,


busur tipis, dan busur ujung. Untuk busur tebal memiliki label !! , untuk busur tipis memiliki label sebesar !! , sedangkan untuk busur kosong dan busur ujung memiliki label sebesar 0. Contoh 2 Tabel 3.3 Input Data untuk Contoh 2 Item 1 2 3 4

!!

!!

!!

!!

1 1 3 1

5 3 4 2

4 2 1 1

1 2 3 4

Dari informasi yang ada didapatkan ! = 4, ! = 8 , dan ! = 2. Jika digambar dalam bentuk graf akan seperti berikut.

Gambar 3.3 Himpunan Simpul untuk Contoh 2

Gambar 3.4 Graf Keseluruhan yang Terbentuk untuk Contoh 2


Tabel 3.4 Daftar Nilai Keputusan pada Setiap Stage untuk Contoh 3.2 Stage 0

Stage 1

Stage 2

Himpunan nilai keputusan: • ! 0,0,0 = 0 • ! 0,0,1 = 0 • ! 0,0,2 = 0 • ! 0,0,3 = 0 • ! 0,0,4 = 0

Himpunan nilai keputusan: • ! 1,1,1 = 5 • ! 1,1,2 = 5 • ! 1,1,3 = 5 • ! 1,1,4 = 5 • ! 2,1,2 = 3 • ! 2,1,3 = 3 • ! 2,1,4 = 3 • ! 3,1,3 = 4 • ! 3,1,4 = 4 • ! 4,1,4 = 2

Himpunan nilai keputusan: • ! 3,2,2 = 8 • ! 3,2,3 = 8 • ! 3,2,4 = 8 • ! 5,2,3 = 7 • ! 5,2,4 = 7 • ! 5,2,4 = 7 • ! 6,2,4 = 5 • ! 7,2,4 = 6 • ! 3,2,2 = 8 • ! 3,2,3 = 8 • ! 3,2,4 = 8 • ! 5,2,3 = 7 • ! 5,2,4 = 7 • ! 5,2,4 = 7 • ! 6,2,4 = 5 • ! 7,2,4 = 6 • ! 9,2,4 = 8

Untuk mencari solusi optimal RKP yang merupakan keuntungan optimal, cukup dengan mencari nilai ! yang paling maksimum untuk nilai !(!, !, !) dan !(!, Γ, !) yang layak yang telah didapatkan, hal ini dapat dicari dengan persamaan (3.10), yaitu ! ∗ = maks !

! !, !, ! ≤ !, ! = 1, . . ! − 1 ! !, Γ, ! ≤ !

Dalam contoh ini, solusi optimal yang didapatkan adalah sebesar 9, yang merujuk pada simpul (9,2,4), dan label dari simpul tersebut adalah total bobot yang dimasukkan ke dalam Knapsack ,atau kapasitas dari Knapsack yang terpakai untuk mendapatkan solusi optimal, yaitu sebesar 8 satuan bobot. 3.1.2 Pencarian himpunan solusi optimal pada RKP Untuk mendapatkan himpunan solusi optimal dapat dilakukan dengan beberapa cara, diantaranya dengan menelusuri kembali busur-busur yang telah dilewati dari simpul dengan label maksimum sampai ke simpul awal. Dan didaftarkan item-item mana saja yang ditempatkan ke dapam Knapsack sehingga mencapai solusi optimal. Namun, prosedur ini meningkatkan


kebutuhan waktu dan memori dalam algoritma. Karena selain memakan waktu yang lama, prosedur ini juga membutuhkan banyak memori penyimpanan. Prosedur lain untuk mencari himpunan solusi optimal adalah dengan cara menyimpan himpunan solusi pada setiap simpulsimpul yang layak pada graf, sehingga himpunan solusi optimal didapatkan dari himpunan solusi yang disimpan oleh simpul dengan label yang paling maksimum. Namun dalam prosedur ini himpunan solusi dari setiap simpul yang layak harus menyalin himpunan solusi dari simpul sebelumnya yang dilalui, yang mengakibatkan banyaknya memori yang terpakai dan waktu yang cukup lama. (Monaci, Pferschy, dan Serafini, 2013) Oleh karena itu, akan dijelaskan prosedur lain yang lebih efisien mencari himpunan solusi optimal pada RKP. Pendekatan ini dilakukan berdasarkan skema partisi rekursif. Ide utamanya adalah mempartisi himpunan item-item ! menjadi dua subhimpunan ! = !! ∪ !! . Jika ! genap, maka !! = 1, … , !! =

! !

! !

dan !! =

! !

+ 1, … , ! , jika ! ganjil maka !! = 1, … ,

! !

dan

+ 1, … , ! . Setelah menghitung nilai solusi optimal untuk seluruh himpunan N, akan

dicari himpunan solusi optimal secara rekursif untuk setiap subhimpunan !! dan !! . Lema 3.3 berikut menjelaskan langkah-langkah algoritma partisi untuk mendapatkan himpunan solusi optimal. Lema 3.3 Setelah himpunan item-item N dipartisi menjadi dua subhimpunan !! dan !! , dan didapatkan nilai ! ∗ terdapat dua kasus seperti berikut •

Jika ! ∗ ≥ !, maka solusi optimal yang telah didapatkan adalah jumlah dari solusi optimal RKP dengan parameter ! untuk !! dan solusi optimal KP untuk !! dengan bobot !! .

•

Sebaliknya, jika ! ∗ < !, maka solusi optimal yang telah didapatkan adalah jumlah dari solusi optimal E-KKP dengan parameter ! ∗ dan !! untuk !! dan solusi optimal RKP dengan parameter ! − ! ∗ untuk !! .

•

Dengan Teorema 3.2 atau Teorema 3.3 dilanjutkan dengan Lema 3.3, akan didapatkan himpunan solusi optimal dari RKP. Langkah-langkahnya adalah sebagai berikut :


1. Buat himpunan ! yang anggotanya item-item yang sudah terurut sesuai urutan kenaikan bobot (!! ) secara tidak naik. 2. Dengan memakai Teorema 3.2 atau Teorema 3.3, buatlah graf yang berkorespondensi dengan masalah RKP. Tentukan solusi optimalnya (! ∗ ), dan tentukan berapa kapasitas yang terpakai (! ∗ ) 3. Partisi himpunan item menjadi dua bagian (!! dan !! ) 4. Cari banyaknya item di !! yang berkorespondensi dengan solusi optimal (! ∗ ) 5. Perhatikan nilai ! ∗ , apakah ! ∗ ≥ Γ atau ! ∗ < Γ. 6. Dengan menggunakan Lema 3.3, •

jika ! ∗ ≥ Γ, maka cari solusi optimal RKP untuk !! , dan cari himpunan solusi optimal {0,1}-KP untuk !! . Untuk mencari himpunan solusi optimal RKP pada !! , dilakukan partisi untuk item pada !! , mencari ! ∗ kembali untuk himpunan partisi pertama, dan ulang langkah 5, kemudian cek nilai ! ∗ kembali. Hal in dilakukan sampai himpunan partisi hanya ada satu item saja

•

jika ! ∗ < Γ, maka cari himpunan solusi optimal dari (E-KKP) dengan parameter ! ∗ dan !! sebagai bobotnya untuk !! , dan cari solusi optimal dari RKP dengan parameter (Γ − ! ∗ ) untuk !! . Untuk mencari himpunan solusi optimal dari RKP pada !! , dilakukan partisi untuk item pada !! , mencari nilai ! ∗ untuk partisi yang pertama dan ulangi kembali langkah 5, kemudian cek nilai ! ∗ kembali. Hal in dilakukan sampai himpunan partisi hanya ada satu item saja

7. Didapatkan solusi optimal dan himpunan solusi optimal dari RKP secara keseluruhan. Dari contoh sebelumnya, jika keuntungan setiap item yang telah terurut adalah (1, 2, 3, 4), maka solusi optimal ! ∗ yang didapatkan adalah 9 dan ! ∗ yang didapatkan sebesar 8. Selanjutnya himpunan item akan dibagi menjadi dua subhimpunan, !! = {!"#$ 1, !"#$ 2} dan !! = !"#$ 3, !"#$ 4 . Setelah itu akan dihitung ! ∗ yang merupakan banyaknya item di !! yang membuat keuntungan menjadi maksimum, untuk contoh ini didapat ! ∗ = 1. Karena ! ∗ < !, maka akan dicari himpunan solusi optimal EKKP dari !! dengan parameter batasan item adalah sebanyak ! ∗ atau sebanyak 1 dan bobot item yang dipakai adalah bobot item yang mencapai !! , dan didapatkan {!"#$ 2} yang dimasukkan ke dalam Knapsack. Sedangkan dicari juga solusi


optimal untuk himpunan dari !! dengan menggunakan Teorema 3.2 atau Teorema 3.3 dengan parameter ! = 1, didapatkan ! ∗ = 7, ! ∗ = 5. Selanjutkan himpunan !! dipartisi kembali menjadi !!! = {!"#$ 3} dan !!! = {!"#$ 4}, didapatkan ! ∗ = 1. Karena untuk himpunan item ini nilai ! = 1, maka ! ∗ = !, akan dicari solusi optimal himpunan untuk !!! dengan menggunakan Teorema 3.2 atau Teorema 3.3 dan kapasitas !"#$%#&' sekarang tinggal 5, didapatkan ! ∗ = 3 dan ! ∗ = 4. Akan dicari pula himpunan solusi optimal {0,1}-KP untuk himpunan !!! dengan bobot item yang dipakai adalah bobot !! , dan dari himpunan !!! didapatkan solusi {!"#$ 4} yang dimasukkan ke dalam Knapsack. Sampai saat ini sudah ada dua item yang dimasukkan ke dapam Knapsack, yaitu item 2 dan item 4. Langkah selanjutnya, karena anggota himpunan item !!! hanya 1 yaitu item 3, maka item 3 juga akan dimasukkan ke dalam Knapsack. Sehingga item-item yang dimasukkan ke dalam Knapsack untuk mendapatkan solusi optimal adalah item 2, item 3, dan item 4.

4. HASIL DAN IMPLEMENTASI Dalam hal ini akan dilihat efisiensi dari kedua algoritma, dimana akan dibagi 2 kasus, yaitu ketika ! <

! !!! !! dan

ketika ! >

! !!! !! .

Dengan input data yang digunakan dibangkitkan

secara random sesuai asumsi yang ada, perbandingan running time kedua algoritma terlihat pada tabel-tabel berikut: Tabel 4.1 Perbandingan Running Time (dalam satuan detik) untuk kasus ! < Nilai ! 10

50

100

Nilai ! !=1 !=3 !=5 !=5 ! = 15 ! = 30 ! = 10 ! = 30 ! = 50

Teorema 3.2 0.00158393408958 0.0025291141356 0.00363801461367 0.0520166691836 0.148880030066 0.29245893916 0.368281847904 1.09795573279 1.83205780443

! !!! !!

Teorema 3.3 0.00211468151974 0.00338437012351 0.00473958432602 0.0734850606328 0.19025096143 0.357927074521 0.540584788463 1.4948988618 2.39153654806


200

! = 20 ! = 50 ! = 80

2.01468666461 5.18729504792 8.33311243714

4.00384173667 9.5823502964 14.211991927

Sedangkan tabel berikut adalah perbandingan running time kedua algoritma ketika nilai !>

! !!! !! .

Tabel 4.2 Perbandingan Running Time (dalam satuan detik) untuk kasus !> Nilai ! 10

50

100

200

Nilai ! !=1 !=3 !=5 !=5 ! = 15 ! = 30 ! = 10 ! = 30 ! = 50 ! = 20 ! = 50 ! = 80

! !!! !!

Teorema 3.2 0.00615674832989 0.0162319605515 0.0165760112598 0.0944873693315 0.279077416296 0.583719657317 0.582945054515 1.72776205766 2.9568685521 5.63463995435 15.158491064 25.9922788961

Teorema 3.3 0.00274067666555 0.00712976673958 0.0097511985573 0.0763895201371 0.375890548868 0.375890548868 0.552950088212 1.55997429394 2.4665347154 4.04117759174 10.3275221018 17.0371877764

Dari Tabel 4.1 terlihat bahwa untuk semua nilai ! dan nilai ! yang diberikan, running time untuk algoritma pertama selalu lebih cepat dibanding dengan algoritma kedua, sebaliknya pada Tabel 4.2, running time untuk algoritma untuk Teorema 3.3 selalu lebih cepat dari algoritma untuk Teorema 3.2. Hal ini memberikan kesimpulan bahwa jika input data yang digunakan memenuhi kasus yang pertama, yaitu nilai ! <

! !!! !!

maka algoritma yang digunakan lebih baik

algoritma untuk Teorema 3.2. Jika input data yang digunakan memenuhi untuk nilai ! >

! !!! !! ,

maka lebih baik menggunakan algoritma untuk Teorema 3.3 untuk mencari solusi optimal dari RKP.

5. KESIMPULAN Dari penjelasan pada bab-bab sebelumnya, dapat disimpulkan bahwa formulasi RKP akan menjadi seperti berikut


maks

!! !∈!

dengan kendala !! + !∈! | !!!!

!! ≤ ! !∈! | !!!!

Untuk mencari solusi optimal dari RKP akan digunakan Pemrograman Dinamik, dimana terdapat dua alternatif cara mencari solusi optimal untuk RKP yaitu dengan Teorema 3.2 dan Teorema 3.3. Kedua teorema tersebut dapat digambarkan dengan graf. Sedangkan untuk mencari himpunan solusi optimal dapat dilakukan dengan menggunakan algoritma rekursif partisi, dengan ide awalnya adalah mempartisi himpunan item N menjadi dua subhimpunan ! = !! ∪ !! . Jika ! genap, maka !! = 1, … , ganjil maka !! = 1, … ,

! !

dan !! =

! !

! !

dan !! =

! !

+ 1, … , ! , jika !

+ 1, … , ! . Setelah menghitung nilai solusi optimal

untuk seluruh himpunan N, akan dicari himpunan solusi optimal secara rekursif untuk setiap subhimpunan !! dan !! . Dari hasil implementasi yang dilakukan, kecepatan algoritma untuk mencari solusi optimal pada RKP tergantung nilai input data yang digunakan. Jika input data yang digunakan memenuhi kasus ketika ! <

! !!! !!

maka algoritma yang digunakan lebih baik algoritma

Teorema 3.2. Jika input data yang digunakan memenuhi untuk nilai ! >

! !!! !! ,

maka lebih baik

menggunakan algoritma Teorema 3.3 untuk mencari solusi optimal dari RKP.

6. DAFTAR REFERENSI Bartholdi, John. 2008. The Knapsack Problem. New York. Springer Bertsimas, D., Melvyn S. 2004. The Price of Robustness. Informs Operation Research, 52, 35-53 Brassard, Gilles., Paul Bratley. 1988. Algorithmics, Theory & Practice. Prentice Hall Caprara, A., Hans Kellerer, Ulrich Pferschy, David Pisinger. 2000. Approximation Algorithms for Knapsack Problems with Cardinality Constraints. European Journal of Operational Research. Cooper, L., Mary Cooper. 1981. Introduction to Dynamic Programing. Pergamon Press.


Hillier, F. S., Gerald J. Lieberman. 2001. Introduction to Operation Research, Seventh Edition. New York. Mc-Graw Hill. Hristakeva, M., Dipti Shrestha. 2005. Different Approaches to Solve the 0/1 Knapsack Problem. Midwest Instruction and Computing Symposium, University of Wisconsin. Monaci, M., Ulrich Pferschy, Paolo Serafini. 2013. Exact Solution for Robust Knapsack Problem. Elsevier Ltd Computer & Operation Reseach, 40, 2625-2628. Pisinger, David. 1995. Algorithm of Knapsack Problem. University of Copenhagen. Departement of Computer Science. Ruohonen, Keijo. 2013. Graph Theory. Tampere University of Technology 2008 Taha, Hamdi A. 2007. Operations Research, an Inroduction, 8th Edition. United States of America. Pearson Prentice Hall. West, Douglas. B. 1996. Introduction to Graph Theory. New Delhi. Prentice of Hall


PENYELESAIAN ROBUST KNAPSACK PROBLEM (RKP) MENGGUNAKAN PEMROGRAMAN DINAMIK

Recommend Documents