Şebeke Analizi

73 soru

Bir lojistik ağının yöneylem araştırması teknikleriyle modellenmesi sürecinde, başlangıç (kaynak) ve varış (kuyu) noktaları dışında kalan tüm ara merkezler (aktarma düğümleri) için özel bir matematiksel denklik kurulur. Bu denklik, bir ara merkeze dışarıdan gelen toplam ürün miktarı ile o merkezden diğer noktalara gönderilen toplam ürün miktarının birbirine tam olarak eşit olmasını zorunlu kılar.

Şebeke analizi terminolojisinde, sistemdeki aktarma düğümleri için kurulan ve sistemde madde kaybı veya yoktan var olma durumunu engelleyen bu temel kural aşağıdakilerden hangisidir?

Akışın korunumu kısıtı

Maksimum kapasite kısıtı

Yapay merkez denge kısıtı

Kapalı çevrim kısıtı

Cevabı ve açıklamayı göster

Cevap: Akışın korunumu kısıtı

Cevap

Akışın korunumu kısıtı

Şebeke modellerinde aktarma (ara) düğümlerine giren toplam akış miktarı ile bu düğümlerden çıkan toplam akış miktarının birbirine eşit olması zorunluluğu 'akışın korunumu kısıtı' olarak adlandırılır. Bu durum matematiksel olarak

\sum x_{ij} - \sum x_{ki} = 0

şeklinde ifade edilir ve sistemin dengesini sağlar.

Adım Adım Çözüm

Soru metnindeki kısıtın işlevini analiz etmek.

Soruda bahsedilen kuralın, ara düğümlere giren toplam ürün ile çıkan toplam ürünün eşit olmasını sağladığı belirlenmiştir.

Yöneylem şebeke modellerinde bu eşitliği sağlayan temel kavramın tanımlanması hedeflenmektedir.

Şebeke analizi terminolojisindeki karşılığını bulmak.

Bir düğümde akışın kaybolmaması veya yaratılmamasını garantileyen (Giren Akış = Çıkan Akış) bu matematiksel eşitlik, 'akışın korunumu' prensibidir.

Diğer seçenekler ayrıt kapasiteleri veya spesifik algoritma adımları ile ilgilidir.

Anahtar Kavram

Akışın Korunumu Prensibi (Conservation of Flow)

Soru 42Soru →

Ulaştırma ve Altyapı Bakanlığı tarafından yürütülen 'Akıllı Otoyol' projesi kapsamında, güzergâh üzerindeki 6 farklı kontrol istasyonu ( $M_1, M_2, M_3, M_4, M_5$ ve $M_6$ ) arasında yeraltı fiber optik haberleşme ağı kurulması planlanmaktadır.

İstasyonlar arasındaki olası kablo güzergâhları ve bu güzergâhların tahmini kurulum maliyetleri (yüz bin TL cinsinden) aşağıdaki tabloda verilmiştir:

Güzergâh	Maliyet (Yüz Bin TL)
$M_4 - M_5$	5
$M_1 - M_2$	6
$M_1 - M_3$	7
$M_1 - M_4$	8
$M_5 - M_6$	9
$M_2 - M_3$	10
$M_3 - M_4$	11
$M_4 - M_6$	12
$M_2 - M_6$	15

Projenin amacı, tüm istasyonları birbirine bağlayan kesintisiz bir ağ kurarken toplam kurulum maliyetini en aza indirmektir.

Buna göre, kurulacak olan en düşük maliyetli fiber optik ağın toplam maliyeti kaç yüz bin TL olur?

Cevabı ve açıklamayı göster

Cevap: 35

Cevap

En küçük yayılan ağacın toplam maliyeti 35 yüz bin TL'dir.

Doğru çözüm, Kruskal algoritması uygulanarak maliyetlerin küçükten büyüğe sıralanması ve çevrim oluşturmayan ilk 5 kenarın (5, 6, 7, 8 ve 9 maliyetli kenarlar) seçilmesiyle elde edilir. Bu kenarların toplamı 35'tir.

Adım Adım Çözüm

Problemin türünü belirleme.

Tüm düğümleri (istasyonları) birbirine bağlayan ve toplam kenar ağırlığı (maliyeti) en düşük olan yapıyı bulmamız gerektiğinden, bu bir 'En Küçük Yayılan Ağaç (Minimum Spanning Tree)' problemidir.

Kesintisiz bir haberleşme ağı kurmak ve bunu minimum maliyetle yapmak En Küçük Yayılan Ağaç problemi modelini gerektirir.

Kruskal algoritmasını uygulamak için kenarları maliyetlerine göre küçükten büyüğe sıralama.

Sıralama: (M4-M5)=5, (M1-M2)=6, (M1-M3)=7, (M1-M4)=8, (M5-M6)=9, (M2-M3)=10, (M3-M4)=11, (M4-M6)=12, (M2-M6)=15.

Kruskal algoritması, döngü oluşturmamak şartıyla her adımda en düşük maliyetli kenarın ağa eklenmesi prensibiyle çalışır.

Çevrim (döngü) oluşturmayacak şekilde en düşük maliyetli kenarları seçerek ağı oluşturma (N=6 düğüm için N-1=5 kenar seçilmelidir).

1. Kenar:

M_4 - M_5

(5) seçildi.
2. Kenar:

M_1 - M_2

(6) seçildi.
3. Kenar:

M_1 - M_3

(7) seçildi.
4. Kenar:

M_1 - M_4

(8) seçildi.
5. Kenar:

M_5 - M_6

(9) seçildi.
Sonraki en küçük kenar olan

M_2 - M_3

(10) seçilseydi

M_1-M_2-M_3

arasında döngü oluşacaktı. 5 kenara ulaşıldığı ve tüm düğümler bağlandığı için işlem tamamlandı.

Bir ağaçta döngü bulunamaz ve 6 düğümlü bir sistemin tam olarak bağlanması için tam olarak 5 kenar gerekir.

Seçilen kenarların maliyetlerini toplama.

Toplam Maliyet = 5 + 6 + 7 + 8 + 9 = 35 yüz bin TL.

En Küçük Yayılan Ağacın (MST) toplam değeri, seçilen optimum kenarların ağırlıkları toplamıdır.

Anahtar Kavram

En Küçük Yayılan Ağaç problemi (Minimum Spanning Tree), bir şebekedeki tüm düğümleri döngü yaratmadan birbirine bağlayan en düşük toplam ağırlıklı kenar kümesini bulmayı amaçlar.

Soru 43Soru →

Büyükşehir belediyesi tarafından yürütülen 'Akıllı Şehir Trafik Entegrasyon Sistemi' projesine ait faaliyetler, bu faaliyetlerin öncel ilişkileri ve süreleri (gün) aşağıdaki tabloda verilmiştir:

Faaliyet	Öncel Faaliyet(ler)	Süre (Gün)
A	-	3
B	A	6
C	A	8
D	B	5
E	B	4
F	C, E	6
G	D, F	4
H	C	5
I	G, H	2

Buna göre, C faaliyetinin serbest bolluğu (SB) ile D faaliyetinin toplam bolluğu (TB) sırasıyla kaç gündür?

0

gün;

5

gün

2

gün;

5

gün

2

gün;

0

gün

0

gün;

0

gün

8

gün;

5

gün

Cevabı ve açıklamayı göster

Cevap: $0$ gün; $5$ gün

Cevap

İstenilen değerler sırasıyla

0

gün ve

5

gün'dür.

C faaliyetinin Serbest Bolluğu hesaplanırken kendisini takip eden F ve H faaliyetlerine bakılır. C'nin erken bitişi 11'dir. H faaliyeti başka önceli olmadığı için erken başlama zamanı olarak doğrudan 11'i alır. Dolayısıyla C faaliyetinde yaşanacak en ufak bir gecikme H faaliyetinin erken başlamasını öteleyecektir. Bu nedenle C'nin Serbest Bolluğu (

11 - 11

) 0 gündür. D faaliyetinin Toplam Bolluğu ise, geç bitişi (19) ile erken bitişi (14) arasındaki fark alınarak (

19 - 14

) 5 gün olarak hesaplanır.

Adım Adım Çözüm

Tüm faaliyetlerin Erken Başlama (EB) ve Erken Bitiş (EBt) zamanlarını ileri doğru hesaplama ile bulma

A(EB:0, EBt:3), B(EB:3, EBt:9), C(EB:3, EBt:11), D(EB:9, EBt:14), E(EB:9, EBt:13), F(EB:13, EBt:19), G(EB:19, EBt:23), H(EB:11, EBt:16), I(EB:23, EBt:25)

Proje tamamlanma süresini ve faaliyetlerin en erken bitiş zamanlarını tespit etmek.

Kritik yolu belirleyip, geriye doğru hesaplama ile Geç Başlama (GB) ve Geç Bitiş (GBt) zamanlarını bulma

Proje 25 günde biter. I(GB:23, GBt:25), G(GB:19, GBt:23), H(GB:18, GBt:23), F(GB:13, GBt:19), D(GB:14, GBt:19), E(GB:9, GBt:13), C(GB:5, GBt:13). Kritik yol: A-B-E-F-G-I.

Toplam bolluk (TB) hesaplaması için faaliyetlerin geç bitiş zamanlarına ihtiyaç vardır.

C faaliyetinin Serbest Bolluğunu (SB) hesaplama

C'yi takip eden faaliyetler F ve H'dir.

SB = \min(EB_{F}, EB_{H}) - EBt_{C}

. F'nin EB=13, H'nin EB=11, C'nin EBt=11'dir.

SB = \min(13, 11) - 11 = 11 - 11 = 0

