Metode greedy adalah metode yang
digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi,
yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud
mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari
sekumpulan alternatif solusi yang ada.
Arti kata greedy sendiri adalah RAKUS, namun
maksud dari metode grredy adalah kita melihat solusi optimal lokal, atau solusi
optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal
secara global atau secara keseluruhan
Untuk lebih jelasnya, berikut
contoh soal dengan berbagai macam metode Greedy.
1. Diketahui 4 program yang akan disimpan dalam
media penyimpanan dengan panjang masing-masing 6, 8, 4, dan 2. Bagaimana proses
penyimpanan yang optimal dengan metode greedy?
Penyelesaian:
Dari kasus
diketahui jumlah data (n) adalah 4, berarti kombinasi yang dibutuhkan adalah
n!, yaitu 4!=4*3*2*1 = 24. Jadi dibutuhkan 24 langkah dalam proses
penyusunannya.
L1 =
6 L2 = 8 L3 = 4
L4 = 2
|
NO
|
ORDER
|
D(L)
|
TOTAL
|
|
1
|
1,2,3,4
|
6+(6+8)+(6+8+4)+(6+8+4+2)
|
58
|
|
2
|
1,2,4,3
|
6+(6+8)+(6+8+2)+(6+8+2+4)
|
56
|
|
3
|
1,3,2,4
|
6+(6+4)+(6+4+8)+(6+4+8+2)
|
54
|
|
4
|
1,3,4,2
|
6+(6+4)+(6+4+2)+(6+4+2+8)
|
48
|
|
5
|
1,4,2,3
|
6+(6+2)+(6+2+8)+(6+2+8+4)
|
50
|
|
6
|
1,4,3,2
|
6+(6+2)+(6+2+4)+(6+2+4+8)
|
46
|
|
7
|
2,1,3,4
|
8+(8+6)+(8+6+4)+(8+6+4+2)
|
60
|
|
8
|
2,1,4,3
|
8+(8+6)+(8+6+2)+(8+6+2+4)
|
58
|
|
9
|
2,3,1,4
|
8+(8+4)+(8+4+6)+(8+4+6+2)
|
58
|
|
10
|
2,3,4,1
|
8+(8+4)+(8+4+2)+(8+4+2+6)
|
54
|
|
11
|
2,4,1,3
|
8+(8+2)+(8+2+6)+(8+2+6+4)
|
54
|
|
12
|
2,4,3,1
|
8+(8+2)+(8+2+4)+(8+2+4+6)
|
52
|
|
13
|
3,1,2,4
|
4+(4+6)+(4+6+8)+(4+6+8+2)
|
44
|
|
14
|
3,1,4,2
|
4+(4+6)+(4+6+2)+( 4+6+2+8)
|
46
|
|
15
|
3,2,1,4
|
4+(4+8)+(4+8+6)+(4+8+6+2)
|
54
|
|
16
|
3,2,4,1
|
4+(4+8)+(4+8+2)+(4+8+2+6)
|
50
|
|
17
|
3,4,1,2
|
4+(4+2)+(4+2+6)+(4+2+6+8)
|
42
|
|
18
|
3,4,2,1
|
4+(4+2)+(4+2+8)+(4+2+8+6)
|
44
|
|
19
|
4,1,2,3
|
2+(2+6)+(2+6+8)+(2+6+8+4)
|
46
|
|
20
|
4,1,3,2
|
2+(2+6)+(2+6+4)+(2+6+4+8)
|
42
|
|
21
|
4,2,1,3
|
2+(2+8)+(2+8+6)+(2+8+6+4)
|
48
|
|
22
|
4,2,3,1
|
2+(2+8)+(2+8+4)+(2+8+4+6)
|
46
|
|
23
|
4,3,1,2
|
2+(2+4)+(2+4+6)+(2+4+6+8)
|
40
|
|
24
|
4,3,2,1
|
2+(2+4)+(2+4+8)+(2+4+8+6)
|
42
|
Dari
nilai diatas dapat nilai minimal adalah…
a. Nilai kecil pertama adalah 40, yaitu untuk posisi
penyimpanan urutan ke-4 posisi ke pertama
b. Nilai terkecil kedua adalah 42 yaitu untuk posisi
penyimpanan urutan ke-3 posisi pertama
c. Nilai terkecil ketiga adalah 46 yaitu untuk posisi
penyimpanan urutan ke-1 posisi pertama
d. Nilai terkecil keempat
adalah 52 yaitu untuk posisi penyimpanan urutan ke-2 posisi pertama.
2.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).
Diketahui:
Banyak barang yang akan disimpan
= (N)
Kapasitas maksimal =(M)
Profit = (P)
Berat barang = (W)
KRITERIA GREEDY
Profit terbesar
(Pi)
N = 4 M
= 30 Kg
Nilai P (Profit) diurutkan dari
nilai yang paling besar ke nilai paling kecil:
(P1, P2, P3, P4 ) = (25,20,15,9)
Nilai W (Berat barang) diurutkan
dari nilai yang paling besar ke nilai paling kecil:
(W1, W2,
W3, W4) = (20,18,15,10)
Penyelesaian:
1. Tentukan Nilai (X1,
X2, X3, X4)
·
X1 = 1 , Karna nilai
W1 = 20 sedangkan kapasitas maksimal 30 berarti nilai W1 dapat disimpan ke
dalam tempat penyimpanan.
30 – 20 = 10 (maka kapasitas maksimal
(M) menjadi 10)
·
X2 = 5/9 ( Karena
nilai sisa kapasitas M dipresentase kan dengan nilai W2 (10/18), jika
disederhanakan hasilnya menjadi 5/9 )
·
Karna kapasitas sudah
terisi penuh oleh X1 dan X2 maka nilai X3 dan X4 menjadi 0 karna sudah tidak
tersedia lagi kapasitas untuk penyimpanan
Maka Hasilnya akan seperi ini :
Solusi ke
|
Nilai
Probabilitas
|
Fungsi
Pembatas
∑ Wi.Xi ≤ M
|
Fungsi Tujuan
∑ Pi.Xi
(Maksimum)
|
|
(W1.X1)+(W2.X2)+(W3.X3)+(W4.X4)
≤ M
|
(P1.X1)+(P2.X2)+(P3.X3)+(P4.X4)
|
|||
(X1,
X2, X3, X4)
|
||||
A
|
(1,5/9,0,0)
|
(20.1)+(18.5/9)+(15.0)+(10.0) ≤ 30
30
|
(25.1)+(20.5/9)+(15.0)+(9.0)
36.1
|
Bobot Terbesar (Wi)
N = 4 M
= 30
Nilai P (Profit) diurutkan dari
nilai yang paling kecil ke nilai paling besar:
(P4,
P3, P2, P1 ) = (9,15,20,25)
Nilai W (Berat barang) diurutkan
dari nilai yang paling kecil ke nilai paling besar:
(W4,
W3, W2, W1) = (10,15,18,20)
Penyelesaian:
1. Tentukan Nilai (X1,
X2, X3, X4)
·
X4 = 1 ( Karna nilai W4 = 10 sedangkan kapasitas
maksimal 30 berarti nilai W4 dapat disimpan ke dalam tempat penyimpanan.)
M = 30
– 10 = 20 (maka kapasitas maksimal (M) menjadi 20)
·
X3 = 1 ( karna nilai W3 adalah 15 sedangkan sisa
kapasitas ialah 20, maka nilai W3 dapat disimpan seluruhnya ke dalam tempat
penyimpanan.)
M =
20 – 15 = 5 (maka kapasitas maksimal (M) menjadi 5)
·
X2 = 5/18 Karena kapasitas M tersisa 5, sedangkan 18
didapat dari nilai W2
·
Karna kapasitas sudah terisi penuh oleh X4, X3, dan X2
maka nilai X1 menjadi 0 karna sudah
tidak tersedia lagi kapasitas untuk penyimpanan
2. Menentukan Nilai dari Fungsi
Pembatas
Mengalikan nilai W dan Nilai X dengan rumus
∑ Wi.Xi ≤ M
3. Menentukan
Nilai Fungsi Tujuan
Mengalikan nilai P dan Nilai X dengan rumus ∑
Pi.Xi (Maksimum)
Maka Hasilnya akan seperti ini:
Solusi ke
|
Nilai
Probabilitas
|
Fungsi
Pembatas
∑ Wi.Xi ≤ M
(W4.X4)+(W3.X3)+(W2.X2)+(W1.X1)
≤ M
|
Fungsi Tujuan
∑ Pi.Xi
(Maksimum)
(P4.X4)+(P3.X3)+(P2.X2)+(P1.X1)
|
(X4, X3, X2, X1)
|
|||
B
|
(1,1,5/18,0)
|
(10.1)+(15.1)+(18.5/18)+(20.0) ≤ 30
30
|
(9.1)+(15.1)+(20.5/18)+(25.0) ≤ 30
29.5
|
Pilih objek dengan nilai perbandingan profit
dengan bobot yang terbesar (Pi/Wi)
Data
yang diketahui:
(P1, P2, P3, P4 ) = (25,20,15,9)
(W1, W2, W3, W4) = (20,18,15,10)
Perbandingan profit dengan bobot
P1/ W1 = 25/20 = 1.25
P2/ W2 = 20/18 = 1.11
P3/ W3 = 15/15 = 1
P4/
W4 = 9/10 = 0.9
Susun
data sesuai kriteria:
(P1, P2, P3, P4) = (25,20,15,9)
(W1, W2, W3, W4) = (20,18,15,10)
Solusi ke
|
Nilai
Probabilitas
|
Fungsi
Pembatas
∑ Wi.Xi ≤ M
(W1.X1)+(W2.X2)+(W3.X3)+(W4.X4)
≤ M
|
Fungsi Tujuan
∑ Pi.Xi
(Maksimum)
(P1.X1)+(P2.X2)+(P3.X3)+(P4.X4)
|
(X1, X2, X3, X4)
|
|||
C
|
(1,5/9,0,0)
|
(20.1)+(18.5/9)+(15.0)+(10.0)
≤ 30
30
|
(25.1)+(20.5/9)+(15.0)+(9.0)
36.1
|
Dari 3 kriteria di atas dapat disimpulkan
bahwa fungsi tujuan yang bernilai
maximum adalah 36.1 dengan fungsi
pembatasnya adalah 30 dan nilai
probabilitasnya adalah (X1, X2,
X3, X4)= (1,5/9,0,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)
ALGORITMA GREEDY
N = 4 M = 30
(P1, P2, P3, P4 ) = (20,25,9,15)
(W1, W2, W3, W4) = (15,10,18,20)
Perbandingan profit dengan bobot
P1/ W1
= 20/15 = 1.3
P2/ W2
= 25/10 = 2.5
P3/ W3
= 9/18 = 0.5
P4/ W4 = 15/20 = 0.75
Susun data sesuai kriteria (non increasing):
(P2, P1,P4, P3) = (25,20,15,9)atau
(P1, P2,
P3,
P4) = (25,20,15,9)
(W2, W1, W4, W3) = (10,15,20,18) atau
(W1, W2,
W3, W4) = (10,15,20,18)
Jadi
(P1, P2, P3, P4) = (25,20,15,9)
(W1, W2, W3, W4) = (10,15,20,18)
(X1, X2, X3, X4)=
(1,1,1/4,0)
Berarti untuk nilai X4 = 0 , sebab nilai probabilitas
untuk objek ke-4 tidak
pernah dicari.
Fungsi Pembatas :
∑ Wi.Xi ≤ M
(W1.X1)+(W2.X2)+(W3.X3)+(W4.X4)
≤ M
(10.1)+(15.1)+(10.1/4)+(18.0) ≤
30
27.5 ≤ 30
Fungsi Tujuan :
∑ Pi.Xi = (P1.X1)+(P2.X2)+(P3.X3)+(P4.X4)
=
(25.1)+(20.1)+(15.1/4)+(9.0)
= 48.75
Tidak ada komentar:
Posting Komentar