Уважаемые форумчане!
Имеется система линейных однородных неравенств:
Вообще говоря, в общем случае система несовместная.
Моя задача состоит в том, чтобы найти хотя бы одно решение
, удовлетворяющее максимально возможному числу неравенств.
В случае нестрогих неравенств всегда существует возможность построения фундаментальной системы решений (метод изложен, например, в книге Солодовникова "Системы линейных неравенств").
Что происходит с такой системой в случае, когда неравенства становятся строгими?
К примеру, при n = 2 получаем множество прямых, проходящих через начало координат и разбивающих плоскость на сектора с вершиной в точке (0,0), для каждого из которых можно вычислить количество выполняемых в нем неравенств и выбрать точку из того сектора, в котором это число максимально). Могу предположить, что в общем случае геометрическая интерпретация системы позволяет решать эту задачу за O(n^m) операций.
У меня имеется система, где m = 80, n = 22. Существуют ли соответствующие эвристики, позволяющие сократить сложность вычислений и дающие приемлимые результаты?
К примеру, применим ли в данном случае метод бустинга, модификация симплекс-метода или что-то подобное?
Видимо, результат лежит где-то на поверхности.
Буду весьма благодарен за любые комментарии в этой теме.
