ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ РАЗРЕЖЕННЫЙ СИМПЛЕКС-МЕТОД |
4 | |
2012 |
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ |
научная статья | 519.6 | ||
232-237 | модифицированный симплекс-метод, разреженный симплекс-метод, целочисленный симплекс-метод, целочисленная Q-матрица, мультипликативная форма присоединённой матрицы, Arageli |
Предлагается вариант модифицированного симплекс-метода, в котором все операции выполняются
над кольцом целых чисел. Метод предназначен для решения больших разреженных задач линейного
программирования. Результаты экспериментов показывают дееспособность предлагаемого подхода. |
1 . Edmonds J., Maurras J.F. Notes sur les Qmatrices d'Edmonds // Recherche op?rationelle. 1997. V. 31. № 2. P. 203-209. 2 . Dodgson C.L. Condensation of determinants // Proceedings of Royal Society of London. 1856. V. 15. P. 150-155. 3 . Waugh F.V., Dwyer P.S. Compact computation of the inverse of a matrix // Annals of Mathematical Statistics. 1945. V. 16. P. 259-271. 4 . Edmonds J. Systems of distinct representatives and linear algebra // Journal of Research of the National Bureau of Standards. 1967. V. 71B. № 4. P. 241-245. 5 . Bareiss E.H. Sylvester's identity and multistep integer- preserving Gaussian elimination // Mathematics of Computation. 1968. V. 22. № 103. P. 565-578. 6 . Bareiss E.H. Computational solutions of matrix problems over an integral domain // J. Inst. Maths Applics. 1972. V. 10. P. 68-104. 7 . Малашонок Г.И. Решение системы линейных уравнений в целостном кольце // Журнал вычисли- тельной математики и математической физики. 1983. Т. 23. № 6. С. 1497-1500. 8 . Azulay D., Pique J.F. A revised simplex method with integer Q-matrices // ACM Transactions on Mathematical Software. 2001. V. 27. № 3. P. 350-360. 9 . Dantzig G.B., Orchard-Hays W. Alternate algorithm for the revised simplex method using product form of the inverse. The RAND Corporation Research Memorandum RM-1268. 1953. 10 . netlib. URL: http://netlib.org/ 11 . Канторович Л.В., Залгаллер В.А. Расчет ра- ционального раскроя промышленных материалов. М.: Госстатиздат, 1951. 12 . Dantzig G.B., Orden A., Wolfe P. The generalized simplex method. The RAND Corporation Research Memorandum RM-1264. 1954. 13 . Dantzig G.B. Upper bounds, secondary constraints and block triangularity in linear programming // Econometrica. 1955. V. 23. № 2. P. 174-183. 14 . Makhorin A. GNU Linear Programming Kit. Version 2.1. Implementation of the Revised Simplex Method. 2001. URL: http://www.ime.unicamp.br/~moretti/ ms428/1sem2006/simplex.pdf 15 . Гантмахер Ф.Р. Теория матриц. М.: Наука, 1966. 16 . GMP. URL: http://gmplib.org/ 17 . Arageli. URL: http://www.arageli.org/ 18 . Microsoft Visual Studio 9.0. URL: http://msdn. microsoft.com/en-us/vstudio/ff431703 |