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

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

A lineáris programozás tekinthető ezek speciális esetének, megoldásukat Is igyekeznek visszavezetni a szimplex módszer valamelyik változatára, de kidolgoztak egyéb megoldási módszereket is: gradiens-módszerek, multiplex-módszer (Frisch), lehetséges irányok módszere (Zoutendijk, 1957) stb. A konvex programozás elmélete 1951—1955 között alakult ki főként Kuhn, Tucker és Beale munkássága nyomán. A hiperbolikus programozással először Martos Béla foglalkozott, tőle származik az elnevezés is (19). A kvadratikus programozás úttörői Barankin, Dorfman, Markovitz és Wolfe voltak az 1956 utáni években. Bellman 1957-ben alapozta meg a dinamikus programozást olyan problémák megoldására, melyekben nem egyszeri optimális döntés, hanem időben egymást követő optimális döntések sorozatának a megadása a feladat (1). A döntések sorozatát politikának, a döntések hasznát mérő függvényt pedig haszonfüggvénynek nevezzük. A feladat az optimális politika és haszonfüggvény megtalálása. A megoldás a Bellman-féle optimalitási elv alapján történik: egy optimális döntéssorozatnak (politikának) minden részsorozata is optimális. A dinamikus programozás körébe tartozik pl. az aranybányász-probléma. Egyetlen drága gépet kell több bányában felváltva a leghatékonyabban kihasználni, ha ismerjük az egyes bányákban valamely aranykészlet meglétének, egy része kibányászásának és a gép meghibásodásának valószínűségeit. Ez a probléma átvezet bennünket a sztochasztikus programozás területére, ahol a probléma paraméterei már nem pontos értékek, hanem valószínűségi változók. A problémák elemzése ekkor főleg valószínűségszámítási eszközökkel történik. A sztochasztikus programozás körébe tartoznak a várakozási, sorbanállási, pótlási, verseny stb. modellek. Az ötvenes évek végén alakult ki és azóta nagy fejlődésen ment keresztül az egész számú (integer) programozás. Különösen olyan gazdasági feladatokban alkalmazható, amelyekben nem osztható nagyértékű tárgyak szerepelnek, ilyenek a beruházási, felújítási, fix költséges, telepítési és ütemezési problémák. Nevezetes az utazó ügynök problémája: keressük meg a legkevésbé költséges utat egy kereskedelmi ügynök számára, akinek adott városból indulva megadott városokat kell felkeresnie, mad vissza kell térnie kiindulópontjára. Az integer programozási feladatokra az első pontos megoldási algoritmus 1958-ból származik: Gomory-féle logaritmus (11). Emellett kialakultak a gráfelméleti eljárások is: a kritikus-út-módszer és a PERT-módszer. A matematikai programozás (az operációkutatás részeként) egyre fontosabb szerepet tölt be a fejlett országok gazdasági életében. Jelentőségét érzékelteti az az adat, hogy a fejlődő országokban a matematikai programozás alkalmazása minden külön beruházás nélkül a nemzeti jövedelem 10—15%-os emelkedését eredményezné. IRODALOM 1. Bellman, R.: „Dynamic programming" Princeton, N. J. (1957.). 2. Dantzig, G. B.: „Maximization of a Linear Function Subject to Linear Inequalities." (15)-ben, 339—347. 3. Egerváry Jenő: „Mátrixok kombinatorikus tulajdonságairól", Matematikai és Fizikai Lapok, 38. (1931.). 4. Egerváry Jenő: „Bemerkungen zum Transportproblem", MTW Mittelungen, 5. Nr. 5. 1958. 5. Farkas Gyula: „A Fourier-féle mechanikai elv alkalmazásai", Mathematikai és Természettudományi Értesítő, 12. (1894.), 457—472. 6. Farkas Gyula: „A Fourier-féle mechanikai elv alkalmazásainak algebrai alapjáról", Mathematikai és Physikai Lapok, 5. (1896.), 49—54.