Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг
Робота присвячена дослідженню оптимізаційної задачі, у якій необхідно розбити множину об’єктів, для яких відомі вага та координати розміщення, на дві підмножини (зони), кожна з яких закріплена за заданими об’єктами–базами (з відомими координатами). Необхідно побудувати розмежувальну лінію, що ділит...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Igor Sikorsky Kyiv Polytechnic Institute
2024-03-01
|
| Series: | Adaptivni Sistemi Avtomatičnogo Upravlinnâ |
| Subjects: | |
| Online Access: | https://asac.kpi.ua/article/view/302419 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849420216722784256 |
|---|---|
| author | О. Жданова О. Папка Л. Рибачук О. Савчук Г. Соболевський |
| author_facet | О. Жданова О. Папка Л. Рибачук О. Савчук Г. Соболевський |
| author_sort | О. Жданова |
| collection | DOAJ |
| description |
Робота присвячена дослідженню оптимізаційної задачі, у якій необхідно розбити множину об’єктів, для яких відомі вага та координати розміщення, на дві підмножини (зони), кожна з яких закріплена за заданими об’єктами–базами (з відомими координатами). Необхідно побудувати розмежувальну лінію, що ділить ділянку на дві зони так, щоб одна зона відповідала одній базі, друга – іншій, і при цьому різниця між зваженими кількостями об’єктів, що попали в різні зони, була мінімальною. Досліджувана задача відноситься до класу задача розбиття множини на підмножини, що має широке застосування на практиці. Побудована математична модель задачі, представлені достатні умови оптимальності. Розроблені чотири алгоритми розв’язання задачі: два евристичних і два генетичних. Перший евристичний алгоритм будує деяку множину розмежувальних прямих, які проходять через середину відрізку, що з’єднує бази. Другий евристичний алгоритм є рекурсивною процедурою виклику першого евристичного алгоритму.
Розроблено також два генетичних алгоритми, що відрізняються умовами завершення. Проведена серія експериментів, метою яких був порівняльний аналіз розроблених алгоритмів за часом роботи та точністю.
Бібл. 14, іл. 6
|
| format | Article |
| id | doaj-art-d76d158b351e4f8e9c0d53c0f1182266 |
| institution | Kabale University |
| issn | 1560-8956 2522-9575 |
| language | English |
| publishDate | 2024-03-01 |
| publisher | Igor Sikorsky Kyiv Polytechnic Institute |
| record_format | Article |
| series | Adaptivni Sistemi Avtomatičnogo Upravlinnâ |
| spelling | doaj-art-d76d158b351e4f8e9c0d53c0f11822662025-08-20T03:31:48ZengIgor Sikorsky Kyiv Polytechnic InstituteAdaptivni Sistemi Avtomatičnogo Upravlinnâ1560-89562522-95752024-03-0114410.20535/1560-8956.44.2024.302419340790Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних вагО. Жданова0О. Папка1Л. Рибачук2О. Савчук3Г. Соболевський4КПІ ім. Ігоря СікорськогоКПІ ім. Ігоря СікорськогоКПІ ім. Ігоря СікорськогоКПІ ім. Ігоря СікорськогоКПІ ім. Ігоря Сікорського Робота присвячена дослідженню оптимізаційної задачі, у якій необхідно розбити множину об’єктів, для яких відомі вага та координати розміщення, на дві підмножини (зони), кожна з яких закріплена за заданими об’єктами–базами (з відомими координатами). Необхідно побудувати розмежувальну лінію, що ділить ділянку на дві зони так, щоб одна зона відповідала одній базі, друга – іншій, і при цьому різниця між зваженими кількостями об’єктів, що попали в різні зони, була мінімальною. Досліджувана задача відноситься до класу задача розбиття множини на підмножини, що має широке застосування на практиці. Побудована математична модель задачі, представлені достатні умови оптимальності. Розроблені чотири алгоритми розв’язання задачі: два евристичних і два генетичних. Перший евристичний алгоритм будує деяку множину розмежувальних прямих, які проходять через середину відрізку, що з’єднує бази. Другий евристичний алгоритм є рекурсивною процедурою виклику першого евристичного алгоритму. Розроблено також два генетичних алгоритми, що відрізняються умовами завершення. Проведена серія експериментів, метою яких був порівняльний аналіз розроблених алгоритмів за часом роботи та точністю. Бібл. 14, іл. 6 https://asac.kpi.ua/article/view/302419задача розбиття множини на підмножинизони відповідальностіевристичний алгоритмгенетичний алгоритм |
| spellingShingle | О. Жданова О. Папка Л. Рибачук О. Савчук Г. Соболевський Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг Adaptivni Sistemi Avtomatičnogo Upravlinnâ задача розбиття множини на підмножини зони відповідальності евристичний алгоритм генетичний алгоритм |
| title | Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг |
| title_full | Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг |
| title_fullStr | Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг |
| title_full_unstemmed | Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг |
| title_short | Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг |
| title_sort | задача формування зон відповідальності на множині об єктів площини за критерієм мінімізації різниці сумарних ваг |
| topic | задача розбиття множини на підмножини зони відповідальності евристичний алгоритм генетичний алгоритм |
| url | https://asac.kpi.ua/article/view/302419 |
| work_keys_str_mv | AT oždanova zadačaformuvannâzonvídpovídalʹnostínamnožiníobêktívploŝinizakriteríêmmínímízacííríznicísumarnihvag AT opapka zadačaformuvannâzonvídpovídalʹnostínamnožiníobêktívploŝinizakriteríêmmínímízacííríznicísumarnihvag AT lribačuk zadačaformuvannâzonvídpovídalʹnostínamnožiníobêktívploŝinizakriteríêmmínímízacííríznicísumarnihvag AT osavčuk zadačaformuvannâzonvídpovídalʹnostínamnožiníobêktívploŝinizakriteríêmmínímízacííríznicísumarnihvag AT gsobolevsʹkij zadačaformuvannâzonvídpovídalʹnostínamnožiníobêktívploŝinizakriteríêmmínímízacííríznicísumarnihvag |