Neumann projektív geometrián alapuló, és Karmarkar projektív skálázású belsőpontos módszere
Absztrakt
Neumann János a 20. század egyik legkiemelkedőbb matematikusa volt, aki összekapcsolta a tiszta és alkalmazott tudományokat. Jelentős szerepet játszott a matematika, fizika, közgazdaságtan és számítástechnika fejlődésében. Különösen fontos munkát végzett a lineáris programozás terén, amely alapvető jelentőségűvé vált a matematikai és gazdasági tervezésben. Neumann egyik úttörő eredménye a Paul Gordan homogén lineáris rendszerén alapuló új lineáris programozási módszer volt, amelyet később Karmarkar algoritmusa tett széles körben ismertté. Ez az algoritmus a lineáris programozás első belsőpontos módszere volt. A cikk ezeket az algoritmusokat ismerteti.
Hivatkozások
Iványi, A. (2005): Informatikai algoritmusok II, pp. 1-768. Budapest: ELTE Eötvös Kiadó.
Dantzig, G. B.-Thapa, M. N. (2006): Linear Programming 2. New York: Springer Science & Business Media.
Dantzig, G. B. (1991): Converting a Converging Algorithm into a Polynomial Bounded Algorithm, pp. 1-9. https://doi.org/10.21236/ADA234961
Dantzig, G. B. (1992): An epsilon-Precise Feasible Solution to a Linear Program with a Con-vexity Constraintc In: 1/epsilon2 Iterations Independent of Problem Size, pp. 1-18.
Epelman, M.-Freund, R. M. (2000): Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system. Mathematical Programming, 88., (3.), pp. 451-485. https://doi.org/10.1007/s101070000136 https://doi.org/10.1007/s101070000136
Karmarkar, N. (1984): A new poly-nomial-time algorithm for linear programming. Combinatorica, 4., (4.), pp. 373-395. https://doi.org/10.1007/bf02579150. https://doi.org/10.1007/BF02579150
Schittkowski, K. (1987): More Test Examples for Nonlinear Programming Codes. Springer. https://doi.org/10.1007/978-3-642-61582-5
