Examkin

Soru

Zorluk: ZorŞebeke Modellerinde Temel Kavramlar

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?

  1. A
    Ş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.
  2. B
    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 (00) olarak yansıtılır.
  3. Ş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
  4. D
    Ş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.
  5. E
    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.

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

1
Ş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 (SS ve TT) bölen ve kaynak düğümünü SS, kuyu düğümünü TT 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.
2
Kesit kapasitesinin (Cut Capacity) matematiksel tanımının değerlendirilmesi.
Kesit kapasitesi hesaplanırken, sadece SS kümesinden (kaynak tarafı) TT 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.
3
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
Bu soruyu puanla

Konular

Şebeke Modellerinde Temel Kavramlar

Bu konudan daha fazla soru