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

Ключевые слова: евклидова задача комбинаторной оптимизации, задача оптимизации на размещениях, лексикографическая эквивалентность, дробно-линейная функция.