Tugas Pertemuan Ke- 12
Logika Algoritma
Tugas Mandiri
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
Fungsi tujuannya adalah mencari profit nilai maksimal. ∑ PiXi
Fungsi Pembatas : ∑ Wi Xi <= 25
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)
1. Tentukan solusi yang mungkin: 2n = 6
2. Hitung berat masing2 : 20X1+17X2+12X3 <= 20
- 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
- Untuk x1=1, x2=0
20.1+17.0+12X3 <= 25
20 + 0 + 12X3 <= 25
12X3 <= 25-20
12X3 <= 5
X3 = 5/12
- Untuk x1=0, x3=1
20.0+17X2+12.1 <= 25
0 + 17X2 + 12 <= 25
17X2 <= 25-12
17X2 <= 13
X2 = 13/17
- Untuk x1=1, x3=0
20.1+17X2+12.0 <= 25
20 + 17X2 + 0 <= 25
17X2 <= 25-20
17X2<=5
X2=5/17
- Untuk x2=0, x3=1
20X1+17.0+12.1 <= 25
20X1 + 0 + 12 <= 25
20X1 <= 25-12
20X1 <= 13
X1 = 13/20
- Untuk x2=1, x3=0
20X1+17.1+12.0 <= 25
20X1 + 17+0<= 25
20X1<= 25-17
20X1 <= 8
X1 = 8/20
Tabel kemungkinan solusi
(W1, W2, W3) = (20, 17, 12)
(P1, P2, P3) = (27, 26, 17)
Solusi Ke
X1, X2ss, X3
Wi Xi
Pi Xi
1
0,1,2/3
25
37.33
2
1,0,5/17
25
34.0
3
1,5/17,1
25
34.36
4
0,13/17,1
25
36.88
5
2/5,1,0
25
36,8
6
13/20.0.1
25
34,55
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 ransel dgn 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 separuh (X3 = 1⁄2) 8 Kg
● Total Max Kapasitas Knapsack adalah 25 Kg
Komentar
Posting Komentar
Kritikan dan Saran. Terimakasih :)