Minimum Maliyetli Akış Problemi Practice Questions — KPSS İstatistik

Question 1Question →

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?

63

67

70

74

81

Show answer & explanation

Answer: 67

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

1

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.

2

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.

3

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.

4

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 2Question →

Dört düğümden (1, 2, 3, 4) oluşan bir şebeke modelinde düğümler arası birim akış maliyetleri ( $c_{ij}$ ) ve yay kapasiteleri ( $u_{ij}$ ) aşağıdaki tabloda sunulmuştur:

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

Şebekede düğüm 1'in arzı 10 birim ( $b_1 = 10$ ) ve düğüm 4'ün talebi 10 birimdir ( $b_4 = -10$ ). Düğüm 2 ve 3 ise aktarma (transshipment) düğümleridir.

Buna göre, toplam 10 birimlik akışın hedeflenen düğüme ulaştırılması için gereken toplam minimum maliyet kaç birimdir?

60

65

70

80

82

Show answer & explanation

Answer: 65

Answer

Toplam minimum maliyet 65 birimdir.

65 birimlik sonuç, en düşük birim maliyete sahip 1-2-3-4 rotasından kapasite sınırı olan 5 birimin, ardından kalan 5 birimin ise bir sonraki en ucuz seçenek olan 1-3-4 rotasından geçirilmesiyle (5*6 + 5*7) elde edilir.

Step-by-Step Solution

1

Şebekedeki olası rotaları ve birim maliyetlerini belirle.

1-2-3-4: 3+1+2=6; 1-3-4: 5+2=7; 1-2-4: 3+7=10.

Minimum maliyetli akış için en ucuz yolların önceliklendirilmesi gerekir.

2

En ucuz yol olan 1-2-3-4 rotasının kapasitesini kontrol et ve akışı ata.

Kapasite = min(u12=8, u23=5, u34=10) = 5 birim. Maliyet: 5 x 6 = 30.

(2, 3) yayının kapasitesi 5 birim olduğu için bu rotadan en fazla 5 birim geçebilir.

3

Kalan 5 birimlik akış için bir sonraki en ucuz yolu belirle ve kapasiteyi kontrol et.

Sıradaki yol 1-3-4 (Maliyet: 7). Kapasite = min(u13=6, u34_kalan=10-5=5) = 5 birim. Maliyet: 5 x 7 = 35.

(3, 4) yayının kalan kapasitesi ve (1, 3) yayının kapasitesi 5 birime izin vermektedir.

4

Toplam maliyeti hesapla.

30 + 35 = 65.

Tüm arz (10 birim) en ekonomik rotalar üzerinden dağıtılmıştır.

Key Concept

Minimum maliyetli akış problemlerinde, akışın birim maliyeti en düşük olan yollar üzerinden kapasite kısıtları dahilinde atanması temel esastır.

Question 3Question →

Bir dağıtım şebekesinde 1 numaralı merkezden (arz kaynağı) 4 numaralı merkeze (talep noktası) toplam 10 birimlik ürün sevkiyatı yapılacaktır. Şebekedeki yaylara (yollar) ait birim akış maliyetleri ( $c_{ij}$ ), kapasite kısıtları ( $u_{ij}$ ) ve düğümlerin arz/talep değerleri ( $b_i$ ) aşağıdaki tabloda verilmiştir:

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

Düğümlerin arz/talep dengesi $b_1 = 10, b_2 = 0, b_3 = 0, b_4 = -10$ şeklinde olduğuna göre, bu şebeke için toplam minimum akış maliyeti kaç birimdir?

66

68

76

85

60

Show answer & explanation

Answer: 66

Answer

Şebeke üzerindeki kapasite kısıtları dahilinde yapılan en uygun akış dağılımı ile toplam minimum maliyet 66 birimdir.

En düşük birim maliyete sahip rota 1-2-3-4 (maliyet=6) yoludur ve bu yolun kapasitesi 4 birim ile sınırlıdır. Kalan 6 birimlik akış, bir sonraki en ucuz yol olan 1-3-4 (maliyet=7) rotasından gönderildiğinde toplam maliyet

4 \times 6 + 6 \times 7 = 66

olarak bulunur. Bu dağılım tüm kapasite ve arz/talep kısıtlarını sağlamaktadır.

Step-by-Step Solution

1

Olası yolların toplam birim maliyetlerini hesaplayın.

Yol 1: 1-2-3-4 (Maliyet: 3+1+2=6), Yol 2: 1-3-4 (Maliyet: 5+2=7), Yol 3: 1-2-4 (Maliyet: 3+7=10).

En düşük maliyetli rotaları belirlemek için yolların maliyet yapısı analiz edilmelidir.

2

En düşük maliyetli yol olan 1-2-3-4 rotasına kapasite kısıtları dahilinde akış atayın.

