Главная страница
russian   english
16+
<< назад

Название статьи

ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ РАЗРЕЖЕННЫЙ СИМПЛЕКС-МЕТОД


Номер журнала
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