Examkin

Question

Difficulty: MediumMinimum Maliyetli Akış Problemi

Dört düğümden (1, 2, 3, 4) oluşan bir şebeke modelinde düğümler arası birim akış maliyetleri (cijc_{ij}) ve yay kapasiteleri (uiju_{ij}) aşağıdaki tabloda sunulmuştur:

Yay (i, j)Birim Maliyet (cijc_{ij})Kapasite (uiju_{ij})
(1, 2)38
(1, 3)56
(2, 3)15
(2, 4)76
(3, 4)210

Şebekede düğüm 1'in arzı 10 birim (b1=10b_1 = 10) ve düğüm 4'ün talebi 10 birimdir (b4=−10b_4 = -10). Düğüm 2 ve 3 ise aktarma (transshipment) düğümleridir.

Buna göre, toplam 10 birimlik akışın hedeflenen düğüme ulaştırılması için gereken toplam minimum maliyet kaç birimdir?

  1. A
    60
  2. 65Answer
  3. C
    70
  4. D
    80
  5. E
    82

Answer

Toplam minimum maliyet 65 birimdir.
65 birimlik sonuç, en düşük birim maliyete sahip 1-2-3-4 rotasından kapasite sınırı olan 5 birimin, ardından kalan 5 birimin ise bir sonraki en ucuz seçenek olan 1-3-4 rotasından geçirilmesiyle (5*6 + 5*7) elde edilir.

Step-by-Step Solution

1
Şebekedeki olası rotaları ve birim maliyetlerini belirle.
1-2-3-4: 3+1+2=6; 1-3-4: 5+2=7; 1-2-4: 3+7=10.
Minimum maliyetli akış için en ucuz yolların önceliklendirilmesi gerekir.
2
En ucuz yol olan 1-2-3-4 rotasının kapasitesini kontrol et ve akışı ata.
Kapasite = min(u12=8, u23=5, u34=10) = 5 birim. Maliyet: 5 x 6 = 30.
(2, 3) yayının kapasitesi 5 birim olduğu için bu rotadan en fazla 5 birim geçebilir.
3
Kalan 5 birimlik akış için bir sonraki en ucuz yolu belirle ve kapasiteyi kontrol et.
Sıradaki yol 1-3-4 (Maliyet: 7). Kapasite = min(u13=6, u34_kalan=10-5=5) = 5 birim. Maliyet: 5 x 7 = 35.
(3, 4) yayının kalan kapasitesi ve (1, 3) yayının kapasitesi 5 birime izin vermektedir.
4
Toplam maliyeti hesapla.
30 + 35 = 65.
Tüm arz (10 birim) en ekonomik rotalar üzerinden dağıtılmıştır.

Key Concept

Minimum maliyetli akış problemlerinde, akışın birim maliyeti en düşük olan yollar üzerinden kapasite kısıtları dahilinde atanması temel esastır.
Rate this question

Topics

Minimum Maliyetli Akış Problemi

More questions from this topic