Уважаемые участники форума,
Хотелось бы знать Ваше мнение о новом «геометрическом» подходе к решению задачи ЛП. Его суть в следующем.
Многогранник решений задан m общими и
координатными ограничениями-неравенствами.Находятся n главных гиперплоскостей (ГП), пересечение которых дает оптимальную вершину.
На каждой из n итераций после определения главной ГП соответствующее ограничение-неравенство становится уравнением, из которого одна из переменных
выражается через другие и подставляется в остальные неравенства. Аналогичная задача отыскания главной ГП рассматривается в линейном подпространстве этой гиперграни, спроецированной на координатное подпространство
.
При подстановке
в уравнения ГП, не смежных с главной ГП, появляются лишние (зависимые) ограничения. Если на следующей итерации они выбираются как главные, то полученное решение будет находиться вне многогранника. Система неравенств-ограничений становится несовместной.
Таким образом, решение задачи ЛП сводится к определению совместности системы неравенств в узком смысле (останется ли система совместной при добавлении к ней одного из противоположных неравенств) или к нахождению смежности гиперграней.
Для сокращения времени решения (что важно для систем управления реального времени) используется простой эвристический алгоритм определения смежных граней, который будет описан позже.Такой алгоритм не всегда определяет все смежные грани, поэтому находится в общем случае квазиоптимальная точка. Переход от нее к близкой оптимальной точке может быть осуществлен любым (в т.ч. и алгебраическим) способом.
Матрица смежности гиперграней может быть определена при анализе полярного многогранника, заданного
вершинами: две гиперграни исходного многогранника являются смежными, если соответствующие вершины полярного многогранника соединены ребром.
Целесообразен предварительный анализ задач, для которых многогранники допустимых решений изоморфны (т.е. имеют ту же матрицу смежности) стандартным многогранникам: n-мерному кубу, симплексу со срезанными вершинами, призме или пирамиде, построенным на этих многогранниках.
Достоинством метода последовательного нахождения главных ГП является малое влияние увеличения размерности задачи на вычислительную трудоемкость. Метод главных ГП может быть применен для построения эффективного эвристического алгоритма поиска целочисленных решений задачи ЛП.
Предварительные результаты моделирования показывают высокую эффективность данного метода по сравнению с различными модификациями симплекс-метода и метода внутренних точек.
