Technikatörténeti szemle 12. (1980-81)

TANULMÁNYOK - Filep László: A matematikai programozás kialakulása és fejlődése

célfüggvény maximumát valamelyik csúcspontban (extremális pontban) veheti fel. A szimplex módszer lényege az, hogy meghatározza egy csúcspontban a megoldást (bázismegoldás), majd ezt addig javítja a szomszédos csúcspontokra való ugrással amíg optimális megoldáshoz nem jutunk, vagy kimutatható, hogy nincs optimális megoldás. A szimplex módszert Dantzig először 1951-ben közölte (2), még ebben az évben sor került első ipari alkalmazására. A matematikai programozás elterjedése a különböző országokban jórészt ennek a módszernek köszönhetően következett be. A szimplex módszer mellett más módszereket is kidolgoztak az egyes speciális feladatok megoldására. Különösen nagy figyelmet keltett a „magyar módszer", amelyet 1955-ben Kuhn alkalmazott a hozzárendelési (assignment) probléma megoldására (17). A hozzárendelési problémában bizonyos számú feladatot kell szétosztani ugyanannyi vállalkozó (üzem, gép, munkás stb.) között. Mindegyik vállalkozó képes akármelyik feladat elvégzésére, de csak egy feladatot vállalhat. Ismert, hogy a vállalkozók milyen költséggel tudják az egyes feladatokat elvégezni. Keressük a legkisebb költséggel járó megoldást. A feladat az egyes költségeket tartalmazó számtáblázat (költség — mátrix) segítségével elemezhető. A megoldás abból áll, hogy minden sorból és oszlopból kiválasztunk pontosan egy elemet (ún. független elemeket) úgy, hogy a kapott költségösszeg minimális legyen. Ez nagyszámú elem esetén nem egyszerű dolog. Alkalmas számok levonásával a feladat visszavezethető maximális számú független zéruselemek keresésére. Ezek számát adja meg a Kőnig—Egerváry-tétel, melyet először Kőnig Dénes bizonyított (16), majd Egerváry Jenő általánosított (3): egy mátrixban a független zérusok maximális száma megegyezik az összes zérusokat lefedő vonalak minimális számával. (Egy fedővonal a zérust tartalmazó sort, vagy oszlopot fedi le.) A módszer jelentőségét csak növelte az, amikor Egerváry megmutatta, hogy alkalmazható a szállítási feladat megoldására is (4). A lineáris programozás elméletének fejlődésében jelentős lépés volt 1947ben a dualitás elvének bevezetése Neumann János által. Az előzőekben jellemzett lineáris programozási feladatnak (prímái feladat) megfeleltette a következő duál feladatot: az airyi + a2iy2+ ... +a

m

iy =_ ci ai

2-yi+a

22

y

2

+ • • • +a

m

2y ^ c

2 ai„yi+a

2n

y

2

+ ... +a y,40 (i =1, 2 ... m) feltételek mellett keresendő a biyi+b

2

y

2

+ ... +b

m

y

m célfüggvény minimuma. Megmutatható, hogy a duál feladat duálja az eredeti prímái feladat. Gazdasági szempontból a prímái feladat azt jelenti, hogy adott erőforrásokat kell maximális eredménnyel felhasználni, a duál feladat pedig azt, hogy adott eredményt kell minimális ráfordítással elérni. A dualitás tétele szerint, ha prímái és duál feladatok közül valamelyiknek van megoldása (optimu-