makalah tugas pendahuluan kelompok 27

MAKALAH TUGAS PENDAHULUAN

TEKNOLOGI INFORMATIKA

IMPLEMENTASI ALGORITMA

GREEDY DALAM PEMROGRAMAN KNAPSACK PROBLEM

Disusun Oleh :

1. Viky Hurisandi                                                                  (21070114120051)

2. Dea Rama Sabrina                                                             (21070114120065)

3. Dhana Antasari                                                                  (21070114140107)

  

PROGRAM STUDI TEKNIK INDUSTRI

FAKULTAS TEKNIK UNIVERSITAS DIPONEGORO

SEMARANG

2014

KATA PENGANTAR

Puji dan sukur kami ucapkan kehadirat Tuhan Yang Maha Esa karena berkat rahmat dan hidayahnya kami dapat menyelesaikan makalah ini yang berjudul “Implementasi Algoritma Greedy untuk Menyelesaikan Masalah Knapsack Problem”, yang dimasa modern ini, semakin banyak masalah yang membutuhkan penanganan khusus.

Makalah ini kami buat untuk memenuhi syarat agar kami para mahasiswa/i dapat melaksanakan praktikum Teknologi Informasi yang diselenggarakan oleh Laboratorium Decicion Support System, Jurusan Teknik Industri, Fakultas Teknik Universitas Diponegoro.

Kami ucapkan terima kasih kepada semua pihak yang telah ikut berkontribusi dalam penyusunan makalah ini

Kami sangat berharap agar makalah ini berguna untuk para pembaca dan dijadikan referensi. Kami juga menyadari bahwa makalah yang kami buat masih banyak kekurangan. Oleh karena itu, kami meminta maaf dan berharap para pembaca memberi kritik dan saran. Terima kasih

Semarang, 9 November 2014

Penulis

DAFTAR ISI

KATA PENGANTAR…………………………………………     2

DAFTAR ISI……………………………………………………     3

BAB I PENDAHULUAN……………………………………...     4

1. LATAR BELAKANG MASALAH……………………      4
2. RUMUSAN MASALAH……………………………….     4
3. TUJUAN MASALAH………………………………….      4
4. BATASAN MASALAH………………………………..      5

BAB II ISI………………………………………………………     6

1. DEFINISI KNAPSACK……………………………...        6
2. STANDAR ALGORITMA GREEDY...…………….          6
3. ANALISA DAN IMPLEMENTASI…………………….    7

BAB III PENUTUP…………………………………………..        10

A.  SIMPULAN……………………………………………       10

B.  SARAN………………………………………………..        10

DAFTAR PUSTAKA………………………………………..        11

BAB I

PENDAHULUAN

A.    LATAR BELAKANG MASALAH

      Ada banyak masalah di bidang transportasi yang terkait dengan optimisasi. Salah satu permasalahan di bidang  transportasi yang muncul adalah  bagaimana suatu perusahaan mengatur produk apa yang harus diangkut agar memperoleh keuntungan yang maksimal, sementara perusahaan sendiri memiliki problematika / kendala yaitu kapasitas angkut dari kendaraan yang sangat  terbatas.
knapsack merupakan kantung untuk mengukurnya. Dengan adanya algoritma, maka memudahkan kita dalam  mengetahui batas maksimum dalam penggunaan knapsack.

B.     RUMUSAN MASALAH

1. Apakah yang dimaksud dengan Knapsack Problem?
2. Apakah yang dimaksud dengan Algoritma Greedy?
3. Bagaimana penggunaan algoritma greedy dalam penyelesaian Knapsack Problem?

C.    TUJUAN MASALAH

1. Dapat mendeskripsikan apa yang dimaksud Knapsack Problem
2. Dapat mendeskripsikan apa yang dimaksud Algoritma Greedy
3. Mengetahui cara penggunaan  algoritma greedy untuk menyelesaikan Knapsack Problem

D.    BATASAN MASALAH

1. Peran algoritma dalam kehidupan sehari-hari
2. Tahapan algoritma greedy dalam knapsack problem

BAB II

ISI

A.    DEFINISI KNAPSACK PROBLEM

Knapsack dalam bahasa Indonesia adalah tas atau karung. Fungsi dari karung atau tas itu sendiri adalah untuk menampung atau memuat suatu barang. Namun, tas dan karung itu sendiri memiliki kapasitas tersendiri sehingga tidak semuabarang dapat tertampung didalam nya. Sebagai contoh, sebuah tas berkapasitas 20 kg dan akan dimasuki barang-barang yang mempunyai massa total 25kg. Yang menjadi persoalan adalah barang mana saja yang akan dimasukkan.

Knapsack Problemnya dapat ditulis secara matematis sebagai berikut:bobot knapsack ialah M. Diketahui n buah objek dengan massa w1, w2,w3,...,wn. Maka dapat persamaan M=b1w1+b2w2+.....+bnwn

Dalam teori algoritma, persoalan knapsack termasuk didalam kelompok NP-complete. Persoalan yang termasuk dalam kelompok Npcomplete tidak dapat dipecahkan dengan  orde polinomial. Sehingga dibutuhkan suatu cara untuk menyelesaikan persoalan tersebut

B.     DEFINISI ALGORITMA GREEDY