Kapasite = min(u12=6, u23=4, u34=10) = 4 birim. Maliyet = 4 * 6 = 24 birim.

Minimum maliyetli akış probleminde maliyeti en az olan rotaya maksimum kapasite kadar akış verilmelidir.

3

Kalan 6 birimlik talep için bir sonraki en düşük maliyetli yolu (1-3-4) kullanın.

Kalan kapasite (3,4) = 10 - 4 = 6 birim. Kapasite = min(u13=8, u34_kalan=6) = 6 birim. Maliyet = 6 * 7 = 42 birim.

Kalan arzın en ekonomik şekilde hedefe ulaştırılması gerekir.

4

Toplam maliyeti hesaplayın.

Toplam Maliyet = 24 + 42 = 66 birim.

Tüm akışların toplam maliyeti nihai sonucu verir.

Key Concept

Minimum Maliyetli Akış Problemi, bir şebekede arz ve talep noktaları arasındaki akışın, yay kapasitelerini aşmadan toplam maliyeti minimize edecek şekilde dağıtılmasıdır.

Practice More

Şebekede bir yayın kapasitesinin değişmesi durumunda toplam maliyetin nasıl etkileneceğini inceleyen duyarlılık analizi soruları çözülebilir.

Estimated Time:2m 0s

Question 4Question →

Bir kamu kurumunun lojistik şebekesinde 1 numaralı merkezden (kaynak) 4 numaralı merkeze (varış) toplam $10$ birimlik ürün sevkiyatı yapılacaktır. Şebekede yer alan yayların birim taşıma maliyetleri ( $c_{ij}$ ) ve kapasiteleri ( $u_{ij}$ ) aşağıdaki tabloda sunulmuştur. 1 numaralı düğümün arzı $10$ birim, 4 numaralı düğümün talebi $10$ birim olup diğer düğümler aktarma merkezidir.

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

Buna göre, bu sevkiyatın en düşük toplam maliyetle gerçekleştirilmesi durumunda oluşacak toplam maliyet kaç birim olur?

60

73

75

78

84

Show answer & explanation

Answer: 73

Answer

Optimal sevkiyat planına göre minimum toplam maliyet 73 birimdir.

Minimum maliyetli akış prensibine göre, 10 birimlik ürünün 5 birimi en ucuz güzergah olan 1-2-3-4 üzerinden (maliyet 30), 2 birimi bir sonraki seçenek 1-3-4 üzerinden (maliyet 16) ve kalan 3 birimi 1-2-4 üzerinden (maliyet 27) gönderildiğinde toplam 73 birimlik en düşük maliyete ulaşılır.

Step-by-Step Solution

1

Şebekedeki olası yolların maliyetlerini hesaplayınız.

1-2-3-4 yolu:

2+1+3=6

; 1-3-4 yolu:

5+3=8

; 1-2-4 yolu:

2+7=9

.

En düşük maliyetli akışı sağlamak için en ucuz güzergahlar önceliklendirilmelidir.

2

En ucuz güzergah olan 1-2-3-4 yoluna kapasite kısıtları dahilinde akış atayınız.

Kapasite:

\min(u_{12}=8, u_{23}=5, u_{34}=7) = 5

birim. Akış:

x_{12}=5, x_{23}=5, x_{34}=5

. Maliyet:

5 \times 6 = 30

.

Sistemdeki en ekonomik yolun kapasitesi 5 birimle sınırlıdır.

3

Kalan 5 birimlik akış için bir sonraki en ucuz yol olan 1-3-4 güzergahını değerlendiriniz.

Yay (3, 4) üzerinde kalan kapasite

7 - 5 = 2

birimdir. Akış:

x_{13}=2, x_{34}=2

. Maliyet:

2 \times 8 = 16

.

1-3-4 yolu, 1-2-4 yoluna göre daha ucuzdur ancak (3, 4) yayının kapasitesi dolmak üzeredir.

4

Kalan 3 birimlik akışı son seçenek olan 1-2-4 güzergahına atayınız.

Yay (1, 2) kalan kapasitesi

8 - 5 = 3

; Yay (2, 4) kapasitesi 6. Akış:

x_{12}=3, x_{24}=3

. Maliyet:

3 \times 9 = 27

.

Toplam 10 birimlik arzın tamamı sevkedilmiş olur.

5

Tüm adımlardaki maliyetleri toplayınız.

30 + 16 + 27 = 73

.

Şebeke üzerindeki toplam minimum maliyet bu şekilde hesaplanır.

Key Concept

Minimum maliyetli akış problemlerinde, akışın kapasite kısıtlarını (u_ij) ihlal etmeden en düşük birim maliyetli (c_ij) yaylar üzerinden yönlendirilmesi esastır.

Question 5Question →

