Всеукраїнська науково-практична конференція



Сторінка17/60
Дата конвертації11.05.2018
Розмір3.74 Mb.
1   ...   13   14   15   16   17   18   19   20   ...   60

ТИМОФІЄВА Н.К.


МННЦІТіС НАН та МОН України (Київ)

ПРО МЕТОДИ В КОМБІНАТОРНІЙ ОПТИМІЗАЦІЇ, ЯКІ ҐРУНТУЮТЬСЯ НА

ВИКОРИСТАННІ РОЗВ'ЯЗНИХ ЗАДАЧ



Описано методи розв'язання задач комбінаторної оптимізації, які ґрунтуються на зведенні нерозв’язних задач до поліноміально розв’язних. Також показано, що класи нерозв’язних задач містять підкласи розв'язних, які виділяються за вибраною мірою подібності і способом моделювання цільової функції; за структурою вхідних даних та за структурою аргумента, яким є комбінаторна конфігурація певного типу.
Вступ. Для розв'язання задач комбінаторної оптимізації розроблено багато методів та алгоритмів. Серед них виділимо такі підходи: а) ітераційні методи та алгоритми, що ґрунтуються на частковому переборі варіантів. До них відносяться як універсальні методи математичного програмування, так і спеціальні, які ураховують специфіку даної проблеми (точні і наближені); б) методи, які ґрунтуються на розпізнаванні структури вхідної інформації і характеризуються великою швидкодією, наприклад метод найближчого сусіда, "жадібний" алгоритм, метод структурно-алфавітного пошуку тощо. Крім оговорених мають місце і такі підходи, в яких нерозв'язні задачі комбінаторної оптимізації зводяться до поліноміально розв'язних та із класів нерозв'язних задач виділяються підкласи розв'язних. Розглянемо ці методи.

Зведення нерозв'язних задач комбінаторної оптимізації до задачі про призначення. Одним із підходів до розв'язання задач комбінаторної оптимізації є зведення деяких із них до класичної задачі про призначення, оскільки остання за допомогою угорського алгоритму розв'язується поліноміально. Задачі комбінаторної оптимізації, вхідні дані в яких задано двома симетричними матрицями або двома скінченними послідовностями, досить просто зводяться до задачі про призначення. З цією метою з елементів двох заданих симетричних матриць за розробленими правилами будується нова матриця (похідна), яка задає вхідні дані для оговореної вище задачі. З використанням побудованої матриці установлюється залежність цільової функції між задачами розміщення, комівояжера, кластеризації і задачею про призначення.

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



Означення. Похідною матрицею транспозиції матриць і назвемо , нумерація рядків (стовпців) у якій збігається з послідовною нумерацією значень функції , а номери стовпців (рядків) – з нумерацією значень функції . Її елементи , , , перша перестановка в , утворена із чисел , – перша перестановка в , утворена із чисел .

Теорема. Якщо вхідні дані в задачі комбінаторної оптимізації задано двома скінченними послідовностями або симетричними матрицями і , елементи яких подано функціями і , а вхідні дані в задачі про призначення похідною матрицею , то ці задачі мають варіанти розв'язку, значення функції цілі яких збігаються, а значення функції цілі для таких класів задач, як розміщення, комівояжер, кластеризація знаходяться в межах , де – найменше, а – найбільше значення цільової функції в задачі про призначення, , .

До задачі про призначення зводиться і транспортна задача. Обидві задачі задаються двома множинами, а вхідні дані – однією несиметричною матрицею. Розв’язок цих задач знаходиться на множині перестановок, причому транспозиція проводиться або стовпців або рядків заданої матриці. Цільова функція зводиться до одного виразу, а її аргумент – перестановка. Таким чином, транспортна задача розв’язується так, як і задача про призначення.



Виділення із класів нерозв'язних задач підкласів розв'язних [1]. В літературі для деяких класів задач комбінаторної оптимізації (задача про призначення, задача розміщення, задача комівояжера) описано підкласи, що мають певну структуру вхідної інформації, для яких відомий спосіб аналітичного знаходження глобального розв'язку. Ці підкласи задач називають розв'язними. Підкласи розв'язних задач із класів нерозв'язних виділяємо за такими ознаками: а) за вибраною мірою подібності і способом моделювання цільової функції; б) за структурою вхідних даних; в) за структурою аргумента.

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

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

Висновок. Отже, задачі комбінаторної оптимізації розділяються на поліноміально розв'язні і нерозв’язні, в яких знайдений глобальний результат не збігається з метою дослідження або його неможливо обчислити із-за великої розмірності задачі. На відміну від існуючих підходів розроблено спосіб зведення нерозв'язних задач до класичної задачі про призначення, яка розв'язується поліноміально угорським алгоритмом.

Для виділення підкласів розв'язних задач із класів нерозв’язних досліджено різні структури вхідних даних, для яких цільова функція змінюється однаково і розроблено для них однакові правила розв’язку. Такий підхід дозволить розробляти поліноміальні алгоритми знаходження глобального оптимуму для широкого класу задач комбінаторної оптимізації.


ПЕРЕЛІК ЛІТЕРАТУРИ

1. Тимофієва Н.К. Про способи зведення нерозв’язних задач комбінаторної оптимізації до розв’язних / Н.К. Тимофієва // Вісник Вінницького політехнічного інституту. 2011 – № 3.– С. 240–244.




Поділіться з Вашими друзьями:
1   ...   13   14   15   16   17   18   19   20   ...   60


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка