Examkin

Soru

Zorluk: Çok zorMinimum Maliyetli Akış Problemi

Bir afet yönetimi organizasyonunda, afet bölgesine çadır ulaştırmak için kurulan tedarik zinciri şebekesinde düğümler ve aralarındaki taşıma hatları (yaylar) modellenmiştir. 11 numaralı düğüm 2020 tonluk arza sahip ana depodur. 44 ve 55 numaralı düğümler ise sırasıyla 88 ton ve 1212 ton çadır talebi olan afet bölgeleridir. 22 ve 33 numaralı düğümler sadece aktarma merkezi olarak kullanılmakta olup arz veya talepleri yoktur.

Şebekedeki yaylara ait kapasite (ton) ve birim taşıma maliyeti (TL/ton) bilgileri aşağıdaki tabloda verilmiştir:

Yay (Başlangıç →\rightarrow Bitiş)Kapasite (ton)Birim Maliyet (TL/ton)
1→21 \rightarrow 2151522
1→31 \rightarrow 3101055
2→32 \rightarrow 35511
2→42 \rightarrow 4101044
3→43 \rightarrow 4101022
3→53 \rightarrow 5151533
4→54 \rightarrow 55511

Buna göre, şebekedeki kapasite kısıtları ihlal edilmeden tüm taleplerin karşılanmasını sağlayan en düşük maliyetli akış planında (minimum maliyetli akış problemi) toplam taşıma maliyeti kaç TL olur?

  1. A
    112
  2. B
    124
  3. 132Cevap
  4. D
    134
  5. E
    142

Cevap

Toplam taşıma maliyeti 132 TL'dir.
Optimal akış planı, şebekedeki kapasite darboğazları (bottlenecks) dikkate alınarak mantıksal bir çıkarımla elde edilebilir. Düğüm 1'den çıkması gereken 20 ton arz, zorunlu olarak kapasitesi 15 ton olan en ucuz hatta (1->2) ve kalan 5 ton mecburen (1->3) hattına yönlendirilir. Düğüm 2'ye ulaşan 15 ton, kapasitesi 5 olan (2->3) hattını doldurur ve artan 10 ton mecburen (2->4) hattından akar. Düğüm 4 kendisine gelen 10 tonun 8 tonunu kullanır, kalan 2 tonu mecburen (4->5) hattından iletir. Düğüm 3'te biriken 10 ton ise Düğüm 5'in kalan 10 tonluk ihtiyacını (3->5) hattı üzerinden tam olarak kapatır. Tüm bu kapasite kaynaklı zorunlu atamaların maliyetleri hesaplandığında ulaşılan tek optimal çözüm 132 TL'dir.

Adım Adım Çözüm

1
Düğüm 1'den çıkması gereken toplam arzın darboğaz analizini yapmak.
Düğüm 1'den çıkacak 20 ton arz için (1→2)(1 \rightarrow 2) yayından 15 ton, (1→3)(1 \rightarrow 3) yayından 5 ton gönderilir.
(1→2)(1 \rightarrow 2) yayının kapasitesi 15 ton ile sınırlı olduğundan, kalan 5 tonluk arz mecburen diğer alternatif olan (1→3)(1 \rightarrow 3) yayına aktarılmak zorundadır.
2
Düğüm 2'ye ulaşan 15 tonluk akışın yönlendirilmesi.
(2→3)(2 \rightarrow 3) yayından 5 ton, (2→4)(2 \rightarrow 4) yayından 10 ton akış gerçekleşir.
Düğüm 2'den çıkışta en ucuz yol olan (2→3)(2 \rightarrow 3) yayının maliyeti 1 TL'dir ancak kapasitesi 5 tondur. Tam kapasite kullanıldıktan sonra kalan 10 ton, mecburen (2→4)(2 \rightarrow 4) yayından (maliyet 4 TL) gönderilir.
3
Düğüm 4'teki talep karşılaması ve kalan akışın yönlendirilmesi.
Düğüm 4 talebini (8 ton) karşılar ve kalan 2 tonu (4→5)(4 \rightarrow 5) yayından Düğüm 5'e gönderir.
Düğüm 2'den Düğüm 4'e ulaşan 10 tonluk çadırın 8 tonu buradaki ihtiyacı giderir. Artan 2 tonun gidebileceği tek yön, kapasitesi 5 ton olan (4→5)(4 \rightarrow 5) yayıdır.
4
Düğüm 3'teki toplam birikimin Düğüm 5'in kalan talebini karşılaması.
(3→5)(3 \rightarrow 5) yayı üzerinden 10 tonluk akış gerçekleştirilir.
Düğüm 3'e Düğüm 1'den 5 ton, Düğüm 2'den 5 ton olmak üzere toplam 10 ton gelmiştir. Düğüm 5'in toplam 12 tonluk talebinin 2 tonu Düğüm 4'ten karşılanmıştır, bu nedenle tam olarak 10 ton açığı vardır. Bu açık (3→5)(3 \rightarrow 5) yayı ile kapatılır.
5
Zorunlu rotalar üzerinden toplam maliyetin hesaplanması.
Toplam Maliyet = 132132 TL olarak bulunur.
Belirlenen akışlar birim maliyetlerle çarpılır: (15×2)+(5×5)+(5×1)+(10×4)+(10×3)+(2×1)=30+25+5+40+30+2=132(15 \times 2) + (5 \times 5) + (5 \times 1) + (10 \times 4) + (10 \times 3) + (2 \times 1) = 30 + 25 + 5 + 40 + 30 + 2 = 132 TL.

Anahtar Kavram

Minimum Maliyetli Akış Problemlerinde Kapasite Darboğazları

Alternatif Yöntem

Problemi ardışık en kısa yollar (Successive Shortest Path) algoritması ile çözerek, her adımda arz düğümünden talep düğümlerine artık (residual) kapasiteleri olan en kısa rotaları bularak da aynı 132 TL sonucuna ulaşabilirsiniz.
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru