Examkin

Soru

Zorluk: OrtaMinimum Maliyetli Akış Problemi

Bir kamu kurumunun lojistik şebekesinde 1 numaralı merkezden (kaynak) 4 numaralı merkeze (varış) toplam 1010 birimlik ürün sevkiyatı yapılacaktır. Şebekede yer alan yayların birim taşıma maliyetleri (cijc_{ij}) ve kapasiteleri (uiju_{ij}) aşağıdaki tabloda sunulmuştur. 1 numaralı düğümün arzı 1010 birim, 4 numaralı düğümün talebi 1010 birim olup diğer düğümler aktarma merkezidir.

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

Buna göre, bu sevkiyatın en düşük toplam maliyetle gerçekleştirilmesi durumunda oluşacak toplam maliyet kaç birim olur?

  1. A
    60
  2. 73Cevap
  3. C
    75
  4. D
    78
  5. E
    84

Cevap

Optimal sevkiyat planına göre minimum toplam maliyet 73 birimdir.
Minimum maliyetli akış prensibine göre, 10 birimlik ürünün 5 birimi en ucuz güzergah olan 1-2-3-4 üzerinden (maliyet 30), 2 birimi bir sonraki seçenek 1-3-4 üzerinden (maliyet 16) ve kalan 3 birimi 1-2-4 üzerinden (maliyet 27) gönderildiğinde toplam 73 birimlik en düşük maliyete ulaşılır.

Adım Adım Çözüm

1
Şebekedeki olası yolların maliyetlerini hesaplayınız.
1-2-3-4 yolu: 2+1+3=62+1+3=6; 1-3-4 yolu: 5+3=85+3=8; 1-2-4 yolu: 2+7=92+7=9.
En düşük maliyetli akışı sağlamak için en ucuz güzergahlar önceliklendirilmelidir.
2
En ucuz güzergah olan 1-2-3-4 yoluna kapasite kısıtları dahilinde akış atayınız.
Kapasite: min⁡(u12=8,u23=5,u34=7)=5\min(u_{12}=8, u_{23}=5, u_{34}=7) = 5 birim. Akış: x12=5,x23=5,x34=5x_{12}=5, x_{23}=5, x_{34}=5. Maliyet: 5×6=305 \times 6 = 30.
Sistemdeki en ekonomik yolun kapasitesi 5 birimle sınırlıdır.
3
Kalan 5 birimlik akış için bir sonraki en ucuz yol olan 1-3-4 güzergahını değerlendiriniz.
Yay (3, 4) üzerinde kalan kapasite 7−5=27 - 5 = 2 birimdir. Akış: x13=2,x34=2x_{13}=2, x_{34}=2. Maliyet: 2×8=162 \times 8 = 16.
1-3-4 yolu, 1-2-4 yoluna göre daha ucuzdur ancak (3, 4) yayının kapasitesi dolmak üzeredir.
4
Kalan 3 birimlik akışı son seçenek olan 1-2-4 güzergahına atayınız.
Yay (1, 2) kalan kapasitesi 8−5=38 - 5 = 3; Yay (2, 4) kapasitesi 6. Akış: x12=3,x24=3x_{12}=3, x_{24}=3. Maliyet: 3×9=273 \times 9 = 27.
Toplam 10 birimlik arzın tamamı sevkedilmiş olur.
5
Tüm adımlardaki maliyetleri toplayınız.
30+16+27=7330 + 16 + 27 = 73.
Şebeke üzerindeki toplam minimum maliyet bu şekilde hesaplanır.

Anahtar Kavram

Minimum maliyetli akış problemlerinde, akışın kapasite kısıtlarını (u_ij) ihlal etmeden en düşük birim maliyetli (c_ij) yaylar üzerinden yönlendirilmesi esastır.
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru