KNAPSACK ALGORITMA

BAB 1

PENDAHULUAN

I.                   Latar belakang

Dari berbagai masalah yang sering muncul dalam kehidupan kita, optimasi selalu menarik untuk diperbincangkan. Dalam pemrograman, optimasi pun memiliki tempatnyatersendiri. Baik itu menjadi masalah yang harus dipecahkan, maupun keharusan dalam membuat program yang optimal. Permasalahan Knapsack merupakan suatu permasalahan yang sering dihadapi oleh perusahaan transportasi dalam pengiriman dan pengelolaan barang. Permasalahan ini sering juga terjadi pada media transportasi ketika akan mengangkut banyak barang. Dimana berat barang yang diangkut tersebut tidak boleh melebihi kapasitas limit daya tampung media transportasi tersebut, dan diharapkan dari pengangkutan barang tersebut didapatkan profit atau keuntungan yang semaksimal mungkin. Untuk menyelesaikan masalah knapsack dapat dilakukan dengan  berbagai macam algoritma, salah satunya adalah dengan menggunakan algoritma genetik , algoritma kolesar ataupun algoritma greedy. Ketiga algoritma tersebut dapat digunakan  untuk menyelesaikan masalah  knapsack karena  dapat menghasilkan solusi yang optimum, serta  dapat menganalisis pemilihan barang  sehingga dapat  menciptakan sebuah daya angkut dan profit yang optimal.

II.                Tujuan

1.      Mampu memahami masalah dalam knapsack.

2.      Dapat menyelesaikan masalah knapsack,dengan menggunakan algoritma.

3.      Mampu menggunakan berbagai macam algoritma untuk menyelesaikan masalah knapsack.

4.      Mengetahui berbagai rumus dalam algoritma.

III.             Rumusan Masalah

A.       Knapsack

·        Pengertian

·        Jenis persoalan

·        Strategi dalam algoritma greedy

·        Masalah knapsack

B.              Algoritma Branch and Bound

·        Pengertian

·        Fungsi heuristik

·        Prinsip dari algoritma branch and bound

·        Pohon

BAB II

PEMBAHASAN

          KNAPSACK

·        Pengertian

Knapsack adalah salah satu masalah yang sering muncul dalam kasus optimasi dan kombinatorial yang banyak ditemukan pada literatur-literatur lama dan hingga kini permasalahan ini masih banyak ditemukan dalam kehidupan sehari-hari. Knapsack sendiri terdiri dari beberapa varian, yaitu0-1Knapsack, Knapsack Terbatas, dan Knapsack Tak Terbatas. Contoh kongkret permasalahan ini dalam dunia nyata adalah penjualan beberapa jenis keperluan rumah tangga oleh pedagang keliling dengan menggunakan gerobak ataupun alat pengangkut lainnya yang hanya memiliki kapasitas angkut maksimum sebesar w kg.

·        Knapsack problem memiliki tiga jenis persolan, yaitu :

1.    Knapsack 0/1

Sesuatu yang dimasukkan kedalam karung dimensinya harus dimasukkan semua atau tidak sama sekali.

2.    Knapsack Bounded

Sesuatu yang dimasukkan kedalam karung dimensinya bisa dimasukkan sebagaian atau seluruhnya.

3.     Knapsack Unbounded

Ada beberapa strategi algoritma yang bisa menghasilkan solusi optimal,diantaranya adalah Brute Force, algotitma genetika, Algoritma greedy. Pada makalah inimasalah knapsack 0/1 akan diselesaikan dengan Algoritma Greedy yaitu solusi yang mencari nilai optimum.

Algoritma ini memecahkan permasalahan langkah per langkah, yaitu:

1.      Mengambil pilihan terbaik yang bisa diperoleh saat itu juga tanpa memperhatikankonsekuensi kedepan

2.      Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir denganoptimum global.

·        Pada algoritma Greedy ada beberapa strategi yang digunakan untuk memilih objek yang akan dimasukkan kedalam knapsack, yaitu:

1.      Greedy by profit 

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang palingmenguntungkan terlebih dahulu.

2.      Greedy by weight.

Pada setiap langkah,knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba mdmaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack.

3.      Greedy by density.

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai densitas,  pi / wi terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

·        Masalah Knapsack

Masalah Knapsack merupakan sebuah persoalan yang menarik. Dalam dunia nyata permasalahan Knapsack ini sering sekali digunakan terutama pada bidang (jasa) pengangkutan barang (seperti pengangkutan peti kemas dalam sebuah kapal). Dalam usaha tersebut, diinginkan suatu keuntungan yang maksimal untuk mengangkut barang yang ada dengan tidak melebihi batas kapasitas yang ada. Berdasarkan persoalan tersebut, diharapkan ada suatu solusi yang secara otomatis dalam mengatasi persoalan itu. Problem Knapsack adalah permasalahan optimasi kombinatorial, dimana kita harus mencari solusi terbaik dari banyak kemungkinan yang dihasilkan.

Penyelesaian masalah dengan menggunakan algoritma exhaustive search adalah mengenumerasikan semua kemungkinan barang-barang yang layak atau memenuhi syarat yaitu tidak melebihi batas. Kemudian menghitung tiap-tiap keuntungan yang diperoleh dan memilih solusi yang menghasilkan keuntungan terbesar. Berbeda dengan algoritma exhaustive search yang cukup memakan waktu dan dapat menghasilkan solusi yang optimum, penyelesaian masalah dengan menggunakan algoritma greedy dilakukan dengan memasukan objek satu persatu, dan tiap kali objek tersebut telah dimasukan, maka objek tersebut tidak dapat lagi dikeluarkan. Dan pencarian solusi akan dilakukan dengan memilih salah satu jenis dari algoritma greedy seperti pada penjelasan diatas.

      Algoritma Branch and Bound

·        Pengertian

Algoritma Branch and Bound juga merupakan salah satu strategi yang dapat digunakan dalam pencarian solusi optimum dari permasalahan knapsack ini. Dengan penentuan keuntungan maksimal pada tiap simpulnya, proses pencarian akan membawa kita pada solusi yang optimum . karena tidak semua objek pada permasalahan ini dapat dimasukan kedalam knapsack, maka kemungkinan bahwa kita akan sampai pada keadaan dimana tidak ada lagi simpul yang dapat dibangkitkan kerena telah melewati batas kapasitas daya angkut membuat kita harus menentukan solusi omtimum dengan membandingkan lintasan-lintasan mana yang berakhir didaun pada pohon yang akan manghasilkan keuntungan paling besar maka objek-objek tersebutlah yang akan dipilih.

Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).

·        Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :

ĉ (i) = f(i) + (i) yang dalam hal ini,

ĉ (i) = ongkos untuk simpul i

f(i)               = ongkos mencapai simpul i dari akar

ĝ(i)  = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan).

Nilai ĉ digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki ĉ minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).

·        Prinsip dari algoritma branch and bound ini adalah :

1.    Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Dan  berhenti.

2.    Jika Q kosong, tidak ada solusi. Dan berhenti.

3.     Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai ĉ (i) paling kecil. Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.

4.    Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.

·        Pohon

Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit. Dengan setiap kemungkinan solusi dianggap sebagai sebuah simpul dan akar dari pohon, banyak algoritma yang menggunakan ruang solusi berupa pohon ini karena akan lebih memudahkan dalam penelusuran solusi yang ada berupa simpul-simpul pohon.

·        Bentuk pohon

Dengan rumus fungsi heuristik

ĉ(i) = f(i) + g(i)

ĉ(2) = 12 + 5*(16-2) = 82

ĉ(3) = 15 + 6*(16-5) = 81

ĉ(3) = 50 + 6*(16-10)-86

ĉ(4) = 10 + 6*(16-5)=76

 

Keterangan :

a.                                                1 merupakan akar

b.                                               2,3,4 dan 5 merupakan simpul anak akar

·        Contoh masalah knapsack

Permasalahan knapsack atau yang biasa kita kenal dengan sebutan 0/1 knapsack merupakan salah satu dari persoalan klasik yang banyak ditemukan pada literatur-literatur lama dan hingga kini permasalahan ini masih banyak ditemukan dalam kehidupan sehari-hari. Contoh kongkret permasalahan ini dalam dunia nyata adalah penjualan beberapa jenis keperluan rumah tangga oleh pedagang keliling dengan menggunakan gerobak ataupun alat pengangkut lainnya yang hanya memiliki kapasitas angkut maksimum sebesar w kg keperluan rumah tangga yang akan dijual hanya berjumlah satu untuk tiap jenisnya dan tiap jenis barang memiliki berat w1,w2,w3,w4, ..wn dengan keuntungan yang diperoleh untuk tiap jenisnya adalah p1,p2,p3,p4, .pn. tidak semua jenis keperluan rumah tangga yang akan dijual oleh pedagang keliling tersebut dapat dimasukan kedalam alat pengangkut. Maka akan dipilih jenis-jenis keperluan rumah tangga yang akan dijual untuk setiap harinya oleh pedagang keliling tersebut agar diperoleh keuntungan yang maksimal dari penjualan barang-barang keperluan rumah tangga tersebut. Telah banyak strategi yang diterapkan untuk menyelesaikan permasalah tersebut diantaranya adalah dengan menggunakan algoritma exhaustive search, greedy dan juga branch and bound.

BAB III

PENUTUP

A.     KESIMPULAN

Knapsack adalah permasalahan kombinasi yang melibatkan optimasi, dan terdapat variasi masalah dilihat dari jumlah tiap barang i yang ditangani dengan menggunakan Knapsack 0/1. Dan Algoritma Branch and Bound merupakan salah satu algoritma yang dapat diterapkan dalam mencari penyelesaian pada permasalahan knapsack. Dengan batas-batas yang ditentukan, algoritma ini mampu mencapai solusi yang optimum seperti yang berhasil dilakukan oleh algoritma exhautive search, namun dengan membunuh semua simpul yang tidak mungkin diperluas, algoritma branch and bound ini tidak memperhitungkan semua kemungkinan yang ada sehingga akan lebih mengefisienkan waktu yang digunakan untuk pemecahan masalah ini.

B.     SARAN

Menurut saya, algoritma Exhaustive Search  masih kurang ringkas untuk diterapkan sebagai strategi pencarian solusi pada permasalahan knapsack karena tidak diketahuinya batasan kapan kita sampai pada tahap solusi. Dibandingkan penerapan algoritma branch adn bound yang dapat dengan jelas diketahui keadaan dimana sudah tercapai solusi tanpa harus terus memperluas semua simpul sampai tidak ada lagi simpul yang tersisa. Selain itu algoritma exhautive seacrh juga memekan waktu banyak dalam menyelesaikan suatu masalah.