SOAL METODE GREEDY & KUNCI JAWABAN

LATIHAN SOAL

1.Terdapat 4 buah program (N=4) yang masing-masing mempunyai panjang program (L1=10, L2=3, L3=9, L4=12), Dengan metode optimal storage ontapes problem, tentukan order yang paling optimal!

JAWABAN :

N=4 (L1=10, L2=3, L3=9, L4=12)

ORDERING           D( I )

1,2,3,4                10+(10+3)+(10+3+9)+(10+3+9+12)=79

1,3,2,4                10+(10+9)+(10+9+3)+(10+9+3+12)=85

1,4,3,2                10+(10+12)+(10+12+9)+(10+12+9+3)=88

2,3,4,1                3+(3+9)+(3+9+12)+(3+9+12+10)=73

2,1,4,3                3+(3+10)+(3+10+12)+(3+10+12+9)=84

2,4,3,1                3+(3+12)+(3+12+9)+(3+12+9+10)=76

3,4,2,1                9+(9+12)+(9+12+3)+(9+12+3+10)=88

3,2,1,4                9+(9+3)+(9+3+10)+(9+3+10+12)=77

4,3,2,1                12+(12+9)+(12+9+3)+(12+9+3+10)=91

4,1,3,2                12+(12+10)+(12+10+9)+(12+10+9+3)=99

Dari tabel tersebut, didapat susunan/ order yang optimal, sbb :

- susunan pertama untuk program ke tiga

- susunan ketiga untuk program kesatu

- susunan keempat untuk program kedua

2.-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:

W1, W2, W3 = 50 ton, 60 ton, 70 ton

P1, P2, P3 = 100 jt, 80 jt, 90 jt.

M = 80 ton

N = 3

Profit maksimal

P1= 100 jt = X1 = 1

P2= 80 jt = X2=0

P3=90 jt = X3 = 3/70

Berat minimal:

W1= 50 ton = X1 = 1

W2= 60 ton = X2 = 2/3

W3= 70 ton = X3 = 0

Pilih barang dengan menghitung perbandingan dari profit dibagi berat (Pi/Wi) yang diurut secara tidak naik, yaitu :

P1/W1 = 100/50 = 2 = karna terbesar X1=1

P2/W2 = 80/60 = 1,3 = pembatas X2 = 1/3

P3/W3 = 90/70 = 1,2 = karna terkecil X3 = 0

Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy

Profit Max        W Min                  P/W Max

P1 = 1               W1 = 1                 P1/W1 = 1

P2 = 0               W2 = 2/3              P2/W2 = 1/3

P3 = 3/70          W3 = 0                 P3/W3 = 0

Penjelasan :

Profit Max =  M = 80 ton

                      P1 = 100 jt

                     P3 = 3/70 x 90 = 3,85 / jumlah 100 jt + 3,85 =103.85 profit  

                     W1 = 50 ton                                

                            =P3 = 1/3 x 90 = 30 ton / total berat 50 + 30 = 80 ton

W min =  M = 80 ton 

                P1 = 100 jt

               profit =  2/3 x 60 = 40 / total 100 jt + 40 = 140 profit

               W1 = 50 ton                           

               W2 = 1/2 x 60 = 30 ton / total berat 50 + 30= 80 ton

 P/W max = M = 80 ton

                    P1/W1 = 100/50

                   P1 = 100 

                   P2/W2 = 1/3 x 80 = 26,6 / total 100 + 20 = 126,6 profit

                   W1= 50 ton

                   P2/W2 = 1/3 x 60 = 30 / total berat 50 + 30 = 80 ton

 harga yang paling mahal atau nilai profit maksimal adalah 140  dengan komposisi yang sama