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

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

  • Tetiana Barbolina Полтавський національний педагогічний університет імені В. Г. Короленка, вул. Остроградського, 2, 36003, Полтава
Ключові слова: евклідова комбінаторна оптимізація, дробово-лінійна оптимізація, задачі комбінаторної оптимізації, поліноміальний алгоритм

Анотація

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

Опубліковано
2021-07-06
Як цитувати
Barbolina, T. (2021). Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення. ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ, (32), 32-36. Retrieved із http://fmmit.lviv.ua/index.php/fmmit/article/view/155