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

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

ma), akkor a másiknak is van, és a két érték egyenlő. A tételt először Gale, Kuhn és Tucker bizonytíották be (10). Neumann János megmutatta, hogy egy mátrixjáték ekvivalens a lineáris programozás egy prímái — duál feladatpárjával, tehát mátrixjáték megoldására is alkalmazható a szimplex módszer. A lineáris programozás egzakt matematikai megalapozása során kiderült, hogy a matematikai előzmények megteremtésében kiemelkedő szerepe volt két magyar matematikusnak: Farkas Gyulának és (kisebb mértékben) Haar Alfrédnek. Farkas Gyula még a múlt század végén a mechanikai egyensúly problémáit vizsgálta, amikor a kényszerfeltételeket lineáris egyenlőtlenségek fejezik ki. Azt az esetet, amikor a feltételeket egyenletek fejezik ki már letárgyalta és megoldotta Lagrange a Lagrange-féle multiplikátoros módszerrel. Az egyenlőtlenségi esetet Fourier vetette fel 1798-ban és kimondta a Fourier-elvet: egyensúlyban a szabaderők összes munkája bármely virtuális elmozdulásnál kisebb vagy egyenlő, mint nulla. Az elvet kifejező egyenlőtlenség következménye a feltételi egyenlőtlenségek rendszerének. (Abban az értelemben, hogy a rendszer minden megoldása kielégíti azt.) Egyensúlyban viszont a potenciálnak (helyi) minimuma van,, ezzel eljutottunk a matematikai optimalizáció problémájához. Farkas alapvető eredménye a fentiekkel kapcsolatban a következő: ha egy (homogén lineáris) egyenlőtlenség következménye valamely (homogén lineáris) egyenlőtlenségrendszernek, akkor az kifejezhető a rendszer egyenlőtlenségeinek nem-negatív súlyokkal vett lineáris kombinációjaként. Ez a híres Farkas-tétel, melyet Farkas Gyula először mondott ki (5). A tétel különösen a dualitás elméletében játszik fontos szerepet. A bizonyítás során Farkas Gyula tulajdonképpen az ún. duál szimplex módszert alkalmazta, de nem gondolt a ciklizálás fellépésének lehetőségére, így a bizonyítás hibásnak tekinthető. A ciklizálás elkerülhető a lexikografikus duál szimplex-módszer alkalmazásával. Farkas Gyula már helyesen bizonyította tételét (más módszerrel) (6). Mégadta a homogén lineáris egyenlőtlenségi rendszerek megoldásainak paraméteres előállítását is (7). Haar Alfréd inhomogén lineáris egyenlőtlenségekre általánosította a Farkas-tételt (12). Haar tétele lényegében ekvivalens a dualitás tételével. Eredményeik sokáig nem keltettek különösebb visszhangot, jelentőségüket, az amerikai Kuhn és Tucker ismerték fel, akik a matematikai programozást elméletileg megalapozó munkájukban (18) először hivatkoztak Farkas Gyula cikkére. (8) Az idézett cikk már nem tartalmazott új eredményeket, összefoglaló jellegű volt. Az eredményeket először közlő cikkek ma sem eléggé ismertek, pedig német nyelvű változatban is megjelentek. A figyelmet rájuk először egy doktori disszertáció hívta fel (9). A nemlineáris programozás akkor indult gyors fejlődésnek, amikor megjelent Kuhn és Tucker már idézett munkája (18). Ebben bebizonyították a matematikai programozás alaptételét, a Kuhn—Tucker-tételt, amely szükséges és elégséges feltételt ad arra, hogy egy lehetséges megoldás optimalizálja a célfüggvényt. A sokirányú, napjainkban is tartó fejlődés részletes bemutatására nem vállalkozhatunk, a továbbiakban csak a főbb tendenciákat igyekszünk körvonalazni. A konvex, a hiperbolikus és a kvadratikus programozásnál a feltételi egyenlőtlenségben szereplő függvények még lineárisak, de a célfüggvény már valamely általános konvex függvény, lineáris törtfüggvény, illetve kvadratikus függvény.