Bir kamu dağıtım şebekesinde, 1 numaralı düğümden (kaynak) 5 numaralı düğüme (varış) toplam 15 birimlik ürün sevkiyatı yapılacaktır. Şebekedeki diğer düğümler (2, 3, 4) aktarma merkezleridir. Düğümler arasındaki yayların birim akış maliyetleri ( $c_{ij}$ ) ve kapasiteleri ( $u_{ij}$ ) aşağıdaki tabloda verilmiştir:

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

Tüm talebin karşılanması ve toplam maliyetin enküçüklenmesi hedeflendiğine göre, bu sevkiyatın minimum maliyeti kaç birimdir?

132

135

138

140

145

Show answer & explanation

Answer: 138

Answer

Toplam sevkiyatın minimum maliyeti 138 birimdir.

Şebekede kaynaktan varışa giden en ucuz güzergahların birim maliyeti 9'dur (1-2-3-5 ve 1-3-5). Ancak her iki güzergah da (3, 5) yayını ortak kullanmaktadır ve bu yayın kapasitesi 12 birimdir. Bu nedenle bu güzergahlardan toplamda en fazla 12 birim sevkiyat yapılabilir. Toplam 15 birimlik talebin kalan 3 birimi, bir sonraki en düşük maliyetli (birim maliyeti 10 olan) 1-2-4-5 güzergahı ile gönderilmelidir. Sonuç olarak toplam maliyet

(12 \times 9) + (3 \times 10) = 138

olur.

Step-by-Step Solution

1

Kaynaktan (1) varışa (5) giden tüm alternatif yolları ve bu yolların birim maliyetlerini hesaplayın.

Yol 1: 1-2-3-5 maliyeti

4+2+3=9

; Yol 2: 1-3-5 maliyeti

6+3=9

; Yol 3: 1-2-4-5 maliyeti

4+5+1=10

.

En düşük maliyetli güzergahları belirlemek için şebeke üzerindeki tüm akış yolları analiz edilmelidir.

2

Yol kapasitelerini ve ortak yay kısıtlarını kontrol edin.

En ucuz iki yol (Yol 1 ve Yol 2) (3, 5) yayını kullanmaktadır. Bu yayın kapasitesi

u_{35} = 12

birim ile sınırlıdır.

Şebeke problemlerinde toplam akış, yayların kapasite kısıtlarını (

x_{ij} \leq u_{ij}

) aşamaz.

3

Birimleri en düşük maliyetli yollardan başlayarak dağıtın.

12 birim maliyeti 9 olan Yol 1 ve Yol 2 üzerinden gönderilir. Kalan 3 birim (

15 - 12 = 3

) maliyeti 10 olan Yol 3 ile gönderilir.

Kapasite dolduğunda kalan talep, maliyeti en düşük olan bir sonraki alternatif güzergaha yönlendirilir.

4

Toplam maliyet fonksiyonunun değerini hesaplayın.

Toplam Maliyet =

(12 \times 9) + (3 \times 10) = 108 + 30 = 138

birim.

Optimal akış miktarları ile ilgili güzergahların birim maliyetlerinin toplamı minimum maliyeti verir.

Key Concept

Minimum maliyetli akış probleminde, kapasite kısıtları bir 'darboğaz' (bottleneck) oluşturduğunda, akışın bir kısmı daha yüksek maliyetli alternatif yollara kaydırılır.

Question 6Question →

Bir kamu lojistik şebekesinde $1$ numaralı düğümden (kaynak) $4$ numaralı düğüme (varış) toplam $20$ birimlik ürün sevkiyatı gerçekleştirilecektir. Şebekedeki düğümler arası birim taşıma maliyetleri ( $c_{ij}$ ) ve yay kapasiteleri ( $u_{ij}$ ) aşağıdaki tabloda verilmiştir:

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

Buna göre, toplam maliyeti minimize eden akış planı uygulandığında ulaşılan toplam maliyet kaç birimdir?

185

180

175

190

200

Show answer & explanation

Answer: $185$

Answer

Optimum akış planına göre toplam maliyet

185

birimdir.

Toplam

20

birimlik akışın en ekonomik dağılımı; birim maliyeti

9

olan iki farklı yola (kapasiteleri dahilinde

5

ve

10

birim) ve kalan

5

birimin birim maliyeti

10

olan yola aktarılmasıyla sağlanır. Bu durumda

(5 \times 9) + (10 \times 9) + (5 \times 10) = 185

birim sonucuna ulaşılır.

Step-by-Step Solution

1

Kaynaktan varışa giden olası yolların birim maliyetlerini hesapla.

Yol 1:

1 \rightarrow 2 \rightarrow 3 \rightarrow 4

(Maliyet:

3+1+5=9

); Yol 2:

1 \rightarrow 3 \rightarrow 4

(Maliyet:

4+5=9

); Yol 3:

1 \rightarrow 2 \rightarrow 4

(Maliyet:

3+7=10

).

En düşük maliyetli yolları önceliklendirmek için birim maliyet analizi gereklidir.

2

Kapasite kısıtlarını dikkate alarak akış ataması yap.

Yol 1 (

9

birim) için darboğaz

2 \rightarrow 3

yayıdır (

u_{23}=5

), bu yoldan

5

birim gönderilir. Yol 2 (

9

birim) için darboğaz

1 \rightarrow 3

yayıdır (

u_{13}=10

), bu yoldan

10

birim gönderilir.

En ucuz yollardan kapasiteleri yettiği ölçüde maksimum akış gönderilmelidir.

3

Kalan akışı bir sonraki en ucuz yola ata.

Toplam

20

birimin

15

'i gönderildi, kalan

5

birim Yol 3 (

10

birim maliyetli) üzerinden gönderilir.

1 \rightarrow 2

yayı toplam

10

birim akışı (

5+5

) kaldırabilir (

u_{12}=15

).

Şebeke dengesi gereği tüm arzın hedefe ulaştırılması gerekir.

4

Toplam maliyeti hesapla.

(5 \times 9) + (10 \times 9) + (5 \times 10) = 45 + 90 + 50 = 185

.

Her bir yoldaki akış miktarı ile birim maliyetin çarpımlarının toplamı toplam maliyeti verir.

Key Concept

Minimum maliyetli akış probleminde amaç, kapasite kısıtlarını ihlal etmeden birim maliyeti en düşük olan yollar üzerinden akışı dağıtarak toplam maliyeti minimize etmektir.

Hints

1

Öncelikle

1

numaralı düğümden

4

numaralı düğüme giden tüm alternatif yolları ve bu yolların birim maliyetlerini listeleyin.

2

En düşük maliyetli yoldan başlayarak, o yolu oluşturan tüm yayların (arkların) kapasitelerini kontrol edin ve en küçük kapasite kadar akış atayın.

3

1-2-3-4

ve

1-3-4

yollarının birim maliyetleri eşittir (

9

). Bu yolların kapasitelerini doldurduktan sonra kalan akışı bir sonraki en ucuz yola yönlendirin.

Practice More

Şebekede bir yayın kapasitesi değiştiğinde toplam maliyetin nasıl duyarlılık göstereceğini analiz etmek için duyarlılık analizi konusuna göz atabilirsiniz.

Estimated Time:2m 0s

Question 7Question →

Bir kamu kurumunun lojistik şebekesinde $1$ numaralı düğümden (kaynak) $4$ numaralı düğüme (varış) toplam $10$ birimlik bir ürün sevkiyatı gerçekleştirilecektir. Şebekede yer alan diğer düğümler ( $2$ ve $3$ ) ara aktarma merkezleridir. Düğümler arasındaki bağlantılar, birim taşıma maliyetleri ( $c_{ij}$ ) ve kapasite sınırları ( $u_{ij}$ ) aşağıdaki tabloda sunulmuştur:

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

Buna göre, tüm kapasite kısıtlarına uyularak $10$ birimlik akışın en düşük maliyetle gerçekleştirilmesi durumunda toplam maliyet kaç birim olur?

60

64

66

70

74

Show answer & explanation

Answer: 64

Answer

Optimum sevkiyat stratejisiyle toplam maliyet 64 birimdir.

Şebekede 1-2-3-4 rotası birim maliyet açısından en avantajlı yoldur (6 birim). Ancak bu rotadaki (1, 2) yayı maksimum 6 birim taşıyabilmektedir. Dolayısıyla 6 birim bu yoldan, kalan 4 birim ise maliyeti 7 olan 1-3-4 rotasından gönderilerek (6*6 + 4*7 = 64) en düşük maliyete ulaşılır.

Step-by-Step Solution

1

Şebekedeki olası rotaların birim maliyetlerini hesaplayın.

1-2-3-4 yolu: 3+1+2 = 6 birim; 1-3-4 yolu: 5+2 = 7 birim; 1-2-4 yolu: 3+8 = 11 birim.

En düşük maliyetli yolları belirlemek için tüm rotalar analiz edilmelidir.

2

En ucuz rotaya kapasite sınırları dahilinde maksimum akışı atayın.

1-2-3-4 yolu birim maliyeti 6'dır. Bu yoldaki (1, 2) yayının kapasitesi 6 birim olduğundan, bu rotaya en fazla 6 birim gönderilebilir. Maliyet: 6 birim * 6 = 36 birim.

Minimum maliyetli akış probleminde öncelik en düşük maliyetli yola verilir.

3

Kalan akışı bir sonraki en ucuz rotaya atayın.

