Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của trường đại học vinh năm 2009 tác giả: 8. Trần Xuân Sinh, Nguyễn Thị Thanh Hiền, Nguyễn Văn Hưng, Một lớp bài toán đầu tư tài chính.
AMBIENT/
Chủ đề:
Nội dung Text: Báo cáo nghiên cứu khoa học: "Một lớp bài toán đầu tư tài chính"
- Mét líp bµi to¸n ®Çu t− tµi chÝnh
TrÇn Xu©n Sinh (a) , NguyÔn ThÞ Thanh HiÒn (a)
NguyÔn V¨n H−ng (b)
Tãm t¾t. Trong bµi b¸o nµy, chóng t«i giíi thiÖu mét m« h×nh bµi to¸n ®Çu t− tµi chÝnh
mµ viÖc gi¶i nã ®−îc quy vÒ bµi to¸n chiÕc tói víi rµng buéc ngÉu nhiªn. Tõ ®ã chóng
t«i x©y dùng thuËt to¸n nh»m t×m ra ph−¬ng ¸n tèi −u.
I. B i to¸n
Mét nhµ ®Çu t− cã b ®¬n vÞ ®ång vèn, dù ®Þnh tham gia ®Çu t− vµo n c«ng ty kinh
doanh (ta gäi c«ng ty thø i lµ C«ng ty i, i = 1, ..., n). NÕu ®Çu t− 1 ®¬n vÞ ®ång vèn vµo
C«ng ty i th× cho l i suÊt lµ ci vµ chi phÝ ph¶i tr¶ lµ ai . Hái nªn ®Çu t− vèn nh− thÕ
nµo ®Ó cã tæng sè l i lín nhÊt.
§Ó thiÕt lËp m« h×nh to¸n häc, ta ký hiÖu I = {1, 2, ..., n} vµ xi , i ∈ I, lµ sù lùa chän
cña Nhµ ®Çu t− vµo C«ng ty i (xi = 1 nÕu C«ng ty i ®−îc lùa chän ®Çu t−, cßn xi = 0
lµ C«ng ty i kh«ng ®−îc lùa chän ®Çu t−). Khi ®ã ta cã bµi to¸n
max{f = c.x} (1)
víi ®iÒu kiÖn
ai xi b, (2)
i∈ I
x ∈ {0; 1}n , (3)
trong ®ã c = (ci ), x = (xi ), c.x = i∈I ci xi .
M« h×nh bµi to¸n nh− trªn, trïng víi m« h×nh bµi to¸n chiÕc tói cæ ®iÓn, cã thÓ
gi¶i b»ng ph−¬ng ph¸p quy ho¹ch ®éng (xem [2]).
Víi mçi sè nguyªn k vµ h, (k = 1, n, h = 0, b), ta ®Æt
k k
h; xi ∈ {0; 1}, i = 1, k (∗).
Fk (h) = max ci xi : ai xi
i=1 i=1
§iÒu ®ã cã nghÜa r»ng Fk (h) lµ gi¸ trÞ lín nhÊt cña hµm f khi c¸c ®å vËt ®−îc chän
tõ k lÇn ®Çu tiªn vµ träng l−îng cña c¸i tói lµ h.
Víi k = 1, ta cã
F1 (h) = max {c1 x1 } = c1 .1 = c1 ; h = 0, b.
x1 ∈{0;1}
1) NhËn bµi ngµy 28/05/2009. Söa ch÷a xong ngµy 24/07/2009
- §èi víi k = 2, n; h = 0, b, c«ng thøc (*) cã thÓ viÕt l¹i
k−1
k
h − ak xk ; xi ∈ {0; 1}, i = 1, k .
Fk (h) = max ci xi : ai xi
i=1 i=1
Khi ®ã ta cã
k−1
Fk (h) = max ck xk + max ci xi ,
xk ∈{0;1} xi ∈{0;1}
i=1
víi ®iÒu kiÖn
k −1
h − ak xk ; xi ∈ {0; 1}, i = 1, k.
ai xi
i=1
Tõ ®ã ta ®−îc
Fk (h) = max {ck xk + Fk−1 (h − ak xk )}.
xk ∈{0;1}
Ký hiÖu
F0 (h) = 0; h = 0, b,
ta cã c«ng thøc ®Ö quy nh− sau:
Fk (h) = max {ck xk + Fk−1 (h − ak xk )}, k = 1, n, h = 0, b. (∗∗)
xk ∈{0;1}
Tõ c«ng thøc (**), ng−êi ta còng cã thÓ biÕn ®æi ®Ó cã ®−îc c«ng thøc ®Ö quy sau
®©y, gäi lµ HÖ thøc Dantzig
Fk (h) = max{Fk−1 (h); ck + Fk−1 (h − ak )}, nÕu h = ak , b, (∗ ∗ ∗)
Nh− vËy, ®Ó gi¶i bµi to¸n c¸i tói ® nªu, ta chia ra c¸c bµi to¸n nhá d¹ng ®Ö quy
(**) hoÆc (***) lÇn l−ît k = 1, 2, ..., n; h = 0, 1, ..., b. KÕt qu¶ ph−¬ng ¸n tèi −u cña bµi
to¸n t−¬ng øng Fn (b) = f (x∗ ) th× x∗ lµ ph−¬ng ¸n tèi −u cÇn t×m.
Trong thùc tÕ thÞ tr−êng tµi chÝnh, c¸c gi¸ trÞ l i suÊt ci vµ chi phÝ ai th−êng biÕn
®éng ngÉu nhiªn. §Ó gi÷ cho ci cè ®Þnh, C«ng ty i, i ∈ I cã thÓ ®iÒu chØnh cho ai biÕn
®éng theo "gi¸ tham chiÕu" ngÉu nhiªn wi víi biªn ®é dao ®éng lµ wi ∈ [wi , wi ].
Trong bµi viÕt nµy, chóng t«i nªu ra mét h−íng gi¶i quyÕt bµi to¸n khi cã sù biÕn
®éng ngÉu nhiªn vÒ chi phÝ nh− ® nªu.
II. C¸c kÕt qu¶ chÝnh
2.1. Bµi to¸n ®Çu t− tµi chÝnh cã rµng buéc ngÉu nhiªn
Gi¶ sö ai , i = 1, ..., n phô thuéc ®¹i l−îng ngÉu nhiªn wi , i = 1, ..., n. Ký hiÖu w = (wi )
lÊy gi¸ trÞ trong W ⊆ Rn ; ®é ®o x¸c suÊt P trªn W lµ P (w ∈ W ) = P (W ) = 1. Khi ®ã
+
bµi to¸n (1)(2)(3) trë thµnh bµi to¸n quy ho¹ch víi rµng buéc ngÉu nhiªn
n
max f = ci xi (4)
i=1
- víi ®iÒu kiÖn
n
b ≥1−ε
P wi xi (5)
i=1
xi ∈ {0; 1}, i = 1, 2, ..., n. (6)
trong ®ã ε > 0, ®ñ bÐ cho tr−íc nµo ®ã.
T×m mét ®iÓm x∗ ∈ {0; 1}n víi x¸c suÊt
Nh− vËy bµi to¸n lóc nµy ®Æt ra lµ:
n
b ≥ 1 − ε sao cho ®¹t max f .
P w i xi
i=1
Do kh«ng ph¶i dÔ dµng duyÖt hÕt c¸c ph−¬ng ¸n cña bµi to¸n ®Æt ra khi n kh¸
lín, cho nªn chóng ta cÇn khai th¸c c¸c tÝnh chÊt cña nã.
2.2. C¸c gi¶ thiÕt ban ®Çu. §Ó nghiªn cøu bµi to¸n (1)(2)(3), trong bµi viÕt nµy,
chóng t«i ®−a ra mét sè gi¶ thiÕt ban ®Çu nh− sau:
(i) C¸c ®¹i l−îng ci , ai , i = 1, ..., n vµ b nguyªn.
(ii) C¸c ®¹i l−îng ngÉu nhiªn wi ∈ [wi , wi ], trong ®ã wi ≥ 0 lµ gi¸ trÞ giao ®éng thÊp
nhÊt cã thÓ ®èi víi gi¸ tham chiÕu cña C«ng ty i; cßn wi lµ gi¸ giao ®éng cao nhÊt cã
thÓ ®èi víi gi¸ tham chiÕu cña C«ng ty i (xem [1]).
(iii) C¸c ®¹i l−îng wi ® ®−îc s¾p xÕp kh«ng gi¶m, cßn ci s¾p xÕp kh«ng t¨ng. §iÒu
®ã cã nghÜa lµ nÕu i < j th× wi wj vµ ci ≥ cj .
(iv) C¸c ®¹i l−îng ngÉu nhiªn {wi }i∈I ®éc lËp vµ ph©n bè ®Òu trªn ®o¹n [0, 1].
LÊy β ∈ {0, 1, ..., n} vµ chän I ⊆ I, β ∈ {0, ..., |I |}, S ⊆ I cã b¶n sè β , nghÜa lµ |S | = β .
Ta xÐt bµi to¸n
max{f = c.x} (7)
víi ®iÒu kiÖn
b, ∀S ⊆ I ,
w i xi + w i xi + w i xi (8)
i∈ S i∈I \S i∈ I
/
x ∈ {(0; 1}n . (9)
Bµi to¸n (7)-(9) ® ®−îc c¸c t¸c gi¶ D.Bertsimas vµ M. Sim ®Ò cËp tíi trong [4] vµ
O.Klopfenstein vµ D.Nace nghiªn cøu trong [5].
2.3. TÝnh chÊt
§Þnh lý 2.3.1. Gi¶ sö víi mäi i ∈ I, wi = w > 0 vµ (wi − wi ) = δ > 0. Khi ®ã ph−¬ng
¸n tèi −u x∗ cña bµi to¸n (7) − (9) tho¶ m·n
nÕu β (w + δ ) b
min{n; [b − βδ/w]},
x∗ =
i
nÕu ng−îc l¹i.
[b/(w + δ )],
i∈I
trong ®ã ký hiÖu [a] lµ phÇn nguyªn cña a.
Chøng minh. Tr−íc hÕt chóng ta nhËn xÐt r»ng mçi ph−¬ng ¸n tèi −u cña bµi to¸n
(7) − (9) lµm cùc ®¹i i∈I xi , víi xi ∈ {0; 1}. Gi¶ sö r»ng β (w + δ ) b. §iÒu nµy cã nghÜa
- lµ ph−¬ng ¸n tèi −u x∗ cña (7) − (9) cã Ýt nhÊt β phÇn tö kh¸c 0, tøc lµ i∈I x∗ ≥ β . V×
i
vËy, x∗ trong thùc tÕ lµ ph−¬ng ¸n tèi −u cña bµi to¸n max xi , víi rµng buéc
i∈I
b − βδ, xi ∈ {0; 1}.
i∈I wxi
B©y giê nÕu β (w + δ ) > b, mét ph−¬ng ¸n cña (7) − (9) kh«ng thÓ cã nhiÒu h¬n β − 1
phÇn tö kh¸c 0. Do ®ã mét ph−¬ng ¸n tèi −u x∗ cña (7) − (9) lµ ph−¬ng ¸n tèi −u cña
bµi to¸n max i∈I xi , víi ®iÒu kiÖn b, xi ∈ {0; 1}. Nh− vËy §Þnh lý
i∈I (w + δ )xi
®−îc chøng minh.
LÊy tËp con V ⊆ W. XÐt bµi to¸n
max(max{f = cx}) (10)
x
V
víi ®iÒu kiÖn
V ⊆ W : P (V ) ≥ 1 − ε, (11)
∀w ∈ V : w.x b,
x ∈ {0; 1}n . (12)
§Þnh lý 2.3.2. Ph−¬ng ¸n x∗ cña bµi to¸n (4) − (6) lµ tèi −u khi vµ chØ khi tån t¹i
V ⊆ W víi P (V ) ≥ 1 − ε sao cho (V, x∗ ) lµ ph−¬ng ¸n tèi −u cña bµi to¸n (10) − (12).
Chøng minh. Râ rµng x∗ lµ ph−¬ng ¸n cña bµi to¸n (4) − (6), khi vµ chØ khi tån t¹i
V ⊆ W : P (V ) ≥ 1 − ε sao cho (V, x∗ ) lµ ph−¬ng ¸n cña bµi to¸n (10)-(12). Chó ý r»ng
nÕu V cã d¹ng V = {w ∈ W : wx b} th× P (wx b) ≥ P (V ). Khi ®ã (V, x∗ ) lµ ph−¬ng ¸n
tèi −u cña bµi to¸n (10)-(12) khi vµ chØ khi x∗ lµ ph−¬ng ¸n tèi −u cña (4) − (6). §ã lµ
®iÒu ph¶i chøng minh.
Víi mçi i ∈ I , ta ký hiÖu
wi − wi
ηi = .
wi − wi
Râ rµng ta cã ηi ∈ [0; 1] lµ mét biÕn ngÉu nhiªn.
LÊy β ⊆ {0, 1, ..., n} lµ b¶n sè cña tËp hîp I nµo ®ã, nghÜa lµ |I | = β . XÐt bµi to¸n
max ci x i (13)
i∈I
víi ®iÒu kiÖn
b, ∀S ⊆ I, |S | = β,
wi xi + wi xi (14)
i∈S
i∈ I \S
x ∈ {0; 1}n . (15)
Víi mçi x ∈ {0; 1}n , ta ký hiÖu
I (x) = {i ∈ I : xi = 1}.
- §Þnh lý 2.3.3.[5]. Ta cã bÊt ®¼ng thøc
b) ≥ P
P (w.x ηi β,
i∈ I
víi mäi ph−¬ng ¸n x cña bµi to¸n (13) − (15)
LÊy I ⊆ I vµ β ∈ {0, ..., |I |}, chóng ta xÐt bµi to¸n
max{f = c.x} (16)
víi ®iÒu kiÖn
w i xi + w i xi + w i xi b, (17)
i∈S i∈ I \S i∈I
/
x ∈ {0; 1}n , (18)
lÊy víi mäi S ⊆ I , |S | = β .
Bµi to¸n (16)-(18) ®−îc ký hiÖu lµ (RKP (I , β )).
Bµi to¸n (13)-(15) lµ tr−êng hîp riªng cña (RKP (I , β )) khi I = I, β = n.
§Þnh lý 2.3.4. [5]. LÊy β ∈ {0, ..., n}. Gi¶ sö x∗ lµ ph−¬ng ¸n tèi −u cña (RKP (I, β )).
Khi ®ã
(i) nÕu β |I (x∗ )| th× x∗ lµ ph−¬ng ¸n tèi −u cña (RKP (I (x∗ ), β )),
(ii) nÕu β ≥ |I (x∗ )| th× x∗ lµ ph−¬ng ¸n tèi −u cña (RKP (I, n)), tøc lµ ph−¬ng ¸n tèi
−u cña bµi to¸n (7) − (9).
§Þnh lý 2.3.5 [5]. Gi¶ sö r»ng ∀i ∈ I, wi − wi = δ > 0, {wi /δ }i∈I vµ b/δ lµ sè nguyªn.
Khi ®ã tån t¹i I ∗ ⊆ I vµ β ∗ ∈ {0, ..., |I ∗ |} sao cho mçi ph−¬ng ¸n tèi −u cña (16) − (18)
lÊy víi I ∗ , β ∗ còng lµ ph−¬ng ¸n tèi −u cña bµi to¸n (4) − (6).
Trªn c¬ së c¸c §Þnh lý 2.3.1, 2.3.4 vµ 2.3.5 ta cã thÓ tr×nh bµy thuËt to¸n vµ vÝ dô
sau ®©y ®Ó gi¶i bµi to¸n ®Çu t− tµi chÝnh víi d÷ liÖu dao ®éng ngÉu nhiªn (4)-(6).
2.4. ThuËt to¸n gi¶i bµi to¸n (4)(5)(6)
Trong thuËt to¸n sau ®©y, gi¸ trÞ cña β t¨ng dÇn cho tíi khi ph−¬ng ¸n tèi −u cña
bµi to¸n (7) − (9) lµ ph−¬ng ¸n cña bµi to¸n (4) − (6), tøc lµ khi β = k = n.
B−íc 1. §Æt k = 0.
B−íc 2. Gi¶i bµi to¸n (RKP (I, k)). Gi¶ sö ®−îc ph−¬ng ¸n tèi −u lµ x(k) .
B−íc 3. §Æt I = I (x(k) ). X¸c ®Þnh β lµ gi¸ trÞ lín nhÊt cña {0, ..., |I |} sao cho
x(k) lµ ph−¬ng ¸n cña bµi to¸n (RKP (I , β )).
B−íc 4. TÝnh cËn d−íi U P i∈I wi b
NÕu U ≥ 1 − ε, th× x(k) lµ ph−¬ng ¸n cña (4) − (6). Dõng l¹i.
Ng−îc l¹i, sang b−íc 5.
B−íc 5. G¸n k := β + 1, trë l¹i b−íc 2.
- Chó ý
b = P (w.x(k) b). Do vËy thuËt to¸n sÏ dõng chØ
+ T¹i B−íc 4, ta cã P i∈I wi
víi mét ph−¬ng ¸n cña (4) − (6). Ngoµi ra, x(k) lµ ph−¬ng ¸n cña (RKP (I , k)) (xem
§Þnh lý 2.3.4), chóng ta cã β ≥ k. Do vËy, viÖc t¨ng chØ sè k t¹i mçi vßng lÆp ®¶m
b¶o sù héi tô cña thuËt to¸n (thùc ra khi k = n = |I | x¸c suÊt ®Ó x(k) lµ ph−¬ng ¸n
b»ng 1, l¹i v× thuËt to¸n dõng ë b−íc 4, nªn k kh«ng thÓ v−ît qu¸ gi¸ trÞ nµy). §iÒu
®ã chøng tá thuËt to¸n lµ h÷u h¹n.
+ Nhê ph−¬ng ph¸p quy ho¹ch ®éng (***) cã thÓ gi¶i c¸c bµi to¸n (RKP (I , β )) vµ
nhê §Þnh lý 2.3.5 ta ®−îc ph−¬ng ¸n tèi −u cña bµi to¸n (4)-(6).
+ §Ó tÝnh cËn d−íi U t¹i b−íc 4, chóng ta cã thÓ tham kh¶o c¸c vÝ dô vÒ cËn x¸c
suÊt trong [4]. ChÊt l−îng cña cËn sÏ cã ¶nh h−ëng trùc tiÕp lªn sè lÇn lÆp cña thuËt
to¸n.
VÝ dô. Nhµ ®Çu t− tµi chÝnh cã 82 ®¬n vÞ vèn, cã thÓ ®Çu t− vµo 9 C«ng ty, víi
møc l i suÊt t¹i C«ng ty i lµ ci = 10 − i, i = 1, ..., 9. Biªn ®é giao ®éng vÒ gi¸ ®Çu t− ë
c¸c C«ng ty nh− nhau víi møc tèi thiÓu lµ w = 8, tèi ®a lµ w = 12 ®¬n vÞ vèn. Khi ®ã
ta cã m« h×nh to¸n häc
9
(10 − i)xi
max f =
i=1
víi ®iÒu kiÖn
9
wi xi 82,
i=1
x ∈ {0; 1}9 ,
trong ®ã tÊt c¶ gi¸ ®Çu t− wi = w ph©n bè ®Òu trªn ®o¹n [8, 12] vµ δ = wi − wi = 4. Gi¶
sö lÊy ε = 0, 1, tøc lµ chóng ta cÇn t×m x cña bµi to¸n ®Çu t− víi x¸c suÊt tèi thiÓu lµ
0, 9.
Chó ý r»ng theo gi¶ thiÕt x¸c suÊt ® nªu, x¸c suÊt P b ®−îc biÕt theo
i∈I wi
sù ph©n tÝch ®èi víi tÊt c¶ c¸c tËp con I ⊆ I . Sau ®©y, ta ký hiÖu e = (e(i) ) lµ vect¬
(i)
j
(i) (i)
0-1, víi ei = 1 vµ ej = 0, i = j . Ta sö dông §Þnh lý 2.1, t−¬ng øng víi c¸c gi¸ trÞ cña
k , lÇn l−ît thùc hiÖn thuËt to¸n:
(0) 9
• k = 0: Chóng ta cã β = 0, i∈I xi = [b/w] = [82/8] = 10, vµ do vËy x(0) = i=1 e(i) .
9
TiÕp tôc, tÝnh cËn d−íi (xem [4]) P 82 ≥ U = 0 < 0, 9 (thÓ hiÖn t×nh huèng
i=1 wi
cã thÓ cña w = wi , v× i∈I x(0) = [b/w] = [82/8] = 10 nªn mäi xi = 1, t−¬ng øng víi kh¶
i
n¨ng lín nhÊt wi = 1 th× bÊt ®¼ng thøc nªu trªn kh«ng thÓ xÈy ra - x¸c suÊt b»ng 0).
G¸n k := β + 1 = 0 + 1 = 1, tiÕp tôc víi k = 1.
(1) 9
= [(82 − 4)/8] = 9, vµ do vËy x(1) = ( i)
• k = 1: i=2 e . Chóng ta cã β =
i∈I xi
9
min{|I |; (b − i∈I wi xi )/δ } = [(82 − 9 ∗ 8)/4] = 2, tÝnh cËn d−íi P 82 ≥ U =
i=2 wi
0, 001 < 0, 9. G¸n k := β + 1 = 2 + 1 = 3, tiÕp tôc víi k = 3.
- (3) 9
= [(82 − 12)/8] = 8, vµ do vËy x(3) = (i)
• k = 3: i=3 e . Chóng ta cã β =
xi
i∈ I
9
[(82 − 8 ∗ 8)/4] = 4, tÝnh cËn d−íi P 82 ≥ U = 0, 5 < 0, 9.
wi
i=3
(5) 9
= [(82 − 20)/8] = 7, vµ do vËy x(5) = (i)
• k = 5: i=4 e . TÝnh ®−îc cËn d−íi
i∈ I x i
9
82 ≥ U = 0, 99... > 0, 9. Dõng l¹i. Tr¶ lêi x(5) lµ ph−¬ng ¸n cña (RKP (I, β )),
P wi
i=4
do vËy nã lµ ph−¬ng ¸n tèi −u cña (SKP ).
Tõ ®ã, ®Ó t×m x(5) = (x(5) ) ta gi¶i bµi to¸n
i
9 9
(5) (5)
= 7; x ∈ {0; 1}9 }.
max{f = (10 − i)xi : xi
i=1 i=1
DÔ dµng ta nhËn ®−îc ph−¬ng ¸n tèi −u lµ
x∗ = (1, 1, 1, 1, 1, 1, 1, 0, 0),
max f = 9 + 8 + 7 + 6 + 5 + 4 + 3 = 24.
T i liÖu tham kh¶o
[1] NguyÔn ThÞ Mïi, Kinh doanh chøng kho¸n, NXB Tµi chÝnh, 2007.
[2] TrÇn Xu©n Sinh, Lý thuyÕt tèi −u, Bµi gi¶ng dïng cho Cao häc, Chuyªn ngµnh
C«ng nghÖ th«ng tin, Tr−êng §¹i häc Vinh, 2007.
[3] NguyÔn Duy TiÕn - Vò ViÕt Yªn, Lý thuyÕt x¸c suÊt, NXB Gi¸o dôc, Hµ Néi, 2001.
[4] D. Bertsimas and M. Sim,The Price of Robustness, Oper. Res., Vol.52, No 1(2004),
35-53.
[5] O. Klopfenstein and D. Nace, A Robust Approach to the Chance-constrained Knap-
sack Problem, 60205 CompiÌgne Cedex, France, 2006.
Summary
A class problem of financial investment
In this paper, we introduced a model for problems of financial investment, the
way of its solving reduced to the knapsack problem with stochastic constrain. Then
we give an algorithm to find an optimal plan.
(a) Khoa To¸n, Tr−êng §¹i häc Vinh
(b) Khoa To¸n, Tr−êng §¹i häc §ång Th¸p.
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
