Examkin

Soru

Zorluk: OrtaMinimum 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. 138Cevap
  4. D
    140
  5. E
    145

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

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.
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru