Олійник В.П.

Вінницький національний аграрний університет

Рівняння Беллмана. Принцип оптимальності

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

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

Так , якщо система на початку k - кроку знаходиться в стані і ми вибираємо довільне керування , то вона прийде в новий стан в , і наступні управління повинні вибиратися оптимальними щодо стану . Останнє, означає, що в цих управленнях максимізується величина , тобто показник ефективності на наступних до кінця процесу кроках. Позначимо через .

Вибравши оптимальне управління на залишилися кроках , отримаємо величину , яка залежить тільки від , тобто .

Назвемо величину умовним максимумом . Якщо виберемо на k -му кроці деякий довільне керування , то система прийде в стан . Згідно з принципом оптимальності , необхідно вибирати управління так , щоб воно в сукупності з оптимальним керуванням на наступних кроках (починаючи з ( k +1 ) -го ) призводило б до загального показника ефективності на кроках, починаючи з k - uго і до кінця. Це положення в аналітичній формі можна записати у вигляді наступного співвідношення :

, (1)

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

З рівняння (1) може бути отримана функція, якщо відомо функція. Аналогічно можна отримати, якщо відомо і т. д., поки не буде визначена величина , що представляє з визначення максимальне значення показника ефективності процесу в цілому:

Вирішуючи рівняння (1) для визначення умовного максимуму показника ефективності за кроків , починаючи з k-го , ми визначаємо відповідне оптимальне управління , при якому цей максимум досягається . Це управління також залежить від ; будемо позначати його через і називати умовним оптимальним керуванням на k -му кроці . Основне значення рівняння (1) , в якому реалізована ідея динамічного програмування , полягає в тому , що рішення вихідної задачі визначення максимуму функції n змінних зводиться до вирішення послідовності n завдань , що задаються співвідношеннями (1), кожне з яких є завданням максимізації функції однієї змінної .

У результаті послідовного вирішення п приватних завдань на умовний максимум визначають дві послідовності функцій : - умовні максимуми і відповідні їм - умовні оптимальні управління . Зазначені послідовності функцій в дискретних завданнях отримують в табличній формі , а в безперервних моделях - аналітично. Після виконання першого етапу ( умовної оптимізації ) приступають до другого етапу - безумовної оптимізації .

Якщо початковий стан задано , то безпосередньо визначають максимум цільової функції, а потім - шукане безумовне оптимальне управління по ланцюжку:

. (2)

Якщо задано безліч початкових станів , то додатково вирішують ще одну задачу на максимум  ,звідки знаходять , а потім по ланцюжку (2) - безумовне оптимальне керування.

У розглянутих рекурентних співвідношеннях наказують починати обчислення з останнього етапу і потім пересуватися назад до етапу 1. Такий метод обчислень відомий як алгоритм зворотного прогонки. Якщо розрахунки здійснюються в природному порядку проходження етапів, то та ¬ кою метод обчислень відомий як алгоритм прямої прогонки.

Наведемо рекурентні співвідношення для цього випадку. Рівняння з-стояння для прямого ходу зручно записувати у вигляді :

Введемо в розгляд умовні максимуми показника ефективності за k кроків, від 1-го до k-го включно, - величину . Повторивши наведені міркування, прийдемо до наступної системи рівнянь Беллмана:

У результаті вирішення цих рівнянь отримаємо послідовності:

; .

Далі визначимо безумовне оптимальне управління по ланцюжку:

.

Отже, оптимальна поведінка в задачах динамічного програмування володіє такими властивостями, що який би не був первинний стан і рішення (тобто "управління"), наступні рішення повинні складати оптимальну поведінку відносно стану, що виходить в результаті першого рішення.

Література

1. Ашманов С.А., Тимохов С.А. Теория оптимизации в задачах. – М.: Наука, 1991.

2. Перестюк М.О., Станжицький О.М. Екстремельні задачі. Навчальний посібник – К.: ВПЦ Київський університет, 2004. – 50 с.