Moscow, Russian Federation
UDK 69 Строительство. Строительные материалы. Строительно-монтажные работы
UDK 004.94 Компьютерное моделирование
Optimization methods have been used to solve many problems in construction. Such well-known problems as the transport problem, some problems of structural mechanics, the problem of the optimal location of objects on the construction site, the assignment of the composition of construction teams in the production of construction and installation works, the tasks of technological equipment and a number of others can be reduced to linear programming problems. An algorithm for checking the compatibility of a system of n linear inequalities in the space of real numbers R of dimension d is given. The algorithm is based on the sequential construction of hyperplanes in the space R of dimension (d+2).
aoptimiztion methods, checking the compatibility of a system of linear inequalities, linear programming problem
Актуальность работы
Существует большое число задач, которые могут быть сведены к задаче линейного программирования (ЛП), например: транспортная задача [7,9], проблема мгновенной корректировки режима электроэнергетической системы [8] и др. Наряду с этим, существует и ряд задач, в которых ограничения задаются системой линейных неравенств, но не требуется нахождения оптимума линейной целевой функции. Например, проверка, является ли точка крайней для множества точек в многомерном пространстве, сводится к построению системы линейных неравенств и проверки ее на совместность.
Областью допустимых решений называется множество всех точек, для которых выполняются все ограничения. Если допустимая область не пуста, то существует сколь угодно малое "ε>0" , такое, что можно найти точку, нарушающую ограничения не более чем на "ε" .
Если при помощи алгоритма точка, нарушающая ограничения не более чем на "ε" , не найдена, то система признается несовместной.
Предложенный в статье алгоритм позволяет решать задачу ЛП.
Постановка задачи
Пусть в пространстве вещественных чисел $R^d$ задана система из n линейных неравенств Ax≤b. Точку, удовлетворяющую системе линейных неравенств, будем называть допустимой. Множество всех допустимых точек назовем допустимой областью. Если допустимая область не пуста, то система линейных неравенств совместна, в противном случае несовместна.
Требуется определить, является ли система совместной. Если система совместна, то требуется найти точку, которая является допустимой.
Таким образом, на входе имеется матрица ограничений системы размера n·(d+1), где n и d фиксированы. Заметим, что на практике матрица, возникающая из реальных задач, является разреженной. Поэтому в алгоритме предусмотрено компактное хранение матрицы (только ненулевые элементы).
Рассмотренный ниже алгоритм ищет допустимую точку в $R^{d+2}$. Дополнительные построения осуществляются таким образом, чтобы исходная допустимая область и в $R^{d+2}$ также являлась допустимой областью.
Для этого необходимо преобразовать множество линейных неравенств (обозначим его через $H^d$) в пространстве $R^d$ в множество линейных неравенств (обозначим его через $H^{d+2}$) в пространстве $R^{d+2}$. Множество линейных уравнений (гиперплоскостей), полученных из неравенств заменой знака «меньше или равно» на знак «равно» обозначим через $H_=^d$ и $H_=^{d+2}$ соответственно.
Дополнительные построения
Проведем дополнительные построения.
Алгоритм
Шаг 1. В пространстве $R^{d+1}$ выберем точку $O_1$ с координатами "(0,…,0," $C_1$ ")" , $C_1$- любое, такое, что $C_1>0$. Неравенства из множества $H^d$ преобразуем (добавив в каждое неравенство коэффициент $a_{id+1}$ при $x_{d+1})$ так, чтобы в пространстве $R^{d+1}$ соответствующие им гиперплоскости проходили через точку $O_1$.
$a_{id+1}=\frac{b_i}{C_1}$ (1)
Множества построенных неравенств и гиперплоскостей обозначим через $H^{d+1}$ и $H_=^{d+1}$. Заметим, что любая точка в пространстве $R^d$ лежит в полупространстве того же знака для ограничения из $H^d$ и соответствующей гиперплоскости из $H^{d+1}$.
Шаг 2. В пространстве размерности $R^{d+2}$ выберем точку $O_2$ с координатами "(0,…,0,"$C_1$","$C_2$") , $C_2$ - любое, такое, что $C_2>0$. Построим сферу с центром в точке $O_2$ и радиусом r, $r<C_2$.
Неравенства из множества $H^{d+1}$ преобразуем (добавив в каждое неравенство коэффициент $a_{id+2}$ при $x_{d+2}$) так, чтобы в пространстве $R^{d+2}$ соответствующие им гиперплоскости касались сферы с центром в точке $O_2$, и точка $O_2$ удовлетворяла каждому построенному в $R^{d+2}$ неравенству, то есть находилась в его отрицательном полупространстве соответствующей гиперплоскости. Коэффициенты $a_{id+2}$ находятся путем решения квадратного уравнения. Выбор константы $C_2$ и радиуса r обеспечивает существование двух вещественных корней квадратного уравнения. Квадратное уравнение получаем из формулы расстояния от гиперплоскости в $R^{d+2}$ до точки $O_2$.
1. Luenberger D.G. Yinyu Y. Linear and Nonlinear Programming (International Series in Operations Research & Management Science, 228) 4th ed. Springer, 2016.
2. Pellegrini M. Randomizing combinatorial algorithms for linear programming when the dimension is moderately high. Symposium on Discrete Algorithms. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. Washington, D.C., United States, P. 101-108, 2001.
3. Roos C, Terlaky T., Vial J.P. Interior point methods for linear optimization (2-nd edition). Boston: Birkhauser, 2006.
4. Topaloglu H. Fundamentals of Linear Optimization: A Hopefully Uplifting Treatment. School of Operations Research and Information Engineering, Cornell Tech, New York, NY 10044, 2021.
5. Tsuchiya T. and Muramatsu M. Global convergence of long-step affine scaling algorithm for degenerate linear programming problems. SIAM Journal on Optimization. Vol.5, No.3, pp.525-551, 1995.
6. Aleksandrov P.S. Lekcii po analiticheskoy geometrii, popolnennye neobhodimymi svedeniyami iz algebry s prilozheniem sobraniya zadach, snabzhennyh resheniyami, sostavlennogo A.S. Parhomenko: Uchebnik. 2-e izd., ster.-SPb.: Izdatel'stvo "Lan'", 2008.
7. Vasil'ev F.P. Ivanickiy A.Yu. Lineynoe programmirovanie. Izd. 3-e ispr. M.: Faktorial Press, 2008.
8. Dikin I.I. Metod vnutrennih tochek v lineynom i nelineynom programmirovanii. M.: KRASAND, 2010.
9. Lungu K.N. Lineynoe programmirovanie. Rukovodstvo k resheniyu zadach. 2-e izd., ispr. i dop. M.: FIZMATLIT, 2009.
10. Shreyver A. Teoriya lineynogo i celochislennogo programmirovaniya. V 2-h t. T.I. M.: Mir, 1991.
11. Preparata F., Sheymos M., Vychislitel'naya geometriya: Vvedenie. M.: Mir, 1989.
