Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг

Анотація

Робота присвячена дослідженню оптимізаційної задачі, у якій необхідно розбити множину об’єктів, для яких відомі вага та координати розміщення, на дві підмножини (зони), кожна з яких закріплена за заданими об’єктами–базами (з відомими координатами). Необхідно побудувати розмежувальну лінію, що ділить ділянку на дві зони так, щоб одна зона відповідала одній базі, друга – іншій, і при цьому різниця між зваженими кількостями об’єктів, що попали в різні зони, була мінімальною. Досліджувана задача відноситься до класу задача розбиття множини на підмножини, що має широке застосування на практиці. Побудована математична модель задачі, представлені достатні умови оптимальності. Розроблені чотири алгоритми розв’язання задачі: два евристичних і два генетичних. Перший евристичний алгоритм будує деяку множину розмежувальних прямих, які проходять через середину відрізку, що з’єднує бази. Другий евристичний алгоритм є рекурсивною процедурою виклику першого евристичного алгоритму.
Розроблено також два генетичних алгоритми, що відрізняються умовами завершення. Проведена серія експериментів, метою яких був порівняльний аналіз розроблених алгоритмів за часом роботи та точністю.

Бібл. 14, іл. 6