Властивості Евклідових задач лексикографічної комбінаторної оптимізації на розміщеннях

Анотація

Розглядаються евклідові задачі лексикографічної комбінаторної оптимізації, які передбачають знаходження лексикографічно мінімальної (для задач мінімізації) чи лексикографічно максимальної (для задач максимізації) точки серед тих, які надають екстремум цільовій функції на заданій евклідовій комбінаторній множині. Обґрунтовано властивості лінійних та дробово-лінійних задач лексикографічної комбінаторної оптимізації на загальній множині розміщень без додаткових обмежень. Отримані в роботі результати спираються на відомі раніше критерії екстремалей лінійної та дробово-лінійної функцій на розміщеннях: будь-яка екстремаль є елементом певної множини полірозміщень (для лінійних задач вигляд множини екстремалей встановлений явно, для дробово-лінійних задач множина полі­розміщень формується на основі деякої відомої екстремалі). У роботі встановлено вигляд точок, які є лексикографічною мінімаллю та лексикографічною максималлю лінійної функції на загальній множині розміщень. Зокрема, якщо елементи мультимножини упорядковані за неспаданням, а коефіцієнти цільової функції — за незростанням, причому s — найменший індекс такий, що відповідний коефіцієнт цільової функції є від’ємним, то лексикографічна мінімаль формується як упорядковані за неспаданням s – 1 перших та k – s + 1 (k — вимірність простору) останніх елементів мультимножини. Для задач з дробово-лінійною цільовою функцією встановлений спосіб формування розв’язку задачі лексикографічної комбінаторної оптимізації на розміщеннях, якщо відома будь-яка з мінімалей (для задач мінімізації) чи максималей (для задач максимізації) цільової функції на заданій множині розміщень. Упорядкування компонент екстремалі у цьому випадку здійснюється з урахуванням упорядкування за незростанням коефіцієнтів лінійної функції спеціального вигляду