gün.

Serbest bolluk, bir faaliyetin kendisini takip eden faaliyetlerin en erken başlama zamanlarını geciktirmeden kullanabileceği esneklik payıdır.

D faaliyetinin Toplam Bolluğunu (TB) hesaplama

D'nin geç bitişi (GBt) 19, erken bitişi (EBt) 14'tür.

TB = GBt - EBt = 19 - 14 = 5

gün.

Toplam bolluk, bir faaliyetin projenin genel tamamlanma süresini geciktirmeden kullanabileceği maksimum gecikme payıdır.

Anahtar Kavram

CPM Ağında Serbest ve Toplam Bolluk Analizi

Soru 44Soru →

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

Cevabı ve açıklamayı göster

Cevap: 180

Cevap

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.

Adım Adım Çözüm

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.

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.

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

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

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.

Anahtar Kavram

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

Soru 45Soru →

Bir savunma sanayii firmasında yeni nesil bir insansız deniz aracı (İDA) prototipinin geliştirilmesi projesinde yer alan faaliyetler, öncül ilişkileri ve hafta cinsinden zaman tahminleri (iyimser ( $a$ ), en olası ( $m$ ), kötümser ( $b$ )) aşağıdaki tabloda verilmiştir:

Faaliyet	Öncül Faaliyet	İyimser Zaman ( $a$ )	En Olası Zaman ( $m$ )	Kötümser Zaman ( $b$ )
A	-	1	4	7
B	-	3	6	9
C	A	2	8	14
D	A, B	5	8	17
E	C, D	2	5	14

Proje yöneticisi, projenin belirli bir $X$ haftasında (veya daha kısa sürede) tamamlanma olasılığını $\%84,13$ olarak üst yönetime raporlamıştır.

Buna göre, proje yöneticisinin raporladığı $X$ süresi ve projenin kritik yol varyansı ( $\sigma_{cp}^2$ ) sırasıyla aşağıdakilerden hangisidir?
(Standart normal dağılım tablosundan bazı değerler: $P(Z \le 0,5) = 0,6915$ ; $P(Z \le 1,0) = 0,8413$ ; $P(Z \le 1,5) = 0,9332$ ; $P(Z \le 2,0) = 0,9772$ )

24 hafta; 9

22 hafta; 9

26 hafta; 5

30 hafta; 9

21 hafta; 14

Cevabı ve açıklamayı göster

Cevap: 24 hafta; 9

Cevap

Raporlanan X süresi 24 hafta ve kritik yol varyansı 9'dur.

Faaliyetlerin beklenen süreleri (te) sırasıyla A=4, B=6, C=8, D=9, E=6 haftadır. Varyanslar ise A=1, B=1, C=4, D=4, E=4 olarak bulunur. Ağ şebekesi çizildiğinde, D faaliyeti A (bitiş 4) ve B (bitiş 6) faaliyetlerini beklediği için 6. haftada başlar. Kritik yol en uzun süreli yol olan B-D-E yoludur ve beklenen proje süresi Te = 6+9+6 = 21 haftadır. Kritik yol varyansı B, D ve E'nin varyansları toplamı olan 1+4+4=9'dur. Standart sapma 3'tür. P(Z) = 0,8413 için Z=1,0 alınır. Z = (X - Te)/σ formülünden 1,0 = (X - 21)/3 denklemi kurulur ve X = 24 hafta bulunur.

Adım Adım Çözüm

Her faaliyetin beklenen süresini (

t_e = \frac{a+4m+b}{6}

) ve varyansını (

\sigma^2 = (\frac{b-a}{6})^2

) hesaplayın.

t_e(A)=4, \sigma^2_A=1

;

t_e(B)=6, \sigma^2_B=1

;

t_e(C)=8, \sigma^2_C=4

;

t_e(D)=9, \sigma^2_D=4

;

t_e(E)=6, \sigma^2_E=4

elde edilir.

PERT analizinde ağ şebekesini kurabilmek ve proje varyansını bulabilmek için bu değerler temel girdilerdir.

Şebeke ağını oluşturarak faaliyetlerin erken başlama zamanlarını belirleyin ve kritik yolu bulun.

D faaliyeti başlamak için hem A (4. haftada biter) hem de B (6. haftada biter) faaliyetlerini bekler. Bu yüzden D ancak 6. haftada başlayabilir. En uzun yol B-D-E yoludur ve proje beklenen süresi

T_e = 6 + 9 + 6 = 21

haftadır.

Projenin toplam süresini belirleyen şey paralel giden kollar arasındaki en uzun (gecikmesiz) yoldur.

Kritik yol varyansını ve projenin standart sapmasını hesaplayın.

Kritik yol varyansı

\sigma_{cp}^2 = \sigma_B^2 + \sigma_D^2 + \sigma_E^2 = 1 + 4 + 4 = 9

'dur. Projenin standart sapması ise

\sigma_{cp} = \sqrt{9} = 3

haftadır.

Projenin tamamlanma olasılığı hesaplamalarında sadece kritik yol üzerindeki faaliyetlerin varyansları toplanır.

Verilen olasılık değeri için Z tablosundan Z değerini bulun ve formülü kullanarak X süresini hesaplayın.

\%84,13

olasılık için

Z = 1,0

'dır.

Z = \frac{X - T_e}{\sigma_{cp}}

denkleminden

1,0 = \frac{X - 21}{3} \implies X = 21 + 3 = 24

hafta olarak bulunur.

Olasılık değeri verildiğinde hedef süreyi bulmak için normal dağılım denklemi tersten işletilir.

Anahtar Kavram

PERT Yönteminde Kritik Yol, Varyans ve Tamamlanma Olasılığı

Soru 46Soru →

Bir ulusal demiryolu şirketi, 7 farklı lojistik merkezi ( $A, B, C, D, E, F, G$ ) arasında kesintisiz bir yüksek hızlı veri iletişim ağı kurmak istemektedir. Merkezler arası veri hatlarının olası güzergahları ve kurulum maliyetleri (milyon TL) aşağıdaki tabloda verilmiştir:

Hat	Maliyet	Hat	Maliyet
A-B	13	C-E	12
A-C	8	C-F	10
A-D	16	D-F	14
B-C	9	E-F	5
B-E	15	E-G	17
C-D	7	F-G	6

Şebekedeki tüm merkezlerin birbirine bağlanması (herhangi iki merkez arasında bir veri yolu olması) ve toplam kurulum maliyetinin en aza indirilmesi hedeflenmektedir.

Buna göre, optimum şebeke ağı (en küçük yayılan ağaç) oluşturulduğunda, $C$ merkezine doğrudan bağlanan hatların kurulum maliyetleri toplamı kaç milyon TL olur?

Cevabı ve açıklamayı göster

Cevap: 34

Cevap

Optimum ağda C merkezine bağlanan hatların maliyetleri toplamı 34 milyon TL'dir.

Verilen şebeke probleminde Prim veya Kruskal algoritması uygulandığında en küçük yayılan ağaç (MST) şu hatlardan oluşur: E-F (5), F-G (6), C-D (7), A-C (8), B-C (9) ve C-F (10). Oluşan bu optimal ağaç topolojisinde, C düğümü merkezî bir köprü görevi görerek A, B, D ve F düğümlerine doğrudan bağlanmaktadır. Bu dört bağlantının maliyetleri toplamı

7 + 8 + 9 + 10 = 34

milyon TL olarak hesaplanır.

Adım Adım Çözüm

Kruskal veya Prim algoritması kullanarak en düşük maliyetli hatlardan başlayarak çevrim oluşturmayacak şekilde kenarları seçmek.

Sırasıyla E-F (5), F-G (6), C-D (7), A-C (8), B-C (9) hatları ağaca eklenir.

En küçük yayılan ağaç (MST) oluşturmanın temel kuralı, en düşük maliyetli bağlantıları çevrim (döngü) yaratmadan sisteme dahil etmektir.

{A,B,C,D} düğümleri ile {E,F,G} düğümlerini birbirine bağlayacak en düşük maliyetli hattı belirlemek.

Kalan olası bağlantılar arasından en düşük maliyetli olan C-F (10) hattı seçilir ve tüm şebeke birbirine bağlanmış olur.

Şebekenin iki ayrı parçasını (alt ağacı) birleştirmek için aralarındaki en kısa (en ucuz) köprü kullanılmalıdır.

Oluşturulan en küçük yayılan ağaç üzerinde sadece C merkezine doğrudan temas eden hatları bulup maliyetlerini toplamak.

C merkezine bağlanan hatlar: C-D (7), A-C (8), B-C (9) ve C-F (10). Toplam = 7 + 8 + 9 + 10 = 34.

Soru bizden tüm ağın maliyetini değil, ağaç yapısı oluştuktan sonra spesifik olarak C düğümündeki fiziksel bağlantı yükünü (maliyetini) istemektedir.

Anahtar Kavram

En Küçük Yayılan Ağaç (Minimum Spanning Tree) Problemi ve Topoloji Analizi

Soru 47Soru →

Bir yöneylem araştırması uzmanı, bir tedarik zinciri ağında üretim (kaynak) ile tüketim (kuyu) merkezleri arasındaki akış kapasitesini sınırlandıran darboğazları tespit etmek istemektedir. Analiz sırasında şebekedeki tüm düğümler kümesi ( $N$ ), kaynak düğümünü içeren bir $X$ alt kümesi ve kuyu düğümünü içeren bir $Y$ alt kümesi olmak üzere ikiye ayrılır. Bu iki alt kümenin kesişimi boş kümedir ( $X \cap Y = \emptyset$ ) ve birleşimleri tüm şebekeyi kapsar ( $X \cup Y = N$ ).

