Основне рекурентне співвідношення

Множина розв’язків оптимізаційних задач описується рекурентними співвідношеннями, аналогічними (1), (2), (4), (6) і (8).

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

У такій системі кожне рівняння відповідає одній вершині мережі. Ці рівняння зазвичай містять оператори типу мінімум або максимум праворуч від знака рівності, а величини й (або ) по обидві сторони від нього.

Синоніми ОРС: функціональне рівняння, основне функціональне рівняння Белмана.

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

Стани

Стан системи є найбільш важливим поняттям у ДП.

Стан системи в деякий момент часу визначається, як множина значень змінних системи в цей момент часу [2].

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

АПП. У ЗОВР стан описуються парою (у підприємства від 1 до вкладено одиниць вартості) (рис. 21).

	Крок j
fj-1(yj-pj(0))
...
yj-pj(0)
	xj=0
fj-1(yj-pj(1))
... yj-pj(1)
yj-pj(1)
	xj=1 fj(yj)
fj-1(yj-pj(2)) ...	yj
	xj=2
yj-pj(2)
	xj=3
fj-1(yj-pj(3))
...
yj-pj(3)

Рис. 21.

У цій парі міститься інформація, достатня для прийняття поточного рішення, а саме: які проекти допустимі для -го підприємства. У даній ситуації не треба знати, як ми прийшли в стан , тобто, як були розподілені кошти в об'ємі на інвестування підприємств від 1 до .

АЗП. У ЗЗНШ вершини мережі є можливими станами системи. Дуги, що виходять із деякої вершини, представляють різні рішення, які можна приймати в даному стані.

У ЗЗНШ у номері вершини () міститься інформація, достатня для ухвалення поточного рішення, а саме: по яких дугах можна перейти до наступного (()-го) слою (рис. 22). У даній ситуації не треба знати, як ми підемо зі станів наступного шару, тобто, яким чином були досягнуті довжини найкоротших шляхів й .

	Крок j		Крок j+ 1			Крок n
		fj +1(k 1)		...
fj (s)
		fj +1(k 2)		...		...
		fj +1(k 3)
				...

Рис. 22.

У моделях ДП стани зазвичай групуються в етапи (кроки, слої) і перехід здійснюється послідовно від етапу до етапу. Слід зазначити, що існує ряд задач, у яких мережа станів не має властивість слоїстості.

Із властивостей стану випливають наступні особливості моделей ДП.

6.5 Умова марковості (відсутність післядії)

Умові марковості повинна задовольняти будь-яка модель ДП.

Нехай - множина всіх можливих станів на етапі .

Кожному етапу ставиться у відповідність своя керована змінна таким чином, що кожному варіанту розв’язку відповідає певне значення керованої змінної. Значення цієї змінної фігурує у виразі ЦФ, наприклад:

ЗЗНШ: керована змінна – дуга ; складова ЦФ: .

ЗОВР: кожному варіанту розв’язку стану відповідає своє значення керованої змінної ; складова ЦФ: .

Нехай:

- множина всіх допустимих розв’язків, за умови, що на етапі система перебуває в стані (цій множині відповідає множина всіх можливих значень керованої змінної);

- перетворений стан, тобто, стан , у який система перейде, якщо в стані буде обрано варіант рішення .

Умова відсутності післядії:

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