Њзбекистон республикаси олий ва њрта махсус

Dinamik dasturlash masalasining umumiy qo‘yilishi. Bellmanning funksional tenglamalari

Vaqtga bog„liq ravishda o„zgaruvchan va boshqarish mumkin bo„lgan tizimni ko„rib chiqamiz. Bu tizimni T ta bosqichlarga ajratish mumkin deb faraz qilamiz

t  1,2,...,T . Har bir bosqichning boshidagi tizimning holatini X _t bilan belgilaymiz.
X_t  X_1t , X _2t ,..., X _mt .

Тaraqqiyot jarayonida tizimning holati o„zgaradi. Uning
^X t 1
holatdan X _t

holatga o„tishiga U_t
boshqarish ta‟sir qiladi. Demak,
X _t o„zgaruvchi
^X t 1
va U_t

o„zgaruvchilarning funksiyasidan iborat bo„ladi, ya‟ni

X_t  X_{t 1} ,U_t .

Bu yerda U_t
mumkin bo„lgan boshqarishlar to„plami G_t
U_t  G_t .
ga tegishli, ya‟ni

Bunday aniqlashlarda tizimning butun davr 0, T 
ichidagi taraqqiyoti

X ₀ , X₁ ,..., X_{T 1} , X_T
^{vektorlar ketma-ketligi orqali aniqlanadi. X  X} t ^
X t ^{- tizimning}

t
t bosqichda mumkin bo„lgan holatlar to„plami. Тizimning boshlang„ich X ₀ holatdan

X_T holatga o„tkazish uchun
U₀ ,U₁ ,...,U_{T 1} ,U_T
boshqarishlar ketma-ketligi, ya‟ni

strategiyalar xizmat qiladi. Тizimni eng yaxshi
X_T holatga o„tkazishni ta‟minlash

uchun
f_T ( X )
maqsad funksiyani kiritamiz.

f_T ( X )  _Z_t X_{t 1} , X_t ,
t 1

bu yerda
Z_t  X_{t 1} , X_t 
tizimning
^X t 1
holatdan
X _t holatiga o„tishida hisoblanadigan

va bu holatlarni solishtirib baholovchi funksiyadir.
Agar tizimning t bosqichdagi holatlar to„plami


^X T ^{, mumkin bo„lgan}

boshqarishlar to„plami G hamda tizimni bir holatdan ikkinchi holatga o„tkazish

qoidasi hamda bu holatlarni solishtiruvchi funksiya
Z_t  X_{t 1} , X_t 
berilgan bo„lsa, T

bosqichli tizim to„la aniqlangan bo„ladi. Bunday tizimni ifodalovchi dinamik dasturlash masalasi quyidagicha yoziladi:

Тizimni boshlang„ich holati X ₀ ma‟lum bo„lganda shunday

strategiyani tanlash kerakki, u
U_t  U₁ ,U ₂ ,...,U_T 

X_t
shartlarni qanoatlantirib
 (X_{t 1} ,U_t ),
X_t  X_t , U_t  G_t ,
t  1,...,T
(5.10)

f_T ( X )  _Z_t X_{t 1} , X_t 
t 1
(5.11)

funksiyaga ekstremal qiymat bersin.
Ushbu munosabatlardan ko„rinadiki, dinamik dasturlash masalasi ko„p
bosqichli tanlash masalasi bo„lib, uning U ^* optimal yechimi bir necha bosqichlarda
topilgan mumkin bo„lgan U_t boshqarishlar asosida tanlanadi.

Geometrik nuqtai nazardan dinamik dasturlash masalasini quyidagicha talqin

X
qilish mumkin. Umumiy holda tizimning boshlang„ich
^* holati va oxirgi
X _k holati

0
aniq berilmaydi hamda boshlang„ich holatning butun bir X ₀ sohasi va oxirgi



X

k
holatlarning ^* sohasi ko„rsatiladi.

Umumiy holda dinamik dasturlash masalasi quyidagicha ta‟riflanadi. Biror

boshqariluvchi X tizim boshlang„ich
X  X ^*
holatda bo„lsin. Vaqt o„tishi bilan

0 0

tizimning holati o„zgaradi va u
X  X ^*
oxirgi holatga o„tadi deb hisoblaylik. Тizim

k k

holatlarining o„zgarishi biror miqdoriy W -mezon bilan bog„liq deylik. Тizimning o„zgarish jarayonini shunday tashkil etish kerakki, bunda W -mezon o„zining optimal qiymatiga erishsin.

U - mumkin bo„lgan boshqaruvlar to„plami bo„lsin. U holda, masala X

tizimni
X  X ^* holatdan X  X ^*
holatga o„tkazishga imkon beruvchi shunday

0 0 k k

U ^* U
boshqaruvni topishdan iboratki, bunda
W (U )
mezon o„zining
W ^*  W (U ^* )

optimal qiymatiga erishsin.

Odatda tizimning X ₀ holatini sonli parametrlar bilan, masalan ajratilgan

fondlar miqdori, jalb qilingan investitsiyalar hajmi, sarflangan yonilg„i miqdori va hokazolar bilan ifodalash mumkin. Bu parametrlarni tizimning koordinatalari deb

ataymiz. U holda tizimning holatini X nuqta bilan va uning
X ₁ holatdan
X ₂ holatga

o„tishini X nuqtaning trayektoriyasi bilan va uning
X ₀ holatdan X _k
holatga o„tishini

X nuqtaning trayektoriyasi bilan tasvirlash mumkin. (5.1-rasm). (5.10) – (5.11) masalani yechishdan avval
^GT ^,GT 1,T ^,...,G1,2,...,T ^{ G}

belgilashlar kiritamiz. Bu yerda G_T

• 
  masalaning oxirgi T bosqichidagi aniqlanish
  

sohasi,
^GT 1,T

• 
  T va
  

T 1
bosqichlardagi aniqlanish sohasi,
^G1,2,...,T ^{ G}

• 
  berilgan
  

masalaning aniqlanish sohasi.

X₂



X
* 0

X

X
*
k
0 _X1
5.1-rasm. Тizimni bir holatdan boshqasiga o„tishi

Maqsad funksiyaning oxirgi bosqichdagi optimal qiymatini belgilaymiz:
f₁ ( X_{T 1} )
bilan

f₁ ( X_{T 1} )  max(min) Z_T X_{T 1} ,U_T 
^UT 1^GT
f₂ ( X_{T 2} )  max(min) Z_{T 1} X_{T 2} ,U_{T 1}  f₁ X_{T 1} 
^UT 2^GT 1,T
(5.12)

(5.13)

Хuddi shuningdek,
belgilaymiz. U holda
T 1
qadamdagi shartli optimal qiymatni
f₂ ( X_{T 2} )
bilan

f₃ ( X_{T 3} )  max(min) Z_{T 2} X_{T 3} ,U_{T 3}  f₂ X_{T 2} 
^UT 3^GT 2,T 1,T
(5.14)

f_k ( X
T k
)  max(min) Z
^UT k ^GT k ,,..., t
T k 1 ^X
T k


^,UT k 1
 f
k 1 ^X
T k 1
,
k  1,T 1
(5.15)

f_T ( X_n )  max(min) Z₁ X_n ,U₁  f_{T 1} X₁ 
U_T G_T
(5.16)

Bu yerda (5.12) – (5.16) ifodalar ortimallik tamoyilining matematik formadagi yozilishidan iborat bo„lib, ular “Bellmanning funksional tenglamalari” yoki “Dinamik dasturlashning asosiy funksional tenglamalari” deb ataladi.

Bu tenglamalar yordamida dinamik dasturlashning
T 1
bosqichdagi yechimini

so„nggi T bosqichdagi yechim orqali topiladi. Shuning uchun yuqoridagi munosabatlar Bellmanning rekkurent munosabatlari deb ataladi.

5. Dinamik dasturlash usuli

Dinamik dasturlashning optimallik tamoyiliga asosan har bir qadamda topilgan yechim faqat shu qadam nuqtai nazaridan emas, balki so„nggi, pirovard maqsad nuqtai nazaridan optimal bo„lishi kerak ekanligini ko„rgan edik. Dinamik dasturlash masalalarini yechish usullari uchun ana shu tamoyil asos qilib olingan.

Faraz qilaylik, birinchi qadamda boshqarish U₁
bo„lsin. Buning ta‟sirida tizim

X ₀ holatdan
X ₁ holatga o„tadi va natijada
Z₁ X ₀ ,U₁ 
yutuq keltiradi. Ikkinchi

qadamda U ₂
boshqarish tizimni
X ₁ holatdan
X ₂ holatga o„tkazadi va natijada

Z₂ X₁ ,U ₂ 
foyda keltiradi va hokazo. K qadamda U_k
boshqarish tizimni
^X k 1

holatdan
X _k holatga ko„chiradi va natijada
Z_k X_{k 1} ,U_k  yutuq keltiradi.

Demak, tizimni
X ₀ holatdan
X_T holatga ko„chirish uchun shunday

U  (U₁,U ₂ ,...,U_T )
boshqarishni (strategiyani) tanlash kerakki, undagi
Z X ,U  yutuq

T 0
(zarar) maksimal (minimal) bo„lsin, ya‟ni
f_T ( X ₀ )  Z (X ₀ ,U )  max (min).

Agar
Z X ,U  ni

T 0
Z_T (X ₀ ,U )  Z₁ (X ₀ ,U₁ )  Z₂ (X₁ ,U₂ )  ...  Z_T (X_{T 1} ,U_T )

yig„indi ko„rinishida ifodalasak, dinamik dasturlash masalasi

f_T (X ₀ )  Z(X ₀ ,U )  Z₁ (X ₀ ,U₁ )  Z₂ (X₁ ,U₂ )  ...  Z_T (X_{T 1} ,U_T )
funksiyaga maksimal (minimal) qiymat beruvchi
U  (U₁,U ₂ ,...,U_T )
boshqarishni topishga keltiriladi.
Bunday boshqarishni topish jarayoni esa quyidagicha amalga oshiriladi. Eng

