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

У задачах лінійного програмування, ми знаходили розв’язок як би в один етап або за один крок. Такі задачі отримали назву одноетапні або однокрокові.

На відміну від цих задач задачі динамічного програмування є багатоетапними або багатокроковими. Іншими словами, знаходження розв’язку конкретних задач методами динамічного програмування включає декілька етапів або кроків, на кожному з яких визначається розв’язок деякої частинної задачі, обумовленої початковою. Тому термін «динамічне програмування» не стільки визначає особливий тип задач, скільки характеризує методи знаходження розв’язку окремих класів задач математичного програмування, які можуть відноситися до задач як лінійного, так і нелінійного програмування. Не дивлячись на це, доцільно дати спільну постановку задачі динамічного програмування і визначити єдиний підхід до її розв’язання.

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

Дата добавления: 2015-08-21