Геометрична інтерпретація задач ДП

 

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

Рис. 1

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

Така геометрична інтерпретація природна для деяких задач. До них відносяться задачі:

- визначення шляху прокладення дороги (трубопроводу);

- знаходження маршруту переїзду з одного району в іншій;

- визначення траєкторії набору висоти літальним апаратом (у цьому випадку стан системи характеризується деякою точкою в просторі ).

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

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