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)

Alkalmazott Matematikai Lapok 25 (2008), 1-74. SZEMELVÉNYEK A KOMBINATORIKUS OPTIMALIZÁLÁS TÖRTÉNETÉBŐL (1960-IG) ALEXANDER SCHRIJVER FORDÍTOTTA: BERNÁTH ATTILA, FLEINER TAMÁS1, PAP GYULA 1. Bevezetés A kombinatorikus optimalizálás a matematika viszonylag fiatal tudományága. Kialakulását szemlélve számos, egymástól független kutatási irányt látunk, mint például az optimális hozzárendelési (optimum assignment), a minimális költségű feszítőfa (shortest spanning tree), a szállítási (transportation), a szállítmányo­zási (transshipment) vagy éppen az utazó ügynök (traveling salesman) feladatokat. E problémákat azonban csupán az 1950-es években sikerült egységes szerkezetbe foglalni és köztük további kapcsolatokat feltárni, mégpedig annak nyomán, hogy a lineáris és egészértékű programozás kifejlődésével az operációkutatás a figyelem homlokterébe került. Mert valóban: a kombinatorikus optimalizálás történetének tengelyében az a lineáris programozás áll, amit éppen kombinatorikus alkalmazások (a szállítási és szállítmányozási problémák) vizsgálata nyomán fogalmazott meg Kantorovich és Koopmans. Később, a lineáris programozás általános megalapozását követően, 1947-ben Dantzig kifejlesztette a szimplex módszert, mint a megoldás eszközét. Ennek eredményeként a kombinatorikus optimalizálási problémákat egyre inkább próbálták lineáris programozási technikával megoldani, gyakran igen sikeresen. A kombinatorikus optimalizálás gyökeres szerteágazóságának egyik oka, hogy számos olyan probléma adódik közvetlen gyakorlati alkalmazásokból, amit akkor is és ma is rutinszerűen kellett és kell tudnunk megoldani. Könnyen belátható, hogy mennyire lényeges még egy primitív társadalomban vagy akár az állatok között is, hogy legrövidebb utat találjunk, vagy például, hogy élelmet keressünk. Az utazó ügynök probléma pedig olyankor merül fel, amikor bevásárlást vagy város­nézést tervezünk, vagy amikor a beteglátogató vagy a postás tervezi az útvonalát. Hasonlóképpen: nem csupán matematikusok szembesülnek olyan elemi problémák­kal, mint az elvégzendő munkák munkások közötti elosztása, javak szállítása vagy éppen kapcsolatok létesítése. •Fleiner Tamás köszönetet nyilvánít az OTKA - 60802 támogatásnak és az MTA-ELTE Eger­váry Kutatócsoportnak. Alkalmazott Matematikai Lapok (2008)

Next