´ Abele-Nagy Krist´ of Budapesti Corvinus Egyetem, Oper´ aci´ okutat´ as ´es Aktu´ ariustudom´ anyok Tansz´ek; MTA SZTAKI, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport
Fu anos ¨ lo ¨p J´ MTA SZTAKI, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport
Pozit´ıv m´ atrixok domin´ ans saj´ atvektor´ anak sz´ am´ıt´ asa ciklikus koordin´ at´ ak m´ odszer´ evel Pozit´ıv m´atrixok domin´ ans saj´ at´ert´ek´enek ´es saj´atvektor´anak kisz´am´ıt´as´ara adunk egy u ´j, egyszer˝ u ´es gyorsan sz´amolhat´ o elj´ ar´ ast. Az elj´ ar´ as a Perron–Frobenius t´etelen ´es a Collatz–Wielandt formul´an alapul. A Perron–Frobenius t´etel garant´ alja a domin´ans saj´at´ert´ek l´etez´es´et ´es egy´ertelm˝ us´eg´et, m´ıg a Collatz–Wielandt formula egy minimax ´es egy maximin tulajdons´agot is megmutat r´ola. Az el˝obbi tulajdons´agokat kihaszn´ alva a ciklikus koordin´ant´ak m´odszer´et alkalmazva egy iterat´ıv elj´ar´assal sz´amoljuk a domin´ ans saj´at´ert´eket ´es saj´ atvektort. A m´odszer egy tov´ abbi kiterjeszt´ese a t¨obbszempont´ u d¨ont´eselm´eletben el˝ofordul´o nem teljesen kit¨olt¨ott p´aros o as m´atrixok esete. A p´aros o¨sszehasonl´ıt´as m´atrixok pozit´ıv ´es reciprok¨sszehasonl´ıt´ szimmetrikus m´atrixok. A nem teljesen kit¨ olt¨ott p´aros o¨sszahsonl´ıt´as m´atrixok olyan p´aros o¨sszehasonl´ıt´as m´atrixok, melyekb˝ ol hi´ anyoznak elemek ´es a reciprokaik. Ilyen m´atrixok gyakran el˝ofordulnak, ha valami´ert nem ´all rendelkez´esre a teljes m´ atrix kit¨olt´es´ehez sz¨ uks´eges o¨sszes inform´aci´o. Ekkor a s´ ulyvektor a domin´ ans saj´atvektorhoz tartoz´ o kit¨olt´esb˝ol sz´amolt saj´atvektor lesz, teh´at egy saj´at´ert´ek minimaliz´al´asi probl´em´ at kell megoldani. Erre a probl´em´ara sz¨ ulettek m´ar megold´asok, de ezek az elj´ar´asok nagy m´eret˝ u probl´em´ akra lassan futnak. A kor´abbiakhoz k´epest egy u ´j, egyszer˝ ubben sz´amolhat´o elj´ar´ast adunk, mely v´ arakoz´ asaink szerint nagy m´eret˝ u probl´em´akra is gyorsan eredm´enyt ad.
´ Agoston Kolos Csaba Budapesti Corvinus Egyetem
Fels˝ ooktat´ asi felv´ eteli feladatok modellez´ ese vegyes eg´ esz´ ert´ ek˝ u programoz´ asi feladatokkal Gale ´es Shapley ´altal megadott k´eseltetett elfogad´asi algoritmus seg´ıts´eg´evel elv´egezhet˝o a jelentkez˝ok egyetemekhez t´ars´ıt´ asa. A magyar felv´eteli elj´ar´asok tartalmaznak olyan elemeket, amelyek megnehez´ıtik, vagy lehetetlenn´e teszik a Gale–Shapley algoritmus haszn´ alat´at. Ilyen specialit´asok a pontsz´amegyez´esek kezel´ese, a k¨ oz¨ os kv´ ot´ ak ´es az als´ o kv´ ot´ak haszn´alata. A magyar felv´eteli elj´ar´asok sor´an k¨ ul¨onf´ele heurisztik´akat haszn´ alnak, de lehets´eges lenne ezeket a specialit´asokat vegyes eg´esz´ert´ek˝ u programoz´asi feladatokkal kezelni. Bemutatjuk, hogy vegyes eg´esz´ert´ek˝ u LP feladatokkal mekkora m´eret˝ u feladatok oldhat´oak meg, majd javaslunk p´ ar m´ odszert, amellyel gyorsabban megkaphat´oak az egzakt optimumok.
1
Balogh J´ anos Szegedi Tudom´ anyegyetem, Juh´ asz Gyula Pedag´ ogusk´epz˝ o Kar, Informatika Alkalmaz´ asai Tansz´ek
B´ ek´ esi J´ ozsef Szegedi Tudom´ anyegyetem, Juh´ asz Gyula Pedag´ ogusk´epz˝ o Kar, Informatika Alkalmaz´ asai Tansz´ek
D´ osa Gy¨ orgy Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
Leah Epstein University of Haifa, Department of Mathematics
Asaf Levin Faculty of Industrial Engineering and Management, The Technion, Haifa
Az online elemsz´ amkorl´ atos l´ adapakol´ asi feladatr´ ol Az elemsz´amkorl´atos l´adapakol´asi feladat (bin packing with cardinality constraints, BPCC) a klasszikus l´adapakol´asi feladat azon term´eszetes vari´ ansa, amikor egy l´ad´aba maximum k darab elem pakolhat´o. (k el˝ore r¨ogz´ıtett konstans.) A BPCC online v´ altozat´ aban a k = 2 esetet kiv´eve el´eg nagy volt a h´ezag (gap) a legjobb ismert als´o ´es fels˝o (aszimptotikus, legrosszabb eset) korl´atok k¨oz¨ott, 7-n´el nagyobb k-kra 0,459. Eg´eszen mostan´ aig: https://arxiv.org/abs/1608.06415. A szerz˝oknek siker¨ ult ezt a h´ezagot az als´o korl´atokat jav´ıtva nagy k-kra lecs¨okkenteni, szinte elt¨ untetni (legfeljebb 2/(k + 1) marad´ek h´ezagot hagyva). Ahhoz, hogy ezt nyerj¨ uk, p´ ar ´erdekes ¨otletet kellett egym´as ut´an alkalmazni, ezekr˝ol lenne sz´o az el˝oad´asban. Hivatkoz´ asok [1] L. Babel, B. Chen, H. Kellerer, and V. Kotov, Algorithms for on-line bin-packing problems with cardinality constraints, Discrete Applied Mathematics, 143(1–3):238–251, 2004. [2] J. B´ek´esi, Gy. D´ osa, and L. Epstein, Bounds for online bin packing with cardinality constraints, Information and Computation, 249:190–204, 2016. [3] L. Epstein, Online bin packing with cardinality constraints, SIAM Journal on Discrete Mathematics, 20(4): 1015–1030, 2006. [4] H. Fujiwara and K. Kobayashi, Improved lower bounds for the online bin packing problem with cardinality constraints, Journal of Combinatorial Optimization, 29(1):67–87, 2015.
2
B´ anhelyi Bal´ azs Szegedi Tudom´ anyegyetem Informatikai Int´ezete
Csendes Tibor Szegedi Tudom´ anyegyetem Informatikai Int´ezete
L´ evai Bal´ azs Szegedi Tudom´ anyegyetem Informatikai Int´ezete
Zombori D´ aniel Szegedi Tudom´ anyegyetem Informatikai Int´ezete
P´ al L´ aszl´ o Sapientia Erd´elyi Magyar Egyetem, Cs´ıkszereda
GlobalJ bemutat´ asa A tansz´ek ´altal fejlesztett MATLAB-os optimaliz´al´ot ´athelyezt¨ uk egy jobban haszn´alhat´o k¨ornyezetre. A v´alaszt´asunk az ipari k¨ ornyezet miatt a JAVA-ra esett. Az el˝oad´asunkban ezzel foglalkozunk. A rendszer el˝ odje a GLOBAL elj´ ar´ as. Ezt a 80-as ´evekben dolgozt´ak ki [1], de a sz´am´ıt´astechnika rohamos fejl˝od´es´evel egyre elavultabb´ a v´ alt a futtat´o k¨ornyezet. 2010 k¨or¨ ul a mai technol´ogiai fejletts´eghez lett igaz´ıtva MATLAB k¨ ornyezetben [2], ezzel jav´ıtva a haszn´alat k´enyelm´et ´es a megb´ızhat´os´agot. Ennek mint´aj´ara k´esz¨ ult a JAVA implement´aci´o is. A rendszer modul´ aris fel´ep´ıt´es˝ u. Egy futtat´as el˝ott a megfelel˝o modulokat kiv´alasztva ´es ¨osszekapcsolva meg kell alkotnunk a rendszer egy vari´ans´at. A vari´ansokban meghat´arozott a r´eszegys´egek architekt´ ur´aja, minden blokkba annak egy implement´aci´oj´at kell helyezni. Ez a gyakorlatban Builder oszt´alyokon kereszt¨ ul val´ osul meg, amelyek garant´alj´ak, hogy csak megfelel˝oen param´eterezett rendszer legyen ´ep´ıthet˝o. Az el˝oad´as els˝ o fel´eben ezen elj´ ar´ asunk hat´asait mutatn´ank be. Az el˝oad´asunkban a GlobalJ sokmagos k¨ornyezetben futtathat´ o v´altozat´ at is bemutatjuk. Jelenleg a folyamatos n¨oveked´est a processzormagok sz´am´anak n¨ ovel´es´evel ´erj¨ uk el, ami kisebb szupersz´am´ıt´og´epekben is t¨obb sz´az magot jelent. Ahhoz, hogy optimaliz´ al´ asi feladataink v´egrehajt´ as´ ahoz ezeket az er˝oforr´asokat k¨onnyen felhaszn´alhassuk, az algoritmusokat t¨ obb sz´ alon futtathat´ ov´ a kell tenn¨ unk. Hivatkoz´ asok [1] Tibor Csendes: Nonlinear parameter estimation by global optimization – efficiency and reliability, Acta Cybernetica, 8 (1988), 361–370. [2] Tibor Csendes, L´ aszl´ o P´ al, J. Oscar H. Send´ın, and Julio R. Banga: The GLOBAL Optimization Method Revisited, Optimization Letters, 2 (2008), 445–454.
Bednay Dezs˝ o Budapesti Corvinus Egyetem Matematika Tansz´ek
Stabil halmazok keszty˝ uj´ at´ ekokban Aukci´okon el´eg gyakori jelens´eg, hogy a vev˝ ok o¨sszej´atszanak ´es a saj´at val´os ´ert´ekel´es¨ ukn´el csak kisebbet mutatnak, amivel olcs´ obban is megszerezhetik a term´eket. Az ´ıgy szerzett hasznot pedig valahogy sz´etosztj´ak egym´ as k¨ ozt. Azt, hogy hogyan osztj´ak sz´et a vev˝ok a hasznot, modellezhetj¨ uk NeumannMorgenstern-f´ele stabil halmazokkal. Ha van egy ilyen ¨osszej´atsz´assal kapott eloszt´asunk (ami nem magbeli), az ¨osszej´ atsz´ asb´ ol sz´armaz´ o profitnak ezen sz´etoszt´as´at b´ar fel tudja r´ ugni valamely vev˝o, de a t¨obbi vev˝ onek erre mindig van egy v´ alaszl´ep´ese (m´eg egy kicsit r´alicit´alnak), ´es ´ıgy visszaker¨ ulnek az eredeti halmazba. A fent eml´ıtett egy elad´os aukci´os eset m´ar Neumann ´es Morgenstern (1953) klasszikus k¨onyv´eben is szerepel p´eldak´ent a stabil halmazok alkalmaz´as´ara. 3
Ezt a megold´ askoncepci´ ot vizsg´ aljuk meg t¨obb elad´o eset´en a legegyszer˝ ubb esetben (a keszty˝ uj´at´ekok oszt´aly´an), amikor minden vev˝ ok nem tesznek k¨ ul¨onbs´eget az elad´ok term´ekei k¨ozt. Megmutatjuk, hogy ebben a j´ at´ekoszt´ alyban minden stabil halmaz egy monoton g¨orb´et alkot, tov´abb´a sz¨ uks´eges ´es el´egs´eges felt´eteleket adunk egy ilyen g¨ orbe stabilit´as´ara.
Bednay Dezs˝ o Budapesti Corvinus Egyetem
Moskalenko Anna Budapesti Corvinus Egyetem
Tasn´ adi Attila Budapesti Corvinus Egyetem
A t¨ obbs´ egi szavaz´ as, mint a diktat´ orikus szavaz´ asi elj´ ar´ asok k¨ oz¨ otti kompromisszum megold´ as Az irodalomban ismert megk¨ ozel´ıt´es szerint a nevezetes szavaz´asi elj´ar´asok megkaphat´ok bizonyos j´o tulajdons´agokat teljes´ıt˝ o profilokhoz (egyhang´ us´ag, Condorcet-konziszencia, Pareto-hat´ekonys´ag) val´o t´avols´agok minimaliz´ al´ asa r´ev´en. Ett˝ ol elt´er˝ o, u ´j megk¨ozel´ıt´est alkalmazva, a rossz diktat´orikus szavaz´asi elj´ar´ast´ol val´o t´avols´ agok optimaliz´ al´ asa r´ev´en megkapjuk a t¨obbs´egi szavaz´ast ´es az inverz-t¨obbs´egi szavaz´ast. A legelemibb t´ avols´ agot v´eve, mely szerint csak azt sz´amoljuk, hogy h´any profilon ad k´et szavaz´asi elj´ar´ as elt´er˝ o eredm´enyt, az ¨ ossze diktat´orikus elj´ar´ast´ol val´o ¨osszt´avols´agot minimaliz´alva, a t¨obbs´egi szavaz´ast kapjuk. A legk¨ ozelebbi dikt´atorhoz val´o t´avols´ag maximaliz´al´as´aval pedig az inverzt¨obbs´egi szavaz´ as ad´odik.
B´ ek´ esi J´ ozsef SZTE Informatika Alkalmaz´ asai Tansz´ek
Galambos G´ abor SZTE Informatika Alkalmaz´ asai Tansz´ek
FFD alap´ u algoritmus elemz´ ese egy p´ aros munka u esi probl´ em´ ara ¨ temez´ A p´aros munk´ ak u ovetkez˝o m´odon defini´alt: adott valah´any munka, mindegyik ¨temez´esi feladata a k¨ k´et r´eszmunk´ab´ ol tev˝ odik ¨ ossze. A k´et r´eszmunk´at a megadott sorrendben kell elv´egezni, ´es van egy pontosan betartand´ o k´esleltet´esi id˝ o is a k´et r´eszmunka v´egrehajt´asa k¨oz¨ott. A k´esleltet´esi id˝o alatt a g´ep m´as munk´aval foglalkozhat. A c´el az ¨ osszes munka u ´gy, hogy k´et k¨ ul¨onb¨oz˝o ¨temez´ese egyetlen g´epre u munk´ahoz tartoz´ o r´eszmunka nem fedheti ´at egym´ast, ´es a legutols´o munka befejez´esi ideje a lehet˝o legkisebb legyen. Az irodalomban a probl´em´ anak t¨ obb v´ altozat´at vizsg´alt´ak. Ageev ´es Baburin az egys´egnyi v´egrehajt´asi id˝okkel rendelkez˝ o esetre defini´ altak egy k¨ozel´ıt˝o algoritmust. Enn´el a v´altozatn´al mink´et r´eszmunka v´egrehajt´asi ideje 1. Az algoritmus legrosszabb-eset h´anyadosa 7/4, ami ´eles. Az el˝oad´asban egy u ´j algoritmust defini´ alunk, ami az FFD (First Fit Decreasing) szab´alyon alapszik ´es legrosszabb eset h´ anyadosa 30/19 ´es 7/4 k¨oz¨ott van. Hivatkoz´ as [1] Ageev, A. A. and Baburin A. E.: Approximation algorithms for UET scheduling problems with exact delays, Operations Research Letters, 35(4) (2007), 533–540.
4
Berlinger Edina Budapesti Corvinus Egyetem, Befektet´esek ´es V´ allalati P´enz¨ ugy Tansz´ek
Dar´ oczi Gergely Budapesti Corvinus Egyetem, Befektet´esek ´es V´ allalati P´enz¨ ugy Tansz´ek
Vad´ asz Tam´ as Budapesti Corvinus Egyetem, Befektet´esek ´es V´ allalati P´enz¨ ugy Tansz´ek
A magyar fedezetlen bankk¨ ozi hitelpiac mag-perif´ eria szerkezete A kutat´as sor´an mag-perif´eria modellt illeszt¨ unk a magyar fedezetlen bankk¨ozi hitelpiac 2003 ´es 2012 k¨oz¨otti h´al´ozat´ ara, ami 55 bank 92 0619 tranzakci´oj´at foglalja mag´aban. Meghat´arozzuk az egyes bankok mags´agi mutat´ oinak id˝ obeli alakul´ as´ at, ´es megvizsg´aljuk, hogy mi a kapcsolat ezen mutat´ok, illetve a bank h´al´ozatban elfoglalt szerep´et jellemz˝o egy´eb mutat´ok ´es a banknak ny´ ujtott hitelek kond´ıci´oi (hitel¨osszeg, kamatl´ ab, futamid˝o) k¨ oz¨ ott. Megvizsg´aljuk a glob´alis p´enz¨ ugyi v´als´agnak a h´al´ozat topol´ogi´ aj´ara gyakorolt hat´ as´ at is. A mag-perif´eria model alkalmaz´ asa sor´ an abb´ol indulunk ki, hogy a tapasztalatok szerint a bankk¨ozi piacok h´al´ozata ritka, alacsony klaszterezetts´eg˝ u, ´es jellemz˝o r´ajuk az u ´n. disszortat´ıv kevered´es”, ” ami azt jelenti, hogy a kisbankok sz´ıvesen kereskednek a nagybankokkal, de nem sz´ıvesen kereskednek egym´assal. Ebb˝ ol k¨ ovetkezik, hogy a legt¨ obb bank nem ad hitelt a m´asiknak k¨ozvetlen¨ ul, hanem csak a magbeli bankokon kereszt¨ ul, melyeket ily m´odon a k¨ozvet´ıt˝ok k¨ozvet´ıt˝oj´enek tekinthet¨ unk. Ez a jelens´eg teh´at hierarchikus strukt´ ur´ at hoz l´etre, ahol a magbeli bankok tekinthet˝ok a rendszerkock´azat szempontj´ab´ol fontos p´enz¨ ugyi int´ezm´enyeknek, (Fricke and Lux, 2015). M´odszertani szempontb´ ol Borgatti-Everett (2000)-re t´amaszkodunk. A mag-perif´eria modellez´es l´enyege, hogy a h´al´ ozat csom´ opontjait k´et diszjunkt halmazra osztjuk: a magra, ahol az egyes csom´opontok s˝ ur˝ un kapcsol´odnak egym´ ashoz ´es a perif´eri´ ara, ahol az egyes elemek alig ´allnak o¨sszek¨ottet´esben egym´assal. Borgatti ´es Everett t´ arsadalmi h´al´ ozatokra alkalmazt´ak ezt a m´odszert. Craig ´es von Peter (2010) a n´emet bankk¨ ozi piacot, Lelyveld ´es Veld (2012) a holland bankk¨ozi piacot, m´ıg Fricke ´es Lux (2015) az olasz piacot (e-Mid platform) vizsg´alt´ak ebb˝ol a szempontb´ol, ut´obbiak egy´ uttal a m´odszert is tov´abbfejlesztett´ek. A diszkr´et mag-perif´eria modelleket a szakirodalomban genetikus algoritmusok seg´ıts´eg´evel (Fricke ´es Lux, 2012), szekvenci´ alis keres˝o algoritmusokkal (Craig ´es von Peter, 2010), vagy alternat´ıv m´odszerekkel (Lip 2013) kalibr´ alj´ak. Mi folytonos ´es aszimmetrikus hitelfelv´eteli ´es hitelny´ ujt´asi mags´agi mutat´okat sz´amolunk a magyar bankokra. Az R szoftvert haszn´ aljuk, ami hat´ekony eszk¨oz a h´al´ozatok elemz´es´eben. Eredm´enyeink seg´ıtenek a magyar bankk¨ ozi piacon tapasztalhat´o, v´als´ag el˝otti ´es v´als´ag ut´ani folyamatok meg´ert´es´eben, ´es egyben lehet˝ ov´e teszik a magyar, a n´emet, a holland ´es az olasz piacok ¨osszehasonl´ıt´as´at. Hivatkoz´ asok [1] Borgatti, S. P. – Everett, M. G. (2000): Models of Core/Periphery Structures, Social Networks, 21(4): 375– 395. [2] Craig, B. – von Peter, G. (2010): Interbank Tiering and Money Center Banks. BIS Working Paper, 322. [3] Fricke, T. – Lux, D. (2015): Core-Periphery Structure in the Overnight Money Market: Evidence from the e-MID Trading Platform, Computational Economics, 45(3): 359–395. [4] Lelyveld, I. and Veld, D. (2012): Finding the Core: Network Structure in Interbank Markets, DNB Working Paper No. 348 / July 2012. [5] Lip, S. Z. W. (2013): A Fast Algorithm for the Discrete Core/Periphery Bipartitioning Problem, http://arxiv.org/pdf/1102.5511.pdf, Accessed: 16.06.2016.
5
Bessenyei Istv´ an P´ecsi Tudom´ anyegyetem K¨ ozgazdas´ agtudom´ anyi Kar
Hartung Katalin P´ecsi Tudom´ anyegyetem K¨ ozgazdas´ agtudom´ anyi Kar
A k´ ek gazdas´ ag elvei szerint m˝ uko o v´ allalatok optim´ alis ¨d˝ er˝ oforr´ as-allaok´ aci´ oja A K´ek gazdas´ag elvei szerint m˝ uk¨ od˝ o v´ allalat optim´alis er˝oforr´asallok´aci´oj´anak probl´em´aj´at az ikertermel´es ´es technol´ ogiai v´ alaszt´ek lehet˝ os´eg´et is tartalmaz´o line´aris tev´ekenys´egelemz´es modellj´enek keretei k¨oz¨ott az al´abbi m´ odon defini´ aljuk: a) Adott vev˝ oi ig´enyt kiel´eg´ıt˝ o yv term´ek-, illetve szolg´altat´ask´eszletet kell el˝o´all´ıtani. b) Emellett a v´ allalat k´esz ´es f´elk´esz term´ekeket, mell´ekterm´ekeket, hullad´ek- ´es szennyez˝oanyagokat adhat el, illetve v´as´ arolhat. c) Szennyez˝oanyagot a k¨ ornyezetbe nem bocs´athat ki: yp = 0. d) Ha a rendelkez´es´ere ´all´ o els˝ odleges er˝ oforr´asok (pl: energia, munka, t˝okejavak) mennyis´ege s el´egtelen, tov´abbi els˝ odleges er˝ oforr´ asokat szerezhet be: s. e) A p´otl´olagosan beszerzett er˝ oforr´ asok k¨olts´eg´et minimaliz´alni kell: qs → min. Meghat´arozzuk, a fenti elvek betart´ as´ anak k¨olts´eg´et, tov´abb´a az egyes szennyez˝o-anyagok kibocs´at´as´ara kivetend˝ o, visszatart´ o er˝ ovel b´ır´ o k¨ornyezetv´edelmi b´ırs´ag als´o k¨ usz¨ob´ert´ek´et. Megmutatjuk tov´abb´a, hogy: 1. A szennyez˝ oanyagok hat´ ark¨ olts´ege ´es ´ara negat´ıv is lehet, de ez esetben is igaz, hogy a b) pontban eml´ıtett tranzakci´ ok sor´ an ´erv´enyes ´arak ar´anya a hat´ark¨olts´egek ar´any´aval, azaz a transzform´aci´os hat´arr´at´aval egyezik meg. ´ enyes a kimer´ıt´esi elv, mely szerint az yv term´ek-, illetve szolg´altat´ask´eszlet hat´ark¨olts´egen sz´a2. Erv´ m´ıtott ´ert´eke megegyezik a piaci ´aron ´ert´ekelt els˝odleges er˝oforr´ask¨olts´egnek, a b) pontban eml´ıtett tranzakci´ok vesztes´eg´enek, tov´ abb´ a a kibocs´atott szennyez˝oanyagok hat´ark¨olts´egen sz´am´ıtott ´ert´ek´enek ¨osszeg´evel. Mivel a z´er´ o k¨ ornyezetterhel´es c) pontban eml´ıtett k¨ovetelm´eny´enek betart´asa nem minden esetben finansz´ırozhat´ o, sz¨ uks´eges a kv´ azi k´ek gazdas´ag elvei szerint m˝ uk¨od˝o v´allalat bevezet´ese. Ehhez az a)–e) probl´em´ at u ´gy m´odos´ıtjuk, hogy a v´allalat c´elja most a szennyez˝oanyag kibocs´at´as´ab´ol ad´od´o k¨ornyezetterhel´es minimaliz´ al´ asa: ryp → min. Az ´ıgy kapott u ´jabb line´ aris programoz´asi feladat megold´asa felhaszn´alhat´o az y ≥ 0 kibocs´at´asi korl´atok, illetve az ezek betart´ as´ ahoz sz¨ uks´eges k¨ornyezetv´edelmi t´amogat´as meghat´aroz´asa, valamint a k¨ornyezetterhel´es ´ert´ekel´ese sor´ an. Megmutatjuk, hogy tov´ abbra is teljes¨ ulnek a fenti 1. ´es 2. tulajdons´agok, mik¨ozben yv ´ert´ek´en most az el˝o´all´ıt´asa sor´an fell´ep˝ o k¨ ornyezetterhel´est ´ertj¨ uk. Megmutatjuk azt is, hogy amennyiben a kv´azi k´ek gazdas´ag elvei szerint m˝ uk¨od˝o v´allalatot egy a k¨ornyezetterhel´es ¨ okol´ ogiai ´es a hullad´ekanyag-piac gazdas´agi realit´asait jobban figyelembe vev˝o, nemline´aris probl´ema r´ev´en defini´ aljuk, a fenti tulajdons´agok k¨oz¨ ul az 1. tov´abbra is ´erv´enyben marad, de az elad´asi ´arakat azok el˝ ojel´et˝ ol f¨ uggetlen¨ ul a kereslet ´arelaszticit´as´aval kell korrig´alni, mint azt piaci er˝of¨ol´eny eset´en a sztenderd mikro¨ okon´ omia is teszi. F˝o k¨ovetkeztet´es¨ unk az, hogy a sztenderd mikro¨okon´omia termel´eselm´elet´enek legfontosabb ¨osszef¨ ugg´esei ´atvihet˝ ok egy olyan ´ert´ekelm´eletre fel´ep´ıtett, alternat´ıv mikro¨okon´omia keretei k¨oz´e, ahol egy term´ek-, illetve szolg´ altat´ ask´eszletet a termel´esi k¨olts´egen, vagy hat´arhasznokon alapul´o, mainstream ´ert´ekel´es helyett az el˝ o´ all´ıt´ asa sor´ an el˝ oid´ezett k¨ornyezetterhel´essel ´ert´ekel¨ unk.
6
Borgulya Istv´ an PTE K¨ ozgazdas´ agtudom´ anyi Kar
Egy evol´ uci´ os val´ osz´ın˝ us´ egi-modell a 2D h´ atizs´ ak probl´ em´ ara guillotine felt´ etellel Az evol´ uci´os val´ osz´ın˝ us´egi modellek (Estimation of distribution algorithms, EDAs) a popul´aci´o szelekt´alt egyedeit felhaszn´ alva gener´ alnak ´es/ vagy aktualiz´alnak egy val´osz´ın˝ us´egi modellt ´es az ut´odokat a val´osz´ın˝ us´egi modell alapj´an gener´ alj´ ak. Mi az EDA-t a 2D h´atizs´ak probl´em´ara alkalmazzuk, ahol n t´eglalap egy r´eszhalmaz´ at kell elhelyezni ´atfed´es n´elk¨ ul egy adott m´eret˝ u lapra u ´gy, hogy a kiv´alasztott t´eglalapok profitja maxim´ alis legyen. A t´eglalapok nem forgathat´ok ´es guillotine v´ag´assal lehet csak kiv´agni ˝oket a lapb´ ol. Evol´ uci´os algoritmusunk k´etf´ele val´ osz´ın˝ us´egi modellt alkalmaz. Az egyik minden t´eglalapn´al becs¨ uli annak val´osz´ın˝ us´eg´et, hogy a t´eglalap beker¨ ul a h´atizs´akba. Ez az EDA modell. A m´asik annak a val´osz´ın˝ us´eg´et becs¨ uli, hogy k´et t´eglalap egyazon csoportba (layerbe) tartozik a pakol´as sor´an. Algoritmusunk a popul´aci´o legjobb megold´ asai alapj´ an becs¨ uli a val´osz´ın˝ us´egeket. Algoritmusunk egy ut´ odot k´et l´ep´esben gener´al: az EDA modell alapj´an kiv´alasztja azokat a t´eglalapokat amelyek beker¨ ulnek a h´atizs´ akba. A m´asodik l´ep´esben sorra v´eletlen magass´ag´ u layereket defini´al, melyekbe egym´ as ut´ an elhelyezi a kiv´ alasztott t´eglalapokat a m´asodik modell alapj´an (am´ıg van hely). Az ut´od min˝ os´eg´et helyi keres˝ o elj´ ar´ asokkal finom´ıtja, amelyek t´eglalapokat cser´elnek layerek k¨ozt, vagy a h´atizs´akban l´ev˝ o t´eglalapokat cser´elik h´atizs´akon k´ıv¨ uli t´eglalapokra. A szok´asos benchmark teszhalmazokkal ellen˝orizt¨ uk algoritmusunk ´es o¨sszehasonl´ıtottuk m´as m´odszerek publik´alt eredm´enyeivel. Egy esetben megtal´alta a legjobb eredm´enyt, a t¨obbi esetben a m´asodik, vagy harmadik legjobb eredm´enyt ´erte el.
Boros Endre Rutgers University
Diszkr´ et momentum probl´ em´ ak Diszkrete momentum problemak sok megbizhatosag elmeleti alkalmazasban fellepnek. Andras Prekopa egy linearis programozason es dualitason alapulo modszert javasolt, aminek szamtalan kovetkezmenye van. Mi itt felidezunk tobb kovetkezmenyt es nehany ujabb eredmenyt.
7
B´ ota Andr´ as Research Centre for Integrated Transport Innovation School of Civil and Environmental Engineering University of New South Wales Sydney NSW 2052, Australia
Lauren M. Gardner Research Centre for Integrated Transport Innovation School of Civil and Environmental Engineering University of New South Wales Sydney NSW 2052, Australia
Hajdu L´ aszl´ o University of Szeged Institute of Informatics
Alezira Khani Department of Civil, Environmental and Geo- Engineering University of Minnesota Twin Cities 500 Pillsbury Drive SE, Minneapolis, MN 55455, USA
Kr´ esz Mikl´ os University of Szeged Faculty of Education
Utaz´ asi mint´ ak detekt´ al´ asa nagyv´ arosi t¨ omegk¨ ozleked´ esben h´ al´ ozatelemz´ esi m´ odszerekkel Napjainkban a nagyv´ arosok t¨ omegk¨ ozleked´esi h´al´ozat´anak a haszn´alata sor´an ¨onk´entelen¨ ul is kapcsolatba ker¨ ulhet¨ unk utast´ arsainkkal. Ezen kapcsolat ugyan gyeng´ebb a szoci´alis h´al´ozatokban megszokottn´al, azonban a v´ırusok terjed´es´enek szempontj´ab´ol illetve a megl´ev˝o t¨omegk¨ozleked´esi h´al´ozatok haszn´alati szok´asainak felder´ıt´ese ´erdek´eben fontos lehet a vizsg´alata. A kutat´asunk sor´ an egy vil´ agv´ aros – Twin Cities MN – egy¨ uttutaz´asi h´al´ozat´at vizsg´altuk meg. Mivel az ilyen jelleg˝ u h´ al´ ozaton a szok´ asos k¨oz¨oss´egdefin´ıci´okkal kev´esb´e nyerhet˝o ki haszn´alhat´o inform´aci´o, ez´ert megalkottunk egy, az ´altalunk vizsg´alt ´es ´erdekesnek tartott szempontoknak megfelel˝o k¨oz¨oss´egdefin´ıci´ ot. A fenti t´ıpus´ u h´ al´ ozatok vizsg´alat´ara kifejlesztett¨ unk egy u ´j k¨oz¨oss´egdetekt´al´o algoritmust, valamint a h´ al´ ozat tulajdons´ agait ´es az utaz´asi szok´asokat is felder´ıtett¨ uk. A kinyert eredm´enyek ´es az elk´esz´ıtett algoritmus haszn´alhat´o tetsz˝oleges nagyv´arosok utaz´asi szok´asainak, gyakran haszn´ alt u ´tvonalainak felder´ıt´es´ere, valamint v´ırusterjed´esi szempontb´ol a kock´azatos j´aratok vagy j´aratkombin´ aci´ ok detekt´ al´ as´ ara. Hajdu L´aszl´ o ´es Kr´esz Mikl´ os jelen kutat´asait a Nemzeti Kutat´asi, Fejleszt´esi ´es Innov´aci´os Hivatal SNN-117879 sz. p´ aly´ azata t´ amogatta.
8
Boz´ oki S´ andor ¨ MTA SZTAKI M´ern¨ oki ´es Uzleti Intelligencia Kutat´ olaborat´ orium, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport; Budapesti Corvinus Egyetem, Oper´ aci´ okutat´ as ´es Aktu´ ariustudom´ anyok Tansz´ek
Vitaliy Tsyganok Laboratory for Decision Support Systems, Institute for Information Recording of National Academy of Sciences of Ukraine; Department of System Analysis, State University of Telecommunications, Ukraine
A fesz´ıt˝ of´ akb´ ol sz´ amolt s´ ulyvektorok m´ ertani k¨ ozep´ enek optimalit´ asa a logaritmikus legkisebb n´ egyzetes c´ elfu enyre n´ ezve ¨ ggv´ A p´aros ¨osszehasonl´ıt´ as m´atrixok hagyom´ anyos alkalmaz´asi ter¨ ulete a t¨obbszempont´ u d¨ont´esi feladatokban a szempontok fontoss´ agi s´ ulyainak meghat´aroz´asa ´es az alternat´ıv´ak ´ert´ekel´ese az egyes szempontok szerint. A nem teljesen kit¨ olt¨ ott p´aros ¨ osszehasonl´ıt´as m´atrixok olyan nagy m´eret˝ u rangsorol´asi feladatokban is alkalmazhat´ ok, amelyekben az elemp´arok egy – ak´ar igen kicsiny – r´esz´ere ismert a k¨ozvetlen ¨osszehasonl´ıt´as eredm´enye. A s´ ulyoz´ asi feladat c´elja egy teljesen vagy nem teljesen kit¨olt¨ott p´aros ¨osszehasonl´ıt´as m´atrix ismeret´eben olyan s´ ulyvektort keresni, amely koordin´at´ainak p´aronk´enti ar´anyai valamilyen ´ertelemben k¨ozel vannak a megfelel˝ o m´ atrixelemekhez. A szakirodalomban legal´abb 25 s´ ulyoz´asi m´odszer ismeretes, ezek k¨oz¨ ul kett˝ o, meglehet˝ osen sz´eles k¨ orben t´argyalt ´es alkalmazott elj´ar´as ekvivalenci´aj´at mutatjuk meg. Lundy, Siraj ´es Greco friss eredm´enye – mely szerint a teljesen kit¨olt¨ott p´aros ¨osszehasonl´ıt´as m´atrixok eset´en az ¨ osszes fesz´ıt˝ of´ ab´ ol sz´ amolt s´ ulyvektor m´ertani k¨ozepe optim´alis a logaritmikus legkisebb n´egyzetes c´elf¨ uggv´enyre n´ezve – ugyanis kiterjeszthet˝o a nem teljesen kit¨olt¨ott m´atrixokra. Bizony´ıt´ asunk nem az eml´ıtett szerz˝ ok bizony´ıt´ as´ ara ´ep¨ ul, hanem egy u ´j ´es l´enyegesen r¨ovidebb u ´ton jutunk el az ´altal´anosabb t´etelhez. Az el˝oad´as di´ ai let¨ olthet˝ ok a http://www.sztaki.mta.hu/%7Ebozoki/slides oldalr´ol. Hivatkoz´ asok [1] Boz´ oki, S., Tsyganok, V. (2017): The logarithmic least squares optimality of the geometric mean of weight vectors calculated from all spanning trees for (in)complete pairwise comparison matrices, b´ır´ alat alatti k´ezirat, arXiv 1701.04265. [2] Lundy, M., Siraj, S., Greco, S. (2017): The mathematical equivalence of the spanning tree” and row geo” metric mean preference vectors and its implications for preference analysis, European Journal of Operational Research, 257(1) 197–208.
9
Boz´ oki S´ andor MTA SZTAKI, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport; Budapesti Corvinus Egyetem, Oper´ aci´ okutat´ as ´es Aktu´ ariustudom´ anyok Tansz´ek
Fu anos ¨ lo ¨p J´ ´ Obudai Egyetem, Neumann Informatikai Kar, Alkalmazott Matematikai Int´ezet MTA SZTAKI, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport;
P´ aros o as m´ atrixokb´ ol sz´ amolt s´ ulyvektorok Pareto-optimalit´ asa ¨sszehasonl´ıt´ A t¨obbkrit´erium´ u d¨ ont´eshozatal m´odszereiben gyakran alkalmaznak p´aros ¨osszehasonl´ıt´as m´atrixokat, amelyekb˝ol megfelel˝ o m´ odszerekkel az ¨ osszehasonl´ıt´asokban r´eszt vev˝o alternat´ıv´akra vonatkoz´oan egy fontoss´agi s´ ulyvektor nyerhet˝ o ki. A vektoroptimaliz´al´as terminol´ogi´aj´at alkalmazva egy s´ ulyvektor hat´ekony, ha nem ´etezik egy m´asik olyan s´ ulyvektor, amely minden komponensben legal´abb olyan j´ol k¨ozel´ıt, s˝ot legal´ abb egy poz´ıci´ oban szigor´ uan jobban. Egy s´ ulyvektor gyeng´en hat´ekony, ha a p´aronk´enti h´anyadosokkal val´ o k¨ ozel´ıt´es nem jav´ıthat´o meg egyszerre minden diagon´alison k´ıv¨ uli poz´ıci´oban. Megmutatjuk, hogy a saj´ atvektor m´ odszer sor´an alkalmazott, a legnagyobb saj´at´ert´ekhez tartoz´o saj´atvektor mindig gyeng´en hat´ekony, viszont numerikus p´eld´akat mutatunk arra is, hogy lehet nem hat´ekony is. Line´aris programoz´ asi feladatokat vezet¨ unk be annak ellen˝orz´es´ere, hogy egy adott s´ ulyvektor (gyeng´en) hat´ekony-e, ´es ha nem az, akkor egy (er˝osen) domin´al´o hat´ekony s´ ulyvektort is kapunk. Kit´er¨ unk a pcmc.online helyen el´erhet˝ o Pairwise Comparison Matrix Calculator alkalmaz´asra is, amelyben az itt bemutatott m´odszerek is implement´ alva lettek.
Cs´ aji Bal´ azs Csan´ ad MTA SZTAKI
Bizonytalan konvex programok Monte Carlo k¨ ozel´ıt´ eseinek megb´ızhat´ os´ ag´ ar´ ol Bizonytalan konvex programok [1, 2, 3, 4, 5] olyan optimaliz´al´asi feladatok, ahol egy konvex1 c´elf¨ uggv´enyt kell minimaliz´alnunk konvex korl´ atoz´ o felt´etelek mellett, amelyek azonban egy bizonytalan (ak´ar vektor) param´etert˝ ol is f¨ uggnek. A k´et klasszikus megk¨ozel´ıt´es a bizonytalans´agok kezel´es´ere, hogy vagy egy olyan megold´ ast keres¨ unk, amely az ¨ osszes lehets´eges korl´atoz´as metszet´eben van – robusztus optimaliz´al´as paradigma [1] –, vagy feltessz¨ uk egy a bizonytalan param´eter lehets´eges ´ert´ekein ´ertelmezett val´osz´ın˝ us´egi m´ert´ek l´etez´es´et – sztochasztikus programoz´as paradigma [5] – ´es a fenti feladat valamilyen relax´aci´oj´at (p´eld´ aul, val´ osz´ın˝ us´egi korl´ atos feladat) oldjuk meg. Az els˝o megk¨ ozel´ıt´es sokszor t´ ul konzervat´ıv megold´asokhoz vezet, m´asr´eszt ahhoz, hogy hat´ekonyan tudjuk fel´ırni a korl´ atoz´ asok metszet´et, ´altal´aban a bizonytalan param´eter ´ert´ekeinek halmaz´ar´ol kell feltev´eseket tenn¨ unk. Ha viszont csak p´eld´ aul valamilyen val´ osz´ın˝ us´eggel k¨ovetelj¨ uk meg a korl´atoz´asok kiel´eg´ıt´es´et, de az ezeknek megfelel˝ o legjobb megold´ast keress¨ uk, akkor tipikusan neh´ez feladatokhoz jutunk, hacsak nem tesz¨ unk er˝ os feltev´eseket a bizonytalan param´eter eloszl´as´ar´ol [1]. Az el˝oad´asban megvizsg´ aljuk az u ´n. szcen´ ari´ o m´ odszert [2, 3, 4], amely egyszer˝ uen abb´ol ´all, hogy vesz¨ unk egy v´eges v´eletlen (i.i.d.) mint´ at a bizonytalan param´eter (potenci´alisan v´egtelen sok) lehets´eges ´ert´ekei k¨ oz¨ ul ´es csak az ezek ´altal meghat´arozott korl´ atoz´asokat vessz¨ uk figyelembe a megold´as keres´esekor. Ehhez a megk¨ ozel´ıt´eshez egyr´eszt nem kell feltenn¨ unk semmit a bizonytalans´agi halmazr´ol, s˝ot a bizonytalans´ agi param´eter val´ osz´ın˝ us´egi eloszl´as´ar´ol sem, el´eg ha (i.i.d.) mint´akat tudunk gener´alni a param´eter ´ert´ekeib˝ ol (ak´ ar szimul´ aci´ o vagy fizikai m´er´esek seg´ıts´eg´evel).
1 Az
´ altal´ anoss´ ag megszor´ıt´ asa n´ elk¨ ul feltehet˝ o, hogy line´ aris ´ es nem f¨ ugg a bizonytalan param´ etert˝ ol.
10
M. C. Campi, S. Garatti ´es G. Calafiore nyom´an [2, 3, 4] megvizsg´aljuk, hogy (i) egy adott mintasz´am mellett kapott (v´eletlen´ıtett) megold´ as milyen megb´ızhat´o, ha az ismeretlen (nem mintav´etelezett) korl´atok megs´ert´es´enek val´ osz´ın˝ us´eg´et egy el˝ore adott ´ert´ek alatt akarjuk tartani; (ii) tudunk-e valamit mondani az ismeretlen korl´ atok megs´ert´esi val´osz´ın˝ us´eg´enek konkr´et eloszl´as´ar´ol, valamint (iii) a m´odszer alkalmaz´asi lehet˝ os´egeir˝ ol szekvenci´ alis d¨ont´esi feladatok eset´en. Hivatkoz´ asok [1] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski, Robust Optimization, Princeton University Press, 2009. [2] Giuseppe Calafiore and Marco C. Campi, Uncertain convex programs: Randomized solutions and confidence levels, Mathematical Programming, 102(1):25–46 (2005). [3] Marco C. Campi and Simone Garatti, The exact feasibility of randomized solutions of uncertain convex programs, SIAM Journal on Optimization, 19(3):1211–1230 (2008). [4] Marco C. Campi and Simone Garatti, Wait-and-judge scenario optimization, Mathematical Programming, pages 1–35 (2016). [5] Andr´ as Pr´ekopa, Stochastic Programming, Springer Science & Business Media (1995).
Cs´ aji Bal´ azs Csan´ ad MTA SZTAKI
H´ al´ ozati fontoss´ ag n¨ ovel´ ese: PageRank optimaliz´ al´ as mint Markov d¨ ont´ esi probl´ ema Egy standard (centralit´ asi) m´ert´ek ir´ any´ıtott gr´afok cs´ ucsainak fontoss´ag´anak m´er´es´ere a PageRank m´odszer [1], amit p´eld´ aul a Google is alkalmaz web-keres´esek fontoss´ag szerinti sorba rendez´es´ehez. A PageRank fogalm´ at mind line´ aris algebrai mind val´osz´ın˝ us´egsz´am´ıt´asi fogalmakkal bevezethetj¨ uk. Ez ut´obbi terminol´ ogi´ aj´ at haszn´alva, egy cs´ ucs PageRank-je nem m´as, mint a gr´afon ´ertelmezett v´eletlen bolyong´as stacion´ arius (egyens´ ulyi) eloszl´ asa az adott cs´ ucsra vonatkoz´oan.2 Egy term´eszetes k´erd´es, hogy egy (adott) ir´any´ıtott gr´afban hogyan tudjuk maximaliz´alni egy (adott) cs´ ucs fontoss´ag´at (PageRank-j´et), ha az ´elek egy (adott) r´eszhalmaz´at megv´altoztathatjuk, azaz eld¨onthetj¨ uk, hogy a halmazb´ ol mely ´elek szerepeljenek a gr´afban ´es melyek ne. Az el˝oad´asban megmutatjuk, hogy ez probl´ema (hat´ekonyan) visszavezethet˝o egy Markov d¨ont´esi probl´em´ara [3], konkr´etan egy sztochasztikus legr¨ ovidebb u ´t feladatra. Ennek egy k¨ovetkezm´enye, hogy a probl´ema polinomi´alis id˝oben megoldhat´o ´es p´eld´ aul line´ aris programoz´ asi feladatk´ent is fel´ırhat´o [2]. Az el˝oad´asban bevezet¨ unk m´eg egy alternat´ıv moh´o algoritmust is, amely szint´en polinomi´alis id˝oben oldja meg a PageRank maximaliz´ al´ as feladatot, valamint megmutatjuk, hogy a feladat tov´abbi gyenge korl´atoz´asok mellett (p´eld´ aul egym´ ast kiz´ ar´o ´elek) NP-neh´ezz´e v´alik. Hivatkoz´ asok [1] Amy N. Langville and Carl D. Meyer, Google’s PageRank and beyond: The science of search engine rankings, Princeton University Press (2011). [2] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of Markov decision processes, Mathematics of Operations Research, 12(3):441–450 (1987). aji, R. Jungers, and V. D. Blondel, Pagerank optimization by edge selection, Discrete Applied [3] B. Cs. Cs´ Mathematics, 169:73–87 (2014).
2 Ez a PageRank eset´ eben mindig l´ etezik, ugyanis a bolyong´ ast u ´gy defini´ aljuk, hogy kis val´ osz´ın˝ us´ eggel az ´ elekt˝ ol f¨ uggetlen¨ ul b´ armely cs´ ucsba el lehessen jutni egy l´ ep´ esben, valamint a kimen˝ o´ elekkel nem rendelkez˝ o cs´ ucsokb´ ol egyenletes eloszl´ assal l´ ep¨ unk tov´ abb egy m´ asik cs´ ucsba, ´ıgy a Markov l´ anc aperiodikus ´ es irreducibilis lesz.
11
Csat´ o L´ aszl´ o MTA Sz´ am´ıt´ astechnikai ´es Automatiz´ al´ asi Kutat´ oint´ezet (MTA SZTAKI), ¨ M´ern¨ oki ´es Uzleti Intelligencia Kutat´ olaborat´ orium, Oper´ aci´ okutat´ as ´es D¨ ont´esi Rendszerek Kutat´ ocsoport; Budapesti Corvinus Egyetem (BCE) Oper´ aci´ okutat´ as ´es Aktu´ ariustudom´ anyok Tansz´ek
A logaritmikus legkisebb n´ egyzetek m´ odszer´ enek karakteriz´ aci´ oi T¨obbszempont´ u d¨ ont´esi probl´em´ ak megold´ asa sor´an gyakran sz¨ uks´egess´e v´alik s´ ulyvektor sz´am´ıt´asa a d¨ont´eshoz´o ´altal megadott p´aros ¨ osszehasonl´ıt´as m´atrixb´ol. Az el˝oad´as az egyik legn´epszer˝ ubb elj´ar´as, a logaritmikus legkisebb n´egyzetek m´ odszere, valamint az ebb˝ol k´epzett rangsor egy-egy axiomatikus karakteriz´aci´oj´ at mutatja be. El˝ osz¨ or bizony´ıtjuk, hogy ez az egyetlen elj´ar´as, amely konzisztens esetben a p´aros ¨osszehasonl´ıt´ as m´atrixot gener´ al´ o s´ ulyvektort adja, valamint f¨ uggetlen a konzisztencia vissza´all´ıt´as transzform´ aci´ ora n´ezve. Ezt k¨ ovet˝ oen igazoljuk, hogy az alternat´ıv´ak logaritmikus legkisebb n´egyzetek m´odszer´eb˝ ol ad´od´ o rangsora az egyetlen olyan, amely rendelkezik a k¨ovetkez˝o tulajdons´agokkal: • Anonimit´as: a rangsor f¨ uggetlen az alternat´ıv´ak elnevez´es´et˝ol; • Aggreg´aci´o invariancia: ha egy alternat´ıva egyetlen d¨ont´eshoz´o preferenci´ai szerint sem rosszabb egy m´asikn´al, akkor ez a kollekt´ıv preferenci´akra is teljes¨ ul; • Gyenge monotonit´ as: amennyiben az i-edik alternat´ıva nem rosszabb a j-edikn´el, akkor szigor´ uan jobb lesz, ha p´aros ¨ osszehasonl´ıt´ asuk eredm´enye az i-edik szempontj´ab´ol javul.
Csendes Tibor SZTE Informatika
B´ anhelyi Bal´ azs SZTE Informatika
Mester Abig´ el SZTE Informatika
Mik´ o J´ ozsefn´ e J´ on´ as Edit SZTE Mez˝ ogazdas´ agi Kar
Horv´ ath J´ ozsef SZTE Mez˝ ogazdas´ agi Kar
Sztochasztikus optimaliz´ al´ as tehen´ eszetben A mez˝ogazdas´ agi nagy rendszerek j´o r´esze alaposan ´atgondolt ´es a gazd´alkod´ok sz´am´ara j´o megold´ast jelent. Maradtak az´ert olyan d¨ ont´esi helyzetek, amikhez az ´erintettek nem kapnak k¨ uls˝o seg´ıts´eget. Ilyen a tehen´eszeteknek az a probl´em´ aja, hogy a megbetegedett tehenet mikor adj´ak el. A l´enyeget illet˝oen a d¨ont´eshoz´onak a j¨ ov˝ obeli v´eletlen esem´enyek ¨osszevont hat´as´at kellene j´ol meg´ıt´elnie ahhoz, hogy az aktu´alis d¨ont´es´et az ´allat tov´abbi tart´ as´ ar´ ol vagy elad´as´ar´ol k¨ozgazdas´agi ´ertelemben kedvez˝o m´odon megtehesse. A szakter¨ ulet k´epvisel˝ oivel egy¨ uttm˝ uk¨ odve a kor´abbi mikroszimul´aci´os tapasztalatunk [1, 2] alapj´an egy olyan sztochasztikus optimaliz´ al´ asi modellt dolgoztunk ki, amely a relev´ans param´eterek j´o r´esz´et tartalmazza, ´es alkalmas az eml´ıtett d¨ ont´es kedvez˝o kialak´ıt´as´ara. Els˝o l´ep´esk´ent n´eh´any gazdas´agb´ol sz´armaz´o val´os adatra t´ amaszkodva olyan okostelefonos alkalmaz´ast dolgoztunk ki, amely k´epes a d¨ont´esi helyzet megalapozott bemutat´ as´ ara, ´es a haszn´alatos h¨ uvelykszab´alyokn´al profit´abilisabb d¨ont´est javasolni. Az alkalmaz´ as Android rendszerekre let¨olhet˝o a www.inf.u-szeged.hu/~banhelyi/Buu c´ımr˝ol. Az el˝oad´ asban besz´ amolunk a m´odszer haszn´alat´anak el˝onyeir˝ol, ´es a tov´abbfejleszt´es tervezett ir´anyair´ol. 12
Hivatkoz´ asok [1] Az utaz´ assz´ am alap´ u jegyrendszer id˝ oalap´ u jegyrendszerr´e t¨ ort´en˝ o ´ at´ all´ıt´ as´ anak gazdas´ agi modellez´ese), KNRet, Szeged, 2010. [2] Alm´ asi Bern´ at ´es Palatinus Endre: Az id˝ oalap´ u jegyrendszer gazdas´ agi hat´ as´ anak sz´ am´ıt´ og´epes modellez´ese. Tudom´ anyos Di´ akk¨ ori Konferencia, Szegedi Tudom´ anyegyetem, 2010.
D´ avid Bal´ azs Szegedi Tudom´ anyegyetem, Juh´ asz Gyula Pedag´ ogusk´epz˝ o Kar
Kr´ esz Mikl´ os Szegedi Tudom´ anyegyetem, Juh´ asz Gyula Pedag´ ogusk´epz˝ o Kar
J´ arm˝ uvek u ese a tervez´ esi egys´ egek k¨ ozti hasonl´ os´ ag ¨ temez´ figyelembev´ etel´ evel A k¨oz¨oss´egi k¨ozleked´esben felmer¨ ul˝ o egyik legfontosabb optimaliz´al´asi probl´ema a j´arm˝ uvek u ¨temez´eseinek kialak´ıt´asa. A k¨ ozleked´esi t´ arsas´ agok szempontj´ab´ol ez a feladat azonban nem az egyes tervez´esi egys´egek (melyek ´altal´ aban az egyes napt´ ari napoknak felelnek meg) alapj´an fel´ep´ıtett f¨ uggetlen u ¨temez´esek megold´ as´ at jelenti, hanem egy hosszabb tervez´esi id˝oszakra t¨ort´en˝o, ´altal´aban t¨obb hetes, vagy h´onapos ¨osszef¨ ugg˝ o id˝ oszakra adott u ¨temez´esek sorozat´at. A fenti tervez´esi id˝ oszak sor´ an sz´ amos olyan napi u ¨temez´est kell megoldani, melyek eset´eben a feladatok bemenet´et k´epez˝ o menetrend szerinti j´arathalmazok k¨oz¨ott nagy az ´atfed´es. Amennyiben ezekre a probl´em´akra f¨ uggetlen megold´ asokat adunk, u ´gy a kapott eredm´enyek strukt´ ur´aja jelent˝osen elt´erhet. A gyakorlati alkalmaz´ as szempontj´ ab´ ol azonban fontos szempont, hogy a hasonl´o bemenettel rendelkez˝o napok megold´ asai hasonl´ ou ¨temez´esek legyenek. Ezzel a jelent˝os probl´em´aval eddig csak kevesen foglalkoztak a szakirodalomban [1, 2]. El˝oad´asunkban egy olyan m´ odszert mutatunk be, amely k¨oz¨osen kezeli a tervez´esi id˝oszak hasonl´o bemenettel rendelkez˝ o napjait, ´es az ezekhez tartoz´o u ¨temez´eseket egyszerre alak´ıtja ki. A m´odszer a feladathoz tartoz´ o ´altal´ anos k¨ olts´egek mellett az u ag´at is figyelembe veszi. ¨temez´esek hasonl´os´ Jelen kutat´ ast a Nemzeti Kutat´ asi, Fejleszt´esi ´es Innov´aci´os Hivatal SNN-117879 sz. p´aly´azat´aval t´amogatta. Hivatkoz´ asok [1] Amberg, B., Amberg, B., & Kliewer, N., Approaches for increasing the similarity of resource schedules in public transport, Procedia-Social and Behavioral Sciences, 20 (2011), 836–845. [2] Kliewer, N., Gintner, V., & Suhl, L.. Line change considerations within a time-space network based multidepot bus scheduling model, in: Computer-aided Systems in Public Transport (pp. 57–70). Springer Berlin Heidelberg (2008).
13
Dobj´ ann´ e Antal Elvira Pallasz Ath´en´e Egyetem, GAMF M˝ uszaki ´es Informatikai Kar
Vink´ o Tam´ as Szegedi Tudom´ anyegyetem, Informatikai Int´ezet
Heurisztik´ ak BitTorrent h´ al´ ozatok max-min m´ elt´ anyos s´ avsz´ eless´ eg-kioszt´ as´ ara Egy BitTorrent k¨ oz¨ oss´eg adat-´ araml´ as´ anak modellez´ese egy speci´alis p´aros gr´afon ´ertelmezett h´al´ozati folyam feladatra vezet. A s´avsz´eless´eg-kioszt´ as (bandwidth allocation) probl´em´aja egy r¨ogz´ıtett h´al´ozat cs´ ucspontjai k¨ oz¨ ott foly´ o adat´ araml´ as optim´ alis intenzit´asainak meghat´aroz´asa. Munk´ankban t¨obbrajos (multiswarm) h´al´ ozatok max-min m´elt´ anyos s´avsz´eless´eg-kioszt´as´ara koncentr´alunk. A feladatra l´etez˝ o egzakt algoritmusok val´os m´eret˝ u h´al´ozatok gr´afjain nagyon lassan futnak, ez´ert c´elunk egy j´o k¨ ozel´ıt´est ad´o, hat´ekony heurisztika megalkot´asa. Az el˝oad´asban val´os BitTorrent k¨oz¨oss´egekb˝ol sz´armaz´ o m´er´esi adatokon mutatjuk be a szimul´alt h˝ ut´es egy adapt´aci´oj´anak m˝ uk¨od´es´et, illetve azt, hogy az ´erintett gr´ af speci´ alis tulajdons´againak kihaszn´al´as´aval milyen m´ert´ekben tudunk az el˝obbi algoritmus hat´ekonys´ ag´ an jav´ıtani.
Dobos Imre V´ allalatgazdas´ agtan Int´ezet, BCE
Gelei Andrea V´ allalatgazdas´ agtan Int´ezet, BCE
Dud´ as Levente V´ allalatgazdas´ agtan Int´ezet, BCE
A bizalomj´ at´ ek egy dinamiz´ alt v´ altozat´ anak statisztikai elemz´ ese A bizalom kutat´ asa k¨ ozponti helyet foglal el az ell´at´asi l´ancok, de t´agabban a glob´alis gazdas´ag u ¨zleti h´al´ozatai kapcsolatrendszer´enek elemz´es´eben. Az ilyen kapcsolatokat elemezz¨ uk dolgozatunkban a k´ıs´erleti k¨ozgazdas´agtan egyik alapmodellj´enek seg´ıts´eg´evel. Az alapj´at´ek j´ ol ismert, nevezik m´eg befektet´esi j´at´eknak is. Az ismert alapj´at´eknak sz´amtalan kiterjeszt´ese van az ism´etelt j´at´ekok k¨ oz¨ ott. Mi – ismereteink szerint – egy u ´j kiterjeszt´est v´alasztottunk. Megold´asunk u ´jszer˝ us´ege a k¨ ovetkez˝ okben ragadhat´o meg: ul¨on koncepci´ ok´ent ´ertelmezz¨ uk a bizalomra m´elt´os´agot ´es a bizalmat. – K¨ – E k´et kapcsol´ od´ o, de k¨ ul¨ onb¨ oz˝ o fogalmat a j´at´ekban operacionaliz´aljuk, a k¨oz¨ott¨ uk l´ev˝o hat´asokat ´ıgy elemezni tudjuk. asunknak az is, hogy az ism´etelt j´at´ek sor´an a r´esztvev˝ok eredm´enyei k¨or¨onk´ent – Egyedis´ege megold´ o¨sszegz˝odnek. A j´at´ek sor´ an kapott adatb´ azisunkat a matematikai statisztika eszk¨ozeivel elemezz¨ uk. Hipot´ezis¨ unk, hogy a stock” jelleg˝ u bizalomra m´elt´ os´ ag adott kapcsolatban befoly´asolja a j´at´ekosok d¨ont´eseit, ´ıgy ” a cselekv´esi hajland´ os´ agk´ent ´ertelmezett bizalmat. A j´at´ek sor´an a n´eh´any tov´abbi inform´aci´ot k´ert¨ unk az egy´ebk´ent anonim r´esztvev˝okt˝ ol, melyek seg´ıts´eg´evel a j´at´ek sor´an tapasztalt alap¨osszef¨ ugg´eseket elemz´es¨ unk m´asodik l´ep´esek´ent finom´ıtani tudjuk.
14
Alapvet˝o kutat´ asi k´erd´es¨ unk az u ¨zleti kapcsolatokhoz k¨ot˝odik. Kor´abbi kutat´asok azt mutatj´ak, hogy az egyetemi hallgat´ ok (k¨ ul¨ on¨ osen a gazdas´agi jelleg˝ u k´epz´esekben r´eszt vev˝ok) d¨ont´esei az u ¨zleti ´eletben gyakorl´ o szakemberek d¨ ont´eseihez hasonl´oak. Ez´ert a j´at´ekot, az adatfelv´etelt a Budapesti Corvinus egyetem hallgat´ oinak r´eszv´etellel bonyol´ıtottuk. K¨ osz¨ onetnyilv´ an´ıt´ as. A szerz˝ ok k¨ osz¨ onik az OTKA K 115542 t´amogat´as´at. Kulcsszavak: Trust Game, Experimental Economics, Diadikus adatelemz´es, Matematikai statisztika.
Dobos Imre Logisztika ´es Ell´ at´ asi L´ anc Menedzsment Tansz´ek, Budapesti Corvinus Egyetem
V¨ or¨ osmarty Gy¨ ongyi Logisztika ´es Ell´ at´ asi L´ anc Menedzsment Tansz´ek, Budapesti Corvinus Egyetem
Zo all´ıt´ o´ ert´ ekel´ es ´ es ´ erz´ ekenys´ egvizsg´ alat egy DEA modellben ¨ld besz´ Egy kor´abbi cikk¨ unkben (Dobos–V¨ or¨ osmarty (2014): Green supplier selection and evaluation using DEAtype composite indicators, International Journal of Production Economics) egy DEA-n alapul´o rangsorol´asi elj´ar´ast javasoltunk a prefer´ alt z¨ old besz´all´ıt´o kiv´alaszt´as´ara. A modell a k¨ornyezeti t´enyez˝oket (CO2, u ´jrafelhaszn´ alhat´ os´ ag stb.), mint a DEA modell outputj´at ´ertelmezi, m´ıg a szok´asos gazd´alkod´asi t´enyez˝oket (k¨olts´eg, min˝ os´eg stb.) mint a rangsorol´asi elj´ar´as inputj´at veszi figyelembe. Folytatjuk a kor´ abbi vizsg´ alatainkat a k¨oz¨os s´ ulyok meghat´aroz´as´aval az´ert, hogy az ut´olagos besz´all´ıt´o ´ert´ekel´eshez ezeket a s´ ulyokat u ´jra felhaszn´alhassuk. Ezek a s´ ulyok a k´et vizsg´alatban szorosan uggnek az ´ert´ekel´es folyam´ an. ¨osszef¨ Az ezt k¨ovet˝ o elemz´esben a k¨ ornyezeti t´enyez˝ok, mint pl. CO2 kibocs´at´as, s´ ulyokra t¨ort´en˝o ´erz´ekenys´eg´et elemezz¨ uk a parametrikus programoz´as seg´ıts´eg´evel. A parametrikus programoz´asra alapul´o ´erz´ekenys´egvizsg´ alatot ebben az esetben az nehez´ıti meg, hogy a parametriz´aland´o v´altoz´o a technol´ogiai m´atrixban szerepel. A line´ aris programoz´asban a jobboldali korl´atok, vagy a c´elf¨ uggv´eny parametriz´al´as´aval kapott eredm´enyek analitikusan bizony´ıthat´o, j´ol viselked˝o eredm´enyeket adnak. Viszont az ´altalunk vizsg´ alt esetben az eredm´enyek sokszor m´eg csak nem is folytonosak, s˝ot, ak´ar szakad´asosak is lehetnek. Ez az elemz´es lehet˝ ov´e teszi a d¨ont´eshoz´onak az optim´alis k¨oz¨os s´ ulyokt´ol elt´erve bizonyos k¨ornyezeti t´enyez˝ oket nagyobb s´ ullyal vegyenek a d¨ont´esn´el figyelembe. El˝oad´asunk a 2015. ´evi MOT konferenci´ an el˝oadott eredm´enyeink folytat´asa. Kulcsszavak: z¨ old besz´ all´ıt´ o ´ert´ekel´es, DEA, K¨ oz¨ os s´ ulyok elemz´ese, T¨ obbt´enyez˝ os d¨ ont´eshoz´ as.
D´ osa Gyo ¨rgy Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
L´ adapakol´ asi j´ at´ ekok A l´adapakol´asi feladattal a 70-es ´evek elej´et˝ ol fogva kezdtek foglalkozni (alapvet˝o eredm´enyeket tartalmaz Johnson [11] dolgozata), a feladat a k¨ ovetkez˝o: Adottak t´argyak, amelyeknek a m´erete 0 ´es 1 k¨oz¨otti sz´amok, ezeket kell a lehet˝ o legkevesebb egys´egnyi m´eret˝ u l´ad´aba pakolni. A feladat NP-neh´ez, ´es sok ´erdekes k´erd´est vet fel, t¨ obbek k¨ oz¨ ott az approxim´aci´os algoritmusok elm´elet´enek kialakul´as´aban is alapvet˝o szerepet j´atszott. A l´adapakol´ asi j´ at´ekok eset´en adott valamilyen pakol´as, ´es a t´argyak igyekeznek” valamilyen sz´a” mukra kedvez˝obb m´odon pakol´ odni. Az ezzel kapcsolatos vizsg´alatokat Bilo kezdte [1]. Itt a t´argyak m´eret¨ ukkel ar´anyosan fizetnek” az´ert hogy egy l´ad´aban benne lehessenek, ´es ha egy t´argy ´at tud ker¨ ulni ” 15
egy m´asik l´ad´aba u ´gy hogy ott kevesebbet fizet (bef´er oda, ´es miut´an odamegy, a t´argyak o¨sszm´erete ˝ovele egy¨ utt a megc´elzott l´ ad´ aban nagyobb mint a jelenlegi l´ad´aj´aban), akkor a t´argy egy o¨nz˝o l´e” p´est” tesz, ´atmegy oda. Kimutathat´ o, hogy v´eges sok l´ep´es ut´an egyens´ ulyi helyzet (Nash Equilibrium, r¨oviden NE) ´all be, ´es az NE pakol´ as eset´en a l´ad´ak sz´ama legfeljebb 5/3-szorosa az optim´alis l´adasz´amnak. A feladatnak az´ota t¨ obbf´ele vari´ ansa sz¨ uletett, illetve k¨ ul¨onf´ele vizsg´alatok folytak az egyens´ ulyi helyzetekkel kapcsolatban [2–10]. Ezekr˝ol igyeksz¨ unk egy ´attekint´est ny´ ujtani, bemutatva az ismert ´es u ´j eredm´enyeket, tov´abbl´ep´esi lehet˝os´egeket, nyitott k´erd´eseket is. Hivatkoz´ asok [1] V. Bil` o, On the packing of selfish items, in: Proc. of the 20th International Parallel and Distributed Processing Symposium (IPDPS’06), IEEE, 2006. 9 pages. [2] G. Dosa, L. Epstein, Generalized selfish bin packing, arXiv:1202.4080 [cs.GT]. [3] G. Dosa, L. Epstein, The convergence time for selfish bin packing, in: Proc. of The 7th International Symposium on Algorithmic Game Theory (SAGT’14), LNCS 8768, 37–48, 2014. [4] G. Dosa, The bin-packing game with priorities, The 29th Conference of the European Chapter on Combinatorial Optimization, ECCO 2016, Budapest, Hungary, May 26–28, 2016. [5] L. Epstein, E. Kleiman, Selfish bin packing, Algorithmica, 60(2) (2011), 368–394. [6] L. Epstein, Bin Packing Games with Selfish Items, eds: Krishnendu Chatterjee and Jir´ı Sgall, 38th International Symposium, MFCS 2013, Lecture Notes in Computer Science 8087, 8–21, 2013. [7] L. Epstein, E. Kleiman, and J. Mestre. Parametric packing of selfish items and the subset sum algorithm, Algorithmica, 74 (2016), 177–207. [8] R. Ma, G. Dosa, X. Han, H. F. Ting, D. Ye, Y. Zhang, A note on a selfish bin packing problem, Journal of Global Optimization, 56 (2012), 1457–1462. [9] Z. Wang, X. Han, G. Dosa, Zs. Tuza, Bin packing game with an interest matrix, LNCS 9198, Chapter: Computing and Combinatorics, 57–69, 2015. [10] G. Yu and G. Zhang, Bin packing of selfish items, in: The 4th International Workshop on Internet and Network Economics (WINE’08), LNCS 5385, 446–453, 2008. [11] D. S. Johnson, Near-optimal bin-packing algorithms, Doctoral Thesis, MIT, Cambridge, 1973.
D¨ om¨ ot¨ or Barbara Budapesti Corvinus Egyetem
Kov´ acs Erzs´ ebet Budapesti Corvinus Egyetem
Mi mozgatja a hat´ arid˝ os devizapoz´ıci´ okat? A magyar piac elemz´ ese A cikkben a deviza´ arfolyam kock´ azat kezel´es´et befoly´asol´o t´enyez˝oket vizsg´altuk, a 2004–2016 k¨oz¨otti v´allalati hat´arid˝ os deviza´ allom´anyok statisztikai elemz´es´evel. Azt tal´altuk, hogy a hat´arid˝os devizaelad´asb´ol sz´armaz´ o kitetts´eg szignifik´ ansan meghaladja a hat´arid˝os devizav´etelt. T¨obbv´altoz´ os line´ aris regresszi´ os modellt ´ep´ıtett¨ unk, amelyben a kereskedelmi m´erleg egyenleg mellett a devizapiaci v´ altoz´ ok alakul´ as´ anak hat´as´at vizsg´altuk a hat´arid˝os poz´ıci´ok havi alakul´as´ara. Az eredm´enyeket er˝ osen befoly´ asol´ o d´ atumokat vizsg´alva egy kritikus h´onapot tal´altuk, amit kihagytunk az elemz´esb˝ ol. V´arakoz´ asainknak megfelel˝on a deviza´arfolyam kedvez˝o ir´any´ u elmozdul´asa – hat´arid˝os elad´as eset´en emelked´ese, hat´ arid˝ os v´etel eset´eben cs¨okken´ese – szignifik´ansan n¨ovelte a hat´arid˝os ´allom´anyt, valamint a n¨ ovekv˝ o devizapiaci volatilit´as szint´en a hat´arid˝os poz´ıci´ok ´allom´any´anak emelked´es´evel j´art egy¨ utt. Mind a hat´ arid˝ os v´eteli, mind pedig a hat´arid˝os elad´asi poz´ıci´ok szignifik´ansan cs¨okkentek az ´ev v´eg´en, amit egyr´eszt az ´ev v´eg´ere k¨ot¨ott fedezeti u ¨gyletek kifut´asa, m´asr´eszt pedig a m´erlegfordul´onap el˝ otti poz´ıci´ oz´ ar´ asok indokolnak. 16
A tov´abbi piaci v´altoz´ ok, a kamatl´ ab-, illetve swap-differencia- (a hat´arid˝os ´es azonnali ´arfolyam k¨ ul¨onbs´ege) t´ıpus´ u v´altoz´ ok m´ar nem ker¨ ultek be a modellbe, aminek oka ezen v´altoz´ok szoros korrel´aci´oja a modellbe bevont t¨ obbi magyar´ az´ o v´altoz´oval. A kereskedelmi m´erleg egyenleg v´altoz´asa egy´altal´an nem hatott az ´allom´ anyokra, ami azzal magyar´azhat´o, hogy m´ıg a kereskedelmi m´erleg a t´enyleges ´arumozg´asokat r¨ ogz´ıti, a hat´ arid˝ os fedez´es ezt megel˝oz˝oen t¨ort´enik. A magyar´az´ o v´ altoz´ oink k¨ oz¨ otti kapcsolatrendszert f˝okomponens elemz´essel vizsg´altuk. A 13 piaci v´altoz´o varianci´ aj´ anak 80%-a ¨ ot f˝ okomponenssel le´ırhat´o, amelyek k¨oz¨ ul az EURHUF ´arfolyamot ´es volatilit´ast mag´ aban foglal´ o els˝o f˝ okomponens a teljes variancia 35%-´at, az EURUSD volatilit´ast tartalmaz´o m´asodik f˝okomponens pedig tov´ abbi 17%-ot magyar´azott. Mindez azt mutatja, hogy els˝osorban a hazai (forint) ´arfolyam mozg´ asa a meghat´ aroz´o, de jelent˝os a glob´alis devizapiaci turbulencia hat´asa is. A hat´arid˝os deviza elad´ asi (r¨ ovid hat´ arid˝os) devizapoz´ıci´o v´altoz´as´at a modell¨ unk mintegy 60%-ban magyar´azta, a hat´ arid˝ os v´eteli (hossz´ u) ´allom´anyok eset´en azonban csak 20%-os a modell¨ unk magyar´az´o ereje. A nem lin´ aris kapcsolatok vizsg´ alat´ aval sem kaptunk enn´el jobb modellt. Mindez azt mutatja, hogy b´ar egy´eb t´enyez˝ ok is hatnak a hat´ arid˝ os deviza´allom´anyokra, a piaci mozg´asok hat´asa, k¨ ul¨on¨osen a deviza elad´asok eset´en jelent˝ os, a hat´ arid˝os devizapoz´ıci´ok teh´at nemcsak fedezeti c´elt szolg´alnak a v´allalati kock´azatkezel´esben, hanem jelent˝ os r´eszben spekul´aci´o eredm´enyei.
Egri P´ eter MTA SZTAKI
Kis Tam´ as MTA SZTAKI
Pareto-optim´ alis anyageloszt´ o mechanizmus Az algoritmikus mechanizmustervez´es a kialakul´asa ´ota vizsg´al elosztott u ¨temez´esi probl´em´akat. Ez az el˝oad´as egy gyakorlatban fontos, ´am elm´eleti szempontb´ol elhanyagolt esetet vizsg´al: a projekt¨ utemez´esi probl´em´ at, ahol a megel˝oz´esi rel´ aci´ okkal adott feladatok k¨ ul¨onb¨oz˝o nem meg´ ujul´o er˝oforr´asok´ert – p´eld´aul alapanyagok – versenyeznek. Hab´ar a k¨ozpontos´ıtott probl´ema polinomi´alis id˝oben megoldhat´o Carlier ´es Rinnooy Kan nyolcvanas ´evekb˝ol sz´armaz´o algoritmus´aval, az anyageloszt´as elosztott k¨ornyezetben ritk´ an optim´ alis. Gyakorlati termel´estervez´esi helyzetekben a projektmenedzserek hajlamosak miel˝obb bet´ arazni a sz¨ uks´eges alapanyagokat a k´es˝obbi anyaghi´anyokb´ol ad´od´o k´es´esek elker¨ ul´ese ´erdek´eben. Ez a moh´ o gyakorlat egyszerre vezet bizonyos helyeken feleslegesen nagy k´eszletekhez, m´ıg m´ashol ezzel egy id˝ oben hi´ any alakulhat ki. Ennek a kutat´ asnak a c´elja egy termel˝o gy´ar anyageloszt´asi probl´em´aj´anak modellez´ese, ahol egy k¨ozponti d¨ont´eshoz´ o – a rakt´ ar – felel˝ os a k¨ ul¨onb¨oz˝o id˝opontokban ´erkez˝o anyagok verseng˝o feladatok k¨oz¨otti eloszt´ as´ a´ert. Mivel a rakt´ ar nem ismeri a hat´arid˝oket, a mechanizmustervez´est alkalmazzuk ¨on´erdekk¨ovet˝o projekt ´agenseket felt´etelezve. A c´el a maxim´alis k´es´es minimaliz´al´asa az anyagok rendelkez´esre ´all´as´ ab´ ol ad´ od´ o ´es a megel˝ oz´esi korl´atok betart´asa mellet. Felt´etelezz¨ uk, hogy a hat´arid˝ok¨on k´ıv¨ ul a rakt´ar ismeri a probl´ema ¨ osszes t¨ obbi param´eter´et. Gyakorlati okokb´ol p´enz¨ ugyi tranzakci´okat nem enged¨ unk meg, ami kiz´ arja az olyan elterjedt ´altal´anos mechanizmusok alkalmaz´as´at, mint a Vickrey – Clarke – Groves. Az el˝oad´as egy polinomi´ alis fut´ asidej˝ uu ´j u ´.n. soros diktat´orikus mechanizmust (Serial Dictatorship Mechanism, SDM) mutat be az anyageloszt´ asra. A mechanizmus mind ˝oszinte (truthful), mind Paretooptim´alis, ´ıgy a lehets´eges sorrendek feletti randomiz´al´as univerz´alisan ˝oszinte Pareto-optim´alis v´eletlen´ıtett mechanizmust eredm´enyez. Azonban bemutatjuk, hogy n´eh´any hozz´arendel´esi probl´em´aval ellent´etben nem minden Pareto-optim´ alis megold´as ´all´ıthat´o el˝o SDM alkalmaz´as´aval. R´aad´asul korl´at sem adhat´o a kapott megold´ as c´elf¨ uggv´eny´enek elt´er´es´ere a lehet˝o legkisebb k´es´est˝ol, ´ıgy a mechanizmus hat´ekonys´ag´at k´ıs´erleti u ´ton vizsg´ aljuk.
17
¨ Osszefoglalva, az el˝ oad´ asban egy gyakorlatilag fontos u ¨temez´esi probl´em´at vizsg´alunk ´es bemutatunk egy u ´jfajta anyageloszt´ o mechanizmust, ami kik¨ usz¨ob¨oli a moh´o anyagig´enyl´esekb˝ol ered˝o hat´ekonys´agveszt´est. Bizony´ıtjuk a kapott megold´ as Pareto-optimalit´as´at, ami a leggyakrabban haszn´alt sz¨ uks´eges krit´erium egy elfogadhat´ o megold´ assal szemben. A kutat´ast a K112881 sz´ am´ u Orsz´ agos Tudom´anyos Kutat´asi Alapprogramok (OTKA), valamint a GINOP-2.3.2-15-2016-00002 t´amogat´ asok tett´ek lehet˝ov´e.
F´ abi´ an Csaba Informatika Tansz´ek, GAMF Kar, Pallasz Ath´en´e Egyetem
Csizm´ as Edit Informatika Tansz´ek, GAMF Kar, Pallasz Ath´en´e Egyetem
Drenyovszki Rajmund Informatika Tansz´ek, GAMF Kar, Pallasz Ath´en´e Egyetem
Wim van Ackooij EDF Research and Development, OSIRIS
Vajnai Tibor Informatika Tansz´ek, GAMF Kar, Pallasz Ath´en´e Egyetem
Kov´ acs L´ or´ ant Informatika Tansz´ek, GAMF Kar, Pallasz Ath´en´e Egyetem
Sz´ antai Tam´ as Differenci´ alegyenletek Tansz´ek, Matematikai Int´ezet, Budapesti M˝ uszaki ´es K¨ ozgazdas´ agtudom´ anyi Egyetem
Val´ osz´ın˝ us´ eg-maximaliz´ al´ as bels˝ o k¨ ozel´ıt´ essel A javasolt bels˝ o k¨ ozel´ıt´es a p-efficiens pontok egy v´altozat´an alapszik. – A p-efficiens pontokat Pr´ekopa Andr´as vezette be, u ´j ir´ anyt mutatva a val´ osz´ın˝ us´egi korl´atos feladatok megold´as´ara. Elj´ar´asunk k¨ onnyen implement´ alhat´ o ´es nem ´erz´ekeny a gradiens-sz´am´ıt´as hib´aira. Egyszer˝ u implement´aci´onk a kezdeti k´ıs´erletek sor´ an robusztusnak bizonyult.
18
Fleiner Tam´ as Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem
Mire j´ ok a stabil p´ aros´ıt´ asok? A stabil p´aros´ıt´ asok t¨ ort´enete 1962-ben kezd˝odik, amikoris Gale ´es Shapley a l´anyk´er˝o algoritmus seg´ıts´eg´evel demonstr´ alt´ ak egyfel˝ ol, hogy egy, a val´os´agt´ol nem teljesen elrugaszkodott modellben mindig lehets´eges stabil m´odon ¨ osszeh´ azas´ıtani n f´erfit ´es n n˝ot, m´asfel˝ol azt, hogy egy matematikai levezet´es elmondhat´o ak´ ar h´etk¨ oznapi nyelven, mindenf´ele obskurus kalkul´aci´o ´es h´okuszp´okusz n´elk¨ ul is. Ezt k¨ovet˝oen Roth mutatott r´ a arra, hogy l´enyeg´eben Gale ´es Shapley eredm´eny´en m´ ulik az USA-ban az ’50-es ´evekt˝ol alkalmazott, k¨ ozpontos´ıtott rezidensprogram azon sikere, hogy az egyes k´orh´azak nem pr´ob´alj´ak a t¨obbiek el˝ol megszerezni a leg´ıg´eretesebb medikushallgat´okat. A jelen el˝oad´asban m´eg kor´abbra vezetj¨ uk vissza a stabil p´aros´ıt´ asok eredet´et: az der¨ ul ki, hogy Knaster ´es Tarski egy sokszor hib´asan az ut´obbi szerz˝onek tulajdon´ıtott fixpontt´etele dolgozik a h´att´erben. Stabil p´aros´ıt´ asokkal kapcsolatban sz´amos ´eredekes elm´eleti ´es gyakorlati jelent˝os´eg˝ u eredm´eny sz¨ uletett. Siker¨ ult megadni a stabil p´aros´ıt´ as poli´eder line´aris le´ır´as´at, Galvin igazolta a Dinitz-sejt´est, diszjunkt utakkal, illetve r´eszbenrendez´esek k¨ oz¨os antil´ancaival kapcsolatos eredm´enyek l´attak napvil´agot. A gyakorlatban az egyetemi (illetve a k¨ oz´ep- ´es ´altal´anos iskolai) felv´eteli elj´ar´asok sor´an vagy az ´el˝odonoros vesetranszplant´ aci´ ok lehet˝ os´eg´et kit´ar´o vesecsereprogramokban kap n´elk¨ ul¨ozhetetlen szerepet a stabil p´aros´ıt´ as keres´ese. A legut´ obbi id˝ okben k¨ ul¨on¨osen felgyorsultak az ezir´any´ u kutat´asok annak nyom´an, hogy idev´ ag´ o munk´ ass´ aguk elismer´esek´epp 2012-ben Roth ´es Shapley kapt´ak a k¨ozgazdas´agi Nobel-eml´ekd´ıjat. A jelen el˝ oad´ as c´elja, hogy err˝ol a gyorsan fejl˝od˝o ter¨ uletr˝ol n´eh´any olyan eredm´enyt mutasson be, amely szorosan kapcsol´ odik ahhoz az u ´jszer˝ u szeml´elethez, amely a stabil p´aros´ıt´asok a fixpontt´etelre ´es gr´afokra alapozott megk¨ ozel´ıt´es´eb˝ol sz´armazik.
Fleiner Tam´ as3 Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem
Jank´ o Zsuzsanna4 Budapesti Corvinus Egyetem
Akihisa Tamura5 Keio University
Alexander Teytelboym University of Oxford, Institute for New Economic Thinking at the Oxford Martin School
Keresked´ esi rendszerek k´ etoldal´ u szerz˝ od´ esekkel Keresked´esi rendszereket modellez¨ unk egy ir´any´ıtott gr´affal, ahol a cs´ ucsok a c´egek, az ´elek a lehet´ s´eges keresked´esek. Elek valamely r´eszhalmaz´at kimenetelnek nevezz¨ uk, ezek azok az ´elek, amelyeken megval´osul a keresked´es. ´ Altal´ anos´ıtjuk Ostrovsky modellj´et, ahol ez a gr´af aciklikus (azaz ell´ at´ asi l´ ancr´ ol van sz´o) ´es minden r´esztvev˝onek van egy teljesen komonoton kiv´alaszt´asi f¨ uggv´enye. A mi modell¨ unkben kiv´alaszt´asi f¨ uggv´ennyel adottak a preferenci´ ak, de a rendszer tartalmazhat ir´any´ıtott k¨or¨oket. Bevezetj¨ uk a s´etastabilit´as ´es a teljes s´eta-stabilit´ as fogalm´ at, ´es megmutatjuk, hogy mindig tal´alhat´o s´eta-stabil illetve teljesen s´eta-stabil kimenetel, felt´eve, hogy minden c´eg kiv´alaszt´asi f¨ uggv´enye teljesen komonoton. Hatfield ´es Kominers a halmaz-stabil rendszereket vizsg´alt´ak, ahol eddig nem megval´osult keresked´esek b´armely halmaza blokkolhatja a jelenlegi kimenetelt. A halmaz-stabil megold´as l´etez´ese nem 3 A kutat´ ast az OTKA K108383 p´ aly´ azat ´ es az MTA-ELTE Egerv´ ary Kutat´ ocsoport t´ amogatta. A kutat´ as egy r´ esze k´ et munkal´ atogat´ as alatt t¨ ort´ ent a Keio Egyetemen. 4 A kutat´ ast az OTKA K109240 p´ aly´ azat ´ es az MTA-ELTE Egerv´ ary Kutat´ ocsoport t´ amogatta. 5 A kutat´ ast a Grants-in-Aid for Scientific Research (B) from JSPS t´ amogatta.
19
garant´alt. Megmutatjuk, hogy egy megadott kimenetelr˝ol NP-neh´ez eld¨onteni, hogy halmaz-stabil-e. A s´eta-stabilit´as definici´ oj´ aban blokkol´ o s´et´akat keres¨ unk, amelyben sorra minden szerepl˝o elfogadn´a a neki felaj´anlott u ´j szerz˝ od´eseket, megengedve, hogy ek¨ozben eldob n´eh´any r´egebbit. A teljesen s´eta-stabil kimenetelek nem¨ ures h´al´ot alkotnak a v´egs˝o elad´ok ´es v´egs˝o vev˝ok (forr´asok ´es nyel˝ok) preferenci´ aira n´ezve. Megmutatjuk a vid´eki k´ orh´ az t´etel erre a rendszerre val´o ´altal´anos´ıt´as´at, strat´egia-biztoss´ agot, ´es hogy mik´epp v´ altozik megy a vev˝o-, illetve elad´o-optim´alis kimenetel, ha egy u ´j v´egs˝o vev˝o l´ep be a piacra. Adunk egy felt´etelt, amely mellett a s´eta-stabilit´as ´es a teljes s´eta-stabilit´as ekvivalens, majd ¨ osszevetj¨ uk ˝oket m´as lehets´eges stabilit´asi definici´okkal is.
Forg´ o Ferenc BCE
Pontos k´ enyszer´ıt´ esi ´ ert´ ekek az n-szem´ elyes, k´ etkiszolg´ al´ os, egyszer˝ u line´ aris torl´ od´ asi j´ at´ ekokra Az n-szem´elyes, k´etkiszolg´ al´ os, egyszer˝ u line´aris torl´od´asi j´at´ekok n´egy oszt´aly´at (cs¨okken˝o/cs¨okken˝o, n¨ovekv˝o/n¨ovekv˝ o, cs¨ okken˝ o/n¨ ovekv˝ o, n¨ ovekv˝o/cs¨okken˝o) vizsg´aljuk abb´ol a szempontb´ol, hogy menynyire k´epes a puha korrel´ alt egyens´ uly (Forg´o (2010), A generalization of correlated equilibrium: A new protocol, Mathematical Social Sciences, 60:186–190) ´altal biztos´ıtott t´arsadalmi hasznoss´ag megk¨ozel´ıteni a t´arsadalmi hasznoss´ ag abszol´ ut maximum´at. Erre a c´elra a k´enyszer´ıt´esi ´ert´ek m´er˝osz´am´at (Ashlagi et al. (2008), On the value of correlation, Journal of Artificial Intelligence, 33:575–613) haszn´aljuk. A vizsg´ alt j´ at´ekoszt´ alyokra a k´enyszer´ıt´esi ´ert´ek rendre pontosan 9/8, 1, 2 ´es 2. Ezek a j´at´ekoszt´alyok tartalmazz´ ak az n-szem´elyes fogolydilemma ´es a gy´ava ny´ ul j´at´ekokat. Mindk´et j´at´ekoszt´alyra a k´enyszer´ıt´esi ´ert´ek 2. Ugyanakkor, ha a gy´ava ny´ ul j´at´ekokra n = 2 (a klasszikus gy´ava ny´ ul j´at´ek) vagy n = 3, akkor a k´enyszer´ıt´esi ´ert´ek 3/2.
Gazdag-T´ oth Bogl´ arka Szegedi Tudom´ anyegyetem
Jos´ e Fern´ andez University of Murcia
MINLP probl´ em´ ak megold´ asa intervallumos B&B m´ odszerrel Az intervallumos korl´ atoz´ as ´es sz´etv´ alaszt´ as (Branch-and-Bound, B&B) m´odszer´et els˝osorban nemkonvex nemline´aris feladatok megb´ızhat´ o megold´as´ara haszn´aljuk. Az intervallum aritmetika seg´ıts´eg´evel b´armely z´art k´eplettel megadott folytonos f¨ uggv´enyhez k¨onnyen sz´am´ıthatunk als´o ´es fels˝o korl´atokat, illetve differenci´ alhat´ o f¨ uggv´enyek eset´en automatikus differenci´al´assal gradiens befoglal´ast, els˝orend˝ u Taylor form´at is k¨ onnyed´en ´es automatikusan sz´am´ıthatunk. Az intervallumos B&B m´ odszer j´o tulajdons´aga, hogy nem ´erz´ekeny a kerek´ıt´esi hib´akra, ´es t¨obb lok´alis optimum eset´en is megtal´ alja a glob´ alis optimumot, aminek egy sz˝ uk befoglal´as´at adja eredm´eny¨ ul. H´atr´anya viszont, hogy csak kis v´altoz´ osz´ am´ u probl´em´akra alkalmazhat´o. A nemkonvex nemline´ aris programoz´ asi feladatokat tov´abb nehez´ıti, ha m´eg eg´esz´ert´ek˝ us´egi felt´etelek is adottak egyes v´ altoz´ okhoz, ´es ´ıgy vegyes eg´esz´ert´ek˝ u nemline´aris programoz´asi (MINLP) probl´em´akat kapunk. Az el˝ oad´ ason megvizsg´ aljuk hogyan lehet az intervallumos B&B m´odszert az u ´j felt´etelekhez igaz´ıtani, miben v´altoznak a kiv´ ag´ asi tesztek, feloszt´asi, kiv´alaszt´asi szab´alyok stb.
20
Az algoritmust egy v´ allalatelhelyez´esi probl´em´an mutatatjuk be, ahol folytonos koordin´at´aj´ u de eg´esz´ert´ek˝ u min˝ os´eg v´ altoz´ oval adott az u ´j v´allalat, illetve a l´etez˝o v´allalatok min˝os´egei is eg´esz´ert´ek˝ u v´altoz´oi lesznek a feladatnak. A kutat´ast a Nemzeti Kutat´ asi, Fejleszt´esi ´es Innov´aci´os Hivatal (NKFIH – PD115554 p´aly´azat) t´amogatja.
Gerencs´ er L´ aszl´ o MTA SZTAKI
Az alkalmazott matematika helye a multidiszciplin´ aris kutat´ asban, fejleszt´ esben ´ es innov´ aci´ oban Nyitott k´ erd´ esek a sztochasztikus programoz´ asban Az el˝oad´asban Pr´ekopa Andr´ as n´eh´ any gondolat´at az alkalmazott matematika ´es m´as tudom´any´agak t´agabb kontextus´ aba helyezve id´ezz¨ uk fel, a ma ´el˝o magyar tudom´anyoss´ag n´eh´any kiemelked˝o eredm´eny´et is felvillantva. Konkr´et p´eldak´ent bemutatjuk a sztochasztikus programoz´as egy alapfeladat´anak a megold´asi k´ıs´erleteit, amelyek v´egs˝ o soron m´aig megoldatlan m´ely, a Fields Medal-os Martin Hairer-t is megihlet˝o matematikai k´erd´esekre vezetnek.
Gerencs´ er L´ aszl´ o MTA SZTAKI
Er˝ oss Lor´ and Orsz´ agos Klinikai Idegtudom´ anyi Int´ezet (OKITI)
Fab´ o D´ aniel Orsz´ agos Klinikai Idegtudom´ anyi Int´ezet (OKITI)
Perczel Gy¨ orgy PPKE ITK, OKITI
V´ ag´ o Zsuzsanna PPKE ITK
Pontfolyamatok statisztikai elemz´ ese ´ es alkalmaz´ asuk az epilepszia kutat´ asban Az epilepszia az idegrendszer egy nem ritka betegs´ege, amely a popul´aci´o mintegy 1%-´at ´erinti. Az epilepszia az egy´ebk´ent kit˝ un˝ o eg´eszs´egnek ¨ orvend˝o beteg ´eletvitel´et jelent˝osen korl´atozza. Az epilepszi´as betegek kb. 70%-a gy´ogyszeresen kezelhet˝ o, a gy´ogyszeresen nem kezelhet˝o betegek hagyom´anyos ter´api´aja az agy ´erintett ter¨ ulet´enek seb´eszi elt´ avol´ıt´asa. A fentiek mellett a ter´apia egy u ´j ir´anya az epilepszi´as rohamra jellemz˝ o agyi aktivit´ as semleges´ıt´ese neuro-modul´aci´os beavatkoz´assal. Ennek az eszk¨oze egy seb´eszi u ´ton be¨ ultetett impl´ antum, amely az agyat k´epes stimul´alni, ´es egy hordozhat´o, az impl´antumb´ol kapott EEG jeleket regisztr´ al´ o ´es elemz˝o szenzor, amelynek funkci´oja a rohamok el˝orejelz´ese, ´es a stimul´ator aktiv´ al´ asa.
21
Az el˝oad´asban egy, a szeizmol´ ogi´ aban sz´eles k¨orben elterjedt metodik´at, a szeizmogr´af jeleib˝ol sz´armaztatott pontfolyamatok statisztikai elemz´es´et adapt´aljuk ´es fejlesztj¨ uk tov´abb EEG jelek statisztikai elemz´es´ere. A fiziol´ ogiai h´ att´er alapj´ an indokoltnak t˝ unik a kapott pontfolyamatok dinamik´aj´aban felt´etelezni egy o¨ngerjeszt˝ o mechanizmust, ily m´odon a statisztikai irodalomban r´eg´ota ismert u ´n. Hawkes folyamatok oszt´ aly´ ahoz jutunk. Ezek illeszt´es´evel, illetve v´altoz´as detekt´al´as´aval kapcsolatban fogalmazunk meg orvosilag is indokolhat´ o u ´jszer˝ u, statisztikai k´erd´eseket ´es eredm´enyeket. Mindezek alapj´an rem´elhet˝o, hogy a roham el˝ orejelz´es mai napig rem´enytelen¨ ul neh´eznek tartott probl´em´aj´aban ´erdemi el˝orel´ep´est siker¨ ul el´erni. Hivatkoz´ asok [1] A. G. Hawkes, Spectra of some self-exciting and mutually exciting point processes, Biometrika, Vol. 58 (1971), 83–90. [2] T. Ozaki, Maximum likelihood estimation of Hawkes self-exciting point processes, Ann. Inst. Stat. Math., Vol. 31 (1979), pp. 145–155.
Hajdu L´ aszl´ o SZTE-TTIK
Kr´ esz Mikl´ os SZTE-JGYPK
T´ oth L´ aszl´ o SZTE-TTIK
Optimaliz´ al´ asi probl´ em´ ak h´ al´ ozatokon defini´ alt ´ altal´ anos´ıtott diff´ uzi´ os modellekben Az ir´any´ıtott gr´afokkal reprezent´ alt h´al´ ozatokon terjed˝o fert˝oz´esek, v´ırusdinamik´ak vizsg´alata klasszikus ter¨ ulet az orvostudom´ anyban, azonban az ut´obbi ´evekben a modellek u ¨zleti ´eletben val´o alkalmaz´asa is el˝ot´erbe ker¨ ult. Munk´ ank sor´ an diff´ uzi´ os modelleket haszn´alunk, ezek a h´al´ozati hat´as eredm´enyek´ent megadj´ak, hogy mik´ent n¨ ovekszik a megadott tulajdons´aggal rendelkez˝o (azaz fert˝oz¨ott) egyedek sz´ama. Ezen modellre defini´ alhat´ o egy optimaliz´al´asi feladat, melynek c´elja adott m´eret˝ u cs´ ucshalmazok k¨oz¨ ul kiv´alasztani azon halmazt, amely a maxim´alis fert˝oz¨otts´eget biztos´ıtja a h´al´ozatban [1]. Ennek meghat´aroz´asa NP-teljes probl´ema, azonban bizony´ıt´asra ker¨ ult, hogy ha a fert˝oz´es terjed´ese az u ´n. triggerel´esi modell szerint t¨ ort´enik, akkor moh´o heurisztik´aval mintegy 63%-os approxim´aci´os korl´at biztos´ıthat´o [1]. Triggerel´esi modellr˝ ol akkor besz´el¨ unk, ha minden cs´ ucsra egy adott szab´aly szerint defini´alt a cs´ ucs bej¨ ov˝ o szomsz´edjainak egy u ´n. triggerel´esi halmaza, ´es a diff´ uzi´ot meghat´aroz´o f¨ uggv´eny abban az esetben rendel fert˝ oz´est a cs´ ucshoz, ha a triggerel´esi halmaza tartalmaz kor´abban fert˝oz¨ott elemet [1]. A fenti modell csak a fert˝ oz¨ otts´eg megl´et´et/hi´any´at k´epes kezelni, azonban a gyakorlati ´elet k´erd´eseire ez nem elegend˝ oen realisztikus. Az alkalmaz´asokn´al val´oj´aban egy kezdeti (apriori) fert˝oz¨otts´egi val´osz´ın˝ us´egr˝ol besz´elhet¨ unk minden cs´ ucsn´ al, amely a diff´ uzi´os folyamat v´eg´en egy eredm´eny (apos´ teriori) val´osz´ın˝ us´eget ad outputk´ent [2]. Ez az Altal´ anos´ıtott Diff´ uzi´os Modell, amelyre ´altal´anos´ıtottuk a fert˝oz´es maximaliz´ al´ asi feladatot, ´es bizony´ıtottuk, hogy a moh´o heurisztika a triggerel´esi modell eset´eben szint´en biztos´ıtja a 63%-os approxim´aci´os korl´atot. A moh´o elj´ar´as hat´ekonys´aga n¨ovelhet˝o, ha valamilyen ki´ert´ekel´esi szempont szerint az egyes iter´aci´okat csak a cs´ ucsok egy r´eszhalmaz´an futtatjuk, ilyen m´ odon reduk´ alva a keres´esi teret. T¨obb elj´ar´ast kidolgoztunk a fenti c´elb´ol, t¨obbek k¨oz¨ott a cs´ ucsok foksz´ama szerinti vagy az ´atfed˝ o k¨ oz¨oss´egekben bet¨olt¨ott szerep szerinti redukci´ot.
22
M´odszereinket keretrendszerbe foglaltuk, ebben k¨ ul¨onb¨oz˝o triggerel´esi modellek defini´alhat´ok, valamint sz´amos redukci´ os m´ odszer k¨ oz¨ ul v´ alaszthatunk. A moh´o heurisztika mellett a szimul´alt h˝ ut´es m´odszere is alkalmazhat´ o alternat´ıv elj´ ar´ ask´ent. A keretrendszer haszn´alat´aval a k¨ ul¨onb¨oz˝o heurisztik´a´ kat r´eszletes tesztek keret´eben o anos´ıtott F¨ uggetlen Kaszk´ad ¨sszehasonl´ıtottuk, az eredm´enyeket az Altal´ Modellj´en illusztr´ aljuk. Jelen kutat´ ast a Nemzeti Kutat´ asi, Fejleszt´esi ´es Innov´aci´os Hivatal SNN-117879 sz. p´aly´azat´aval t´amogatta. Hivatkoz´ asok [1] D. Kempe, J. Kleinberg and E. Tardos, Maximizing the spread of influence through a social network, in: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, pp. 137–146, New York, NY, USA, 2003. ACM. [2] A. B´ ota, M. Kr´esz, A. Pluh´ ar, Approximations of the generalized cascade model, Acta Cybernetica, 21, pp. 37–51, 2013.
Heged˝ us Csaba Pannon Egyetem, Kvantitat´ıv M´ odszerek Int´ezeti Tansz´ek
Koszty´ an Zsolt Tibor Pannon Egyetem, Kvantitat´ıv M´ odszerek Int´ezeti Tansz´ek
M´ atrix-alap´ u projektkock´ azat-menedzsment A kutat´as c´elja, hogy kvantitat´ıv m´ odszerekkel modellezze ´es elemezze a projekt siker´et ´es kock´azatait. A javasolt ´agens-alap´ u m´odszerek modellezik a hagyom´anyos, az agilis ´es a hibrid projekt menedzsment megk¨ozel´ıt´esek m˝ uk¨ od´es´et, mik¨ ozben az ´altalunk javasolt kock´azati keretrendszer seg´ıts´eg´evel szimul´aljuk az id˝o/k¨olts´eg ´es min˝ os´egi param´eterek v´altoz´as´an fel¨ ul a vev˝oi ig´enyek megv´altoz´as´anak hat´as´at is. El˝oad´asunkban r´eszletesen ismertetj¨ uk, hogy ´agens-alap´ u m´odszerekkel milyen m´odon lehet modellezni a k¨ ul¨onb¨oz˝ o projektmenedzsment megk¨ozel´ıt´eseket. Ismertetj¨ uk, hogy milyen m´odon lehet ´ert´ekelni szimul´aci´os eszk¨ oz¨ okkel a v´egrehajt´ as sikeress´eg´et, valamint a projekttervek kock´azati kitetts´eg´et. ´ v´elj¨ Ugy uk, hogy a javasolt keretrendszer hasznos eleme lehet egy projektkock´azat-´ert´ekel˝o d¨ont´est´amogat´o rendszernek. ¨ ond´ıja ´es az Emberi Er˝oA kutat´ast a Magyar Tudom´ anyos Akad´emia Bolyai J´anos Kutat´asi Oszt¨ ´ Nemzeti Kiv´ ´ forr´as Miniszt´erium Uj al´ os´ ag Programja (UNKP-PD-16) t´amogatta.
Heitler Krisztina Szegedi Tudom´ anyegyetem, K¨ ozgazdas´ agtudom´ anyi Doktori Iskola
Hat´ ekonys´ agelemz´ es az eg´ eszs´ egu ¨ gyben Napjainkban sokat vitatott k´erd´es a magyar eg´eszs´eg¨ ugy hat´ekonys´aga. A k¨ uls˝o szeml´el˝o javar´eszt forr´ashi´anyos betegell´ at´ ast, m´ıg a bels˝ o r´esztvev˝o sokszor pazarl´o k¨oltekez´est tapasztal. Az egyik k´orh´az meg tudja teremteni az eur´ opai sz´ınvonalhoz k¨ozeli ell´at´ast modern m˝ uszerei ´es maxim´alisan felszerelt oszt´alyai seg´ıts´eg´evel, m´ıg m´ ashol a beteg´etkeztet´es is nagy gondokat jelent, nem besz´elve az elavult infrastrukt´ ur´ar´ol. Nincs ez m´ask´ent a Semmelweis Egyetem klinik´ai k¨or´eben sem. Az egyik klinika pazarul felszerelt, m´ıg a m´asik a fennmarad´ as´ert k¨ uzd. Jelen tanulm´annyal a szerz˝o arra v´allalkozik, hogy ezen int´ezm´enyek 23
k¨or´eben hat´ekonys´ agi elemz´est hajtson v´egre. A t´em´aval foglalkoz´o sz´amos szakirodalom ´attanulm´anyoz´as´at k¨ovet˝oen a legalkalmasabb elemz´esi m´odszernek a DEA anal´ızis bizonyult. A Data Evelopment Analysis (DEA) egy szil´ard matematikai h´att´errel rendelkez˝o nem param´eteres determinisztikus elj´ ar´ as. Seg´ıts´eg´evel egyes gazdas´agi egys´egeket (jelen esetben klinik´ak) lehet a hat´ekonys´ag ´ert´ekeinek meghat´ aroz´ as´ aval egym´ ashoz viszony´ıtani. Kiv´alaszt´asra ker¨ ulnek azon d¨ont´eshoz´o egys´egek (Desicion Making Unit, DMU), amelyek az output/input ar´any szempontj´ab´ol a leghat´ekonyabbak, s a t¨ obbit ezen egys´egekhez viszony´ıtja. Mindezek alapj´ an az elemz´es sor´ an meghat´aroz´asra ker¨ ulnek a klinik´ak k¨ ul¨onb¨oz˝o inputjai, mint pl. az akt´ıv k´orh´azi ´agysz´ am, vagy az orvosok, szakdolgoz´o sz´ama. Output v´altoz´ok´ent figyelembe vehet˝o a HBCS (Homog´en Betegs´egcsoportok) s´ ulysz´amai, illetve esetsz´amai. Ezen sz´amok a klinik´ak bev´eteleit hat´arozz´ak meg. A vizsg´ alat eredm´enyek´ent a legjobb hat´ekonys´ag´ u klinika a tov´abbiakban p´eldak´ent szolg´alhat a t¨obbi szervezeti egys´eg m˝ uk¨ od´es´eben ( best practise”). ” Haz´ankban a DEA m´odszert els˝ ok´ent 2010-ben D´ozsa Csaba alkalmazta, megyei ´es v´arosi k´orh´azakra vonatkoz´oan. Ezt k¨ ovet˝ oen is csak ritk´an tal´alkozhatunk az eg´eszs´eg¨ ugyi int´ezm´enyek ilyenfajta ¨osszehasonl´ıt´as´aval, annak ellen´ere, hogy tiszt´aban vagyunk azzal, hogy a rendszerben v´altoz´asra (v´altoz´ tat´asra) lenne sz¨ uks´eg. Eppen ez´ert jelen munka egyfajta u ´tmutat´onak is tekinthet˝o j´o n´eh´any int´ezm´eny vezet˝oje sz´am´ara. Kulcsszavak: Eg´eszs´eg¨ ugy, hat´ekonys´ ag, DEA elemz´es, input, output, DMU.
Horv´ ath Mark´ o MTA SZTAKI
Kis Tam´ as MTA SZTAKI
Poli´ ederes eredm´ enyek projekt u esi feladatokra ¨ temez´ Az er˝oforr´as-korl´atos projekt u ¨temez´esi feladatban adott tev´ekenys´egek id˝obeli v´egrehajt´as´at kell meghat´arozni u ´gy, hogy a tev´ekenys´egek a v´egrehajt´asuk sor´an felhaszn´alnak bizonyos mennyis´eget egy vagy t¨obb, limit´altan el´erhet˝ o (meg´ ujul´ o vagy nemmeg´ ujul´o) er˝oforr´asb´ol. Az el˝oad´ason egy esem´eny-alap´ u megk¨ ozel´ıt´est ismertet¨ unk, ahol az n tev´ekenys´eghez 2n esem´eny tartozik, ´es minden esem´eny egy tev´ekenys´eg kezdet´et vagy befejez´es´et jelenti. Modell¨ unkben minden tev´ekenys´eg-esem´eny p´ arhoz k´et bin´ aris v´ altoz´ot haszn´alunk azt jel¨olve, hogy az adott esem´enyt az adott tev´ekenys´eghez rendelj¨ uk-e mint kezdeti illetve befejez´esi esem´eny. Bemutatjuk poli´ederes eredm´enyeinket, melyek a megengedett hozz´ arendel´eseket (minden tev´ekenys´eghez pontosan egy kezd´esi ´es pontosan egy befejez´esi esem´enyt rendel¨ unk; a kezd´esi esem´eny megel˝ozi a befejez´esi esem´enyt; minden esem´enyt pontosan egy tev´ekenys´eghez rendel¨ unk) le´ır´ o pontok konvex burk´ara vonatkoznak. A kutat´as az OTKA K112881 ´es GINOP-2.3.2-15-2016-00002 projektek t´amogat´as´aval j¨ott l´etre.
Hujter Mih´ aly BME Matematika Int´ezet
Mely merev k¨ or˝ u gr´ afok ´ es hogyan haszn´ alhat´ ok val´ osz´ın˝ us´ egi becsl´ esekhez? A merev k¨or˝ u gr´ afok vizsg´ alat´ at Haj´os Gy¨ orgy, Gallai Tibor, Sur´anyi J´anos, Hajnal Andr´as kezdt´ek el. A val´osz´ın˝ us´egi becsl´esek tanulm´ anyoz´ asa Pr´ekopa Andr´as ´es tan´ıtv´anyai munk´aiban ´el´enk¨ ult fel. Boros ´es Veneziani, illetve t˝ ol¨ uk f¨ uggetlen¨ ul Dohmen r´atal´altak arra a fontos kapcsolatra, mely a merev k¨or˝ u gr´afok ´es az esem´eny´ uni´ ok val´ osz´ın˝ us´eg´enek fels˝o becsl´ese k¨oz¨ott van. 24
El˝oad´asunkban r¨ oviden ´attekintj¨ uk a fent idezett eredm´enyek t¨ort´enet´et. R´amutatunk majd, hogy a leghasznosabb merev k¨ or˝ u gr´ afok tulajdons´againak felt´ar´asa mennyire indokolt. A merev k¨or˝ u gr´afok sz´ınez´eseinek k´erd´esk¨ or´et is ´erinteni fogjuk.
Ill´ es Tibor BME DET
Farkas lemm´ at´ ol az EP-t´ etelekig Farkas Gyula 2017. m´ arcius 28-´an lenne 170 ´eves, ha ember meg´erhetne ilyen kort. Legh´ıresebb n´emetnyelv˝ u, matematika cikk´et 1901-ben publik´alta. Annak ellen´ere, hogy a Farkas lemm´anak nem ez az els˝o n´emetnyelv˝ u publik´ aci´ oja, m´egis ez alapj´an v´alt ismertt´e, – kicsit megk´esve, – a nemzetk¨ozi matematikus k¨ oz¨ oss´eg sz´ am´ ara, Kuhn ´es Tucker (1951) nemline´aris programoz´asr´ol ´ırt alapm˝ uv´eb˝ol. Farkas Gyula munk´ ass´ aga ´es h´ıress´e v´ alt lemm´aja, a XIX. sz´azad v´eg´en ´es a XX. sz´azad elej´en nem csak magyar matematikusokra (Ha´ ar, Neumann, Riesz) volt hat´assal, hanem nemzetk¨ozi matematikai ´elet vezet˝o szem´elyis´egeire is (pl. Minkowski). Az el˝oad´asom c´elja, els˝ osorban a line´ aris alternat´ıva t´etelek konstrukt´ıv bizony´ıt´asi m´odszereinek a nyomon k¨ovet´ese az elm´ ult ´evtizedekben a szimplex m´odszer megjelen´es´et˝ol. M´asfel˝ol fontosnak tartom a line´aris alternat´ıva t´etelek n´eh´ any fontos alkalmaz´as´anak ´es ´altal´anos´ıt´as´anak a kiemel´es´et. Term´eszetesen kit´erek Farkas lemma n´eh´any el˝ozm´eny´ere is. Az el˝oad´asom ink´ abb egy szubjekt´ıv gondolatsor a line´aris alternat´ıva t´etelekr˝ol, mint egy mindenre kiterjed˝o, r´eszletes o sszegz´ ese a t´emak¨ ornek. ¨
K´ annai Zolt´ an Budapesti Corvinus Egyetem, Matematika tansz´ek
Szab´ o Imre Budapesti Corvinus Egyetem, Matematika tansz´ek
Tallos P´ eter Budapesti Corvinus Egyetem, Matematika tansz´ek
Nemkonvex ir´ any´ıt´ asi feladatok Optim´alis ir´any´ıt´ asi feladatok egzisztencia k´erd´esein´el a szakirodalom t´ ulnyom´o r´esz´eben a konvexit´as fontos szerepet j´atszik. Az al´abbiakban nemkonvex probl´em´ak egy ´erdekes oszt´aly´ara igazoljuk az optim´alis ir´any´ıt´as l´etez´es´et differenci´ altartalmaz´asok technik´aj´anak felhaszn´al´as´aval. Mathematics Subject Classifications: 34A60, 49K15, 93D15
Tekints¨ uk a k¨ ovetkez˝ o egyszer˝ u alak´ u optim´alis ir´any´ıt´asi feladatot: ∫ T ( ) H(x, u) = h x(t), u(t) dt → min 0
(1)
x′ (t) = u(t), u(t) ∈ K
x(0) = x0
majdnem minden¨ utt.
A Pontrjagin-f´ele maximumelv (l´ asd K´ annai, Szab´o ´es Tallos (2014)) sz¨ uks´eges felt´etelt fogalmaz meg az optim´alis u ir´ any´ıt´ asra, de semmilyen t´ ampontot nem ad arra, hogy val´oban l´etezik-e optim´alis ir´a´ ny´ıt´as. Altal´ aban az egzisztencia k´erd´ese csak igen m´ely, a halmaz´ert´ek˝ u anal´ızisen alapul´o technik´aval 25
kezelhet˝o, ´es a szakirodalom ´altal´ aban konvexit´asi felt´eteleket alkalmaz a feladatban szerepl˝o f¨ uggv´enyekre. Itt utalunk p´eld´ aul Rockafellar (1976) ´attekint˝o munk´aj´ara, vagy Aubin ´es Frankowska (1990) eredm´enyeire. Az al´abbi dolgozatban megmutatjuk, hogy a differenci´altartalmaz´asok technik´aj´anak alkalmaz´as´aval optim´alis ir´any´ıt´ asi feladatok egy ´erdekes oszt´aly´ara igazolhatjuk a megold´as l´etez´es´et differenci´alhat´os´agi ´es konvexit´asi felt´etelek felhaszn´ al´ asa n´elk¨ ul.
Kir´ aly Tam´ as ELTE TTK Oper´ aci´ okutat´ asi Tansz´ek
M´ esz´ aros-Karkus Zsuzsa ELTE TTK Oper´ aci´ okutat´ asi Tansz´ek
N´ epszer˝ u´ es er˝ osen n´ epszer˝ u p´ aros´ıt´ asok A n´epszer˝ u p´aros´ıt´ as fogalm´ at G¨ ardenfors vezette be 1975-ben, a stabil p´aros´ıt´asok kiterjeszt´esek´ent. Adott egy gr´af, ´es minden cs´ ucsn´ al egy r´eszbenrendez´es a r´a illeszked˝o ´eleken. K´et p´aros´ıt´ast u ´gy hasonl´ıtunk ¨ossze, hogy minden egyes cs´ ucsn´ al ¨osszevetj¨ uk a r´a illeszked˝o p´aros´ıt´as-´eleket (ha az egyik p´aros´ıt´as nem fedi a cs´ ucsot, akkor a m´asik a prefer´alt), ´es ¨osszes´ıtj¨ uk a cs´ ucsok szavazatait. Amelyik p´aros´ıt´as t¨obb szavazatot kap, az a n´epszer˝ ubb. Ez a p´aronk´enti ¨osszehasonl´ıt´as nem ad felt´etlen¨ ul tranzit´ıv rel´aci´ot, teh´ at lehet, hogy M1 n´epszer˝ ubb mint M2 , M2 n´epszer˝ ubb mint M3 , ´es M3 n´epszer˝ ubb mint M1 . Egy p´ aros´ıt´ as n´epszer˝ u, ha nincs n´ala n´epszer˝ ubb p´aros´ıt´as, ´es er˝ osen n´epszer˝ u, ha minden m´as p´aros´ıt´asn´al n´epszer˝ ubb. Er˝ osen n´epszer˝ u p´aros´ıt´asb´ol nyilv´anval´oan legfeljebb egy lehet. G¨ardenfors megmutatta, hogy ha a cs´ ucsok preferenci´ai line´aris rendez´esek, akkor minden stabil p´aros´ıt´as n´epszer˝ u, ´es minden er˝ osen n´epszer˝ u p´aros´ıt´as stabil. Bir´o, Irwing ´es Manlove tetsz˝oleges preferenci´ak eset´en polinom idej˝ u algoritmust adtak annak eld¨ont´es´ere, hogy egy p´aros´ıt´as n´epszer˝ u illetve er˝osen n´epszer˝ u-e. Sz´ amos tov´ abbi eredm´eny is sz¨ uletett maxim´alis m´eret˝ u illetve maxim´alis s´ uly´ u n´epszer˝ u p´aros´ıt´ asok keres´es´evel kapcsolatban. Az el˝oad´asban besz´elek ezekr˝ol ´es a fennmarad´o nyitott k´erd´esekr˝ ol, valamint elmondok egy M´esz´aros-Karkus Zsuzs´aval k¨oz¨os u ´j eredm´enyt az er˝osen n´epszer˝ u p´aros´ıt´as keres´esi feladatr´ ol.
Kiss Tibor P´ecsi Tudom´ anyegyetem
Egy termel˝ ou okol´ ogiai szempont´ u tervez´ ese ¨ zem ¨ A fenntarthat´os´ ag, er˝ oforr´ as-hat´ekonys´ ag, hullad´ekmentes termel´es fogalmai, megold´asai egyre ink´abb teret nyernek a gondolkod´ asunkban, a politikai ir´anyelvekben ´es a v´allalati strat´egi´akban egyar´ant. Sokf´ele t¨orekv´es ir´ anyul a probl´em´ ak megold´ as´ ara, amelyek mind el˝oremutat´oak, b´ar nem minden esetben k´ın´alnak rendszerszint˝ u megold´ ast. Ebben a tanulm´anyban arra tesz¨ unk k´ıs´erletet, hogy egy termel˝ov´allalat tervez´es´en´el figyelembe vegy¨ uk az ¨ okol´ ogiai rendszerek egyik alapvet˝o m˝ uk¨od´esi elv´et, a rezilienci´at (rugalmass´agot, robosztuss´ agot). Az eredm´enyek azt jelzik, hogy t¨obb, fenntarthat´onak ´ıt´elhet˝o m´odszer k¨oz¨ ul van olyan, amely rendszerszint˝ u, az ¨okol´ogiai rendszerek m˝ uk¨od´esi elveinek is megfelel, ´ıgy nagyobb es´ellyel sz´ am´ıt igaz´ an fenntarthat´ onak.
26
´ Kom´ aromi Eva
Pr´ ekopa Andr´ as: Line´ aris programoz´ as I. A magyar oper´ aci´ okutat´ as megszervez˝ od´ ese: az els˝ o 30 ´ ev A jegyzet a Bolyai J´ anos Matematikai T´arsulat 1967-69 k¨oz¨ott tartott, Az oper´aci´okutat´as matematikai ” m´odszerei” c´ım˝ u posztgradu´ alis kurzus´ ara k´esz¨ ult. Pr´ekopa Andr´as iskola-teremt˝o munk´aj´anak jelent˝os ´allom´asa volt e kurzus, kiindul´o pontja r´eszben az ELTE oper´aci´okutat´asi szakir´anya beind´ıt´as´anak, r´eszben az MTA SZK-ban, majd a SZTAKI-ban l´ev˝o matematikai programoz´assal foglalkoz´o kutat´ocsoportok meger˝os´ıt´es´enek, lend¨ uletet adott a hazai matematikai programoz´asi iskola ´es int´ezm´enyrendszere l´etrej¨ott´enek. El˝ oad´ asomban a jegyzetet mint inspir´aci´ot ´es a Pr´ekopa Andr´as k¨or¨ ul kialakult hazai matematikai programoz´ asi iskol´ at szeretn´em bemutatni.
Koniorczyk M´ aty´ as P´ecsi Tudom´ anyegyetem Term´eszettudom´ anyi Kar, Matematikai ´es Informatikai Int´ezet, Alkalmazott Matematika Tansz´ek
A kvantum korrel´ aci´ ok val´ osz´ın˝ us´ egi geometri´ aj´ ar´ ol A kvantummechanika, a XX. sz´ azad paradigmav´alt´o tudom´anyos elm´elete jelenleg is az ´erdekl˝od´es k¨oz´eppontj´aban ´all, t¨ obbek k¨ ozt az´ert, mert u ´j lehet˝os´egeket nyit meg az inform´aci´ofeldolgoz´as ´es a kommunik´aci´o ter¨ ulet´en. Ez egy u ´j szakter¨ ulet, a kvantuminformatika kialakul´as´ahoz vezetett, amely els˝osorban az er˝os titkos´ıt´ as ´es bizonyos nagy sz´ am´ıt´ asig´eny˝ u probl´em´ ak hat´ekony megold´asa ter¨ ulet´en ´ıg´eretes. Mindezen alkalmaz´ asok egyik f˝o felt´etele a kvantummechanikai ¨osszefon´odotts´ag megl´ete. Ennek fontos megnyilv´anul´ asa, hogy t¨ obb, izol´ alt rendszeren v´egzett m´er´es, megfigyel´es eredm´enyei k¨oz¨ott olyan ugg´eseket tal´ alunk, melyek nem sz´ armaztathat´ok egyetlen k¨oz¨os val´osz´ın˝ us´egi eloszl´asb´ol. Ezen ¨osszef¨ ugg´esek, (sz˝ ukebb ´ertelemben: korrel´ aci´ok) matematikai le´ır´asa a rendszer viselked´es´et jellemz˝o ¨osszef¨ felt´eteles val´osz´ın˝ us´egek ter´eben 0-1 polit´ opokkal, ´es azok bizonyos konvex r´eszhalmazaival (polit´opokkal, illetve szemidefinit programok hierarchi´ aj´aval defini´alt r´eszhalmazokkal) lehets´eges. El˝oad´asomban ´attekintem a t´emak¨ ort, annak m´ara m´ar viszonylag kiterjedt irodalma alapj´an, ´es folyamatban l´ev˝o kutat´ asom egyes r´eszeredm´enyeit mutatom be. Ezek els˝osorban a sz´oban forg´o konvex halmazok szerkezet´enek vizsg´ alat´ aval, illetve a kvantuminformatikai protokollok konkr´et megval´os´ıt´asa eset´en sz¨ uks´eges optimaliz´ aci´ os megfontol´ asokkal kapcsolatosak.
Kopp´ any Kriszti´ an Sz´echenyi Istv´ an Egyetem, Gy˝ or
Mi lenne velu oipar n´ elku ¨ nk az aut´ ¨ l? ´ Agazataink nemzetgazdas´ agi jelent˝ os´ eg´ enek vizsg´ alata input-output t´ abl´ akkal ´ es hypothetical extractions m´ odszerrel A gazdas´agi ´es gazdas´ agfejleszt´esi d¨ ont´esek el˝ok´esz´ıt´es´ehez ´es meghozatal´ahoz n´elk¨ ul¨ozhetetlen az ´erintett ´agazatok ´es v´ allalatok makrogazdas´ agi s´ uly´aval, szerep´evel ´es tovagy˝ ur˝ uz˝o hat´asaival kapcsolatos tiszt´anl´at´as. Az input-output elemz´es szakirodalma hypothetical extractions (hipetikus kivon´as/kivonul´as) elnevez´essel illeti azt a m´ odszert, amely az egyes ´agazatok (v´allalatok) nemzetgazdas´agi jelent˝os´eg´et u ´gy vizsg´alja, hogy egy gondolatk´ıs´erlet keret´eben elt´avol´ıtja azokat a gazdas´ag rendszer´eb˝ol, elv´agva az ¨osszes olyan sz´ alat, amellyel m´as hazai v´allalatokhoz, az els˝odleges inputt´enyez˝okh¨oz ´es a v´egs˝o 27
felhaszn´al´okhoz ´es kapcsol´ odnak. A vele” ´es n´elk¨ ule” ´allapot k¨ ul¨onbs´egei mutatj´ak a vizsg´alt sze” ” repl˝ok makrogazdas´ agi kateg´ ori´ akra gyakorolt hat´asait. A tanulm´any a K¨ozponti Statisztikai Hivatal ´ ´altal k¨oz¨olt ´agazati kapcsolati m´erlegadatok (AKM), s az ezekb˝ol a 2010-2015. ´evekre tov´abbvezetett nemzetgazdas´agi input-output t´ abl´ ak alapj´ an a fenti m´odszerrel, valamint multiplik´atorok seg´ıts´eg´evel elemzi Magyarorsz´ ag ´agazatainak upstream ´es downstream ´ert´ekl´ancait. A vizsg´alat a hazai kibocs´at´asban ´es k¨ ulkereskedelemben kiemelked˝ o, s a hozz´aadott´ert´ek-termel´esben is jelent˝os ar´anyt k´epvisel˝o k¨oz´ uti j´arm˝ ugy´ art´ asra koncentr´al, ¨ osszehasonl´ıtva az itt kapott eredm´enyeket m´as ´agazatok ´ert´ekeivel. Makrogazdas´agi m´er˝ osz´ amaink szempontj´ ab´ ol egyre meghat´ aroz´obb szerepe ellen´ere az ´agazat magyar gazdas´agba val´ o integr´ alts´ ag´ anak mutat´ oi a legalacsonyabbak k¨oz¨ott vannak, s szinte alig v´altoztak az elm´ ult f´el ´evtizedben. ¨ ond´ıj ´es a Pallas Ath´en´e Domus A kutat´ast ´es a tanulm´ any meg´ır´ as´ at a Bolyai J´anos Kutat´asi Oszt¨ Scientiae Alap´ıtv´ any t´ amogatta. Kopp´ any Kriszti´ an a Sz´echenyi Istv´an Egyetem egyetemi docense, a Gazdas´agmodellez˝ o Kutat´ ocsoport tagja. Kulcsszavak: Input-output elemz´es, hipotetikus elt´ avol´ıt´ as, ´ert´ekl´ ancok, el˝ ore- ´es h´ atratekint˝ o kapcsolatok, multiplik´ atorok, k¨ oz´ uti j´ arm˝ ugy´ art´ as. JEL: C67, O11, O25, O52.
Kov´ acs Andr´ as MTA SZTAKI
K´ etszint˝ u programoz´ asi megk¨ ozel´ıt´ es ´ aramtarifa optimaliz´ al´ as´ ara a keresletoldali szab´ alyoz´ ashoz Az el˝oad´asban k´etszint˝ u optimaliz´ al´ asi megk¨ozel´ıt´est javaslunk intelligens energiah´al´ozatokban t¨ort´en˝o tarifaoptimaliz´ al´ asra. A Stackelberg j´ at´ekban a vezet˝o a h´al´ozat u ´gy szeretn´e megha¨zemeltet˝oje, aki u t´arozni a fogyaszt´ oknak k´ın´ alt, id˝ oben v´ altoz´o ´aramtarif´at, hogy azzal a saj´at profitj´at maximaliz´alja. A k¨ovet˝ok az ´aramfogyaszt´ ok csoportjai, akik a tarif´ara adott v´alaszk´ent u ¨temezik a szab´alyozhat´o fogyaszt´oikat ´es akkumul´ atoraik t¨ olt´es´et/kis¨ ut´es´et u ´gy, hogy azzal az ´aramk¨olts´eg¨ uket minimaliz´alj´ak ´es a saj´at hasznoss´ agf¨ uggv´eny¨ uket maximaliz´alj´ak. A j´at´ekot k´etszint˝ u optimaliz´al´asi feladatk´ent ´ırjuk fel, majd bizony´ıtjuk egyes alapvet˝ o tulajdons´agait ´es sz´am´ıt´asi komplexit´as´at. Javaslatot adunk a feladat egyszint˝ u, kvadratikus f¨ uggv´enyekkel korl´atozott kvadratikus programra (QCQP) t¨ort´en˝o ´at´ır´as´ara, majd ism´etelt line´ aris programoz´ assal (successive linear progreamming, SLP) val´o megold´as´ara. A megk¨ozel´ıt´es hat´ekonys´ ag´ at sz´ am´ıt´ asi k´ıs´erletben demonstr´aljuk. A kutat´ast az Ipar 4.0 kutat´ asi ´es innov´ aci´os kiv´al´os´agi k¨ozpont” c´ım˝ u GINOP-2.3.2-15-2016-00002 ” t´amogat´as tette lehet˝ ov´e.
28
Kov´ acs Edith BME Differenci´ al Egyenletek Tansz´ek
Sz´ antai Tam´ as BME Differenci´ al Egyenletek Tansz´ek
Do esi f´ ak – u ´ j lehet˝ os´ egek ¨nt´ A d¨ont´esi f´ak nagy n´epszer˝ us´egnek ¨ orvendenek a besorol´asi, illetve el˝orejelz´esi lehet˝os´egei miatt. Egyszer˝ u ´ertelmezhet˝ os´eg¨ uk miatt sok ter¨ uleten alkalmazz´ak ˝oket. El˝oad´asunkban u ´j lehet˝ os´egeket mutatunk be a hat´ekonys´aguk megn¨ovel´es´ere. Az elj´ar´ast val´os adathalmazokon tesztelj¨ uk.
Kov´ acs Krist´ of BME, Differenci´ alegyenletek tansz´ek
G.-T´ oth Bogl´ arka Emilio Carrizosa Rafael Blanquero
A median probl´ ema megold´ asa folytonos kereslettel h´ al´ ozatokon A h´al´ozaton ´ertelmezett v´ allalatelhelyez´esi modellek t¨obbs´eg´eben a kereslet a cs´ ucsokba van koncentr´alva. T¨obben foglalkoztak olyan probl´em´ akkal, ahol az ´eleken is tal´alhat´o kereslet, de t¨obbnyire egyenletes eloszl´ast haszn´ alva. Tetsz˝ oleges eloszl´ ast kev´es cikkben vizsg´altak a feladat neh´ezs´ege miatt. Egy olyan modellt mutatunk be, ahol a h´al´ozat ´elein is van kereslet, valamilyen folytonos eloszl´as szerint. A c´el egy v´ allalat elhelyez´ese u ´gy, hogy a k¨olts´eg¨ unket minimaliz´aljuk, ahol a k¨olts´eg a v´allalat keresleti pontokt´ ol val´ o t´ avols´ ag´ at´ ol f¨ ugg. Legyen N = (A, E) ir´ any´ıtott ¨ osszef¨ ugg˝o gr´af, az A = {a1 , a2 , . . . , an } cs´ ucshalmazzal ´es E = {e1 , e2 , . . . , em } ´elhalmazzal. Tov´ abb´ a jel¨ olje lij az (ai , aj ) ∈ E ´el hossz´at, valamint d(x, y) a h´al´ozat k´et x, y ∈ N pontj´ anak t´ avols´ ag´ at. A t´ avols´ ag alatt a legr¨ovidebb u ´t ´ertend˝o x-b˝ol y-ba a gr´af ´elein haladva. Jel¨olje a keresletet az a cs´ ucson wa ≥ 0 ´es a teljes keresletet az e cs´ ucson pe ≥ 0. Adott e ´el keresleteloszl´ a s´ a t az F eloszl´ a sf¨ u ggv´ e ny adja meg. A teljes keresletet az eg´ esz h´al´ozaton jel¨olje D = e ∑ ∑ w + p . a e a∈A e∈E A teljes kereslet legal´ abb α r´eszet ki kell el´eg´ıteni. Az ´elek ´es cs´ ucsok bev´alaszt´asa bin´aris, azaz ha egy ´elet felhaszn´ alunk, akkor a teljes kereset´et kiel´eg´ıtj¨ uk. A c´elf¨ uggv´eny a kiv´alasztott A∗ ´es E ∗ cs´ ucs´es ´elhalmazt´ol vett kereslettel s´ ulyozott ¨ osszt´avols´aga a v´allalatnak. ∫ ∑ ∑ min G(x) := w d(x, a) + p d(x, b)dFe (b) a e ∗ ∗ A ⊆A, E ⊆E, x∈N
a∈A∗
f.h.
∑
a∈A∗
wa +
∑
e∈E ∗
b∈e
pe ≥ αD
e∈E ∗
A probl´ema megold´ as´ ahoz egy korl´ atoz´ as ´es sz´etv´alaszt´as algoritmust alkalmazunk. A neh´ezs´eg´et a bels˝o h´atizs´ak probl´ema adja. A kutat´ast a Nemzeti Kutat´ asi, Fejleszt´esi ´es Innov´aci´os Hivatal (NKFIH – PD115554) t´amogatja.
29
Kov´ acs Zolt´ an Pannon Egyetem, Ell´ at´ asi L´ anc Menedzsment Tansz´ek
Koszty´ an Zsolt Tibor Pannon Egyetem, Kvantitat´ıv M´ odszerek Int´ezeti Tansz´ek
Csizmadia Tibor Pannon Egyetem, Menedzsment Int´ezet
T¨ obbdimenzi´ os hierarchikus hibam´ od ´ es hat´ aselemz´ es Napjainkban az egyre er˝ os¨ od˝ o versenyhelyzet ´es a gazdas´agi instabilit´as arra k´eszteti a v´allalatokat, hogy t¨orekedjenek az el´erhet˝ o legjobb min˝ os´egre. Ennek ´erdek´eben sz¨ uks´egess´e v´alt olyan min˝os´eget szab´alyoz´o mechanizmusok be´ep´ıt´ese a termel˝o rendszerekbe, melyek c´elja az ¨osszes lehets´eges hiba ´es hat´as felt´ar´asa, ´es a nem megfelel˝ o term´ekek vev˝oh¨oz val´o eljut´as´anak megakad´alyoz´asa. Az egyik ilyen m´odszer a hibam´ od- ´es hat´ aselemz´es (FMEA). Az FMEA k¨ ozismerts´ege m´ar ¨ onmag´ aban min˝os´ıti haszn´alhat´os´ag´at, ha a megfelel˝o v´allalati h´att´erre tud t´amaszkodni. Az ´alland´ o magas min˝os´eg fontos szempont lett az ´elet minden ter¨ ulet´en. Mivel a v´as´arl´ok bizalm´ at nagyon k¨ onny˝ u elvesz´ıteni, ez´ert – ipar´agt´ol f¨ uggetlen¨ ul – k¨oz´eppontba ker¨ ultek azok az elj´ar´asok, melyek alacsony r´ aford´ıt´ assal, hat´ekonyan seg´ıtik a term´ekek min˝os´egk´epess´eg´et meghat´aroz´o v´allalati ter¨ uletek munk´ aj´ at. Ugyanakkor a k¨ ozismerts´ege ´es elterjedts´ege mellett sz´amos jogos kritika is megfogalmaz´odik a hagyom´anyos FMEA-val szemben. Az egyik ilyen kritika, hogy a kock´azat jellemz´es´ere haszn´alt el˝ofordul´as (occurrance = O), s´ ulyoss´ ag (severity = S), ´eszlelhet˝os´eg (detection = D) alapj´an sz´am´ıtott kock´azati ´ert´ek nem felt´etlen¨ ul t¨ ukr¨ ozi a val´ os kock´azatokat. Ennek okai k¨oz´e sorolhat´o, hogy e 3 t´enyez˝o nem felt´etlen¨ ul tekinthet˝ o f¨ ugetlennek egym´ast´ol. Sokszor e h´arom faktor nem elegend˝o a kock´azat jellemz´es´ere, sz¨ uks´eg van u ´j t´enyez˝ ok bevon´ as´ara, mint pl. a kock´azati kiterjedts´eg figyelembe v´etel´ere. Fontos probl´ema, hogy a trad´ıcion´ alis FMEA nem kezel komplex hibaok-hibam´od-hibahat´as l´ancolatokat, h´al´ozatokat, hierarchi´ akat. Az FMEA m´odszertani hi´anyoss´agaib´ol is ad´odik, hogy ´altal´aban csak egy ter¨ uletre, min˝ os´eg vagy k¨ ornyezeti hat´ as elemz´es´ere f´okusz´al seg´ıtve ezzel az ISO 9000 ´es az ISO 14000 szabv´anycsal´ adban megfogalmazott kock´azat´ert´ekel´esi feladatokat. Ugyanakkor a komplex hat´asok, komplex ´ert´ekel´esek hi´ anya miatt e ter¨ uletek integr´al´asa m´odszertani szinten sem val´osul meg. A javasolt m´odszerrel olyan t¨ obbdimenzi´ os keretrendszert javasolunk, amely k´epes hibaok-hibam´odhibahat´asok komplex h´ al´ ozat´ at kezelni. Aggreg´altan, t¨obbt´enyez˝os d¨ont´esi m´odszerekkel k´epes meghat´arozni a folyamatok, k¨ oz¨ os okok, hat´ asok kock´azati ´ert´ek´et. K´epes integr´alni t¨obb ter¨ ulet kock´azat´ert´ekel´esi m´odszertan´ at. El˝oad´asunkban bemutatjuk, hogy a javasolt ´es egy aut´oipari v´allalatn´al m´ar be is vezetett kock´azat´ert´ekel´esi keretrendszer seg´ıts´eg´evel siker¨ ult h´arom (min˝os´eg, k¨ornyezet ´es az eg´eszs´eg/biztons´ag) ter¨ ulet´et k¨oz¨os hibaokok ´es hibam´ odok meghat´aroz´as´aval integr´alni, kock´azat´ert´ekel´es¨ uket k¨oz¨os m´odszertani b´azisra helyezni. ¨ ond´ıja ´es az Emberi Er˝oA kutat´ast a Magyar Tudom´ anyos Akad´emia Bolyai J´anos Kutat´asi Oszt¨ ´ Nemzeti Kiv´ ´ forr´as Miniszt´erium Uj al´ os´ ag Programja (UNKP-PD-16) t´amogatta.
30
Kreji´ c Nataˇ sa ´ ´ ıt˝ Ujvid´ eki Egyetem, Szabadkai Ep´ om´ern¨ oki Kar
Krklec Jerinki´ c Nataˇ sa ´ ´ ıt˝ Ujvid´ eki Egyetem, Szabadkai Ep´ om´ern¨ oki Kar
Roˇ znjik Andrea ´ ´ ıt˝ Ujvid´ eki Egyetem, Szabadkai Ep´ om´ern¨ oki Kar
Felt´ eteles optimaliz´ al´ asi probl´ em´ ak megold´ asa v´ altoz´ o mintanagys´ ag´ u elj´ ar´ assal Felt´eteles optimaliz´ al´ asi probl´em´ akkal foglalkozunk, amelyekn´el a c´elf¨ uggv´eny determinisztikus, a felt´etel pedig egyenl˝os´egekkel van megadva ´es v´arhat´o ´ert´ekk´ent. A sztochasztikus felt´etelt SAA approxim´aci´o (Sample Average Approximation) felhaszn´ al´as´aval determinisztikuss´a alak´ıtottuk ´at. V´altoz´o mintanagys´ag´ u (Variable Sample Size) elj´ ar´ ason, vonalmenti keres´esen ´es b¨ untet˝o m´odszer alapj´an k´esz´ıtett algoritmust mutatunk be. A javasolt algoritmussal kapott iter´aci´os pontok sorozata az SAA probl´ema Karush–Kuhn–Tucker pontj´ aba tart. P´eld´ akon ¨osszehasonl´ıtottuk a m´odszer¨ unket az SAA elj´ar´assal ´es a heurisztikus mintan¨ ovel´eses algoritmussal. Az eredm´enyek azt mutatj´ak, hogy a m´odszer¨ unkkel kevesebb f¨ uggv´eny´ert´ek kisz´ am´ıt´ as´ aval lehet megkapni a megold´ast.
Kr´ esz Mikl´ os SZTE JGYPK
A cs´ ucs-s´ ulyozott inverz p´ aros´ıt´ asi probl´ ema A p´aros´ıt´asi algoritmusok t´emak¨ ore klasszikusnak sz´am´ıt a gr´afelm´eleten bel¨ ul, azonban a cs´ ucs-s´ ulyozott eset vizsg´alata eddig ´erdekes m´odon nem ker¨ ult a vizsg´alatok homlokter´ebe. B´ar Spencer ´es Mayr 1984-es ´ıg´eretes eredm´enye [2] megmutatta, hogy a probl´ema komplexit´asa k¨ozelebb esik a s´ ulyozatlan esethez, mint a s´ ulyozotthoz, n´eh´ any speci´ alis esetet lesz´am´ıtva az elm´eleti kutat´asok nem foglalkoztak a t´em´aval. Ugyanakkor alkalmaz´ asi oldalon, k¨ ul¨on¨osen a h´al´ozattervez´es ter´en az elm´ ult ´evekben sz´amos eredm´eny sz¨ uletett cs´ ucs-s´ ulyozott modellek haszn´alat´aval (lsd. pl. [1]). Jelen el˝oad´as keret´eben vizsg´ alt probl´emak¨or eset´eben feltessz¨ uk, hogy a s´ ulyok nemnegat´ıv eg´eszek. Ezen felt´etelez´essel az ´altal´ anoss´ ag megszor´ıt´asa n´elk¨ ul ´elhet¨ unk a [2] dolgozat k¨ovetkez˝o k´et ´eszrev´etele miatt. Egyr´eszt meg´ allap´ıt´ ast nyert, hogy a negat´ıv s´ ulyok egy egyszer˝ u strukt´ ura-meg˝orz˝o transzform´aci´oval kik¨ usz¨ ob¨ olhet˝ oek. M´ asr´eszt a kidolgozott algoritmus egyik implicit eredm´enye volt, hogy a t´enyleges s´ ulyok helyett elegend˝ o a k¨ ul¨ onb¨oz˝o s´ ulyok sorrendj´et tekintetbe venni, ez m´ar egy´ertelm˝ uen meghat´arozza a probl´ema strukt´ ur´ aj´ at. ´ Altal´ anoss´agban egy inverz optimaliz´ al´asi probl´ema alatt azt ´ertj¨ uk, hogy bizonyos param´eterek tekintet´eben a minim´ alis k¨ olts´eg˝ u ´ert´ekad´ ast keress¨ uk azon felt´etel szerint, hogy az el˝ore defini´alt megold´as optim´alis legyen az adott param´eterek ´altal meghat´arozott feladat eset´en. K¨onnyen l´athat´o, hogy a maxim´alis cs´ ucs-s´ ulyozott p´ aros´ıt´ asok eset´eben a fenti probl´ema trivi´alis (az ¨osszes cs´ ucs s´ ulya 0), abban az esetben, ha egy adott p´ aros´ıt´ ast tekint¨ unk el˝ore defini´alt megold´asnak. Azonban, ha az ¨osszes maxim´alis cs´ ucs-s´ ulyozott p´ aros´ıt´ ast tekintj¨ uk kiindul´asi megold´ask´ent, a feladat komplexebb´e v´alik. A fentiek alapj´an a cs´ ucs-s´ ulyozott inverz p´ aros´ıt´asi probl´em´at a k¨ovetkez˝ok´epp defini´alhatjuk. Adott egy gr´af, valamint az egyes ´eleinek ´es cs´ ucsainak a st´atusza: a st´atusz lehet tiltott (egy maxim´alis cs´ ucs-s´ ulyozott p´ aros´ıt´ as sem tartalmazza) vagy k¨otelez˝o (minden maxim´alis cs´ ucs-s´ ulyozott p´aros´ıt´as tartalmazza), illetve flexibilis m´ask¨ ul¨onben. A cs´ ucsok egy s´ ulyoz´as´at leg´alisnak nevezz¨ uk, ha minden ´el illetve cs´ ucs st´ atusza megfelel az el˝ore adott mint´anak. A c´el, hogy hat´arozzunk meg egy minim´alis ¨ossz-s´ uly´ u leg´ alis s´ ulyoz´ ast.
31
Az el˝oad´as keret´eben el˝ osz¨ or bebizony´ıtjuk, hogy a fenti probl´ema ´altal´anos esetben NP-teljes. Ezt k¨ovet˝oen a cs´ ucs-s´ ulyozott maxim´ alis p´ aros´ıt´asok dekompoz´ıci´oja seg´ıts´eg´evel kidolgozott elj´ar´as ker¨ ul ismertet´esre, amely polinomi´ alisan visszavezeti a feladatot egy speci´alis r´eszgr´af maximum Tuttehalmaz´anak meghat´ aroz´ as´ ara. Ezen eredm´enyek seg´ıts´eg´evel sz´amos esetben (pl. p´aros gr´afok, Hamilton gr´afok) polinomi´ alis algoritmust kapunk a probl´em´ara, melyek szint´en bemutat´asra ker¨ ulnek. Jelen kutat´ ast a Nemzeti Kutat´ asi, Fejleszt´esi ´es Innov´aci´os Hivatal SNN-117879 sz. p´aly´azat´aval t´amogatta Hivatkoz´ asok [1] B. Ji, G. R. Gupta, X. Lin, and N. B. Shroff, Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multi-Channel Wireless Networks, IEEE/ACM Transactions on Networking (ToN), 22 (2014), pp. 1911–1924. [2] T. H. Spencer, E. W. Mayr, Node weighted matching, in: Automata, Languages and Programming (1984), pp. 454–464.
London Andr´ as SZTE TTIK Informatika Int´ezet
Ko egkeres´ es p´ aros gr´ afok statisztikailag valid´ alt projekci´ oin ¨zo ¨ss´ Gr´afok k¨oz¨oss´egszerkezet´en a gr´ af cs´ ucsainak egy oszt´alyoz´as´at ´ertj¨ uk. A c´el olyan oszt´alyoz´as megad´asa, ami valamilyen elv´ ar´ as alapj´an relev´ans inform´aci´ot ad a gr´af szerkezet´er˝ol. Egy lehets´eges, ´es a val´os rendszerek gr´af modelljein ´altal´ aban j´ol m˝ uk¨od˝o megold´as a Newman-f´ele modularit´as-f¨ uggv´enyt maximaliz´al´o algoritmus ´altal adott klasszifik´aci´o [1]. P´aros gr´afok – melyek sz´amos komplex rendszer term´eszetes modelljei – eset´en sokszor relev´ ans inform´aci´ot ad az egy sz´ınoszt´alyban lev˝o pontok tov´abbi oszt´alyoz´asa. Erre egy lehet˝ os´eg a p´ aros gr´ af egyoldali projekci´oja, azaz egy seg´ed gr´af meghat´aroz´asa az azonos sz´ınoszt´ alyban lev˝ o pontokon, majd k¨oz¨oss´egkeres´es a kapott gr´afon. Ugyanakkor a projekci´ok nem mindig stabilak ´es robusztusak a hib´as adatokra, illetve m´as zajforr´asokra. Egy megold´as lehet statisztikailag ´erv´enyes´ıtett projekci´ o haszn´alata, mely csak a statisztikailag szignifik´ans kapcsolatokat veszi figyelembe a projekci´ o sor´ an [2]. Ez egyr´eszt jelent˝osen reduk´alja a rendszer m´eret´et, ugyanakkor a megtartja a k¨ oz˝ oss´egek magjait j´ o statisztikai precizit´assal. Az el˝oad´as sor´an ismertetj¨ uk a metodol´ogia f˝o elemeit ´es alkalmaz´ asokat mutatunk be sz´ın´esz-film p´aros gr´af, t´arsszerz˝os´egi h´al´ozat ´es szavak egy¨ uttes el˝ofordul´ asainak h´al´ ozata term´eszetesen nyelvi sz¨ovegekben eset´en [3]. Hivatkoz´ asok [1] Newman, M. E. (2006), Modularity and community structure in networks, Proceedings of the national academy of sciences, 103(23), 8577–8582. [2] Tumminello, M., Micciche, S., Lillo, F., Piilo, J., and Mantegna, R. N. (2011), Statistically validated networks in bipartite complex systems, PloS one, 6(3), e17994. [3] Bongiorno C., London A., Miccich`e S. and Mantegna R. N. (2017), Core of communities and statistically validated networks. Submitted for publication.
32
M´ adi-Nagy Gergely ELTE, Oper´ aci´ okutat´ asi Tansz´ek
T¨ obbv´ altoz´ os diszkr´ et momentum probl´ em´ ak ´ es alkalmaz´ asaik A diszkr´et momentum probl´em´ ak t´emak¨ or´et a 80-as ´evek v´eg´et˝ol Pr´ekopa Andr´as kezdte el vizsg´alni: megmutatta, hogy a probl´ema (egy rosszul kondicion´alt) line´aris programoz´asi feladattal modellezhet˝o. A c´elf¨ uggv´enyre tett bizonyos felt´etelek mellett siker¨ ult a du´al megengedett b´azisok teljes halmaz´at az oszlopindexek seg´ıts´eg´evel le´ırnia ´es ez alapj´an egy numerikusan stabil du´al megold´o algoritmust kifejlesztenie. A m´odszertan lehet˝ os´eget ny´ ujtott ´eles val´osz´ın˝ us´egi korl´atok algoritmikus illetve k´epletszer˝ u megad´as´ara: ezek j´ol alkalmazhat´ oak p´eld´ aul eloszl´asf¨ uggv´eny ´ert´ekeinek becsl´esre, h´al´ozat megb´ızhat´os´ag´anak becsl´es´ere, Boole–Bonferroni t´ıpus´ u korl´atok fel´ır´as´ara. A doktori dolgozatomat Andr´ as t´emavezet´ese alatt a diszkr´et momentum probl´ema t¨obbv´altoz´os ´altal´anos´ıt´as´ab´ol ´ırtam. K¨ oz¨ os munk´ ank sor´an, mely a doktori fokozat megszerz´ese ut´an is folytat´odott, a t¨obbv´altoz´os eset du´ al megengedett b´azisstrukt´ ur´ait vizsg´altuk k¨ ul¨onf´ele momentumfelt´etelek mellett, u ´jabb alkalmaz´ asokkal (pl. v´ arhat´ o hasznoss´ag becsl´ese) kieg´esz´ıtve. A t¨obbv´altoz´os modellez´es seg´ıts´eg´evel t¨obb alkalmaz´ asi ter¨ uleten is siker¨ ult az egyv´altoz´os modell eredm´enyein´el er˝osebb korl´atokat adni illetve lehet˝os´eg ny´ılt vegyes momentumokat haszn´al´o Boole–Bonferroni t´ıpus´ u korl´atok kidolgoz´as´ara is. Az el˝oad´as sor´ an e k¨ oz¨ os munk´ ar´ ol szeretn´ek besz´elni, a kapott eredm´enyekkel illusztr´alva. Az el˝oad´ast Pr´ekopa Andr´as eml´ek´ere aj´anlom.
Mell´ ar Tam´ as P´ecsi Tudom´ anyegyetem
A potenci´ alis kibocs´ at´ as, u ´ tfu os´ eg ´ es hiszter´ ezis-hat´ as ¨ gg˝ A potenci´alis kibocs´ at´ as k¨ ozvetlen¨ ul nem megfigyelhet˝o, l´atens v´altoz´o, ez´ert meghat´aroz´asa csak modellalap´ u becsl´essel t¨ ort´enhet. A viszonylag pontos meghat´aroz´asa nemcsak elm´eleti, hanem gyakorlati szempontb´ol is fontos. K¨ ul¨ on¨ osk´eppen jelent˝os inform´aci´o a gazdas´agpolitika sz´am´ara a t´enyleges ´es a potenci´alis kibocs´ at´ as k¨ ul¨ onbs´egek´ent ad´ od´o kibocs´at´asi r´es (output gap) ismerete. A potenci´alis kibocs´at´ as meghat´ aroz´ as´ ara vonatkoz´o becsl´esi elj´ar´asok a kezdeti id˝okben a hossz´ u t´av´ u trendir´anyzat meghat´ aroz´ as´ an alapultak (HP-filter, termel´esi f¨ uggv´eny). A k´es˝obbiekben ink´abb a potenci´alis kibocs´ at´ as egyens´ ulyi jelleg´ere alapozva a makroegyens´ ulyi param´eterek alapj´an pr´ob´alt´ak becs¨ ulni. Az elm´ ult ´evek hazai ´es k¨ ulf¨ oldi tapasztalatai azt mutatj´ak, hogy nem igen volt sikeres a potenci´alis kibocs´ at´ as ´es az output gap val´os idej˝ u, el˝oretekint˝o becsl´ese. A 2008-as v´als´ ag ut´ ani id˝ oszakban, l´ atva az igen lass´ u kil´abal´ast, egyre ink´abb a figyelem el˝oter´ebe ker¨ ult a hiszter´ezis-elm´elet ´es az u ´tf¨ ugg˝ os´eg. Ennek ´ertelm´eben a v´als´ag maradand´o negat´ıv hat´ast gyakorolt a n¨oveked´esi potenci´ alra, ´es megv´ altoztatta az egyes orsz´agokban a n¨oveked´esi p´aly´at ´es ebb˝ol k¨ovetkez˝oen a potenci´ alis kibocs´ at´ asi p´ aly´ at is. Az el˝oad´as r´eszletesen t´argyalja, hogy az (i) aggreg´alt kereslet jelent˝os v´ altoz´ asa, (ii) a k¨ ul¨ onf´ele ´at´all´asi ´es tranzakci´os k¨olts´egek, (iii) az infl´aci´os hat´asok, (iv) a beruh´az´ asok ´es a t˝ oke´ allom´ any v´ altoz´asa, (v) a technol´ogiai meg´ ujul´as ´es a szerkezeti v´alt´as mik´ent befoly´asolj´ ak ´es v´ altoztatj´ ak meg a potenci´alis n¨oveked´esi p´aly´at.
33
Mester Abig´ el Informatikai Int´ezet, Szegedi Tudom´ anyegyetem
B´ anhelyi Bal´ azs Informatikai Int´ezet, Szegedi Tudom´ anyegyetem
P´ al L´ aszl´ o Informatikai Int´ezet, Szegedi Tudom´ anyegyetem
Lok´ alis optimaliz´ al´ ok vonal menti keres´ es v´ altozatainak hat´ asa a GLOBAL elj´ ar´ asra Az optimaliz´al´asi probl´em´ ak ´eszrev´etlen¨ ul k¨orbe¨olelik ´elet¨ unket, sokszor a legh´etk¨oznapibb tev´ekenys´egek sor´an is optimaliz´ al´ ast hajtunk v´egre. El˝oad´asomban bemutatom, hogy a felmer¨ ul˝o probl´em´akat hogyan modellezhetj¨ uk a sz´am´ıt´ og´ep sz´ am´ ara is ´erthet˝o” m´odon. A modellez´es eredm´enye sokszor egy ” c´elf¨ uggv´eny, melyet minimaliz´ alunk. C´elf¨ uggv´enyek minimum pontjainak megtal´al´as´ara t¨obb glob´alis optimaliz´al´o elj´ar´as is alkalmas. El˝oad´asomban az optimaliz´ al´ asi tansz´ek ´altal fejlesztett Java alap´ u GLOBAL fejleszt´es´enek eredm´enyeit mutatom be. A GLOBAL[1] 3 f˝o komponensb˝ ol ´ep¨ ul fel, melyek a mintav´etelez´es, a klaszterez´es, valamint a lok´alis keres´es. M˝ uk¨od´es´enek l´enyege, hogy a sz´ am´ ara defini´alt keres´esi t´erb˝ol v´eletlenszer˝ uen v´alasztott pontokban ki´ert´ekeli a c´elf¨ uggv´enyt, majd ezekb˝ ol klasztereket k´epez. A klaszterek pontjaiban felvett c´elf¨ uggv´eny ´ert´ekekt˝ol f¨ ugg˝o val´ osz´ın˝ us´eggel iterat´ıvan u ´j pontokat k´epez a klaszterekben a lok´alis keres´essel, am´ıg be nem k¨ovetkezik valamelyik el˝ ore defini´ alt, az iterat´ıv optimaliz´aci´okban m´ar j´ol ismert meg´all´asi felt´etel. Fut´asa sor´ an t¨ obb optimum pont megtal´al´as´ara is k´epes. A lok´alis keres˝ o hat´ekonys´aga nagyban befoly´asolja a GLOBAL m˝ uk¨od´es´enek hat´ekonys´ag´at. C´elom a lok´alis keres˝ ok hat´ekonys´ ag´ anak jav´ıt´ as´aval kapott eredm´enyek bemutat´asa. Els˝o l´ep´esben az eredeti Unirandit m´odos´ıtottuk u ´gy, hogy a vonalmenti keres´ese egy modul legyen. Majd megval´os´ıtottuk a Rosenbrock-elj´ ar´ ast is, ugyanilyen modul´ aris szerkezetben. Kifejlesztett¨ unk t¨obb vonalmenti keres˝ot. Alap dupl´ azva l´epeget˝ o”, m´ asodfok´ u illeszt˝o”, negyedfok´ u illeszt˝o” elj´ar´asokat. Az el˝oad´as alatt ” ” ” megmutatom az ´altalunk fejlesztett k¨ ul¨ onf´ele elj´ar´asok eredm´enyess´eg´et, illetve a modul´aris szerkezet el˝onyeit. Hivatkoz´ as [1] Tibor Csendes: Nonlinear parameter estimation by global optimization – efficiency and reliability, Acta Cybernetica 8 (1988), 361–370.
Mih´ alyffy L´ aszl´ o K¨ ozponti Statisztikai Hivatal
Egy speci´ alis line´ aris felt´ etelrendszer megengedett megold´ as´ anak meghat´ aroz´ asa a v´ altoz´ ok sz´ am´ aval ar´ anyos aritmetikai m˝ uveletek seg´ıts´ eg´ evel El˝oad´asomban a k¨ ovetkez˝ o feladattal foglalkozom. Adottak a nyitott (0, 1) intervallumba es˝o p1 , p2 , . . . , pN val´os sz´amok, p1 + p2 + . . . + pN = n, n ´es N term´eszetes sz´amok, n ≪ N . Keres¨ unk N (N − 1) sz´am´ u pij val´os sz´ amot a k¨ ovetkez˝ o felt´etelekkel: (1) (2) (3)
pi1 + . . . + pi,i−1 + pi,i+1 + . . . + piN = (n − 1)pi , i = 1, 2, . . . , N, 0 < pij < pi pj , 1 ≤ i, j ≤ N, i ̸= j, pij = pji ,
1 ≤ i, j ≤ N, i ̸= j. 34
A feladat megold´ asa a mintav´eteles elj´ ar´asokban alkalmazhat´o. Az el˝oad´asban a feladat megold´as´anak m´odszer´ere, ennek o tlet´ e re helyezem a hangs´ ulyt, v´elve, hogy ez esetleg a mintav´eteles elj´ar´asokt´ol ¨ k¨ ul¨onb¨oz˝o ter¨ uleten is alkalmazhat´ o lehet. A (2) felt´etel al´abbi ´atfogalmaz´as´aval (2′ ) (3′ )
pij = xij pi pj , 0 < xij < 1, 1 ≤ i, j ≤ N, i ̸= j xij = xji , 1 ≤ i, j ≤ N, i ̸= j
a feladatot a k¨ ovetkez˝ o, az eredetivel ekvivalens feladatt´a alak´ıthatjuk: (4)
Ax = b,
ahol A N × M m´eret˝ u m´ atrix, M = N (N − 1)/2, oszloponk´ent k´et z´erust´ol k¨ ul¨onb¨oz˝o eleme van; x komponensei az al´ abbiak: (5) (6)
x12 , x13 , . . . , x1N , x23 , x24 , . . . , x2N , x34 , . . . , x3N , . . . , xN −2,N −1 , xN −2,N , xN −1,N , ´es az N -dimenzi´ os b vektor mindegyik komponense (n − 1).
A (4) ´es (6) felt´etelekkel valamint a 0 < xij < 1, 1 ≤ i, j ≤ N , i ̸= j egyedi korl´atokkal meghat´arozott feladat nyilv´ an line´ aris programoz´ asi eszk¨oz¨okkel is kezelhet˝o, emellett alkalmazhat´o r´a az iterat´ıv ar´anyos k¨ozel´ıt´esek m´odszer´enek egy speci´alis esete is, az u ´n. gerebly´ez´es”, angolul raking”. Ezek ” ” helyett egy eleg´ ans ´es gyors elj´ ar´ ast adunk a k¨ovetkez˝ok szerint. Az xij ismeretlenekre n´ezve ismert az irodalomb´ol egy explicit k´eplettel megadott x0 vektor, amely a (4) egyenletet ´es a nem-negativit´asi felt´eteleket kiel´eg´ıti, bizonyos xij v´ altoz´ ok ´ert´eke azonban 1-n´el nagyobb lehet. Ebb˝ol az x0 vektorb´ol kiindulva, 1-t˝ol M -ig v´egig vizsg´ aljuk az A m´atrix oszlopait, illetve a hozz´ajuk tartoz´o xij v´altoz´okat. Ahol 1-n´el nagyobb ´ert´eket tal´ alunk, azt 1 ´ert´ekkel r¨ogz´ıtj¨ uk, ´es a nem r¨ogz´ıtett v´altoz´ok ´ert´ek´et u ´gy m´odos´ıtjuk, hogy a (4) egyenl˝ os´eg teljes¨ ulj¨ on. A m´atrix minden oszlop´at csak egyszer kell megvizsg´alni. Az eredm´eny a visszatev´es n´elk¨ uli, nagys´aggal ar´anyos val´osz´ın˝ us´eg szerinti mintav´eteln´el alkalmazhat´o, ´ert´ek¨osszeg sz´or´ asn´egyzet´enek becsl´es´ere. Egy kor´abbi eredm´enyemmel kombin´alva, ismereteim szerint a sz´oban forg´ o feladatra a legegyszer˝ ubb, leggyorsabb megold´ast szolg´altatja.
Mih´ alyk´ o Csaba Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
´ Mih´ alyk´ on´ e Orb´ an Eva Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
Nemteljes p´ aros ¨ osszehasonl´ıt´ asokon alapul´ ou ´ j m´ odszer axiomatikus tulajdons´ againak elemz´ ese P´aros ¨osszehasonl´ıt´ asi m´ odszereket gyakran alkalmaznak d¨ont´esek sor´an, leggyakrabban akkor, amikor az ¨osszehasonl´ıt´ asok szempontjai szubjekt´ıvek. Az egyik leggyakrabban alkalmazott m´odszer az AHP, amelyben egy p´aros ¨ osszehasonl´ıt´ asi m´ atrix legnagyobb saj´ at´ert´ek´ehez tartoz´o saj´atvektor´anak kisz´amol´as´aval t¨ort´enik az ¨ osszehasonl´ıtott objektumok ki´ert´ekel´ese [1]. Nemteljes ¨ osszehasonl´ıt´ asok eset´en t¨ obbek k¨oz¨ott Boz´oki ´es t´arsai az LLSM m´odszert vizsg´alt´ak ´es bizony´ıtottak sz¨ uks´eges ´es el´egs´eges felt´etelt a ki´ert´ekel´es eredm´eny´enek l´etez´es´ere ´es egy´ertelm˝ us´eg´ere [2]. M´asik gyakran alkalmazott m´odszer a Thurstone m´odszer, amelyben az egyes objektumokhoz l´atens val´osz´ın˝ us´egi v´altoz´ okat t´ ars´ıtanak ´es a d¨ ont´es sor´an ezek k¨ ul¨onbs´eg´et ´ert´ekelik ki. E m´odszer ´altal´anos´ıthat´o a jobb/rosszabb lehet˝ os´egekr˝ ol t¨ obb d¨ ont´esi kateg´ori´ara is. Az ´altal´anos´ıtott m´odszer¨ unk nemteljes an val´ o alkalmaz´ asa eset´en el´egs´eges felt´etelt adtunk a rangsor l´etez´es´ere ´es egy´ertel¨osszehasonl´ıt´as sor´ m˝ us´eg´ere [3].
35
Az egyes m´odszereket vizsg´ alj´ ak olyan szempont szerint is, hogy mely tulajdons´agokat teljes´ıtenek ´es melyeket nem ([4], [5]). El˝oad´asunkban ezzel az axiomatikus megk¨ozel´ıt´essel elemezz¨ uk az ´altal´anos´ıtott Thurstone m´odszer¨ unket, ´es mutatjuk be a tulajdons´ agait. T¨obbek k¨oz¨ott azt, hogy a m´odszer anonim, homog´en, szimmetrikus, az egyenletess´eget meg˝ orzi, teljes´ıti az inverzi´ os tulajdons´agot, viszont a sorrendet nem ˝orzi meg, ´es hogy nem f¨ uggetlen az irrelev´ ans ¨osszehasonl´ıt´asokt´ol. Hivatkoz´ asok [1] Saaty, T. L. (2008). Decision making with the analytic hierarchy process, International Journal of Services Sciences, 1(1), 83–98. [2] Boz´ oki, S., F¨ ul¨ op, J., & R´ onyai, L. (2010). On optimal completion of incomplete pairwise comparison matrices, Mathematical and Computer Modelling, 52(1), 318–333. ´ Mih´ [3] Orb´ an-Mih´ alyk´ o, E., alyk´ o, Cs., Koltay L. A generalization of the Thurstone method for multiple choice and incomplete paired comparisons (elk¨ uldve a CJOR-ba). [4] Csat´ o, L. (2013). Fogalmak, m´ odszerek. P´ aros ¨ osszehasonl´ıt´ asokon alapul´ o rangsorol´ asi m´ odszerek (Ranking methods based on paired comparisons), Szigma, 44(3–4), 155–198. [5] Gonz´ alez-D´ıaz, J., Hendrickx, R., & Lohmann, E. (2014). Paired comparisons analysis: an axiomatic approach to ranking methods, Social Choice and Welfare, 42(1), 139–169.
´ Mih´ alyk´ on´ e Orb´ an Eva Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
Mih´ alyk´ o Csaba Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
Koltay L´ aszl´ o Pannon Egyetem, M˝ uszaki Informatikai Kar, Matematika Tansz´ek
´ Altal´ anos´ıtott Thurstone m´ odszer nemteljes p´ aros ¨ osszehasonl´ıt´ asok eset´ en P´aros ¨osszehasonl´ıt´ asi m´odszereket gyakran alkalmaznak d¨ont´eshozatalok sor´an. A m´odszerek t¨obbs´ege az objektumok ¨ osszehasonl´ıt´ as´ an´ al k´et kateg´ori´at enged meg, a jobb ´es a rosszabb opci´okat. Enn´el azonban t¨obb d¨ ont´esi kateg´oria is c´elszer˝ u lehet, p´eld´aul az egyforma, vagy a sokkal jobb/ sokkal rosszabb v´alaszt´ asi lehet˝ os´eg. Az egyik leggyakrabban alkalmazott m´odszer, az AHP rendelkezik ezzel az el˝onnyel. AHP eset´en a ki´ert´ekel´es m´odszere az, hogy az ¨osszehasonl´ıt´asok eredm´enyek´ent egy p´aros ¨osszehasonl´ıt´asi m´atrixot hoznak l´etre, aminek legnagyobb saj´at´ert´ek´ehez tartoz´o saj´atvektora koordin´at´ainak sorrendje adja az objektumok sorrendj´et [1]. A m´odszer akkor alkalmazhat´o, ha a m´atrix minden eleme adott, ehhez pedig az kell, hogy b´armely k´et objektum ¨ossze legyen hasonl´ıtva. Nemteljes arsai az LLSM m´odszert vizsg´alt´ak ´es bizony´ıtottak sz¨ uks´eges ´es ¨osszehasonl´ıt´asok eset´en Boz´oki ´es t´ el´egs´eges felt´etelt a ki´ert´ekel´es eredm´eny´enek egy´ertelm˝ us´eg´ere [2]. A fenti m´odszerek h´atr´anya, hogy a statisztikai hipot´ezisvizsg´ alatok nem kidolgozottak. M´asik gyakran alkalmazott m´odszer a Thurstone m´odszer, amelyben az egyes objektumokhoz l´atens val´osz´ın˝ us´egi v´ altoz´ okat t´ ars´ıtanak, ´es az egyes ¨ossze-hasonl´ıt´ asok sor´an a val´osz´ın˝ us´egi v´altoz´ok k¨ ul¨onbs´eg´enek el˝ojel´er˝ ol d¨ ontenek. E m´ odszer ´altal´anos´ıthat´o a jobb/rosszabb lehet˝os´egekr˝ol t¨obb d¨ont´esi kateg´ori´ara is. A l´ atens val´ osz´ın˝ us´egi v´altoz´ ok k¨ ul¨onbs´eg´et norm´alis eloszl´as´ unak felt´etelezve, a likelihood f¨ uggv´enyt fel´ırva a param´eterek ML m´odszerrel becs¨ ulhet˝ok.
36
´ Altal´ anos´ıtott m´odszer¨ unk nemteljes o ¨sszehasonl´ıt´as sor´an val´o alkalmaz´asa eset´en el´egs´eges felt´etelt adtunk az optimum l´etez´es´ere ´es egy´ertelm˝ us´eg´ere [3]. El˝oad´a-sunkban bemutatjuk ezt a felt´etelt, valamint egy, az objektumok azonoss´ ag´ anak tesztel´es´et lehet˝ov´e tev˝o pr´ob´at. Konfidencia intervallumokat konstru´alunk a para-m´eterekre, az egyes kateg´ori´ak kialakul´as´anak val´osz´ın˝ us´egeire. Kit´er¨ unk tov´abb´a arra az ´altal´ anos´ıt´ asra, amikor a l´ atens val´osz´ın˝ us´egi v´altoz´ok k¨ ul¨onbs´ege szigor´ uan logkonk´av s˝ ur˝ us´egf¨ uggv´ennyel rendelkezik (lsd. a Bradley–Terry modell [4]). Hivatkoz´ asok [1] Saaty, T. L. (2008). Decision making with the analytic hierarchy process, International Journal of Services Sciences, 1(1), 83–98. [2] Boz´ oki, S., F¨ ul¨ op, J., & R´ onyai, L. (2010). On optimal completion of incomplete pairwise comparison matrices, Mathematical and Computer Modelling, 52(1), 318–333. ´ Mih´ [3] Orb´ an-Mih´ alyk´ o, E., alyk´ o, Cs., Koltay, L., A generalization of the Thurstone method for multiple choice and incomplete paired comparisons (elk¨ uldve a CJOR-ba). [4] Bradley, R. A., & Terry, M. E. (1952). Rank analysis of incomplete block designs: I. The method of paired comparisons, Biometrika, 39(3/4), 324–345.
P´ al L´ aszl´ o Sapientia Erd´elyi Magyar Tudom´ anyegyetem
S´ andor Zsolt Sapientia Erd´elyi Magyar Tudom´ anyegyetem
Mak´ o Zolt´ an Sapientia Erd´elyi Magyar Tudom´ anyegyetem
A BLP modell alternat´ıv megold´ asi m´ odszereinek vizsg´ alata A BLP (Berry,Levinsohn, ´es Pakes) [1] modellt sz´eles k¨orben haszn´alj´ak fogyaszt´oi preferenci´ak becsl´es´ere. Ez egy diszkr´et v´alaszt´ asi v´eletlen egy¨ utthat´oj´ u modell, amelyben az egyes fogyaszt´ok elt´er˝oen ´ert´ekelik az egyes term´ekjellemz˝ oket. A modell param´etereinek becsl´es´ere legelterjedtebb m´odszer az ´altal´anos´ıtott momentumok m´odszere (GMM). A m´odszer egy k¨ uls˝o ´es egy bels˝o ciklusb´ol ´all, amelynek l´enyege egy kontrakci´ os algoritmus. Az el˝ oz˝o algoritmus h´atr´anyainak kik¨ usz¨ob¨ol´es´ere u ´j m´odszereket javasoltak, mint az MPEC (mathematical programming with equilibrium constraints) [2] vagy ABLP (approximated BLP) [3]. A [4]-ben egy Spectral ´es egy Squarem nev˝ u m´odszert vizsg´alnak az el˝oz˝o algoritmusok mellett. Az el˝oad´asban a fenti m´odszerek szisztematikus tesztel´es´et ´es ¨osszehasonl´ıt´as´at mutatjuk be mesters´egesen gener´ alt adatokon. A vizsg´ alatokat a v´eletlen egy¨ utthat´ok k¨ ul¨onb¨oz˝o variancia ´ert´ekei mellett valamint v´altoz´ o sz´ am´ u piac ´es term´ek sz´ am mellett v´egezz¨ uk el. Hivatkoz´ asok [1] Berry, S., Levinsohn, J. and Pakes, A. (1995): “Automobile Prices in Market Equilibrium,” Econometrica, 63(4), 841–890. [2] Dub´e, J. P., Fox, J. T., and Su, C.-L. (2012): “Improving the Numerical Performance of BLP Static and Dynamic Discrete Choice Random Coefficients Demand Estimation.” Econometrica, 80, 2231–2267. [3] Lee, J. and Seo, K. (2015): “A computationally fast estimator for random coefficients logit demand models using aggregate data”. RAND Journal of Economics, 46: 86–102. [4] Reynaerts, J., Varadhan, R., and Nash, J. C. (2012): Enhancing the Convergence Properties of the BLP (1995) Contraction Mapping, Discussion Paper, Vives.
37
Pek´ ardy Mil´ an Pannon Egyetem
Baumgartner J´ anos Pannon Egyetem
Su an ¨ le Zolt´ Pannon Egyetem
Ell´ at´ asi l´ anc optimaliz´ al´ as P -gr´ af m´ odszertan alkalmaz´ as´ aval mennyis´ egi ´ es min˝ os´ egi param´ eterek figyelembev´ etel´ evel Ell´at´asi l´ancok modellez´ese ´es elemz´ese kapcs´an sz´amos ter¨ uleten mer¨ ulnek fel optimaliz´al´asi probl´em´ak, amelyek legt¨obb esetben h´al´ ozati modellek vizsg´alat´ara vezetnek. E feladatok megold´asakor sok esetben a k¨olts´eg optimum megtal´ al´ asa a c´el, amelyet vegyes eg´esz ´ert´ek˝ u feladat form´aj´aban ´ırhatunk fel, de az optimaliz´al´ asi feladat m´erete kritikus lehet nagy elemsz´ am´ u h´al´ozati probl´em´ak eset´en. A k¨olts´eg param´eter mellett tov´ abbi szempontokat is figyelembe v´eve m´ar t¨obbszempont´ u optimaliz´al´asi feladatot kell hat´ekonyan kezeln¨ unk, amely tov´ abbi speci´alis metodik´ak alkalmaz´as´at k¨ovetelheti meg. El˝oad´asunkban egy korl´ atoz´ as ´es sz´etv´ alaszt´as alap´ u algoritmust ismertet¨ unk ell´ at´asi l´ancok k¨olts´eg szempont´ u optimaliz´ al´ as´ ara, ahol a megold´ as sor´an figyelembe vessz¨ uk a l´anc elemeit jellemz˝o min˝os´egi jellemz˝oket (diszkr´et esetben v´ arhat´ o meghib´asod´ast, m´ıg folytonos esetben meghib´asod´asi f¨ uggv´enyt), valamint a rendelkez´esre ´all´ o ´es megk¨ ovetelt mennyis´egi ´es kapacit´ast le´ır´o param´etereket. Olyan korl´atoz´o f¨ uggv´enyt defini´ alunk, amely fels˝ o becsl´est szolg´altat a megold´as sor´an a r´eszprobl´em´ak megb´ızhat´os´ag´ara, ´ıgy lehet˝ os´eg ad´ odik hat´ekony v´ag´asi l´ep´esek elv´egz´es´ere. A megb´ızhat´os´agi m´er˝osz´am sz´am´ıt´as´ara a Kov´ acs ´es Friedler ´altal bevezetett megb´ızhat´os´agi polinomot adapt´altuk azon esetekre, amikor nem csak a struktur´ alis jellemz˝ oket tekintj¨ uk, hanem az optimaliz´al´as alapj´aul szolg´al´o k¨olts´eg ´es mennyis´egi szempontokat is figyelembe vessz¨ uk. A kidolgozott metodik´ at egy logisztikai esettanulm´anyon kereszt¨ ul mutatjuk be, r´amutatva az alkalmazott elj´ar´as hat´ekonys´ ag´ ara. ´ ´ NemK¨ osz¨ onetnyilv´ an´ıt´ as. Az Emberi Er˝ oforr´asok Miniszt´eriuma UNKP-2016-3-I k´odsz´am´ u Uj zeti Kiv´al´os´ag Programj´ anak t´ amogat´ as´ aval k´esz¨ ult.
38
Petr´ oczy D´ ora Gr´ eta Budapesti Corvinus Egyetem
Mark Francis Rogers ´ Budapesti Fazekas Mih´ aly Gyakorl´ o Altal´ anos Iskola ´es Gimn´ azium
´ L´ K´ oczy A. aszl´ o MTA KRTK K¨ ozgazdas´ agtudom´ anyi Int´ezet; ´ Obudai Egyetem Keleti K´ aroly Gazdas´ agi kar
D¨ ont´ esi befoly´ as v´ altoz´ asa az Eur´ opai Uni´ o Tan´ acs´ aban egy lehets´ eges kil´ ep´ es ut´ an A Brexit ut´an Csehorsz´ agban is felmer¨ ult, hogy szavaz´ast tartsanak az Uni´ob´ol t¨ort´en˝o kil´ep´esr˝ol. Cikk¨ unkben el˝osz¨or a Czexit hat´ asait elemezt¨ uk a Brexit ut´ani helyzetben, majd megvizsg´altuk, hogy ha b´armely orsz´ag kil´epne, hogyan v´ altozn´ anak az er˝oviszonyok a bennmarad´o orsz´agok k¨oz¨ott. A kil´ep´esek lehets´eges hat´ asaib´ ol egyetlen vonatkoz´ast vizsg´altunk, hogyan v´altozna az er˝oviszonyok eloszt´asa az Eur´opa Uni´ o Tan´ acs´ aban. A Lisszaboni Egyezm´eny a d¨ ont´eshozatalt a t´amogat´o orsz´agok sz´am´ahoz, illetve lakoss´ag´ahoz k¨oti. Egy javaslat akkor l´ep ´erv´enybe, ha a tag´allamok legal´abb 55%-a t´amogatja, akik az EU ´allampolg´arainak legal´abb 65%-´ at k´epviselik. A s´ ulyok ilyen m´odon t¨ort´en˝o kialak´ıt´asa lehet˝ov´e teszi, hogy el˝ore meg tudjuk mondani, hogyan alakulnak a szavaz´ asi er˝oviszonyok, ha egy orsz´ag kil´ep az Eur´opai Uni´ob´ol. A Shapley–Shubik hatalmi index haszn´alat´aval megvizsg´altuk a tagok erej´et a lehets´eges kil´ep˝ovel egy¨ utt, illetve n´elk¨ ule. Figyelembe vett¨ uk azt is, hogy egy orsz´ag kil´ep´es´evel a befizet´ese is elveszik. Ez´ert korrig´altuk a Shapley–Shubik indexeket a befizet´es cs¨okken´essel ar´anyosan. Minden orsz´ag kil´ep´es´ere ugyanazt a mint´ azatot tal´ altuk, szoros ¨osszef¨ ugg´es van a n´epess´egsz´am ´es a d¨ont´esi befoly´as v´altoz´asa k¨oz¨ott. A kis orsz´ agok hatalmi indexe n˝ott a legnagyobb m´ert´ekben. A kisebb lakoss´ag´ u orsz´agoknak kedvez, hogy 27, illetve 26 tag´ allam eset´en is 15 orsz´ag t´amogat´asa kell, hogy eredm´enyes legyen a szavaz´as, viszont a kil´ep´essel a n´epess´egkorl´at cs¨okken. A Czexit hat´as´ara M´alta, Luxembourg ´es Ciprus befoly´ asa t¨ obb, mint 25%-kal, Magyarorsz´ag´e viszont csak 4,5%-kal n˝o. A 17 milli´on´al nagyobb lakoss´ag´ u orsz´ agok hatalmi ereje viszont cs¨ okken. Azt is megn´ezt¨ uk, mi t¨ ort´enik, ha m´eg egy orsz´ag kil´ep, p´eld´aul N´emetorsz´ag ut´an Csehorsz´ag. Azaz az EU tag´ allamok sz´ ama 26-r´ ol 25-re cs¨okkenne. Ez a Brexithez hasonl´o eset, hiszen mindk´etszer az Eur´opa Uni´ o Tan´ acs´ aban is v´ altozik a d¨ont´eshez sz¨ uks´eges tag´allamok sz´ama. Azt tal´altuk, hogy ekkor a nagy orsz´ agok hatalmi ereje n¨ ovekszik, m´ıg a kis orsz´agok´e cs¨okken. Ez megegyezik azokkal a hatalmi v´altoz´asokkal, amit a Brexit eredm´enyez. ´ t˝ Ugy unik, hogy fel lehet fedezni egy ´altal´anos mint´at: egy kil´ep´es, ami a tag´allam-kv´ota cs¨okken´es´et okozza, a nagy orsz´ agok sz´ am´ ara kedvez, m´ıg egy kil´ep´es, ami nem okoz kv´ota v´altoz´ast, a kis orsz´agok hatalmi index´et n¨ oveli. Ez azt sugallja, hogy a Brexitet Horv´atorsz´ag csatlakoz´asa el˝ott m´ask´eppen kezelt´ek volna. Kulcsszavak: Eur´ opai Uni´ o Tan´ acsa, s´ ulyozott szavaz´ as, hatalmi indexek. JEL k´ odok: C71, D72..
39
Pint´ er Mikl´ os P´ecsi Tudom´ anyegyetem
Kock´ azateloszt´ asi j´ at´ ekok nukleolusza A kock´azateloszt´ asi j´at´ekok [3] oszt´ alya egybe esik a teljesen kiegyens´ ulyozott j´at´ekok oszt´aly´aval [1]. A prenukleolusz [4] a Kovariancia, az Egyenl˝oen Kezel˝o Tulajdons´ag ´es a Reduk´alt-j´at´ek Tulajdons´ag axi´om´akkal karakteriz´ alhat´ o az ¨ osszes j´ at´ekok oszt´aly´an [5], ahol a reduk´alt-j´at´ek a Davis–Maschler-f´ele reduk´alt j´at´ek [2]. K¨ oztudott, hogy a kiegyens´ ulyozott j´at´ekok oszt´aly´an a prenukleolusz ´es a nukleolusz megegyezik. Az el˝oad´asban megmutatjuk, hogy a nukleolusz nem teljes´ıti Reduk´alt-j´at´ek Tulajdons´agot a kock´azatleoszt´asi j´ at´ekok oszt´ aly´ an, ´ıgy Sobolev [5] karakteriz´aci´oja nem m˝ uk¨odik ebben az esetben. Hivatkoz´ asok ´ (2009). Stable Allocations of Risk, Games and Economic Behavior [1] Cs´ oka, P., Herings, P. J. J., K´ oczy, L. A. 67(1):266–276. [2] Davis, M., Maschler, M. (1965). The kernel of a cooperative game, Naval Research Logistics Quarterly, 12(3):223–259. [3] Denault, M. (2001). Coherent Allocation of Risk Capital, Journal of Risk, 4(1):1–34. [4] Schmeidler, D. (1967). On balanced games with infinitely many players. Mimmeographed, RM-28. Department of Mathematics, The Hebrew University, Jerusalem. [5] Sobolev, A. I. (1975). A characterization of optimality principles in cooperative games by functional equations (in Russian), in: Vorobyev, N. N. (ed.) Mathematical Methods in the Social Sciences, Vipusk, pp. 92–151.
R´ acz Anett Debreceni Egyetem, Informatikai Kar, Alkalmazott Matematika ´es Val´ osz´ın˝ us´egsz´ am´ıt´ as tansz´ek
Holh´ os Attila Debreceni Egyetem, Informatikai Kar, Alkalmazott Matematika ´es Val´ osz´ın˝ us´egsz´ am´ıt´ as tansz´ek
´ ekenys´ Erz´ egvizsg´ alat R-ben Napjaink egyik legelterjedtebb ny´ılt forr´ ask´ od´ u programnyelve az R. A nyelv, b´ar els˝osorban statisztikai alkalmaz´asok ter´en elterjedt egyre gyakrabban haszn´alatos m´as ter¨ uleteken is, mint p´eld´aul az optimaliz´aci´o. A jelenleg haszn´ alt optimaliz´ aci´ os R csomagok, mint az lpSolve vagy a linprog tartalmaznak ugyan f¨ uggv´enyeket, melyek adnak inform´ aci´okat a Line´aris Programoz´asi (LP) feladatok ´erz´ekenys´egvizsg´alat´ahoz sz¨ uks´eges adatokr´ ol, de vizsg´ alataink sor´an arra jutottunk, hogy egyike sem teljes. Ez´altal sz¨ uks´eg´et ´erezt¨ uk egy olyan csomag kidolgoz´as´anak, mely r´eszben t´amaszkodik a fent eml´ıtett k´et csomag elj´ar´asaira, de azokat kieg´esz´ıti olyan f¨ uggv´enyekkel, melyek seg´ıts´eg´evel ´atl´athat´o ´es teljes k´epet kaphatunk a feladat du´ alis v´ altoz´ oinak ´ert´ek´er˝ol ´es az ´erz´ekenys´egi hat´arokr´ol. C´elunk egy k¨ onnyen kezelhet˝ o elj´ ar´ asgy˝ ujtem´eny kidolgoz´asa volt R-ben, melyn´el a jelenlegi csomagok hi´anyoss´againak kik¨ usz¨ ob¨ ol´ese mellett k¨ ul¨on¨osen nagy hangs´ ulyt fektett¨ unk az eredm´enyek ´atl´athat´o megjelen´ıt´es´ere is. Az el˝ oad´ asunkban bemutatjuk az ´altalunk fejlesztett csomag lehet˝os´egeit, ´es u ´jdons´agait a k´et eml´ıtett elj´ ar´ ashoz k´epest.
40
Sanja Rapaji´ c Szabadkai M˝ uszaki Szakf˝ oiskola
Papp Zolt´ an Szabadkai M˝ uszaki Szakf˝ oiskola
A nemline´ aris komplementarit´ asi feladat megold´ as´ ara szolg´ al´ o nem monoton sim´ıt´ o m´ odszer A nemline´aris komplementarit´ as feladata a matematikai optimaliz´aci´o egy j´o megalapozott r´eszter¨ ulete, amely sok m´ern¨ oki, k¨ ozgazdas´ agi ´es m´ as ter¨ uleteken jelentkez˝o re´alis probl´em´ak matematikai modellj´eben jelentkezik. C´elunk egy Jacobi-m´ atrixot sim´ıt´ o nempontos Newton-m´odszer fejleszt´ese, amely a nemline´aris komplementarit´ as feladat´ anak megold´ as´ at k¨ozel´ıti. A m´odszer olyan nemmonoton vonalmenti optimaliz´aci´os elj´ar´ast haszn´ al, amely nem ig´enyel deriv´altki´ert´ekel´est. Ez az elj´ar´as a Grippo–Lampariello– Lucidi ´es Li–Fukushima elj´ ar´ as kombin´ aci´ oja, ´ıgy kihaszn´alja az eml´ıtett elj´ar´asok j´o tulajdons´agait ´es kik¨ usz¨ob¨oli h´atr´ anyait. Az elj´ ar´as biztos´ıtja a m´odszer glob´alis konvergenci´aj´at. A Jacobi-m´ atrixot sim´ıt´ o nempontos Newton-m´odszer a nemline´aris komplementarit´asi feladat Fischer–Burmeister ekvivalens ´atalak´ıt´ as´ at haszn´alja, ami f´elsima f¨ uggv´eny˝ u nemline´aris egyenletrendszerhez vezet. A m´ odszer ezt az egyenletrendszert oldja nempontos Newton-m´odszerrel. Mindegyik iter´aci´oban egy vegyes Newton egyenletrendszert kell k¨ozel´ıt˝oleg megoldani, ami tartalmazza az egyenletrendszer f´elsima f¨ uggv´eny´et ´es annak sim´ıtott verzi´oj´anak Jacobi-m´atrix´at. Mivel a m´odszer nempontos keres´esi ir´anya ´altal´ anos esetben nem monoton cs¨okken˝o, a vonalmenti optimaliz´aci´oban nemmonoton felt´etelt kell alkalmazni. A szerz˝oknek siker¨ ult bebizony´ıtani bizonyos felt´etelek mellett a m´odszer glob´alis konvergenci´aj´at ´es a szuperline´aris konvergenciasebess´eget. A numerikus k´ıs´erletek eredm´enye is a m´odszer robusztusoss´ag´ar´ol tan´ uskodik.
Romsics Erzs´ ebet MTA K¨ ozgazdas´ ag-tudom´ anyi Int´ezet Mechanizmustervez´es kutat´ ocsoport
Hogyan osszunk el igazs´ agosan egy tort´ at sokfel´ e? A mindenkori t´arsadalom sz¨ untelen probl´em´ aja a javak igazs´agos feloszt´asa, ez´ert elengedhetetlen az osztozkod´ast v´egz˝o m´odszerek m¨ og¨ otti helyes matematikai modellek fel´all´ıt´asa. Az igazs´agos tortaoszt´as probl´em´aja, hogy egy felszeletelhet˝ o, heterog´en j´osz´agot kell megadott ar´anyban felosztani, ´es minden r´esztvev˝o c´elja, hogy min´el t¨ obbet kapjon. A feladat neh´ezs´ege abb´ol sz´armazik, hogy a j´at´ekosok egym´ast´ol k¨ ul¨onb¨ oz˝ o m´odon ´ert´ekelik az adott j´osz´agot, ´ıgy szerencs´es esetben az is el˝ofordulhat, hogy mindenki jelent˝ osen t¨ obbet kap ann´ al, mint ami jog szerint j´ ar neki. A teljes kutat´ as sor´ an t¨ obb u ´j igazs´ agosan oszt´o algoritmus sz¨ uletett. Az egyenl˝oen ar´anyban oszt´o Boldogs´ ag az Egyenjog´ us´ agban Algoritmus (BEA) megalkot´as´aval az optim´alis v´ag´assz´am´ u Oszd Meg ´es Uralkodj Algoritmus (OMUA) elveinek tov´abbfejleszt´ese volt a c´el annak ´erdek´eben, hogy egyfel˝ol elker¨ ulj¨ uk a passz´ıv j´ at´ekos szerep´et, m´asr´eszt mindenki egyenl˝o es´ellyel kapjon t¨obbet a jogos r´esz´en´el. Az osztozkod´asunk er˝ osen igazs´ agos, vagyis mindenki szigor´ uan t¨obbet kap az igazs´agos r´esz´en´el, ha az els˝o jel¨ol´eskor mindenki m´ashol szeretn´e elv´agni a tort´at. Ezek a tulajdons´agok u ´gy ´erhet˝ok el, hogy a v´ag´assz´am egy line´ aris taggal b˝ ov¨ ul, ami az optim´alis O(n · log n) nagys´agrenden nem v´altoztat, ´ıgy a BEA k¨ozel optim´ alis marad. A R´eszv´enyt´ arsas´ ag Feloszt´ as Algoritmus (melyben az ¨osszk¨ovetel´es n) sikeresen v´egzi el a k-szem´elyes nemegyenl˝ o ar´any´ u osztozkod´ ast. Ugyan´ ugy ¨osszehasonl´ıthat´o az Oszd Meg ´es Uralkodj Algoritmussal, mint BEA. A nemegyenl˝ o oszt´ as visszavezethet˝o az OMUA-ra, ´es ezzel O(n·log n) nagys´agrend˝ u v´ag´assz´ammal v´egezhetj¨ uk el az osztozkod´ast. Az RTFA(k) v´ag´assz´am´anak nagys´agrendje O(2k · log n), 41
´ıgy elmondhat´o, hogy ha az o ovetel´es nagyobb, mint 2k , akkor az RTFA(k) jobban teljes´ıt, mint ¨sszk¨ az OMUA. Megeml´ıtj¨ uk, hogy az RTFA(k) v´ag´assz´am´ara adott fels˝o becsl´es k¨ozel sem ´eles. A j¨ov˝obeli kutat´ omunka c´elja, hogy az RTFA(k) v´ag´assz´am´ara ´elesebb becsl´est tal´aljunk, hiszen a T¨ obbszem´elyes Nemegyenl˝ oen Oszt´ o Algoritmus (TNOA) v´ag´assz´ama O(k 2 ·log n), ami nagys´agrenddel kisebb az RTFA(k)-´en´ al.
Sebesty´ en Tam´ as ¨ P´ecsi Tudom´ anyegyetem, K¨ ozgazdas´ agtudom´ anyi Kar, K¨ ozgazdas´ agtan ´es Okonometria Int´ezet
Longauer D´ ora P´ecsi Tudom´ anyegyetem, K¨ ozgazdas´ agtudom´ anyi Kar, Region´ alis Politika ´es Gazdas´ agtan Doktori Iskola
H´ al´ ozati szerkezet, endog´ en preferenci´ ak ´ es egyens´ uly egy egyszer˝ u cseremodellben A f˝o´aram´ unak sz´ am´ıt´ o k¨ ozgazdas´ agtani modellek k´et gyakran haszn´alt premissz´aja a szerepl˝ok teljes inform´alts´aga a piaci folyamatokr´ ol, valamint a preferenci´ak adotts´aga, exog´en volta. Ezek a feltev´esek j´ol kezelhet˝o modellekre vezetnek, azonban fontos k´erd´es megvizsg´alni, hogy a feltev´esek old´asa mennyiben befoly´asolja a modellb˝ ol kapott eredm´enyek robosztuss´ag´at. A tanulm´anyban azt vizsg´ aljuk, hogy e k´et alapfeltev´es old´asa egyoldal´ uan, illetve egym´assal k¨olcs¨onhat´asban mik´eppen befoly´ asolja a szerepl˝ok k¨oz¨otti cser´ek dinamik´aj´at ´es eredm´eny´et. A vizsg´alatot egy mikro¨okon´omiai cseremodell kontextus´ aban v´egezz¨ uk el, amelybe egyr´eszt szelekt´ıv csereh´al´ozatot ´ep´ıt¨ unk be, m´asr´eszt pedig a szerepl˝ ok preferenci´ait endog´enn´e tessz¨ uk oly m´odon, hogy azok egym´as megfigyelt k´eszleteit˝ ol f¨ uggenek. A preferenci´ak endogenit´as´at szint´en egy h´al´ozat ment´en modellezz¨ uk, ami a cser´ekhez hasonl´ oan a szerepl˝ ok rendelkez´es´ere ´all´o inform´aci´ok szelektivit´as´at k´epes megjelen´ıteni. A modellben azt vizsg´ aljuk, hogy a Pareto-optimum kialakul´as´at ´es az optimumban l´etrej¨ov˝o k´eszleteloszt´ast mik´eppen befoly´ asolja (i) a cserh´ al´ozat szerkezete, (ii) a preferenci´ak endogenit´as´at biztos´ıt´o h´al´ozat szerkezete, valamint (iii) a k´eszletek kezdeti eloszt´asa. A h´al´ozati szerkezet szempontj´ab´ol megvizsg´aljuk, hogy mik´eppen hat az eredm´enyekre a k´etf´ele h´al´ozat s˝ ur˝ us´ege, azok kisvil´ag jellege, valamint sk´alaf¨ uggetlens´ege. Az indul´ o k´eszletek kapcs´an egyenletes, egym´odusz´ u valamint k´etm´odusz´ u eloszl´asokat vizsg´alunk. Az el˝ozetes eredm´enyek azt mutatj´ ak, hogy h´al´ozati szerkezet szerepe nem elhanyagolhat´o. A cserelehet˝os´egeket meghat´ aroz´ o h´ al´ ozat szempontj´ab´ol az sz´am´ıt, hogy a kapcsolatok min´el nagyobb h´anyada ellent´etes ig´eny˝ u ´agensek k¨ oz¨ ott l´etezzen, ami miatt a cserekapcsolatok v´eletlen h´al´ozati szerkezete szolg´alja a leghat´ekonyabban az egyens´ ulyi eloszt´ asban az egyenl˝os´eget. Ha viszont a kapcsolatrendszereknek az egy´eni preferenci´ akat befoly´ asol´ o hat´ as´ at vizsg´aljuk, akkor a kisvil´ag-t´ıpus´ u h´al´ozatok n¨ovelik legnagyobb m´ert´ekben az egyen´ert´ek˝ u cser´ek val´ osz´ın˝ us´eg´et.
Solymosi Tam´ as Budapesti Corvinus Egyetem
A per-capita nukleolusz kisz´ am´ıt´ asa hozz´ arendel´ esi j´ at´ ekokban Bemutatunk egy er˝ osen polinomi´ alis algoritmust egy hozz´arendel´esi j´at´ek per-capita nukleolusz´anak a kisz´am´ıt´as´ara. Az algoritmus a k¨ ovetkez˝ o eredm´enyekre ´ep¨ ul: – Solymosi (2016) megmutatta, hogy b´armely kiegyens´ ulyozott j´at´ek per-capita nukleolusz´anak kisz´am´ıt´asakor elegend˝ o csak a du´ alis j´at´ekban l´enyeges koal´ıci´okat tekinteni; 42
– N´ unez ´es Solymosi (2017) bizony´ıtott´ ak, hogy egy hozz´arendel´esi j´at´ek du´alis j´at´ek´aban csak az egyelem˝ u ´es a vegyesp´ aros koal´ıci´ ok lehetnek l´enyeges koal´ıci´ok; unez ´es Solymosi (2017) megadtak egy polinom sok elemi m˝ uveletb˝ol ´all´o olyan elj´ar´ast, ami– N´ vel a hozz´ arendel´esi j´ at´ekot meghat´ aroz´ o alapm´atrixb´ol megkapjuk az egyelem˝ u ´es a vegyesp´aros koal´ıci´ok du´ alis j´ at´ekbeli ´ert´ek´et. A bemutatott per-capita nukleolusz algoritmus a hozz´arendel´esi j´at´ek magj´anak du´alis le´ır´as´at haszn´alja, egy´ebk´ent t¨ obb fontos jellemz˝ oj´eben hasonl´ıt Solymosi ´es Raghavan (1994) er˝osen polinomi´alis algoritmus´ara, amivel egy hozz´arendel´esi j´at´ek standard nukleolusz´at lehet kisz´am´ıtani. Hivatkoz´ asok [1] N´ unez, M.; Solymosi, T. (2017): Lexicographic allocations and extreme core payoffs: the case of assignment games, Annals of Operations Research (First online 2017.02.14.), pp. 1–24. [2] Solymosi, T. (2016): Weighted nucleoli and dually essential coalitions. Corvinus Economics Working Papers 12/2016, http://unipub.lib.uni-corvinus.hu/2480/1/cewp_201612.pdf. [3] Solymosi, T.; Raghavan, T. E. S. (1994): An algorithm for finding the nucleolus of assignment games, International Journal of Game Theory, 23(2):119–143.
Szak´ al Szilvia Budapesti Corvinus Egyetem, Matematika Tansz´ek
Nagy Bal´ azs Budapesti Corvinus Egyetem, Matematika Tansz´ek
V´ alaszt´ okeru anak vizsg´ alata ¨ letek alakj´ A gerrymandering a v´ alaszt´ oker¨ uletek politikai elfogults´ag szerinti ´atrajzol´asa. Sz´amos m´ert´ek l´etezik s´ıkbeli alakzatok bizonyos tulajdons´ againak vizsg´alat´ara, de az ide´alis v´alaszt´oker¨ ulet form´at neh´ez lenne meghat´arozni. Kutat´ asunkban, a k´epfeldolgoz´as eszk¨ozeinek a seg´ıts´eg´evel, n´eh´any amerikai ´allam v´alaszt´oker¨ ulet´enek alakj´ at ´es az id˝ ok¨ oz¨ onk´ent el˝ofordul´o v´altoztat´asok hat´as´at vizsg´aljuk. C´elunk egy olyan elj´ar´as l´etrehoz´ asa, amellyel a manipul´aci´o sz´and´eka hat´ekonyan kisz˝ urhet˝o a v´alaszt´oker¨ uletek u ´jrarajzol´as´an´al. Hivatkoz´ asok [1] Lee, D. R., & Sallee, G. T. (1970). A method of measuring shape, Geographical Review, 555–563. [2] Rosin, P. L., & Mumford, C. L. (2006). A symmetric convexity measure, Computer Vision and Image Understanding, 103(2), 101–111. [3] Zunic, J., Hirota, K., & Rosin, P. L. (2010). A Hu moment invariant as a shape circularity measure, Pattern Recognition, 43(1), 47–57.
43
Sz´ antai Tam´ as BME TTK Differenci´ alegyenletek Tansz´ek
Az egyu osz´ın˝ us´ eg eloszl´ as hat´ asa a val´ osz´ın˝ us´ eggel korl´ atozott ¨ ttes val´ sztochasztikus programoz´ asi feladat optimum ´ ert´ ek´ ere Az el˝oad´asban megmutatom, hogy mekkora k¨ ul¨onbs´egek lehetnek az egy¨ uttes val´osz´ın˝ us´eggel korl´atozott sztochasztikus programoz´ asi feladat optimum ´ert´ekei k¨oz¨ott, ha az egy¨ uttes val´osz´ın˝ us´eg eloszl´as egydimenzi´os peremeloszl´ asainak ugyanaz a v´arhat´o ´ert´eke ´es sz´or´asa, de k¨ ul¨onb¨oz˝o a k¨ozt¨ uk l´ev˝o korrel´aci´o. Ugyanezt fogom megvizsg´ alni arra az esetre is, amikor az egydimenzi´os peremeloszl´asainak nem csak a v´arhat´o ´ert´eke ´es sz´ or´ asa azonos, hanem m´eg a k¨ozt¨ uk l´ev˝o korrel´aci´o is ugyanaz, de m´as az egy¨ uttes val´osz´ın˝ us´eg eloszl´ as jellege (norm´ alis, gamma, Dirichlet vagy t¨obbdimenzi´os kopulaf¨ uggv´enyek ´altal gener´alt). Az el˝ oad´ assal arra szeretn´em felh´ıvni a figyelmet, hogy mennyire jelent˝os az az u ´j szeml´elet, amelyet ezen a ter¨ uleten Pr´ekopa Andr´ as az 1970-es esztend˝ok kezdet´en kialak´ıtott. Az el˝oad´as t¨obb kor´abbi el˝oad´asom eredm´enyeire ´ep¨ ul. Az el˝ oad´ast Pr´ekopa Andr´as eml´ek´ere aj´anlom.
Sziklai Bal´ azs K¨ ozgazdas´ agtudom´ anyi Int´ezet, MTA
Hogyan v´ alasszunk ki szak´ ert˝ oket? A csoportidentifik´ aci´ os probl´em´ aban adott n egy´en ´es meg szeretn´enk hat´arozni, hogy ki tartozik bele egy adott csoportba. Ehhez rendelkez´esre ´all az egy´enek egym´asr´ol (´es magukr´ol) alkotott v´elem´enye, amelyet egy n-dimenzi´ os 0-1 vektor form´ aj´ aban k¨oz¨olnek. Kasher ´es Rubinstein h´ıres cikk¨ ukben az ¨onbevall´asra, mint kiv´ alaszt´ asi szab´ alyra adtak egy meggy˝oz˝o karakteriz´aci´ot. Az ¨onbevall´as val´oban j´ol m˝ uk¨odik, ha a csoport az egy´enek bels˝ o meggy˝oz˝od´ese (pl. nemzets´eg, vall´as) ment´en szervez˝odik, de kev´esb´e hat´ekony, ha l´etezik valamilyen objekt´ıv szempont, ami alapj´an be lehet sorolni, hogy ki tartozik bele a csoportba (pl. a legjobb sakkoz´ ok, h´ıress´egek, sz´ep l´anyok). El˝oad´asunkban felv´azolunk egy algoritmust, amely egy k¨ oz¨ oss´egben valamilyen szempontb´ol kulcsszerepet bet¨olt˝o szem´elyeket tudja azonos´ıtani. Bemutatjuk, hogyan lehet az algoritmus seg´ıts´eg´evel szak´ert˝oket kiv´alasztani egy hivatkoz´asi h´al´ozaton, valamint elm´eleti szempontb´ ol, axiomatikusan is al´at´amasztjuk.
44
Tak´ acs Petra Ren´ ata Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem; Babes-Bolyai Tudom´ anyegyetem
Darvay Zsolt Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem; Babes-Bolyai Tudom´ anyegyetem
Ill´ es Tibor Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem; Babes-Bolyai Tudom´ anyegyetem
Nem megengedett ind´ıt´ as´ u bels˝ opontos algoritmusok A line´aris programoz´ asi feladatok megold´ as´ ara a bels˝opontos m´odszerek a legjobb elm´eleti hat´ekonys´aggal rendelkez˝o algoritmusok. Ezekben az algoritmusokban a kezdeti pontok megv´alaszt´asa neh´ezs´eget okozhat. Erre a probl´em´ ara a Ye, Todd ´es Mizuno [6], illetve Terlaky [4] ´altal bevezetett ¨ondu´alis be´agyaz´as technik´aja adhat megold´ ast egy nagyobb m´eret˝ u feladatba val´o be´agyaz´as ´altal. Ez a technika eld¨onti, hogy az eredeti feladat megengedett-e vagy sem, ´es egy teljesen centr´alis kezdeti pontot hat´aroz meg. Ennek a m´odszernek a hat´ekonys´ ag´ at a feladat megn¨ovekedett m´erete ´es strukt´ ur´aja befoly´asolja. Ez´ert a gyakorlatban ´altal´ aban a nem megengedett ind´ıt´as´ u bels˝opontos m´odszereket alkalmazz´ak. A kezdeti pontokat k¨ ul¨onb¨ oz˝ o heurisztikus m´odszerekkel lehet meghat´arozni. Ezek k¨oz¨ ul az egyik leghat´ekonyabb a Mehrotra [2] ´altal megadott elj´ ar´ as. Az els˝o nem megengedett ind´ıt´ as´ u algoritmusokra vonatkoz´o eredm´enyek Lustig [1] ´es Tanabe [3] nev´ehez f˝ uz˝odnek. Zhang [7] adott meg els˝ ok´ent egy nem megengedett ind´ıt´as´ u bels˝opontos algoritmust, amely polinom id˝ oben hat´ aroz meg egy k¨ ozel´ıt˝o megold´ast. Az elm´eletben a nem megengedett ind´ıt´as´ u bels˝opontos algoritmusoknak k´etf´ele le´ all´ asi krit´eriumuk van. Az egyik az, hogy a m´odszer tal´al εoptim´alis fizibilis megold´ ast. A m´asik pedig bizony´ıtja az approxim´alt Farkas lemm´at felhaszn´alva, hogy nincs megengedett megold´ as [5]. A gyakorlatban viszont ´altal´aban azt tartj´ak a nem megengedetts´eg bizony´ıt´ek´anak, ha el´egg´e megn˝ ottek a koordin´ at´ak. Ez´ert ennek a krit´eriumnak az elm´eleti ´es gyakorlati vonatkoz´asait is elemezz¨ uk. Hivatkoz´ asok [1] I. J. Lustig, Feasibility issues in a primal-dual interior-point method for linear programming, Math. Program., 49(1–3):145–162, 1990. [2] S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2(4):575–601, 1992. [3] K. Tanabe, Centered Newton method for linear programming: Interior and ‘exterior’ point method, in: K. Tone, editor, New Methods for Linear Programming, volume 3, pages 98–100. 1990. In Japanese. [4] T. Terlaky, An easy way to teach interior-point methods, Eur. J. Oper. Res., 130(1):1–19, 2001. [5] M. J. Todd and Y. Ye, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, Mathematical Programming, 81(1):1–21, 1998. √ [6] Y. Ye, M. J. Todd and S. Mizuno, An O( nL)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19:53–67, 1994. [7] Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4(1):208–227, 1994.
45
T´ oth Attila Szegedi Tudom´ anyegyetem, Juh´ asz Gyula Pedag´ ogusk´epz˝ o Kar, Informatika Alkalmaz´ asai Tansz´ek
Tesztp´ eld´ ak gener´ al´ asa nyomtatott ´ aramk¨ or¨ oket ¨ osszeszerel˝ o g´ epsor konfigur´ al´ asi ´ es u temez´ e si probl´ e m´ a hoz ¨ A mai vil´agban a nyomtatott ´aramk¨ or¨ ok gy´art´asa az elektronikai ipar egyik frekvent´alt ´es dinamikusan fejl˝od˝o ter¨ ulete. A legt¨ obb elektronikai eszk¨oz nyomtatott ´aramk¨orre ´ep¨ ul, melyek fel´ep´ıt´ese, m´erete ´es ¨osszet´etele rendk´ıv¨ ul v´ altozatos. A komoly piaci versenyben a gy´art´as hat´ekonys´ag´anak n¨ovel´ese kiemelt k´erd´es. Mivel a g´epek rendk´ıv¨ ul dr´ ag´ ak, jellemz˝oen a g´epek sz´ama ´es fajt´aja r¨ogz´ıtett. A gy´art´as hat´ekonys´ag´at csak u ´gy lehet n¨ ovelni, hogy a termel´ekenys´eget jav´ıtjuk a gy´art´asi folyamat sebess´eg´enek n¨ovel´es´evel. A gy´art´ asi folyamat legkritikusabb r´esze az ´aramk¨or ¨osszeszerel´ese, amikor egy g´epsor az el˝ok´esz´ıtett lapra helyezi a megfelel˝ o komponenseket. A mai, korszer˝ u ilyen g´epsor modulok el´eg flexibilisek, hogy az ig´enyeknek megfelel˝ oen lehessen konfigur´alni. Emiatt a probl´ema el´eg komplex, ´ıgy hat´ekony gy´art´ osort ´ep´ıteni komoly kih´ıv´ as. Az ¨osszeszerel´esi folyamat ¨ osszetett ´es t¨obb, k¨ ul¨on-k¨ ul¨on is neh´ez r´eszfeladatb´ol ´all. A szakirodalomban jellemz˝ oen a probl´em´ at egy adott n´ez˝opontb´ol k¨ozel´ıtik meg ´es csak egy-k´et r´eszprobl´em´ara koncentr´alnak, emiatt a megold´ asok glob´ alis ki´ert´ekel´ese ´es ¨osszehasonl´ıt´asa neh´ez. A ma legn´epszer˝ ubb u ´n. collect-and-placement g´epek t¨ obb alkatr´esze is cser´elhet˝o, konfigur´alhat´o, ez´altal a gy´artand´o term´ekek ig´enyeihez igaz´ıthat´ o. A piaci ig´enyek ellen´ere az ilyen g´epek hat´ekony konfigur´al´as´aval nagyon kevesen foglalkoztak. Az ilyen neh´ez feladatokhoz kidolgozott algoritmusok ki´ert´ekel´es´et leggyakrabban tesztp´eld´akon v´egzett futtatat´ asok statisztikai elemz´es´evel v´egzik. Ez a m´odszer viszont jelent˝osen f¨ ugg a haszn´alt tesztp´eld´akt´ol. A nyomtatott ´aramk¨ or¨ ok gy´art´asa eset´en a term´ekek fel´ep´ıt´ese ipari titoknak min˝os¨ ul, gyakran m´eg elemz´esre se haszn´ alhatj´ ak a kutat´ok. A haszn´alt ipari mintafeladatok pedig ´altal´aban csak egy sz˝ uk szelet´et fedik a val´ os ´eletben el˝ofordul´o probl´em´aknak. A v´eletlenszer˝ uen gener´alt p´eld´ak v´eletlenszer˝ u eredm´enyt adnak, ´ıgy az algoritmus ezeken val´o ki´ert´ekel´ese teljesen val´otlan is lehet. Jelen munka c´elja olyan m´ odszer kidolgoz´asa, amellyel olyan p´elda probl´em´ak k´esz´ıthet˝oek az ¨osszeszerel˝o g´epek konfigur´ al´ asi probl´em´ ahoz, amelyek neh´ezs´ege, ¨osszetetts´ege j´ol sk´al´azhat´o. Ez´altal az ´ıgy gener´alt probl´ema gy˝ ujtem´eny alkalmas arra, hogy a feladatra kidolgozott b´armilyen algoritmus ki´ert´ekel´ese val´os ´es ¨osszehasonl´ıthat´ o legyen.
Tu ˝ -Szab´ o Boldizs´ ar ¨u Sz´echenyi Istv´ an Egyetem, Informatika Tansz´ek, Gy˝ or
F¨ oldesi P´ eter Sz´echenyi Istv´ an Egyetem, Logisztika Tansz´ek, Gy˝ or
K´ oczy T. L´ aszl´ o Sz´echenyi Istv´ an Egyetem, Informatika Tansz´ek, Gy˝ or; Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem, T´ avk¨ ozl´esi ´es M´ediainformatikai Tansz´ek, Budapest
Diszkr´ et Bakteri´ alis Memetikus Evol´ uci´ os Algoritmus ¨ az Utaz´ o Ugyn ok Probl´ ema megold´ as´ ara ¨ ¨ Az Utaz´o Ugyn¨ ok Probl´ema az NP-neh´ez probl´em´ak oszt´aly´aba tartozik, ez´ert jelenlegi tud´asunk szerint nincs olyan polinom idej˝ u algoritmus, amely ezt a probl´em´at meg tudn´a oldani. A probl´ema heurisztikus m´odszerekkel kezelhet˝ o hat´ekonyan, amelyek elfogadhat´o id˝on bel¨ ul biztos´ıtanak optim´alis, illetve k¨ozeloptim´alis megold´ asokat. Az el˝oad´as sor´ an szeretn´enk bemutatni az ´altalunk kifejlesztett Diszkr´et Bakteri´alis Memetikus Evol´ uci´os Algoritmust (DBMEA), amelyet eddig metrikus ´es szimmetrikus referenciaprobl´em´akon tesztelt¨ unk [1], [2]. A DBMEA egy memetikus algoritmus, amelyn´el a bakteri´alis evol´ uci´os algoritmust 2-opt 46
illetve 3-opt lok´alis keres´essel eg´esz´ıtett¨ uk ki. K´es˝obb az algoritmust tov´abbfejlesztett¨ uk a lok´alis keres´es keres´esi tartom´ any´ anak sz˝ uk´ıt´es´evel [3], valamint az algoritmus p´arhuzamos´ıt´as´aval. Az algoritmust 0-5000 pontb´ol ´all´ o referenciaprobl´em´ akon tesztelt¨ uk. Az optim´alis megold´ast´ol val´o elt´er´es a legnagyobb vizsg´alt probl´ema eset´en is 0,2%-on bel¨ ul maradt. A fut´asid˝o tekintet´eben a DBMEA az esetek t¨obbs´eg´eben gyorsabb megold´ ast biztos´ıtott, mint a Concorde (optim´alis megold´ast biztos´ıt´o m´odszer) algoritmus. A f˝o el˝ onye a DBMEA-nak a prediktabilit´as, a fut´asid˝o a probl´emam´eretb˝ol j´ol megbecs¨ ulhet˝o. A Concorde algoritmusr´ ol ez nem mondhat´o el, hiszen a pontok elhelyezked´ese nagyban befoly´asolja a fut´asid˝ot, azonos probl´emam´eret eset´en ak´ar t¨obb nagys´agrend˝ u elt´er´es is lehet a fut´asid˝ok k¨oz¨ott a Concorde eset´eben. Hivatkoz´ asok [1] L. T. K´ oczy, P. F¨ oldesi, B. T¨ uu ˝-Szab´ o: A Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem, in: IEEE World Congress on Computational Intelligence (WCCI 2016), Vancouver, Kanada, 2016.07.25–2016.07.29. New York: IEEE, 2016. pp. 3261–3267. [2] L. T. K´ oczy, P. F¨ oldesi, B. T¨ uu ˝-Szab´ o: An effective Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem, in: International Journal of Intelligent Systems, 2017, accepted, available online: http://onlinelibrary.wiley.com/doi/10.1002/int.21893/full. uu ˝-Szab´ o, P. F¨ oldesi, L. T. K´ oczy: Improved Discrete Bacterial Memetic Evolutionary Algorithm for the [3] B. T¨ Traveling Salesman Problem, in: Somnuk Phon-Amnuaisuk, Thien-Wan Au, Saiful Omar: Proceedings of the Computational Intelligence in Information Systems Conference (CIIS 2016). 308 p., Bandar Seri Begawan, Brunei, 2016.11.18–2016.11.20. Bandar Seri Begawan: Springer International Publishing, 2017. pp. 27–38. (Advances in Intelligent Systems and Computing; 532.) Computational Intelligence in Information Systems.
Vink´ o Tam´ as Szegedi Tudom´ anyegyetem, Sz´ am´ıt´ og´epes Optimaliz´ al´ as Tansz´ek
H´ al´ ozat alap´ u differential evolution A differential evolution egy glob´ alis optimaliz´al´asi m´odszer, amely n´epszer˝ us´eg´et a sz´amos alkalmazott ter¨ uleten kimutatott hat´ekonys´ ag´ anak ´es egyszer˝ u implement´alhat´os´ag´anak k¨osz¨onheti. Az elj´ar´as iterat´ıv, popul´aci´o alap´ u, ´es deriv´altmentes, teh´at csak az optimaliz´aland´o c´elf¨ uggv´eny ´ert´ek´et haszn´alja. Az eredeti v´altozatban, nagyvonalakban, minden iter´aci´os l´ep´esben v´eletlenszer˝ uen v´alasztunk h´arom, egym´ast´ol k¨ ul¨onb¨ oz˝ o elemet a popul´ aci´ ob´ ol, majd azokb´ol egy alkalmas k´eplet felhaszn´al´as´aval k´esz´ıt¨ unk egy u ´j, lehets´eges megold´ ast. Az el˝ oad´ asban ennek a v´alaszt´asnak az alternat´ıv lehet˝os´egeit vizsg´aljuk. Az alap¨otlet, hogy a popul´ aci´ o elemeit tekints¨ uk egy gr´af cs´ ucspontjainak, amelyeket ´elekkel k¨ot¨ unk utt szerepelnek a kiv´ alasztott h´armasban. Az ´ıgy ´ep¨ ul˝o gr´afb´ol cs´ ucsot nem t¨or¨ossze, amennyiben egy¨ l¨ unk. Amennyiben m´ ar elegend˝ oen nagym´eret˝ u a gr´afunk, a cs´ ucsokat rendezz¨ uk fontoss´agi sorrendbe, haszn´alva ehhez p´eld´ aul a PageRank vagy m´as hasonl´o elj´ar´ast. Az u ´j egyed el˝o´all´ıt´as´ahoz haszn´aljuk a legfontosabb cs´ ucsokat. Vajon ez az algoritmus v´altozat hat´ekonys´ag n¨oveked´eshez vezet? El˝oad´asunkban bemutatjuk az elv´egzett numerikus teszteket a v´alasz megad´as´ara.
47
Vo ozsef ¨ro ¨s J´ P´ecsi Tudom´ anyegyetem
Rappai G´ abor P´ecsi Tudom´ anyegyetem
Hauck Zsuzsanna P´ecsi Tudom´ anyegyetem
A folyamatmin˝ os´ eg jav´ıt´ as´ anak sorozatnagys´ agra gyakorolt hat´ as´ ar´ ol JIT k¨ ornyezetben, b´ eta eloszl´ ast k¨ ovet˝ o kapacit´ askihaszn´ al´ as eset´ en Just-In-Time k¨ ornyezetben a jidoka elv ´ertelm´eben a dolgoz´okat felhatalmazz´ak arra, hogy jelezz´ek az ´eszlelt min˝os´egi probl´em´ akat. Mindez a szerel˝oszalag gyakori meg´all´ıt´as´ahoz vezet. Ennek ok´an a kibocs´atott mennyis´eget b´eta eloszl´ as´ u val´ osz´ın˝ us´egi v´altoz´oval ´ırjuk le, ahol b´eta ´ert´eke alacsony. Bizonyos b´eta ´ert´ekekre explicit megold´ ast mutatunk be a k´eszletez´essel kapcsolatos ´eves ¨osszk¨olts´egre, a b´eta eloszl´ as m´asik param´etere, alfa f¨ uggv´eny´eben. Alfa n¨oveked´ese a folyamatmin˝os´eg javul´as´at jelenti. Meg´allap´ıt´asaink szerint a n¨ ovekv˝ o folyamatmin˝os´eg cs¨okkenti a v´arhat´o ´eves ¨osszk¨olts´eget, ´es az explicit form´ak megmutatj´ ak ezen megtakar´ıt´ as m´ert´ek´et. K´et szimul´aci´o seg´ıts´eg´evel elemezz¨ uk az ´eves ¨osszk¨olts´eg varianci´ aj´ anak alakul´ as´at. Az elv´egzett becsl´esek alapj´an a folyamatmin˝os´eg javul´as´aval cs¨okken az ´eves ¨osszk¨olts´eg minimum´ anak varianci´ aja. Kulcsszavak: JIT, folyamatmin˝ os´eg, sztochasztikus sorozatnagys´ ag, h´ atral´ek, b´eta eloszl´ as.
48
