Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності
Стаття є продовженням досліджень у сфері екстремальних задач та задач багатокритеріальної оптимізації. Розглядається екстремальна задача на комбінаторній конфігурації розміщень за умови багатокритеріальності, що полягає в знаходженні множини елементів конфігурації, за яких досягається певне значення...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/58834 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності / Л.М. Колєчкіна, О.А. Родіонова // Штучний інтелект. — 2011. — № 2. — С. 137-143. — Бібліогр.: 5 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859809450995482624 |
|---|---|
| author | Колєчкіна, Л.М. Родіонова, О.А. |
| author_facet | Колєчкіна, Л.М. Родіонова, О.А. |
| citation_txt | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності / Л.М. Колєчкіна, О.А. Родіонова // Штучний інтелект. — 2011. — № 2. — С. 137-143. — Бібліогр.: 5 назв. — укр. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Стаття є продовженням досліджень у сфері екстремальних задач та задач багатокритеріальної оптимізації. Розглядається екстремальна задача на комбінаторній конфігурації розміщень за умови багатокритеріальності, що полягає в знаходженні множини елементів конфігурації, за яких досягається певне значення векторної функції. Описується метод розв’язування багатокритеріальної задачі на конфігурації розміщень на основі теорії графів з урахуванням структури комбінаторної конфігурації. Розглянуто приклад реалізації методу та описані параметри числових експериментів.
Статья является продолжением предыдущих исследований. Рассматривается экстремальная задача на комбинаторной конфигурации размещений, которая состоит в поиске точек множества, в которых достигается заданное значение функции. Описывается метод локализации значения целевой функции на основании теории графов с учетом структуры множества размещений. Рассмотрен пример реализации метода и описаны параметры числовых экспериментов.
This paper is a continuation of previous studies. We consider the extremal problem on combinatorial configuration which consists of finding points of the set in which the specified value of the function is attained. The method for the localization of the target function on the basis of graph theory, given the structure of the set of arrangements is described. The example of realization of the method is considered and the numerical parameters of experiments are described.
|
| first_indexed | 2025-12-07T15:18:33Z |
| format | Article |
| fulltext |
«Штучний інтелект» 2’2011 137
2К
УДК 519.1
Л.М. Колєчкіна, О.А. Родіонова
ВНЗ Укоопспілки «Полтавський університет економіки і торгівлі»,Україна
Розв’язування екстремальних задач
на комбінаторних конфігураціях
за умови багатокритеріальності
Стаття є продовженням досліджень у сфері екстремальних задач та задач багатокритеріальної оптимізації.
Розглядається екстремальна задача на комбінаторній конфігурації розміщень за умови багатокритеріаль-
ності, що полягає в знаходженні множини елементів конфігурації, за яких досягається певне значення
векторної функції. Описується метод розв’язування багатокритеріальної задачі на конфігурації розміщень
на основі теорії графів з урахуванням структури комбінаторної конфігурації. Розглянуто приклад
реалізації методу та описані параметри числових експериментів.
Вступ
Для моделювання прикладних задач та проблем використовуються екстремальні за-
дачі, що є досить поширеними останнім часом. Значне місце серед вказаного типу задач
належить екстремальним задачам на комбінаторних конфігураціях за умови багатокри-
теріальності. Векторна функція, що складається з набору непорівнюваних критеріїв, ви-
значається на певній комбінаторній конфігурації, властивості якої відповідають умовам
поставленої задачі. Збільшення спектра застосування моделей комбінаторної оптимі-
зації та ускладнення задач на комбінаторних конфігураціях, що не є достатньо вивче-
ними та дослідженими, створюють умови для пошуку нових методів та модифікації іс-
нуючих з метою оптимізації процесу обробки даних. Перспективним шляхом розвитку
методів розв’язування екстремальних задач є застосування підходів, що ґрунтуються на
теорії графів.
Для опису різних типів комбінаторних задач може бути використана теорія графів.
Перевагою використання є не лише наочність графічного представлення, а й можли-
вість одержання нових підходів до розв’язування екстремальних комбінаторних задач,
що враховують властивості комбінаторних конфігурацій. Тісний зв’язок з метричними
характеристиками графів мають проблеми оцінки числа ітерацій та ефективності алго-
ритмів симплексного типу в задачах лінійного програмування.
Дана робота є продовженням досліджень [1-5] і дає можливість розв’язати склад-
ну екстремальну комбінаторну задачу за умови багатокритеріальності, що полягає в
знаходженні множини елементів конфігурації, при яких досягається задане значення
функції. Слід зазначити, що дана задача є підзадачею для загальної екстремальної за-
дачі за умови багатокритеріальності та додаткових обмежень.
Постановка задачі. Розглянемо поняття комбінаторної конфігурації з метою по-
дальшого викладу матеріалу. Нехай задані множини mX ,...,2,1 , nyyyY ,...,, 21 ,
і нехай на Y задане упорядкування: nyyyY ...21 . Відображення YX : , що
задовольняє деякий комплекс обмежень , будемо називати конфігурацією. Комплекс
обмежень , що задовольняє відображення , визначає деякий клас конфігурації, який
відповідає умовам комбінаторної конструкції в задачі [5].
Колєчкіна Л.М., Родіонова О.А.
«Искусственный интеллект» 2’2011 138
2К
Екстремальна комбінаторна задача на комбінаторній конфігурації за умови
багатокритеріальності відрізняється наявністю більше ніж одного критерію, що можуть
бути представлені набором функцій
k
i
iij xcxf
1
)( , lNj або у вигляді векторного
критерію 1 2( ) ( ( ), ( ),..., ( ))lF x f x f x f x .
Слід зазначити, що загальним підходом до розв’язування багатокритеріальних задач
є зведення їх до скалярних шляхом визначення ваги кожного з критеріїв оптимальності,
тобто визначення вагових коефіцієнтів i та
l
i
ii xfxf
1
)()( . Таким чином, векторна
задача стає однокритеріальною і для знаходження екстремальних значень можуть вико-
ристовуватись методи розв’язування скалярних задач.
В загальному екстремальна задача на комбінаторній конфігурації за умови багато-
критеріальності формулюється так: маємо множину з n елементів, на ній задається ком-
бінаторна конфігурація ki aaaA ,...,, 21 . На множині A задається вектор-функ-
ція ))(),..,(),(()( 21 xfxfxfxF l . Необхідно знайти екстремум функції
l
i
ii xfxf
1
)()(
та елементи множини A , у яких цей екстремум досягається.
Враховуючи, що в екстремальних задачах можуть бути присутні і додаткові об-
меження, які звужують сферу допустимих значень, то є доцільним використати для по-
шуку розв’язку такої багатокритеріальної екстремальної задачі підпрограму у вигляді
алгоритму, що розроблений за методом локалізації значення функції на деякій комбі-
наторній конфігурації [1], [4]. Суть алгоритму полягає у поступовому поглибленні у
структуру графа комбінаторної конфігурації, розбитого на підграфи, причому відки-
даються ті підграфи, які не можуть містити розв’язку. Такий підхід значно скорочує
кількість варіантів перебору та оптимізує процес розв’язування задачі.
Граф розглядаємо як фігуру, що складається з непорожньої скінченної множини V
точок (вершин) і скінченної множини Е орієнтованих чи неорієнтованих ліній (ребер),
що з’єднують деякі пари вершин. Підграфом рангу r графа конфігурації розміщень
назвемо граф, вершини якого мають r фіксованих координат.
Алгоритм розв’язування багатокритеріальної екстремальної задачі
на комбінаторній конфігурації розміщень
Крок 0. Зведемо багатокритеріальну задачу до однокритеріальної. Знайдемо зна-
чення коефіцієнтів відповідної скалярної функції
l
i
ii xfxf
1
)()( та впорядкуємо їх
за зростанням, тоді дана функція набуває вигляду:
nn xcxcxf ~...~)( 11 , nccc ~...~~
21 ,
а до вихідного вигляду приходимо, застосовуючи перетворення до коефіцієнтів:
1
~
cci ,
nccc
n
...
...21
21
,
nccc
n
~...~~
...21
21
1 .
Крок 1. Визначаємо кількість вершин графу комбінаторної конфігурації [1].
Для розміщень це значення дорівнює
)!(
!
nk
k
.
Розв’язування екстремальних задач на комбінаторних конфігураціях…
«Штучний інтелект» 2’2011 139
2К
Крок 2. Визначаємо кількість крайніх точок у загальному графі кожного з
підграфів.
Крок 3. Обчислюємо максимальне та мінімальне значення заданої цільової функції
в крайніх точках підграфів загального графа:
knknnknk xcxcxcxcxf 112211max ...)( ;
knknnn xcxcxcxcxf 112211min ...)( .
Крок 4. Будуємо структурний граф, що представляє розкладання графа на підграфи
та відображає лише крайні вершини підграфа.
Крок 5. Визначаємо значення цільової функції в початковій та кінцевій вершинах
підграфів.
Крок 6. Визначаємо множину структурних підграфів, для яких задане значення
цільової функції може міститись між його крайніми точками.
Крок 7. Формуємо множину точок-елементів конфігурації, для яких yxf *)(
[1-3]. Якщо всі точки знайдено (тобто серед множини підграфів немає таких, для яких
би виконувалась умова кроку 6), то задача розв’язана. Виводимо елементи конфігурації.
Інакше – переходимо на крок 8.
Крок 8. У підграфі, визначеному на кроці 6, фіксуємо останню координату в точці –
вершині підграфу. Здійснюємо перехід на крок 1.
Вище описаний алгоритм програмно реалізовано для конфігурації розміщень.
Розглянемо числовий приклад його роботи.
Приклад 1. Дано: а) набір рівноважливих функцій
k
i
iij xcxf
1
)( ,
lNj , де
4k , 3l :
43211 6532)( xxxxxf ,
43212 283)( xxxxxf ,
43213 525)( xxxxxf ;
б) визначено значення скалярної функції 23*)(*)(
1
l
i
ii xfxf ;
в) елементи множини розміщень (1 2 3 4 5 6 7 8).
Знайти: точки – елементи конфігурації розміщень, у яких досягається задане
значення цільової функції.
Розв’язання: знайдемо значення коефіцієнтів функції
l
i
ii xfxf
1
)()( . Врахо-
вуючи рівноважливість критеріїв, що входять до складу вектор-функції, маємо
3
1
321 , тоді 1 2 3 4( ) 2 5 3 .F x x x x x
Для впорядкування елементів цільової функції визначимо відображення :
)3,5,1,2(c , )5,3,2,1(0 i
, 10
c
i
3412
4321
,
3412
43211 .
Будуємо граф, який містить 1680
)!48(
!8
вершин. Визначимо мінімальне та
максимальне значення цільової функції:
max : 1 5 2 6 3 7 5 8 78,
min : 1 4 2 3 3 2 5 1 21.
Колєчкіна Л.М., Родіонова О.А.
«Искусственный интеллект» 2’2011 140
2К
Згідно з алгоритмом, визначимо крайні точки підграфів та знайдемо значення цільо-
вої функції в них. Будуємо структурний граф многогранника розміщень (рис. 1).
Рисунок 1 – Структурний граф многогранника розміщень
З рис. 1 видно, що шукане значення функції, яке рівне 23, може досягатись лише на
7 та 8 рівнях структурного графу. Таким чином перші 6 рівнів розглядати не будемо.
Розглянемо наступний підграф, зафіксувавши останню координату 14 x , що належить
усім вершинам підграфу 8. Одержимо наступний структурний граф (рис. 2).
Рисунок 2 – Структурний граф ІІ рівня многогранника розміщень при 14 x
Шукане значення міститься між вершинами )1,3,8,7(1621x і )1,3,2,4(1650x (рівень 6)
та )1,2,8,7(1651x і )1,2,3,4(1680x (рівень 7). Отже, тепер зафіксуємо значення наступної
координати 23 x та проведемо обчислення для підграфа наступного рівня, де знахо-
дяться вершини, у яких досягається шукане значення 23*)( xF (рис. 3).
Розв’язування екстремальних задач на комбінаторних конфігураціях…
«Штучний інтелект» 2’2011 141
2К
Рисунок 3 – Структурний граф ІІ рівня многогранника розміщень при 14 x , 23 x
Зафіксуємо значення 32 x та знайдемо значення у відповідних точках.
Одержимо точку )1,2,3,6(x , у якій досягається значення 23. Таким чином з ура-
хуванням відображення функції одержуємо )2,1,6,3(*x , для якої 23*)( xf .
Провівши аналогічні розрахунки для усіх підграфів, для яких виконується умова
кроку 6, одержимо наступні точки, що будуть розв’язками задачі (табл. 1):
Таблиця 1 – Координати вершин, що є розв’язками задачі
1x 2x 3x 4x )(xF
3 4 2 1 23
3 6 1 2 23
2 5 1 3 23
Отже, одержано три точки, що задовольняють умові задачі, значно скоротивши
кількість варіантів перебору: розглянуто 100 точок із 1680.
Таблиця 2 – Результати числових експериментів
Колєчкіна Л.М., Родіонова О.А.
«Искусственный интеллект» 2’2011 142
2К
Вищевказаний алгоритм програмно реалізований та проведені числові експеримен-
ти. Розрахунки показали ефективність даного алгоритму для розглядуваного класу задач,
оскільки кількість варіантів перебору значно скорочується. Числові експерименти об’єд-
наємо і представимо у табл. 2, відобразивши наступні параметри: розмірність цільової
функції, кількість елементів множини, кількість підграфів, на які розбивається граф, кіль-
кість точок, у яких знаходиться значення функції, час виконання програми, шукане зна-
чення функції, кількість розв’язків.
Аналізуючи дані табл. 2, можна побудувати графічні залежності кількості роз-
глянутих точок від кількості розв’язків (рис. 4) та часу роботи програми від кількості
розв’язків задачі (рис. 5).
З рис. 4 та 5 видно, що існує прямо пропорційна залежність між кількістю роз-
в’язків та кількістю точок, що розглядаються, причому ця кількість значно менша кіль-
кості вершин графа, які мав би пройти алгоритм при повному переборі, що свідчить про
ефективність роботи програми.
Рисунок 4 – Графік залежності кількості розглянутих точок комбінаторної
конфігурації від кількості розв’язків
Рисунок 5 – Графік залежності часу роботи програми від кількості розв’язків
Висновки
Виконано постановку екстремальної комбінаторної задачі за умови багатокрите-
ріальності. Для теоретичних та прикладних досліджень сформульована задача є ак-
туальною, а запропонований шлях пошуку розв’язків використовується як допоміжний
алгоритм у загальному методі розв’язування екстремальних задач за умови багатокрите-
Розв’язування екстремальних задач на комбінаторних конфігураціях…
«Штучний інтелект» 2’2011 143
2К
ріальності. Застосування теорії графів до пошуку ефективних підходів до розв’язування
екстремальних задач на комбінаторних конфігураціях дає можливість вдосконалення
методів пошуку розв’язків поставленої задачі та інших класів задач. Подальші досліджен-
ня плануються у сфері розробки загального алгоритму на різних комбінаторних кон-
фігураціях.
Литература
1. Донец Г.А. Локализация значения линейной функции заданной на перестановках / Г.А. Донец,
Л.Н. Колечкина // Радиоэлектроника и информатика. – 2009. − № 1. – С. 76-81.
2. Донец Г.А. Метод упорядочения значений линейной функции на множестве перестановок / Г.А. Донец,
Л.Н. Колечкина // Кибернетика и системный аналіз. – 2009. – № 2. – С. 50-61.
3. Колечкина Л. Н. Об одном алгоритме решения комбинаторных задач векторной оптимизации на
множестве размещений / Л. Н. Колечкина // Искусственный интелект. – 2010. – № 1. – С. 61-69.
4. Колечкина Л.Н. Обоснование структурированного метода локализации значения линейной функции,
заданной на комбинаторной конфигурации перестановок / Л.Н. Колечкина // Динамические системы. –
2009. – Вып. 27. – C. 67-80.
5. Сачков В.Н. Комбинаторные методы дискретной математики / Сачков В.Н. – М. : Наука, 1977. – 320 с.
Literatura
1. Donec G.A. Radiojelektronika i informatika. 2009. № 1. P. 76-81.
2. Donec G.A. Kibernetika i sistemnyjanalіz. 2009. № 2. P. 50-61.
3. Kolechkina L.N. Iskusstvennyjintelekt. 2010. № 1. P. 61-69.
4. Kolechkina L.N. Dinamicheskiesistemy. 2009. Vyp. 27 P. 67-80.
5. Sachkov V.N. Moscow : Nauka. 1977. 320 p.
Л.Н. Колечкина, Е.А. Родионова
Решение экстремальных задач на комбинаторных конфигурациях при условии многокритериальности
Статья является продолжением предыдущих исследований. Рассматривается экстремальная задача на
комбинаторной конфигурации размещений, которая состоит в поиске точек множества, в которых
достигается заданное значение функции. Описывается метод локализации значения целевой функции на
основании теории графов с учетом структуры множества размещений. Рассмотрен пример реализации
метода и описаны параметры числовых экспериментов.
L.M. Kolechkina, O.A. Rodionova
Solution of Extremal Tasks on Combinatorial Configurations with Multicriteria
This paper is a continuation of previous studies. We consider the extremal problem on combinatorial configuration
which consists of finding points of the set in which the specified value of the function is attained. The method for the
localization of the target function on the basis of graph theory, given the structure of the set of arrangements is
described. The example of realization of the method is considered and the numerical parameters of experiments are
described.
Стаття надійшла до редакції 15.03.2011.
|
| id | nasplib_isofts_kiev_ua-123456789-58834 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:18:33Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Колєчкіна, Л.М. Родіонова, О.А. 2014-03-31T12:10:47Z 2014-03-31T12:10:47Z 2011 Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності / Л.М. Колєчкіна, О.А. Родіонова // Штучний інтелект. — 2011. — № 2. — С. 137-143. — Бібліогр.: 5 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58834 519.1 Стаття є продовженням досліджень у сфері екстремальних задач та задач багатокритеріальної оптимізації. Розглядається екстремальна задача на комбінаторній конфігурації розміщень за умови багатокритеріальності, що полягає в знаходженні множини елементів конфігурації, за яких досягається певне значення векторної функції. Описується метод розв’язування багатокритеріальної задачі на конфігурації розміщень на основі теорії графів з урахуванням структури комбінаторної конфігурації. Розглянуто приклад реалізації методу та описані параметри числових експериментів. Статья является продолжением предыдущих исследований. Рассматривается экстремальная задача на комбинаторной конфигурации размещений, которая состоит в поиске точек множества, в которых достигается заданное значение функции. Описывается метод локализации значения целевой функции на основании теории графов с учетом структуры множества размещений. Рассмотрен пример реализации метода и описаны параметры числовых экспериментов. This paper is a continuation of previous studies. We consider the extremal problem on combinatorial configuration which consists of finding points of the set in which the specified value of the function is attained. The method for the localization of the target function on the basis of graph theory, given the structure of the set of arrangements is described. The example of realization of the method is considered and the numerical parameters of experiments are described. uk Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Моделирование объектов и процессов Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності Решение экстремальных задач на комбинаторных конфигурациях при условии многокритериальности Solution of Extremal Tasks on Combinatorial Configurations with Multicriteria Article published earlier |
| spellingShingle | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності Колєчкіна, Л.М. Родіонова, О.А. Моделирование объектов и процессов |
| title | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| title_alt | Решение экстремальных задач на комбинаторных конфигурациях при условии многокритериальности Solution of Extremal Tasks on Combinatorial Configurations with Multicriteria |
| title_full | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| title_fullStr | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| title_full_unstemmed | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| title_short | Розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| title_sort | розв’язування екстремальних задач на комбінаторних конфігураціях за умови багатокритеріальності |
| topic | Моделирование объектов и процессов |
| topic_facet | Моделирование объектов и процессов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58834 |
| work_keys_str_mv | AT kolêčkínalm rozvâzuvannâekstremalʹnihzadačnakombínatornihkonfíguracíâhzaumovibagatokriteríalʹností AT rodíonovaoa rozvâzuvannâekstremalʹnihzadačnakombínatornihkonfíguracíâhzaumovibagatokriteríalʹností AT kolêčkínalm rešenieékstremalʹnyhzadačnakombinatornyhkonfiguraciâhpriusloviimnogokriterialʹnosti AT rodíonovaoa rešenieékstremalʹnyhzadačnakombinatornyhkonfiguraciâhpriusloviimnogokriterialʹnosti AT kolêčkínalm solutionofextremaltasksoncombinatorialconfigurationswithmulticriteria AT rodíonovaoa solutionofextremaltasksoncombinatorialconfigurationswithmulticriteria |