optimalizációs módszerek ”Titkos utazás”
”Réges-régen egy messzi-messzi galaxisban…”
Készítette: Gelencsér Tamás xdthsq
1. Bevezetés: „Nehéz idők járnak a Lázadókra. Habár a Halálcsillagot elpusztították, a Birodalmi erők kiűzték őket titkos támaszpontjukról és végigüldözték őket a Galaxis-on.A rettegett Birodalmi Csillagflotta elől menekülve a szabadságért küzdők maroknyi csapata, Luke Skywalker vezetésével új, titkos bázist létesített a távoli Hoth jégvilágában. A gonosz Vader nagyúr parancsára, távkutászok ezrei rajzottak ki az űrbe, hogy az ifjú Skywalker nyomára leljenek…” Menekülés közben, Luke Skywalker egy volt Birodalmi kommandóst (Kyle Katarn) küld a Vjun rendszerbe, Vader nagyúr erődjébe, hogy az ősi jedi holokronok lehetséges lelőhelyéről térképeket és információkat gyűjtsön. A pontosan megtervezett visszaút, nagyban hozzájárul a küldetés sikeréhez…
2. Információk az utazásról: A visszaútról a következő ábra áll a rendelkezésre, ahol a piros a birodalmi, a kék a semleges, a zöld pedig a Szövetséges bolygókat jelöli. A nyilak a lehetséges útvonalakat jelölik (fekete-barna között nincs különbség):
Továbbá minden bolygóról rendelkezünk egy menetrenddel, ami tartalmazza az utazásidőt és a várakozásidőt is: Honnan|Hova: Vjun
Taris 10
Chazwa 5
Taanab 4
Nar Shaddaa 7
Honnan|Hova: Taris Chazwa Taanab Nar Shaddaa
Vortex 12 7 N/A N/A
Carnatos 8 5 6 8
Balmora 7 4 7 9
Manaan N/A 5 6 7
Honnan|Hova: Vortex Carnatos Balmora Manaan
Galantos 12 8 9 13
Coruscant 10 5 7 8
Honnan|Hova: Galantos Coruscant Corellia
Codian Moon 15 N/A N/A
Honnan|Hova: Codian Moon Byss Devaron Tyana
Cerea 5 N/A N/A N/A
Ghorman N/A 8 10 9
Umgul N/A N/A N/A 12
Honnan|Hova Cerea Ghorman Umgul Lorta Nkllon
Lorta 8 7 N/A N/A N/A
Nkllon 5 5 N/A N/A N/A
Hoth N/A N/A 6 4 5
Byss 10 8 12
Devaron N/A 9 9
Corellia N/A 7 5 10 Tyana N/A 10 7
A rendszer magja felé egyre nagyobb a veszélye a lebukásnak (egyre több az ellenőrző pont), illetve a Birodalmi bolygókon drágábban lehet csak megfelelően biztonságos szállást találni. Ezeket az adatokat az alábbi táblázat foglalja össze: Bolygó neve: Taris Chazwa Taanab Nar Shaddaa Vortex Carnatos Balmora Manaan Galantos Coruscant Corellia Codian Moon Byss Devaron Tyana Cerea Ghorman Umgul Lorta Nkllon
Szállás: 100 220 220 100 220 220 220 220 220 220 220 100 220 220 220 0 0 100 100 0
Ellenőrzőpontok száma: 1 3 3 1 1 5 5 3 5 10 5 1 5 5 3 0 0 1 1 0
A visszaútra 800 kredit áll rendelkezésre, és az ügynök maximum 15 ellenőrzőponton tud észrevétlenül átjutni. Az indulásig még 3 nap van hátra, így még kaphatunk plusz információkat a Bothán Kémhálózattól, ami megváltoztathatja a visszaút megtervezését.
3. A visszaút megtervezése: A csillagtérképet a legegyszerűbb módon egy gráfként tudjuk értelmezni, ahol a bolygók a csúcsok és a lehetséges útvonalak az őket összekötő éleknek felnek meg. Számunkra az utazás a fontos (tehát az élekre koncentrálunk), nem pedig az, hogy melyik bolygókat érintettük, így a bolygókhoz egy sorszámot rendelünk, ezzel leegyszerűsítve a kezelésüket: 1. Vjun 2. Taris 3. Chazwa 4. Taanab 5. Nar Shaddaa 6. Vortex 7. Carnatos 8. Balmora 9. Manaan 10. Galantos 11. Coruscant
12. Corellia 13. Codian Moon 14. Byss 15. Devaron 16. Tyana 17. Cerea 18. Ghorman 19. Umgul 20. Lorta 21. Nkllon 22. Hoth
A következő lépésben a fent meghatározott táblázatokból kinyerjük a szükséges információkat és egy mátrixba rendezzük őket (bolygók számozással): Honnan-Hova : 1 →2 1 →3 1 →4 1 →5 2 →6 2 →7 2 →8 3 →6 3 →7 3 →8 3 →9 4 →7 4 →8 4 →9 5 →7 5 →8 5 →9 6 →10 6 →11 7 →10 7 →11 7 →12 8 →10 8 →11 8 →12
út szállás: ellenőrzőpont: 10 100 1 5 220 3 4 220 3 7 100 1 12 100 1 8 220 5 7 220 5 7 100 1 5 220 5 4 220 5 5 220 3 6 220 5 7 220 5 6 220 3 8 220 5 9 220 5 7 220 3 12 220 5 10 220 10 8 220 5 5 220 10 7 220 5 9 220 5 7 220 10 5 220 5
9 →10 9 →11 9 →12 10 →13 10 →14 11 →14 11 →15 11 →16 12 →14 12 →15 12 →16 13 →17 14 →18 15 →18 16 →18 16 →19 17 →20 17 →21 18 →20 18 →21 19 →22 20 →22 21 →22
13 8 10 15 10 8 9 10 12 9 7 5 8 10 9 12 8 5 7 5 6 4 5
220 220 220 100 220 220 220 220 220 220 220 0 0 0 0 100 100 0 100 0 0 0 0
5 10 5 1 5 5 5 3 5 5 3 0 0 0 0 1 1 0 1 0 0 0 0
Feltételek meghatározása: a.) A legfontosabb feltétel, aminek mindenképpen eleget kell tennünk, hogy utat tervezzünk: tehát, ha egy csúcsba bemegyünk, onnan ki is kell jönnünk. A legegyszerűbb megoldás, ha kezdő ponthoz egy bemenő élt a végponthoz egy kimenő élt rendelünk, így biztos, hogy az algoritmus a két pont között keresi az utat. b.) Továbbá, felső korlátunk van az elkölthető kreditre illetve az ellenőrző pontok maximális számára, amit figyelembe kell vennünk az algoritmus tervezésekor. Ha az előbb említett feltételeknek eleget teszünk, akkor már csak a cél függvényt kell minimalizálni, azaz meg kell keresni a legrövidebb utat.
4. GLPK A feladat megoldását két fájlban oldottam meg (Windows-t használok, így hazi.m.txt illetve hazi.d.txt a kiterjesztés). Hazi.m.txt: param koltseg{(i,j) in HonnanHova}; /*Bolygon tartozkodas koltsege*/ param danger{(i,j) in HonnanHova}; /*Bolygon tartozkodas veszelyessege*/ param start, integer > 0; /*Kezdo bolygo*/ param cel, integer > 0; /*Cel bolygo*/ param penz, integer > 0; /*Rendelkezesre allo kredit*/ param veszely, integer > 0; /*Rejtezkodes*/ var x{(i,j) in HonnanHova}, binary; /*Változó ami az éleket jelöli ki, utaztunk vagy nem*/ s.t. beelkiel{i in 1..Bolygokszama}: sum{(j,i) in HonnanHova} x[j,i] + (if i = start then 1) = sum{(i,j) in HonnanHova} x[i,j] + (if i = cel then 1); /*Azt vizsgaljuk, ha bolygora elmentunk onnan el is kell jonnunk*/ s.t. szallas: sum{(i,j) in HonnanHova} (x[i,j] *koltseg[i,j]) <= penz; /*Szallast kitudjuk-e fizetni*/ s.t. lebukas: sum{(i,j) in HonnanHova} (x[i,j] *danger[i,j]) <= veszely; /*Elkerulheto-e a lebukas*/ minimize utazas: sum{(i,j) in HonnanHova} ut[i,j] * x[i,j];
A program megírás közben arra törekedtem, hogy minél kevésbé legyen „bedrótozva”, ezért amit csak lehetett paraméterként definiáltam: param start, cel, veszely, penz … s.t. beelkiel{i in 1..Bolygokszama}: sum{(j,i) in HonnanHova} x[j,i] + (if i = start then 1) = sum{(i,j) in HonnanHova} x[i,j] + (if i = cel then 1);
Minden csúcsra ellenőrzi, hogy a belépő élek száma megegyezik-e a kilépő élek számával (esetünkben 1 ki 1 be). s.t. szallas: sum{(i,j) in HonnanHova} (x[i,j] *koltseg[i,j]) <= penz;
A kiválasztott élekhez tartozó szállás költség szummája belefér-e a keretbe. s.t. lebukas: sum{(i,j) in HonnanHova} (x[i,j] *danger[i,j]) <= veszely;
A kiválasztott élekhez tartozó ellenőrzőpontok száma kisebb-e, mint a megadott összeg. minimize utazas: sum{(i,j) in HonnanHova} ut[i,j] * x[i,j];
A fenti feltételekkel minimalizáljuk a utazás időtartalmát. Az adatokat a Hazi.d.txt fájlba töltöttem fel és futtattam a Hazi.m.txt modellre. A jelenlegi adatokkal a következő megoldást kaptam: 1-5 5-8 8-12 12-16 16-18 18-21 21-22, ami azt jelenti, hogy a legrövidebb út: Vjun – Nar Shaddaa – Balmora – Corellia – Tyana – Ghorman – Nkllon – Hoth. Idő: 47 nap, Költség: 760 kredit, Ellenőrzőpont: 14.
MAY THE Force Be with You!!!
Függelék: Hazi.m.txt: param Bolygokszama, integer > 0; /*Grafcsucsai*/ set HonnanHova, within {i in 1..Bolygokszama, j in 1..Bolygokszama}; /*Grafelei*/ param ut{(i,j) in HonnanHova}; /*Grafeleinek a sulya*/ param koltseg{(i,j) in HonnanHova}; /*Bolygon tartozkodas koltsege*/ param danger{(i,j) in HonnanHova}; /*Bolygon tartozkodas veszelyessege*/ param start, integer > 0; /*Kezdo bolygo*/ param cel, integer > 0; /*Cel bolygo*/ param penz, integer > 0; /*Rendelkezesre allo kredit*/ param veszely, integer > 0; /*Rejtezkodes*/ var x{(i,j) in HonnanHova}, binary; /*Változó ami az éleket jelöli ki, utaztunk vagy nem*/ s.t. beelkiel{i in 1..Bolygokszama}: sum{(j,i) in HonnanHova} x[j,i] + (if i = start then 1) = sum{(i,j) in HonnanHova} x[i,j] + (if i = cel then 1); /*Azt vizsgaljuk, ha bolygora elmentunk onnan el is kell jonnunk*/ s.t. szallas: sum{(i,j) in HonnanHova} (x[i,j] *koltseg[i,j]) <= penz; /*Szallast kitudjuk-e fizetni*/ s.t. lebukas: sum{(i,j) in HonnanHova} (x[i,j] *danger[i,j]) <= veszely; /*Elkerulheto-e a lebukas*/ minimize utazas: sum{(i,j) in HonnanHova} ut[i,j] * x[i,j]; /*A fenti feltetelek mellett a legrovidebb utat keressuk*/
Data.m.txt: /*Az adott parameterek tarolasara*/ param Bolygokszama:= 22; param start := 1; param cel := 22; param penz := 800; param veszely := 15; param : HonnanHova : 1 2 1 3 1 4 1 5 2 6 2 7 2 8 3 6 3 7 3 8 3 9 4 7 4 8 4 9 5 7 5 8 5 9 6 10 6 11 7 10 7 11 7 12 8 10 8 11 8 12 9 10 9 11 9 12 10 13 10 14 11 14 11 15 11 16 12 14 12 15 12 16 13 17 14 18 15 18 16 18 16 19 17 20 17 21 18 20 18 21 19 22 20 22 21 22
ut
koltseg danger:=
10 5 4 7 12 8 7 7 5 4 5 6 7 6 8 9 7 12 10 8 5 7 9 7 5 13 8 10 15 10 8 9 10 12 9 7 5 8 10 9 12 8 5 7 5 6 4 5
100 220 220 100 100 220 220 100 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 220 100 220 220 220 220 220 220 220 0 0 0 0 100 100 0 100 0 0 0 0
1 3 3 1 1 5 5 1 5 5 3 5 5 3 5 5 3 5 10 5 10 5 5 10 5 5 10 5 1 5 5 5 3 5 5 3 0 0 0 0 1 1 0 1 0 0 0 0;
Eredmény: Problem: hazi Rows: 25 Columns: 48 (48 integer, 48 binary) Non-zeros: 222 Status: INTEGER OPTIMAL Objective: utazas = 47 (MINimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------1 beelkiel[1] -1 -1 = 2 beelkiel[2] 0 -0 = 3 beelkiel[3] 0 -0 = 4 beelkiel[4] 0 -0 = 5 beelkiel[5] 0 -0 = 6 beelkiel[6] 0 -0 = 7 beelkiel[7] 0 -0 = 8 beelkiel[8] 0 -0 = 9 beelkiel[9] 0 -0 = 10 beelkiel[10] 0 -0 = 11 beelkiel[11] 0 -0 = 12 beelkiel[12] 0 -0 = 13 beelkiel[13] 0 -0 = 14 beelkiel[14] 0 -0 = 15 beelkiel[15] 0 -0 = 16 beelkiel[16] 0 -0 = 17 beelkiel[17] 0 -0 = 18 beelkiel[18] 0 -0 = 19 beelkiel[19] 0 -0 = 20 beelkiel[20] 0 -0 = 21 beelkiel[21] 0 -0 = 22 beelkiel[22] 1 1 = 23 szallas 760 800 24 lebukas 14 15 25 utazas 47 No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------1 x[1,2] * 0 0 1 2 x[1,3] * 0 0 1 3 x[1,4] * 0 0 1 4 x[1,5] * 1 0 1 5 x[2,6] * 0 0 1 6 x[2,7] * 0 0 1 7 x[2,8] * 0 0 1 8 x[3,6] * 0 0 1 9 x[3,7] * 0 0 1 10 x[3,8] * 0 0 1 11 x[3,9] * 0 0 1 12 x[4,7] * 0 0 1 13 x[4,8] * 0 0 1 14 x[4,9] * 0 0 1
15 x[5,7] * 16 x[5,8] * 17 x[5,9] * 18 x[6,10] * 19 x[6,11] * 20 x[7,10] * 21 x[7,11] * 22 x[7,12] * 23 x[8,10] * 24 x[8,11] * 25 x[8,12] * 26 x[9,10] * 27 x[9,11] * 28 x[9,12] * 29 x[10,13] * 30 x[10,14] * 31 x[11,14] * 32 x[11,15] * 33 x[11,16] * 34 x[12,14] * 35 x[12,15] * 36 x[12,16] * 37 x[13,17] * 38 x[14,18] * 39 x[15,18] * 40 x[16,18] * 41 x[16,19] * 42 x[17,20] * 43 x[17,21] * 44 x[18,20] * 45 x[18,21] * 46 x[19,22] * 47 x[20,22] * 48 x[21,22] *
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Integer feasibility conditions: KKT.PE: max.abs.err = 0.00e+000 on row 0 max.rel.err = 0.00e+000 on row 0 High quality KKT.PB: max.abs.err = 0.00e+000 on row 0 max.rel.err = 0.00e+000 on row 0 High quality End of output
