Навигация
Моделі і методи прийняття рішень
20329
знаков
3
таблицы
4
изображения
Моделі і методи прийняття рішень
(реферат)
1. Планування цілеспрямованих дій і прийняття рішень
1.1 Оптимізаційні задачі
Інтелектуальна система спочатку аналізує зовнішню ситуацію, потім планує цілеспрямовані дії і приймає рішення про вибір певної дії.
Широкий клас завдань у рамках прийняття рішення можна сформулювати у вигляді класичної оптимізаційної задачі: знайти рішення, за яким цільова функція досягає максимуму при заданих обмеження. Оптимізацій ні задачі є предметом науки „дослідження операцій”.
Формально оптимізацій на задача описується у вигляді:
знайти рішення х=(х1, ...хn), для якого цільова функція f(x) досягає максимуму (або мінімуму) і задовольняються обмеження gi(x)>=0.
Приклад. Мандрівник збирається у дорогу. Він може взяти в рюкзак певну кількість xi предметів різних типів. Нехай є n типів предметів, наявна кількість і-го предмета становить rі. Кожний предмет має власну цінність ci та вагу qi. Потрібно зібрати рюкзак таким чином, щоб сумарна цінність узятих предметів була максимальною, але щоб сумарна вага не перевищувала межі u.
Математично задача про рюкзак формулюється так: знайти х=(х1, ...хn), для якого 
та задовольняються обмеження 
, де xi - цілі числа, xi>=0; xi<=ri.
Будь-який елемент х, що задовольняє обмеженням gi(x)>=0, називається допустимим рішенням задачі. Якщо умова максимізації не висувається, то йдеться про задачу пошуку допустимих рішень. Якщо обмежень немає, то йдеться про безумовну оптимізацію.
Якщо потрібно вирішити задачу мінімізації, то вона переводиться до задачі максимізації зміною знаку в цільовій функції.
Залежно від вигляду цільової функції та обмежень розрізняють:
1) лінійне програмування – цільова функція і обмеження лінійні;
2) нелінійне програмування - цільова функція і обмеження нелінійні;
3) дискретне програмування – всі хі є цілими числами (як у задачі про рюкзак).
Розглянемо основні методи вирішення оптимізацій них задач
1.2 Метод перебору
Метод повного перебору – це очевидний і універсальний метод вирішення оптимізаційних задач, якщо множина допустимих рішень М обмежена. Метод є точним, тобто гарантує оптимальний розв’язок.
Недолік перебору – для практичних задач кількість варіантів надто велика.
Іноді можна пожертвувати точністю розв’язку і знайти субоптимальне рішення за рахунок значного зменшення часу розрахунку. В цьому полягає суть евристичних алгоритмів.
2. Евристичний пошук
Евристичний пошук – процедура систематизованого перебору варіантів. Загальна схема методу така:
1. Вибрати певну дію з області можливих дій
2. Здійснити дію, що приведе до зміни ситуації.
3. Оцінити нову ситуацію.
4. Якщо досягнуто успіху – кінець, інакше повернутися на крок 1.
Здійснити дію можна реально (стратегія спроб і помилок) або уявно (планування).
Одним з важливих варіантів евристичного пошуку є метод послідовних поліпшень.
2.1 Експоненційна складність евристичного пошуку
Розглянемо складність рішення оптимізацій них задач на прикладі задачі про виконуваність булевого виразу, яка формулюється так: для будь-якого виразу від n змінних знайти хоча б один набір значень (x1, … xn), для якого вираз приймає значення 1.
Найпростіша схема евристичного пошуку така: надаємо одне з можливих значень (0/1) першій, другій і т.д. змінним. Після встановлення значень всіх змінних перевіряється значення виразу: 1 – задача вирішена, не 1 – повернутися на початок.
Таку задачу можна розглядати як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень x1, …xk. Ми можемо встановити змінну xk+1 в 0 або в 1, тобто маємо вибір з двох дій. Тоді кожній з цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Тобто вершина (x1, …xk) має двох нащадків (x1, …xk, 0) і (x1, …xk, 1).
При n=3 дерево перебору /можливостей/ матиме вигляд (рис.1).
Рис.1. Дерево перебору (вершини – значення змінних, дуги – рішення), зафарбовані вершини відповідають виразу (х1х2) = х3
З рис.1 видно, що вирішення задачі зводиться до перебору листів (гілок) дерева з пошуком набору, що відповідає умові задачі. Для виразу (х1х2) = х3 такими наборами будуть 000, 010, 100, 111.
Якщо n=3, дерево має 23=8 листів. Тобто число варіантів експоненційно залежить від n (2n=exp(n ln2).
Не кожний перебірний алгоритм є експоненційним (алгоритм пошуку максимального елемента в масиві – лінійний).
Із збільшенням розмірності задачі будь-який поліноміальний алгоритм стає ефективнішим за експоненційний.
Похожие работы
... продукції; зміна виробничого профілю або спеціалізації традиційних виробників продукції; відсутність у підприємства повної інформації про конкретні сегменти ринку. Фактори ризику – технічний прогрес; залежність результатів прийняття рішень споживачами від таємних умов договору, які задовольняють особисті інтереси керівництва; зміна умов імпорту, що полегшує ввіз імпортної продукції; активізація ...
... виявити особливості функціонування економічного обєкта лінійне, нелінійне, динамічне, статистичне Залежно від типів проблем, що вирішуються ОПР, можна сформувати набори методів прийняття управлінських рішень, які найчастіше застосовуються на практиці (табл. 8). В умовах ризику і невизначеності типова задача прийняття управлінського рішення є дещо ускладненою, оскільки має місце велика кількі ...
... ів факторного аналізу для дослідження нематеріальних активів дозволить визначити місце (значення) даних ресурсів у формуванні результатів діяльності підприємств. 3. Методи управління Дослідженнями встановлено, що особливості управління нематеріальних активів визначаються специфікою їх об’єкта, зумовленою відсутністю нематеріальної форми. Особливістю управління нематеріальних активів є ...
... ічно зростають показники ефективноств їх діяльності. Науково-дослідні інститути закордоном працюють над новими моделями, які раніше чи пізніше пристосуються до практики управління. Щоб якимось чином впорядкувати та зробити більш наочним питання про сфери застосування тих чи інших моделей і методів наведемо таблицю (див. табл.7).Таблиця 7: Сфери застосування моделей і методів обгруниування управлі ...
0 комментариев