Examkin

Soru

Zorluk: OrtaMinimum Maliyetli Akış Problemi

Bir dağıtım şebekesinde 1 numaralı merkezden (arz kaynağı) 4 numaralı merkeze (talep noktası) toplam 10 birimlik ürün sevkiyatı yapılacaktır. Şebekedeki yaylara (yollar) ait birim akış maliyetleri (cijc_{ij}), kapasite kısıtları (uiju_{ij}) ve düğümlerin arz/talep değerleri (bib_i) aşağıdaki tabloda verilmiştir:

Yay (i,j)(i, j)Birim Maliyet (cijc_{ij})Kapasite (uiju_{ij})
(1, 2)36
(1, 3)58
(2, 3)14
(2, 4)75
(3, 4)210

Düğümlerin arz/talep dengesi b1=10,b2=0,b3=0,b4=−10b_1 = 10, b_2 = 0, b_3 = 0, b_4 = -10 şeklinde olduğuna göre, bu şebeke için toplam minimum akış maliyeti kaç birimdir?

  1. 66Cevap
  2. B
    68
  3. C
    76
  4. D
    85
  5. E
    60

Cevap

Şebeke üzerindeki kapasite kısıtları dahilinde yapılan en uygun akış dağılımı ile toplam minimum maliyet 66 birimdir.
En düşük birim maliyete sahip rota 1-2-3-4 (maliyet=6) yoludur ve bu yolun kapasitesi 4 birim ile sınırlıdır. Kalan 6 birimlik akış, bir sonraki en ucuz yol olan 1-3-4 (maliyet=7) rotasından gönderildiğinde toplam maliyet 4×6+6×7=664 \times 6 + 6 \times 7 = 66 olarak bulunur. Bu dağılım tüm kapasite ve arz/talep kısıtlarını sağlamaktadır.

Adım Adım Çözüm

1
Olası yolların toplam birim maliyetlerini hesaplayın.
Yol 1: 1-2-3-4 (Maliyet: 3+1+2=6), Yol 2: 1-3-4 (Maliyet: 5+2=7), Yol 3: 1-2-4 (Maliyet: 3+7=10).
En düşük maliyetli rotaları belirlemek için yolların maliyet yapısı analiz edilmelidir.
2
En düşük maliyetli yol olan 1-2-3-4 rotasına kapasite kısıtları dahilinde akış atayın.
Kapasite = min(u12=6, u23=4, u34=10) = 4 birim. Maliyet = 4 * 6 = 24 birim.
Minimum maliyetli akış probleminde maliyeti en az olan rotaya maksimum kapasite kadar akış verilmelidir.
3
Kalan 6 birimlik talep için bir sonraki en düşük maliyetli yolu (1-3-4) kullanın.
Kalan kapasite (3,4) = 10 - 4 = 6 birim. Kapasite = min(u13=8, u34_kalan=6) = 6 birim. Maliyet = 6 * 7 = 42 birim.
Kalan arzın en ekonomik şekilde hedefe ulaştırılması gerekir.
4
Toplam maliyeti hesaplayın.
Toplam Maliyet = 24 + 42 = 66 birim.
Tüm akışların toplam maliyeti nihai sonucu verir.

Anahtar Kavram

Minimum Maliyetli Akış Problemi, bir şebekede arz ve talep noktaları arasındaki akışın, yay kapasitelerini aşmadan toplam maliyeti minimize edecek şekilde dağıtılmasıdır.

Daha Fazla Pratik

Şebekede bir yayın kapasitesinin değişmesi durumunda toplam maliyetin nasıl etkileneceğini inceleyen duyarlılık analizi soruları çözülebilir.
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru