Зміст | назад | далі | Словник понять
Динамічне програмування - це обчислювальний метод для вирішення завдань певної структури. Виникло і сформувалося в 1950-1953 рр. завдяки роботам Р. Беллмана над динамічними завданнями управління запасами. У спрощеній формулюванні динамічне програмування являє собою спрямований послідовний перебір варіантів, який обов'язково призводить до глобального максимуму.
Основні необхідні властивості задач, до яких можливо застосувати цей принцип:
- Завдання має допускати інтерпретацію як n -шаговий процес прийняття рішень.
- Завдання має бути визначена для будь-якого числа кроків і мати структуру, не залежну від їх числа.
При розгляді k -шаговой завдання повинно бути задано деякий безліч параметрів, що описують стан системи, від яких залежать оптимальні значення змінних. Причому це безліч не повинно змінюватися при збільшенні числа кроків.
Вибір рішення (управління) на k-му кроці не повинен впливати на попередні рішення, крім необхідного перерахунку змінних.
Завдання про вибір траєкторії, завдання послідовного прийняття рішення, завдання про використання робочої сили, завдання управління запасами - класичні задачі динамічного програмування.
Постановка завдання динамічного програмування.
Постановку задачі динамічного програмування розглянемо на прикладі інвестування, пов'язаного з розподілом коштів між підприємствами. В результаті управління інвестиціями система послідовно перекладається з початкового стану S0 В кінцеве Sn. Припустимо, що управління можна розбити на n кроків і рішення приймається послідовно на кожному кроці, а управління являє собою сукупність n покрокових управлінь. На кожному кроці необхідно визначити два типи змінних - змінну стану системи Sk змінну управління xk. Мінлива Sk визначає, в яких станах може виявитися система на даному k-му кроці. Залежно від стану S на цьому кроці можна застосувати деякі управління, які характеризуються змінною xk які задовольняють певним обмеженням і називаються допустимими. Припустимо. 
= (X 1, x 2, ..., x k, ..., xn) - управління, що переводить систему на стану S0 в стан Sn, a Sk - є стан системи на k-му кроці управління. Тоді послідовність станів системи можна представити у вигляді графа, представленого на рис. 2.11.
Мал. 2.11
Застосування керуючого впливу xk на кожному кроці переводить систему в новий стан S1 (S, xk) і приносить певний результат Wk (S, xk). Для кожного можливого стану на кожному кроці серед всіх можливих управлінь вибирається оптимальне управління x * k, таке, щоб результат, який досягається за кроки з k -го по останній n -й, виявився б оптимальним. Числова характеристика цього результату називається функцією Беллмана Fk (S) і залежить від номера кроку k і стану системи S. Завдання динамічного програмування формулюється так: потрібно визначити таке управління 
, Що переводить систему з початкового стану S0 в кінцевий стан Sn, при якому цільова функція приймає найбільше (найменше) значення F (S 0, ) => Extr.
Розглянемо більш докладно особливості математичної моделі динамічного програмування:
- задача оптимізації формулюється як кінцевий багатокроковий процес управління;
- цільова функція (виграш) є адитивною і дорівнює сумі цільових функцій кожного кроку:
вибір управління xk на кожному кроці залежить тільки від стану системи k цього кроку Sk-1, і не впливає на попередні кроки (немає зворотного зв'язку);
стан системи Sk після кожного кроку управління залежить тільки від попереднього стану системи Sk-1 і цього керуючого впливу xh (відсутність післядії) і може бути записано у вигляді рівняння стану: Sk = fk (S k-1, xk), k = 1, n;
на кожному кроці управління xk залежить від кінцевого числа керуючих змінних, а стан системи залежить Sk - від кінцевого числа параметрів;
Принцип оптимальності та математичний опис динамічного процесу управління.
В основі методу ДП лежить принцип оптимальності, вперше сформульований в 1953 р американським математиком Р.Е.Беллманом: яким би не був стан системи в результаті якого-небудь числа кроків, на найближчому кроці потрібно вибирати управління так, щоб воно в сукупності з оптимальним керуванням на всіх наступних кроках приводило до оптимального виграшу на всіх, хто лишився кроках, включаючи виграш на даному кроці. При вирішенні завдання на кожному кроці вибирається управління, яке повинно привести до оптимального виграшу. Якщо вважати всі кроки незалежними, тоді оптимальним управлінням буде те управління, яке забезпечить максимальний виграш саме на даному етапі. Однак, наприклад, при покупці нової техніки замість застарілої на її придбання витрачаються певні кошти, тому дохід від її експлуатації на початку може бути невеликою, а в наступні роки нова техніка буде приносити більший дохід. І навпаки, якщо прийнято рішення залишити стару техніку для отримання доходу в поточному році, то в подальшому це призведе до значних збитків. Цей приклад демонструє наступний факт: в багатокрокових процесах управління на кожному конкретному етапі треба вибирати з урахуванням його майбутніх впливів на весь процес. Крім того, при виборі управління на даному етапі слід ураховувати можливі варіанти стану попереднього кроку. Наприклад, при визначенні кількості коштів, вкладених у підприємство в i-му році, необхідно знати, скільки коштів залишилося в наявності до атому році і який дохід отриманий в попередньому (i - 1) -м році. Таким чином, при виборі крокового управління необхідно враховувати наступні вимоги:
- можливі результати попереднього кроку Sk-1;
- вплив управління xk на все, що залишилися до кінця процесу кроки (nk).
У завданнях динамічного програмування перша вимога враховують, роблячи на кожному кроці умовні припущення про можливі варіанти закінчення попереднього кроку і проводячи для кожного з варіантів умовну оптимізацію. Виконання другої вимоги забезпечується тим, що в цих завданнях умовна оптимізація проводиться від кінця процесу до початку.
умовна оптимізація
На першому етапі рішення задачі, званому умовної оптимізацією, визначаються функція Беллмана і оптимальні управління для всіх можливих станів на кожному кроці, починаючи з останнього відповідно до алгоритму зворотного прогону. На останньому, n-му кроці оптимальне управління - х * n визначається функцією Беллмана: F (S) = max {W n (S, xn)}, відповідно до якої максимум вибирається з усіх можливих значень xn, причому xn € X.
Подальші обчислення проводяться згідно рекурентному співвідношенню, що зв'язує функцію Беллмана на кожному кроці з цієї ж функцією, але обчисленої на попередньому кроці. У загальному вигляді це рівняння має вигляд Fn (S) = max {W n (S, xn) + F k + 1 (S n (S, xk)} xk € X.
Цей максимум (або мінімум) визначається за всіма можливими для k і S значенням змінної управління X.
безумовна оптимізація
Після того, як функція Беллмана і відповідні оптимальні управління знайдені для всіх кроків з n-го по перший, здійснюється другий етап рішення задачі, званий безумовної оптимізацією. Користуючись тим, що на першому кроці (k = 1) стан системи відомо - це її початковий стан S0, можна знайти оптимальний результат за все n кроків і оптимальне управління на першому кроці x1, яке цей результат приносить. Після застосування цього управління система перейде в інший стан S1 (S, x * 1), знаючи яку, можна, користуючись результатами умовної оптимізації, знайти оптимальне управління на другому кроці x * 2, і так далі до останнього n-го кроку. Обчислювальну схему динамічного програмування можна будувати на мережевих моделях, а також по алгоритмам прямий прогонки (від початку) і зворотної прогонки (від кінця до початку). Розглянемо приклади розв'язання різних за своєю природою завдань, зміст яких вимагає вибору змінних стану і управління.
Зміст | назад | далі | Словник понять
