Алгоритм рішення задач динамічного програмування

Нехай в системі є певний запас ресурсу К, який треба розподілити між m агрегатами, А 1, А 2, …, Аm. Кожен агрегат Аi за умови давання йому ресурсу в розмирі х приносить дохід, що можна знайти за функцією ц (хi). Всі функції ц (хi) (i=1,2,…m) задані та є неубутніми. Треба знайти такий розподіл засобів К між агрегатами, за якого вони приносять найбільший дохід.

Значення ефективності знаходиться за формулою:

.

де i=1,2,…m, j=1,2,…К.

Якщо 0<�бi1 вона опукла донизу (рис. 2.4.2), а при бi=1 вона є лінійною (рис. 2.4.3).

Рисунок 2.4.3 — бi=1.

На першому етапі приймаємо вкладення засобів у перший агрегат, А 1, на другому — в агрегат, А 2 і так далі.

Система управління S в даному випадку — засоби або ресурси, які розподіляються. Стан системи S перед кожним кроком характеризується одним числом S — початковим запасом ще не вкладених засобів. В цій задачі етапним управлінням є засоби х 1, х 2,…xm, що виділяються агрегатам. Потрібно знайти оптимальне управління, тобто таку сукупність чисел х 1, х 2,…xm, за якої сумарних дохід буде максимальним:

.

Перший етап починаємо з оптимізації останнього m-го кроку. Нехай ми підійшли до цього кроку із залишком засобів S. Звичайно, треба вкласти всю суму S в агрегат Аm. Тому умовне оптимальне управління на m-ому кроці: віддати останньому агрегатові всі засоби S, тобто:

хm (S)=S,.

а умовний оптимальний виграш.

Wm (S)=цm (S).Задаючись цілою гамою значень S, для кожного значення S розраховуємо хm (S) та Wm (S). Таким чином останній крок оптимізовано.

На другому етапі переходимо до передостаннього (m-1)-го кроку. Припустимо ми підійшли до нього із запасом засобів S. Позначимо Wm-1(S) умовний оптимальний виграш на двох останніх кроках: (m-1)-м та m-м (який вже оптимізовано на першому етапі розв’язання). Якщо виділити (m-1)-му кроці (m-1)-му агрегату засоби у розмирі х, то на останній крок залишиться S-x. Тоді виграш на двох останніх кроках буде дорівнювати:

цm-1(х) + Wm (S-х),.

треба знайти таке х, за якого виграш максимальний:

Wm-1(S)=max{цm-1(x)+Wm (S-x)}.

Цей максимум — умовний оптимальний виграш за останні два кроки, а значення х, за якого цей максимум досягається — умовне оптимальне управління на (m-1)-м кроці.

На наступних етапах оптимізуємо (m-2)-ий, (m-3)-ий і т.д. кроки. В загальному випадку, для будь-якого і-го кроку знаходимо умовний оптимальний виграш за всі кроки до цього та до кінця за формулою:

Wі(S)=max{ці(x)+Wі+1(S-x)}.

А відповідне йому умовне оптимальне управління хі(S) — те значення х, за якого цей максимум досягається.

На останньому етапі дійшли до першого агрегату, А 1. На цьому кроці не треба перебирати значення S, оскільки точно відомо, що запас засобів перед першим кроком дорівнює К:

W*=W1(K)=max{ц1(x)+W2(K-x)}.

Таким чином максимальний виграш (дохід) від всіх агрегатів знайдений. Залишається лише «прочитати рекомендації». Те значення х, за якого досягається максимум, є оптимальне управління х 1* на першому кроці. Після того, як ці засоби вкладено у перший агрегат залишається К-х 1*. «Читаючи» рекомендацію для S=К-х 1*, другому агрегату надаємо оптимальну кількість засобів х 2*=х 2-(К-х 1*) і т.д. до кінця.