Giriş
Bu araştırmada, bir düğümün ne olacağının tanımı, bir ağ modelinde kullanılan köşeler, olabilecek bir yay gibi en temel kavramlardan başlayarak, ağ modellerinin her birini tanımlama hedefi gündeme getirildi. ağ içindeki her bir düğümün ok veya konektörü, ayrıca bir ağın yapısını anlamak için göz önünde bulundurulması gereken hususlar, yayların aldığı yönler gibi olabilir, bunlar doğrudan veya dolaylı olabilir.
Ağları oluşturan parçaların terminolojilerini anladıktan sonra, modellerin her birinin ne olacağına devam ediyoruz, ilki ağdaki bir modeli temsil eden bir tablo olacak bir düğüm-yay geliş matrisi olabilir, ağaç tekniği minimum genişleme, bunu gerçekleştirmek için izlenmesi gereken adımlar, maksimum akış tekniği, teknik adımlar, en kısa yol tekniği ve olabilecek diğer ağ modelleri, ulaşım sorunları, en kısa yol sorunları, ağ proje planlamasında kritik yol, en az maliyetli akış sorunu, ağ modelleri için duyarlılık analizi, satıcı seyahat problemi, ayrıca bazı örnekler kullanarak sorunları daha net hale getirebilir.
Tüm bu konular belge içerisinde daha detaylı ve daha iyi anlaşılarak açıklanmıştır.
Ağ Modelleri
Bir ağ modeli, en kısa yol modeli ve maksimum ve minimum akış modeli, minimum erişim ağacı problemi, kritik yol yöntemi gibi çeşitli biçimler alabilen kapasitelere sahip bir aktarma modelidir. finans ve üretim planlamasının diğer uygulamaları.
Kapasiteleri olan bir aktarma modelinin temel özelliği, tekliflerin belirli çıkış noktalarında olduğu, belirli varış noktalarındaki taleplerin ve nakliye alternatiflerinin ara düğümler üzerinden sunulduğu bir ağ olması, yani başlangıçtan varış noktasına kadar tanımlanmış yeteneklere sahip rotaları izleyen.
Ağ terminolojisi
Bir ağ, yaylarla (veya dallarla) birleştirilen bir dizi düğümden oluşur. Bir ağı tanımlayan gösterim, (N, A) 'dır, burada N, düğümler kümesidir ve A, yay kümesidir.
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5) }
Aşağıda ağın ve ana bileşenlerinin bir şeması bulunmaktadır.
Teknolojik ağ modelleri
Düğüm nedir?
Genellikle tepe veya nokta olarak adlandırılır. Genellikle bir daire ile temsil edilir. Ulaşım ağlarında, bunlar harita üzerindeki kasaba veya şehirler olmalıdır.
Kemer nedir?
Genellikle sınır veya ok olarak adlandırılır. Bu, doğrudan veya dolaylı olabilir. Baş hedef, kuyruk ise başlangıç noktasıdır. Baş ve kuyruk, hem başlangıçta hem de sonunda olabilen düğümlerdir. Ulaşım ağlarında, yaylar yollar, bir nehirdeki navigasyon kanalları veya bir uçağın uçuş modelleri olabilir. Yaylar, düğümler arasındaki bağlantıyı sağlar. Tek yönlü bir cadde bir yay ile temsil edilebilirken, iki yönlü bir cadde, yönsüz bir yay veya zıt yönleri gösteren iki yay ile temsil edilebilir. Düğümleri olan bir ağ, n! / = n (n-1) / 2. Hedeflenirse bu sayı iki katına çıkabilir.Bu muazzam sayıda olası yay, belirli ağ problemleri için özel algoritma çözümlerinin olmasının nedenlerinden biridir.
Ağ düğümünde, genellikle düğümün arzını (+) ve talebini veya gereksinimlerini (-) gösteren pozitif veya negatif işaretli bir sayı bulacaksınız.
Yol, iki farklı düğümü birleştiren ve ağdaki diğer düğümlerden geçen bir dizi yaydır. Örneğin, Şekil 1'de yaylar (1,2), (2,3), (3,4) ve (4,5) 1 ve 5 numaralı düğümler arasında bir yol oluşturur. Bir yol bir döngü veya bir Bir düğümü diğer düğümler aracılığıyla kendisine geri bağlarsanız döngü. Şekil 6.1'de, yaylar (2,3), (3,4) ve (4,2) bir döngü oluşturur.
Önemli hususlar:
- Tek yönlü oklar / çizgiler doğrudan yaylardır. Her iki yön için akışı olan çizgiler dolaylı yaylardır. Yalnızca doğrudan yayları olan bir ağ, doğrudan bir ağdır. Her iki yönde yayları olan bir ağ, dolaylı bir ağdır. İ düğümünden j'ye doğrudan bir yol, bağlı yay dizisidir, bu nedenle bu yoldan geçen bir akış uygundur. İ düğümünden j'ye dolaylı bir yol, yönü i olan ve tersi olan bağlı yay dizisidir. Aynı düğümde başlayan ve biten bir yol bir döngüdür Ağ, 2 düğüm arasında en az bir doğrudan yol içeriyorsa, bunların bağlı olduğu söylenir. Ağ yollarından hangisinin seçileceğini belirlemek için, güzergahlar boyunca maliyetleri ve kapasiteleri dikkate almalıyız.
Ağ Modelleri Sürüm 1
Düğüm - yay geliş matrisi
Bir ağ modelindeki kısıtların verilerini temsil eden bir tablodur. Ağın her yayı, tablonun bir sütununa karşılık gelir. Ağdaki her düğüm, tablodaki bir satıra karşılık gelir. Sütunlarda sıfır olmayan yalnızca iki giriş vardır: +1 ve -1.
Teknolojik ağ modelleri
Doğrusal programlama modelini yükselttikten sonra, doğrusal programlamanın çözümünü bulmalıyız, hedef işlevi optimize eden çözümü bulmalıyız.
- En uygun çözümü bulmak için SOLVER veya LINDO gibi bazı doğrusal programlama yazılımlarını kullanabiliriz.
Kapanış
- Bir ağ çizmek için terminoloji ve prosedür, optimizasyon modellerini uygulamanıza yardımcı olacaktır, çünkü Örnek 3'e bakıldığında en kısa veya en uzun yolu vb. Belirlemek çok daha kolaydır.
Ağ modeli sürüm 2
Minimum kapsayan ağaç tekniği
Bu ağaç, bağlanan dalların minimum toplam uzunluğunu kullanarak bir ağın düğümlerini birbirine bağlar. Kasabaları birbirine bağlayan veya doğrudan veya diğer şehirlerden geçen yolların asfaltlanmasında yaygın bir uygulama ortaya çıkar. En az yayılan ağaç çözümü, yol sisteminin tasarımını sağlar.
Adımlar Minimum Kapsama Ağacı Tekniği
- Ağdaki herhangi bir düğümü seçin. Bu düğümü, toplam mesafeyi en aza indiren en yakın düğüme bağlayın. Şu anda bağlı olan tüm düğümleri göz önünde bulundurarak, bağlı olmayan en yakın düğümü bulun ve bağlayın. En yakın düğüm için bir bağ varsa, rastgele birini seçin. Bir bağ, birden fazla optimal çözüm olabileceğini gösterir.Tüm düğümler bağlanana kadar üçüncü adımı tekrarlayın.
Misal
Orlando yakınlarında büyük bir at yetiştirme çiftliğine sahip olan Roxie LaMothe, tüm ahırları ve ahırları birbirine bağlayan bir su sistemi kurmayı planlıyor. Tesislerin konumu ve aralarındaki mesafeler aşağıdaki şekilde gösterilmiştir. Roxie, her tesise su sağlamanın en ucuz yolunu belirlemelidir.
Teknolojik ağ modelleri
Tepe Akış Tekniği
- Tepe akış tekniği, bir ağ üzerinden akabilecek en fazla olanı belirler.
Tepe akış tekniğinin 4 adımı
- Biraz akışla başlangıçtan (orijinal) sona (hedef) herhangi bir yolu seçin. Akış yolu yoksa, en uygun çözüme ulaşılmıştır Mevcut en küçük akış kapasitesine sahip yolun kavisini bulun Bu kapasiteyi C olarak adlandırın. Bu, bu yola tahsis edilebilecek maksimum ek kapasiteyi temsil eder.Bu yoldaki her düğüm için akış yönündeki akış kapasitesini C miktarı kadar azaltın. Bu yoldaki her düğüm için kapasiteyi artırın C miktarına göre ters yönde akış
Akışı artırmak artık mümkün olmayana kadar bu adımları tekrarlayın.
Misal
Louisiana, Baton Rouge'un güneyinde Mississippi Nehri üzerinde bulunan bir petrol rafinerisi olan PetroChem, dizel yakıt üretmek için yeni bir tesis tasarlıyor. Şekil 5, mevcut akış hızı ile birlikte ana işleme merkezlerinin ağını göstermektedir. Yönetim, düğüm 1'den düğüm 7'ye tesisten akabilecek maksimum yakıt miktarını belirlemek istiyor.
Teknolojik ağ modelleri
En kısa yol tekniği
Bu sorun, bir ulaşım ağındaki bir kaynak ile bir hedef arasındaki en kısa yolu belirler.
En kısa yol tekniğinin adımları
- Orijine en yakın düğümü bulun. Mesafeyi düğümün yanındaki bir kutuya koyun Başlangıç noktasına (bitkiye) en yakın düğümü bulun ve mesafeyi düğümün yanındaki bir kutuya koyun. Bazı durumlarda, en yakın düğümü bulmak için birden çok yolun gözden geçirilmesi gerekir - tüm ağı geçene kadar işlemi tekrarlayın. Son düğümdeki son mesafe, en kısa yolun mesafesi olacaktır. Her düğümün yanındaki kutuya yerleştirilen mesafenin bu düğüme giden en kısa yol olduğuna dikkat edin. Bu mesafeler, bir sonraki en yakın düğümü bulmak için ara sonuçlar olarak kullanılır.
Misal:
RentCar, 4 yıllık planlama ufku içinde araç filosu için bir yenileme politikası geliştiriyor. Her yılın başında bir araba değiştirilir veya bir yıl daha çalışır durumda tutulur. Bir araba 1 ila 3 yıl hizmette olmalıdır. Aşağıdaki tablo, bir arabanın satın alındığı yıl ve faaliyette olan yılların bir fonksiyonu olarak değiştirme maliyetini vermektedir.
Teknolojik ağ modelleri
Sorun, 1'den 5'e kadar olan düğümlerin 1'den 5'e kadar olan yılların başlangıcını temsil ettiği bir ağ olarak formüle edilebilir. Düğüm 1'den (yıl 1) gelen yaylar 2, 3 ve 4 düğümlerine ulaşabilir çünkü bir araba 1 ila 3 yıldır faaliyette olmak. Diğer düğümlerden gelen yaylar aynı şekilde yorumlanabilir. Her bir kemerin uzunluğu, değiştirme maliyetine eşittir. Sorunu çözmek, düğüm 1 ve 5 arasındaki en kısa yolu belirlemeye eşdeğerdir.
Resim 6, ortaya çıkan ağı göstermektedir. TORA 2 kullanıldığında en kısa yol 1 S3 S5'tir.
Çözüm, 1. yılın başında (düğüm 1) satın alınan bir arabanın 3. yılın başında (düğüm 3) 2 yıl sonra değiştirilmesi gerektiğini gösteriyor. Değiştirilen araba daha sonra 4. yılın sonuna kadar hizmette kalacaktır. Bu değiştirme politikasının toplam maliyeti 12.500 $ 'dır.
(= 5400 ABD doları + 7100 ABD doları).
Teknolojik ağ modelleri
Ağ oluşturma modeli sürüm 3
Ağ Modeli Türleri
Ağ optimizasyon problemleri ailesi aşağıdaki model prototiplerini içerir: Atama problemleri, kritik yol, maksimum akış, en kısa yol, taşıma ve minimum akış maliyeti. Ağ yayları ve düğümleri kullanılarak sorunlar kolayca kurulur.
Ulaşım sorunları
Nakliye modelleri, maliyetleri düşürmek ve hizmetleri iyileştirmek için lojistik yönetiminde ve tedarik zincirinde önemli bir rol oynamaktadır. Bu nedenle amaç, malları taşımanın en uygun maliyetli yolunu bulmaktır. İçerisinde ürün tedariki bulunan "m" deposu bulunan bir distribütör, söz konusu ürünleri coğrafi olarak dağınık perakende merkezlerine göndermelidir, her biri belirli bir müşteri talebine sahip, örneğin kapsanması gerekir. Amaç, i'nci depo ile Cij olan j Th perakende merkezi arasındaki nakliye birimi başına maliyetler göz önüne alındığında mümkün olan en düşük nakliye maliyetini belirlemektir.
En Kısa Yol Problemleri
Sorun, bir kaynaktan belirli bir varış noktasına mümkün olan en ucuz yolu bulmak için bir ağı geçmenin en iyi yolunu belirlemektir. Belirli bir ağda m düğüm ve n yay (kenarlar) ve ağdaki her yay (iaj) ile ilişkili bir maliyet Cij olduğunu varsayalım. Resmi olarak, en kısa yol (CC) problemi, başlangıç düğümünden m düğümüne kadar en kısa yolu (en düşük maliyet) bulmaktır. Yolun maliyeti, gidilen her bir arkın maliyetlerinin toplamıdır. Xij ikili değişkenlerini tanımlayın, burada eğer yay (iaj) CC üzerindeyse Xij = 1 ve aksi takdirde Xij = 0. Kaynak ve hedef adında iki özel düğüm vardır. Amaç, başlangıç ve varış noktası arasındaki en kısa yolu bulmaktır.
Ağ Proje Planlamasında Kritik Yol
İnşaat, nakliye veya finans gibi iddialı bir projenin başarılı yönetimi, çeşitli görevlerin dikkatli koordinasyonuna ve planlanmasına dayanır. Kritik Yol (veya Yol) Yöntemi (CCM), proje planlamasını analiz etmeye çalışır. Bu, projenin daha iyi kontrol edilmesini ve değerlendirilmesini sağlar. Örneğin, projenin ne kadar süreceğini bilmek istiyoruz? Belirli bir görev ne zaman başlamaya hazır olacak? Görev zamanında tamamlanmadıysa, Projenin geri kalanı ertelenecek mi?
Projeyi daha erken bitirmek için hangi görevler hızlandırılmalıdır (etkili)?
Minimum Maliyet Akış Problemi
Yukarıdaki ağ sorunlarının tümü, minimum maliyet akışı sorununun özel durumlarıdır. Tepe akış problemi gibi, yetenekli ağlardaki akışları dikkate alır. En kısa yol problemi gibi, bu da bir yaya giden akış başına maliyeti dikkate alır. Ulaşım sorunu gibi, birden fazla başlangıç ve varış noktasına izin verir. Bu nedenle, tüm bu sorunlar minimum maliyet akışı sorununun özel durumları olarak görülebilir. Sorun, bazı düğümlerin mevcudiyetine ve talebine ve her bir ark boyunca akışın üst bağlantısına bağlı olarak toplam maliyeti en aza indirmektir.
Ağ Modelleri için Duyarlılık Analizi
Klasik bir ağ optimizasyon problemi ailesi şu model prototiplerini içerir: ayırma, kritik yol, maksimum akış, en kısa yol ve taşıma. Bu tür problemlerin doğrusal programlama olarak modellenebileceği iyi bilinmesine rağmen, genellikle asla yapılmazlar. Ağ modelleri için simpleks yönteminin (ilkel, ikili ve diğer varyasyonlar) verimsizliği ve göreceli karmaşıklığı nedeniyle, bu sorun 400'den fazla özel algoritmadan biri tarafından ele alınmaktadır. Bu birçok zorluğa yol açar. Algoritmaların çözümleri birleşik değildir ve her algoritma, belirli bir problemin özel yapısını keşfetmek için farklı bir strateji kullanır. Ek olarak, problemde ayrı bir kısıtın eklenmesi veya çoklu indeksler gibi küçük varyasyonlar,özel yapıyı yok eder ve algoritmayı yeniden başlamaya zorlar. Dahası, bu algoritmalar, bir duyarlılık analizi yapmak için yeterli bilgiye sahip olmayan bu algoritmaların nihai çözümü olarak, yönetimsel kurnazlık pahasına verimli çözümler elde eder.
Satıcının Seyahat Problemi
Bir satıcı 1, 2,.. N şehirlerini ziyaret etmelidir ve yolculuğu Memlekette başlar ve biter. Cij, verilen şehir ve şehir j seyahatinin maliyeti olsun. Sorun, şehirleri minimum maliyetle gezmek için en uygun düzeni belirlemektir. Akışların maksimizasyonu, birçok uygulamaya sahip olan Yöneylem Araştırmasında tipik bir sorundur, örneğin bir şehirdeki yol akışı, bir kanalizasyon ağı, bir bilgisayar ağı vb.
Sonuç
Sonuç olarak, yayların her ağdaki düğümlerin bağlayıcıları olduğunu söyleyebiliriz, bu modeller doğrudan veya dolaylı bir adrese sahip olabilir, her ağ içinde birkaç düğümü birleştirmeye ve böylece her birinde yollar oluşturmaya hizmet eden birden çok bağlayıcı olabilir. ağ, orijinal yolun dışındaki düğümleri birleştiren döngüler vardır.
Modeller ağ programları ile temsil edilebilir, minimum yayılma ağacı tekniği gibi ikinci versiyondakiler kısa mesafeler veya küçük yollar için kullanılır, maksimum akış tekniği akabilecek en fazla ne kadar olduğunu belirler. Bir ağ içinde, en kısa yol tekniği, başlangıç noktamızdan ve taşıma yolumuzdan en kısa yolu belirlememize yardımcı olur.
Ağ modellerinin belirli işçilik yönlerinde ortak bir kullanımı vardır ve bunlar sayesinde sorunları çözebiliriz ve farklı alanlarda geliştirilebilir, onlara en uygun rotaları kolaylaştırır.
Umarım bu makale çok yararlıdır ve içerdiği kavramlar net bir şekilde açıklanmıştır.
Referanslar
- Hillier, F., Lieberman, G. (2006). Yöneylem araştırmasına giriş. (8. Baskı) Meksika. McGraw Hill. ISBN 970-10-5621-3Oc, F, (2010), Models of networks-Investigación de Operaciones, http://www.slideshare.net/FreddOc/modelos-de-redes-investigacin-de-operacionesTaha, HA adresinden erişildi (2012), Investigation of Operations, (9.Baskı), Meksika, Pearson Education. ISBN: 978-607-32-0796-6 Raffo, E. (1990), Investigation of Operations, Lima, Raffo Lecca Editores, Library Code: 658.4034 / T16