Şebeke analizi terminolojisine göre; başlangıç düğümü $X$ kümesinde, bitiş düğümü ise $Y$ kümesinde yer alan tüm yönlü ayrıtların oluşturduğu ve bu iki küme arasındaki akışı taşıyan özel ayrıt kümesine ne ad verilir?

Kesit

Çevrim

Yayılan ağaç

Artık şebeke

Cevabı ve açıklamayı göster

Cevap: Kesit

Cevap

Verilen matematiksel koşulları (

X \cap Y = \emptyset

X \cup Y = N

) sağlayan ve bu iki küme arasındaki akışı barındıran ayrıtların kümesine 'Kesit' adı verilir.

Kesit (Cut), şebeke analizi terminolojisinde, düğüm kümesini birbirinden ayrık iki alt kümeye (

X

Y

) bölen ve bir kümeden diğerine akışı sağlayan yönlü ayrıtların oluşturduğu özel bir kümedir. Maksimum Akış - Minimum Kesit teoreminde sistemin darboğazını tanımlamak için kullanılır. Soruda verilen

X \cap Y = \emptyset

X \cup Y = N

özellikleri, tam olarak bir kesitin (cut-set) resmi matematiksel tanımıdır.

Adım Adım Çözüm

Şebeke problemlerinde düğümlerin ayrık iki kümeye (

X

Y

) bölünmesi durumunu analiz etme

Düğümlerin tümünü kapsayan ve birbiriyle kesişmeyen bu iki kümenin, şebekeyi iki parçaya ayırdığı tespit edilir.

Sorudaki matematiksel tanımın (

X \cup Y = N

X \cap Y = \emptyset

) hangi ağ yapısını ifade ettiğini belirlemek için.

Bir kümeden (

X

) diğer kümeye (

Y

) giden ayrıtların oluşturduğu yapıyı terminolojik olarak tanımlama

Bu ayrıtların kapasiteleri toplamının, kaynak ile kuyu arasındaki maksimum akışı sınırlayan darboğaz (bottleneck) olduğu belirlenir. Bu yapıya Kesit (Cut) denir.

Şebeke teorisinde akışı kesintiye uğratan veya sınırlandıran temel bölümleme (partition) kavramını adlandırmak için.

Anahtar Kavram

Şebeke Modellerinde Kesit (Cut) Kavramı

Tahmini Süre:1m 0s

Soru 48Soru →

Bir yöneylem araştırması uzmanı, bir enerji dağıtım ağını yönlü bir şebeke (directed network) olarak modellemektedir. Bu şebeke modelinde, herhangi bir $i$ düğümü için akış dengesi (akışın korunumu) denklemi aşağıdaki gibi formüle edilmiştir:

\sum_{j} x_{ji} - \sum_{j} x_{ij} = b_i

Bu denklemde;
$x_{ji}$ : $j$ düğümünden $i$ düğümüne gelen akış miktarını,
$x_{ij}$ : $i$ düğümünden $j$ düğümüne giden akış miktarını,
$b_i$ : $i$ düğümünün net akış değerini göstermektedir.

Modelin incelenmesi sonucunda belirli bir $K$ düğümü için $b_K < 0$ olduğu, bir $M$ düğümü için ise $b_M = 0$ olduğu tespit edilmiştir.

Buna göre, şebeke terminolojisi dikkate alındığında $K$ ve $M$ düğümlerinin türleri sırasıyla aşağıdakilerden hangisinde doğru verilmiştir?

K

: Kaynak düğümü,

M

: Aktarma düğümü

K

: Kuyu düğümü,

M

: Aktarma düğümü

K

: Aktarma düğümü,

M

: Kaynak düğümü

K

: Kaynak düğümü,

M

: Kuyu düğümü

Cevabı ve açıklamayı göster

Cevap: $K$ : Kaynak düğümü, $M$ : Aktarma düğümü

Cevap

K

düğümü bir kaynak düğümü,

M

düğümü ise bir aktarma düğümüdür.

Verilen denklemde

b_i

değeri, düğüme giren toplam akış ile düğümden çıkan toplam akış arasındaki farktır.

K

düğümü için

b_K < 0

olması, (Giren - Çıkan) < 0 eşitsizliğini, dolayısıyla Çıkan > Giren durumunu yaratır. Sisteme net akış üreten bu noktalar 'Kaynak Düğümü' olarak adlandırılır.

M

düğümü için

b_M = 0

olması ise Giren = Çıkan dengesini gösterir. Kendi içinde arzı veya talebi olmayan, sadece üzerinden akış geçen bu noktalar ise 'Aktarma Düğümü' olarak isimlendirilir.

Adım Adım Çözüm

Akış dengesi denklemindeki matematiksel ifadelerin yönlerini yorumlamak.

Denklem (Giren Akış) - (Çıkan Akış) =

b_i

yapısındadır.

Bir düğümün şebekedeki kavramsal rolünü (kaynak, kuyu, aktarma) belirlemek için net akış formülünün işaretini analiz etmek gerekir.

K

düğümünün türünü verilen

b_K < 0

şartına göre belirlemek.

(Giren Akış) - (Çıkan Akış) < 0 olduğundan, Çıkan Akış > Giren Akış eşitsizliği elde edilir. Düğüm sisteme akış sağladığı için

K

bir 'Kaynak Düğümü'dür.

Çıkan akışın giren akıştan daha fazla olması, o spesifik noktanın ağa dışarıdan kapasite (arz) sunduğunu gösterir.

M

düğümünün türünü verilen

b_M = 0

şartına göre belirlemek.

(Giren Akış) - (Çıkan Akış) = 0 olduğundan, Giren Akış = Çıkan Akış eşitliği elde edilir. Bu nedenle

M

bir 'Aktarma Düğümü'dür.

Düğüme giren akış miktarının tamamen düğümden çıkması, o noktada bir üretim veya tüketim olmadığını, sadece geçiş yapıldığını (transshipment) kanıtlar.

Anahtar Kavram

Şebeke modellerinde akış korunumu prensibi ve net akış denklemine göre düğüm türlerinin (kaynak, kuyu, aktarma) matematiksel sınıflandırılması.

Soru 49Soru →

Sağlık Bakanlığı tarafından planlanan bir ihtisas hastanesinin ek hizmet binası inşaatına ait iş paketleri, bu paketler arası öncelik ilişkileri ve öngörülen tamamlanma süreleri (hafta) aşağıdaki tabloda verilmiştir:

Faaliyet Kodu	Faaliyet Adı	Öncel Faaliyetler	Süre (Hafta)
A	İhale Sürecinin Tamamlanması	-	3
B	Altyapı Hazırlıkları	A	4
C	İklimlendirme (HVAC) Siparişi	A	5
D	Zemin ve Duvar Kaplamaları	B	3
E	İklimlendirme Kurulumu	C	4
F	Elektrik ve Gaz Tesisatı	B, C	6
G	Tıbbi Ekipman Yerleşimi	D, F	2
H	Son Kontroller ve Ruhsat	E, G	2

Projenin zaman çizelgesi CPM (Kritik Yol Yöntemi) kullanılarak oluşturulacaktır.

Buna göre, "Altyapı Hazırlıkları" (B) faaliyetinin toplam bolluğu (TB) ve serbest bolluğu (SB) sırasıyla aşağıdakilerden hangisinde doğru verilmiştir?

TB = 1 hafta, SB = 0 hafta

TB = 1 hafta, SB = 1 hafta

TB = 0 hafta, SB = 0 hafta

TB = 4 hafta, SB = 0 hafta

TB = 0 hafta, SB = 1 hafta

Cevabı ve açıklamayı göster

Cevap: TB = 1 hafta, SB = 0 hafta

Cevap

B faaliyetinin Toplam Bolluğu (TB) 1 hafta, Serbest Bolluğu (SB) ise 0 haftadır.

Projenin ağ diyagramı çizildiğinde B faaliyetinin ardılları D ve F faaliyetleridir. B'nin en erken bitiş süresi (EF) 3+4=7 haftadır. B'yi izleyen D faaliyetinin en erken başlama süresi (ES) 7, F faaliyetinin en erken başlama süresi (ES) ise B ve C'nin bitiş sürelerinin maksimumu (max(7,8)) olan 8 haftadır. Geriye doğru hesaplamada, D'nin en geç başlama süresi (LS) 11, F'nin en geç başlama süresi (LS) 8 haftadır. Bu durumda B'nin en geç bitiş süresi (LF) ardıllarının minimum LS değeri olan 8'dir. Toplam Bolluk = LF - EF = 8 - 7 = 1 hafta bulunur. Serbest Bolluk ise ardılların ES değerlerinin minimumundan kendi EF değerinin çıkarılmasıyla bulunur: min(7, 8) - 7 = 0 hafta. Dolayısıyla doğru yanıt TB = 1, SB = 0'dır.

Adım Adım Çözüm

Tüm faaliyetler için ileri yönlü hesaplama yaparak En Erken Başlama (ES) ve En Erken Bitiş (EF) zamanlarını bul.

A(ES:0, EF:3), B(ES:3, EF:7), C(ES:3, EF:8), D(ES:7, EF:10), E(ES:8, EF:12), F(ES:8, EF:14), G(ES:14, EF:16), H(ES:16, EF:18). Proje 18 haftada tamamlanır.

Kritik yolu ve faaliyetlerin proje süresine etkisini belirlemek için ağ üzerindeki en erken gerçekleşme zamanları saptanmalıdır.

Proje bitiş süresinden (18) başlayarak geriye yönlü hesaplama yap ve En Geç Başlama (LS) ile En Geç Bitiş (LF) zamanlarını bul.

H(LF:18, LS:16), G(LF:16, LS:14), E(LF:16, LS:12), F(LF:14, LS:8), D(LF:14, LS:11). B'nin izleyenleri D ve F'dir. B'nin LF değeri = min(LS_D, LS_F) = min(11, 8) = 8'dir. LS_B = 8 - 4 = 4 olur.

Her bir faaliyetin projeyi geciktirmeden başlayabileceği ve bitebileceği en son zamanları bulmak bolluk hesaplaması için zorunludur.

B faaliyeti için Toplam Bolluk (TB) ve Serbest Bolluk (SB) değerlerini formüllerle hesapla.

TB = LF_B - EF_B = 8 - 7 = 1 hafta. SB = min(ES_D, ES_F) - EF_B = min(7, 8) - 7 = 7 - 7 = 0 hafta.

Toplam bolluk faaliyetin kendi esnekliğini, serbest bolluk ise kendinden sonraki faaliyetleri etkilemeden sahip olduğu esnekliği verir.

Anahtar Kavram

CPM'de En Erken ve En Geç Zamanların Hesaplanması ile Bolluk Analizi

Soru 50Soru →

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

Cevabı ve açıklamayı göster

Cevap: 320

Cevap

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.

Adım Adım Çözüm

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.

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.

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.

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.

Anahtar Kavram

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

Alternatif Yöntem

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.

Tahmini Süre:2m 30s

Soru 51Soru →

Afet ve Acil Durum Yönetimi Başkanlığı (AFAD) tarafından yürütülen 'Ulusal Afet Erken Uyarı Sistemi Kurulum Projesi'ne ait faaliyetler, bu faaliyetlerin öncel ilişkileri ve öngörülen süreleri (hafta) aşağıdaki tabloda verilmiştir:

Faaliyet	Öncel Faaliyet(ler)	Süre (Hafta)
A	-	4
B	-	6
C	A	5
D	A, B	7
E	C	8
F	B	4
G	D, F	6
H	E, G	3

CPM (Kritik Yol Yöntemi) kullanılarak proje ağı modellendiğinde, C faaliyetinin toplam bolluğu (TB) ile F faaliyetinin serbest bolluğu (SB) sırasıyla aşağıdakilerin hangisinde doğru verilmiştir?

2 hafta ; 3 hafta

0 hafta ; 3 hafta

4 hafta ; 3 hafta

2 hafta ; 0 hafta

3 hafta ; 2 hafta

Cevabı ve açıklamayı göster

Cevap: 2 hafta ; 3 hafta

Cevap

İstenen değerler doğru sırasıyla '2 hafta ; 3 hafta' şeklindedir.

İleriye doğru hesaplama yapıldığında, B (6) > D (7) > G (6) > H (3) rotası 22 hafta ile kritik yol olarak belirlenir. C faaliyetinin ağ üzerindeki konumuna bakıldığında; A'dan sonra başlar (

ES=4

), 5 hafta sürer (

EF=9

). Kendisini izleyen E faaliyetinin en geç başlama zamanı (

LS=11

) olduğu için C'nin en geç bitiş zamanı (

LF=11

) olur. Bu durumda C'nin Toplam Bolluğu (

TB = LF - EF = 11 - 9 = 2

) haftadır. F faaliyeti ise B'den sonra başlar (

ES=6

), 4 hafta sürer (

EF=10

). F'yi izleyen G faaliyetinin başlayabilmesi için D'nin de (13. haftada) bitmesi gerektiğinden G'nin en erken başlama zamanı

ES=13

'tür. F faaliyetinin Serbest Bolluğu (

SB = G'nin ES değeri - F'nin EF değeri = 13 - 10 = 3

) haftadır. İstenen değerler 2 ve 3 haftadır.

Adım Adım Çözüm

İleriye doğru hesaplama (Forward Pass) ile her faaliyetin En Erken Başlama (ES) ve En Erken Bitiş (EF) zamanlarını ile projenin tamamlanma süresini belirleyin.

A(ES:0, EF:4), B(ES:0, EF:6), C(ES:4, EF:9), D(ES:max(4,6)=6, EF:13), E(ES:9, EF:17), F(ES:6, EF:10), G(ES:max(13,10)=13, EF:19), H(ES:max(17,19)=19, EF:22). Proje süresi 22 haftadır.

Faaliyetlerin kendilerinden öncekilerin tamamen bitmesini bekleme kuralı gereği, birleşme noktalarında maksimum EF değerleri alınarak proje süresi tespit edilir.

Geriye doğru hesaplama (Backward Pass) ile her faaliyetin En Geç Bitiş (LF) ve En Geç Başlama (LS) zamanlarını bulun.

H(LF:22, LS:19), E(LF:19, LS:11), G(LF:19, LS:13), C(LF:11, LS:6), D(LF:13, LS:6), F(LF:13, LS:9), A(LF:min(6,6)=6, LS:2), B(LF:min(6,9)=6, LS:0). Kritik yol: B-D-G-H.

Bolluk hesaplamaları için projenin 22 haftada bitmesi koşuluyla faaliyetlerin en geç ne zaman tamamlanabileceği bulunmalıdır.

C faaliyeti için Toplam Bolluk (

TB

) ve F faaliyeti için Serbest Bolluk (

SB

) formüllerini uygulayın.

C için

TB = LF - EF = 11 - 9 = 2

hafta. F için

SB = ES(G) - EF(F) = 13 - 10 = 3

hafta.

TB

, bir faaliyetin proje süresini uzatmadan gecikebileceği maksimum süreyi;

SB

ise kendisini izleyen faaliyetin en erken başlama zamanını etkilemeden gecikebileceği süreyi verir.

Anahtar Kavram

CPM Ağlarında İleri ve Geriye Doğru Hesaplama ile Bolluk Analizi

Soru 52Soru →

Enerji Bakanlığı tarafından yürütülen bir "Boru Hattı Güvenlik Otomasyonu" projesinin planlama aşamasında belirlenen faaliyetler, öncelik ilişkileri ve maliyet bilgileri aşağıdaki tabloda verilmiştir.

Faaliyet	Öncül Faaliyet	Normal Süre (Hafta)	Hızlandırılmış Süre (Hafta)	Normal Maliyet (₺)	Hızlandırılmış Maliyet (₺)
A	-	3	2	10.000	15.000
B	A	4	2	15.000	20.000
C	A	7	5	18.000	24.000
D	B	5	3	25.000	33.000
E	C, D	2	1	8.000	14.000

Mevcut durumda projenin normal sürede tamamlanması öngörülmektedir. Ancak, sisteme acil entegrasyon yapılması gerektiğinden proje teslim süresinin 11 haftaya indirilmesi istenmektedir.

Buna göre, projenin tamamlanma süresini 11 haftaya düşürmek için katlanılması gereken minimum toplam proje maliyeti (normal maliyetler + hızlandırma maliyetleri) kaç ₺ olmalıdır?

84.000

85.000

86.000

87.000

88.000

Cevabı ve açıklamayı göster

Cevap: 86.000

Cevap

Projenin tamamlanma süresini 11 haftaya düşürmek için katlanılması gereken minimum toplam proje maliyeti 86.000 ₺ olmalıdır.

Doğru sonuca ulaşmak için öncelikle normal proje maliyeti 76.000 ₺ olarak hesaplanır. A-B-D-E yolu 14 hafta, A-C-E yolu 12 haftadır. Kritik yol olan A-B-D-E üzerindeki en düşük maliyet eğimine sahip B faaliyeti (2.500 ₺/hafta) maksimum kapasitesi olan 2 hafta hızlandırıldığında, maliyet 5.000 ₺ artar ve her iki yolun süresi 12 haftada eşitlenir. Proje süresini 11 haftaya indirebilmek için her iki yolu da 1 hafta kısaltacak bir müdahale gereklidir. Bu aşamada ortak faaliyetlerden A'nın maliyeti (5.000 ₺), E'nin maliyeti (6.000 ₺) ve C ile D'nin ortak hızlandırılma maliyeti (7.000 ₺) kıyaslanır. En uygun seçenek A faaliyetini 1 hafta hızlandırmaktır. Toplam maliyet

76.000 + 5.000 + 5.000 = 86.000

₺ olur.

Adım Adım Çözüm

Ağ diyagramını oluşturup mevcut yolları ve normal proje süresini hesaplamak.

Yol 1: A - B - D - E

\rightarrow 3 + 4 + 5 + 2 = 14

hafta. Yol 2: A - C - E

\rightarrow 3 + 7 + 2 = 12

hafta. Kritik yol A-B-D-E ve projenin normal süresi 14 haftadır.

Hangi faaliyetlerin hızlandırılacağını belirlemek için öncelikle kritik yolun tespit edilmesi gerekir.

Projenin normal maliyetini ve her bir faaliyetin maliyet eğimini (haftalık hızlandırma maliyeti) hesaplamak.

Normal Maliyet =

10.000 + 15.000 + 18.000 + 25.000 + 8.000 = 76.000

₺. Eğilimler

\rightarrow

A: 5.000 ₺, B: 2.500 ₺, C: 3.000 ₺, D: 4.000 ₺, E: 6.000 ₺.

Minimum maliyetli hızlandırma seçeneklerini değerlendirmek için birim zaman başına maliyet artışı bilinmelidir.

Süreyi 14 haftadan 11 haftaya indirmek için ilk hızlandırmayı yapmak.

