Kellemetlen üzem elhelyezése Magyarországon - leírása

Feladat: A feladat egy olyan kellemetlen gyár telepítési helyszín meghatározása, amelyre a magyarországi nagyobb városok lakosai számával arányos elutasítás figyelembevételével a lehető legkisebb gondot okozza.

További megszorításokat is teszünk:

• nem lehet a város 5 km-es körzetében
• nem lehet a határ 50 km-es körzetében sem.

A célfüggvény ennek megfelelően:

f(x,y)=Σ_{(i : város)} l_i / ((x-x_i)²+(y-y_i)²)^1/2

Ahol l_i az i-edik város ellenszenvének súlya, x_i és y_i pedig a koordinátái. A célunk pedig f(x,y) minimalizálása.

A feladat megoldására kifejlesztett demó program:

A programban Magyarország városai szerepelnek (249 db), melyek közül egy listából kiválasztható, hogy melyek jelenjenek meg a térképen (alapértelmezésben a megyeszékhelyek). A városok súlya hasonlóképpen megadható - kiválasztjuk a várost és megadjuk az értéket. (Ez alapértelmezésben a városok lakosainak száma, melyet a KSH 2004-es népszámlálási adataiból vettem.)

A programban kétféle algoritmus van megvalósítva a célfüggvény minimalizálására:

• teljes leszámolás módszere: minden pontra megnézi a célfüggvényértéket, és a legkisebb lesz a végeredmény. Közben a térképen megjelenik az aktuális minimum helye (egy piros pont sárga körrel keretezve), és a számítás végeztével pedig a tényleges optimum.
• gradiens módszer: a térképre klikkelve kiválaszthatjuk a kezdőpontot, ahonnan az optimalizálást kezdjük, majd elindítva azt az optimumpont elkezd "vándorolni" a térképen, mégpedig a legnagyobb célfüggvényérték-csökkenés irányába. Az így megtalált optimum azonban nem globális minimum! Ez a módszer csak egy helyi minimumot talál meg, azonban igen látványos, ahogy a pontunk "szlalomozik" a városok között.

A program extrái:

• Váltogathatunk a megjelenítési stílusok között (amennyiben több megjelenítési séma is telepítve van számítógépünkre)
• Törekedtem a látványosságra és érthetőségre a térkép és a kezelőfelületek esetén is
• A különböző funkciókat külön ablakban helyeztem el, melyek elrendezése tetszés szerint változtatható
• A könnyebb kezelhetőség érdekében a városok mindegyike egy gombnyomásra ("mind") kirajzoltatható a térképre, lehetőség van csak a megyeszékhelyek megjelenítésére ("csak megyeszákhelyek"), valamint visszaállítható a kezdőállapot ("eredeti")
• A menüsorban megtalálható a "Súgó" is, amiből megismerhetjük a program alapvető funkcióit
• A térkép egy pontjára klikkelve a "vezérlőablak"-ban megjelenik az adott pontbeli célfüggvényérték.
• A könnyebb kezelhetőséget segíti, hogy lehetőség van file-ból beolvasni az inputot, így könnyen megváltoztathatjuk a városok értékét ("File/File-ból beolvas").

A program indítható alkalmazásként és appletként is. (A program futtatásához java interpreter szükséges, appleként való indításhoz pedig java-appletet támogató böngésző és java-plugin.)

Forrás letöltése

Összes letöltése

© Gara Mihály - 2006. április 16.