Bir şebeke modelinde düğümler arasındaki birim akış maliyetleri (c_{ij}), yay kapasiteleri… — KPSS İstatistik

Bir şebeke modelinde düğümler arasındaki birim akış maliyetleri ( $c_{ij}$ ), yay kapasiteleri ( $u_{ij}$ ) ve düğümlerin arz/talep değerleri ( $b_i$ ) aşağıda sunulmuştur. Pozitif $b_i$ değerleri arzı, negatif $b_i$ değerleri ise talebi temsil etmektedir.

Yay $(i, j)$	Birim Maliyet ( $c_{ij}$ )	Kapasite ( $u_{ij}$ )
$(1, 3)$	$2$	$6$
$(1, 4)$	$8$	$10$
$(2, 3)$	$4$	$8$
$(2, 4)$	$6$	$5$
$(3, 4)$	$1$	$4$

Düğüm Arz/Talep Dengesi:
- Düğüm $1$ : $+10$
- Düğüm $2$ : $+5$
- Düğüm $3$ : $-8$
- Düğüm $4$ : $-7$

Buna göre, şebekedeki tüm talebi karşılayan ve toplam maliyeti minimize eden optimal akış planında toplam maliyet kaç birimdir?

A
63
67Cevap
C
70
D
74
E
81

Cevap

Optimal çözümde toplam maliyet 67 birimdir.

Optimal çözümde, maliyeti en düşük olan

(1, 3)

yayı 6 birim kapasitesine kadar doldurulur. Düğüm 1'den kalan 4 birim

(1, 4)

yayına aktarılır. Düğüm 2'den gelen 5 birim ise, doğrudan

(2, 4)

üzerinden gitmek yerine

(2, 3)

ve ardından

(3, 4)

aktarma yayını kullanarak Düğüm 4'e ulaştırılır; çünkü

4+1 < 6

birim maliyet avantajı sağlar. Bu konfigürasyonda tüm arz-talep dengeleri sağlanır ve toplam maliyet

12 + 32 + 20 + 3 = 67

olarak bulunur.

Adım Adım Çözüm

Akış korunum denklemlerini ve kısıtları belirleyin.

Düğüm 1:

x_{13} + x_{14} = 10

; Düğüm 2:

x_{23} + x_{24} = 5

; Düğüm 3:

x_{13} + x_{23} - x_{34} = 8

; Düğüm 4:

x_{14} + x_{24} + x_{34} = 7

. Kapasiteler:

x_{13} \leq 6

x_{24} \leq 5

x_{34} \leq 4

Minimum maliyetli akış problemlerinde her düğümde giren ve çıkan akışın arz/talep dengesine eşit olması gerekir.

Düşük maliyetli yollara öncelik vererek akışı dağıtın.

En ucuz yay olan

(1, 3)

için

x_{13} = 6

(kapasite sınırı). Bu durumda Düğüm 1'in kalan 4 birim arzı mecburen

(1, 4)

üzerinden gönderilir (

x_{14} = 4

Maliyet minimizasyonu için önce en düşük birim maliyetli kapasiteler doldurulur.

Diğer arz düğümünden (Düğüm 2) gelen akışı optimize edin.

Düğüm 2'den 5 birim arz vardır. Eğer 5 birimin tamamı

(2, 3)

üzerinden gönderilirse (

x_{23}=5

), Düğüm 3'te toplam

6+5=11

birim birikir. Düğüm 3'ün talebi 8 olduğu için kalan 3 birim

(3, 4)

üzerinden Düğüm 4'e aktarılır (

x_{34}=3

). Bu durumda

x_{24}=0

olur.

(2, 3) + (3, 4)

yolunun toplam maliyeti (

4+1=5

), doğrudan

(2, 4)

yayının maliyetinden (

6

) daha düşüktür.

Toplam maliyeti (

Z

) hesaplayın.

Z = (6 \times 2) + (4 \times 8) + (5 \times 4) + (0 \times 6) + (3 \times 1) = 12 + 32 + 20 + 0 + 3 = 67

Belirlenen optimal akış miktarları ile birim maliyetlerin çarpımlarının toplamı toplam maliyeti verir.

Anahtar Kavram

Minimum Maliyetli Akış Problemi ve Kapasite Kısıtlı Şebeke Optimizasyonu

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru