Ağ Modeli (Yöneylem Araştırması)

From Systems analysis Wiki
Jump to navigation Jump to search

Ağ modelleri (yöneylem araştırmasında; İng. Network models) — bir problemi, köşelerin (düğümlerin) nesne veya durumları, kenarların (yayların) ise aralarındaki bağlantı veya süreçleri temsil ettiği bir graf (ağ) biçiminde ifade eden matematiksel modeller sınıfıdır[1]. Optimizasyon bağlamında ağ, çoğunlukla yönlü bir graf olarak anlaşılır; bu graf, operasyonel analizde doğrudan "ağ" olarak adlandırılır: söz konusu ağın köşelerine düğüm, kenarlarına ise yay denir[2].

Ağ modelleri; lojistik, telekomünikasyon, proje yönetimi ve finans gibi alanlarda karmaşık sistemlerin analizi ve optimizasyonu için güçlü bir araçtır. Güçleri, yüksek soyutlama düzeyinden kaynaklanır: bir düğüm bir şehri, bilgisayar yönlendiricisini veya proje aşamasını; bir yay ise bir yolu, iletişim kanalını ya da teknolojik bir işlemi temsil edebilir.

Tanım ve Terminoloji

Ağ modellerinin temeli graf teorisidir. Temel kavramlar şunlardır:

  • Akış ağı (İng. flow network): Her kenarın bir kapasite (capacity) ve bir akış (flow) değerine sahip olduğu yönlü bir graftır. Grafta iki özel köşe ayırt edilir: akışın çıktığı kaynak (source) ve akışın girdiği hedef (sink)[1].
  • Akış korunumu yasası: Kaynak veya hedef olmayan herhangi bir köşe için toplam giren akış, toplam çıkan akışa eşit olmalıdır. Bu koşul, fiziksel korunum yasalarının ayrık bir analoğudur[3].
  • Ağ planlaması: Bir projeyi birbirine bağlı işlemler (yaylar) ve olaylar (düğümler) bütünü olarak temsil eden modeldir. Bu tür ağlar, işlerin yürütülme sırasını yansıtan yönlü döngüsüz graflardır[4].

Temel Özellikler ve Teoremler

Ağ modelleri, çözümleri için son derece verimli algoritmaların uygulanmasına olanak tanıyan bir dizi özel özelliğe sahiptir.

  • Çözümlerin tam sayılılığı: Pek çok ağ optimizasyonu problemi (örneğin maksimum akış veya en kısa yol problemi), kısıtlar matrisinin tam ünimüdülerlik özelliğine sahiptir. Bu sayede, problemin parametreleri (kapasiteler, uzunluklar) tam sayı ise doğrusal programlama yöntemleriyle bulunan optimal çözüm de ek kısıtlara gerek kalmaksızın tam sayı olacaktır[5][6].
  • Maksimum akış - minimum kesim teoremi: Akış teorisinin merkezi sonucudur. Kaynaktan hedefe giden maksimum akış miktarının, kaynağı ve hedefi birbirinden ayıran tüm kesimler arasındaki minimum kapasiteye eşit olduğunu öne sürer. Bu teorem, akış için optimallik ölçütü belirler ve pek çok algoritmanın temelini oluşturur[6][7].
  • En kısa yollar için optimallik ilkesi: A noktasından C noktasına giden bir yol en kısa yol ise, bu yolun herhangi bir parçası (örneğin ara nokta B'den C'ye) de ilgili köşeler arasındaki en kısa yoldur. Dinamik programlamanın temelinde yatan bu özellik, Dijkstra algoritması gibi algoritmaların doğruluğunu güvence altına alır[8].
  • Minimum yayılan ağaç (MYA) özellikleri:
  • Kesim özelliği: Grafın herhangi bir kesimi için, kesimi geçen minimum ağırlıklı kenar en az bir MYA'ya aittir.
  • Döngü özelliği: Grafın herhangi bir döngüsünde maksimum ağırlıklı kenar hiçbir MYA'ya ait değildir.

Bu özellikler, Prim ve Kruskal'ın "açgözlü" algoritmalarının doğruluğunun temelini oluşturur[9].

Ağ Optimizasyonunun Temel Problemleri

  • En kısa yol problemi: İki belirli düğüm arasında minimum toplam uzunluklu (ağırlıklı) yolu bulmak. Dijkstra algoritmasıyla (negatif olmayan ağırlıklar için) veya Bellman-Ford algoritmasıyla (keyfi ağırlıklar için) çözülür[8].
  • Maksimum akış problemi: Verilen yay kapasiteleri ile kaynaktan hedefe mümkün olan maksimum akışı belirlemek. Klasik çözüm yöntemi Ford-Fulkerson algoritmasıdır[6].
  • Minimum yayılan ağaç problemi: Ağın tüm köşelerini birbirine bağlayan ve toplam kenar maliyeti minimum olan alt grafı bulmak.
  • Kritik yol yöntemi (CPM): Planlama ağ modellerinde, tüm projenin mümkün olan minimum tamamlanma süresini belirleyen en uzun iş dizisini bulmak. Bu yol üzerindeki işlerin zaman tamponu sıfırdır[10].

Örnekler

  • En kısa yol: Bir navigasyon sisteminin şehir haritasında iki nokta arasındaki optimal güzergahı bulması; şehirler düğümleri, yollar ise ağırlıkları mesafe veya seyahat süresi olan yayları temsil eder.
  • Maksimum akış: Pompa istasyonlarının düğümleri, boruların ise sınırlı kapasiteli yayları oluşturduğu bir boru hattı ağının maksimum kapasitesinin belirlenmesi.
  • Minimum yayılan ağaç: Birden fazla şehri minimum toplam kablo uzunluğuyla birbirine bağlamak için bir iletişim ağının (örneğin fiber optik kablo döşenmesi) tasarlanması.
  • Kritik yol: Belirli süreler ve teknolojik bağımlılıkları olan işlerden (temel atma, duvar örme, çatı montajı) oluşan bir ev inşaatı projesinde kritik yol, inşaatın minimum tamamlanma süresini belirler. Bu yol üzerindeki herhangi bir işin gecikmesi tüm projenin gecikmesine yol açar[10].

Ayrıca bakınız

  • Yöneylem araştırması
  • Graf teorisi
  • Ulaştırma problemi
  • Kritik yol yöntemi
  • PERT

Notlar

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Ağ_Modeli_(Yöneylem_Araştırması)&oldid=512"