Tr›Œng §„i h(cid:228)c Vinh
T„p ch(cid:221) khoa h(cid:228)c, t¸p XXXVII, sŁ 2A-2008
V(cid:210) mØt b(cid:181)i to‚n ph'n phŁi fii(cid:214)n fi›(cid:238)c gi¶i b»ng ph›‹ng ph‚p Monte - Carlo
Tr˙n Xu'n Sinh (a), Th‚i Do•n ¢n (b)
Tªm t(cid:190)t. §(cid:211) gi¶i quy(cid:213)t b(cid:181)i to‚n ph'n phŁi fii(cid:214)n, ch(cid:243)ng t«i fi›a ra m« h(cid:215)nh to‚n h(cid:228)c l(cid:181) b(cid:181)i to‚n quy ho„ch l(cid:229)i ng(cid:201)u nhi“n, v(cid:237)i h(cid:181)m m(cid:244)c ti“u ph(cid:244) thuØc fi„i l›(cid:238)ng ng(cid:201)u nhi“n t›‹ng łng. Tı fiª, ch(cid:243)ng t«i x'y døng thu¸t to‚n Monte - Carlo, k(cid:213)t h(cid:238)p v(cid:237)i thu¸t to‚n gi¶i b(cid:181)i to‚n quy ho„ch l(cid:229)i nh»m t(cid:215)m ra ph›‹ng ‚n tŁi ›u.
I. B(cid:181)i to‚n 1.1. B(cid:181)i to‚n m(cid:181) ch(cid:243)ng t«i fi(cid:210) c¸p t(cid:237)i º fi'y, xu˚t ph‚t tı thøc t(cid:213) nh› sau: Gi¶ s(cid:246) t„i thŒi fii(cid:211)m x‚c fi(cid:222)nh n(cid:181)o fiª, C«ng ty fii(cid:214)n løc c˙n ph'n bŁ l›(cid:238)ng fii(cid:214)n A (KW) tı m nh(cid:181) m‚y fii(cid:214)n kh‚c nhau, d(cid:239)ng fi(cid:211) ph(cid:244)c v(cid:244) n fi(cid:222)a ph›‹ng (n‹i ti“u th(cid:244)). Nh(cid:181) m‚y fii(cid:214)n thł i cª s¶n l›(cid:238)ng l(cid:181) ai (KW). N(cid:213)u nh(cid:181) m‚y fii(cid:214)n thł i truy(cid:210)n t¶i fii(cid:214)n tr“n tuy(cid:213)n v(cid:210) n‹i ti“u th(cid:244) thł j th(cid:215) tß l(cid:214) h(cid:247)u (cid:221)ch ch(cid:216) cª th(cid:211) fi„t dij (tr“n 1KW) trong mØt thŒi gian x‚c fi(cid:222)nh. Chi ph(cid:221) truy(cid:210)n t¶i 1 (KW) fii(cid:214)n tı nh(cid:181) m‚y fii(cid:214)n thł i tr“n tuy(cid:213)n v¸n t¶i v(cid:210) n‹i ti“u th(cid:244) thł j l(cid:181) cij. Tuy nhi“n, nhu c˙u fii(cid:214)n wj º n‹i s(cid:246) d(cid:244)ng fii(cid:214)n thł j kh«ng th(cid:211) bi(cid:213)t tr›(cid:237)c fi›(cid:238)c v(cid:181) ph¶i coi nª nh› mØt fi„i l›(cid:238)ng ng(cid:201)u nhi“n, ph'n bŁ li“n t(cid:244)c v(cid:237)i m¸t fiØ x‚c su˚t l(cid:181) pj(wj), j = 1, 2, ..., n. H•y t(cid:215)m c‚ch ph'n phŁi fii(cid:214)n sao cho t(cid:230)ng chi ph(cid:221) v(cid:181) młc thi(cid:214)t h„i th˚p nh˚t, m(cid:181) b¶o fi¶m kh¶ n¤ng cung c˚p, ph(cid:244)c v(cid:244) nhu c˙u s(cid:246) d(cid:244)ng fii(cid:214)n º m(cid:231)i n‹i.
1.2. Thi(cid:213)t l¸p b(cid:181)i to‚n. K(cid:253) hi(cid:214)u xij l(cid:181) sŁ l›(cid:238)ng KW fii(cid:214)n chuy(cid:211)n tı nh(cid:181) m‚y fii(cid:214)n thł i, (i = 1, 2, ..., m), t(cid:237)i n‹i ti“u th(cid:244) thł j, (j = 1, 2, ..., n), trong mØt thŒi gian x‚c fi(cid:222)nh. Khi fiª t(cid:230)ng chi ph(cid:221) v¸n t¶i fii(cid:214)n cæa C«ng ty fii(cid:214)n t(cid:237)i n‹i ti“u th(cid:244) thł j l(cid:181)
m X
cijxij.
i=1 §(cid:229)ng thŒi sŁ l›(cid:238)ng fii(cid:214)n fi›(cid:238)c t¶i v(cid:210) j sˇ l(cid:181)
m X
zj =
dijxij, j = 1, 2, ..., n.
L(cid:243)c n(cid:181)y, cª th(cid:211) x¶y ra:
+ N(cid:213)u zj 6 wj, cª ngh(cid:220)a l(cid:181) nhu c˙u kh«ng b— h‹n kh¶ n¤ng. Trong tr›Œng h(cid:238)p n(cid:181)y cª wj − zj nhu c˙u kh«ng fi›(cid:238)c thøc hi(cid:214)n. K(cid:253) hi(cid:214)u vj l(cid:181) gi‚ tr(cid:222) thi(cid:214)t h„i do kh«ng fiæ fii(cid:214)n b‚n m(cid:231)i KW fii(cid:214)n t„i n‹i ti“u th(cid:244) thł j. L(cid:243)c n(cid:181)y gi‚ tr(cid:222) thi(cid:214)t h„i cæa C«ng ty t„i
1 - Nh¸n b(cid:181)i ng(cid:181)y 03/5/2008. S(cid:246)a ch(cid:247)a xong ng(cid:181)y 22/7/2008.
i=1
j sˇ l(cid:181) vj(wj − zj). Sø thi(cid:214)t h„i trung b(cid:215)nh do y“u c˙u kh«ng fi›(cid:238)c fi‚p łng º n‹i ti“u th(cid:244) j fi›(cid:238)c x‚c fi(cid:222)nh bºi kœ v(cid:228)ng to‚n Ej cæa fi„i l›(cid:238)ng ng(cid:201)u nhi“n vj(wj − zj). Khi fiª ta cª
Z ∞
Ej =
vj(wj − zj)pj(wj)dwj, zj 6 wj 6 ∞.
+ N(cid:213)u zj ≥ wj, cª ngh(cid:220)a l(cid:181) nhu c˙u kh«ng cao h‹n kh¶ n¤ng. Trong tr›Œng h(cid:238)p n(cid:181)y zj − wj l(cid:181) fiØ l(cid:214)ch sŁ KW fii(cid:214)n c(cid:223)n thıa kh«ng b‚n fi›(cid:238)c t„i n‹i ti“u th(cid:244) thł j. K(cid:253) hi(cid:214)u uj l(cid:181) gi‚ tr(cid:222) thi(cid:214)t h„i do m(cid:231)i KW fii(cid:214)n thıa, kh«ng b‚n fi›(cid:238)c t„i j. L(cid:243)c n(cid:181)y thi(cid:214)t h„i º tuy(cid:213)n t¶i fii(cid:214)n thł j sˇ l(cid:181) uj(zj − wj). Sø thi(cid:214)t h„i trung b(cid:215)nh do thıa fii(cid:214)n º tuy(cid:213)n j fi›(cid:238)c x‚c fi(cid:222)nh bºi kœ v(cid:228)ng to‚n E0
zj
j cæa fi„i l›(cid:238)ng ng(cid:201)u nhi“n uj(zj − wj).
Z zj
E0
uj(zj − wj)pj(wj)dwj, 0 6 wj 6 zj.
V¸y t(cid:230)ng chi ph(cid:221) v¸n t¶i cØng thi(cid:214)t h„i trung b(cid:215)nh cho ho„t fiØng cæa C«ng ty fii(cid:214)n
do thi(cid:213)u fii(cid:214)n c(cid:242)ng nh› thıa fii(cid:214)n fi›(cid:238)c m« t¶ bºi h(cid:181)m m(cid:244)c ti“u
j = 0
Z zj
Z ∞
i
n X
h m X
f =
→ min
cijxij +
vj(wj − zj)pj(wj)dwj +
uj(zj − wj)pj(wj)dwj
v(cid:237)i fii(cid:210)u ki(cid:214)n:
a) H„n ch(cid:213) v(cid:210) l›(cid:238)ng fii(cid:214)n cæa nh(cid:181) m‚y thł i
0 zj j=1 i=1
n X
xij 6 ai, i = 1, 2, ..., m;
b) V(cid:210) sŁ l›(cid:238)ng fii(cid:214)n fi›(cid:238)c t¶i v(cid:210) n‹i ti“u th(cid:244) thł j
j=1
m X
dijxij = zj, j = 1, 2, ..., n;
c) R(cid:181)ng buØc d˚u cæa ¨n
i=1
xij ≥ 0, i = 1, 2, ..., m; j = 1, 2, ..., n,
zj ≥ 0, j = 1, 2, ..., n.
Tı fi'y ta cª b(cid:181)i to‚n quy ho„ch ng(cid:201)u nhi“n
Z zj
Z ∞
n
io
h m X
n X
min
f =
cijxij +
vj(wj − zj)pj(wj)dwj +
uj(zj − wj)pj(wj)dwj
0 zj i=1 j=1
(1.1)
v(cid:237)i fii(cid:210)u ki(cid:214)n
n X
(1.2)
xij 6 ai, i = 1, 2, ..., m;
j=1
m X
(1.3)
dijxij − zj = 0, j = 1, 2, ..., n;
i=1
(1.4)
xij ≥ 0, i = 1, 2, ..., m; j = 1, 2, ..., n; zj ≥ 0, j = 1, 2, ..., n. B(cid:181)i to‚n (1.1)-(1.4) l(cid:181) b(cid:181)i to‚n quy ho„ch ng(cid:201)u nhi“n, cª h(cid:181)m m(cid:244)c ti“u ph(cid:244) thuØc
fi„i l›(cid:238)ng ng(cid:201)u nhi“n wj.
II. K(cid:213)t qu¶
2.1. §(cid:222)nh l(cid:253). B(cid:181)i to‚n (1.1) − (1.4) l(cid:181) b(cid:181)i to‚n quy ho„ch l(cid:229)i ng(cid:201)u nhi“n v(cid:237)i mi(cid:210)n
r(cid:181)ng buØc l(cid:181) t¸p l(cid:229)i, compact.
Chłng minh. X—t h(cid:181)m m(cid:244)c ti“u
Z zj
Z ∞
i
n X
h m X
f =
vj(wj − zj)pj(wj)dwj +
uj(zj − wj)pj(wj)dwj
cijxij +
0 zj
Z ∞
Z zj
j=1 n X i=1 m X n X n X
=
uj(zj − wj)pj(wj)dwj
cijxij +
vj(wj − zj)pj(wj)dwj +
0 zj j=1 j=1 j=1
trong ޻
i=1 = f1 + f2 + f3,
n X m X
f1 =
cijxij,
i=1 Z ∞ j=1 n X
f2 =
vj(wj − zj)pj(wj)dwj,
zj
Z zj
j=1 n X
uj(zj − wj)pj(wj)dwj.
f3 =
Ta th˚y h(cid:181)m f1 l(cid:181) h(cid:181)m tuy(cid:213)n t(cid:221)nh, f2 v(cid:181) f3 l(cid:181) h(cid:181)m t(cid:230)ng cæa c‚c kœ v(cid:228)ng to‚n, do fiª
nª c(cid:242)ng c‚c h(cid:181)m l(cid:229)i. V¸y f l(cid:181) h(cid:181)m l(cid:229)i.
M˘t kh‚c, ta th˚y mi(cid:210)n ch˚p nh¸n M l(cid:181) giao cæa c‚c n(cid:246)a kh«ng gian fiªng, n“n nª l(cid:181) t¸p l(cid:229)i fia di(cid:214)n fiªng. §(cid:229)ng thŒi cª th(cid:211) ch(cid:216) ra r»ng M kh‚c r(cid:231)ng v(cid:181) b(cid:222) ch˘n, do fiª nª l(cid:181) fia di(cid:214)n l(cid:229)i, fiªng.
0 j=1
2
Tı fiª suy ra fii(cid:210)u ph¶i chłng minh. K(cid:253) hi(cid:214)u x = (xij) ∈ Rm×n, z = (zj) ∈ Rn. §(cid:222)nh l(cid:253) 2.1 l(cid:181) c‹ sº cho vi(cid:214)c x'y døng thu¸t to‚n gi¶i b(cid:181)i to‚n (1.1)-(1.4).
2.2. Thu¸t to‚n B›(cid:237)c chu¨n b(cid:222). Ch(cid:228)n ng(cid:201)u nhi“n c‚c gi‚ tr(cid:222) w(0)
j
, j = 1, 2, ..., n. T„i w(0) = (w(0) j )
fi• ch(cid:228)n, gi¶i b(cid:181)i to‚n ph(cid:244) (1.1)-(1.4), fi›(cid:238)c nghi(cid:214)m (x(0), z(0), w(0)).
6= w(k)
, j = 1, 2, ..., n. T„i w(k+1) = (w(k+1)
K(cid:253) hi(cid:214)u f (x(0), z(0), w(0)) = β0 l(cid:181) gi‚ tr(cid:222) kß l(cid:244)c hi(cid:214)n t„i. B›(cid:237)c k, (k = 0, 1, ...). §• bi(cid:213)t gi‚ tr(cid:222) kß l(cid:244)c βk t„i w(k). Ch(cid:228)n ng(cid:201)u nhi“n c‚c gi‚ ) fi• ch(cid:228)n, gi¶i b(cid:181)i to‚n ph(cid:244)
tr(cid:222) w(k+1) j (1.1)-(1.4), fi›(cid:238)c nghi(cid:214)m (x(k+1), z(k+1), w(k+1)). K(cid:253) hi(cid:214)u f (x(k+1), z(k+1), w(k+1)) = βk+1. + N(cid:213)u βk+1 < βk th(cid:215) gi‚ tr(cid:222) kß l(cid:244)c hi(cid:214)n t„i l(cid:181) βk+1. G‚n k := k + 1, trº l„i b›(cid:237)c k. + N(cid:213)u ng›(cid:238)c l„i, ta lo„i bÆ w(k+1), trº l„i b›(cid:237)c k. B›(cid:237)c k(cid:213)t th(cid:243)c. V(cid:237)i k fiæ l(cid:237)n, t(cid:221)nh trung b(cid:215)nh m(cid:201)u
j j
k X
F k =
f (x(k), z(k), w(k)).
1 k
i=1
Ch(cid:243) (cid:253). Tı fii(cid:210)u ki(cid:214)n (1.2), (1.3) v(cid:181) (1.4) cho th˚y t¸p ph›‹ng ‚n cæa b(cid:181)i to‚n l(cid:181) kh‚c r(cid:231)ng (fii(cid:211)m cª to„ fiØ xij = 0, v(cid:181) zj = 0, v(cid:237)i m(cid:228)i i, j, l(cid:181) mØt ph›‹ng ‚n). M˘t kh‚c, c(cid:242)ng tı fii(cid:210)u ki(cid:214)n fi• n“u cho th˚y t¸p ph›‹ng ‚n b(cid:222) ch˘n. Do v¸y vi(cid:214)c gi¶i c‚c b(cid:181)i to‚n ph(cid:244) º m(cid:231)i b›(cid:237)c lu«n cª nghi(cid:214)m.
§(cid:211) chłng minh sø hØi t(cid:244) cæa thu¸t to‚n, ta nh(cid:190)c l„i mØt k(cid:213)t qu¶ quan tr(cid:228)ng trong
[4].
Cho b(cid:181)i to‚n
Z
F (x) =
(2.1),
f (x, w)p(w)dw → min
trong fiª x ∈ M ⊂ Rn; p(w) l(cid:181) h(cid:181)m m¸t fiØ cæa fi„i l›(cid:238)ng ng(cid:201)u nhi“n w.
Gi¶ s(cid:246) łng v(cid:237)i c‚c gi‚ tr(cid:222) m(cid:201)u w(k), b»ng ph›‹ng ph‚p Monte Carlo, cho ta d•y
ph›‹ng ‚n x(k) tŁt d˙n. V(cid:237)i k fiæ l(cid:237)n, ta cª
k X
f (x(k), w(k)).
F (k) =
1 k
K(cid:253) hi(cid:214)u (x∗, w∗) l(cid:181) ph›‹ng ‚n tŁi ›u, t›‹ng łng v(cid:237)i gi‚ tr(cid:222) h(cid:181)m m(cid:244)c ti“u F ∗ cæa b(cid:181)i
to‚n (2.1).
2.3. §(cid:222)nh l(cid:253) [4]. Cho kh«ng gian x‚c su˚t (Ω, Σ, P ). Gi¶ s(cid:246) f (∗, w) l(cid:181) h(cid:181)m l(cid:229)i; M l(cid:181) t¸p l(cid:229)i, compact; {x(k)} l(cid:181) d•y tŁt d˙n t›‹ng łng c‚c m(cid:201)u fiØc l¸p w(k). Khi fiª F (k) → F ∗ h˙u ch(cid:190)c ch(cid:190)n (h.c.c).
2.4. §(cid:222)nh l(cid:253). Ta cª
i=1
(F (k) − F ∗) = 0} = 1.
P { lim k→∞
Chłng minh. Nh› ch(cid:243)ng ta fi• th˚y trong fi(cid:222)nh l(cid:253) 2.1, b(cid:181)i to‚n (1.1)-(1.4) l(cid:181) b(cid:181)i to‚n quy ho„ch l(cid:229)i (h(cid:181)m m(cid:244)c ti“u f l(cid:229)i) v(cid:237)i t¸p ph›‹ng ‚n l(cid:229)i fia di(cid:214)n, kh‚c r(cid:231)ng v(cid:181) b(cid:222) ch˘n (t¸p ph›‹ng ‚n l(cid:229)i v(cid:181) compact). §(cid:229)ng thŒi v(cid:237)i c‚ch x'y døng d•y {x(k)} v(cid:181) ch(cid:228)n m(cid:201)u fiØc l¸p w(k) fi• n“u trong thu¸t to‚n cho ta d•y {x(k)} l(cid:181) tŁt d˙n.
Nh› v¸y c‚c fii(cid:210)u ki(cid:214)n cæa fi(cid:222)nh l(cid:253) 2.3 fi›(cid:238)c tho¶ m•n. Tı fiª suy ra fii(cid:210)u ph¶i chłng
2
minh.
III. Th¶o lu¸n. B(cid:181)i to‚n ph'n phŁi fii(cid:214)n l(cid:181) mØt trong nh(cid:247)ng b(cid:181)i to‚n c˙n s(cid:237)m cª fi›(cid:238)c nh(cid:247)ng c«ng tr(cid:215)nh nghi“n cłu hi(cid:214)u qu¶. Song song v(cid:237)i b(cid:181)i to‚n ph'n phŁi fii(cid:214)n l(cid:181) b(cid:181)i to‚n dø tr(cid:247) n›(cid:237)c cho c‚c h(cid:229) thuß fii(cid:214)n. Ch(cid:243)ng t«i hy v(cid:228)ng r»ng, v(cid:237)i thu¸t to‚n fi• n“u, tr“n m(cid:231)i m« h(cid:215)nh c(cid:244) th(cid:211), sˇ gªp ph˙n t(cid:221)ch cøc v(cid:181)o vi(cid:214)c (cid:230)n fi(cid:222)nh fii(cid:214)n hi(cid:214)n nay cæa Vi(cid:214)t Nam.
T(cid:181)i li(cid:214)u tham kh¶o
[1] Nguy(cid:212)n Qu(cid:253) Hß, Ph›‹ng ph‚p m« phÆng sŁ Monte Carlo, NXB §„i h(cid:228)c QuŁc gia H(cid:181) NØi, H(cid:181) NØi, 2004.
[2] Tr˙n Xu'n Sinh, C‚c ph›‹ng ph‚p ng(cid:201)u nhi“n gi¶i b(cid:181)i to‚n quy ho„ch, B(cid:181)i gi¶ng d(cid:239)ng cho Sau §„i h(cid:228)c, chuy“n ng(cid:181)nh X‚c su˚t thŁng k“ to‚n h(cid:228)c, §„i h(cid:228)c Vinh, 2006.
[3] Nguy(cid:212)n Duy Ti(cid:213)n v(cid:181) V(cid:242) Vi(cid:213)t Y“n, L(cid:253) thuy(cid:213)t x‚c su˚t, NXB Gi‚o d(cid:244)c, H(cid:181) NØi, 2001.
[4] Yuri M. Ermoliev and Vladimir I. Norkin, Monte Carlo optimization and path dependent nonstationary laws of Large numbers, IIASA, International Institute for applied systems analysis, 1998, Web: www.iiasa.ac.at.
Summary
On the problem of mange a electric solved by method of Monte-Carlo
In order to study the problem about supplying electricity, we set up a mathematical model, which is a stochastic convex programming with objective function depending on a stochastic variable. Then, we construct a Monte-Carlo algorithm combining with a algorithm for solving convex programming problems to find an optimization plan.
(a) Khoa To‚n, Tr›Œng §„i h(cid:228)c Vinh
(b) Cao h(cid:228)c 14, X‚c su˚t thŁng k“, Tr›Œng §„i h(cid:228)c Vinh.
