ALKALMAZOTT MATEMATIKAI LAPOK 25. KÖTET (A MTA Matematikai Tudományok Osztályának Közleményei, 2008)

2008 / 1. sz. - SCHRIJVER, ALEXANDER: Szemelvények a kombinatorikus optimalizálás történetéből (1960-ig)

2 ALEXANDER SCHRI.JVER Mindezen problémák nyomait valószínűleg megtaláljuk az egészen távoli törté­nelemben. A jelen tanulmány azonban a fenti kérdéseknek csupán a matema­tikai megközelítéseit tárgyalja. Az áttekintett időhorizont másik széle 1960-ig nyúlik, így a feldolgozott anyag még kézben tartható marad. Ennek az a következ­ménye, hogy fontos későbbi eredmények, mint például a párosítások és a matroidok elmélete Edmonds munkája nyomán vagy Cook és Karp bonyolultságelmélete (az NP-teljesség) kimaradnak a tanulmányból. A továbbiakban az alábbi hat területet vizsgáljuk meg tüzetesebben: a hoz­zárendelési, a szállítási, a maximális folyam, a minimális költségű feszítőfa, a leg­rövidebb út és végül az utazó ügynök problémát. 2. A hozzárendelési probléma A hozzárendelési probléma formálisan a következőképpen fogalmazható meg: egy adott n x n méretű С › (citi) „költségmátrixhoz" találjuk meg az l,...,n számok egy olyan тг permutációját, melyre a összeg a lehető legkisebb. Monge (1784) A hozzárendelési probléma az egyik legelsőként vizsgált kombinatorikus opti­malizálási probléma. G. Monge [1784] egy folytonos problémának „álcázott", gyak­ran szállítási feladatnak nevezett változatát tanulmányozta. Monge kiindulási feladata a földszállítás volt,­­ ezt egy molekulák áthelyezé­sére vonatkozó diszkrét kombinatorikus problémának tekintette. Két azonos terü­letű tartomány közül az egyik tele van földdel, a másik üres. A cél, hogy az első tartományból a földet úgy vigyük át a másodikba, hogy eközben az össz-szállítási út a lehető legkisebb legyen. Az össz-szállítási út alatt pedig a „földmolekulák" által megtett összutat értjük, így tehát egy hatalmas költségmátrixszal rendelkező hozzárendelési problémát kapunk. Monge az alábbiak szerint írta le a problémát: Lorsqu'on doit transporter des terres d'un lieu dans un autre, on a coutime de donner le nom de Déblai au volume des terres que l'on doit transporter, & le nom de Remblai à l'espace qu'elles doivent occuper après le transport. Le prix du transport d'une molécule étant, toutes choses d'ailleurs égales, propor­tionnel à son poids & à l'espace qu'on lui fait parcourir, & par conséquent le prix du transport total devant être proportionnel à la somme des produits des molécules multipliées chacune par l'espace parcouru, il s'ensuit que le déblai & le remblai étant donnés de figure & de position, il n'est pas indifférent que telle molécule du déblai soit transportée dans tel ou tel autre endroit du remblai, mais qu'il y a une certa­ine distribution à faire des molécules du premier dans le second, d'après laquelle la n ci,n(i) i= 1 Alkalmazott Matematikai Lapok (2008)

Next