Article
MSC:
90C05
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Summary:
Lineární optimalizace hraje v oboru matematické informatiky velmi významnou roli. Její jednoduchá formulace, deterministická řešitelnost a prokazatelná optimalita ji předurčují k široké aplikaci napříč všemi obory našeho každodenního života. Přestože se může tato disciplína zdát komplikovanou, pro její pochopení stačí středoškolská matematika a trochu prostorové představivosti. Aniž bychom se pouštěli do složitých vět a důkazů, získáme náhled do teorie i praktického využití.
References:
[1] Dantzig, G. B.: Linear Programming and Extensions. United States Air Force Project RAND, R-366-PR, Princeton University Press, Princeton, 1963. MR 0201189
[2] Dantzig, G. B.: A History of Scientific Computing. Origins of the Simplex Method, S. G., Nash (ed.), ACM, New York, NY, 1990, 141–151. MR 1203105
[3] Karp, R. M.: Reducibility among Combinatorial Problems. R. E., Miller, J. W., Thatcher, J. D., Bohlinger (eds.), Springer, Boston, MA, 1972, 85–103. MR 0378476
[4] Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica, 4 (1984), 4, 373–395. DOI 10.1007/BF02579150 | MR 0779900
[5] Khachiyan, L. G.: Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20 (1980), 1, 53–72. DOI 10.1016/0041-5553(80)90061-0 | MR 0639296
[6] Land, A. H., Doig, A. G.: An automatic method of solving discrete programming problems. Econometrica, 28 (1960), 3, 497–520. DOI 10.2307/1910129 | MR 0115825
[7] Spielman, D. A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. JACM, 51 (2004), 3, 385–463. DOI 10.1145/990308.990310 | MR 2145860
Search
Partner of
