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:
Jawab:
Fungsi tujuannya adalah mencari profit nilai maksimal.
∑ Pi Xi
Fungsi Pembatas : ∑ Wi Xi ≤ 25
Dengan nilai-nilai batasan:
- 0 ≤ Xi ≤ 1 (batas bawah = 0, batas atas = 1)
- Pi > 0
- Wi > 0
Penyelesaian Soal:
Penyelesaian Knapsack Secara Matematika (Lanjutan)
(W₁, W₂, W₃) = (20, 17, 12)
(P₁, P₂, P₃) = (27, 26, 17)
- Tentukan solusi yang mungkin: 2n = 6
- Hitung berat masing2 : 20X1 + 17X2 + 12X3 ≤ 25
- Untuk x1 = 0, x2 = 1
20*0 + 17*1 + 12X3 ≤ 25
12X3 ≤ 8
X3 = 2/3 - Untuk x1 = 1, x2 = 0
20*1 + 17*0 + 12X3 ≤ 25
12X3 ≤ 5
X3 = 5/12 - Untuk x1 = 1, x3 = 0
20*1 + 17X2 + 12*0 ≤ 25
X3 = 5/17 - Untuk x1 = 0, x3 = 1
20*0 + 17X2 + 12*1 ≤ 25
X3 = 13/17 - Untuk x2 = 1, x3 = 0
20X1 + 17*1 + 12*0 ≤ 25
X3 = 2/5 - Untuk x2 = 0, x3 = 1
20X1 + 17*0 + 12*1 ≤ 25
X3 = 13/20
- Buat Tabel kemungkinan solusi yang mungkin
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
1, 5/17, 0
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
Pi Xi = 27X1 + 26X2 + 17X3= 27(0) + 26 (1) + 17 (2/3)= 0 + 26 + 11,33= 37,33 - (W₁, W₂, W₃) = (20, 17, 12)(P₁, P₂, P₃) = (27, 26, 17)Kesimpulan : komposisi dari ketiga barang yang dapattermuat dalam ransel dgn profit maksimal 37,33 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=2/3) = 8 kg● Total Max Kapasitas Knapsack adalah 25 kg
Kelompok 3 :
Terima kasih telah datang ke Blog Kami..
Jangan Lupa Tinggalkan Like & Komen..
Jangan Lupa Tinggalkan Like & Komen..
Tidak ada komentar:
Posting Komentar