Kritik yol (A-B-D-E) üzerindeki en ucuz faaliyet B'dir (2.500 ₺/hafta). B faaliyeti maksimum 2 hafta hızlandırılır. Ek maliyet:

2 \times 2.500 = 5.000

₺. Yeni süreler

\rightarrow

A-B-D-E: 12 hafta, A-C-E: 12 hafta.

Maliyeti en aza indirmek için kritik yol üzerindeki en ucuz faaliyet sınırına kadar hızlandırılır. Bu işlem sonucunda her iki yol da kritik yol haline gelir.

Proje süresini 12 haftadan 11 haftaya indirecek son 1 haftalık hızlandırmayı seçmek.

Her iki yol da 12 hafta olduğundan, süreyi 1 hafta daha düşürmek için ya ortak faaliyetler (A veya E) hızlandırılmalı ya da bağımsız kollar (C ve D) birlikte hızlandırılmalıdır. Maliyetler: A için 5.000 ₺, E için 6.000 ₺, C+D için

3.000+4.000=7.000

₺. En ucuz seçenek A faaliyetini 1 hafta hızlandırmaktır (5.000 ₺).

Birden fazla kritik yol olduğunda, proje süresinin kısalması için tüm kritik yolların eş zamanlı olarak kısaltılması gerekir.

Toplam proje maliyetini hesaplamak.

Toplam Maliyet = Normal Maliyet + Hızlandırma Maliyetleri =

76.000 + 5.000 \text{ (B'den)} + 5.000 \text{ (A'dan)} = 86.000

₺.

İstenen değer proje için katlanılan normal maliyetler ve ilave hızlandırma maliyetlerinin toplamıdır.

Anahtar Kavram

Çoklu kritik yolların varlığında zaman-maliyet analizi ve proje çökertme (crashing) optimizasyonu.

Soru 53Soru →

Milli Uzay Programı kapsamında yürütülen 'Gözlem Uydusu Entegrasyon' projesine ait faaliyetler, öncelik ilişkileri ve süre/maliyet tahminleri aşağıdaki tabloda verilmiştir:

Faaliyet	Öncül Faaliyet	Normal Süre (Hafta)	Hızlandırılmış Süre (Hafta)	Normal Maliyet (TL)	Hızlandırılmış Maliyet (TL)
A	-	6	4	20.000	26.000
B	-	5	3	15.000	19.000
C	A	8	5	30.000	42.000
D	B	7	6	25.000	30.000
E	C, D	4	2	40.000	50.000

Proje yöneticisi, normal şartlarda planlanan proje süresini 15 haftaya indirmek istemektedir.

Buna göre, hedeflenen süreye ulaşmak için katlanılması gereken en düşük ek hızlandırma maliyeti kaç TL'dir?

10.000

12.000

11.000

13.000

14.000

Cevabı ve açıklamayı göster

Cevap: 11.000

Cevap

Doğru cevap 11.000 TL'dir. A faaliyeti 2 hafta, E faaliyeti 1 hafta kısaltılmalıdır.

Projenin başlangıçtaki süresi A-C-E yolu üzerinden 18 haftadır. B-D-E yolu ise 16 haftadır. Projeyi 15 haftaya indirmek için kritik yolu 3 hafta kısaltmalıyız. Maliyet eğimleri hesaplandığında A=3.000, B=2.000, C=4.000, D=5.000, E=5.000 TL/Hafta bulunur. İlk olarak A-C-E yolu üzerindeki en ucuz faaliyet olan A, sınır değeri olan 2 hafta boyunca kısaltılır (Maliyet: 6.000 TL). Bu işlem sonunda A-C-E yolu 16 haftaya düşer ve B-D-E yolu ile eşitlenerek projede iki kritik yol oluşur. Kalan 1 haftayı düşürmek için her iki yolu da etkileyen ortak E faaliyeti 1 hafta kısaltılmalıdır (Maliyet: 5.000 TL). Alternatif olarak A, B, C'den bağımsız kombinasyonlar denense de (Örn: C ve B) maliyet 6.000 TL'ye çıkacaktır. Dolayısıyla en düşük maliyet 6.000 + 5.000 = 11.000 TL'dir.

Adım Adım Çözüm

Ağ diyagramı çizilerek proje yolları ve süreleri hesaplanır.

İki yol bulunur: 1. Yol (A-C-E) = 6+8+4 = 18 hafta. 2. Yol (B-D-E) = 5+7+4 = 16 hafta.

Maliyet optimizasyonu yapabilmek için öncelikle kritik yolu belirlemek şarttır.

Kritik yol ve hedeflenen süre farkı belirlenir.

Kritik Yol: A-C-E yoludur ve proje 18 haftadır. Hedef 15 hafta olduğu için proje toplam 3 hafta kısaltılmalıdır.

Hızlandırma işlemi sadece kritik yol üzerindeki faaliyetlere uygulanır.

Her faaliyetin maliyet eğimi (Haftalık Hızlandırma Maliyeti) hesaplanır.

A: (26k-20k)/2 = 3.000 TL, B: (19k-15k)/2 = 2.000 TL, C: (42k-30k)/3 = 4.000 TL, D: (30k-25k)/1 = 5.000 TL, E: (50k-40k)/2 = 5.000 TL.

Hangi faaliyetin kısaltılacağına karar vermek için birim zaman başına en düşük maliyetin bulunması gerekir.

Kritik yol üzerindeki (A, C, E) en düşük maliyetli faaliyet maksimum düzeyde kısaltılır.

En ucuz faaliyet A'dır (3.000 TL). A faaliyeti maksimum 2 hafta kısaltılır. Maliyet = 2 × 3.000 = 6.000 TL. Yeni yollar: A-C-E = 16 hafta, B-D-E = 16 hafta olur.

Maliyeti minimize etmek için her adımda en ucuz faaliyet seçilmelidir.

Kalan 1 haftalık kısaltma için yeni oluşan çoklu kritik yollar analiz edilir.

Artık iki yol da 16 haftadır. Projeyi 1 hafta kısaltmak için ya ortak faaliyet (E) kısaltılmalıdır (5.000 TL) ya da her iki yoldan birer faaliyet (Örn: C ve B) kısaltılmalıdır (4.000 + 2.000 = 6.000 TL). En uygunu E faaliyetini 1 hafta kısaltmaktır (5.000 TL).

Paralel kritik yolların sürelerini aynı anda düşürmek zorundayız. Ortak kesişim düğümü daha ucuz maliyet sunmaktadır.

Toplam ek hızlandırma maliyeti hesaplanır.

Toplam Maliyet = 6.000 (A'dan) + 5.000 (E'den) = 11.000 TL.

Projenin 15 haftaya inmesi için katlanılan nihai maliyettir.

Anahtar Kavram

Şebeke Modellerinde Proje Çökertme (Crashing) ve Maliyet Eğimi Analizi

Soru 54Soru →

Bir afet yönetimi planlamasında, deprem riski yüksek olan bir bölgeden ( $1$ numaralı düğüm), güvenli toplanma alanına ( $6$ numaralı düğüm) vatandaşların tahliyesi için yönlü bir karayolu ağı kullanılacaktır. Ağ üzerindeki düğümler kavşakları, oklar ise tek yönlü yolları temsil etmektedir.

Yollar ve maksimum taşıma kapasiteleri (saatte bin araç) şu şekildedir:
- $1 \to 2$ : $18$
- $1 \to 3$ : $12$
- $2 \to 4$ : $8$
- $2 \to 5$ : $6$
- $3 \to 2$ : $4$
- $3 \to 5$ : $10$
- $4 \to 6$ : $15$
- $5 \to 4$ : $5$
- $5 \to 6$ : $12$

Buna göre, bu ulaşım ağı kullanılarak riskli bölgeden ( $1$ ) güvenli toplanma alanına ( $6$ ) saatte maksimum kaç bin araç tahliye edilebilir?

Cevabı ve açıklamayı göster

Cevap: 24

Cevap

Maksimum tahliye kapasitesi saatte 24 bin araçtır.

Maksimum akış problemi çözülürken, başlangıç düğümünden hedef düğüme kadar artan yollar aranır veya ağın kapasitesini sınırlayan 'minimum kesit' bulunur. Bu soruda, düğümleri {1, 2, 3} ve {4, 5, 6} şeklinde iki ayrı kümeye ayıran kesit, ağdaki akışı sınırlar. Bu iki küme arasındaki tek yönlü geçişler

2 \to 4

(kapasite: 8),

2 \to 5

(kapasite: 6) ve

3 \to 5

(kapasite: 10) yollarıdır. Toplam darboğaz (min-cut)

8 + 6 + 10 = 24

birim olduğundan maksimum tahliye edilebilir araç sayısı 24 bindir.

Adım Adım Çözüm

Ford-Fulkerson algoritması kullanılarak artan yollar üzerinden akış atanır. İlk olarak en yüksek kapasiteli yol olan

1 \to 2 \to 4 \to 6

yolu seçilir.

Bu yolun darboğaz kapasitesi

\min(18, 8, 15) = 8

birimdir. Akış atandığında kalan kapasiteler:

(1 \to 2): 10

(2 \to 4): 0

(4 \to 6): 7

olur.

Maksimum akışa ulaşmak için öncelikle kapasitesi tükenmemiş geçerli yollar bulunmalıdır.

İkinci bir yol olarak

1 \to 3 \to 5 \to 6

yolu değerlendirilir.

Bu yolun darboğaz kapasitesi

\min(12, 10, 12) = 10

birimdir. Akış atandığında kalan kapasiteler:

(1 \to 3): 2

(3 \to 5): 0

(5 \to 6): 2

olur.

