LTM Pertemuan 12

1.       Jelaskan 5 manfaat penggunaan metode Greedy?

Jawaban:

1.       Mendapatkan solusi yang optimal dari permasalahan

2.       Optimal on tape storage problem

3.       Knapsack problem

4.       Minimum spanning tree problem

5.       Shortest path problem

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?

Jawaban:

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.       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?

Jawaban:

Kapasitas ransel = 80 ton

Banyak barang =  3

Berat (W)

W_1, W_2, W₃  = 50, 60, 70

Profit (P)

P₁, P₂, P₃ = 100, 80, 90

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

Jawab :

P₁ = 100                (80-50)=30          X₁ = 1                     (50.1) + (60.0) + (70.30/70) =      

p₂ = 80                                   X₃ = 0                       50   +      0    +         30        =  80  P_i Maximal

P₃ = 90 (30/70)                   X₂ = 30/70

W₁ = 50 (80-50) =30         X₁ = 1                    

W₂ = 60 (30/60) = 1/2     X₂ = 1/2                W_i Minimum

W₃ = 70                                 X₃ = 0

100/50 = 2 (80-50)=30                     X₁ = 1

80/60 = 4/3 (30/60) = 1/2              X₂ = 1/2                                P_i . W_i

90/70 = 1,29                                        X₃ = 0

P_i.∑X_i

(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.       Dalam metode greedy jelaskan apa yang menjadi fungsi tujuan dan fungsi pembatas?

Jawaban:

          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.