О вычислении вершины многогранника допустимых решений системы линейных ограничений

Александр Эдуардович Жулев, Леонид Борисович Соколинский, Ирина Михайловна Соколинская

Аннотация


В статье предлагается новый алгоритм вычисления вершины многогранника, представляющего собой область допустимых решений системы линейных ограничений. Алгоритм, получивший название VeSP, начинает работу в произвольной точке многогранника и, перемещаясь по его граням, завершает свою работу в некоторой его вершине. Для вычисления направления движения по грани используется проекционный метод, суть которого заключается в следующем. Для точки текущего приближения вычисляется аффинное подпространство, являющееся аффинной оболочкой грани, на которой расположена эта точка. К точке текущего приближения прибавляется ненулевой вектор, дающий «внешнюю» точку. Из «внешней» точки по известной аналитической формуле вычисляется ортогональная проекция на текущее аффинное подпространство. Точка проекции определяет направление движения по грани до ее границы, что дает следующее приближение. При каждом таком перемещении размерность текущей грани уменьшается. В конечном итоге приходим к грани нулевой размерности, то есть к вершине многогранника. Дается формальное описание алгоритма VeSP. Доказывается сходимость алгоритма VeSP к вершине многогранника за конечное число итераций, не превышающих размерность пространства. Приводится информация о реализации алгоритма VaSP на языке C++. Описываются результаты вычислительных экспериментов на эталонных задачах из репозитория Netlib-LP. Результаты экспериментов показывают, что алгоритм VeSP применительно ко всем тестовым задачам успешно нашел вершину многогранника за количество итераций, не превышающее размерность пространства. Для большинства задач время нахождения вершины на обычном персональном компьютере потребовало менее одной секунды.

Ключевые слова


линейные ограничения; многогранник допустимых решений; вычисление вершины; проекционный метод; алгоритм VeSP

Полный текст:

PDF

Литература


Dantzig G.B. Linear programming and extensions. Princeton, N.J.: Princeton university press, 1998. 656 p.

Zhulev A., Sokolinsky L. AlEM: a new parallel algorithm for linear programming on cluster computing systems. PREPRINTS.RU. 2025. P. 1–19. (in Russian) DOI: 10.24108/preprints-3113529.

Avis D. A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm. Polytopes - Combinatorics and Computation. DMV Seminar, vol 29 / ed. by G. Kalai, G. Ziegler. Basel: Birkhauser, 2000. P. 177–198. DOI: 10.1007/978-3-0348-8438-9_9.

Assad C.L., Morales G., Arica J. Vertex Enumeration of Polyhedra. Pesquisa Operacional. 2022. Vol. 42: e25457. P. 1–20. DOI: 10.1590/0101-7438.2022.042.00254570.

Schrijver A. Theory of Linear and Integer Programming. Chichester, New York, Brisbane, Tofonfo, Singapore: Wiley, Sons, 1998. 484 p.

Klee V., Minty G.J. How good is the simplex algorithm?. Inequalities - III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1-9, 1969 / ed. by O. Shisha. New York, NY, USA: Academic Press, 1972. P. 159–175.

Khachiyan L. Fourier–Motzkin Elimination Method. Encyclopedia of Optimization / ed. by C. Floudas, P. Pardalos. Boston, MA: Springer, 2008. P. 1074–1077. DOI: 10.1007/978-0-387-74759-0_187.

Duffin R.J. On fourier’s analysis of linear inequality systems. Pivoting and Extensions / ed. by M. Balinski. Berlin, Heidelberg: Springer, 1974. P. 71–95. DOI: 10.1007/BFB0121242.

Motzkin T.S. Contributions to the Theory of Linear Inequalities. Theodore S. Motzkin: Selected Papers / ed. by D. Cantor, B. Gordon, B.L. Rothschild. Boston: Birkhauser, 1983. P. 1–80.

Gritzmann P., Klee V. Mathematical Programming and Convex Geometry. Handbook of Convex Geometry, Vol. A / ed. by P.M. Gruber, J.M. Wills. Amsterdam: Elsevier, 1993. P. 627–674.

Ziegler G.M. Lectures on Polytopes. Vol. 152. New York, NY: Springer New York, 1995. XI, 370 p. Graduate Texts in Mathematics. DOI: 10.1007/978-1-4613-8431-1.

Murty K.G. Computational and Algorithmic Linear Algebra and n-Dimensional Geometry. World Scientific, 2011. xxi, 552 p. DOI: 10.1142/8261.

Kaczmarz S. Approximate solution of systems of linear equations. International Journal of Control. 1993. Vol. 57, no. 6. P. 1269–1271. DOI: 10.1080/00207179308934446.

Chen X. The Kaczmarz algorithm, row action methods, and statistical learning algorithms. Frames and Harmonic Analysis. Contemporary Mathematics, vol. 706 / ed. by Y. Kim, S. Narayan, G. Picioroaga, E. Weber. Providence, Rhode Island: American Mathematical Society, 2018. P. 115–128. DOI: 10.1090/CONM/706.

Olkhovsky N.A., Sokolinsky L.B. Surface Movement Method for Linear Programming. Lobachevskii Journal of Mathematics. 2024. Vol. 45, no. 10. P. 5061–5079. DOI: 10.1134/S1995080224605745.

Olkhovsky N., Sokolinsky L. Visualizing Multidimensional Linear Programming Problems. Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science, vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2022. P. 172–196. DOI: 10.1007/978-3-031-11623-0_13.

Agmon S. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. Vol. 6. P. 382–392. DOI: 10.4153/CJM-1954-037-2.

Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities. Canadian Journal of Mathematics. 1954. Vol. 6. P. 393–404. DOI: 10.4153/CJM-1954-038-x.

Gay D.M. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin. 1985. Vol. 13. P. 10–12.

Koch T. The final NETLIB-LP results. Operations Research Letters. 2004. Vol. 32, no. 2. P. 138–142. DOI: 10.1016/S0167-6377(03)00094-4.

Sokolinsky L.B., Sokolinskaya I.M. Apex Method: A New Scalable Iterative Method for Linear Programming. Mathematics. 2023. Vol. 11, no. 7. P. 1–28. DOI: 10.3390/MATH11071654.

Deutsch F. Rate of Convergence of the Method of Alternating Projections. Parametric Optimization and Approximation / ed. by B. Brosowski, F. Deutsch. Basel: Birkhauser Verlag, 1985. P. 96–107. DOI: 10.1007/978-3-0348-6253-0_7.




DOI: http://dx.doi.org/10.14529/cmse250301