Examkin

Question

Difficulty: MediumMinimum Maliyetli Akış Problemi

Bir kamu dağıtım şebekesinde, 1 numaralı düğümden (kaynak) 5 numaralı düğüme (varış) toplam 15 birimlik ürün sevkiyatı yapılacaktır. Şebekedeki diğer düğümler (2, 3, 4) aktarma merkezleridir. Düğümler arasındaki yayların birim akış maliyetleri (cijc_{ij}) ve kapasiteleri (uiju_{ij}) aşağıdaki tabloda verilmiştir:

Yay (i, j)Birim Maliyet (cijc_{ij})Kapasite (uiju_{ij})
(1, 2)410
(1, 3)610
(2, 3)25
(2, 4)58
(3, 5)312
(4, 5)110

Tüm talebin karşılanması ve toplam maliyetin enküçüklenmesi hedeflendiğine göre, bu sevkiyatın minimum maliyeti kaç birimdir?

  1. A
    132
  2. B
    135
  3. 138Answer
  4. D
    140
  5. E
    145

Answer

Toplam sevkiyatın minimum maliyeti 138 birimdir.
Şebekede kaynaktan varışa giden en ucuz güzergahların birim maliyeti 9'dur (1-2-3-5 ve 1-3-5). Ancak her iki güzergah da (3, 5) yayını ortak kullanmaktadır ve bu yayın kapasitesi 12 birimdir. Bu nedenle bu güzergahlardan toplamda en fazla 12 birim sevkiyat yapılabilir. Toplam 15 birimlik talebin kalan 3 birimi, bir sonraki en düşük maliyetli (birim maliyeti 10 olan) 1-2-4-5 güzergahı ile gönderilmelidir. Sonuç olarak toplam maliyet (12×9)+(3×10)=138(12 \times 9) + (3 \times 10) = 138 olur.

Step-by-Step Solution

1
Kaynaktan (1) varışa (5) giden tüm alternatif yolları ve bu yolların birim maliyetlerini hesaplayın.
Yol 1: 1-2-3-5 maliyeti 4+2+3=94+2+3=9; Yol 2: 1-3-5 maliyeti 6+3=96+3=9; Yol 3: 1-2-4-5 maliyeti 4+5+1=104+5+1=10.
En düşük maliyetli güzergahları belirlemek için şebeke üzerindeki tüm akış yolları analiz edilmelidir.
2
Yol kapasitelerini ve ortak yay kısıtlarını kontrol edin.
En ucuz iki yol (Yol 1 ve Yol 2) (3, 5) yayını kullanmaktadır. Bu yayın kapasitesi u35=12u_{35} = 12 birim ile sınırlıdır.
Şebeke problemlerinde toplam akış, yayların kapasite kısıtlarını (xij≤uijx_{ij} \leq u_{ij}) aşamaz.
3
Birimleri en düşük maliyetli yollardan başlayarak dağıtın.
12 birim maliyeti 9 olan Yol 1 ve Yol 2 üzerinden gönderilir. Kalan 3 birim (15−12=315 - 12 = 3) maliyeti 10 olan Yol 3 ile gönderilir.
Kapasite dolduğunda kalan talep, maliyeti en düşük olan bir sonraki alternatif güzergaha yönlendirilir.
4
Toplam maliyet fonksiyonunun değerini hesaplayın.
Toplam Maliyet = (12×9)+(3×10)=108+30=138(12 \times 9) + (3 \times 10) = 108 + 30 = 138 birim.
Optimal akış miktarları ile ilgili güzergahların birim maliyetlerinin toplamı minimum maliyeti verir.

Key Concept

Minimum maliyetli akış probleminde, kapasite kısıtları bir 'darboğaz' (bottleneck) oluşturduğunda, akışın bir kısmı daha yüksek maliyetli alternatif yollara kaydırılır.
Rate this question

Topics

Minimum Maliyetli Akış Problemi

More questions from this topic