Tugas Pertemuan 12 | Logika dan Algoritma ( Metode Greedy )
Tugas Pertemuan 12
Logika dan Algoritma ( Metode Greedy )
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 :
1. Secara Matematika
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)
Penyelesaian soal:
Fungsi tujuannya adalah mencari profit nilai maksimal. ∑ PiXi
Fungsi Pembatas : ∑ Wi Xi <= 20
Dengan nilai-nilai batasan:
0<=Xi<=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)
- Tentukan solusi yang mungkin: 2n = 6
- Hitung berat masing2 : 20X1+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=020.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.1 <= 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 + 0 + 12 <= 25
20X1 <= 25-12
20X1 <= 13
X1 = 13/20
6. Untuk x2=1, x3=0
20X1 + 17.1 + 12.0 <= 25
20X1 + 17 + 0 <= 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,33 |
|
2 |
1,0,5/12 |
25 |
34,08 |
|
3 |
0,13/17,1 |
25 |
36,88 |
|
4 |
1,5/17,0 |
25 |
34,64 |
|
5 |
13/20,0,1 |
25 |
34,55 |
|
6 |
2/5,1,0 |
25 |
36,8 |
Nilai profit maksimalnya ( diambil nilai yg paling besar ) :
Pi Xi = 25X1 + 26X2 + 17X3
= 25(0) + 26(1) + 17(2/3)
= 0 + 26 + 11,33
= 37,3
Kesimpulan Solusi 1:
Komposisi dari ketiga barang yang dapat termuat dalam ransel dgn profit maksimal 37,28 adalah:
● Barang jenis 1 tidak dimuat (X1 = 0) 0 Kg
● Barang jenis 2 dimuat semuanya (X2 = 1) 17 Kg
● Barang jenis 3 dimuat dua pertiga (X3 = 2/3) 8 Kg
● Total Max Kapasitas Knapsack adalah 25 Kg
2. Peyelesaian secara kriteria Greedy
Diketahui bahwa kapasitas M = 20 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 = 2/17, dihitung dengan Fungsi Pembatas
P3 = 17 → X3 = 0, dimisalkan sebagai batas bawah nilai
Rumus fungsi pembatas :
20.0 + 17X2 + 12.1 <= 25
0 + 17X2 + 12 <= 25
17X2 <= 25-12
17X2 <= 13
X2 = 13/17Pilih barang dengan Berat Minimal
W1 = 20 → X1 = 0, sebagai batas bawah
W2 = 17 → X2 = 2/3,dihitung dgn Fungsi Pembatas
W3 = 12 →X3 = 1, sebagai batas atas
Rumus fungsi pembatasnya :
20.1 + 17X2 + 12.0 <= 25
20 + 17X2 + 0 <= 25
17X2 <= 25 – 20
17X2 <= 5
X2 = 5/17
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
Ø Rumus fungsi pembatasnya :
W1.X1 + W2.X2 + W3.X3 ≤ M
(20.0) + (17.1) + (12.X3) ≤ 25
17 + 12X3 ≤ 25
12X3 ≤ 25-17
12X3 ≤ 8
X3 ≤ 8/12
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,5/17,0 |
25 |
34,64 |
|
Pi/Wi Max |
0,1,2/3 |
25 |
37,33 |
Nilai profit diambil yg paling besar :
Pi / Wi max = 27(0) + 26(1) + 17(2/3)
= 0 + 26 + 11,33
= 37,33
Nilai profit maksimal = 37,3 dengan komposisi yang sama.
Komentar
Posting Komentar