avval jarayonni teskari yo„nalishda ( X_{T 1}
dan
X ₀ ga tomon) tahlil qilamiz. Buning

uchun oxirgi T bosqich uchun funksional tenglama

ko„rinishda bo„ladi.
f₁ ( X_{T 1} )  max(min) Z_T X_{T 1} ,U_T 
^UT 1^GT

Oxirgi T bosqichning boshida jarayon
^XT 1,1 ^{, X}T 1,2 ^{,..., X}T 1,k
holatlarda bo„lishi

mumkin deb faraz qilamiz. Soddalik uchun faqat butun sonli
ko„ramiz.
^XT 1,k ^{ X}T 1
holatlarni

Bu holatlarning har biri uchun T bosqichdagi shartli optimal U_{T ,1} ,U_{T ,2} ,...,U_{T ,k}

yechimlar va ularga mos keluvchi
Z_{T ,1} , Z_{T ,2} ,..., Z_{T ,k}
daromad (xarajat) lar topiladi.

U_{T ,1} ,U_{T ,2} ,...,U_{T ,k}
yechimlar orasida
^f1 ^XT 1 ^
funksiyaga maksimum (minimum) qiymat

beruvchi va optimal U ^*
strategiyaning tarkibiga kiruvchi
^* yechim topiladi. Lekin

T

U
bu yechim masalani yechish jarayonining ikkinchi bosqichida, ya‟ni jarayon to„g„ri

yo„nalishda ( X ₀
dan
X_{T 1} ga tomon) tekshirilganda topiladi.

Shunday qilib, oxirgi qadam optimallashtiriladi, ya‟ni bu qadamning boshida tizim qanday bo„lishidan qat‟iy nazar qabul qilinadigan yechim aniqlanadi.

So„ngra T 1 bosqichga o„tiladi. Bu qadam uchun funksional tenglama
f₂ ( X_{T 2} )  max(min) Z_{T 1}X_{T 2} ,U_{T 1}  f₁( X_{T 1})
^UT 2 ^GT 1,T

tuziladi.
Bu bosqichda ham, xuddi yuqoridagidek har bir mumkin bo„lgan


^XT 2,k ^{ X}T 2

holat uchun mumkin bo„lgan
^UT 1,k ^GT 1
yechim va unga mos keluvchi
^ZT 1,k
daromad

(xarajat) topiladi. So„ngra
Z_{T 1,k}  f₁ yig„indilarni o„zaro solishtirib, har bir
^XT 2,k
holatga

mos keluvchi yig„indi va unga mos keluvchi shartli optimal yechim U_{T 1,k} topiladi. Bu

yechimlar orasida
^f2 ^XT 2 ^
funksiyaga ekstremal qiymat beruvchi va optimal U ^*

T 1
strategiyaning tarkibiga kiruvchi U ^* topiladi.

Shunday yo„l bilan davom etib, jarayonning birinchi bosqichiga o„tiladi. Bu qadamda jarayon faqat bitta aniq holatda bo„lishi mumkin. Shuning uchun bu bosqichda oldingi bosqichlarda topilgan barcha shartli optimal yechimlarni nazarga

oluvchi va X ₀ holatga mos keluvchi optimal yechim topiladi.

Shunday qilib, hamma mumkin bo„lgan holatlar uchun ketma-ket
f₁ , f₂ ,..., f_{T 1} , f_T funksiyalarning qiymatlari va turli bosqich va holatlarga tegishli
yechimlar, shu jumladan U ^* optimal strategiyaning tarkibiga kiruvchi optimal
U ^* ,U ^* ,...,U ^* yechimlar topiladi. Bu yechimlar asosida tuzilgan U ^* strategiya f ( X )
T T 1 1 T 0

funksiyaga ekstremal qiymat beradi. Optimal

U ^*  U ^*,U ^*,...,U ^* ,U ^* 
1 2 T 1 T

strategiyani aniqlash uchun jarayonni to„g„ri yo„nalishda ( X ₀
dan
^XT 1
ga tomon)

yana bir marta tekshirib chiqish kerak. Bunda eng avval aniq boshlang„ich X ₀

holatdan va topilgan
f_T ( X ₀ )
funksiyaning qiymatidan foydalanib,

• 
  topiladi.
  

1

U

U
So„ngra

• 
  va
  

^fT 1
( X₁ )
funksiyaning qiymati orqali

• 
  topiladi va hokazo. Eng
  

T 1

1

2

U
oxirida U ^*
va f
T 1
( X₁ )
orqali U ^*
topiladi.

T
Dinamik dasturlash masalasini yechish jarayonini quyidagi misolda yaqqol ko„rsatish mumkin.
Masala. Eng qisqa yo„lni tanlash masalasi.
Faraz qilaylik, A va B punktlarni o„zaro bog„lovchi temir yo„llar to„ri berilgan bo„lsin (5.2-rasm).