Diğer bağımsız rotalar üzerinden akış artırılmaya devam edilir.

Yeni bir artan yol olan

1 \to 2 \to 5 \to 6

yolu üzerinden akış geçirilir.

Kalan kapasitelere göre bu yolun darboğazı

\min(10, 6, 2) = 2

birimdir. Kalan kapasiteler:

(1 \to 2): 8

(2 \to 5): 4

(5 \to 6): 0

olur.

Ana yollar dolduğunda ara bağlantılar ve kalan kapasiteler kullanılarak akışın sınırları zorlanır.

Son olarak, halen kapasitesi bulunan

1 \to 2 \to 5 \to 4 \to 6

çapraz yolu kullanılır.

Bu yolun kalan kapasiteler üzerinden darboğazı

\min(8, 4, 5, 7) = 4

birimdir. Toplam akış:

8 + 10 + 2 + 4 = 24

birim bulunur.

Hedefe ulaşan başka bir artan yol kalmadığı için ulaşılan toplam değer ağın maksimum akışıdır.

Minimum Kesit (Min-Cut) teoremi ile sağlama yapılır.

Düğümleri

S = \{1, 2, 3\}

T = \{4, 5, 6\}

olarak iki kümeye böldüğümüzde,

S

'den

T

'ye giden yolların kapasiteleri toplamı:

C(2\to4) + C(2\to5) + C(3\to5) = 8 + 6 + 10 = 24

birimdir.

Max-Flow Min-Cut teoremine göre, herhangi bir şebekedeki maksimum akış, o şebekenin minimum kesit kapasitesine eşittir.

Anahtar Kavram

Maksimum Akış Problemi ve Ford-Fulkerson Algoritması / Min-Cut Teoremi

Soru 55Soru →

Ticaret Bakanlığı tarafından yürütülen bir "Sınır Kapısı Otomasyon ve Güvenlik Yükseltme" projesine ait faaliyetler, öncelik ilişkileri, normal ve hızlandırılmış süreleri ile maliyet bilgileri aşağıdaki tabloda verilmiştir:

Faaliyet	Öncel Faaliyet	Normal Süre (Hafta)	Hızlandırılmış Süre (Hafta)	Normal Maliyet (TL)	Hızlandırılmış Maliyet (TL)
A	-	4	3	20.000	24.000
B	A	5	3	30.000	36.000
C	A	9	7	25.000	28.000
D	B	5	3	15.000	22.000
E	C, D	3	2	10.000	15.000

Projenin normal şartlarda tamamlanma süresi hesaplanmış, ancak yönetim projenin 15 haftada tamamlanmasını talep etmiştir.

Buna göre, projenin tamamlanma süresini 15 haftaya indirmek için uygulanacak optimum (en düşük maliyetli) hızlandırma planı sonucunda projenin toplam maliyeti kaç TL olur?

103.000

106.000

107.000

107.500

109.000

Cevabı ve açıklamayı göster

Cevap: 107.000

Cevap

Optimum hızlandırma planı sonucunda projenin toplam maliyeti 107.000 TL olur.

Doğru yaklaşımda öncelikle kritik yolun A-B-D-E (17 hafta) olduğu belirlenir ve maliyet eğimleri (A:4k, B:3k, C:1.5k, D:3.5k, E:5k) hesaplanır. İlk 1 haftalık kısaltma için kritik yoldaki en ucuz faaliyet olan B seçilir ve maliyet 3.000 TL artar. Bu aşamada A-B-D-E yolu 16 haftaya düşerken, A-C-E yolu da 16 hafta olduğu için her iki yol da kritik hale gelir. 16 haftadan 15 haftaya inebilmek için iki yolun da süresi azaltılmalıdır. Bunun için paralel olan B ve C faaliyetlerinin birlikte hızlandırılması (3.000+1.500=4.500 TL) ile ortak faaliyet olan A'nın hızlandırılması (4.000 TL) kıyaslanır. A faaliyetini hızlandırmak daha ucuz olduğu için bu yol seçilir. Normal maliyet olan 100.000 TL'nin üzerine toplam 7.000 TL hızlandırma maliyeti eklenerek 107.000 TL sonucuna ulaşılır.

Adım Adım Çözüm

Proje ağını çizerek yolları ve normal proje süresini belirleyin.

İki yol vardır: Yol 1 (A-B-D-E) = 4+5+5+3 = 17 hafta. Yol 2 (A-C-E) = 4+9+3 = 16 hafta. Kritik yol 17 hafta ile A-B-D-E yoludur.

Hızlandırma işlemlerine her zaman projenin tamamlanma süresini belirleyen kritik yol üzerinden başlanmalıdır.

Tüm faaliyetlerin haftalık hızlandırma maliyetlerini (maliyet eğimi) hesaplayın ve normal proje maliyetini bulun.

Normal Maliyet = 20k+30k+25k+15k+10k = 100.000 TL.
Maliyet Eğimleri: A = 4.000 TL/hafta, B = 3.000 TL/hafta, C = 1.500 TL/hafta, D = 3.500 TL/hafta, E = 5.000 TL/hafta.

Hızlandırma kararları, süreyi kısaltırken en az maliyet artışına sebep olan (maliyet eğimi en düşük) faaliyetler seçilerek verilir.

Süreyi 17 haftadan 16 haftaya indirmek için kritik yoldaki (A-B-D-E) en ucuz faaliyeti seçin ve 1 hafta hızlandırın.

Kritik yoldaki en düşük eğimli faaliyet B'dir (3.000 TL). B 1 hafta hızlandırılır. Yeni süreler: Yol 1 = 16 hafta, Yol 2 = 16 hafta. Maliyet artışı = +3.000 TL.

Süreyi sadece kritik yoldaki bir faaliyeti kısaltarak düşürebiliriz. B faaliyeti en uygun maliyetli seçenektir.

Süreyi 16 haftadan hedeflenen 15 haftaya indirmek için oluşan yeni kritik yolları değerlendirin.

Artık her iki yol da kritik olduğundan, ya iki yoldan da birer faaliyet birlikte hızlandırılmalı (Örn: B+C = 3.000+1.500 = 4.500 TL) ya da her iki yolda da bulunan ortak bir faaliyet hızlandırılmalıdır (Örn: A = 4.000 TL, E = 5.000 TL).

Birden fazla kritik yol olduğunda, proje süresini 1 hafta kısaltmak için tüm kritik yolların süresinin aynı anda 1 hafta kısalması gerekir.

En düşük maliyetli alternatifi seçerek son hızlandırmayı yapın ve toplam maliyeti hesaplayın.

Ortak faaliyet olan A'nın tek başına hızlandırılması (4.000 TL), B+C'nin birlikte hızlandırılmasından (4.500 TL) daha ucuzdur. A 1 hafta hızlandırılır (+4.000 TL). Toplam proje maliyeti = 100.000 + 3.000 + 4.000 = 107.000 TL.

Maliyet minimizasyonu ilkesi gereği, hedef süreye ulaşmak için en düşük kümülatif maliyet artışını sağlayan kombinasyon seçilmelidir.

Anahtar Kavram

Proje Çökertme (Crashing) ve Maliyet Eğimi Analizi

Soru 56Soru →

Yöneylem araştırması kapsamında bir iletişim sistemini modelleyen uzman, sistemi $n=8$ düğüm (merkez) ve $m=12$ ayrıttan (bağlantı hattı) oluşan tam bağlantılı ve yönsüz bir şebeke olarak tanımlamıştır. Bu şebeke üzerinde veri iletiminin kesintisiz ve döngüsüz (çevrimsiz) yapılabilmesi için bir yayılan ağaç (spanning tree) tasarlanmıştır.

Şebeke teorisindeki temel kavramlar ve topolojik özellikler dikkate alındığında, tasarlanan bu şebeke ve yayılan ağaç yapısı ile ilgili aşağıdaki ifadelerden hangisi yanlıştır?

Belirlenen yayılan ağaç altyapısı, ağ içindeki herhangi iki merkez arasında sadece tek bir basit yol bulunacak şekilde tam olarak 7 adet bağlantı hattı (ayrıt) içerir.

Yayılan ağaca dahil edilmeyen (dışarıda bırakılan) 5 adet bağlantı hattı bulunur ve bunlardan herhangi birinin ağaca eklenmesi, sistemde benzersiz bir temel çevrim oluşturur.

Şebekede tanımlanabilecek birbirinden bağımsız temel çevrimlerin (fundamental cycles) toplam sayısı, yayılan ağaçtaki ayrıt sayısına eşit olup 7'dir.

Yayılan ağaç yapısındaki mevcut 7 bağlantı hattından herhangi birinin arızalanarak devre dışı kalması, ağacı birbiriyle iletişim kuramayan iki ayrık alt bileşene böler.

Sistemin başlangıçtaki 12 bağlantılı tam yapısından bir yayılan ağaç elde edebilmek için, şebekede yer alan tüm kapalı yollardan (çevrimlerden) en az birer bağlantı hattının çıkarılması zorunludur.

Cevabı ve açıklamayı göster

Cevap: Şebekede tanımlanabilecek birbirinden bağımsız temel çevrimlerin (fundamental cycles) toplam sayısı, yayılan ağaçtaki ayrıt sayısına eşit olup 7'dir.

Cevap

Şebekede tanımlanabilecek birbirinden bağımsız temel çevrimlerin sayısının 7 olduğunu iddia eden ifade yanlıştır. Bu şebekedeki bağımsız çevrim sayısı 5'tir.

