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
67Answer
C
70
D
74
E
81

Answer

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.

Step-by-Step Solution

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.

Key Concept

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

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic