ltm 13

PERTEMUAN 13

METODA GREEDY 2

1.      Terdapat sebuah kapal dengan kapasitas 180 Ton, Akan memuat 6 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. Beras 50 Ton dengan harga 150 Juta, Terigu 20 ton dengan harga 40 Juta, Minyak goring 60 Ton dengan harga 200 Juta. Dengan metoda Algoritma Greedy Tentukan barang apa saja yang dimuat truk dengan harga yang paling mahal

2.       Apa yang menjadi persyaratan traveling salesman, agar perjalannya efektif dan efisien

3.      Jelaskan manfaat pengguanaan Minimum Spanning Tree

4.      Jelaskan manfaat penggunaan Shortest Path Problem

Jawab:

 1.      Diketahui M=180

                  N = 6 buah

      (Berat   Wi ) W1 W2 W3 W4  W5 W6    = 50, 60, 70,  50,  20,  60

     (Profit  Pi )  P1 P2 P3  P4  P5  P6         = 100, 80, 90, 150 , 40, 200      

     Gula Pasir          => P1 /W1 => 100/50  = 2                   = menjadi urutan 4

     Gula Merah        => P2 /W2 =>  80/60   = 1,3                = menjadi urutan 5

     Gula Batu                      => P3 /W3 =>  90/70  = 1,28    = menjadi urutan 6

     Beras                  => P4 /W4 => 150/50 = 3                       = menjadi urutan 2

     Terigu                 => P5 /W5 =>  40/20  = 2                       = menjadi urutan 3

     Minyak goreng  => P6 /W6 => 200/60 = 3,3                 = menjadi urutan 1

     Menjadi :

    (Berat   Wi ) W1 W2 W3 W4  W5 W6    = 60,50,20,50,60,70

    (Profit  Pi )  P1 P2 P3  P4  P5  P6           = 200,150,40,100,80,90

2.    Syarat utama yang menjadi persyaratan metode Traveling salesman adalah

Menentukan WAKTU perjalanan seorang salesman seminimal mungkin

3.    Manfaat penggunaan Minimum Spanning Tree adalah untuk memilih ruas suatu Graph dengan biaya seminimal mungkin. 

·         Setiap ruas pada graph harus terhubung (conected)

·         Setiap ruas pada graph harus mempunyai nilai (label graph)

·         Setiap ruas pada graph tidak mempunyai arah (graph tidak berarah)

4.    Manfaat penggunaan Shortest Path Problem adalah untuk menghitung jalur Terpendek dari sebuah graph berarah

ü  Setiap ruas pada graph harus mempunyai nilai (label graph)

ü  Setiap ruas pada graph tidak harus terhubung (unconected)

ü   Setiap ruas pada graph harus mempunyai arah (graph berarah)