До формалізації та класифікації задач комбінаторної оптимізації
Аналізуються ряд відомих в літературі означень задач комбінаторної оптимізації (ЗКО) та їх співвідношення з терміном "дискретна оптимізація". Пропонується новий підхід до формалізації поняття ЗКО, який дозволяє не лише чітко виокремити конкретні класи ЗКО, але й здійснювати загальну класиф...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/12697 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | До формалізації та класифікації задач комбінаторної оптимізації / Л.Ф. Гуляницький // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 45-49. — Бібліогр.: 12 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860033340351971328 |
|---|---|
| author | Гуляницький, Л.Ф. |
| author_facet | Гуляницький, Л.Ф. |
| citation_txt | До формалізації та класифікації задач комбінаторної оптимізації / Л.Ф. Гуляницький // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 45-49. — Бібліогр.: 12 назв. — укр. |
| collection | DSpace DC |
| description | Аналізуються ряд відомих в літературі означень задач комбінаторної оптимізації (ЗКО) та їх співвідношення з терміном "дискретна оптимізація". Пропонується новий підхід до формалізації поняття ЗКО, який дозволяє не лише чітко виокремити конкретні класи ЗКО, але й здійснювати загальну класифікацію задач оптимізації.
Анализируются ряд известных определений задач комбинаторной оптимизации и их соотношение с термином "дискретная оптимизация". Предлагается подход к формализации понятия задач комбинаторной оптимизации, который позволяет не только четко выделить отдельные классы таких задач, но и предложить общую классификацию задач оптимизации.
А number of well-known definitions of combinatorial optimization probem (COP) are analyzed and their correlation with "discrete optimization" term is investigated. An approach to COP formalization is suggested, which allows not only to distinguish single COP classes, but also to classify optimization problems in general.
|
| first_indexed | 2025-12-07T16:52:51Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2008, № 7 45
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Аналізуються ряд відомих в літе-
ратурі означень задач комбіна-
торної оптимізації (ЗКО) та їх
співвідношення з терміном "диск-
ретна оптимізація". Пропонує-
ться новий підхід до формалізації
поняття ЗКО, який дозволяє не
лише чітко виокремити конкретні
класи ЗКО, але й здійснювати за-
гальну класифікацію задач опти-
мізації.
Л.Ф. Гуляницький, 2008
ÓÄÊ 519.5
Ë.Ô. ÃÓËßÍÈÖÜÊÈÉ
ÄÎ ÔÎÐÌÀ˲ÇÀÖ²¯
ÒÀ ÊËÀÑÈÔ²ÊÀÖ²¯ ÇÀÄÀ×
ÊÎÌÁ²ÍÀÒÎÐÍί ÎÏÒÈ̲ÇÀÖ²¯*
Вступ. Розглядаються питання формального
означення важливого як в теоретичному, так
і в прикладному аспектах терміна "задача
комбінаторної оптимізації (ЗКО)". Вводи-
ться поняття комбінаторних об’єктів, що є
узагальненням поняття комбінаторних
конфігурацій, запропонованого К. Бержем,
на основі якого дається формальне озна-
чення ЗКО.
Формулювання проблеми. В науковій
літературі широко вживається термін “задача
комбінаторної оптимізації”. У загальному
випадку задачу оптимізації подають
кортежем < f, X, Π, D, ext >, де f: X→ R
1 –
задана цільова функція задачі, R1 – числова
пряма, X – простір розв’язків задачі, Π –
предикат, який визначає підмножину D X⊆
допустимих варіантів розв’язку згідно
наявних обмежуючих умов,
{min, max}ext ∈ – напрям оптимізації [1]. У
цих позначеннях задачу оптимізації можна
переписати у вигляді:
необхідно знайти *x D X∈ ⊆ таке, що
* arg m in ( )
x D X
x f x
∈ ⊆
= . (1)
У роботі [2] під ЗКО розуміється проблема
пошуку екстремумів заданої цільової функції
вигляду (1), коли Х – комбінаторний простір.
Під комбінаторним простором тут
розуміється сукупність комбінаторних
об’єктів певного типу, утворених із
елементів заданої скінченної множини
* Робота виконана при частковій підтримці
INTAS (проект 06-1000017-8909)
Л.Ф. ГУЛЯНИЦЬКИЙ
46 Теорія оптимальних рішень. 2008, № 7
потужності п (твірна множина). Водночас, поняття “комбінаторний об’єкт” не
формалізується, а як приклад названі комбінації, перестановки та розміщення. В
зарубіжній літературі переважно вживається означення ЗКО, введене в [3]
(переклад з оригінального видання 1982 р., яке стереотипно перевидано в 1998
р. [4]), де простір варіантів Х визначається як “скінченна (рідше – нескінченна
злічена) множина”. Таке тлумачення не дозволяє строго формально окреслювати
окремі класи ЗКО, такі, наприклад, як дискретне, цілочислове чи булеве
програмування. Більше того, воно часто призводить до фактичного ототожнення
понять дискретної та комбінаторної оптимізації, яке і спостерігається в ряді
робіт. Зауважимо, що під дискретним програмуванням інколи розуміють
дослідження та розв’язання екстремальних задач, визначених на скінченних
множинах [5]. Більш прийнятним є підхід із [6], де під дискретною
оптимізацією розуміють задачу вигляду (1), в якій Х – це n-вимірний дійсний
простір, 1( ,..., ), , 1,..., ,
n i i
x x x x D i n= ∈ = а хоча б одне з Di є скінченним або
зліченним (без граничних точок), тобто дискретним.
Зауважимо, що розгляд прикладів ЗКО в [3] взагалі починається із задачі
лінійного програмування, яка, зрозуміло, може в більшості випадків індукувати
відповідну ЗКО, але в загальному випадку належить до задач неперервної
оптимізації, оскільки в ряді індивідуальних задач лінійного програмування
множина їх глобальних розв’язків є континуальною (неперервною). Показовим у
цьому плані є той факт, що К. Блюм та А. Ролі, відтворивши в [1] дослівно
означення з [3], вже в [7] обмежили клас ЗКО задачами вигляду (1), в яких
Х – обов’язково лише скінченна множина.
Далі розвивається підхід до визначення поняття комбінаторної оптимізації
[8, 9], на основі якого здійснюється формальна класифікація класів ЗКО .
Більш строго формалізація комбінаторних об’єктів може бути здійснена на
основі запропонованого в [10] поняття комбінаторної конфігурації. Нехай U =
={1, …, m}, а V – скінченна лінійно впорядкована множина (ланцюг).
Означення 1 [10]. Під комбінаторною конфігурацією розуміється
відображення φ : U → V, яке задовольняє певній системі обмежень Λ.
На основі цього підходу побудовані комбінаторні конфігурації, які
відповідають найпростішим комбінаторним об’єктам: розміщенням,
перестановкам, комбінаціям, розбиттям та іншим об’єктам, утвореним на основі
урнової схеми [10, 11].
Наприклад, якщо Λ = Ø, то кожна конфігурація φ визначає розміщення з
необмеженими повтореннями обсягу т із п різних елементів. Нехай тепер Λ =І,
де І – множина ін’єктивних відображень:
∀x, y ∈ U, x ≠ y ⇒ φ(x) ≠ φ(y). (2)
За виконання умови (2) конфігурація φ задає розміщення т елементів із
усіх п можливих, а при т = п – перестановку. Позначивши М множину строго
ДО ФОРМАЛІЗАЦІЇ ТА КЛАСИФІКАЦІЇ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ
Теорія оптимальних рішень. 2008, № 7 47
монотонних функцій, тобто таких, що φ(і) < φ(j), коли і < j, маємо при Λ=М
відображення сполучень (комбінацій).
Проте, поза рамками схеми залишилися інші комбінаторні об’єкти,
наприклад, графи, булеві простори, перестановочні матриці та ін. Далі
пропонується узагальнення схеми К. Бержа, що дозволяє породжувати та
природним чином класифікувати комбінаторні об’єкти.
Нехай задані множина Y={1, … , m}, Z – дискретний, зокрема, скінченний
простір (назвемо його твірним), ϕ – гомоморфізм, що задовольняє деякій системі
обмежень Ω. Нагадаємо, що під дискретним простором розуміється множина,
яка складається з ізольованих точок.
Означення 2. Під комбінаторним об’єктом κ розумітимемо тріаду
( ,κ = ϕ , )X Ω% , де :Y Xϕ → % , а X% – базовий простір.
Конкретизацією виду базового простору можна породжувати комбінаторні
об’єкти різного типу, які класифікуємо наступним чином.
Означення 3. Назвемо комбінаторними об’єктами 1-го порядку такі
комбінаторні об’єкти, у яких базовий простір збігається з твірним:
(1)( , , )Xκ = ϕ Ω , де (1)X Z≡ , :Y Zϕ → .
Неважко переконатися, що якщо Z – це скінченний ланцюг, то такі
комбінаторні об’єкти збігаються з комбінаторними конфігураціями у сенсі
Бержа [10].
Означення 4. Комбінаторними об’єктами k-го порядку (k > 1) назвемо
комбінаторні об’єкти ( )( , , )kXκ = ϕ Ω , де ( ) ( 1)
k
k kX X Z−= ∪ , ( ): kY Xϕ → .
Повертаючись до оптимізаційної задачі (1), дамо наступне
Означення 5. Задача (1) називається ЗКО, якщо простір її розв’язків Х – це
простір, елементами якого є комбінаторні об’єкти.
Як приклад, при k = 1, окрім комбінаторних конфігурацій у сенсі Бержа,
комбінаторними об’єктами можна описати множину цілочислових або булевих
векторів розмірності т, якщо покласти Z = С, де С – множина цілих чисел, або
Z = {0,1} відповідно.
При k = 2 можна описати, зокрема, задачі, визначені на графах: орієнтованих
і неорієнтованих, зв’язних і незв’язних. Розглянемо випадок k > 2. Тоді можлива
побудова відповідності комбінаторних об’єктів і, як приклад, наступних
структур.
1. Гіперграфи, максимальна довжина ребра в яких не перевищує k, а сума
числа вершин та ребер – m.
2. Комбінаторні матриці. Нехай Рп – це множина всіх перестановок чисел
1,…, п. Тоді конкретна комбінаторна матриця (тобто матриця з k рядків, кожний
із яких є перестановкою [12]) буде відображена комбінаторним об’єктом k-го
роду, коли Х(k) = (Рп)
k .
3. Речення з т слів, довжина кожного з яких не перевищує k, якщо Z – це
деякий скінченний алфавіт.
Л.Ф. ГУЛЯНИЦЬКИЙ
48 Теорія оптимальних рішень. 2008, № 7
Отже, на відміну від підходу К. Бержа, в наведеній схемі не вимагається
повна впорядкованість твірного простору, а сам він може бути нескінченним
(взагалі кажучи, не обов’язково дискретним).
Можливе подальше узагальнення наведеної схеми: як твірна множина може
виступати, наприклад, деяка множина дійсних чисел, тобто континуальна
множина. Тоді можливе охоплення в рамках схеми і задач неперервної
оптимізації. Якщо твірний простір – скінченна множина, то базисний простір
теж буде скінченним. У цьому випадку, перенумерувавши його елементи, можна
застосувати і схему Бержа, однак тоді нівелювались би відмінності між цими
елементами в утворених комбінаторних конфігураціях.
На основі описаної схеми породження комбінаторних об’єктів можлива
класифікація комбінаторних просторів за різними характеристиками.
Наприклад, за потужністю твірної множини такі простори можна розділити на
скінченні та нескінченні, за характером комбінаторних об’єктів – на
числові/нечислові простори, за типом базового простору – породжувані з
повторенням елементів або без повторень.
Використовуючи пропонований підхід, можна чітко класифікувати ЗКО,
виділивши, зокрема, такі класи:
1) ЗКО у прямому розумінні (власне ЗКО в розумінні [2], [7]).
Цей клас складають ЗКО, які визначені на просторі комбінаторних об’єктів,
якщо твірна множина Z – це скінченна множина довільної природи (символи,
числа чи інші об’єкти). Іншими словами, це сукупність задач оптимізації,
визначених на скінченних просторах;
2) задачі цілочислового програмування.
Для їх описання покладаємо Z = С, де С – множина цілих чисел;
3) задачі (псевдо) булевого програмування.
Цьому випадку відповідає Z={0,1}. Нагадаємо, що при такому виборі, як і в
попередньому випадку, виникають комбінаторні конфігурації у сенсі К. Бержа
(див. означення 1);
4) задачі дискретного програмування.
Цей дуже важливий клас задач у нашому випадку описується тоді, коли Z –
це певна дискретна підмножина простору дійсних чисел. Зауважимо, що це
узгоджується з означенням задач дискретної оптимізації, наведеному в [6], якщо
у випадку наявності не лише дискретних підмножин простору розв’язків Х такі
задачі назвати змішаними або дискретно-неперервними.
Висновок. Запропоновано підхід до чіткого визначення поняття
комбінаторного об’єкта, на основі якого досягається головна мета дослідження –
подати формалізацію терміну "задача комбінаторної оптимізації", який часто
вживається багатьма дослідниками без строгого означення. На основі
викладеного підходу запропонована класифікація ЗКО, яка дозволяє як чітко
окреслювати відомі класи оптимізаційних задач (такі як власне комбінаторна,
булева, цілочислова чи дискретна оптимізація), так і описувати нові класи ЗКО.
Можливий розвиток підходу – класифікація довільних задач оптимізації.
ДО ФОРМАЛІЗАЦІЇ ТА КЛАСИФІКАЦІЇ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ
Теорія оптимальних рішень. 2008, № 7 49
Л.Ф. Гуляницкий
К ФОРМАЛИЗАЦИИ И КЛАССИФИКАЦИИ ЗАДАЧ КОМБИНАТОРНОЙ
ОПТИМИЗАЦИИ
Анализируются ряд известных определений задач комбинаторной оптимизации и их
соотношение с термином "дискретная оптимизация". Предлагается подход к формализации
понятия задач комбинаторной оптимизации, который позволяет не только четко выделить
отдельные классы таких задач, но и предложить общую классификацию задач оптимизации.
L.F. Hulianytskyi
ABOUT THE FORMALIZATION AND CLASSIFICATION OF COMBINATORIAL
OPTIMIZATION PROBLEM
А number of well-known definitions of combinatorial optimization probem (COP) are analyzed and
their correlation with "discrete optimization" term is investigated. An approach to COP
formalization is suggested, which allows not only to distinguish single COP classes, but also to
classify optimization problems in general.
1. Blum C., Roli A. Metaheuristics in Combinatorial Optimization: Overview and Conceptual
Comparison // ACM Computing Surveys. – 2003. – 35, N 3. – P. 268–308.
2. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных
задач оптимизации. – Киев: Наук. думка, 1981. – 288 с.
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. –
М.: Мир, 1985. – 512 с.
4. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity (second
edition). – N.Y.: Dover Publications, 1998. – 496 p.
5. Энциклопедия математики. – М.: Советская энциклопедия, 1979. – Т. 2. – С. 204–205.
6. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации. – Киев: Наук. думка, 2003. –
261 с.
7. Blum C., Roli A., Alba E. An introduction to metaheuristic techniques // Parallel metaheuristics: A
new class of algorithms (Ed. E.Alba). – Hoboken: John Wiley & Sons. – 2005. – P. 3–42.
8. Гуляницкий Л. Метаэвристический метод деформаций для решения задач комбинаторной
оптимизации // Proc. of XIII Int. Conf. "Knowledge. Dialogue. Solution (KDS-2007)" (Varna,
Bulgaria, June, 2007). V.1. – Sofia: ITHEA, 2007. – P. 95–102.
9. Гуляницкий Л.Ф., Сергиенко И.В. Метаэвристический метод деформируемого
многогранника в комбинаторной оптимизации // Кибернетика и системный анализ. –
2007. – № 6 . – С. 70–79.
10. Berge C. Principes de combinatoire. – Paris: Dunod, 1968. – 146 p.
11. Сачков В.Н. Комбинаторные методы дискретной математики. – М.: Наука, 1975. – 319 с.
12. Grundel D., Krokhmal P., Oliveira C., Pardalos P. On the Number of Local Minima for the
Multidimensional Assignment Problem // J. of Combinatorial Optimization. – 2007. – N 13 . –
P. 1–18.
Отримано 25.03.2008
|
| id | nasplib_isofts_kiev_ua-123456789-12697 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:52:51Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гуляницький, Л.Ф. 2010-10-20T09:47:14Z 2010-10-20T09:47:14Z 2008 До формалізації та класифікації задач комбінаторної оптимізації / Л.Ф. Гуляницький // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 45-49. — Бібліогр.: 12 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/12697 519.5 Аналізуються ряд відомих в літературі означень задач комбінаторної оптимізації (ЗКО) та їх співвідношення з терміном "дискретна оптимізація". Пропонується новий підхід до формалізації поняття ЗКО, який дозволяє не лише чітко виокремити конкретні класи ЗКО, але й здійснювати загальну класифікацію задач оптимізації. Анализируются ряд известных определений задач комбинаторной оптимизации и их соотношение с термином "дискретная оптимизация". Предлагается подход к формализации понятия задач комбинаторной оптимизации, который позволяет не только четко выделить отдельные классы таких задач, но и предложить общую классификацию задач оптимизации. А number of well-known definitions of combinatorial optimization probem (COP) are analyzed and their correlation with "discrete optimization" term is investigated. An approach to COP formalization is suggested, which allows not only to distinguish single COP classes, but also to classify optimization problems in general. Робота виконана при частковій підтримці INTAS (проект 06-1000017-8909). uk Інститут кібернетики ім. В.М. Глушкова НАН України До формалізації та класифікації задач комбінаторної оптимізації К формализации и классификации задач комбинаторной оптимизации About the formalization and classification of combinatorial optimization problem Article published earlier |
| spellingShingle | До формалізації та класифікації задач комбінаторної оптимізації Гуляницький, Л.Ф. |
| title | До формалізації та класифікації задач комбінаторної оптимізації |
| title_alt | К формализации и классификации задач комбинаторной оптимизации About the formalization and classification of combinatorial optimization problem |
| title_full | До формалізації та класифікації задач комбінаторної оптимізації |
| title_fullStr | До формалізації та класифікації задач комбінаторної оптимізації |
| title_full_unstemmed | До формалізації та класифікації задач комбінаторної оптимізації |
| title_short | До формалізації та класифікації задач комбінаторної оптимізації |
| title_sort | до формалізації та класифікації задач комбінаторної оптимізації |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12697 |
| work_keys_str_mv | AT gulânicʹkiilf doformalízacíítaklasifíkacíízadačkombínatornoíoptimízacíí AT gulânicʹkiilf kformalizaciiiklassifikaciizadačkombinatornoioptimizacii AT gulânicʹkiilf abouttheformalizationandclassificationofcombinatorialoptimizationproblem |