Dalam kehidupan
sehari-hari, kita sering dipusingkan dengan media penyimpanan yang terbatas
padahal kita diharuskan menyimpan beberapa objek kedalam media tersebut.
Bagaimana kita mengatur objek apa saja yang dipilih dan seberapa
besar objek tersebut disimpan?
Dari
permasalahan tersebut, munculah suatu permasalahan yang dikenal dengan “Permasalahan Knapsack” atau lebih
dikenal dengan “Knapsack Problem”. Masalah
Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian
banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu
penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek
(1,2,3,...) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan
memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai
probabilitas dari setiap objek (Xi).
Permasalahan
ini dapat diselesaikan dengan 3 cara, yaitu :1. Matematika, 2. Kriteria Greedy,
dan 3. Algoritma Greedy. Dalam
kasus ini penulis mencoba menyelesaikan dengan 3 cara di atas.
Metode
Greedy merupakan salah satu cara untuk mendapatkan solusi optimal dalam proses
penyimpanan. Pada metode ini untuk mendapatkan solusi optimal dari permasalahan
yang mempunyai dua kriteria yaitu Fungsi
Tujuan/Utama dan Nilai Pembatas (Constrain). Fungsi Tujuan hanya terdiri
atas satu fungsi sedangkan Fungsi Pembatas dapat terdiri atas lebih dari satu
fungsi.
Proses Kerja Metode Greedy
Menyelesaikan
suatu masalah dengan beberapa fungsi pembatas untuk mencapai satu fungsi
tujuan. Jadi dalam penyelesaiannya harus ditentukan mana sebagai fungsi
pembatas dan mana sebagai fungsi tujuan.
Cara menyelesaikan masalah
Knapsack adalah
1.
Tentukan Fungsi Tujuan, yaitu mencari nilai
maximum dari jumlah hasil perkalian
antara nilai profit (Pi) dengan nilai probabilitas (Xi)
Maximum ∑Pi.Xi
2.
Tentukan Fungsi Pembatas, yang merupakan
hasil penjumlahan dari perkalian antara bobot (Wi) dengan nilai probabilitas
(Xi) yang tidak boleh melebihi dari kapasitas media penyimpanan (M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari
ke-2 cara di atas berarti kita harus mengetahui
1.
Jumlah objek (n)
2.
Bobot setiap objek (Wi)
3.
Profit setiap objek (Pi)
4.
Probabilitas setiap objek (Xi), dan
5.
Kapasitas media penyimpanan (M)
Seperti penulis sudah sampaikan di
atas bahwa permasalahan knapsack ini bisa diselesaikan dengan 3 cara, yaitu
matematika, kriteria greedy dan algoritma greedy.
Penulis
mencoba untuk membahas satu persatu.
1.
Cara Matematika, kita harus memperhatikan
nilai probabilitas dari setiap barang, karena nilai inilah sebagai penentunya
dengan memperhatikan nilai probabilitas (Xi) yaitu 0≤Xi≤1. Disini nilai Xi kisarannya sangat banyak bisa 0, 0.1, 0.01,
0.001, ...., 1.
2.
Kriteria greedy dengan memperhatikan:
a.
Pilih objek dengan nilai profit terbesar (Pi)
b.
Pilih objek dengan bobot terkecil (Wi)
c.
Pilih objek dengan nilai perbandingan profit
dengan bobot yang terbesar (Pi/Wi)
3.
Algortima greedy, yaitu
PROCEDURE GREEDY KNAPSACK (P, W, X, n)
REAL P(1:n), W(1:n),
X(1:n), M, isi
INTEGER i, n
X(1:n) = 0
isi = M
FOR i = 1 TO n DO
IF W(i) > isi THEN EXIT ENDIF
X(i) = 1
isi = isi – W(i)
REPEAT
IF i ≤ n THEN X(i) = isi/W(i) ENDIF
END GREEDY KNAPSACK
Teknik yang ke-3 ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan
nilai Pi/Wi.
Contoh :
Diketahui
3 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal
sebesar 20 Kg. Berat masing-masing barang adalah 18 Kg, 15 Kg, dan 10 Kg dimana
setiap barang memiliki profit sebesar masing-masing 25, 24, dan 15. Tentukan
barang mana saja yang dapat disimpan ke dalam tempat penyimpanan sehingga
diperoleh nilai profit yang maksimal.
Jawab
1.
Cara matematika
n = 3, (1,
2, 3) à
objek
M = 20 à kapasitas
(W1,
W2, W3) = (18, 15, 10)
(P1,
P2, P3) = (25, 24, 15)
Nilai
probabilitas 0
≤ Xi ≤ 1
Solusi ke
|
Nilai Probabilitas
|
Fungsi Pembatas
|
Fungsi Tujuan
|
∑
Wi.Xi ≤ M
|
∑
Pi.Xi (Maximum)
|
||
(X1,
X2, X3)
|
(W1. X1)
+ (W2. X2) + (W3. X3) ≤ M
|
(P1. X1)
+ (P2. X2) + (P3. X3)
|
|
1
|
(1, 2/15, 0)
|
(18.1) + (15.2/15) + (10.0) ≤ 20
|
(25.1) + (24.2/15) + (15.0)
|
20
|
28,2
|
||
2
|
(1, 0, 1/5)
|
(18.1) + (15.0) + (10.1/5) ≤ 20
|
(25.1) + (24.0) + (15.1/5)
|
20
|
28
|
||
3
|
(0, 1, ½)
|
(18.0) + (15.1) + (10.1/2) ≤ 20
|
(25.0) + (24.1) + (15.1/2)
|
20
|
31,5
|
||
4
|
(1/3, ½, ½)
|
(18.1/3) + (15.1/2) + (10.1/2) ≤ 20
|
(25.1/3) + (24.1/2) + (15.1/2)
|
18,5
|
27,83
|
||
...
|
....
|
....
|
....
|
Dengan cara
ini sulit untuk menentukan yang paling optimal sebab kita harus mencari
nilai probabilitas yang tersebar antara 0 dan 1, 0 ≤ Xi ≤ 1 untuk setiap objek. Cara ini
disarankan tidak digunakan.
2.
Cara kriteria greedy
n = 3, (1,
2, 3) à
objek
M = 20 à kapasitas
(W1,
W2, W3) = (18, 15, 10)
(P1,
P2, P3) = (25, 24, 15)
Nilai
probabilitas 0
≤ Xi ≤ 1
Kriteria greedy :
a. Pilih objek dengan nilai profit terbesar (Pi)
Susun
data sesuai kriteria:
(P1,
P2, P3) = (25, 24, 15)
(W1,
W2, W3) = (18, 15, 10)
Solusi ke
|
Nilai Probabilitas
|
Fungsi Pembatas
|
Fungsi Tujuan
|
∑
Wi.Xi ≤ M
|
∑
Pi.Xi (Maximum)
|
||
(X1,
X2, X3)
|
(W1. X1)
+ (W2. X2) + (W3. X3) ≤ M
|
(P1. X1)
+ (P2. X2) + (P3. X3)
|
|
a
|
(1, 2/15, 0)
|
(18.1) + (15.2/15) + (10.0) ≤ 20
|
(25.1) + (24.2/15) + (15.0)
|
20
|
28,2
|
b. Pilih objek dengan bobot terkecil (Wi)
Susun
data sesuai kriteria:
(P3,
P2, P1) = (15, 24, 25)
(W3,
W2, W1) = (10, 15, 18)
Solusi ke
|
Nilai Probabilitas
|
Fungsi Pembatas
|
Fungsi Tujuan
|
∑
Wi.Xi ≤ M
|
∑
Pi.Xi (Maximum)
|
||
(X3,
X2, X1)
|
(W3. X3)
+ (W2. X2) + (W1. X1) ≤ M
|
(P3. X3)
+ (P2. X2) + (P1. X1)
|
|
b
|
(1, 2/3, 0)
|
(10.1) + (15.2/3) + (18.0) ≤ 20
|
(15.1) + (24.2/3) + (25.0)
|
20
|
31
|
c. Pilih objek dengan nilai perbandingan profit
dengan bobot yang terbesar (Pi/Wi)
Data
yang diketahui:
(P1,
P2, P3) = (25, 24, 15)
(W1,
W2, W3) = (18, 15, 10)
perbandingan profit dengan
bobot
P1/
W1 = 25/18 = 1,39
P2/
W2 = 24/15 = 1,6
P3/
W3 = 15/10 = 1,5
Susun data sesuai kriteria:
(P2,
P3, P1) = (24, 15, 25)
(W2,
W3, W1) = (15, 10, 18)
Solusi ke
|
Nilai Probabilitas
|
Fungsi Pembatas
|
Fungsi Tujuan
|
∑
Wi.Xi ≤ M
|
∑
Pi.Xi (Maximum)
|
||
(X2,
X3, X1)
|
(W2. X2)
+ (W3. X3) + (W1. X1) ≤ M
|
(P2. X2)
+ (P3. X3) + (P1. X1)
|
|
c
|
(1, 1/2, 0)
|
(15.1) + (10.1/2) + (18.0) ≤ 20
|
(24.1) + (15.1/2) + (25.0)
|
20
|
31,5
|
Dari
3 kriteria di atas dapat disimpulkan bahwa fungsi
tujuan yang bernilai maximum adalah 31,5 dengan fungsi pembatasnya adalah 20
dan nilai probabilitasnya adalah (X2, X3, X1)
= (1, 1/2, 0), jadi disini
yang memeberikan hasil optimal pada kriteria yang ke-3 yaitu Pilih objek dengan nilai
perbandingan profit dengan bobot yang terbesar (Pi/Wi)
3.
Cara algoritma greedy
Teknik ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan
nilai Pi/Wi.
Data yang diketahui:
n = 3, (1,
2, 3) à
objek
M = 20 à kapasitas
(W1,
W2, W3) = (18, 15, 10)
(P1,
P2, P3) = (25, 24, 15)
Nilai
probabilitas 0
≤ Xi ≤ 1
perbandingan profit dengan
bobot
P1/
W1 = 25/18 = 1,39
P2/
W2 = 24/15 = 1,6
P3/
W3 = 15/10 = 1,5
Susun data sesuai kriteria
(non increasing):
(P2,
P3, P1) = (24, 15, 25) atau
(P1, P2, P3)
= (24, 15, 25)
(W2,
W3, W1) = (15, 10, 18) atau
(W1, W2, W3)
= (15, 10, 18)
Masukkan nilai kriteria di atas ke
dalam algoritma greedy
1. PROCEDURE
GREEDY KNAPSACK (P, W, X, n) à nama prosedur/proses
2. REAL P(1:n), W(1:n), X(1:n), M, isi à variabel yang digunakan
3. INTEGER
i, n à variabel yang digunakan
4. X(1:n) = 0
5. isi =
M
6. FOR i
= 1 TO n DO
7. IF W(i) > isi THEN EXIT ENDIF
8. X(i) = 1
9. isi = isi – W(i)
10. REPEAT
11. IF i
≤ n THEN X(i) = isi/W(i) ENDIF
12. END
GREEDY KNAPSACK à akhir prosedur/proses
Proses kegiatan dimulai dari langkah ke- 4 sampai dengan 11.
X(1:3) = 0, artinya
X(1)=0, X(2)=0, X(3)=0
isi = M = 20
Pengulangan untuk i = 1
sampai dengan 3
Untuk i = 1
Apakah W(1) > isi
Apakah 15 > 20, jawabnya tidak, karena tidak maka perintah dibawah IF dikerjakan.
X(1) = 1 à nilai probabilitas untuk
objek pada urutan pertama (X1)
isi = 20 – 15 = 5
REPEAT à mengulang untuk perulangan FOR
Untuk i = 2
Apakah W(2) > isi
Apakah 15 > 5, jawabnya ya, karena ya maka perintah EXIT dikerjakan, yaitu keluar dari
pengulangan/FOR dan mengerjakan perintah di bawah REPEAT.
Apakah 2 ≤ 3, jawabnya ya, karena ya maka X(2) = 5/10 = ½ à nilai probabilitas untuk
objek pada urutan kedua (X2).
Selesai (akhir dari prosedur greedy knapsack)
Berarti untuk nilai X(3) = 0 atau X3 = 0, sebab nilai probabilitas untuk objek
ke-3 tidak pernah dicari.
Jadi
(P1,
P2, P3) = (24, 15, 25)
(W1, W2, W3)
= (15, 10, 18)
(X2, X3, X1)
= (1, 1/2, 0)
Fungsi Pembatas :
∑
Wi.Xi ≤ M
(W1.
X1) + (W2.
X2) + (W3.
X3) ≤ M
(15.1)
+ (10.1/2) + (18.0) ≤ 20
20 ≤ 20
Fungsi Tujuan :
∑
Pi.Xi = (P1. X1)
+ (P2. X2)
+ (P3. X3)
= (24.1) + (15.1/2) + (25.0)
= 31,5
Latihan :
Diketahui
4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal
sebesar 30 Kg. Berat masing-masing barang adalah 15 Kg, 10 Kg, 18 Kg dan 20 Kg
dimana setiap barang memiliki profit sebesar masing-masing 20, 25, 9, dan 15.
Tentukan barang mana saja yang dapat disimpan ke dalam tempat penyimpanan
sehingga diperoleh nilai profit yang maksimal (Cari dengan kriteria greedy dan algoritma greedy).
No comments:
Post a Comment