TUGAS PERTEMUAN 12 LOGIKA DAN ALGORITMA (Metode Greedy)
TUGAS 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 : 20Kg
Barang
Kedua : 17Kg
Barang
Ketiga : 12Kg
Masing-masing
barang memiliki profit (keuntungan):
Barang
Pertama : 27
Barang
Kedua : 26
Barang
Ketiga: 17
Tentukan
Hasil Profit Maksimalnya ?
Jawab
: Diketahui bahwa Kapasitas M = 25Kg 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 <= 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 masing-masing : 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=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.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 + 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,0 |
25 |
34,64 |
|
5 |
13/20,0,1 |
25 |
34,55 |
|
6 |
2/5,1,0 |
25 |
36,8 |
Contoh Solusi Pertama 1. :
Pi Xi =
27X1 + 26X2 + 17X3
27(0) + 26(1) + 17(2/3)
0 + 26 + 11,3 = 37,3
Kesimpulan solusi pertama 1. :
Komposisi dari ketiga barang yang dapat termuat
dalam ransel dengan profit maksimal 37,3 adalah :
Barang jenis 1 tidak dimuat (X1 = 0) 0Kg
Barang jenis 2 dimaut semua (X2 = 1) 17Kg
Barang jenis 3 dua pertiga (X3 = 2/3) 8Kg
Total Kapasitas Knapsack adalah 25Kg
2. Peyelesaian secara kriteria Greedy
Contohnya :
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,5/17,0 |
25 |
34,64 |
|
Pi/Wi Max |
0,1,2/3 |
25 |
37,3 |
Nilai profit maksimal = 37,3 dengan komposisi yang sama
-------------- TRIMAKASIH--------------
Komentar
Posting Komentar