16.2. 16.2. A „magyar módszer” eredetéről

A történeti hűséghez hozzátartozik, hogy a „magyar módszert” H. W. KUHN 1955-ben [ 10 ] a hozzárendelési feladat megoldására fejlesztette ki. Mivel a szállítási feladat a hozzárendelési feladat általánosításaként kezelhető, így a szállítási feladat megoldására is alkalmas. A jegyzetbeli tárgyalásban a „magyar módszert” szállítási feladatra ismertettük és a szállítási feladat speciális esetére, a hozzárendelési feladatra csupán alkalmazzuk.

Mivel a módszernek magyar vonatkozása van, érdemes a "magyar módszer" eredetéről a felfedezőnek az 1991-ben megjelent, a Matematikai programozás történetéről c. könyvben [ 6 ] írt visszaemlékezéséből idézni.

”... A történet 1953 nyarán kezdődik, amikor ...”. A szószerinti idézés helyett röviden összefoglaljuk a cikkben foglaltakat.

Ebben az időben H. W. KUHN a Bryn Mawr College-ban dolgozott és a nyári szünetben több kíváló kombinatorikust és algebristát hívtak meg a Kaliforniai Egyetemre, többek között KUHN-t is. A nyár folyamán C. B. TOMPKINS egy -es hozzárendelési feladatot próbált megoldani az akkori időszak egyik legjobb számítógépének (SWAC) segítségével az összes permutáció leszámlálásával. Egyetlen próbálkozása sem járt sikerrel.

A cikk ezen részében KUHN a hozzáredelési feladatot lineáris programozási feladatként írja fel, a célfüggvényben szereplő együtthatókat -vel jelölve és maximum problémaként megfogalmazva.

Ebben az időszakban KŐNIG DÉNES klasszikus művét [ 9 ] olvasta KUHN és rájött, hogy egy gráf két darab egyenként pontból álló részre particionálása és a két rész közötti párosítás problémája pontosan megegyezik egy olyan -es hozzárendelési feladattal, ahol az mátrix minden eleme vagy vagy . De még ennél is fontosabb volt KUHN számára, hogy KŐNIG DÉNES megadott egy olyan kombinatorikus algoritmust, amellyel meghatározhatók voltak a párosítási problémának és kombinatorikus duáljának az optimális megoldásai. KUHN a cikkben e helyen a már klasszikusnak számító KŐNIG-EGERVÁRY tételt ([ 9 ], 240. oldal, D Tétel) fogalmazza meg. KUHN megjegyzi: Ezek után már csak a következő probléma megoldása maradt hátra: hogyan lehet az általános hozzárendelési feladatot 0-1 típusúra visszavezetni?

Figyelmesebben olvasva KŐNIG DÉNES könyvét [ 9 ] KUHN felfigyelt a 238. oldalon található 2. lábjegyzetre, amely EGERVÁRY JENŐ magyar nyelvű cikkére [ 1 ] mutatott rá.. KUHN érezte, hogy a probléma megoldásának kulcsát éppen itt találhatja meg.

Amikor ősszel visszatért Kaliforniából a munkahelyére, a könyvtárból kikölcsönözte EGERVÁRY cikkének egy másolatát valamint egy nagy magyar szótár és nyelvtan könyvet. Ahogy írja: Két hétig magyarul tanult és közben lefordította Egerváry cikkét. KUHN megérzése bevált, mivel EGERVÁRY cikke valóban tartalmazott egy módszert, amelynek alapján az általános hozzárendelési feladat visszavezethető véges sok 0-1 típusú hozzárendelési feladatra. Felhasználva EGERVÁRY redukciós eljárását és KŐNIG párosítási algoritmusát 1953 őszén számos -es hozzárendelési feladat megoldását számolta ki kézzel. Mindegyik feladatot meg tudta oldani két órán belül és ez meggyőzte KUHN-t, hogy az általa javasolt kombinált algoritmus "jó". KUHN egy érdekes megjegyzést tesz: Valószínüleg ez egyike volt azon legutolsó eseteknek, amikor papirral és tollal le lehetett győzni a világ legnagyobb és leggyorsabb elektronikus számítógépét.

Végezetül KUHN megjegyzi: Hogy teljesen nyilvánvaló legyen, miszerint az általa javasolt algoritmust két magyar matematikus, KŐNIG DÉNES és EGERVÁRY JENŐ munkája inspirálta, ezért ezt az eljárást "magyar módszer"-nek nevezte el és ezen a néven is publikálta [ 10 ], [ 2 ].

Eddig a "magyar módszer" története.