Algoritma Greedy merupakan algoritma yang lazim dalam persoalan mengenai optimalisasi meskipun hasilnya bukan merupakan solusi yang optimum. Prinsip utama dari algoritma ini ialah mengambil sebanyak banyaknya yang dapat diperoleh sekarang. Hal ini sesuai dengan arti harfiahnya dari kata Greedy yang berarti tamak.untuk menyelesaikan persoalan algoritma greedy kita membutuhkan elemen elemen.

Elemen yang pertama ialah himpunan kandidat yang berisi elemen elemen solusi. Elemen yag kedua ialah himpunan solusi yang berisi kandidat terpilih. Elemen yang ketiga ialah fungsi seleksi. Fungsi ini untuk memilih kandidat yang memungkinkan guna mencapai hasil yang optimum. Elemen yang keempat ialah fungsi kelayakan. Fungsi ini berguna untuk mengecek kandidat yang terpilih sesuai dengan aturan. Elemen yang kelima ialah fungsi objektif yang memaksimumkan dan meminimumkan nilai solusi.

Skema umum algoritma greedy ialah yang pertama inisialisasi S dengan kosong. Kemudian pilih kandidat C melalui fungsi seleksi. Kemudian kurangi C dengan kandidat yang sudah dipilih. Kemudian periksa dengan fungsi kelayakan. Dan yang terakhir periksa dengan fungsi objektif.

Pada setiap langkah pilih objek dengan berat teringan kemudian mencoba memaksimumkan keuntungan dengan memasukkan objek sebanyak mungkin kedalam knapsack. Pertama kali mengurutkan objek dengan menaik berdasarkan beratnya. Kemudian masukkan satu per satu objek kedalam knapsack sampai knapsack tidak dapat dimasukkan lagi.

 

C.    ANALISA DAN IMPLEMENTASI

Berdasarkan teori dan contoh algoritma greedy dalam  menyelesaikan Knapsack Problem maka  pseudocode algoritma greedy adalah sebagai berikut :

function Knapsack( input C : himpunan_objek, K : real) ®himpunan_solusi

{ Menghasilkan solusi persoalan knapsack dengan algoritma greedy yang menggunakan

strategi pemilihan objek berdasarkan profit (pi),weight(wi),density (pi/wi). Solusi

dinyatakan sebagai vektor X = x[1], x[2], ..., x[n].

Asumsi: Untuk Greedy by profit seluruh objek sudah terurut berdasarkan nilai pi

yang  menurun. Untuk Greedy by weighted seluruh objek sudah terurut berdasarkan nilai wi yang  menaik.Untuk Greedy by density seluruh objek sudah

terurut berdasarkan nilai p

i

/w

i

yang menurun.

Deklarasi i, TotalBobot : integer

Avalaible :

boolean

x : himpunan_solusi

Algoritma:

For i ¬1

To n do

x[i] ¬0

{ inisialisasi setiap status

pengambilan objek i dengan 0 }

endfor

i ¬0

TotalBobot ¬0

Available ¬true

While (i £ n)

and

(Available)

do

{ cek objek ke - i }

i ¬ i + 1

if TotalBobot + w[i] £ K

then { masukkan objek Ci ke dalam knapsack }

x[i]¬1

TotalBobot ¬TotalBobot + w[i]

else

Available ¬false

BAB III

PENUTUP

A.                SIMPULAN

Jadi, berdasarkan uraian bahasan di atas dapat disimpulkan bahwa :

1.    Knapsack  adalah tas atau karung. Fungsi dari karung atau tas itu sendiri adalah untuk menampung atau memuat suatu barang.

2.    Algoritma tidak dapat di buat secara sembarangan, karena dibutuhkaan algoritma yang baik dan sistematis untuk menghasilkan output yang akurat.

3.  salah satu contoh implementasi algoritma greedy dalam kehidupan sehari hari adalah penggunaannya pada knapsack problem.  Sistem ini cocok untuk kasus yang item barang / objek nya harus diambil  keseluruhan (1) atau tidak diambil sama sekali  (0) lebih sering disebut Knapsack Problem 0/1. Sistem ini tidak dapat menangani kasus dimana item barang/objek nya dapat diambil sebagian

B.                 SARAN

Dari pembahasan diatas sebaiknya kita dapat:

1. Mengetahui algoritma yang sesuai dalam menyelesaikan suatu kasus

2. Mempelajari dan melakukan latihan pembuatan bahasa pemrograman

DAFTAR PUSTAKA

Dian Rachmawati, Ade Candra, Jurnal SAINTIKOM, IMPLEMENTASI ALGORITMA GREEDY UNTUK MENYELESAIKAN MASALAH KNAPSACK PROBLEM, Vol. 12, No.3, September 2013.

Vaxtra Maendhapaskha, Andi Wahju Rahardjo Emanuel, Jurnal Sistem Informasi, Penerapan Algoritma Greedy Knapsack untuk Optimalisasi Poin pada Situs Anggota Direct Selling Oriflame,Vol. 9 No. 1, Maret 2014: 83 – 92.

Prasetyo Andy Wicaksono, MAKALAH IF2251 STRATEGI ALGORITMIK, EKSPLORASI ALGORITMA BRUTE FORCE, GREEDY DAN PEMROGRAMAN DINAMIS PADA PENYELESAIAN MASALAH 0/1 KNAPSACK, 2007.