Technikatörténeti szemle 12. (1980-81)
TANULMÁNYOK - Filep László: A matematikai programozás kialakulása és fejlődése
Történetileg az első olyan munka, amely lineáris programozási problémákat tárgyalt szovjet szerzőtől származott 1939-ben (14). Kantorovics ebben a cikkében különféle termelési és elosztási problémákat modellizalt, sőt kidolgozott egy megoldási módszert is, az ún. megoldó együtthatók módszerét. Sajnos cikke ismeretlen maradt még a Szovjetunión belül is, főként az akkori helytelen, dogmatikus közgazdasági nézetek miatt. Így az amerikai F. L. Hitchock 1941-ben elért eredménye az első, amely jelentős lökést adott a lineáris programozás fejlődésének (13). Hitchock megfogalmazta és megoldotta a szállítási problémát: Adott bizonyos számú feladó és bizonyos számú felvevő. Ismertek az egyes feladóhelyek készletei és az egyes felvevőhelyek igényei. Hogyan lehet minimális költséggel eljuttatni az árut a rendeltetési helyekre? A szállítási probléma megodását az amerikai hadsereg sikeresen alkalmazta az utánpótlás szállításának megszervezésére a különböző hadszínterekre. A problémát Hitchocktól függetlenül Koopmans is megoldotta (15). A játékelmélet eredetileg olyan ún. stratégiai játékok elemzésével foglalkozott, amelyek kimenete nemcsak a szerencsétől függ. Feladata a játékosok optimális cselekvéseinek (stratégiáinak) meghatározása. Első művelői E. Borel, E. Zermelo és Kalmár László voltak. Megalapozója Neumann János volt, aki 1928ben bebizonyította a játékelmélet alaptételét: minden véges stratégiájú kétszemélyes zérus összegű játéknak (mátrix-játéknak) van megoldása, azaz mindkét játékosnak van optimális stratégiája. Optimális stratégia az, mely az ellenfél legkedvezőtlenebb ellenlépése esetén is biztosítja a maximális nyereséget (minimális veszteséget). Szokás a tételt minimax tételnek is nevezni. Az alaptételt végtelen mátrixjátékokra a szintén magyar származású Wald Ábrahám bizonyította be. Neumann János felismerte, hogy a játékelmélet segítségével sok konfliktushelyzet sikeresen modellezhető a gazdaság, a hadászat, a politika stb. területén. Az alkalmazásokat is tárgyalja a Morgensternnel együtt írt (20) könyve, mely a játékelmélet klasszikus kézikönyvének számít. A II. világháború után behatoltak a gazdasági életbe is a- lineáris programozás eszközei, és fontos új elméleti eredmények is születtek. Megfogalmazták a lineáris programozás általános feladatát: az aii -xi+ ai2X 2 + ... +ai n x n 4 bi a 2 rxi-|-a22 XÜ+ ... +a 2n x n 4b 2 a m ix 1 +a m2 x 2 + ... +a mn x n áb m 1,^0 0-1, 2, ...n) egyenlőtlenségrendszerrel megadott feltételek mellett keresendő a ClXl + C 2 X2+ ... +c n x n célfüggvény maximuma. Az amerikai Dantzig 1947-ben kidolgozta a lineáris programozási feladatok általános, számítógépre is vihető megoldási módszerét: a szimplex módszert. A feltételi egyenlőtlenségek megoldásai n dimenziós konvex poliédert alkotnak. A konvex poliéderek legegyszerűbb esetei a szimplexek. Ilyen pl. a síkban egy háromszög, térben egy tetraéder. Bebizonyítható, hogy a
