MATHEMATICAL MODELLING OF PLACEMENT OF EMERGENCY PHONE CENTRES IN A CAMPUS NETWORK

Year 2011, Volume: 13 Issue: 1, 1 - 8, 01.01.2011

Pınar Dündar Mehmet Ali Balcı Elgin Kılıç

Abstract

In this study graph set covering problem which is a problem of defining relations in a
network by using less number of objects, is examined by the aid of graphs that are used
mostly in design of communication networks. Cover problem is also known as the distinct
optimization problem in this field of study. The problem of placement of emergency phones in
Ege University Campus to provide security is considered as a cover problem. The obtained
linear programming problem is solved by WQSB and the result that at least number of places
which a phone is required to be placed, is found.

Keywords

Mathematical modelling, Discrete optimization, Graph theory, Network structure

BİR KAMPÜS AĞINDA ACİL TELEFON MERKEZLERİ YERLEŞTİRİLMESİ PROBLEMİNİN MATEMATİKSEL MODELLEMESİ

Abstract

Bir G grafında, seçilen bazı tepeler yardımıyla grafın tüm ayrıtlarını tanımlama graf
örtüsü problemi olarak bilinir. Başka bir açıdan bakıldığında örtü problemi; sayılabilir bir
küme üzerinde verilmiş bir bağıntıyı, bu kümenin minimum sayıda elemanını kullanarak
tanımlama olarak düşünülebilir. Optimizasyon teorisinde; bir G grafının örtü kümeleri içinden
en az elemanlısını bulmaya minimal örtü problemi adı verilir. Bu problem literatürde bir
discrete optimizasyon problemi olarak bilinmektedir. Problem doğrusal programlama ile
matematiksel olarak ifade edilebilir. Bu çalışmada iletişim ağı grafla modellenerek, bu ağda
ilişkileri minimum sayıda elemanla tanımlayan graf örtüsü problemi ele alınmıştır. Örtü
probleminin genel doğrusal programlama modeli verilerek çözüm araştırılmıştır. Daha sonra
uygulama problemi olarak ele alınan, Ege Üniversitesi Kampüsünde güvenliği sağlamak
amacıyla acil telefonlarının yerleştirilmesi problemi, bir örtü problemi olarak modellenmiştir.
Elde edilen doğrusal programlama problemi WQSB programı yardımı ile çözülüp minimum
sayıda hangi noktalara telefon yerleştirilmesi gerektiği hesaplanmıştır.

Keywords

Matematiksel modelleme, Ayrık optimizasyon, Graf teori, Ağ yapıları

References

• Beasley J. E. (1987): “An Algorithm for Set Covering Problems, Europen Journal of Operational Research”, 31, s. 85-93.
• Beasley J. E., Jörnsten K (1992): “Enhancing an Algorithm for Set Covering Problems”, European Journal of Operational Research, 58, s. 293-300.
• Buckley F., Harary F. (1990): “Distance in Graphs”, Addison Wesley Pub., California.
• Chartrand G., Leisnak L. (1986): “Graphs & Digraphs”, Wadsworth & Brooks.
• Christofides N. ,(1986): “Graph Theory: An Algorithmic Approach”, Academic Press, London.
• West D.B. (2001): “Introduction to Graph Theory”, Prentice Hall.