Examkin

Soru

Zorluk: ZorMinimum Maliyetli Akış Problemi

Devlet Malzeme Ofisi (DMO) merkez deposundan (Düğüm 1), iki farklı bölge müdürlüğüne (Düğüm 4 ve Düğüm 5) ofis malzemesi sevk edilecektir.

Düğüm 1'de 4040 birim malzeme arzı bulunmakta olup, Düğüm 4'ün 1515 birim, Düğüm 5'in ise 2525 birim talebi vardır. Düğüm 2 ve Düğüm 3 yalnızca aktarma (transfer) merkezleridir ve kendi arz/talepleri bulunmamaktadır. Şebekedeki yönlü hatların (i,j)(i, j) birim gönderim maliyetleri (cijc_{ij}) ve kapasiteleri (uiju_{ij}) sırasıyla (cij,uij)(c_{ij}, u_{ij}) biçiminde aşağıdaki tabloda verilmiştir:

Hat (i,j)(i, j)Birim Maliyet (cijc_{ij})Kapasite (uiju_{ij})
(1, 2)2 ₺30
(1, 3)5 ₺20
(2, 3)1 ₺15
(2, 4)7 ₺20
(3, 4)3 ₺10
(3, 5)4 ₺25
(4, 5)2 ₺10

Buna göre, tüm talebin kapasite kısıtları ihlal edilmeden en düşük maliyetle karşılanabilmesi için elde edilen minimum toplam taşıma maliyeti kaç ₺'dir?

  1. A
    265
  2. B
    305
  3. 320Cevap
  4. D
    350
  5. E
    370

Cevap

Optimum taşıma planında toplam maliyet 320 ₺ olarak hesaplanır.
Toplam arz ve talebin 40 birim olduğu dengeli bir modelde, her bir talep noktasına birim taşıma maliyeti en düşük olan yollardan, hat kapasiteleri elverdiği ölçüde ardışık (greedy) atama yapıldığında toplam maliyet fonksiyonu minimize edilir. Düğüm 5 için 1→2→3→51 \rightarrow 2 \rightarrow 3 \rightarrow 5 rotasından 15 birim (105 ₺), 1→3→51 \rightarrow 3 \rightarrow 5 rotasından 10 birim (90 ₺); Düğüm 4 için 1→3→41 \rightarrow 3 \rightarrow 4 rotasından 10 birim (80 ₺) ve 1→2→41 \rightarrow 2 \rightarrow 4 rotasından 5 birim (45 ₺) akış sağlandığında tüm kısıtlar sağlanır ve minimum maliyet olan 320 ₺ elde edilir.

Adım Adım Çözüm

1
Düğüm 5'in 25 birimlik talebini en ucuz yoldan karşılamaya başla.
Düğüm 5'e giden en ucuz yol 1→2→3→51 \rightarrow 2 \rightarrow 3 \rightarrow 5'tir (Birim maliyet: 2+1+4 = 7 ₺). Bu yol üzerindeki en dar kapasite (2, 3) hattındaki 15 birimdir. Bu yoldan 15 birim gönderilir. Maliyet: 15×7=10515 \times 7 = 105 ₺.
Marjinal maliyeti en düşük olan alternatif yol, kapasite sınırı dolana kadar öncelikle kullanılır.
2
Düğüm 5'in kalan 10 birimlik talebini karşıla.
(2, 3) hattı dolduğundan, Düğüm 5'e giden bir sonraki en ucuz yol 1→3→51 \rightarrow 3 \rightarrow 5'tir (Birim maliyet: 5+4 = 9 ₺). Bu yolun 20 birimlik boş kapasitesi vardır. 10 birim bu yoldan gönderilir. Maliyet: 10×9=9010 \times 9 = 90 ₺.
Düğüm 5'in 25 birimlik talebi tamamen karşılanmış oldu.
3
Düğüm 4'ün 15 birimlik talebini en ucuz alternatiflerden karşıla.
Düğüm 4'e giden yollardan 1→2→3→41 \rightarrow 2 \rightarrow 3 \rightarrow 4 yolu kullanılamaz çünkü (2, 3) hattı doludur. Kullanılabilir en ucuz yol 1→3→41 \rightarrow 3 \rightarrow 4'tür (Birim maliyet: 5+3 = 8 ₺). (3, 4) hattının kapasitesi 10 olduğundan buradan 10 birim gönderilir. Maliyet: 10×8=8010 \times 8 = 80 ₺.
(3, 4) hattının kapasitesi dolduğu için kalan talep başka bir yoldan gönderilmelidir.
4
Düğüm 4'ün kalan 5 birimlik talebini karşıla ve toplam maliyeti hesapla.
Düğüm 4'e ulaşan bir sonraki en ucuz yol 1→2→41 \rightarrow 2 \rightarrow 4'tür (Birim maliyet: 2+7 = 9 ₺). Bu yoldan kalan 5 birim gönderilir. Maliyet: 5×9=455 \times 9 = 45 ₺. Toplam Maliyet: 105+90+80+45=320105 + 90 + 80 + 45 = 320 ₺.
Tüm talepler (15 + 25 = 40) arzla (40) eşleşti ve kapasiteler aşılmadan optimum maliyet bulundu.

Anahtar Kavram

Şebeke Modellerinde Minimum Maliyetli Akış Optimizasyonu ve Kapasite Kısıtları

Alternatif Yöntem

Problemi Doğrusal Programlama (DP) modeli olarak kurgulayarak Simpleks algoritması ile çözmek de mümkündür. 7 adet değişken (hatlar) ve 5 adet kısıt (düğümler) ile denge denklemleri kurularak optimum çözüme (320 ₺) matematiksel olarak da ulaşılır.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru