LTM Dasar Pemograman Metode Greedy

 PERTEMUAN 12

METODE GREEDY 1

 

A.   Pertanyaan

1.    Jelaskan 5 manfaat penggunaan metode Greedy?

2.    Terdapat  7 buah program (N=7) yang masing-masing mempunyai panjang program (L1=10, L2=3, L3=9, L4=12, L5=20, L6=7, L7=11), dengan metode Optimal  Storage Ontapes Problem. Tentukan order yang paling optimal?

3.    Terdapat sebuah truk dengan kapasitas 80 ton. Akan memuat 3 buah barang masing masing adalah gula pasir 50 ton dengan harga 100 juta, gula merah 60 ton dengan harga 80  juta dan gula batu 70 ton dengan harga 90 juta. Dengan metode Greedy tentukan barang apa saja yang dimuat truk dengan harga yang paling mahal?

4.    Dalam metode greedy jelaskan apa yang menjadi fungsi tujuan dan fungsi pembatas?

B.   Jawaban

1.    5 manfaat Metode Greedy :

a)    Mendapatkan solusi yang optimal dari permasalahan

b)   Optimal on tape storage problem

c)    Optimal on tape storage problem

d)   Knapsack problem

e)    Minimum spanning tree problem

f)     Shortest path problem

2.    Jawab:

2314567 = 3 + (3+9) + (3+9+10) + (3+9+10+12) + (3+9+10+12+20) + (3+9+10+12+20+7) + (3+9+10+12+20+7+11) = 258

3.    Kapasitas ransel = 80 ton

Banyak barang =  3

Berat (W)

W1, W2, W3  = 50, 60, 70

Profit (P)

P1, P2, P3 = 100, 80, 90

Tentukan  barang apa saja yang dimuat ditruk dengan harga yang paling mahal!

Jawab :

P1 = 100                (80-50)=30          X1 = 1

(50.1) + (60.0) + (70.30/70) = P2 = 80

X3 =0     50 + 0 + 30= 80     Pi Maximal

P3 = 90 (30/70)                    X2 = 30/70

W1 = 50 (80-50) =30            X1 = 1                   

W2 = 60 (30/60) = ½            X2 = ½         Wi Minimum

W3 = 70                                 X3 = 0

100/50 = 2 (80-50)=30                  X1 = 1

80/60 = 4/3 (30/60) = ½               X2 = ½

Pi . Wi

90/70 = 1,29              X3 = 0

Pi.?Xi

(100.1) + (80.0) + (90.30/70) = 100 + 0 + 38,5 = 138,5

(50.1) + (60.1/2) + (70.0) = 50 + 30 + 0 = 80

(100.1) + (80.1/2) + (90.0) = 100 + 40 + 0 = 140

4.   Fungsi Tujuan = fungsi yang menjadi penyelesaian permasalahan dengan mendapatkan solusi yang optimal.

Fungsi Pembatas = memberikan batas maksimal dari setiap obyek untuk dapat dimuat sehingga kapasitasnya tidak melebihi dari jumlah maksimal daya tampung.