Квазіполнота класу задач на графах "вага-мінімаксне ребро"

  • V. A. Perepelitsya
  • E. V. Tereschenko
  • A. E. Ryabenko
Ключові слова: багатокритеріальна оптимізація, паретовська множина, повна множина альтерна-тив, квазіповна задача

Анотація

Задачі багатокритеріальної оптимізації в загальній постановці не мають очевидного рішення, що породжує безліч підходів у визначенні найбільш «вдалого» з деякої сукупності рішень, які відповідають поставленим умовам. Одним із шляхів формального визначення множини можливих альтернативних рішень є виділення паретовської множини, множини непокращуваних альтернатив. Свою продуктивність підтвердив шлях вивчення деяких класів багатокритеріальних задач, цільові функції яких мають певні властивості. Була введена концепція повних задач, для яких виконується рівність множини допустимих рішень, множини Парето і повного набору альтернатив. У попередніх роботах авторами введено поняття квазіповноти. У статті виділено клас двокритеріальних задач. Допустиме рішення за першим критерієм в цих задачах має постійне число ребер, і цільова функція містить критерій ваги і критерій мінімаксного ребра. Представниками цього класу обрані задача на графі загальної структури та задача на дводольному графі, допустимі рішення яких мають постійну кількість ребер. Сформована методика вивчення властивостей і оцінки потужностей допустимої множини рішень, паретовскої множини і повної множини альтернатив для задач виділеного класу. Доведено теорему про квазіповноту задач виділеного класу. Отримано оцінки для двох представників цього класу: «про остовне дерево і минимаксне ребро», «про досконале паросполучення на дводольному графі і мі-німаксне ребро». Запропоновано поліноміальні алгоритми вирішення досліджува-них задач. Дано оцінки обчислювальної складності цих алгоритмів

Переглядів анотації: 0
Завантажень PDF: 0
Опубліковано
2018-09-22