Принцип оптимальності Белмана

Стани

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

Стан системи в деякий момент часу визначається, як множина значень змінних системи в цей момент часу [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

f_{j +1}(k ₁)

...

f_j (s)

f_{j +1}(k ₂)

...

...

f_{j +1}(k ₃)

...

Рис. 22.

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

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

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

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

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

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

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

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

Нехай:

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

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

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

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

Введемо поняття підшляху для спрямованої мережі. Шлях є підшляхом шляху , якщо .

Мережевий варіант принципу оптимальності: підшлях найкоротшого шляху сам є найкоротшим шляхом.

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

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

Це формулювання не що інше, як словесний запис твердження, яке міститься в ОРС. Так, якщо – вартість, яка відповідає оптимальній стратегії на етапах від до за умови, що на етапі система перебуває в стані , а – безпосередній економічний ефект, що досягається в результаті вибору рішення при заданому стані (ефект -го етапу), то

.

Іншими словами: яким би не був стан системи перед черговим кроком, рішення на цьому кроці потрібно обирати так, що б виграш на даному кроці плюс оптимальний виграш на всіх наступних кроках був максимальним.

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

Дата добавления: 2014-11-29