A kutatás célja
Általános egyensúlyi modellek:
A kérdéskörhöz tartozik például az Arrow-Deberu piaci egyensúlyi modell megoldásának keresése, amire egyelőre csak speciális (lineáris) célfüggvény esetén létezik hatékony megoldó algoritmus. Ide tartozik még portfóliók kockázatkezelési feladata, ami felfogható több célfüggvényű optimalizálási problémának is. A gyakorlatban fontos esetek gyakran vezetnek NP—teljes problémára, ezért nagyon ritka, hogy olyan módszert találunk, mely gyakorlati feladatok megoldására használható. Ezekben az esetekben vagy ki kell használnunk a feladatunk valamilyen speciális strukturális tulajdonságát, ami mégis lehetővé teszi, hogy megtaláljuk a megoldást, vagy valamilyen közelítő eljárást kell alkalmaznunk. Mivel mindkét megoldásra az a jellemző, hogy csak nagyon speciális körülmények között használhatók, ezért e témakörökben bőségesen akadnak hozzáférhető megoldatlan problémák.
Hatékony pivot algoritmusok hálózati és többtermékes hálózati folyamfeladatokra:
A hálózati, és többtermékes hálózati folyamfeladatok gyakorlati alkalmazása igen sokrétű. Az eszköz és személyzet hozzárendelési feladatoktól kezdve, az ellátási láncoknál (supply chain), illetve a termeléstervezési feladatoknál, mint részfeladatok jelentkezhetnek hálózati folyamfeladatok. Ezek megoldásához célszerű olyan keretalgoritmusokat kidolgozni, amelyek a részfeladatok, illetve a teljes feladat megoldását azonos (vagy nagyon hasonló) pivot algoritmusokkal oldják meg. Elméleti és gyakorlati szempontból az olyan pivot algoritmusok az érdekesek, amelyek egyszerűekés polinomiális futásidejűek. Goldfarb, Hao és mások kidolgozták a primál és duál szimplex módszer polinomiális változatait maximális folyam minimális vágás feladatokra, illetve a minimális folyam problémára. Érdekes lenne olyan pivot algoritmusok hálózati folyamfeladatra alkalmazható változatait megvizsgálni, amelyekről meg-állapítható, hogy lehetséges-e polinom futásidejű variánst készíteni, vagy sem. A többtermékes hálózati folyamfeladatokról tudjuk, hogy az elvárt egész-értékű megoldás előállítása NP-teljes feladat. Legjobb tudomásunk szerint viszont senki sem vizsgálta azt az érdekesnek tűnő kérdést, hogy többtermékes hálózati folyam-feladat lineáris programozási relaxáltja megoldható-e pivot algoritmussal polinom időben, vagy sem. Ebben a témakörben további érdekes elméleti és gyakorlati kérdések vethetők fel.
Technikai leírás
Valamennyi kutatási feladathoz szükséges mind az analitikus módszerek (matematikai bizonyítások), mind a számítógépes eszközök (szimulációk, konkrét feladatokhoz kapcsolódó számítások) alkalmazása. Mindegyik említett témára vonatkozik, hogy a matematikai modellek kipróbálásához és értékeléséhez szükséges a numerikus eljárásokat számítógéppel tesztelni. Ehhez mindenképpen szükséges egy gyors és megbízható számítógép, ideális esetben a klaszter alapú szuperszámítógép.
A bemutatott kutatási irányok kidolgozásához a matematikában szokásos kutatási módszertan alkalmazása látszik megfelelőnek. Az egyes kérdéskörök már létező irodalmának áttekintése után matematikai fogalomalkotásokra, sejtések kialakítására, majd ezek vizsgálatára, tétel-bizonyításokra van szükség. E munka elvégzésére kiváló kereteket biztosít, és inspiráló légkört teremt az egyes kisebb szellemi műhelyek által rendszeresen megrendezett szemináriumi munka, ahol az elért részeredményeket és felmerülő ötleteket a résztvevők együtt beszélik meg, illetve együtt gondolkodhatnak a fellépő nehézségek kezelésének módján.
Egyes vizsgálati irányokban (különösen a csoportreprezentációk kérdéskörében) a sejtések kialakítása számítógépes kísérletekre, „szimulációkra” alapozható. Ezek a példák szolgáltathatják azt a tapasztalatot, melyből – szerencsés esetben – lehetőség van az általános, absztrakt törvényszerűségeket felismerni. A fent bemutatott vizsgálati irányok egy további jelentős részében (pl. a többtermékes hálózati folyamfeladatok kapcsán) pedig pont az a cél, hogy olyan algoritmusokat, módszereket dolgozzunk ki, melyek eddig reménytelenül nagynak tűnő adatszerkezeteket dolgoznak fel hatékonyan. Ebben az esetben szükség van rendkívül nagy számítási kapacitású számítógépre.
A várt eredmények összefoglalása
Általános egyensúlyi modellek:
A gazdasági élet különböző döntés előkészítési kérdéseihez fogunk tudni új módszereket biztosítani. Mint említettük, számos ilyen kérdés – teljes általánosságában – NP-teljes, ezért nem várható, hogy kezelésükhöz hatékony módszereket sikerül találni. A vizsgált konkrét kérdések speciális szerkezetén alapuló megoldási lehetőségek, és az elméleti optimum megkeresése helyett közel-optimális megoldásokat szolgáltató módszerek kidolgozásával egyrészt használható megoldásokat biztosítunk a vizsgált konkrét kérdésekre. Másrészt e módszerek rendszerezésétől várható, hogy sikerül azokat a fogalmi kereteket kialakítani, melyek elvezethetnek a vizsgálatainkban szereplő kérdéseknél tágabb, absztraktabb feladatosztályok hatékony kezelésére alkalmas módszerek megvalósításához is.
Hatékony pivot algoritmusok hálózati és többtermékes hálózati folyamfeladatokra:
A várt eredmények tartalmi szempontból megegyeznek az előző pontban leírtakkal. Többtermékes hálózati folyamfeladatok hatékony megoldására szükség lehet pl. különböző hozzárendelési és termeléstervezési feladatok végrehajtása során.
A tehetséggondozás formája a kutatás során
A fentebb vázolt kutatások jelentősége kettős. Egyrészt, a matematikai alapkutatások szempontjából, az említett vizsgálatok az adott terület nemzetközi élvonalát leginkább foglalkoztató kérdésekre irányulnak. A vázolt eredmények kellően jelentősek ahhoz, hogy azokkal fel lehet kelteni a nemzetközi közösség figyelmét, be lehet kapcsolódni annak vérkeringésébe, további jelentős kutatói projektekbe. Ehhez a BME Matematika Intézete által biztosított kiterjedt kutatói kapcsolatrendszer is kiváló hátteret teremt. Másrészt feltétlen érdemes kiemelni az alkalmazási lehetőségek széles körét, többek között a fizika, a kémia, az informatika és a mechanika különféle területein. Itt fontos megemlítenünk a Budapesti Műszaki és Gazdaságtudományi Egyetem különböző szervezeteivel, a támogatásban részesülő további doktori iskolákkal való jó kapcsolatainkat.
A vázolt kutatásokat – senior oktatói-kutatói témavezetés mellett – a doktori iskola hallgatói végzik. Célunk, hogy ezek a hallgatók a kutatás során elért eredményeik alapján hatékonyan élhessenek a fent említett lehetőségek széles körével. A kutatás technikájának megismerése mellett hallgatóink segítséget kapnak az eredmények dolgozatokban és előadásokon való bemutatásánál, kutatói kapcsolatok megteremtésében és ápolásában, az alkalmazási lehetőségek feltérképezésében is.
A doktori iskola számos korábbi hallgatója ma kiválóan megállja a helyét, mint világszerte elismert alapkutató, vagy az innováció szempontjából jelentős fejlesztéseken dogozó alkalmazott kutató. Bízunk benne, hogy a támogatással tovább bővül azon hallgatóink száma, akik később a kutatói élet különböző területein sikeresen képesek elhelyezkedni.
A bemutatott vizsgálati irányok mindegyike korszerű, jelenleg – nemzetközi vonatkozásban is – igen aktív kutatásokhoz kapcsolódik. A felvetett problémák megoldásit – tapasztalt témevezetők irányításával – a BME Matematika Doktori Iskola doktorandusz hallgatói dolgozzák ki. E munka során átélhetik a szellemi alkotás örömét, megismerhetik a matematikai kutatás módszertanát, a tudományos közlemények és konferencia-előadások összeállításának technikáját, sőt, egyes esetekben arra is remény van, hogy a hallgatók részt vehessenek eredményeik versenyszférában történő hasznosításának kidolgozásában is.
A BME Matematika Doktori Iskola keretei között létrejött tudományos műhelyek rendkívül inspiráló közeget biztosítanak hallgatóinknak. A Doktori Iskola hallgatói képzésük teljes ideje alatt kapcsolatban vannak témavezetőikkel, sőt e kapcsolat gyakran évekkel korábban, az alapképzés, vagy mesterképzés végén elkészített szakdolgozattal, TDK dolgozattal kezdődik. Intézményesült, hogy a tehetséges MSC hallgatók tanulmányait folyamatosan nyomon követi, segíti egy vezető oktató (tipikusan a volt szakdolgozati témavezető). Hallgatóink fejlődését folyamatosan figyelve mód van rá, hogy (doktori képzésük teljes ideje alatt) tehetségük kibontakoztatásához személyre szabott segítséget kapjanak.
A BME Matematika Doktori Iskola hallgatói részt vesznek a BME alapképzésében a mérnökhallgatók oktatásában. Tanulmányaik befejezésekor tehát több éves oktatói gyakorlatuk van, mely kiválóan hasznosítható felsőoktatási intézmények matematika jellegű kurzusainak szervezésében, illetve megvalósításában.
A BME Matematika Doktori Iskolán fokozatot szerzett kutatók eddigi eredményei alapján várható, hogy doktoranduszhallgatóink képességeikben megerősödve olyan versenyképes tudásra tesznek szert, melynek segítségével sikeresen helyt tudnak majd állni akár alapkutatóként, akár alkalmazott kutatóként. Bízunk benne, hogy a támogatás tovább növeli munkánk eredményességét.
PROJEKT ELŐREHALADÁSI JELENTÉSEK
Időtartam: 2011. december 31 - 2012. június 30
A kutatásban részt vesznek:
Oktatók: Dr. Gazdag-Tóth Boglárka, Dr. Hujter Mihály, Dr. Illés Tibor, Dr. Szántai Tamás, Dr. Egri Attila
Doktoranduszok: Barta Zsuzsanna, Lovics Gábor
MSc hallgató: Molnár-Szipai Richárd
A MÁV Trakció számára elvégeztük a rendelés alapú tehervonatok közlekedés szervezés múltbeli adatainak az elemzését. Sikerült a megrendelés alapú menetrendeket összeállítani és megoldani egy- illetve többtermékes hálózati folyam feladatok segítségével. A megoldás során XPRESS-MP lineáris programozási megoldóját használtuk (többtermékes folyam feladat) illetve az egytermékes folyamfeladatot saját, C programozási nyelven implementált primál szimplexes folyam algoritmussal (Goldfarb-Hao) oldottuk meg.
Kifejlesztettünk egy új MBU szimplex algoritmus alapú folyamfeladatot megoldó algoritmust is.
Időtartam: 2012. július 1 - 2013. január 15.
A kutatásban részt vesznek:
Oktatók: Dr. Illés Tibor, Dr. Szántai Tamás
Doktoranduszok: Barta Zsuzsanna, Egri Attila, Guzmics Sándor, Lovics Gábor, Molnár-Szipai Richárd
Egytermékes hálózati folyam feladatok polinomiális pivot algoritmusa: Az optimalizálás elmélet egyik sokat kutatott és széles körben alkalmazott klasszikus területének egy érdekes, még elméleti eredményekkel is kecsegtető területe a hálózati folyam feladatok pivot algoritmusai hatékonyságának, komplexitásának a vizsgálata. A szakirodalomból ismert Goldfarb és társszerzőinek a munkássága nyomán a primál szimplex algoritmus egy polinomiális változata nulla alsó korlátú maximális folyam feladatra. Az alkalmazások során előforduló, alsó korláttal rendelkező feladatokat egy nagyobb gráfba történő beágyazással szokták megoldani. Ennek elkerülésére sikerült az úgynevezett MBU fízibilitási algoritmust specializálni hálózati folyam feladat megengedett megoldásának keresésére. Ez egy duál típusú algoritmus, melyről az azonos struktúra miatt azonnal elindítható Goldfarbék algoritmusa, komplexitása pedig szintén erősen polinomiális. További kutatási cél az MBU-LP algoritmus hálózati folyamon való hatékonyságának vizsgálata, ilyen primál-duál típusú pivot algoritmus még nem ismert a szakirodalomban. Résztvevők: Illés Tibor, Molnár-Szipai Richárd.
Többtermékes hálózati folyam feladatok alkalmazása vasút-optimalizálási feladatokra. A MÁV-Trakció Zrt. teherszállítási részlegének, véletlenszerűen változó menetrendre kell mozdonyfordulókat, illetve személyzetszolgálatokat készíteni. A megfelelő személyzetszolgálatok tervezése előtt először el kell készíteni a mozdonyforduló terveket. A gondot az okozza, hogy ezeket a terveket legkésőbb 15 nappal a megvalósításuk előtt kell elkészíteni, bizonytalan menetrendi adatok alapján.
Optimalizálási szempontból először többtermékes cirkulációs feladat segítségével meghatározzuk a minimális szükséges mozdonyszámot az egyes típusokból. Annak érdekében, hogy a szükséges mozdonyszám alacsony legyen, már ennél a feladatnál be kell tervezni, un. gépmeneteket, amelyeknek az egyetlen célja az, hogy szükség esetén a mozdonyokat áthelyezzék egyik állomásról a másikra. Nyilván a költségeket növeli a gépmenetek száma, illetve az összes gépmenet-kilométer. A feladat duál degeneráltsága miatt ennek a modellnek sok alternatív optimális megoldása van. Miután meghatározzuk a minimálisan szükséges mozdonyok számát és figyelembe vesszük a lehetőségeket (sokszor néhánnyal több gépünk is akad), újabb többtermékes hálózati folyam feladatot tudunk definiálni, jelenleg egy minimál költséges többtermékes hálózati folyam feladatot, amellyel adott gép szám esetén, minimalizáljuk a futott gépmenet-kilométereket.
Az utolsó feladatunk az operatív fázisban, egy nappal az üzemeltetés előtt, amikor kialakul egy pontosabb menetrend, három napos gördülő tervet készítünk több, a vasúttársaság által fontosnak tartott szempont figyelembe vételével. Az egyik fontos szempont itt is a kevés gépmenet-kilométer, míg a másik (a szolgálatok előretervezése miatt) a mozdonyfordulók megtartása, vagy minimális módosítása. Az újratervezéses modell is egy minimális költségű többtermékes hálózati folyam feladat, így ugyanabba a feladatosztályba tartozik, mint a tervezési fázisban használt modellek, de a termékek ebben az esetben már a mozdonyfordulók. A minimális gépmenet-kilométer, illetve a minimális eltérés a tervezett mozdonyfordulóktól sokszor egymásnak ellentmondó célok, azaz ebben az esetben már másodszor találkozunk több-célfüggvényes többtermékes hálózati folyam feladattal. Résztvevők: Illés Tibor, Barta Zsuzsanna, Egri Attila.
Egészértékű programozási feladatok alkalmazása személyzet-hozzárendelési feladatokra.
A személyzet-hozzárendelési feladat az operációkutatás egyik legérdekesebb alkalmazási területe. A személyzet-hozzárendelési feladat olyan vállalkozásoknál lehet érdekes, amelyeknél a kiadások nagy százalékát teszik ki a bérköltségek, ahol a költségek mértéke és a munkavállalók időbeosztása között szoros kapcsolat áll fenn, illetve ahol nagyon speciális szaktudású embereket kell beosztani többféle feladat együttes, vagy egymással párhuzamos megoldására. Általában a cél a költségek minimalizálása. A személyzet-hozzárendelési feladat legegyszerűbb modelljei is bonyolultabbak, mint a jól ismert alapfeladatok (halmazfedés, halmazfelbontás stb.), így nem meglepő, hogy komplexitás szempontjából NP-teljes optimalizálási feladatokat kapunk.
A megoldásra többféle lehetőségünk van. Az egyik, a klasszikus MILP modellek megoldási technológiája, míg a másik a feladat struktúráját kihasználó hatékony, approximációs algoritmusok kifejlesztése. Mi a második utat követtük. Eredményeink leírása folyamatban van. Résztvevők: Illés Tibor, Barta Zsuzsanna.
Több-célfüggvényes optimalizálási feladatok Pareto-efficiens pontjainak a közelítése.
Több-célfüggvényes optimalizálási feladat megoldásának az értelmezése jelentősen eltér az egy célfüggvényes (klasszikus) optimalizálási feladatok optimális megoldásának az értelmezésétől. A több-célfüggvényes optimalizálási feladatok megoldásai a Pareto-efficiens pontok. Ezek jellemzői, hogy azzal a tulajdonsággal rendelkeznek, hogy egyik célfüggvény javítása sem fogadható el akkor, ha másik célfüggvény megoldása romlik. Általában, a több-célfüggvényes optimalizálási feladatok esetén több Pareto-efficiens pont létezik. A gond csak az, hogy különböző Pareto-efficiens pontoknak más és más lehet a gyakorlati jelentése. Nyilvánvaló, hogy több-célfüggvényes optimalizálási feladat esetén a megalapozott döntéshez nem egyetlen Pareto-efficiens pont ismerete a fontos, hanem a teljes Pareto-efficiens ponthalmaz ismerete. Tudomásunk szerint módszerünk az első olyan eljárás, amelyik segítségével lineáris, feltételes, több-célfüggvényes optimalizálási feladat esetén az egész Pareto-efficiens megoldáshalmaz approximálható, közelíthető, egy véges módszer segítségével. A közelítés finomsága természetesen több paramétertől függ, és a számítási igény még kisszámú változó esetén is igen nagy. Résztvevők: Illés Tibor, Lovics Gábor.
Készletszint szabályozási módszerek kidolgozása: Megvizsgáltuk annak a lehetőségét, hogy a Prékopa András és Szántai Tamás által a Balaton vízszintszabályozására kidolgozott modell hogyan alkalmazható a kéthetes akciók idején az áruházi polcokra kihelyezett áruk mennyiségének előírt szintek közti tartásának a szabályozására. Azt a következtetést kellett levonnunk, hogy az áruk akció alatti napi véletlen fogyásainak a modellezésére nem helyes a többdimenziós normális eloszlást alkalmazni, ezért kidolgoztunk egy újabb eljárást, amely a megfigyelési adatok együttes tapasztalati eloszlásának feltételes entrópia alapú vizsgálatán alapul. Résztvevők: Szántai Tamás, Egri Attila.
PERT modellek és alkalmazásaik: Áttekintettük az általánosabb precedencia előírásokat is megengedő PERT modelleket és az azok szimulációs elemzésével nyert eredményeket. Mind a szimulációs számítások, mind a továbbiak során szükségessé váló, nagyméretű tervütem hálókban történő legrövidebb út keresési algoritmusok igen számításigényesek lesznek. Ehhez a BME újonnan beüzemelt szuperszámítógépét kell igénybe vennünk, melyhez a projekt leírásunkat benyújtottuk a szuperszámítógép üzemeltetőnek. Résztvevők: Szántai Tamás, Guzmics Sándor.
A projektre deklarált publikációk
Megjelent publikációk: -
Beküldött és elfogadott publikációk: -
Beküldött publikációk:
Illés Tibor, Molnár-Szipai Richárd, On Strongly Polynomial Variants of the MBU-Simplex Algorithm for a Maximum Flow Problem with Nonzero Lower Bounds.. Operations Research Report 2012-01.
Illés Tibor, Lovics Gábor, Approximation of the Whole Pareto-Optimal Set for Vector Optimization Problems. 2012, pp. 21 (leadása folyamatban).
Konferenciaelőadások:
- Dynamic control of goods on hand in a bargain sale (Prékopa András, Szántai Tamás, Egri Attila) StoProg International Workshop on Stochastic Programming for Implementation and Advanced Applications, 2012 July 3-6, 2012, Neringa, LITHUANIA
- A Method to Approximate the Whole Pareto-optimal Set of Linearly Constrained Convex Multi Objective Optimization Problem (Lovics Gábor, Illés Tibor) VOCAL (Veszprém Optimization Conference: Advanced ALgorithms) , 2012 December 11-14, 2012, Veszprém
- Application of the newsvendor problem (Egri Attila, Illés Tibor, Lovics Gábor) VOCAL (Veszprém Optimization Conference: Advanced ALgorithms) , 2012 December 11-14, 2012, Veszprém
- Minimum Conditional Entropy Based Inventory Control and its Application (Szántai Tamás, Kovács Edith, Egri Attila) VOCAL (Veszprém Optimization Conference: Advanced ALgorithms) , 2012 December 11-14, 2012, Veszprém
- On Strongly Polynomial Variants of the MBU-Simplex Algorithm for a Maximum Flow Problem with Nonzero Lower Bounds (Molnár-Szipai Richárd, Illés Tibor) VOCAL (Veszprém Optimization Conference: Advanced ALgorithms) , 2012 December 11-14, 2012, Veszprém
- The Locomotive Assignment Problem in Freight Transportation (Barta Zsuzsanna, Egri Attila, Illés Tibor, Kelemen Zoltán, Molnár-Szipai Richárd) VOCAL (Veszprém Optimization Conference: Advanced ALgorithms) , 2012 December 11-14, 2012, Veszprém
- A method to approximate the whole Pareto-optimal set of the Markowitz model (Lovics Gábor) International Annual Conference of the German OR Society 2012
September 4 – 7, 2012
Időtartam: 2013. január 15. - 2013. június 15.
A kutatásban részt vesznek:
Oktatók: Dr. Illés Tibor, Dr. Szántai Tamás
Doktoranduszok: Barta Zsuzsanna, Egri Attila, Guzmics Sándor, Lovics Gábor, Molnár-Szipai Richárd
Egytermékes hálózati folyam feladatok polinomiális pivot algoritmusa:. Az optimalizálás elmélet egyik klasszikus, sokat kutatott és széles körben alkalmazott klasszikus területének egy érdekes, még elméleti eredményekkel is kecsegtető területe a hálózati folyam feladatok pivot algoritmusai hatékonyságának, komplexitásának a vizsgálata. A szakirodalomból ismert Goldfarb és társszerzőinek a munkássága nyomán a primál szimplex algoritmus egy polinomiális változata nulla alsó korlátú maximális folyam feladatra. Az alkalmazások során előforduló, alsó korláttal rendelkező feladatokat egy nagyobb gráfba történő beágyazással szokták megoldani. Ennek elkerülésére sikerült az úgynevezett MBU fízibilitási algoritmust specializálni hálózati folyam feladat megengedett megoldásának keresésére. Ez egy duál típusú algoritmus, melyről az azonos struktúra miatt azonnal elindítható Goldfarbék algoritmusa, komplexitása pedig szintén erősen polinomiális. További kutatási cél az MBU-LP algoritmus hálózati folyamon való hatékonyságának vizsgálata, ilyen primál-duál típusú pivot algoritmus még nem ismert a szakirodalomban. Résztvevők: Illés Tibor, Molnár-Szipai Richárd.
Többtermékes hálózati folyam feladatok alkalmazása vasút-optimalizálási feladatokra. A MÁV-Trakció Zrt. teherszállítási részlegének, véletlenszerűen változó menetrendre kell mozdonyfordulókat illetve személyzetszolgálatokat készíteni. A megfelelő személyzetszolgálatok tervezése előtt először el kell készíteni a mozdonyforduló terveket. A gondot az okozza, hogy ezeket a terveket – legkésőbb – 15 nappal a megvalósításuk előtt kell elkészíteni, bizonytalan menetrendi adatok alapján.
Optimalizálás szempontból először többtermékes cirkulációs feladat segítségével meghatározzuk a minimális szükséges mozdonyszámot az egyes típusokból. Már ennél a feladatnál, annak érdekében, hogy a szükséges mozdony szám alacsony legyen, be kell tervezni, un. gépmeneteket, amelyeknek az egyetlen célja az, hogy szükség esetén a mozdonyokat áthelyezzék egyik állomásról a másikra. Nyilván a költségeket növelik a gépmenetek száma, illetve az összes gépmenet-kilométer. A feladat duál degeneráltsága miatt, sok alternatív optimális megoldás van ennek a modellnek. Miután meghatározzuk a minimálisan szükséges mozdonyok számát és figyelembe vesszük a lehetőségeket (sokszor néhánnyal több gépünk is akad), újabb többtermékes hálózati folyam feladatot tudunk definiálni, jelenleg egy minimál költséges többtermékes hálózati folyam feladatot, amellyel adott gép szám esetén, minimalizáljuk a futott gépmenet-kilométereket.
Az utolsó feladatunk az operatív fázisban, egy nappal az üzemeltetés előtt, amikor kialakul egy pontosabb menetrend, három napos gördülő tervet készítünk több, a vasúttársaság által fontosnak tartott szempontok figyelembe vételével. Az egyik fontos szempont itt is a kevés gépmenet-kilométer, míg a másik (a szolgálatok előretervezése miatt) a mozdonyfordulók megtartása vagy minimális módosítása. Az újratervezéses modell is egy minimális költségű többtermékes hálózati folyam feladat, így ugyanabba a feladatosztályba tartozik, mint a tervezési fázisban használt modellek, de termékek ebben az esetben már a mozdonyfordulók. A minimális gépmenet-kilométer illetve minimális eltérés a tervezett mozdonyfordulóktól, sokszor, egymásnak ellentmondó célok, azaz ebben az esetben már másodszor találkozunk több-célfüggvényes többtermékes hálózati folyam feladattal. Résztvevők: Illés Tibor, Barta Zsuzsanna
Egészértékű programozási feladatok alkalmazása személyzet-hozzárendelési feladatokra.
A személyzet-hozzárendelési feladat az operációkutatás egyik legérdekesebb alkalmazási területe. A személyzet-hozzárendelési feladat, olyan vállalkozásoknál lehet érdekes, amelyeknél a kiadások nagy százalékát teszik ki a bérköltségek, ahol a költségek mértéke és a munkavállalók időbeosztása között szoros kapcsolat áll fenn illetve ahol nagyon speciális szaktudású embereket kell beosztani többféle feladat együttes vagy egymással párhuzamos megoldására. Általában a cél a költségek minimalizálása. A személyzet-hozzárendelési feladat, legegyszerűbb modelljei is, bonyolultabbak, mint a jól ismert alapfeladatok (halmazfedés, halmazfelbontás stb.), így nem meglepő, hogy komplexitás szempontjából NP-teljes optimalizálási feladatokat kapunk.
A megoldásra többféle lehetőségünk van. Az egyik, a klasszikus MILP modellek megoldási technológiája, míg a másik a feladat struktúráját kihasználó hatékony, approximációs algoritmusok kifejlesztése. Mi a második utat követtük. Eredményeink leírása folyamatban van. Résztvevők: Illés Tibor, Barta Zsuzsanna.
Több-célfüggvényes optimalizálási feladatok Pareto-efficiens pontjainak a közelítése.
Több-célfüggvényes optimalizálási feladat megoldásának az értelmezése jelentősen eltér az egy célfüggvényes (klasszikus) optimalizálási feladatok, optimális megoldásának az értelmezésétől. A több-célfüggvényes optimalizálási feladatok megoldásai a Pareto-efficiens pontok. Ezek jellemzői, hogy azzal a tulajdonsággal rendelkeznek, hogy egyik célfüggvény javítása sem fogadható el akkor, ha másik célfüggvény megoldása romlik. Általában, a több-célfüggvényes optimalizálási feladatok esetén több Pareto-efficiens pont létezik. A gond, csak az, hogy különböző Pareto-efficiens pontoknak más és más lehet a gyakorlati jelentése. Nyilvánvaló, hogy a megalapozott döntéshez, több-célfüggvényes optimalizálási feladat esetén, nem egy Pareto-efficiens pont ismerete a fontos, hanem a teljes Pareto-efficeins ponthalmaz ismerete. Módszerünk, tudomásunk szerint az első olyan eljárás, amelyik segítségével az egész Pareto-efficiens megoldáshalmaz approximálható, közelíthető, lineáris feltételes, több-célfüggvényes optimalizálási feladat esetén, egy véges módszer segítségével. A közelítés finomsága, természetesen, több paramétertől függ és a számítási igény, még kisszámú változó esetén is igen nagy. Résztvevők: Illés Tibor, Lovics Gábor.
Cserekereskedelmi modellek és megoldó algoritmusaik. A cserekereskedelmi modellek az általános egyensúlyi modellek speciális esetei. Ez a modell család azt vizsgálja, hogy komplex, sokszereplős, soktermékes gazdaságban kialakulhatnak-e olyan árak, melyek mellett egyfajta Nash-egyensúlyba kerül a gazdaság. A klasszikus eredmények a játékelmélet egzisztencia tételeit felhasználva és azokhoz hasonlóan csak az egyensúly létezését tudják bizonyítani, semmit nem mondanak arról, hogyan kereshetőek meg az egyensúlyok. Egy az Eisnbeg-Gale szerzőpáros által 1954-ben felírt feladat segítségével a lineáris hasznossági függvényes feladat megoldása visszavezethető egy konvex optimalizálási feladat megoldására. Ennek az eredménynek azóta számos továbbfejlesztése, és általánosítása készült el. A keletkezett feladatokat egy részét sok különböző algoritmussal megoldották polinom időben. Legtöbbjükről belátható, hogy az LP feladatokkal azonos időben oldhatóak meg, ha belsőpont módszereket használunk. Van olyan feladat is azonban, amely NP teljes problémára vezet. Tanulmányunk ezekkel a kérdésekkel kapcsolatos eredményeket mutatja be részletesen. Résztvevők: Illés Tibor, Lovics Gábor.
Cserekereskedelmi modellek és a geometria programozás. A cserekereskedelmi modellek az általános egyensúlyi modellek speciális esetei. Ez a modell család azt vizsgálja, hogy komplex, sokszereplős, soktermékes gazdaságban kialakulhatnak-e olyan árak, melyek mellett egyfajta Nash-egyensúlyba kerül a gazdaság. Egy az Eisnbeg-Gale szerzőpáros által 1954-ben felírt feladat segítségével a lineáris hasznossági függvényes feladat megoldása visszavezethető egy konvex optimalizálási feladat megoldására. Ezt az eredményt Kalszfky Emil újrabizonyította, és ezzel a bizonyítással feltárta a kapcsolatot a cserekereskedelmi modellek, és a geometriai programozás között. Eiseberg egy 1961-es eredménye alapján a módszer általásítható tetszőleges homogén konkáv hasznossági függvényünkre. Tanulmányunkban megmutatjuk, hogy a Kalszfky féle bizonyítási módszerrel, ez az általánosabb eset is újrabizonyítható, ha hasznossági függvényről még deriválhatóságot is megköveteljük. Résztvevők: Illés Tibor, Lovics Gábor.
Az általánosított almapakolási feladat Az eredeti feladatban egy ládába kell almákat pakolni oly módon, hogy meg van adva az egy sorban illetve egy oszlopban elhelyezendő almamennyiség. A feladatra megoldást olvashatunk Clausen és Krarup: Arranging apples in an array című cikkében. Bizonyos személyzet hozzárendelési feladatok az almapakoláshoz hasonló problémára vezetnek, ám az új korlátozó feltételek (tipikusan tiltott minták és kötelező minták) miatt a fent említett cikkbeli algoritmus nem használható. A hozzárendelés első fázisára, a szabadnapkiosztásra kifejlesztettünk egy randomizált algoritmust, amely az új korlátozó feltételeket szem előtt tartva sorra osztja ki a szabadnapokat. Az új algoritmus kulcsa egy súlyfüggvény, amely minden nap-dolgozó párhoz meghatározza azt, hogy annak mekkora "valószínűséggel" kell szabadnapnak lennie. Amelyik napra a legnagyobb valószínűség esik, azt realizáljuk, majd az eljárást iteráljuk. Amennyiben egy ilyen választásra több egyforma (vagy közel egyforma) súly esik, akkor véletlenszerűen választunk közülük, így kapjuk a randomizált algoritmusunkat. A gyakorlati tapasztalatok alapján az algoritmus kevés futás alatt megtalál egy fízibilis megoldást, vagy infízibilis esetben ad egy maximális kitöltést. További kérdés ezen tulajdonságok bizonyítása. Résztvevők: Egri Attila
Készletszint szabályozási módszerek kidolgozása: Megvizsgáltuk annak a lehetőségét, hogy a Prékopa András és Szántai Tamás által a Balaton vízszintszabályozására kidolgozott modell hogyan alkalmazható a kéthetes akciók idején az áruházi polcokra kihelyezett áruk mennyiségének előírt szintek közti tartásának a szabályozására. Azt a következtetést kellett levonnunk, hogy az áruk akció alatti napi véletlen fogyásainak a modellezésére nem helyes a többdimenziós normális eloszlást alkalmazni, ezért kidolgoztunk egy újabb eljárást, amely a megfigyelési adatok együttes tapasztalati eloszlásának feltételes entrópia alapú vizsgálatán alapul. Résztvevők: Szántai Tamás, Egri Attila.
PERT modellek és alkalmazásaik: Áttekintettük az általánosabb precedencia előírásokat is megengedő PERT modelleket és az azok szimulációs elemzésével nyert eredményeket. Mind a szimulációs számítások, mind a továbbiak során szükségessé váló, nagyméretű tervütem hálókban történő legrövidebb út keresési algoritmusok igen számításigényesek lesznek. Ehhez a BME újonnan beüzemelt szuperszámítógépét kell igénybe vennünk, melyhez a projekt leírásunkat benyújtottuk a szuperszámítógép üzemeltetőnek. Erre a kérésre választ nem kaptunk. Asztali számítógépes futási eredményeinkről a Magyar Operációkutatási Konferencián június 12-én számolunk be. Résztvevők: Szántai Tamás, Guzmics Sándor és külső szakértőként Hajdú Miklós.
A projektre deklarált publikációk
Megjelent publikációk:
Illés, T., Molnár-Szipai R., On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds.
Optimization, DOI: 10.1080/02331934.2013.800515. http://www.tandfonline.com/doi/full/10.1080/02331934.2013.800515
Konferenciaelőadások:
Barta, Zs., The locomotive assignment problem in freight transportation, PhD Conference organized by the Doctoral School of Mathematics and Computer Science Budapest University of Technology and Economics, in the framework of TÁMOP-4.2.2.B-10/1--2010-0009 May 8-10, 2013. p. 71.
Egri, A., Bilinear programming models, PhD Conference organized by the Doctoral School of Mathematics and Computer Science Budapest University of Technology and Economics, in the framework of TÁMOP-4.2.2.B-10/1--2010-0009 May 8-10, 2013. p. 69.
Guzmics, S., The effect of the different activity duration time distributions on the distribution of the project completion time in PERT modeling, PhD Conference organized by the Doctoral School of Mathematics and Computer Science Budapest University of Technology and Economics, in the framework of TÁMOP-4.2.2.B-10/1--2010-0009 May 8-10, 2013. p. 75.
Lovics, G., Finding Equilibrium Solution of Exchange Models With the Results of the Geometric Programming, PhD Conference organized by the Doctoral School of Mathematics and Computer Science Budapest University of Technology and Economics, in the framework of TÁMOP-4.2.2.B-10/1--2010-0009 May 8-10, 2013. p. 70.
Molnár-Szipai, R., On strongly polynomial variants of the MBU simplex algorithm for a maximum flow problem with nonzero lower bounds, PhD Conference organized by the Doctoral School of Mathematics and Computer Science Budapest University of Technology and Economics, in the framework of TÁMOP-4.2.2.B-10/1--2010-0009 May 8-10, 2013. pp. 72-74.
Barta Zsuzsanna és Illés Tibor, Mozdony-hozzárendelési problémák, XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-13. p. 71,
Egri Attila, Az általánosított almapakolási feladat, XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-13.
Guzmics Sándor, Hajdú Miklós és Szántai Tamás, A különböző tevékenység végrehajtási idő eloszlások hatása a projekt végrehajtási idő eloszlására, XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-13.
Lovics Gábor, Eisenberg-Nagy Marianna és Illés Tibor, Általános egyensúlyi modellek megoldása geometriai programozás eszközeivel, XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-13.
Molnár-Szipai Richárd és Illés Tibor, Az alsó korlátos hálózati folyam feladat megoldása MBU szimplex algoritmussal, XXX. Magyar Operációkutatási Konferencia, Balatonőszöd, 2013. június 10-13.