4
2.ШТА ЈЕ ДИНАМИЧКО ПРОГРАМИРАЊЕ?
Динамичко програмирање је посебан метематички апарат, који омогућује оптимално
планирање тзв. Вишеетапних процеса управљања. Ту спадају процеси у којима се доноси
низ одлука и оне се доносе постепено у времену. Многи задаци управљањапроцесима у
техници, економији, војсци, физици, биологији, итд могу се представити у виду
вишеетапних процеса, на које се може применити метода динамичких програмирања.
Основни циљ јесте добијање оптималног плана управљања, при чему се под оптималним
управљањем подразумева оно управљање које даје најбоље решење, односно решење којим
се постиже максимални циљ операције.
За практичну примену динамичког програмирања (писаћемо, краће DP метод)
потребно је да сваки разматрани процес има свој јасно постављен математички модел, са
прецизно дефинисаном функцијом цилља, који треба максимизирати или минимизирати,
као и ограничењима која се морају узети у обзир у тоју процеса. За овако постављен задатак,
уколико су задовољени услови које захтева примена ДП методе, треба наћи функционалне
релације применом принципа оптималности. У извесним случајевима могуће је наћи
аналитичко решење, али најчешће решење се налази нумеричком анализом, уз примену
развијених програма.
Одређивање оптималне стратегије заснива се на принципу оптималности који се,
према оснивачу ове дисциплине, назива Белманов принцип оптималности. У слободној
интерпретацији, можемо га формулисати као особину да оптимална стратегија, без обзира
на почетно стање и претходно решење, у свакој наредној етапи треба да одреди оптималну
стратегију у односу на претходно добијено стање, као резултат претходног решења.
Принцип оптималности се може изразити математички, помоћу функционалних једначина
или рекурзивних релација помоћу којих се изражавају везе између функција циља
посматране етапе и функције суседне етапе.
Динамичко програмирање је веома моћна алгоритамска стратегија којом се
проблеми решавају на следећи начин:
-идентификује се колекција подпроблема главног проблема
-та колекција се линеаризује – подпроблеми се решавају линеарно, почев од
најмањег па до највећег подпроблема, нашег полазног проблема идентификује се формула
којом се сваки подпроблем изражава у функцији претходних, једноставнијих подпроблема.
У динамичком програмирању немамо експлицитно присутан ДАГ, али у сваком
проблему динамичког програмирања он је имплицитно присутан, он је основа
линеаризације. Чворови тог ДАГ-а су подпроблеми, док гране представљају зависности
између подпроблема – ако је, да би решили подпроблем
?
, неопходно да претходно решимо
подпроблем
?
, онда у том ДАГ-у постоји грана из
?
у
?
. У том случају
?
се сматра за
подпроблем мањи од подпроблема
?
.
2
2
Милан Вугделија,
Динамичко програмирање
, Београд, 1999.
5
3.ОСНОВНИ ПОЈМОВИ И КАРАКТЕРИСТИКЕ ДП МОДЕЛА
Под термином систем подразумева се физички (технички, економски...) систем који
се може дефинисати као низ стања у одређеном временском интервалу.
3
Ако p
0
означава
почетно, а p
1
, p
2
,...p
n
,...стања система у узастопним временским тренуцима, онда постоји
релација
p
n
+ 1 = W (p
n
), n = 0, 1, 2,...,
која представља скуп вектора (p
0
, p
1
, p
2
,...,) као репрезентацију понашања система у
дискретним тренуцима времена n = 0, 1, 2, ..., тада се може рећи да такав скуп вектора
дефинише једну специјалну врсту процеса који се назива вишеетапни процес. Јасно је да је
оваква врста процеса дефинисана почетним стањем система p = p
0
и трансформацијом W (p),
што се симболично може представити са
[p, W (p)].
Процес се најједноставније може описати као понашање система у току времена. У
општем облику, скаларне функције G (p
0
, p
1
, p
2
, ..., p
n
) које зависе од процеса могу се, код
вишеетапних процеса, исказати као функција следећег типа
∑
i
=
0
n
G
(
pi
)
С тим у вези, нас ће пре свега интересовати разни процеси и управљања, односно
процеси који протичу у времену и на чији ток можемо утицати планирањем и реализацијом
одговарајућих активности.
Наравно, у вези са овом проблематиком, природно се намеће питање марљивости,
тј.како одредити који од два и више модела управљања процесом најбоље задовољава неке
унапред постављене критеријуме. Да би одговорили на ово питање, потребно је извршити
математичку карактеризацију овог задатка, тј. изабрати неки нумерички критеријум F којим
можемо довољно добро описати стање у процесу , па на тај начин измерити и саму
ефикасност његовим управљањем. Сасвим је јасно да ће кријеријум F при избору разних
модела управљања имати и различите нумеричке вредности на основу којих можемо
планирати неке акције у будућности тако да F достигне оптималну вредност, тј.максиумум
или минимум, у зависноти од тога како је постављен сам задатак.
Када је реч о управљању процесима треба рећи да поред методе динамичког
програмирања, постоје и друге математичке методе међу којима је метода динамичког
програмирања свакако најважнија. Метода ДП -а у процесу управљања процесом се
примењује на следећи начин: основна идеја у примени ове методе састоји се у томе да се
3
Р. Петровић,
Специјалне методе у оптимизацији система
, Техничка Књига, Београд, 1978.
