Examkin

Soru

Zorluk: ZorMinimum Maliyetli Akış Problemi

Bir kamu kurumunun Ulusal Sağlık Veri Ağı projesi kapsamında, Ana Veri Merkezi'nden (Düğüm 1), bölgesel veri merkezlerine (Düğüm 4 ve Düğüm 5) şifrelenmiş günlük sağlık verisi aktarımı yapılacaktır. Şebekede yer alan 2 ve 3 numaralı düğümler ise yalnızca yönlendirici (router) görevi görmekte olup veri üretmez veya tüketmezler.

Düğümlerdeki arz ve talep miktarları (Terabayt/gün) şu şekildedir:
- Düğüm 1 (Ana Veri Merkezi): 30 TB veri üretiyor (Arz)
- Düğüm 4 (1. Bölge): 10 TB veriye ihtiyaç duyuyor (Talep)
- Düğüm 5 (2. Bölge): 20 TB veriye ihtiyaç duyuyor (Talep)

Şebeke üzerindeki bağlantıların günlük veri aktarım kapasiteleri (uiju_{ij}) ve 1 Terabayt verinin aktarım maliyetleri (cijc_{ij} Bin TL) aşağıdaki tabloda verilmiştir:

| Bağlantı (i→ji \rightarrow j) | Kapasite (uiju_{ij}) | Birim Maliyet (cijc_{ij})
| :---: | :---: | :---: |
| 1→21 \rightarrow 2 | 20 | 2 |
| 1→31 \rightarrow 3 | 25 | 5 |
| 2→32 \rightarrow 3 | 15 | 1 |
| 2→42 \rightarrow 4 | 15 | 6 |
| 3→43 \rightarrow 4 | 10 | 3 |
| 3→53 \rightarrow 5 | 20 | 4 |
| 4→54 \rightarrow 5 | 10 | 2 |

Buna göre, Ana Veri Merkezi'ndeki 30 TB verinin tamamının talep merkezlerine ulaştırılmasını sağlayan optimum minimum maliyetli akış planında toplam aktarım maliyeti kaç Bin TL'dir?

  1. A
    200
  2. 230Cevap
  3. C
    240
  4. D
    250
  5. E
    260

Cevap

Sistemin günlük veri aktarımını en düşük maliyetle gerçekleştirebilmesi için hesaplanan minimum toplam aktarım maliyeti 230 Bin TL'dir.
Verilen şebekede arz-talep ve kapasite kısıtlarını sağlayan optimum akış dağılımı şu şekildedir: x12=20,x13=10,x23=15,x24=5,x34=5,x35=20,x45=0x_{12}=20, x_{13}=10, x_{23}=15, x_{24}=5, x_{34}=5, x_{35}=20, x_{45}=0. Bu değerler birim maliyetlerle çarpılıp toplandığında minimum maliyet olan 230 değerine ulaşılır. Herhangi bir alternatif rota üzerinden akış kaydırmak, ya kapasiteyi aşar ya da toplam maliyeti artırır.

Adım Adım Çözüm

1
Arz ve talep dengesini kontrol etme.
Toplam arz = 30 TB (Düğüm 1). Toplam talep = 10 TB (Düğüm 4) + 20 TB (Düğüm 5) = 30 TB. Şebeke dengelidir.
Minimum maliyetli akış problemlerinde (eğer dışarıdan bir yapay düğüm eklenmemişse) toplam giren akışın toplam çıkan akışa eşit olması gerekir.
2
Düğüm 1'den çıkan veriyi en düşük maliyetli hatlara kapasiteleri dahilinde yönlendirme.
1→21 \rightarrow 2 hattının maliyeti 2, 1→31 \rightarrow 3 hattının maliyeti 5'tir. Maksimum akışı ucuz olan 1→21 \rightarrow 2 hattına veririz: x12=20x_{12} = 20 (kapasite doldu). Kalan 10 TB veriyi zorunlu olarak 1→31 \rightarrow 3 hattına veririz: x13=10x_{13} = 10.
Kaynaktan çıkan verinin mümkün olan en ucuz rotalardan sisteme giriş yapması toplam maliyeti minimize eder.
3
Düğüm 2'deki 20 TB veriyi yönlendirme.
Düğüm 2'den çıkış yolları: 2→32 \rightarrow 3 (maliyet 1) ve 2→42 \rightarrow 4 (maliyet 6). En ucuz olan 2→32 \rightarrow 3 hattına kapasitesi kadar (x23=15x_{23} = 15) yönlendiririz. Kalan 5 TB veriyi 2→42 \rightarrow 4 hattına yönlendiririz (x24=5x_{24} = 5).
Ara düğümlerde biriken akış, kapasite kısıtları ihlal edilmeden en düşük maliyetli rotalara aktarılmalıdır.
4
Düğüm 3'teki veriyi yönlendirme ve talep düğümlerinin ihtiyaçlarını karşılama.
Düğüm 3'e Düğüm 1'den 10 TB, Düğüm 2'den 15 TB olmak üzere toplam 25 TB veri gelir. Düğüm 4'ün toplam ihtiyacı 10 TB olup, 5 TB'ını Düğüm 2'den almıştır; bu yüzden 3→43 \rightarrow 4 hattından sadece 5 TB gönderilir (x34=5x_{34} = 5). Düğüm 3'te kalan 20 TB veri 3→53 \rightarrow 5 hattından gönderilir (x35=20x_{35} = 20). Düğüm 5 talebini tam karşılamıştır.
Yönlendirici düğümlerde giren akış çıkan akışa eşit olmalı ve nihai talep düğümlerinin eksikleri tam olarak kapatılmalıdır.
5
Toplam optimum maliyeti hesaplama.
Maliyet = (20×2)+(10×5)+(15×1)+(5×6)+(5×3)+(20×4)+(0×2)=40+50+15+30+15+80=230(20 \times 2) + (10 \times 5) + (15 \times 1) + (5 \times 6) + (5 \times 3) + (20 \times 4) + (0 \times 2) = 40 + 50 + 15 + 30 + 15 + 80 = 230 Bin TL.
Bulunan bu temel uygun çözümde kalıntı (residual) şebekede negatif maliyetli bir çevrim bulunmamaktadır, dolayısıyla çözüm optimumdur.

Anahtar Kavram

Minimum Maliyetli Akış Problemlerinde Kapasite Kısıtlı Yönlendirme
Bu soruyu puanla

Konular

Minimum Maliyetli Akış Problemi

Bu konudan daha fazla soru