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

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

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

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

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

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

.

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

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