Лекція №10 основні підходи до планування цілеспрямованих дій

1. Планування цілеспрямованих дій і прийняття рішень

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

Широкий клас завдань у рамках прийняття рішень може бути сфор­мульовано у вигляді класичної оптимізаційної задачі: знайти рішення, за яким деяка цільова функція досягає свого максимуму при заданих обме­женнях. Так, керівник фірми бажає максимізувати свій дохід, не порушу­ючи при цьому закони. Або потрібно якнайшвидше посадити космічний корабель на Марсі, але так, щоб сила удару була не надто великою.

Подібні задачі є предметом науки, яка називається дослідженням операцій. Формальніше оптимізаційну задачу можна сформулювати в такому вигляді:

знайти х = (х₁, ..., х_n), за якого функція f(x) досягає максимуму і задовольняються обмеження g_i(х) 0.

Функція f(х) називається цільовою функцією, а функції g_i(х) – обмеженнями оптимізаційної задачі.

Приклад Мандрівник збирається в дорогу. Він може взяти в рюкзак певну кількість предметів різних типів. Нехай є п типів предметів; наявна кількість i-го предмета становить r_i. Кожний предмет має власну цінність с_і та вагу q_i. Потрібно зібрати рюкзак таким чином, щоб сумарна цінність узятих предметів була максимальною, але щоб сумарна вага не перевищувала заданої межі и. Формалізуємо цю постановку. Позначимо через х_і кількість предметів і-го типу, що беруться в дорогу. Тоді очевидним чином отримуємо математичну постановку задачі:

Знайти х=(x₁,…, x_n), для якого max та задовольняються обмеження , х_і – цілі, х_і0, х_іr_і.

Будь-який елемент х, який задовольняє обмеженням g_i(х)0, назива­ється допустимим рішенням задачі. Якщо умова максимізації не висува­ється, йдеться про задачу пошуку допустимих рішень. Якщо обмежень немає, йдеться про безумовну оптимізацію.

Умова максимізації цільової функції ніяк не звужує загальності поста­новки. Дійсно, якщо треба вирішити задачу мінімізації функції g(х), ми завжди можемо поміняти знак цієї функції і вирішувати задачу максиміза­ції функції h(x)=– g(х).

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

Серед багатьох ідей, які застосовуються для знаходження максимумів функцій і функціоналів, можна, мабуть, виокремити такі: лінійне програ­мування, принцип максимуму Понтрягіна і теорію локальних екстремумів.

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