г. Москва и Московская область, Россия
УДК 69 Строительство. Строительные материалы. Строительно-монтажные работы
УДК 004.94 Компьютерное моделирование
Для решения многих задач в строительстве нашли применение методы оптимизации. Такие известные задачи, как транспортная задача, некоторые задачи строительной механики, задача оптимального расположения объектов на строительной площадке, назначения состава строительных бригад при производстве строительно-монтажных работ, задачи технологической комплектации и ряд других могут быть сведены к задачам линейного программирования. Приводится алгоритм проверки совместности системы из n линейных неравенств в пространстве вещественных чисел R размерности d. Алгоритм основан на последовательном построении гиперплоскостей в пространстве R размерности (d+2). Рассматривается применение данного алгоритма для решения задачи линейного программирования.
методы оптимизации, проверка совместности системы линейных неравенств, задача линейного программирования
Актуальность работы
Существует большое число задач, которые могут быть сведены к задаче линейного программирования (ЛП), например: транспортная задача [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 Т., 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. Александров П.С. Лекции по аналитической геометрии, пополненные необходимыми сведениями из алгебры с приложением собрания задач, снабженных решениями, составленного А.С. Пархоменко: Учебник. 2-е изд., стер.-СПб.: Издательство "Лань", 2008.
7. Васильев Ф.П. Иваницкий А.Ю. Линейное программирование. Изд. 3-е испр. М.: Факториал Пресс, 2008.
8. Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании. М.: КРАСАНД, 2010.
9. Лунгу К.Н. Линейное программирование. Руководство к решению задач. 2-е изд., испр. и доп. М.: ФИЗМАТЛИТ, 2009.
10. Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т. T.I. M.: Мир, 1991.
11. Препарата Ф., Шеймос М., Вычислительная геометрия: Введение. М.: Мир, 1989.
