а оптимального розподілу ресурсів. p align="justify">. Завдання про заміну. ​​p align="justify">. Завдання управління виробництвом і запасами. br/>
1 . Основні поняття. Загальна постановка задачі динамічного програмування
Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішень може бути розбитий на окремі етапи, кроки.
Такі операції називаються багатокроковими. Багато економічні процеси розчленовуються на кроки природним чином. Це процеси планування і управління, що розвиваються у часі. Природним кроком може бути рік, квартал, місяць і т.д. Т.ч., якщо управління зводиться до однократному прийняттю рішення, то відповідна задача називається одноетапної або однокрокової. Раніше розв'язувані завдання лінійного та нелінійного програмування - приклади подібних завдань. Якщо управління вимагає деякої послідовності прийнятих рішень, то таке завдання називається багатоетапної або багатокрокової.
Розглянемо деяку керовану систему, що характеризується певним набором параметрів, які задають її стану. Система під впливом управління переходить з початкового стану в кінцеве. Введемо позначення. p align="justify"> 1. x i - багатовимірний вектор, компоненти якого визначають стан системи на i-тому кроці. Подальша зміна стану залежить тільки від даного стану і не залежить від того, яким шляхом система перейшла в нього (процес без наслідки).
2. На кожному кроці вибирається одне рішення, управління u i , під дією якого система переходить з попереднього стану x i-1 в нове x i . Це новий стан є функцією стану на початок кроку x i-1 і прийнятого в на чалі рішення u i , тобто
x i = x i < span align = "justify"> (x i-1 , u i ).
. Дія на кожному кроці пов'язано з певним виграшем (доходом, прибутком) або втратою (витратами), які залежать від стану на початок кроку і прийнятого рішення. F i - прирощення цільової функції задачі в результаті i-того кроку, аналогічно, F i = F i (x < b align = "justify"> i-1 , u i ) . Тоді значення цільової функції при переході системи з початкового стану в кінцеве за n кроків
. br/>
. На вектори стану хi та управління ui можуть бути накладені обмеження, об'єднання яких становить область допустимих рішень u U.
5. Потрібно знайти таке припустиме керування u * = (u1 *, ..., un *) (для кожного кроку), щоб отримати екстремальне значення функції мети F * за всі n кроків.
Будь послідовність дій для кожного кроку, переводить систему з початкового стану в кінцеве, називається стратегією управління.
Допустима стратегія управління, що доставляє функції мети екстремальна значення, називається оптимальною.
2. Принцип оптимальності. Функціональні рівняння Беллмана
Метод динамічного програмування полягає в тому, що оптимальне управління будується поступово, крок за кроком. На кожному кроці оптимізується управління тільки цього кроку. Разом з тим на кожному кроці управління вибирається з урахуванням наслідків, тому що управління, оптимизирующее цільову функцію тільки для даного кроку, може призвести до неоптимальної ефекту всього процесу. Управління на кожному кроці має бути оптимальним з точки зору процесу в цілому. В основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом. p> Принцип оптимальності: якщо деяка послідовність рішень оптимальна, то на будь-якому кроці наступні рішення утворюють оптимальну стратегію по відношенню до результату поп...
