![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Визначеності
2.1. Методи багатокритеріальної оптимізації
Задача багатокритеріальної оптимізації (1.4.2) є некоректною, тому що у загальному випадку не забезпечує визначення єдиного оптимального рішення з допустимої множини X. Цю некоректність можна усунути шляхом регуляризації задачі, тобто введенням деякої додаткової інформації, математичних співвідношень або правил, що дають змогу забезпечити вибір єдиного рішення. При реалізації евристичного підходу джерелом регуляризаційної інформації є особа, що приймає рішення, (ОПР) на інтуїтивному рівні. Формальний (конструктивний) підхід ґрунтується на визначенні формальних правил вибору єдиного рішення із області компромісів. При цьому можливі два випадки. 1. Рішення ранжирують за порядком спадання чи зростання якості на множині компромісу 2. Безпосередньо визначають екстремальне рішення Загальний підхід до розв'язання цієї проблеми полягає в трансформації багатокритеріальної задачі в однокритеріальну зі скалярним критерієм. Існує декілька способів трансформації багатокритеріальних оптимізаційних задач в однокритеріальні. Розглянемо основні з них [12]. Метод головного критерію базується на виділенні головного критерію і переведенні всіх інших критеріїв у обмеження. Для цього проводиться аналіз конкретних особливостей багатокритеріальної задачі, із множини частинних критеріїв вибирається один – найважливіший, який береться за єдиний критерій оптимізації. Для кожного з інших частинних критеріїв призначається граничне значення, нижче якого він не може опускатися. Отже, всі частинні критерії, крім одного, перетворюються в обмеження, що додатково звужують множину допустимих рішень X. Тоді вихідна багатокритеріальна задача (1.4.2) перетворюється в однокритеріальну^
де k* (х) - оптимізаційний скалярний критерій; Реалізуючи розглянутий метод, потрібно звертати особливу увагу на те, щоб допустима множина рішень, яка задана частинними критеріями-обмеженнями, не виявилась порожньою. Функціонально-вартісний аналіз. Вихідна множина частинних критеріїв К= { ki (x)}, 1. Якщо обидва критерії К*ф і К*В, мають однакову вимірність або їх можна звести до однакової вимірності, то використовується узагальнений оптимізаційний критерій
а оптимальне рішення визначається за схемою
де X – звужена додатковими обмеженнями область допустимих рішень. Критерій К 1 (х) може бути інтерпретований як прибуток системи. 2. Якщо критерії К*ф і К*В, мають різну вимірність, то використовується критерій
а оптимальне рішення має вигляд:
Критерій К2 (х)являє собою нормований на одиницю витрат ефект системи. В окремому випадку для зведення двокритеріальної задачі до однокритеріальної у функціонально-вартісному аналізі використовується принцип головного критерію. Тоді один із двох розглянутих критеріїв К*ф або К* в перетворюється в додаткове обмеження, і оптимізаційні задачі мають відповідно вигляд:
де КфП, КВП – допустимі рівні відповідних критеріїв. Функціонально-вартісний аналіз застосовується при дослідженні соціально-економічних і технічних систем, які мають однакову якісну залежність ефекту Кф* від витрат Кф*, що описується логістичною (іноді її називають S-подібною) кривою. У загальному випадку ця залежність широко використовуєься для аналізу життєвого циклу систем, що починається в момент зародження ідеї (принципу) створення системи і містить у собі етапи реалізації, інтенсивного розвитку, морального старіння і завершується заміною її новою, більш прогресивною системою. При цьому поряд із задачами оцінювання і порівнювання ефективності різних варіантів рішень на всіх етапах (розроблення, створення, модернізація, реінжиніринг) життєвого циклу виникають специфічні задачі стратегічного планування розвитку, тобто визначення моментів і розмірів витрат на нове розроблення, модернізацію існуючих систем, заміну їх новими тощо. Метод послідовної оптимізації (лексикографічного впорядкування). Ідея цього методу полягає в трансформації багатокритеріальної оптнмізаційної задачі в упорядковану послідовність однокритеріальних. Для цього всі частинні критерії упорядковуються в послідовності спадання важливості, тобто встановлюється лінійний порядок
У цій послідовності розв'язуються однокритеріальні оптимізаційні задачі за кожним частинним критерієм. Метод послідовної оптимізації зводиться до правила впорядкування слів за алфавітом при створенні словників, тому його іноді називають методом лексикографічного упорядкування рішень. Відповідно до принципу послідовної оптимізації з рішень
Звідси найкраще рішення визначається за наступною схемою. На першому кроці з вихідної множини допустимих рішень X виділяється підмножина
Якщо множина
У загальному випадку
Оптимізація продовжується доти, поки на Отримане єдине рішення береться як найкраще (оптимальне). Якщо треба ранжирувати всю множину рішень х Коли вже на перших кроках оптимізації знайдено єдине рішення, усі наступні частинні критерії втрачають сенс. Тут може бути застосована схема поступки. Відповідно до цієї схеми ОПР призначає допустимий рівень зниження
за умови ki (х) > Вибір розміру поступки є евристичною операцією, яка здійснюється ОПР і залежить від особливостей задачі оптимізації. Залежність Метод послідовної оптимізації широко застосовується в ситуаціях, коли ОПР має у своєму розпорядженні тільки якісну інформацію про важливість частинних критеріїв. Метод формування узагальненого скалярного критерію, що враховує всірізнорідні частинні критерії. У цьому випадку єдиний скалярний критерій К формується як функціонал частинних критеріїв
Це найбільш загальний і універсальний підхід до розв'язання задачі багатокритеріальної оптимізації, відомий як проблема багатофакторного оцінювання. 2.2. Метод дерева рішень [15]
Розглянемо багатокрокову задачу прийняття рішень, що може розглядатися, наприклад, при максимізації прибутку або мінімізації витрат. Нехай одержання прибутку реалізується на кожному кроці процесу прийняття рішень, а потім ці прибутки додаються. Модель такої багатокрокової задачі прийняття рішень може бути подано у вигляді орієнтованого графу, що називається деревом рішень і вказує шлях із заданої множини початкових вершин в задану множину його кінцевих вершин. При цьому з кожною вершиною графа асоціюється деякий стан Рисунок 2.2.1 – Дерево рішень за умов визначеності У наведеному прикладі граф містить тільки так звані основні, або " розв’язуючі" вершини (рис. 2.2.2). При цьому вважається, що система (об’єкт прийняття рішень) знаходиться у визначеному фазовому стані
Рисунок 2.2.2 – " Розв’язуючі " вершини
Якщо вибір конкретного рішення
Рисунок 2.2.3 – Імовірнісний зв’язок вершин
У ймовірнісному дереві рішень (рис. 2.2.3) після вибору
2.3. Детермінований метод Беллмана
Розглянемо конкретный приклад детермінованого дерева рішень (рис. 2.3.1) [15]. Рисунок 2.3.1– Дерево решень із заданими локальними витратами
На рис. 2.3.1 кінцевими є всі чотирі вершини, що відповідають моменту часу Основна ідея методу Беллмана складається із двох моментів: 1. Задача пошуку оптимального шляху починає розв’язуватися з кінця. 2. Як початкова вершина послідовно розглядаються всі без винятку вершини графу при одній і тій самій кінцевій вершині. Реалізуємо метод Беллмана для показаного на рис 2.3.1 графа. Будемо просуватися по графу справа-наліво, відмічаючи в середені кожного квадратика-вершини числа, які дорівнюють найменшим із можливих сумарних витрат при просуванні із поточної початкової вершини по оптимальному шляху, та вказуючи оптимальні напрямки руху з кожної вершини за допомогою стрілок. Наприклад, якщо має місце ситуація, зображена на рис. 2.3.2 а, де вершини 2, 3, 4 вже помічено в правому верхнєму куті квадратика, і треба помітити вершину 1, то будемо розмірковувати так. Якщо як початкову взяти вершину 1, то пошук оптимального шляху із неї зводиться до порівняння трьох чисол: 5+10=15, 4+10=14, 4 + 9= 13. Найменше із цих чисол – 13, і тому саме це число записується у вершину 1, а стрілкою з’єднуються вершини 1 и 4 (рис. 2.3.2 б ) і відповідно оптимальний маршрут з вершини 1 проходить через вершину 4.
Рисунок 2.3.2 – Метод динамічного програмування Беллмана
Рисунок 2.3.3 – Розмічений граф
Для відновлення оптимального шляху в графі (2.3.1) тепер достатньо пройти вже зліва-направо у напрямку стрілок, починаючи із вже поміченої початкової вершини (оптимальний шлях на рис. 2.3.3 виділено жирними стрілками). Отримане на етапі розмітки графа число 20 означає мінімальні можливі витрати. Оскільки отимальний шлях може бути не єдиним, то за методом Беллмана одночасно знаходяться всі можливі оптимальні шляхи. При цьому варто розуміти, що глобально оптимальна стратегія не є суперпозицією локально оптимальних стратегій. Наприклад, при спробі побудови оптимального шляху на графі (рис. 2.3.3) при просуванні зліва-направо і виборі кожного разу стрілок з найменшою вагою слід очікувати невдачу, оскільки отримаємо результат: 3+8+10=21, що більше 20.
2.4. Запитання та завдання для самопідготовки
1. Поясніть суть евристичного та формального підходів до розв’язання задачі багатокритеріального прийняття рішень. 2. Яка суть методу головного критерію? 3. Яка суть функціонально-вартісного аналізу? 4. Яка суть методу послідовної оптимізації (лексографічного впорядкування)? 5. Яка основна ідея методу формування узагальненого критерію? 6. Наведіть приклад детермінованого дерева рішень. 7. Що називається “розв’язуючою” вершиною? 8. Наведіть приклад імовірнісного зв’язку між вершинами дерева рішень. 9. Яка основна ідея методу динамічного програмування Беллмана? 10. Знайдіть оптимальний шлях із вершини 1 (рис. 2.4.1):
k
Рисунок 2.4.1 11. Укажіть оптимальний шлях у наведеному на рис. 2.4.2 графі.
Рисунок 2.4.2
|