DOI: https://doi.org/10.32626/2308-5878.2019-19.5-11

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

Тетяна Миколаївна Барболіна

Анотація


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


Повний текст:

PDF

Посилання


Сергиенко И. В., Шило В. П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Киев : Наук. думка, 2003. 261 с.

Згуровский М. З., Павлов А. А. Принятие решений в сетевых системах с ограниченными ресурсами. Киев : Наук. думка. 2010. 573 с.

Cтоян Ю. Г., Ємець О. О. Теорія і методи евклідової комбінаторної оптимізації. Київ : Інститут системних досліджень освіти, 1993. 188 с.

Емец О. А., Барболина Т. Н. Комбинаторная оптимизация на размещениях. Київ : Наук. думка, 2008. 159 с.

Емец О. А., Барболина Т. Н. Свойства комбинаторных оптимизационных безусловных задач на размещениях с линейной и дробно-линейной целевыми функциями. Проблемы управления и информатики. 2017. № 1. С. 66–76.

Емец О. А., Барболина Т. Н. Полиномиальный метод решения безусловной дробно-линейной задачи комбинаторной оптимизации на размещениях. Проблемы управления и информатики. 2017. № 2. С. 27–36.