Logika Dan Algoritma (Metode Greedy)
soal :
Diketahui
bahwa ada 3 barang disimpan di tempat dengan kapasitas maksimal sebesar 25 Kg.
Berat masing‐masing barang tersebut adalah:
Barang
pertama :
20 Kg
Barang
kedua :
17 Kg
Barang
ketiga :
12 Kg
Masing-masing
barang memiliki profit (keuntungan):
Barang
pertama :
27
Barang
kedua :
26
Barang
ketiga :
17
Tentukan
berapa profit maksimalnya?
jawab :
Diketahui
bahwa kapasitas M : 25 Kg
Dengan
jumlah barang n=3
berat W1
,W2,W3= 20, 17, 12
nilai P1,P2,P3
= 27, 26, 17
penyelesaian
soal =
fungsi
tujuan nya adalah mencari profit nilai maksimal P1 ,X1
fungsi
pembatasan = W1, X1 <=
M
dengan
nilai batasan 0 <= X1 <=
1 (batas bawah=0, batas atas=1)
Pi => 0
Wi => 0
Penyelesaian Soal:
(W1, W2, W3) = (20, 17, 12)
(P1, P2, P3) = (27, 26,17)
1. Tentukan solusi yang mungkin : 2n=6
2. Hitung berat masing2 : 20 X1+17X2+12X3 <= 25
1. untuk X1 = 0, X2 = 1
20.0+17.1+12X3
<= 25
0+17+12X3 <=
25
12X3 <= 25-17
12X3 <= 8
X3 = 8/12 =2/3
2. Untuk X1 = 1, X2
= 0
20.1+17.0+12X3
<= 25
20+0+12X3 <=
25
12X3 <= 25-20
12X3 <= 5
X3 = 5/12
3. Untuk X1 = 0, X3 = 1
20.0+.17X2+12.0
<= 25
0+17X2+12 <=
25
17X2 <= 25-12
17X2 <= 13
X2 =13/17
4.Untuk
X1=1, X3=0
20.1+17X2+12.0 <= 25
20 + 17X2 + 0 <= 25
17X2 <= 25/20
17X2 <= 5
X2 = 5/17
5.Untuk
X2=0, X3=1
20X1+17.0+12.1 <= 25
20X1 + 12 <= 25
20X1 <= 25-12
20X1 <= 13
X1 = 13/20
6.Untuk X2=1, X3=0
20X1+17.1+12.0 <= 25
20X1 + 17 <= 25
20X1 <= 25-17
20X1 <= 8
X1 = 8/20 = 2/5
Tabel kemungkinan solusi
(W1, W2, W3)
= (20, 17, 12)
(P1, P2, P3) =
(27, 26, 17)
|
Solusi Ke |
X1, X2, X3 |
Wi Xi |
Pi Xi |
|
1 |
0,1,2/3 |
25 |
37,3 |
|
2 |
1,0,5/12 |
25 |
34,08 |
|
3 |
0,13/17,1 |
25 |
36,88 |
|
4 |
1,5/17,1 |
25 |
34,64 |
|
5 |
13/20,0,1 |
25 |
34,55 |
|
6 |
2/5,1,0 |
25 |
36,8 |
Contoh
solusi 1 :
pi xi =
27X1 + 26X2 + 17X3
27(0) + 26(1) + 17(2/3)
0 + 26 + 11,3 = 37, 3
Kesimpulan
solusi 1 :
Komposisi
dari ketiga barang yang dapat termuat dalam rangsel dengan profit maksimal 37,
3 adalah..
barang
jenis 1 tidak dimuat (X1 = 0) 0 Kg
barang
jenis 2 dimuat semua (X2 = 1) 17
Kg
barang
jenis 3 dimuat sepertiga (x3 = 2/3) 8 Kg
total max
kapasitas knapsack adalah 25
Kg
2. Peyelesaian secara kriteria Greedy
Contoh :
Diketahui
bahwa kapasitas M = 25 Kg Dengan jumlah barang n=3
Berat Wi masing-masing barang (W1, W2, W3) = (20, 17, 12)
Nilai Pi
masing-masing barang (P1, P2, P3) = (27, 26, 17)
Pilih barang dengan Nilai Profit Maksimal
P1 = 27 → X1 = 1, dimisalkan sebagai atas nilai
P2 = 26 → X2 =13/17, dihitung dengan Fungsi Pembatas
P3 = 17 → X3 = 0, dimisalkan sebagai batas bawah nilai
Pilih barang dengan Berat Minimal
W1 = 20 → X1 = 1, sebagai batas bawah
W2 = 17 → X2 = 5/17 ,dihitung dgn Fungsi Pembatas
W3 = 12 →X3 = 0, sebagai batas atas
Pilih barang dengan menghitung perbandingan yang terbesar dari Profit
dibagi Berat (Pi/Wi) yang diurut secara tidak naik, yaitu :
P1/W1 = 27/20= 1.35 → karena
terkecil maka X1 = 0
P2/W2 = 26/17 = 1.52 → karena terbesar maka X2 = 1
P3/W3 = 17/12 = 1.41 → dengan Fungsi pembatas X3 = 2/3
Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy.
(W1, W2, W3) = (20,17,12)
(P1, P2, P3) = (27,26,17)
|
Solusi ke |
X1,X2,X3 |
WiXi |
PiXi |
|
Pi Max |
0,13/17,1 |
25 |
36, 88 |
|
Wi Min |
1,2/17,0 |
25 |
34, 64 |
|
Pi/Wi Max |
0,1,2/3 |
25 |
37, 3 |
nilai profit maksimal = 37,3 dengan komposisi yang sama....
Komentar
Posting Komentar