6.5 Умова марковості (відсутність післядії)

Умові марковості повинна задовольняти будь-яка модель ДП.

Нехай - множина всіх можливих станів на етапі .

Кожному етапу ставиться у відповідність своя керована змінна таким чином, що кожному варіанту розв’язку відповідає певне значення керованої змінної. Значення цієї змінної фігурує у виразі ЦФ, наприклад:

ЗЗНШ: керована змінна – дуга ; складова ЦФ: .

ЗОВР: кожному варіанту розв’язку стану відповідає своє значення керованої змінної ; складова ЦФ: .

Нехай:

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

- перетворений стан, тобто, стан , у який система перейде, якщо в стані буде обрано варіант рішення .

Умова відсутності післядії:

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

6.6 Принцип оптимальності Белмана

Введемо поняття підшляху для спрямованої мережі. Шлях є підшляхом шляху , якщо .

Мережевий варіант принципу оптимальності: підшлях найкоротшого шляху сам є найкоротшим шляхом.

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

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

Це формулювання не що інше, як словесний запис твердження, яке міститься в ОРС. Так, якщо – вартість, яка відповідає оптимальній стратегії на етапах від до за умови, що на етапі система перебуває в стані , а  – безпосередній економічний ефект, що досягається в результаті вибору рішення при заданому стані (ефект -го етапу), то

.

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

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

6.7 Загальна схема застосування алгоритму дп

Сутність динамічного підходу полягає в заміні розв’язання -крокової задачі послідовністю задач: однокрокової, двокрокової і т.п.

Основні властивості задач, що необхідні для можливого застосування цього підходу.

1. Задача повинна допускати інтерпретацію як n-кроковий процес прийняття рішень.

2. Задача повинна бути визначена для будь-якої кількості кроків і мати структуру, що не залежить від їхньої кількості.

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

4. Вибір рішення (управління) на -му кроці не повинен впливати на попередні рішення, крім необхідного перерахунку змінних.

При застосуванні методу ДП необхідно виконати наступні дії.

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

2. Визначити етапи (їх кількість і суть планування на кожному етапі).

3. Для кожного етапу визначити множину можливих станів системи.

4. Для кожного стану визначити множину можливих варіантів рішень (значень керованих змінних).

5. Вивести ОРС.

6. Знайти розв’язки множини оптимізаційних задач (за допомогою алгоритму зворотньої або прямої прогонки).

7. Сформувати оптимальний розв’язок (рухаючись у напрямку, зворотньому до розрахунків).