Toplam 10 birimden kalan 4 birim (10 - 6), birim maliyeti 7 olan 1-3-4 yoluna atanır. Maliyet: 4 birim * 7 = 28 birim.

Talebin tamamı karşılanana kadar maliyet sırasına göre akış atanmaya devam edilir.

4

Toplam maliyeti hesaplayın.

36 + 28 = 64 birim.

Atanan tüm akışların maliyetleri toplamı şebekenin minimum toplam maliyetini verir.

Key Concept

Minimum Maliyetli Akış Problemi (MCFP) ve Kapasite Kısıtları

Question 8Question →

Bir enerji dağıtım şebekesinde 1 numaralı üretim merkezinden 4 numaralı tüketim merkezine toplam $10$ birim enerji aktarılacaktır. Şebekedeki hatların birim iletim maliyetleri ( $c_{ij}$ ) ve kapasite sınırları ( $u_{ij}$ ) aşağıdaki tabloda verilmiştir:

Hat $(i, j)$	Maliyet ( $c_{ij}$ )	Kapasite ( $u_{ij}$ )
$(1, 2)$	$2$	$7$
$(1, 3)$	$5$	$10$
$(2, 3)$	$1$	$4$
$(2, 4)$	$4$	$5$
$(3, 4)$	$3$	$10$

Düğümlerdeki arz/talep değerleri $b_1 = 10$ ve $b_4 = -10$ olup diğer düğümler ara duraktır ( $b_2 = b_3 = 0$ ). Bu şebekede toplam iletim maliyetini minimize eden akış planı uygulandığında ulaşılabilecek minimum toplam maliyet kaç birimdir?

60

66

70

74

80

Show answer & explanation

Answer: 66

Answer

Şebekedeki kapasite kısıtları ve birim maliyetler dikkate alındığında minimum toplam maliyet 66 birimdir.

Şebekedeki en düşük maliyetli rotalar

1-2-4

ve

1-2-3-4

olup her ikisinin de birim maliyeti

6

birimdir. Ancak bu iki yol da

(1,2)

hattını ortak kullanmaktadır ve bu hattın kapasitesi

7

birimdir. Dolayısıyla en ucuz maliyetle sadece

7

birim enerji taşınabilir (

7 \times 6 = 42

). Geriye kalan

3

birimlik enerji mecburen bir sonraki en ucuz yol olan

1-3-4

(maliyeti

8

) üzerinden gönderilmelidir (

3 \times 8 = 24

). Toplam maliyet

42 + 24 = 66

birim olarak bulunur.

Step-by-Step Solution

1

Olası yolları ve birim maliyetlerini belirleyin.

Yol 1:

1-2-4

(Maliyet:

2+4=6

), Yol 2:

1-2-3-4

(Maliyet:

2+1+3=6

), Yol 3:

1-3-4

(Maliyet:

5+3=8

)

En ucuz rotaları belirlemek için alternatif yolların maliyetleri toplanır.

2

En düşük maliyetli yollara (

6

birim maliyetli) kapasite kısıtlarına göre akış atayın.

Yol 1 ve Yol 2 toplamda

(1,2)

hattını kullanır (Kapasite:

7

). Yol 1 ayrıca

(2,4)

hattını (Kapasite:

5

), Yol 2 ise

(2,3)

hattını (Kapasite:

4

) kullanır.

Kapasite kısıtları, ucuz yollardan ne kadar akış gönderilebileceğini sınırlar.

3

Akışın dağılımını yapın.

Maliyeti

6

olan yollardan toplam

7

birim (hattın sınırı kadar) gönderilir (

5

birim

1-2-4

üzerinden,

2

birim

1-2-3-4

üzerinden). Kalan

3

birim maliyeti

8

olan

1-3-4

yolundan gönderilir.

Toplam

10

birimlik arzın tamamı varış noktasına ulaştırılmalıdır.

4

Toplam maliyeti hesaplayın.

Toplam Maliyet =

(7 \times 6) + (3 \times 8) = 42 + 24 = 66

birim.

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

Key Concept

Minimum Maliyetli Akış Problemi'nde amaç, kapasite kısıtlarını ihlal etmeden kaynak düğümden varış düğümüne gerekli akışı en düşük toplam maliyetle ulaştırmaktır.

Estimated Time:1m 30s

Question 9Question →

Bir büyükşehir belediyesinin içme suyu şebekesinde, ana su deposundan (Düğüm 1) iki farklı ilçeye (Düğüm 4 ve Düğüm 5) su pompalanacaktır. Şebekedeki düğümlerin arz/talep miktarları (bin $m^3$ ) ve mevcut bir temel uygun çözüme ait yay akışları ile birim pompalama maliyetleri (bin $m^3$ başına birim maliyet) aşağıda verilmiştir:

Arz ve Talep Miktarları: $b_1 = 20$ , $b_2 = 0$ , $b_3 = 0$ , $b_4 = -10$ , $b_5 = -10$

