ÖRNEK BİR KÜME KAPLAMA PROBLEMİNİN GAMS İLE ÇÖZÜMÜ
Ankara’nın Çankaya ilçesinin emek,bahçelievler,devlet,merkez,öveçler,dikmen,oran,birlik ve cebeci semtlerine en az sayıda itfaiye istasyonu kurulmak isteniyor. Amaç kurulacak olan istasyon sayısını minimize etmek ve olay yerine en fazla 10 dakika içerisinde ulaşmaktır. Problem küme kaplama modeli olarak yazılmış ve ardından GAMS ile çözülmüştür.
Düğümler
|
SEMT İSİMLERİ
|
1
|
EMEK MAH.
|
2
|
BAHÇELİEVLER MAH.
|
3
|
DEVLET MAH.
|
4
|
ÇANKAYA MAH.
|
5
|
ÖVEÇLER MAH.
|
6
|
DİKMEN MAH.
|
7
|
ORAN MAH.
|
8
|
BİRLİK MAH.
|
9
|
CEBECİ MAH.
|
Semtlere numaralar verilip birbirine ulaşma süreleri ise aşağıda tabloda verilmiştir. Birbirleriyle direk ulaşımı olmayanların en kısa ulaşma süreleri hesaplanmıştır.
DK
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
1
|
0
|
7
|
9
|
17
|
13
|
19
|
19
|
24
|
21
|
2
|
7
|
0
|
11
|
19
|
17
|
23
|
26
|
26
|
14
|
3
|
9
|
11
|
0
|
8
|
6
|
12
|
21
|
15
|
13
|
4
|
17
|
19
|
8
|
0
|
9
|
10
|
15
|
7
|
21
|
5
|
13
|
17
|
6
|
9
|
0
|
6
|
15
|
16
|
19
|
6
|
19
|
23
|
12
|
10
|
6
|
0
|
11
|
14
|
25
|
7
|
19
|
26
|
21
|
15
|
15
|
11
|
0
|
25
|
40
|
8
|
24
|
26
|
15
|
7
|
16
|
14
|
25
|
0
|
19
|
9
|
21
|
14
|
13
|
21
|
19
|
25
|
40
|
19
|
0
|
Problemin Matematiksel Modeli
İtfaiye için ulaşma
kısıtını 10 dakika alarak aşağıdaki model kurulmuştur.
Minimize Z = x1+x2+x3+x4+x5+x6+x7+x8+x9
Subject to
x1 +x2
+ x3
>= 1;
x1+x2 >=1;
x1+ x3+x4+x5 >=1;
x3+x4+x5+x6+ x8 >=1;
x3+x4+x5+x6 >=1;
x4+x5+x6 >=1;
x7 >= 1;
x4+ x8 >=1;
x9 >=1;
Xi
{0,1}
Her i için
Gams Modeli
Sets
i dugum /1*9 /
j aday tesisler / 1*9 / ;
table t(i,j) semtlerin birbirine ulasma sureleri
1 2 3 4 5 6 7 8 9
1 0 7 9 17 13 19 19 24 21
2 7 0 11 19 17 23 26 26 14
3 9 11 0 8 6 12 21 15 13
4 17 19 8 0 9 10 15 7 21
5 13 17 6 9 0 6 15 16 19
6 19 23 12 10 6 0 11 14 25
7 19 26 21 15 15 11 0 25 40
8 24 26 15 7 16 14 25 0 19
9 21 14 13 21 19 25 40 19 0 ;
variable
z;
binary variable x(j);
equations
amac, kisit ;
amac.. z =e= sum (j,x(j));
kisit(i).. Sum(j$(t(i,j)<=10), x(j))=G=1;
model kumekaplama/all/;
solve kumekaplama using MIP minimizing z;
display x.l;
Gams Çıktısı
LOWER LEVEL UPPER MARGINAL
1 . 1.000 1.000 1.000
2 . . 1.000 1.000
3 . . 1.000 1.000
4 . 1.000 1.000 1.000
5 . . 1.000 1.000
6 . . 1.000 1.000
7 . 1.000 1.000 1.000
8 . . 1.000 1.000
9 . 1.000 1.000 1.000
Yani her semte en az 10 dakikada ulaşabilmek için 1.semte, 4.semte,7.semte ve 9.semte istasyon kurulması gerektiği ortaya çıkmıştır.
