Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення

Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36

Анотація

Стаття присвячена вивченню одного класу задач евклідової комбінаторної оптимізації — задач комбінаторної оптимізації на загальній множині розміщень з дробово-лінійною цільовою функцією та без додаткових (некомбінаторних) обмежень. У роботі обгрунтовано удосконалення поліноміального алгоритму розв’язування зазначеного класу задач, який передбачає розвязування скінченної послідовності лінійних безумовних задач комбінаторної оптимізації на розміщеннях. В основу модифікації алгоритму покладено використання оцінок цільової функції на допустимій множині, що дозволяє виключити з розгляду частину задач і зменшити кількість задач, що підлягають розв’язуванню. Проведені числові експерименти підтверджують практичну ефективність пропонованого підходу.