Mevcut (Başlangıç) Temel Yaylar:
- $(1,2)$ yayı: Akış ( $x_{12}$ ) = 20, Birim Maliyet ( $c_{12}$ ) = 2
- $(2,3)$ yayı: Akış ( $x_{23}$ ) = 20, Birim Maliyet ( $c_{23}$ ) = 3
- $(3,4)$ yayı: Akış ( $x_{34}$ ) = 10, Birim Maliyet ( $c_{34}$ ) = 4
- $(3,5)$ yayı: Akış ( $x_{35}$ ) = 10, Birim Maliyet ( $c_{35}$ ) = 5

Temel Dışı (Alternatif) Yaylar ve Maliyetleri:
- $(1,3)$ yayı: Birim Maliyet ( $c_{13}$ ) = 6
- $(2,4)$ yayı: Birim Maliyet ( $c_{24}$ ) = 6
- $(2,5)$ yayı: Birim Maliyet ( $c_{25}$ ) = 9

Şebekedeki tüm yayların kapasiteleri, olası akış transferlerini kısıtlamayacak kadar yeterince büyüktür ( $u_{ij} \ge 30$ ).

Verilen bu başlangıç temel uygun çözümü üzerinden Şebeke Simpleks algoritması kullanılarak optimum akış planı elde edildiğinde, şebekedeki minimum toplam pompalama maliyeti kaç birim olur?

130

170

180

190

200

Show answer & explanation

Answer: 180

Answer

Optimum akış planında şebekedeki minimum toplam taşıma maliyeti 180 birim olacaktır.

Şebeke simpleks algoritmasının başlangıç adımında, temel yayların birim maliyetleri kullanılarak düğüm potansiyelleri (u_1=0, u_2=2, u_3=5, u_4=9, u_5=10) hesaplanır. Temel dışı (2,4) yayının indirgenmiş maliyeti c_24 + u_2 - u_4 = 6 + 2 - 9 = -1 olarak bulunur ve bu yay temel çözüme dahil edilir. Bu yay eklendiğinde 2 -> 4 -> 3 -> 2 şeklinde bir çevrim oluşur. Akış aktarımı, sıfırlanacak olan ilk temel yay tarafından (x_34 = 10 birim) sınırlanır. Toplam maliyet, aktarılan birim (10) ile indirgenmiş maliyetin mutlak değerinin (1) çarpımı kadar (10 birim) azalır. Başlangıç maliyeti 190 olduğundan yeni minimum maliyet 180 olur. Sonraki potansiyel kontrollerinde tüm indirgenmiş maliyetler pozitif çıktığından bu çözüm optimaldir.

Step-by-Step Solution

1

Başlangıç temel uygun çözümünün toplam maliyetini hesaplayın.

Z_0 = (20 * 2) + (20 * 3) + (10 * 4) + (10 * 5) = 40 + 60 + 40 + 50 = 190 birim.

Mevcut durumu ve referans maliyetini belirlemek için başlangıç akışları ile birim maliyetler çarpılarak toplanır.

2

Düğüm potansiyellerini (simpleks çarpanları, u_i) belirleyin.

u_1 = 0 atanır. Temel yaylar için u_i + c_ij = u_j eşitliği kullanılır: u_2 = 0 + 2 = 2; u_3 = 2 + 3 = 5; u_4 = 5 + 4 = 9; u_5 = 5 + 5 = 10.

Temel dışı yayların optimalliğini test etmek üzere indirgenmiş maliyetleri hesaplamak için düğüm potansiyellerine ihtiyaç vardır.

3

Temel dışı yayların indirgenmiş maliyetlerini (c_ij_bar) hesaplayın ve giren yayı belirleyin.

c_13_bar = 6 + 0 - 5 = +1. c_24_bar = 6 + 2 - 9 = -1. c_25_bar = 9 + 2 - 10 = +1. c_24_bar negatif olduğu için (2,4) yayı çözüme girer.

Minimum maliyet problemi olduğu için, indirgenmiş maliyeti negatif olan yay çözümü iyileştirir (maliyeti düşürür).

4

(2,4) yayını temel çözüme ekleyerek oluşacak çevrimi (loop) ve aktarılacak maksimum akış miktarını belirleyin.

Oluşan çevrim: 2 -> 4 -> 3 -> 2 şeklindedir. Akış değişimleri: x_24 = +Delta, x_34 = 10 - Delta, x_23 = 20 - Delta. Negatif olmama kısıtından dolayı Max Delta = 10 olur.

Giren yayın şebeke dengesini bozmaması için çevrim üzerindeki ters yönlü akışların kapasiteyi aşmadan azaltılması gerekir. Darboğaz x_34 yayındadır.

5

