ередніх рішень.
Іншими словами, яке б не був стан системи перед черговим кроком, треба вибрати управління на цьому кроці так, щоб виграш на даному кроці (програш) плюс оптимальний виграш (програш) на всіх наступних кроках був би максимальним (мінімальним). На основі принципу оптимальності Беллмана будується схема рішення монгошаговой завдання, що складається з 2-х частин:
1) Зворотний хід: від останнього кроку до першого отримують безліч можливих оптимальних (В«умовно-оптимальнихВ») управлінь.
2) Прямий хід: від відомого початкового стану до останнього з отриманого безлічі В«умовно-оптимальнихВ» управлінь складається шукане оптимальне управління для всього процесу в цілому.
Оптимальну стратегію управління можна отримати, якщо спочатку знайти оптимальну стратегію управління на n-му кроці, потім на двох останніх кроках, потім на трьох останніх кроках і т.д., аж до першого кроку.
Щоб можна було використовувати принцип оптимальності практично, необхідно записати його математично. Означимо через z1 (xn-1), z2 (xn-2), ..., zn (x0) умовно-оптимальні значення збільшень цільової функції на останньому кроці, двох останніх, ..., на всій послідовності кроків відповідно. p> Тоді для останнього кроку:
z1 (xn-1) = (min) {Fn (xn-1, un)},
де un - безліч допустимих (можливих) управлінь на n-му кроці, xn-1 - можливі стану системи перед n-им кроком.
Для двох останніх кроків:
z2 (xn-2) = (min) {Fn-1 (xn-2, un-1) + z1 (xn-1)}.
Для k останніх кроків:
zk (xn-k) = (min) {Fn-k +1 (xn-k, un-k +1) + zk-1 (xn-k +1)}.
Для всіх n кроків:
zn (x0) = (min) {F1 (x0, u1) + zn-1 (x1)}.
Отримані рекурентні співвідношення називають функціональними рівняннями Беллмана.
При цьому згідно з визначенням zn (x0) = F *.
3. Задача оптимального розподілу ресурсів
а) Постановка завдання.
Завдання на оптимальний розподіл ресурсу, який можна використовувати різним чином, виникають при розробці оперативних та перспективних планів особливо часто. До ним відносяться завдання про розподіл коштів на придбання обладнання, закупівлю сировини і найм специалистов; завдання про розподіл товара по торгових підприємствах і складах; завдання з визначення послідовності пропорцій між продукцією с/г виробництва, призначеної для реалізації та відтворення і т.д.
Розглянемо задачу оптимального розподілу заданого обсягу капіталовкладень у кілька підприємств.
Нехай на реконструкцію і модернізацію 4-х своїх філій фірма має можливість виділити 200 млн. руб. Очікуваний приріст прибутку залежить як від фінансованого філії, так і від обсягу цього фінансування. Однак, приріст прибутку в окремо взятому філії не залежить від вкладених коштів у інші філії, а загальний прибуток фірми дорівнює сумі всіх приростів по філіях. Слід визначити оптимальний розподіл капіталовкладень між філіями, максимізуючи загальний приріст прибутку фірми. p> У даному випадку мова йде про одноразове розподілі коштів, і тому завдання сама по собі не є динамічною. Однак, її можна найбільш просто вирішити як В«багатокроковогоВ», якщо об'єкти капіталовкладень (філії) включати до розгляд послідовно, тобто на кожному кроці до розглянутих додавати наступний.
При такому підході можна використовувати функціональні рівняння Беллмана. Для їх вирішення в табульованих вигляді загальний обсяг капіталовкладень розбивається на N інтервалів з кроком (для нашої задачі покладемо N = 4, тоді = 200/4 = 50 млн. руб.). Тобто значення функцій, що входять до рівняння Беллмана, будуть визначатися тільки в точках, кратних (у нашому прикладі в точках 0, 50, 100, 150, 200).
Нехай очікуваний приріст прибутку філій при відповідних капіталовкладеннях заданий таблицею.
Кап. ВложеніяПрірост прибутку за филиалам12345025303628100607064561501009095110200140122130142
С = 200 - загальний обсяг розподіляються засобів;
х - об'єм коштів, що виділяються філіям (на кожному кроці), 0? х? C.
F i (x i < span align = "justify">) - очікуваний приріст i-тої фірми при виділенні їй х i засобів. Тоді цільова функція
F = F 1 (x 1 ) + F 2 (x 2 ) + F 3 (x 3
