Model jaringan

Contoh kasus

• Seorang pengusaha yang bergerak dibidang pemasangan kabel pada suatu daerah tertentu , memperoleh pesanan untuk memasang kabel pada enam gardu listrik yang mewakili enam kota, mengingat akhir akhir ini semua biaya peralatan naik cukup meningkat , maka dia berusaha agar pemasangan kabel tersebut ditekan dengan biaya semurah mungkin , dengan cara pemasangan kabel cukup satu jalur saja tanpa ada tumpah tindih antara satu kabel dengan kabel lain tetapi seluruh kota terhubung . jika rancangan tersebut dapat dilihat pada gambar berikut lengkap dengan kebutuhan kabel yang diperlukan ( km).Tentukanlah berapa total biaya yang dibutuhkan jika 1 km kabel adalah Rp 1000.000,-dibutuhkan menghubungkan keenam kota tersebut

Gambar rancangan

• 1

• 2

• 4

• 3

• 6

• 5

• 1

• 3km

• 4

• 6km

• 9km

• 7

• 5

• 5

• 10

• 8

• 3

Algorithma rute terdekat

• Algorithma Asiklis (tanpa loop)
• Uj = Jarak terdekat dari node 1 ke node 2
• Dimana U1 = 0,Nilai Uj ,j = 1,2,3 …..n dihitung secara rekursif dengan rumus berikut:
• Uj = minimum yang ke i dari Ui ditambah dij
• Algorithma Siklis (dengan loop)
• Lakukan evaluasi dari label tetap ke node node yang lain dengan jarak terdekat
• Tentukan node tetap berikutnya dari hasil evaluasi yang berpedoman pada jarak terdekat
• Lakukan proses satu dan dua secara terus menerus sehingga diperoleh jarak terdekat

Contoh Asiklis:

• Tentukanlah jarak terdekat dari node satu ke node tujuh dari gambar berikut:

• 1

• 2

• 5

• 3

• 4

• 6

• 7

• 2km

• 5km

• 10km

• 4

• 3

• 1km

• 11

• 7

• 8

• 6

• 9

Contoh Siklis

• Carilah jarak terdekat antar node berikut

• 1

• 2

• 3

• 4

• 5

• 30

• 100

• 20

• 10

• 15

• 50

• 60

Aliran maksimum

• Langkah langkah
• Tentukan jalur yang mungkin dicapai dari node awal ke node akhir
• Tentukan minimasi aliran yang dapat dialirkan dari node awal ke node akhir
• Lakukan evaluasi dari langkah satu dan dua secara terus menerus hingga diperoleh arus maksimal

Contoh:

• A

• B

• D

• C

• F

• E

• 3

• 2

• 10

• 0

• 3

• 2

• 0

• 1

• 1

• 1

• 2

• 1

• 2

• 1

• 0

• 1

• 6

• 1

Download 161.5 Kb.

Share with your friends: