Män hc: Váûn hnh Hãû thäúng âiãûn
Nhọm Nh mạy âiãûn - Bäü män Hãû thäúng âiãûn - ÂHBK Â Nàơng .
31
Chỉång 3

TÊNH TOẠN PHÁN BÄÚ TÄÚI ỈU CÄNG SÚT TRONG HÃÛ THÄÚNG ÂIÃÛN
BÀỊNG PHỈÅNG PHẠP QUI HOẢCH ÂÄÜNG

3.1. MÅÍ ÂÁƯU
Quy hoảch âäüng l mäüt phỉång phạp quy hoảch toạn hc nhàòm tçm låìi gii täúi
ỉu ca quạ trçnh nhiãưu bỉåïc (hồûc nhiãưu giai âoản). Tênh tỉì “âäüng” åí âáy nhàòm nháún
mảnh vai tr thåìi gian v sỉû xút hiãûn dy cạc quút âënh trong quạ trçnh gii bi toạn,
cng nhỉ thỉï tỉû cạc phẹp toạn cọ nghéa quan trng.
Quạ trçnh kho sạt âỉåüc chia thnh nhiãưu bỉåïc, åí mäùi bỉåïc ta sỉí dủng mäüt quút
âënh. Quút âënh åí bỉåïc trỉåïc cọ thãø âiãưu khiãøn quạ trçnh åí bỉåïc sau. Nhỉ váûy quy
hoảch âäüng tảo nãn mäüt dy quút âënh. Dy quút âënh âọ gi l sạch lỉåüc (hồûc cọ
khi l chiãún lỉåüc). Sạch lỉåüc tha mn mủc tiãu quy âënh gi l sạch lỉåüc täúi ỉu. Chè
tiãu täúi ỉu phi thãø hiãûn âäúi våïi ton bäü quạ trçnh nhiãưu bỉåïc.
Sau âáy âãø chøn bë tçm hiãøu näüi dung cå bn ca phỉång phạp quy hoảch âäüng
ta kho sạt mäüt thê dủ vãư quạ trçnh âiãưu khiãøn nhiãưu bỉåïc.
Gi thiãút cáưn tçm mäüt sạch lỉåüc täúi ỉu âãø phán phäúi ngưn väún ban âáưu X cho
mäüt hãû thäúng k xê nghiãûp hoảt âäüng trong n nàm sao cho låüi nhûn thu âỉåüc tỉì k xê
nghiãûp âọ sau n nàm l cỉûc âải.
ÅÍ âáy ngưn väún X cọ thãø l ngưn váût tỉ, sỉïc lao âäüng, cäng sút âàût ca mạy
mọc .v.v... Ngoi ra bi toạn cọ thãø xáy dỉûng theo nhỉỵng mủc tiãu khạc nhỉ chi phê vãư
nhiãn liãûu l cỉûc tiãøu, hiãûu qu täøng vãư lao âäüng l cỉûc âải v.v...
Sạch lỉåüc täúi ỉu åí âáy l bäü giạ trë ngưn väún âáưu tỉ cho tỉìng nh mạy åí mäùi
nàm sao cho låüi nhûn täøng sau n nàm l cỉûc âải.
Gi thiãút gi X
j
(i)

(i)
..., X
n
(i)
) (3-2)
Âáy l bi toạn âiãøn hçnh ca quy hoảch âäüng v cọ thãø phạt biãøu nhỉ sau :
Xạc âënh táûp giạ trë
( )
{ }
i
j
X ; i = 1,2 ...,k; j = 1, 2 ,...,n sao cho :
W(X,n) ⇒ max (3-3)
v tha mn :

()
∑
=
k
t
i
j
X
1
= X
j
: j = 1, 2 ..., n (3-4)
Mọn hoỹc: Vỏỷn haỡnh Hóỷ thọỳng õióỷn
Nhoùm Nhaỡ maùy õióỷn - Bọỹ mọn Hóỷ thọỳng õióỷn - HBK aỡ Nụng .
32

>
()
i
X
2
> ... >
( )
i
j
X
> .... >
( )
i
n
X (3-7)
Lồỡi giaới tọỳi ổu ồớ õỏy õổồỹc xaùc õởnh nhồỡ giaới quyóỳt mỏu thuỏựn sau õỏy : Thổồỡng
xờ nghióỷp saớn xuỏỳt õem laỷi lồỹi nhuỏỷn nhióửu laỷi coù tyớ lóỷ hao huỷt vóử nguọửn vọỳn cao (hổ
hoớng maùy moùc, sổớ duỷng nhióửu vỏỷt tổ, thióỳt bở, lao õọỹng). Ngoaỡi ra cỏửn õỷc bióỷt lổu yù laỡ
lồỹi nhuỏỷn cuớa k xờ nghióỷp phaới õaỷt giaù trở cổỷc õaỷi sau n nm, maỡ khọng phaới chố xeùt
tổỡng nm rióng reợ.
Baỡi toaùn xaùc õởnh saùch lổồỹc tọỳi ổu phỏn phọỳi nguọửn vọỳn X cho k xờ nghióỷp saớn
xuỏỳt trong n nm trón õỏy coù thóứ giaới quyóỳt theo hai hổồùng :
+ Hổồùng thổù nhỏỳt : Xaùc õởnh õọửng thồỡi bọỹ giaù trở
( )
{ }
i
j
X õóứ haỡm lồỹi nhuỏỷn
W(W1, W2 ..., Wn) õaỷt giaù trở cổỷc õaỷi trong khọng gian n chióửu. Trong trổồỡng hồỹp n
nhoớ, caùc haửm W

bỉåïc n ỉïng våïi nhỉỵng phỉång ạn kãút thục khạc nhau åí bỉåïc (n-1). Låìi gii âọ âỉåüc gi
l giạ trë täúi ỉu cọ âiãưu kiãûn åí bỉåïc n nhàòm âảt cỉûc trë hm mủc tiãu åí bỉåïc n (v
khäng quan tám âãún trảng thại ca hãû sau bỉåïc n).
Tiãúp tủc cáưn xạc âënh låìi gii täúi ỉu cọ âiãưu kiãûn åí bỉåïc (n - 1) ỉïng våïi mi
phỉång ạn kãút thục cọ thãø ca bỉåïc (n-2) sao cho hm mủc tiãu âảt cỉûc trë trong c hai
bỉåïc cúi (bỉåïc n - 1 v n)
Tiãúp theo kho sạt nhỉ váûy âãún bỉåïc âáưu tiãn. Åí mäùi bỉåïc ta tçm âỉåüc låìi gii
täúi ỉu cọ âiãưu kiãûn âm bo cho c dy quút âënh tiãúp theo âãún bỉåïc n l täúi ỉu. Th
tủc âọ phn ạnh ngun l täúi ỉu â trçnh by.
Sau khi thỉûc hiãûn xong trçnh tỉû ngỉåüc xạc âënh âỉåüc låìi gii (quút âënh) täúi ỉu
cọ âiãưu kiãûn åí mäùi bỉåïc, càn cỉï vo trảng thại ban âáưu â cho ca bi toạn, ta tiãún hnh
trçnh tỉû thûn tỉì bỉåïc 1 âãún bỉåïc n v xạc âënh dy quút âënh täúi ỉu.
Vãư màût toạn hc, nhåì viãûc chuøn nghiãn cỉïu quạ trçnh n bỉåïc vãư tỉìng bỉåïc,
phỉång phạp quy hoảch âäüng â lm gim thỉï ngun ca bi toạn, tảo thûn låüi âãø
gii. Ngoi ra nhåì nhỉỵng th tủc truy chỉïng mang tênh cháút chỉång trçnh họa nãn
phỉång phạp quy hoảch âäüng dãù dng thỉûc hiãûn trãn mạy tênh âiãûn tỉí säú.
ÅÍ âáy cáưn chụ ràòng viãûc mä t n giai âoản (trong thåìi gian) ca quạ trçnh chè
l quy ỉåïc, cng cọ thãø quan niãûm hãû gäưm n âäúi tỉåüng kho sạt trong mäüt giai âoản thåìi
gian hồûc täøng quạt l hãû gäưm k âäúi tỉåüng hoảt âäüng trong n giai âoản thåìi gian.

3.2. THNH LÁÛP PHỈÅNG TRÇNH PHIÃÚM HM BELLMAN
Xẹt bi toạn phán phäúi ngưn väún nhỉ sau: Gi thiãút ta âáưu tỉ ngưn väún ban
âáưu X
1
vo mäüt xê nghiãûp âãø sn xút hai màût hng A v B. Quạ trçnh kho sạt l n
nàm. Vo âáưu nàm thỉï nháút ngưn väún täøng X
1
âỉåüc phán lm hai pháưn: x
1
âãø sn xút

1
) trong âọ 0 < b < 1
Ngưn väún x
2
v (X
2
- x
2
) tiãúp tủc âáưu tỉ vo nàm thỉï hai âãø sn xút màût hng
A v B. Quạ trçnh tiãúp diãùn trong n nàm.
Mọn hoỹc: Vỏỷn haỡnh Hóỷ thọỳng õióỷn
Nhoùm Nhaỡ maùy õióỷn - Bọỹ mọn Hóỷ thọỳng õióỷn - HBK aỡ Nụng .
34
Giaù trở ban õỏửu X
1
cuợng nhổ sọỳ nm n õaợ bióỳt. Do coù sổỷ khaùc nhau giổợa caùc giaù
trở g(x
i
), h (X
i
- x
i
), a, b nón xuỏỳt hióỷn yóu cỏửu tỗm sổỷ phỏn phọỳi tọỳi ổu nguọửn vọỳn X
i

trong tổỡng nm sao cho tọứng lồỹi nhuỏỷn cuớa xờ nghióỷp sau n nm laỡ cổỷc õaỷi.

3.2.1. Caùch õỷt baỡi toaùn theo phổồng phaùp cọứ õióứn:
Baỡi toaùn phỏn phọỳi nguọửn vọỳn trón õỏy coù thóứ phaùt bióứu mọỹt caùch cọứ õióứn nhổ
sau:

) + h (X
n
- x
n
) max (3-8)
Trong õoù : 0 x
i
X
i
i = 1, 2, ..., n (3-9)
Vaỡ :
X
1
õaợ cho
X
2
= ax
1
+ b (X
1
- x
1
)
.............. (3-10)
X
n
= ax
n
+ b (X
n-1

hoaỷch õọỹng.

3.2.2. Caùch õỷt baỡi toaùn theo tinh thỏửn quy hoaỷch õọỹng.
óứ õồn giaớn ta giaớ thióỳt caùc haỡm lồỹi nhuỏỷn g(x
i
) vaỡ h (X
i
- x
i
) chố phuỷ thuọỹc vaỡo
lổồỹng vọỳn õỏửu tổ vaỡo õỏửu nm thổù i laỡ x
i
vaỡ (X
i
- x
i
), maỡ khọng thay õọứi theo thồỡi gian,
nghộa laỡ daỷng haỡm g(x
i
) vaỡ h (X
i
- x
i
) õọỹc lỏỷp vồùi thồỡi gian.
Nhồỡ saùch lổồỹc tọỳi ổu phỏn phọỳi nguọửn vọỳn, lồỹi nhuỏỷn cuớa xờ nghióỷp sau n nm
saớn xuỏỳt mỷt haỡng A vaỡ B õaỷt giaù trở cổỷc õaỷi f
n
(X
1
) laỡ haỡm cuớa nguọửn vọỳn ban õỏửu X

vọỳn õỷt vaỡo nm õỏửu tión laỡ X
1
.
Män hc: Váûn hnh Hãû thäúng âiãûn
Nhọm Nh mạy âiãûn - Bäü män Hãû thäúng âiãûn - ÂHBK Â Nàơng .
35
Biãøu thỉïc (3-11) cho ta cạch xạc âënh giạ trë f
1
(X
1
) nhỉ sau: cho x
1
nháûn cạc giạ
trë khạc nhau tỉì 0 âãún X
1
, tênh g(x
1
) v h (X
1
- x
1
) sau âọ xạc âënh f
1
(X
1
). Tỉì âáy tháúy
ràòng nãúu chè xẹt quạ trçnh sn xút 1 nàm, nãúu g (x
1
) > h (X
1

2
= ax
1
+ b (X
1
- x
1
) cng phi phán phäúi täúi ỉu trong nhỉỵng
nàm cn lải, åí âáy l 1 nàm cn lải. Vç váûy låüi nhûn thu âỉåüc åí nàm thỉï hai våïi säú väún
X
2
phi âảt cỉûc âải, bàòng f
1
(X
2
)
f
1
(X
2
) = f
1
[ax
1
+ b (X
1
- x
1
)] (3-12)
trong âọ f

1
) = max {g(x
1
) + h (X
1
- x
1
) + max [g(x
2
) + h (X
2
- x
2
)]} (3-14)
0 ≤ x
1
≤ X
1
0 ≤ x
2
≤ X
2

trong âọ:
x
2
= ax
1

(X

1
- x
1
).
Theo ngun l täúi ỉu ca quy hoảch âäüng, d åí nàm thỉï nháút giạ trë x
1
âỉåüc
chn thãú no, thç säú väún cn lải X
2
= ax
1
+ b (X
1
- x
1
) cng cáưn phi phán phäúi täúi ỉu
sút trong (n - 1) nàm cn lải âãø nháûn âỉåüc giạ trë låüi nhûn cỉûc âải f
n-1
(X
2
). Vç váûy âãø
cho täøng låüi nhûn sau n nàm l cỉûc âải cáưn xạc âënh x
1
sao cho âảt cỉûc âải phiãúm hm
sau âáy:
W
n
(x
1
,X

) = max {g(x
1
) + h (X
1
- x
1
) + f
n-1
[ax
1
+ b (X
1
- x
1
)]} (3-16)
Trong âọ f
n
(X
1
) l giạ trë cỉûc âải ca låüi nhûn trong n nàm khi ngưn väún täøng
âàût vo nàm âáưu l X
1
.
f
n-1
[ax
1
+ b (X
1
- x

(X
2
) = max {g(x
2
) + h (X
2
- x
2
) + f
n-2
[ax
2
+ b (X
2
- x
2
)]} (3-17)
0 ≤ x
2
≤ X
2

V tiãúp tủc tênh cho âãún f
1
(X
n
) l giạ trë cỉûc âải ca låüi nhûn 1 nàm cúi cng
khi väún âáưu tỉ l X
n
. Giạ trë f

) = b (X
n-1
- x
n-1
)

3.3. ẠP DỦNG:
Âãø minh ha th tủc xạc âënh sạch lỉåüc täúi ỉu theo phỉång trçnh phiãúm hm
Bellman ta xẹt vê dủ âån gin sau âáy:
Vê dủ 3-1: Váùn sỉí dủng bi toạn phán phäúi ngưn väún (thiãút bë) X
1
cho xê
nghiãûp sn xút hai màût hng. Gi thiãút hng nàm màût hng A cho låüi nhûn g(x
i
) = x
i
2
;
i = 1, 2, 3 ; màût hng B cho låüi nhûn h (X
i
- x
i
) - 2 (X
i
- x
i
)
2
; i = 1, 2, 3. Sau mäùi nàm
do hao mn, ngưn väún x

2
- x
2
), (X
3
- x
3
) sao cho låüi nhûn ca xê nghiãûp sau 3 nàm âảt cỉûc
âải.
Nhỉ trãn â trçnh by, quạ trçnh gii âỉåüc tiãún hnh theo cạc bỉåïc sau âáy:
a. Bỉåïc 1:
Bàõt âáưu tỉì nàm cúi cng, åí âáy l nàm thỉï ba. Ta xạc âënh låìi gii
täúi ỉu cọ âiãưu kiãûn ca nàm thỉï 3, nghéa l xạc âënh giạ trë ngưn väún âáưu tỉ x
3
cho sn
xút màût hng A åí nàm thỉï 3 khi gi thiãút ràòng täøng säú väún cn lải sau 2 nàm l X
3
v
phi âảt låüi nhûn cỉûc âải trong nàm thỉï ba l f
1
(X
3
). Åí âáy cọ:
f
1
(X
3
) = max [x
3
2

Xf


= 2x
3
- 4 (X
3
- x
3
) = 0 tổỡ õỏy :
x
3
=
3
2
X
3

vỗ
( )
2
3
31
2
x
Xf


= 6 > 0
nón giaù trở x

3
2

Vồùi x
3
= X
3
coù f
1
(X
3
) = X
3
2
.
Vỏỷy lồỡi giaới tọỳi ổu laỡ x
3
= 0, nghộa laỡ ồớ nm thổù ba, hoaỡn toaỡn khọng õỏửu tổ vọỳn
õóứ saớn xuỏỳt mỷt haỡng A maỡ tỏỳt caớ vọỳn X
3
duỡng õóứ saớn xuỏỳt mỷt haỡng B. ióửu õoù dóự hióứu
vỗ lồỹi nhuỏỷn do mỷt haỡng B õem laỷi gỏỳp õọi do A õem laỷi. Tuy nhión tyớ lóỷ hao moỡn vọỳn
khi saớn xuỏỳt B rỏỳt lồùn (70%) nhổng vỗ laỡ nm cuọỳi nón ta khọng quan tỏm õóỳn nhổợng
nm tióỳp nổợa.

b. Bổồùc 2:
Ta xaùc õởnh lồỡi giaới tọỳi ổu coù õióửu kióỷn ồớ nm thổù hai sao cho lồỹi
nhuỏỷn õaỷt cổỷc õaỷi trong caớ hai nm cuọỳi (thổù hai vaỡ thổù ba). Lồỹi nhỏỷn cổỷc õaỷi trong hai
nm cuọỳi f
2


Trong õoù :
X
3
= x
3
+ (X
3
- x
3
) = ax
2
+ b (X
2
- x
2
) = 0,75x
2
+ 0,3 (X
2
- x
2
)
Thay giaù rở f
1
(X
3
) vaỡo haỡm f
2
(X

cuợng duỡng õóứ saớn xuỏỳt mỷt haỡng B. Khi õoù lồỹi nhuỏỷn cổỷc õaỷi cuớa caớ
hai nm cuọỳi laỡ:
f
2
(X
2
) = 2,18X
2
2
khi lổồỹng vọỳn coỡn laỷi sau nm õỏửu laỡ X
2

c. Bổồùc 3:
Ta xaùc õởnh lồỡi giaới tọỳi ổu coù õióửu kióỷn cho nm õỏửu tión sao cho õaỷt
cổỷc õaỷi lồỹi nhuỏỷn trong caớ ba nm vaỡ coù giaù trở f
3
(X
1
) ổùng vồùi nguọửn vọỳn õỏửu tổ vaỡo nm
thổù nhỏỳt laỡ X
1
:
f
3
(X
1
) = max [x
1
2
+ 2 (X

2

Thay giaù trở f
2
(X
2
) vaỡo haỡm f
3
(X
1
) õóứ khaớo saùt cổỷc õaỷi. Tổồng tổỷ nhổ hai trổồỡng
hồỹp trón, haỡm f
3
(X
1
) laỡ mọỹt parabol loợm, giaù trở cổỷc õaỷi õaỷt ồớ bión (x
1
= 0 vaỡ x
1
= X
1
)
2
3
X
2
3
2X
3
X