Главная | Обратная связь | Поможем написать вашу работу!

Основні властивості задач динамічного програмування та недоліки методу

РОЗДІЛ 6

ЕЛЕМЕНТИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

Основні властивості задач динамічного програмування та недоліки методу

Ряд задач оптимізації описують явища, для яких істотним є зміна об’єкта за часом (періодами) чи у просторі (стадіями), або для яких повинна бути багатокроковість прийняття рішень у процесі керування.

При цьому сам процес розв’язування задачі поділяють на кілька етапів. Для одних задач такі етапи природні, наприклад, задачі календарного планування, в яких природні кроки прийняття рішення відображуються дискретними відрізками часу (доба, тиждень, декада тощо). Для інших задач розподіл процесу на багатокроковий є умовним, наприклад, у випадку розподілу сировини між підприємствами: кількість кроків оптимізації дорівнює кількості підприємств.

При розв’язуванні задач багатокрокової структури можливо використовувати два підходи:

– визначення оптимального розв’язку одночасно на всіх кроках оптимізації;

– визначення оптимального розв’язку поступово, крок за кроком, наближаючись до оптимального плану.

Розв’язування багатокрокових задач одночасно на всіх етапах оптимізації має суттєві обсяги обчислювання, що навіть із залученням потужних засобів обчислювальної техніки такий підхід до розв’язування багатокрокових задач є малоефективним.

Оптимізація одного кроку, звичайно, простіша, ніж одночасно усього процесу, і тому доцільніше розв’язувати кілька простих задач, ніж один раз складну.

Багатокрокова структура розв’язування, тобто крок за кроком, визначає динамічні властивості задачі. Для розв’язування цих задач найефективніше використання так званого динамічного програмування. Цей метод, а точніше – підхід, розглядає процес розв’язування задачі, який складається з кількох послідовних кроків оптимізації, а саме явище розглядається покроково з фіксованими довільними станами об’єкта. Причому будь-який етап розв’язання можна виділити і зробити проміжний аналіз, або прийняти його як кінцевий розв’язок, якщо це необхідно. Сукупність прийнятих рішень покроково дає загальну динаміку процесу керування у цілому.

Таким чином, метод динамічного програмування ґрунтується на принципі поетапної, тобто послідовної оптимізації.

Типовими задачами, що розв’язуються методом динамічного програмування, вважаються такі:

– задача розподілу ресурсів (людські, енергетичні, із сировини та інші) між об’єктами з точки зору їх раціонального використання;

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

– задача про найкоротший шлях, що зустрічається при розв’язуванні транспортної задачі та сітьової моделі;

– задача про завантаження обладнання різним вантажем та інші.

Задачі, які можна розв’язувати методом динамічного програмування, повинні мати такі властивості:

– задача повинна передбачати багатокрокову структуру;

– загальна ефективність розв’язування дорівнює сумі окремих ефективностей розв’язування на кожному -му кроці оптимізації, тобто

цільова функція повинна мати властивість адитивності:

– подальші пошуки оптимального розв’язку ведуться відносно стана об’єкта, якого він досяг на початок даного кроку оптимізації і не залежить від того, яким чином цей об’єкт потрапив у цей стан. Таке твердження називається принципом оптимальності. Ця ідея вперше була запропонована Р. Беллманом у 1950-1953 роках;

– підхід до розв’язування задачі не повинен змінюватися, якщо змінилася кількість кроків оптимізації, або величина ресурсів розподілу для даного класу задач. Це твердження називається принципом укладення. З цього принципу виходить, що коли відомі процес розв’язування та розв’язок задачі більшого розміру, то відомі усі розв’язки задач меншого розміру однакової природи.

Перевагою методу динамічного програмування є наступне:

– цей метод поки що єдиний для ефективного розв’язування задач багатокрокової структури, для яких немає інших практично-припустимих методів розв’язування;

– визначення глобального оптимуму не залежить від кількості локальних екстремумів;

– метод дозволяє вводити до моделі будь-який вид обмеження, причому, чим більше їх буде, тим скоріше знаходиться оптимальний варіант, якщо існує область довільних розв’язків;

– обчислювальна процедура методу дозволяє проводити аналіз знайденого розв’язку по етапам, тим самим переглядаючи динаміку поведінки об’єкта;

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

а) у формі таблиці

б) у формі графіка (рис. 6.1):

Недоліки методу динамічного програмування:

f _j(x _j)

– метод не має універсального алго-

f ₁(x ₁) ритму, який, наприклад, є у лінійному

програмуванні – симплексний метод;

f ₂(x ₂) у методі динамічного програмування в

f ₃(x ₃) кожному конкретному випадку склада-

ється спеціальне функціональне рівнян-

х _j ня, яке відображує природу процесу

Рис. 6.1 пошуку оптимального розв’язку;

– формулювання задач у термінах динамічного програмування – досить трудомісткий етап і від того, як вибрані кроки оптимізації і стани об’єкта на цих кроках оптимізації залежить якість розв’язування задачі; причому, найбільш важкий момент у процесі розв’язування задачі – складання функціонального рівняння, що передбачає принцип оптимальності.

Далі розглянемо метод розв’язування задач дискретного типу.

12 3 4 5 6 7 8 9 10 Следующая ⇒