Doğru cevap (yanlış olan ifade), birbirinden bağımsız temel çevrimlerin toplam sayısını 7 olarak belirten seçenektir. Şebeke teorisinde, yayılan ağaçtaki ayrıt sayısı

n-1

(bu örnekte

8-1=7

) iken, birbirinden bağımsız temel çevrimlerin (cyclomatic number) sayısı

m-n+1

formülü ile bulunur. Bu örnekte

12-8+1 = 5

bağımsız çevrim vardır. İlgili seçenekte ağaç ayrıt sayısı ile çevrim sayısı karıştırılmıştır.

Adım Adım Çözüm

Şebekenin düğüm (n) ve ayrıt (m) sayılarını belirle.

n = 8 (düğüm sayısı), m = 12 (ayrıt sayısı).

Şebekenin topolojik özelliklerini (ağaç ayrıtları, çevrim sayıları) hesaplamak için bu temel parametrelere ihtiyaç vardır.

Yayılan ağaçtaki (spanning tree) ayrıt sayısını hesapla.

Ağaçtaki ayrıt sayısı = n - 1 = 8 - 1 = 7.

Tam bağlantılı herhangi bir yayılan ağaç her zaman düğüm sayısının bir eksiği kadar ayrıt barındırır.

Ağaca dahil olmayan ayrıt (kiriş) sayısını ve buna bağlı olarak temel çevrim sayısını hesapla.

Temel çevrim sayısı = m - n + 1 = 12 - 8 + 1 = 5.

Yayılan ağaca dışarıdan eklenen her bir kiriş, sistemde tam olarak bir bağımsız temel çevrim yaratır.

Hesaplanan değerleri seçeneklerle karşılaştırarak hatalı ifadeyi tespit et.

Bağımsız temel çevrim sayısını 7 olarak belirten seçenek kavramsal olarak hatalıdır (gerçek değer 5 olmalıdır).

Çevrim sayısı ile ağaçtaki ayrıt sayısı (7) birbirine karıştırılmış ve hatalı bir önerme sunulmuştur.

Anahtar Kavram

Yayılan Ağaç (Spanning Tree) ve Temel Çevrimler (Fundamental Cycles)

Soru 57Soru →

Büyükşehir Belediyesi Ulaşım Planlama Dairesi tarafından yürütülen "Akıllı Trafik Sinyalizasyon Ağı" projesinin faaliyetleri, öncelik ilişkileri, normal ve hızlandırılmış süreleri ile maliyetleri aşağıdaki tabloda verilmiştir.

Faaliyet	Öncül Faaliyet	Normal Süre (Hafta)	Hızlandırılmış Süre (Hafta)	Normal Maliyet (Bin TL)	Hızlandırılmış Maliyet (Bin TL)
A	-	4	3	50	70
B	A	5	3	80	100
C	A	6	4	120	180
D	C	4	3	60	75
E	B, D	3	2	40	80

Belediye yönetimi, artan trafik yoğunluğu nedeniyle projenin normal tamamlanma süresini 14 haftaya indirmek istemektedir.

Buna göre, projenin 14 haftada tamamlanabilmesi için katlanılması gereken minimum ek hızlandırma (çökertme) maliyeti kaç bin TL'dir?

Cevabı ve açıklamayı göster

Cevap: 65

Cevap

Projenin 14 haftaya indirilmesi için gereken minimum ek hızlandırma maliyeti 65 bin TL'dir.

Projenin kritik yolu 17 hafta süren A-C-D-E yoludur. 14 haftaya inmek için 3 haftalık kısaltma gereklidir. Kritik yoldaki faaliyetlerin maliyet eğimleri; A=20, C=30, D=15 ve E=40 Bin TL/Hafta'dır. Optimum çökertme sırasıyla en ucuz olan D faaliyeti (1 hafta, 15 Bin TL), ardından A faaliyeti (1 hafta, 20 Bin TL) ve son olarak C faaliyeti (1 hafta, 30 Bin TL) hızlandırılarak yapılır. Toplam minimum ek maliyet 15 + 20 + 30 = 65 Bin TL olur.

Adım Adım Çözüm

Proje ağındaki tüm yolların sürelerini hesaplayarak kritik yolu belirlemek.

Yol 1 (A-B-E) = 12 hafta, Yol 2 (A-C-D-E) = 17 hafta. Kritik yol 17 hafta ile A-C-D-E yoludur. Hedef 14 hafta olduğu için kritik yolda toplam 3 haftalık hızlandırma (çökertme) yapılmalıdır.

Sadece kritik yol üzerindeki faaliyetleri hızlandırmak projenin toplam süresini kısaltabilir.

Kritik yol üzerindeki faaliyetlerin maliyet eğimlerini (Hızlandırma Maliyeti - Normal Maliyet) / (Normal Süre - Hızlandırılmış Süre) formülü ile hesaplamak.

A: (70-50)/(4-3) = 20, C: (180-120)/(6-4) = 30, D: (75-60)/(4-3) = 15, E: (80-40)/(3-2) = 40.

Birim zaman başına en az maliyet artışı getiren faaliyetleri öncelikli olarak seçmek için.

Maliyet eğimi en düşük olan faaliyetten başlayarak süre limitleri dahilinde kritik yolu 3 hafta kısaltmak.

1. D faaliyeti 1 hafta hızlandırılır (Maliyet: 15). Kritik yol 16 haftaya düşer.
2. A faaliyeti 1 hafta hızlandırılır (Maliyet: 20). Kritik yol 15 haftaya düşer.
3. C faaliyeti 1 hafta hızlandırılır (Maliyet: 30). Kritik yol hedeflenen 14 haftaya düşer.

Minimum ek maliyetle hedeflenen 14 haftalık proje süresine ulaşmak için.

Yapılan hızlandırma işlemlerinin toplam ek maliyetini hesaplamak.

Toplam Minimum Ek Maliyet = 15 + 20 + 30 = 65 Bin TL.

Soruda istenen toplam hızlandırma maliyeti değerini bulmak için.

Anahtar Kavram

Proje Çökertme (Project Crashing) ve Zaman-Maliyet Analizi

Soru 58Soru →

Devlet Su İşleri (DSİ) tarafından yürütülen "Bölgesel Su Yönetimi ve Baraj İyileştirme" projesinin planlama aşamasında belirlenen faaliyetler, öncelik ilişkileri ve süre-maliyet tahminleri aşağıdaki tabloda verilmiştir:

Faaliyet	Öncül Faaliyetler	Normal Süre (Hafta)	Hızlandırılmış Süre (Hafta)	Normal Maliyet (Bin TL)	Hızlandırılmış Maliyet (Bin TL)
A	-	5	3	20	50
B	-	6	4	30	46
C	A	4	2	15	45
D	A, B	7	5	40	60
E	C, D	3	2	25	45

Buna göre, projenin tamamlanma süresini 14 haftaya indirmek için katlanılması gereken minimum toplam proje maliyeti kaç Bin TL'dir?

146

148

150

155

166

Cevabı ve açıklamayı göster

Cevap: 148

Cevap

Projenin tamamlanma süresini 14 haftaya indirmek için gereken minimum toplam proje maliyeti 148 Bin TL'dir.

Başlangıçta kritik yol 16 hafta ile B-D-E'dir. İlk hafta hızlandırması için en düşük maliyet eğimine sahip B faaliyeti seçilir (+8 Bin TL). Bu işlemden sonra hem A-D-E hem de B-D-E 15 hafta ile yeni kritik yollar olur. İkinci hafta hızlandırması için proje süresini 14 haftaya çekmek amacıyla her iki kritik yolu da etkileyen ortak faaliyetlerden en ucuzu olan D faaliyeti seçilir (+10 Bin TL). Toplam normal maliyet 130 Bin TL'dir. 130 + 8 + 10 = 148 Bin TL minimum toplam maliyet olarak bulunur.

Adım Adım Çözüm

Her bir faaliyetin Maliyet Eğimi (Haftalık Hızlandırma Maliyeti) değerlerini hesaplayın.

A: (50-20)/(5-3)=15, B: (46-30)/(6-4)=8, C: (45-15)/(4-2)=15, D: (60-40)/(7-5)=10, E: (45-25)/(3-2)=20

Maliyet eğimi, süreyi bir birim kısaltmak için katlanılması gereken ek maliyeti gösterir ve hızlandırma kararlarının temelidir.

Projedeki tüm yolları belirleyin, başlangıçtaki Kritik Yolu ve Normal Proje Maliyetini hesaplayın.

Yollar: A-C-E = 12 hafta, A-D-E = 15 hafta, B-D-E = 16 hafta. Kritik Yol B-D-E'dir (16 hafta). Normal Maliyet = 20+30+15+40+25 = 130 Bin TL.

Hızlandırma işlemine daima en uzun yol olan Kritik Yol üzerinden başlanmalıdır.

Proje süresini 16 haftadan 15 haftaya indirmek için Kritik Yol (B-D-E) üzerindeki en düşük maliyet eğimli faaliyeti 1 hafta hızlandırın.

B, D ve E arasından en düşük eğime sahip B (8 Bin TL) seçilir. B'nin süresi 5 haftaya düşer. Yeni yollar: A-C-E (12), A-D-E (15), B-D-E (15). Ek maliyet: 8 Bin TL.

Maliyetin minimum kalması için her zaman kritik yoldaki en ucuz faaliyet hızlandırılır.

Proje süresini 15 haftadan 14 haftaya indirmek için yeni Kritik Yolları (A-D-E ve B-D-E) aynı anda kısaltacak en uygun seçeneği belirleyin.

