Актуальность работы
Существует большое число задач, которые могут быть сведены к задаче линейного программирования (ЛП), например: транспортная задача [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$.
