Моделі і методи прийняття рішень

(реферат)

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) першій, другій і т.д. ............