Page 104 - 6109

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

11.2 Повний перебір

Існує очевидний і досить універсальний метод вирішення оптимізаційних
задач, який може бути застосований, якщо множина припустимих рішень М
обмежена. Це – метод повного перебору, який полягає у переборі всіх можливих
варіантів. Метод дає гарантований розв'язок якщо множина М скінчена
(ситуація, характерна для дискретного програмування), та існує ефективний
алгоритм породження будь-якого елемента з М та обчислення на цьому
елементі цільової функції.
Таким чином, ми маємо типову загальноінтелектуальну процедуру. Якщо
інтелектуальна система потрапляє в нову ситуацію і намагається планувати
подальші дії, вона може спробувати звести задачу планування цілеспрямованих
дій до оптимізаційної задачі (для цього, очевидно, достатньо визначити
множину припустимих рішень М і цільову функцію f(x)). Якщо ця вдається,
повний перебір варіантів у більшості випадків дозволить отримати оптимальне
рішення.
Але повний перебір має очевидний недолік: для більшості практичних
ситуацій кількість варіантів, які доводиться перебирати, надто велика, і ре-
алізувати метод за прийнятний час не вбачається можливим. Тому розви-
ваються методи і алгоритми, які дозволяють скоротити такий перебір.
У той самий час далеко не завжди слід шукати саме оптимальне рішення.
Часто достатньо обмежитися рішенням субоптимальним (наближеним до
оптимального) або просто припустимим. У таких випадках достатньо виробити
якесь правило, яке б виключало застосування повного перебору і для більшості
вхідних даних давало б прийнятний результат. У цьому полягає суть
евристичних алгоритмів.
Втім далеко не будь-яка інтелектуальна задача припускає очевидне
зведення до оптимізаційної, оскільки часто не вдається записати в явному
вигляді цільову функцію або обмеження.

104