İki kritik yol vardır. Seçenekler: Sadece D'yi (10) hızlandırmak, sadece E'yi (20) hızlandırmak veya A ve B'yi (15+8=23) aynı anda hızlandırmak. En ucuzu D (10 Bin TL) faaliyetidir. Toplam maliyet = 130 + 8 + 10 = 148 Bin TL.

Birden fazla kritik yol olduğunda, proje süresinin kısalması için tüm kritik yolların aynı anda kısaltılması şarttır.

Anahtar Kavram

Proje Çökertme ve Zaman-Maliyet Analizi

Soru 59Soru →

Büyük ölçekli bir su dağıtım ağı, yöneylem araştırması kapsamında yönlü bir şebeke (directed network) olarak modellenmiştir. Bu modelde düğümler pompa istasyonlarını, yaylar (ayrıtlar) ise boru hatlarını temsil etmektedir. Şebekede bir ana kaynak (arz) düğümü ve bir ana kuyu (talep) düğümü bulunmaktadır.

Sistemin darboğazlarını ve kapasite sınırlarını analiz etmek isteyen bir yöneylem uzmanının, şebeke modellemesindeki temel kavramları kullanırken yaptığı aşağıdaki değerlendirmelerden hangisi doğrudur?

Şebekedeki darboğazı aşmak amacıyla maksimum akış miktarını artırmak için, kuyu kümesinden kaynak kümesine doğru ters yönde yer alan (geri akışlı) yayların taşıma kapasitelerinin artırılması sistemin toplam kapasitesini doğrudan yükseltir.

Sistemdeki toplam arz ile toplam talebin birbirine eşit olmadığı dengesiz durumlarda, modeli dengelemek için yapıya eklenen yapay düğümlere (kukla düğüm) bağlanan yapay yayların taşıma kapasiteleri modele her zaman sıfır (

0

) olarak yansıtılır.

Şebekeyi; kaynak düğümünü içeren bir alt küme ve kuyu düğümünü içeren ayrık diğer bir alt küme olarak ikiye bölen herhangi bir 'kesitin (cut)' kapasitesi, yalnızca yönü kaynak kümesinden kuyu kümesine doğru olan yayların taşıma kapasiteleri toplanarak hesaplanır.

Şebeke içinde matematiksel olarak tanımlanacak kapalı bir 'çevrim (cycle)', başlangıç ve bitiş düğümleri aynı olan bir dizilimdir ve çevrimin kapanabilmesi için ardışık düğümlerin birbirine doğrudan bir yay ile bağlı olması şartı aranmaz.

Kaynak ile kuyu düğümleri arasındaki en kısa yol hesaplanırken, incelenen bir düğüme ulaşan alternatif bir rotanın maliyeti mevcut düğüm etiketindeki değerden yüksek olsa dahi, algoritmanın döngüden çıkmaması için etiket değeri bu yeni değerle güncellenmelidir.

Cevabı ve açıklamayı göster

Cevap: Şebekeyi; kaynak düğümünü içeren bir alt küme ve kuyu düğümünü içeren ayrık diğer bir alt küme olarak ikiye bölen herhangi bir 'kesitin (cut)' kapasitesi, yalnızca yönü kaynak kümesinden kuyu kümesine doğru olan yayların taşıma kapasiteleri toplanarak hesaplanır.

Cevap

Şebekeyi kaynak ve kuyu alt kümelerine ayıran bir kesitin kapasitesi, yalnızca kaynak alt kümesinden kuyu alt kümesine doğru giden ileri yönlü yayların kapasiteleri toplanarak hesaplanır.

Şebeke teorisinde bir kesitin (cut) kapasitesi tanımlanırken, sadece kaynak düğümünün bulunduğu alt kümeden kuyu düğümünün bulunduğu alt kümeye doğru yönlenmiş (ileri yönlü) yayların kapasiteleri dikkate alınır. Kuyu kümesinden kaynak kümesine doğru ters dönen yaylar, ağın kaynak-kuyu arası ileri yönlü toplam akış kapasitesine katkı yapmadığı için kapasite hesabına dahil edilmez. Bu, Maksimum Akış teoremindeki temel kurallardan biridir.

Adım Adım Çözüm

Şebeke analizi modellerindeki temel kavramların ve özellikle 'kesit (cut)' kavramının kapasite formülasyonunun incelenmesi.

Kesit (Cut), şebekedeki düğümleri iki ayrık kümeye (

S

T

) bölen ve kaynak düğümünü

S

, kuyu düğümünü

T

kümesinde bırakan yapıdır.

Maksimum akış - Minimum kesit (Max-Flow Min-Cut) teoremine göre şebekenin darboğazını tanımlayabilmek için kesit kavramının doğru anlaşılması gerekir.

Kesit kapasitesinin (Cut Capacity) matematiksel tanımının değerlendirilmesi.

Kesit kapasitesi hesaplanırken, sadece

S

kümesinden (kaynak tarafı)

T

kümesine (kuyu tarafı) doğru olan ileri yönlü yayların kapasiteleri toplanır.

Ters yöndeki (kuyudan kaynağa doğru) yaylar net ileri akışa ek kapasite sağlamadığı için bu toplama matematiksel olarak dahil edilmez.

Diğer seçeneklerdeki şebeke kavramlarına dair ifadelerin doğruluğunun test edilmesi.

Geri akış kapasitesinin darboğazı çözmemesi, dengesiz modellerde yapay kapasitenin sıfır olmaması, çevrimlerde doğrudan bağlantı şartı olması ve en kısa yolda sadece daha küçük maliyetlerin etiket güncellemesi yapması gerçekleri, diğer yargıların hatalı olduğunu kanıtlar.

Yöneylem araştırmasındaki şebeke algoritmalarının temel işleyiş kuralları (Dijkstra, MODI, Max-Flow vb.) bu yanlış kavramsal yargıları çürütmektedir.

Anahtar Kavram

Kesit (Cut) ve Kesit Kapasitesi

Tahmini Süre:1m 30s

Soru 60Soru →

Bir kamu kurumu, birimler arası evrak ve bilgi akışını yönlü bir şebeke (directed network) $G=(N, A)$ olarak modellemiştir. Şebekenin yapısal analizi için $n$ adet düğüm (satır) ve $m$ adet yaydan (sütun) oluşan bir düğüm-yay matrisi (insidans matrisi) oluşturulmuştur. Bu matriste her bir yay için; yayın çıktığı düğüme $+1$ , yayın girdiği düğüme $-1$ ve yayla doğrudan bağlantısı olmayan düğümlere $0$ değeri atanmıştır.

Buna göre, oluşturulan bu düğüm-yay matrisinin özellikleri dikkate alındığında aşağıdaki ifadelerden hangisi kesinlikle yanlıştır?

Herhangi bir satırdaki tüm elemanların cebirsel toplamı, ilgili düğüme bağlanan tüm yayların toplam sayısını (düğümün toplam derecesini) verir.

Matrisin herhangi bir sütunundaki elemanların cebirsel toplamı her zaman sıfıra eşittir.

Şebeke tam bağlantılı (connected) bir yapıda ise, matrisin rankı düğüm sayısının bir eksiğine (

n-1

) eşittir.

Matristeki doğrusal bağımsız sütun vektörlerinin oluşturduğu herhangi bir temel (baz), şebekenin bir yayılan ağacına (spanning tree) karşılık gelir.

Cevabı ve açıklamayı göster

Cevap: Herhangi bir satırdaki tüm elemanların cebirsel toplamı, ilgili düğüme bağlanan tüm yayların toplam sayısını (düğümün toplam derecesini) verir.

Cevap

Düğüm-yay matrisinde bir satırdaki elemanların cebirsel toplamının o düğümün toplam derecesini verdiğini iddia eden seçenek yanlıştır.

Düğüm-yay matrisinde herhangi bir satırdaki elemanların cebirsel (işaretli) toplamı, o düğümden çıkan yayların sayısı ile o düğüme giren yayların sayısı arasındaki farkı verir. Bu değere düğümün 'net derecesi' denir. Düğümün 'toplam derecesi' ise o düğüme bağlanan tüm yayların sayısıdır ve bunu bulmak için satırdaki elemanların mutlak değerlerinin toplamı alınmalıdır. Bu nedenle cebirsel toplamın toplam dereceyi verdiğini belirten ifade kesinlikle yanlıştır.

Adım Adım Çözüm

Düğüm-yay (insidans) matrisinin satır yapısını analiz et.

Bir satır belirli bir düğümü temsil eder. Satırdaki

+1

'ler o düğümden çıkan yayları,

-1

'ler ise o düğüme giren yayları gösterir.

Soruda verilen

+1

-1

atama kuralları matrisin temel yapısını oluşturur.

Bir satırdaki elemanların cebirsel toplamını değerlendir.

Cebirsel toplam, (Çıkan Yay Sayısı) + (-Giren Yay Sayısı) işlemini yapar. Bu da düğümün net derecesini (net akış katsayısını) hesaplar.

Pozitif ve negatif değerler birbirini sönümler.

Düğümün 'toplam derecesi' kavramı ile satır toplamını karşılaştır.

Toplam derece, düğüme bağlı tüm yayların (yön fark etmeksizin) sayısıdır. Bunu bulmak için matristeki elemanların mutlak değerlerinin (

|+1| + |-1|

) toplanması gerekir.

Cebirsel toplam toplam dereceyi değil, net dereceyi verdiğinden bu ifade matematiksel olarak yanlıştır.

Anahtar Kavram

Düğüm-Yay (İnsidans) Matrisi Özellikleri

ÖncekiSayfa 3 / 4Sonraki

Şebeke Analizi

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Alternatif Yöntem

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Cevap

Adım Adım Çözüm