Tugas Pertemuan Ke 13

 

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 Kriteria Greedy

(P1 , P2 , P3 ) = (27, 26, 17)

(W1, W2, W3) = (20, 17, 12)

Pilih barang dengan Nilai Profit Maksimal

P1 = 27 → X1 =1 , dimisalkan sebagai atas atas nilai

P2 = 26 → X2 =5/17 , dihitung dengan Fungsi Pembatas

P3 = 17 → X3 = 0, dimisalkan sebagai batas bawah nilai

 

Wi Xi ≤ M

=20.x1+17.x2+12.x3 ≤ 25

=20.1+17x2+12.0 ≤ 25

=20+17x2+0 ≤ 25

=17x2  ≤ 25-20

=17x2  ≤ 5

=x2  ≤ 5/17

Pilih barang dengan Berat Minimal

W1 = 20 → X1 = 0 sebagai batas bawah

W2 = 17 → X2 =13/17 dihitung dgn Fungsi Pembatas

W3 = 12 → X3 = 1 sebagai batas atas

 

Wi Xi ≤ M

=20.x1+17.x2+12.x3 ≤ 25

=20.0+17x2+12.1 ≤25

=0+17x2+12 ≤25

=17x2 ≤ 25-12

=17x2 ≤ 13

=x2 ≤ 13/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 = 1/2

Dibuatkan tabel berdasarkan elemen dr ke-3 kriteria metode

Greedy :

(X1,X2,X3)	∑ PiXi
(1 , 5/17 , 0) (0, 13/17 , 1) (0 , 1 , 1/2 )	(27.1)+(26.(5/17))+17.0=34,6 (27.0)+(26.(13/17))+17.1=36,8 (27.0)+(26.1)+(17.(1/2))=34,5

Solusi Ke	(X1,X2,X3)	∑ WiXi	∑ PiXi
Pi max	1, 1/5,0	25	34,6
Wi Min	0, 13/17,1	25	36,8
Pi/Wi Max	0,1,1/2	25	34,5

 

Nilai profit maksimal = 36,8 dengan komposisi yang sama

 

 

Solusinya adalah elemen dengan nilai ∑ PiXi  yang terbesar adalah

 

(X1,X2,X3) = (0 , 13/17 , 1 )

 

Sehingga Komposisi barang yang di muat di dalam ransel adalah :

(W1, W2, W3) = (20, 17, 12)

Ø Barang ke-1 tidak dimuat ke dalam ransel = 0

Ø Barang ke-2 dimuat sebanyak 13/17 bangian = (17.(13/17)) = 13

Ø Barang ke-3 dimuat sebanyak 1 bagian     = 12

Total     = 25