Küme bölme problemlerinin optimizasyonu ve Türkiye futbol liglerine uygulanması

Abstract

Bu çalışmanın esas amacı, küme bölme (set partitioning) problemlerinin yapısal özelliklerini ortaya koyarak bu problemlerin çözümü için kullanılabilecek algoritmaları araştırmak ve Türkiye ikinci ve üçüncü futbol liglerinde alt grupların belirlenmesi sorununu çözecek uygun bir algoritma önermektir. Küme bölme problemi, 0-1 tamsayılı doğrusal modelin özel bir hali olarak ortaya çıkar: Min. Z = SjeN cjxj v-< Kısıtlar: ZojeN aijxj=1 ieM, M = {1,2,...,m}, Xj?{0,l}, aije{0,l}, CjâO, jeN, N = {1,2,...,n} Bu problemlerin çözümünde; önce, olası alt kümelerden oluşan küme bölme tablosu hazırlanarak 0-1 tamsayılı doğrusal modeli kurulur. Problemin optimizasyonunda tamsayımlama ve/veya kesme düzlemi tekniklerine dayanan fakat bu problemlerin yapısına uygun olarak hazırlanan özel algoritmalar kullanılır. Bu tez çalışmasında, Türkiye futbol liglerinde alt grupların belirlenmesi (ve benzeri) sorunların küme bölme problemleri olarak çözümünde kullanılabilecek uygun bir algoritma önerildi. Uygulama çalışmaları sonucunda, bu tür sorunların çözümünde en uygun modelin küme bölme modeli olduğu gözlendi.1992-1993 Sezonunda Türkiye ikinci ve üçüncü futbol liglerinde alt grupların belirlenmesi sorunu, küme bölme problemi olarak düzenlenip çözüldü. Futbol Federasyonunun bu sezonda uyguladığı plana göre takımların ve taraftarlarının deplasman maçları için gidecekleri yolun uzunlumu 1471972 Km. iken, optimum plana göre bu rakam 1291436 Km. olarak ortaya çıktı. Bu sonuçlara göre optimum planın maliyeti Futbol Federasyonu tarafından belirlenen planın maliyetine nazaran 180536 Km. (oran olarak 112.3) daha düşük olmaktadır. Km olarak belirlenen bu rakamın parasal karışılıg`ının 1993 yılı fiyatlarıyla yaklaşık 100 milyar lira civarında olduğu tahmin edilmektedir.

The main purpose of this study is to research algorithms vhich can be used for the solutions of the set partitioning problems by bringing up the structural characteristics of these problems and is suggesting a convenient algorthm vhich vill solve the problem of determining subgroups in the second and the third football leauges in Turkey. The set partitioning problem appears as a special case of linear model which has integers of 0-1: /7 Mi ni mi z e 2jj e N Çj Xj ^rt Subject to ZjjeN aij^j=l *e^ ^ = {1^2,...,m}, Xje{0,l}, aij?{0,l}, CjâO, j eN N = {1,2,..., n} in the solutions of these problems; first, the linear model is set vrhich has integers of 0-1 by prepearing the set partitioning table composed of possible subsets. The special algorithms based on implicit enumeration and/or cutting plane techniques but prepared in accordance with the structure of the problem are used in the optimization of the problem. in this thesis, a convenient algorithm which vill be able to used in the solution of the guestions of determining subgroups in the football leagues in Turkey (and similar questions) was suggested. As a result of practicing studies, it was observed that the most convenient model was set partitioning model in the solutions of such guestions..The question ör determining the subgroups in the second and third football leauges in Turkey in the seasons of 1992-1993, was organized and solved as a set partitioning problem. ¥hile the length of the way which has to be covered by supporters and teams for displacement matches is 1471972 kilometres according to the existing schedules programmed by Turkish Football Federation, this figüre has appeared as 1291436 kilometres according to the optimum plan. in the light of these results, the cost of optimum plan is 180536 kilometres that is, per cent 12.3 l över with regard to the cost of the schedules which vas determined by Turkish Football Federation. The monetary equivalent of this figüre determined as kilometer has been guessed about hundred billions liras vith the prices of 1993.