Классы лексикографической эквивалентности в евклидовой комбинаторной оптимизации на размещениях

В статье рассматривается применение регулярных разбиений пространства к решению задач евклидовой комбинаторной оптимизации, в частности, линейных условных задач оптимизации на размещении. Введено понятие точек пространства, эквивалентных относительно размещений, показано, что введенное отношение между точками является отношением эквивалентности. Приведены алгоритмы поиска элемента множества размещений, являющегося представителем комбинаторного класса эквивалентности, ближайшего к заданному классу в порядке лексикографического возрастания (убывания).
Рассмотрен также новый класс оптимизационных задач, именно, линейных условных задач лексикографической максимизации на размещениях. Предложены и обоснованы алгоритмы решения как одного частного случая, так и общего случая этого класса задач. Алгоритмы основываются на упорядоченном переборе допустимых точек в порядке лексикографического возрастания (убывания) и используют рассмотренные алгоритмы поиска ближайшего элемента множества размещений.