Yeni maliyeti hesaplayın ve çözümün optimalliğini doğrulayın.

Maliyet azalışı = Delta * |c_24_bar| = 10 * |-1| = 10 birim. Yeni maliyet: 190 - 10 = 180 birim. Yeni çarpanlar ile tüm temel dışı yayların indirgenmiş maliyetleri pozitif olduğundan çözüm optimaldir.

Optimum durum, iterasyon sonucunda hiçbir temel dışı yayın negatif indirgenmiş maliyete sahip olmaması ile kanıtlanır.

Key Concept

Şebeke Simpleks Algoritmasında Düğüm Potansiyelleri ve İndirgenmiş Maliyet Analizi

Question 10Question →

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 $40$ birim malzeme arzı bulunmakta olup, Düğüm 4'ün $15$ birim, Düğüm 5'in ise $25$ 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)$ birim gönderim maliyetleri ( $c_{ij}$ ) ve kapasiteleri ( $u_{ij}$ ) sırasıyla $(c_{ij}, u_{ij})$ biçiminde aşağıdaki tabloda verilmiştir:

Hat $(i, j)$	Birim Maliyet ( $c_{ij}$ )	Kapasite ( $u_{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?

265

305

320

350

370

Show answer & explanation

Answer: 320

Answer

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 \rightarrow 2 \rightarrow 3 \rightarrow 5

rotasından 15 birim (105 ₺),

1 \rightarrow 3 \rightarrow 5

rotasından 10 birim (90 ₺); Düğüm 4 için

1 \rightarrow 3 \rightarrow 4

rotasından 10 birim (80 ₺) ve

1 \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.

Step-by-Step Solution

1

Düğüm 5'in 25 birimlik talebini en ucuz yoldan karşılamaya başla.

Düğüm 5'e giden en ucuz yol

1 \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 \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 \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 \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 \rightarrow 2 \rightarrow 3 \rightarrow 4

yolu kullanılamaz çünkü (2, 3) hattı doludur. Kullanılabilir en ucuz yol

1 \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 \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 \rightarrow 2 \rightarrow 4

'tür (Birim maliyet: 2+7 = 9 ₺). Bu yoldan kalan 5 birim gönderilir. Maliyet:

5 \times 9 = 45

₺. Toplam Maliyet:

105 + 90 + 80 + 45 = 320

₺.

Tüm talepler (15 + 25 = 40) arzla (40) eşleşti ve kapasiteler aşılmadan optimum maliyet bulundu.

Key Concept

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

Alternative Method

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.

Estimated Time:2m 30s

Question 11Question →

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 ( $u_{ij}$ ) ve 1 Terabayt verinin aktarım maliyetleri ( $c_{ij}$ Bin TL) aşağıdaki tabloda verilmiştir:

| Bağlantı ( $i \rightarrow j$ ) | Kapasite ( $u_{ij}$ ) | Birim Maliyet ( $c_{ij}$ )
| :---: | :---: | :---: |
| $1 \rightarrow 2$ | 20 | 2 |
| $1 \rightarrow 3$ | 25 | 5 |
| $2 \rightarrow 3$ | 15 | 1 |
| $2 \rightarrow 4$ | 15 | 6 |
| $3 \rightarrow 4$ | 10 | 3 |
| $3 \rightarrow 5$ | 20 | 4 |
| $4 \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?

200

230

240

250

260

Show answer & explanation

Answer: 230

Answer

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:

x_{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.

Step-by-Step Solution

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 \rightarrow 2

hattının maliyeti 2,

1 \rightarrow 3

hattının maliyeti 5'tir. Maksimum akışı ucuz olan

1 \rightarrow 2

hattına veririz:

x_{12} = 20

(kapasite doldu). Kalan 10 TB veriyi zorunlu olarak

1 \rightarrow 3

hattına veririz:

x_{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 \rightarrow 3

(maliyet 1) ve

2 \rightarrow 4

(maliyet 6). En ucuz olan

2 \rightarrow 3

hattına kapasitesi kadar (

x_{23} = 15

) yönlendiririz. Kalan 5 TB veriyi

2 \rightarrow 4

hattına yönlendiririz (

x_{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 \rightarrow 4

hattından sadece 5 TB gönderilir (

x_{34} = 5

). Düğüm 3'te kalan 20 TB veri

3 \rightarrow 5

hattından gönderilir (

x_{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 \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.

Key Concept

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

Question 12Question →

Bir kamu lojistik şebekesinde $1$ numaralı düğümden (arz kaynağı) $4$ numaralı düğüme (talep merkezi) toplam $12$ birimlik ürün sevkiyatı planlanmaktadır. Şebekedeki düğümler arasındaki birim taşıma maliyetleri ( $c_{ij}$ ) ve yay kapasiteleri ( $u_{ij}$ ) aşağıdaki tabloda sunulmuştur:

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

Bu şebeke modelinde toplam arzın tamamının karşılanması koşuluyla gerçekleştirilebilecek minimum toplam akış maliyeti kaç birimdir?

105

96

108

112

115

Show answer & explanation

Answer: 105

Answer

Şebeke üzerindeki kapasite kısıtları altında minimum maliyetli akış dağıtımı yapıldığında toplam maliyet 105 birimdir.

Minimum maliyetli akış probleminde, kapasite kısıtları ihlal edilmeden en düşük birim maliyetli yollara öncelik verilir. Yapılan hesaplamada, 8 birim maliyetli yola 5 birim, 9 birim maliyetli yola 5 birim ve 10 birim maliyetli yola 2 birim akış atanarak toplam 105 birimlik optimum maliyete ulaşılmıştır.

Step-by-Step Solution

1

Olası yolların ve birim maliyetlerin belirlenmesi

Yol 1:

1 \rightarrow 2 \rightarrow 3 \rightarrow 4

(Maliyet:

3+1+4=8

), Yol 2:

1 \rightarrow 3 \rightarrow 4

(Maliyet:

5+4=9

), Yol 3:

1 \rightarrow 2 \rightarrow 4

(Maliyet:

3+7=10

).

Minimum maliyetli akış için en ucuz yolları önceliklendirmek gerekir.

2

En ucuz yol (Yol 1) için akış ataması

Kapasite:

\min(u_{12}, u_{23}, u_{34}) = \min(10, 5, 10) = 5

birim. Akış:

5

birim, Maliyet:

5 \times 8 = 40

.

En düşük maliyetli yola kapasitesi kadar akış gönderilir.

3

İkinci en ucuz yol (Yol 2) için kalan kapasite üzerinden akış ataması

Kalan arz:

12 - 5 = 7

. Yol 2 kapasitesi:

\min(u_{13}, \text{kalan } u_{34}) = \min(8, 10-5) = 5

birim. Akış:

5

birim, Maliyet:

5 \times 9 = 45

.

Yaylar üzerindeki kalan kapasiteler kontrol edilerek akış devam ettirilir.

4

Kalan arzın uygun yola (Yol 3) atanması

Kalan arz:

7 - 5 = 2

. Yol 3 uygunluğu:

\min(\text{kalan } u_{12}, u_{24}) = \min(10-5, 10) = 5

. Akış:

2

birim, Maliyet:

2 \times 10 = 20

.

Tüm arzın hedefe ulaşması sağlanır.

5

Toplam maliyetin hesaplanması

Toplam Maliyet =

40 + 45 + 20 = 105

.

Tüm akışların maliyetleri toplanarak sonuca ulaşılır.

Key Concept

Minimum maliyetli akış problemleri, hem kapasite kısıtlarını hem de birim taşıma maliyetlerini optimize ederek toplam maliyeti minimize etmeyi amaçlar.

Question 13Question →

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. $1$ numaralı düğüm $20$ tonluk arza sahip ana depodur. $4$ ve $5$ numaralı düğümler ise sırasıyla $8$ ton ve $12$ ton çadır talebi olan afet bölgeleridir. $2$ ve $3$ 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 \rightarrow 2$	$15$	$2$
$1 \rightarrow 3$	$10$	$5$
$2 \rightarrow 3$	$5$	$1$
$2 \rightarrow 4$	$10$	$4$
$3 \rightarrow 4$	$10$	$2$
$3 \rightarrow 5$	$15$	$3$
$4 \rightarrow 5$	$5$	$1$

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?

112

124

132

134

142

Show answer & explanation

Answer: 132

Answer

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.

Step-by-Step Solution

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 \rightarrow 2)

yayından 15 ton,

(1 \rightarrow 3)

yayından 5 ton gönderilir.

(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 \rightarrow 3)

yayına aktarılmak zorundadır.

2

Düğüm 2'ye ulaşan 15 tonluk akışın yönlendirilmesi.

(2 \rightarrow 3)

yayından 5 ton,

(2 \rightarrow 4)

yayından 10 ton akış gerçekleşir.

Düğüm 2'den çıkışta en ucuz yol olan

(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 \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 \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 \rightarrow 5)

yayıdır.

4

Düğüm 3'teki toplam birikimin Düğüm 5'in kalan talebini karşılaması.

(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 \rightarrow 5)

yayı ile kapatılır.

5

Zorunlu rotalar üzerinden toplam maliyetin hesaplanması.

Toplam Maliyet =

132

TL olarak bulunur.

Belirlenen akışlar birim maliyetlerle çarpılır:

(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.

Key Concept

Minimum Maliyetli Akış Problemlerinde Kapasite Darboğazları

Alternative Method

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.

Minimum Maliyetli Akış Problemi

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method