Суть задачі динамічного програмування.

Суть задачі динамічного програмування полягає у тому,щоб з області можливих станів її вибрати такий,при якому критерій Wбуде оптимальним.

Приклад. Нехай треба сформуватирозробкуS нафтогазових родовищ на період при чомувідомо сума грошовихінвестиційD,якірозподіляються за роками t_i. Початковий стан системи який характеризується кількістю грошових коштів вже вкладених в розробку та кінцевий стан системи ,який характеризується запланованою сумою інвестицій D.Треба таким чином розприділити кошти D за роками щоб сумарний дохід підприємства був maxW.Позначимо через суму коштів,що виділяються на початок року і-тому родовищу.Нехай кошти на і-тому етапі вже розподілені тобто вибраним управління ,яке означає що на початок і-того року родовищу виділені кошти ,кошти на х-етапи розрахунків отримаємо набір управління

Сумарний дохід за к- етапів буде як функція управління У динамічному програмуванні для maxW починають планувати процес з х- того року, поступово переходячи до х-1,х-2 і до -початку етапу системи.Щоб спланувати х-критерії крок треба знати х-1.Позначимо стан системи на попередньому кроці через S_х-1,1;S_x-2,1;переходячи до.Знаючи х-1 крокзнаходятьоптимальніуправління на х-кроці як функцію стану системи на х-1.

В якості оптимального значення обирають.Переносячи на попередні кроки приходять до оптимального стану систему на початку стані системи.Даний принцип відповідно до якого оптимальне продовження процесу відшуковується відносно процесу досягнутого на даний момент називається принципом оптимальності Велмена.

46. Суть принципу Бемнана. Для прийняття оптимального рішення на k -му кроці багатокрокового процесу потрібна оптимальність рішень на всіх його попередніх кроках, а сукупність усіх рішень дає оптимальний розв’язок задачі лише в тому разі, коли на кожному кроці приймається оптимальне рішення, що залежить від параметра етапу , визначеного на попередньому кроці.

Цей факт є основою методу динамічного програмування і є сутністю так званого принципу оптимальності Р. Белмана, який формулюється так:

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

Доведемо справедливість такого твердження, міркуючи від супротивного. Нехай маємо задачу на максимізацію функції і вектор є її оптимальним планом (стратегією, поведінкою) n -крокового процесу (n -вимірної задачі) з початковим параметром стану b.

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

,

але

,

що суперечливо. Отже, принцип оптимальності доведено.

47. Суть задачі вибору шляху в динамічній постановці. Нехай відомо схеми деякого переміщення.Рух можливий в будь якому напрямку але з різною вартістю.Необхідно знайти такий шлях з точки в ,щоб сума витрат була найменшою.

для розв'язку задачі розіб’ємо шляхи на 4 вертикальні зони розрахунку.Алгоритм розрахунку починаємо для кінцевої точки на 4 етапі 4 вертикалі можна попасти не інакше тільки по цій вертикалі. Позначаємо цей шлях стрілками.Для т.0.

Перше знаходимо шляхи від до інших точок ідучи по горизонталі до точки ,можна попасти на шляху що складає саму верхню горизонталь Розрахунок вартості при цьому аналогічно вертикалі.Знаходимо переміщення до точки ,що лежить на діагоналі.До цієї точки можна попасти по 3 шляхах

Вибираючи той який має найменше значення критерія переміщення найменш.є шлях переміщення 19, проставляємо стрілку над шляхом, що визначає переміщення

Такий розрахунок застосовуємо послідовно для інших точок,визначаємо множину всіх можливих шляхів переміщень або управлінь V.Результат є таким (стрілочки на малюнку відповідно переміщенню)

Те управління яке починається в закінчується в і буде оптимальним значенням.