Şebeke Modelleri

Sayısal yöntemler veya yöneylem araştırmasında, şebeke (dallar ile birbirine bağlanan düğümler) olarak uygun bir biçimde modellenip çözülebilen çok sayıda durum vardır. Bunları anlayabilmek için aşağıdaki durumları inceleyebiliriz.

· Azerbaycan’da bulunan petrol kuyularını Türkiye’de bulunan teslim noktalarına bağlayan petrol boru hattı probleminin tasarımı. Modelin amacı boru hattının inşa maliyetlerini minimum kılınmasıdır.

· Mevcut olan karayolları şebekesinde herhangi iki şehir arasında en kısa güzergâhın belirlenmesi.

· İnşaat projelerinin faaliyetleri için zaman çizelgesinin belirlenmesi.

Yukarıda sayılan durumların çözülebilmesi için çeşitli şebeke optimizasyon algoritmalarından faydalanılabilir. Bu algoritmalardan bazıları:

1. Minimum Kapsayan ağaç algoritması (Minimum Spanning Tree)

2. En kısa yol algoritması.

3. Maksimum Akış algoritması

4. Minimum Maliyet kapasiteli şebeke algoritması

5. Kritik yol ( Critical Path Method) algoritması.

Bu algoritmaların uygulandığı durumların çoğu ayrıca doğrusal programlama modeli olarak da yazılabilir. Fakat yukarıda belirtilen algoritmalar simpleks yönteme göre daha etkilidirler.

Şebeke Tanımları

Bir şebeke, bağlantılar veya dallar ile birbirine bağlanmış bir dizi düğümden oluşur. Göz önüne aldığımız bir şebeke (N, A) rotasyonuyla ifade edilir. Burada N, düğümler kümesi, A ise bağlantılar kümesidir.

N={1, 2, 3, 4,5}

A={(1, 2), (1, 3), (2,3), (2,4), (2,5), (3,4), (3, 5), (4, 5)}

Her şebekenin kendisine has bir akış tipi vardır. Örneğin petrol ürünleri, boru hattından, trafik bir karayolu şebekesinden akar. Genellikle bir şebekedeki akış, şebekedeki bağlantıların sonlu veya sonsuz olabilen kapasiteleriyle sınırlıdır.

Bir yönde pozitif akışa, diğer yönde sıfır akışa izin veren bir bağlantının yönlendirilmiş veya yönelimli olduğu söylenir. Yönlendirilmiş şebekenin tüm dalları yönlendirilmiştir.

Yol: Her bir daldaki akışın yönüne bakılmaksızın iki düğümü birleştiren aynı dalların sırasıdır.

WINQSB Programı kullanarak Şebeke modellerini çözebiliriz. Winqsb birçok yöneylem konusunda bizlere yardımcı olabilecek bir program. Doğrusal programlama, oyun teorisi, en kısa yol problemleri, ağ modelleri, ulaştırma modeller, dinamik programlama, tamsayılı programlama ve birçok konuda görselliği ile bizlere yardımcı olmakta.

Bu yazımızda Winqsb yardımı ile CPM (critical path method) problemlerini çözümünü anlatacağız.

1. WINQSB ile CPM Modellerinin Çözümü

CPM problemlerinin çözümüne geçilmeden önce projeye ait tüm faaliyetlerin belirlenmiş olması gerekmekte. Faaliyetlerin süreleri, öncü faaliyetler belirlenmeli ve analize hazır hale getirilmelidir.

Çözüm için kullanacağımız örnek projede 10 faaliyet bulunmakta. Faaliyetlere ait süreler ve maliyetler önceden belirlenmiş ve biz çözüme geçeceğiz.

Öncelikle programı kurmuş olduğumuz klasör içinde bulunan PERT-CPM.exe dosyasına tıklayarak Winqsb programını çalıştırıyoruz. Açılan ekranda File-New komutları ile yeni bir problem modeli oluşturuyoruz. Görülen ekran aşağıdaki gibidir.