0
Trêng ®¹i häc vinh
Khoa To¸n
nguyÔn thÞ chung
Bµi to¸n quy ho¹ch
ngÉu nhiªn 2 giai ®o¹n
Kho¸ luËn tèt nghiÖp ®¹i häc
Ngµnh cö nh©n khoa häc to¸n
Chuyªn ngµnh : To¸n øng dông
C¸n bé híng dÉn : PGS.TS. TrÇn Xu©n Sinh
Sinh viªn thùc hiÖn : NguyÔn ThÞ Chung
Líp : 43E2 - To¸n
Vinh, 5/2007
Lêi nãi ®Çu
Quy ho¹ch to¸n häc lµ mét bé m«n quan trong ®ang ®îc nhiÒu nhµ nghiªn
cøu quan t©m. Nã cã nhiÒu øng dông trong thùc tÕ, nhÊt lµ trong lao ®éng vµ s¶n
xuÊt. §©y lµ mét chuyªn ngµnh ®ang ®îc gi¶ng d¹y, häc tËp ë c¸c trêng §¹i häc
vµ Sau §¹i häc. §©y còng lµ nh÷ng vÊn ®Ò kh«ng cßn l¹ vÒ tªn gäi, nhng sè ngêi
®i s©u nghiªn cøu nã ngµy cµng nhiÒu, cã rÊt nhiÒu c«ng tr×nh díi d¹ng s¸ch vµ
bµi viÕt ®¨ng trªn c¸c T¹p chÝ khoa häc. Mét trong nh÷ng néi dung cña Quy
ho¹ch to¸n häc, ®îc øng dông nhiÒu trong thùc tiÔn, ®ã lµ c¸c bµi to¸n quy
ho¹ch víi th«ng tin kh«ng ®Çy ®ñ, phô thuéc vµo c¸c yÕu tè ngÉu nhiªn - bµi
to¸n quy ho¹ch ngÉu nhiªn. V× thêi gian vµ kh¶ n¨ng cã h¹n, nªn chóng t«i chän
®Ò tµi nghiªn cøu “Bµi to¸n quy ho¹ch ngÉu nhiªn hai giai ®o¹n”.
1
Môc ®Ých cña ®Ò tµi lµ nªu ra mét sè bµi to¸n quy ho¹ch tuyÕn tÝnh ngÉu
nhiªn, ®Æc biÖt lµ bµi to¸n quy ho¹ch tuyÕn tÝnh ngÉu nhiªn hai giai ®o¹n vµ mét
sè ph¬ng ph¸p gi¶i chóng.
Kho¸ luËn ®îc chia lµm 2 ch¬ng.
Ch¬ng 1, tr×nh bµy nh÷ng kiÕn thøc c¬ së cÇn thiÕt cã liªn quan trong c¸ch
tr×nh bµy néi dung cña kho¸ luËn.
Ch¬ng 2, tr×nh bµy néi dung vµ mét sè vÊn ®Ò cña lý thuyÕt quy ho¹ch ngÉu
nhiªn hai giai ®o¹n.
Kho¸ luËn ®îc thùc hiÖn vµ hoµn thµnh t¹i trêng §¹i häc Vinh. §Ó hoµn
thµnh ®îc kho¸ luËn nµy, t¸c gi¶ ®· nhËn ®îc sù híng dÉn nhiÖt t×nh, chu ®¸o
cña thÇy gi¸o, PGS.TS. TrÇn Xu©n Sinh vµ nh÷ng ý kiÕn ®ãng gãp cña c¸c thÇy,
c« gi¸o thuéc Khoa To¸n. T¸c gi¶ xin bµy tá lßng biÕt ¬n ch©n thµnh ®Õn thÇy
gi¸o híng dÉn vµ c¸c thÇy gi¸o trong Khoa To¸n.
T¸c gi¶ xin tr©n träng c¶m ¬n tíi thÇy gi¸o PGS.TS. TrÇn Xu©n Sinh vµ c¸c
thÇy, c« gi¸o cïng b¹n bÌ, gia ®×nh ®· gióp ®ì nhiÒu trong qu¸ tr×nh häc tËp, lµm
viÖc cña t¸c gi¶.
T¸c gi¶
Ch¬ng 1
C¸c kiÕn thøc c¬ së
1.1. Lý thuyÕt quy ho¹ch
1.1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh vµ ph¬ng ph¸p ®¬n h×nh
Quy ho¹ch tuyÕn tÝnh ®îc h×nh thµnh vµo nh÷ng n¨m gi÷a thÕ kû 20. Ngay
sau ®ã, nã ®îc ph¸t triÓn rÊt nhanh nhê sù ph¸t hiÖn ra nhiÒu bµi to¸n øng dông,
cã thÓ kh¸c nhau vÒ h×nh thøc, ®îc ®a vÒ bµi to¸n quy ho¹ch tuyÕn tÝnh.
Dantzig ®îc coi lµ cha ®Î cña ph¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n quy ho¹ch
tuyÕn tÝnh. Lý thuyÕt vÒ c¸c bÊt ®¼ng thøc tuyÕn tÝnh, ®· ®îc nghiªn cøu bëi
Fourier tõ 1826, lµ chç dùa ®Ó Dantzig ph¸t hiÖn ra ph¬ng ph¸p ®¬n h×nh.
Tõ khi ra ®êi, ph¬ng ph¸p ®¬n h×nh ®· gÇn nh thèng trÞ thêi gian dµi nh»m
gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh. Dùa trªn nhËn xÐt r»ng miÒn chÊp nhËn (ph¬ng ¸n) cña bµi to¸n quy ho¹ch tuyÕn tÝnh lµ tËp låi ®a diÖn vµ nÕu bµi to¸n ®·
cho cã ph¬ng tèi u th× tån t¹i ®Ønh cña tËp låi nµy tèi u, néi dung cña ph¬ng
ph¸p ®¬n h×nh lµ xuÊt ph¸t tõ mét ®Ønh cña tËp ph¬ng ¸n, cè g¾ng ®i tíi mét
®Ønh kÒ tèt h¬n (gi¸ trÞ hµm môc tiªu gÇn tíi gi¸ trÞ tèi u h¬n). V× sè ®Ønh lµ h÷u
h¹n nªn nãi chung, víi mét gi¶ thiÕt vÒ lý thuyÕt nhÊt ®Þnh, qu¸ tr×nh sÏ kÕt thóc
sau h÷u h¹n bíc lÆp. Ph¬ng ph¸p nµy tËn dông triÖt ®Ó cÊu tróc tuyÕn tÝnh cña
bµi to¸n, kh¸c h¼n víi tèi u phi tuyÕn.
GÇn mét thÕ kû nghiªn cøu vµ øng dông, mÆc dï ®· cã nhiÒu ph¬ng ph¸p
kh¸c nhau gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh, ngêi ta vÉn thÊy r»ng ph¬ng ph¸p
2
®¬n h×nh vÉn lµ ph¬ng ph¸p cã hiÖu qu¶ nhÊt trong viÖc t×m lêi gi¶i cña c¸c bµi
to¸n kinh tÕ (xem [2], [5], [9]).
1.1.1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh
D¹ng tæng qu¸t cña bµi to¸n quy ho¹ch lµ:
T×m vect¬ X = (x1, x2, ..., xn) ℝn, lµm cùc tiÓu (hoÆc cùc ®¹i) hµm sè f(X),
víi c¸c ®iÒu kiÖn gi(X) 0, i = 1, 2,..., m; xj 0, j = 1, 2, ..., k, k n.
§iÒu ®ã ®ßi hái ta cÇn gi¶i bµi to¸n
min (max) f(X)
víi ®iÒu kiÖn
(1.1)
gi(X) 0, i = 1, 2,..., m
(1.2)
xj 0, j = 1, 2,..., k , k n,
(1.3)
trong ®ã hµm f : ℝn ℝ, gi : ℝm ℝ, i = 1, 2, ..., m.
Hµm f(X) gäi lµ hµm môc tiªu, c¸c ®iÒu kiÖn (1.2)(1.3) gäi lµ ®iÒu kiÖn buéc
cña bµi to¸n.
Mçi vect¬ X = (xj) ℝn tho¶ m·n hÖ ®iÒu kiÖn buéc gäi lµ mét ph¬ng ¸n.
Ta ký hiÖu tËp ph¬ng ¸n lµ M.
Mét ph¬ng ¸n lµm cùc tiÓu (hoÆc cùc ®¹i) hµm môc tiªu gäi lµ ph¬ng ¸n tèi
u (hoÆc gäi lµ nghiÖm) cña bµi to¸n.
Cã thÓ thÊy r»ng hai bµi to¸n sau ®©y lµ t¬ng ®¬ng
min f(X)
vµ max g(X) = - f(X)
XM
X M.
Tuú theo hµm f(X) hoÆc tËp M mµ ngêi ta chia bµi to¸n (1.1)(1.2)(1.3) thuéc
c¸c líp bµi to¸n kh¸c nhau.
§Æc biÖt, khi f(X) vµ gi(X) (i = 1, 2,..., m) lµ c¸c hµm tuyÕn tÝnh, M ℝn th×
bµi to¸n ®· cho ®îc gäi lµ bµi to¸n quy ho¹ch tuyÕn tÝnh.
Nh vËy, bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t cã d¹ng
n
min f(X) = cjxj
j 1
víi ®iÒu kiÖn
n
aijxj = bi , i = 1, 2, ..., k
j 1
n
aijxj bi , i = k+1, ..., m
j 1
xj 0, j = 1, 2, ..., r; r n.
3
Tõ bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng tæng qu¸t nh ®· nªu trªn, ta cã thÓ
chuyÓn vÒ d¹ng t¬ng ®¬ng (theo nghÜa kh«ng lµm thay ®æi gi¸ trÞ tèi u cña hµm
môc tiªu) nh sau:
n
min f(X) = cjxj
j 1
víi ®iÒu kiÖn
n
(1.4)
aijxj = bi , i = 1, 2, ..., m
(1.5)
xj 0, j = 1, 2, ..., n.
(1.6)
j 1
th× bµi to¸n (1.4)(1.5)(1.6) ®îc gäi lµ bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c.
V× vËy, vÒ mÆt tÝnh to¸n, ngêi ta xÐt bµi to¸n quy ho¹ch tuyÕn tÝnh ë d¹ng
chÝnh t¾c.
Bµi to¸n (1.4)(1.5)(1.6) cã thÓ viÕt l¹i nh sau:
a) C¸ch viÕt theo ma trËn
Ký hiÖu ma trËn hµng C = (c1 c2 ... cn) cÊp 1 n
C¸c ma trËn cét X = (x1 x2 ... xn)T cÊp n1, B = (b1 b2 ... bm)T cÊp m1 vµ ma
trËn A = (aij) cÊp mn; T lµ ký hiÖu cho phÐp chuyÓn vÞ cña ma trËn.
Khi ®ã ta cã bµi to¸n
min CX
AX = B
víi ®iÒu kiÖn
X 0.
b) C¸ch viÕt theo vect¬: Ký hiÖu c¸c vect¬
C = (c1, c2, ..., cn) ℝn, X = (x1, x2, ..., xn) ℝn,
A0 = (b1, b2, ..., bm) ℝm, Aj = (a1j, a2j, ..., amj) ℝm, j = 1, , ...,
n.
Khi ®ã ta cã bµi to¸n
min C, X
4
víi ®iÒu kiÖn
x1A1 + x2A2 + ... + xnAn = A0
x1, x2, ...., xn 0.
1.1.1.2. TÝnh chÊt cña bµi to¸n quy ho¹ch tuyÕn tÝnh
Ký hiÖu M lµ tËp ph¬ng ¸n cña bµi to¸n (1.4)(1.5)(1.6).
Bµi to¸n quy ho¹ch tuyÕn tÝnh cã c¸c tÝnh chÊt quan träng sau ®©y (xem [5]):
1) TËp ph¬ng ¸n M lµ mét tËp låi ®a diÖn.
2) NÕu tËp ph¬ng ¸n cña bµi to¸n quy ho¹ch tuyÕn tÝnh lµ ®a diÖn låi th× tån
t¹i ph¬ng ¸n cùc biªn tèi u.
3) NÕu bµi to¸n quy ho¹ch tuyÕn tÝnh cã ph¬ng ¸n tèi u, th× cã Ýt nhÊt mét
ph¬ng ¸n cùc biªn tèi u.
Tõ tÝnh chÊt 2 vµ 3 cho phÐp ta t×m ph¬ng ¸n tèi u cña bµi to¸n quy ho¹ch
tuyÕn tÝnh chØ cÇn t×m trªn tËp c¸c ph¬ng ¸n cùc biªn. Sau nµy chóng ta sÏ thÊy
thªm r»ng sè ph¬ng ¸n cùc biªn lµ h÷u h¹n.
4) Ph¬ng ¸n X = (xj) lµ cùc biªn khi vµ chØ khi øng víi c¸c chØ sè j mµ x j > 0
lµ hÖ vect¬ cét Aj ®éc lËp tuyÕn tÝnh (tøc lµ ®Þnh thøc c¸c to¹ ®é cña c¸c
vect¬ Aj t¬ng øng kh¸c 0).
HÖ qu¶
a) Sè to¹ ®é d¬ng cña ph¬ng ¸n cùc biªn cã tèi ®a lµ m.
b) Sè ph¬ng ¸n cùc biªn cña M lµ h÷u h¹n (nhiÒu l¾m lµ Cnm).
c) X M lµ ph¬ng ¸n cùc biªn khi vµ chØ khi X tho¶ m·n chÆt n rµng buéc.
Chó ý r»ng hÖ qu¶ c) cßn ®óng c¶ trong trêng hîp bµi to¸n quy ho¹ch tuyÕn
tÝnh d¹ng tæng qu¸t.
§Þnh nghÜa. Ph¬ng ¸n cùc biªn cã ®ñ m to¹ ®é d¬ng ®îc gäi lµ ph¬ng ¸n
cùc biªn kh«ng suy biÕn (hay kh«ng tho¸i ho¸).
Bµi to¸n quy ho¹ch tuyÕn tÝnh cã tÊt c¶ c¸c ph¬ng ¸n cùc biªn kh«ng suy
biÕn ®îc gäi lµ bµi to¸n kh«ng suy biÕn.
HÖ m vect¬ Aj ®éc lËp tuyÕn tÝnh t¬ng øng víi ph¬ng ¸n cùc biªn X nh ®·
nªu trong tÝnh chÊt 4 gäi lµ c¬ së liªn kÕt cña X.
5) NÕu bµi to¸n quy ho¹ch tuyÕn tÝnh cã hai ph¬ng ¸n tèi u kh¸c nhau th× cã
v« sè ph¬ng ¸n tèi u.
6) NÕu hµm môc tiªu f cña bµi to¸n (1.4)(1.5)(1.6), bÞ chÆn díi (bÞ chÆn trªn
nÕu bµi to¸n maxf) trªn tËp ph¬ng ¸n kh¸c rçng th× bµi to¸n quy ho¹ch tuyÕn
tÝnh tån t¹i ph¬ng ¸n tèi u.
§Þnh nghÜa. Cho bµi to¸n quy ho¹ch tuyÕn tÝnh
n
min f(X) = cjxj
j 1
víi ®iÒu kiÖn
n
aijxj bi , i = 1, 2, ..., m1
j 1
(1.7)
(1.8)
5
n
aijxj bi , i = m1+1, ..., m2
(1.9)
j 1
n
aijxj = bi , i = m1+1, ..., m
(1.10)
j 1
xj 0, j = 1, 2, ..., n1
xj 0, j = n1+1, ..., n2
xj tù do, j = n2+1, ..., n.
(1.11)
(1.12)
(1.13)
Bµi to¸n ®· cho ®îc gäi lµ bµi to¸n gèc. §Ó cã bµi to¸n ®èi ngÉu ta thùc hiÖn
theo quy t¾c sau:
+ NÕu bµi to¸n gèc lµ minf(X) th× bµi to¸n ®èi ngÉu lµ maxf(X) vµ ngîc l¹i.
+ øng víi bµi to¸n gèc cã ®iÒu kiÖn
n
j 1
aijxj bi , i = 1, 2, ..., m1 th× t¬ng
øng bµi to¸n ®èi ngÉu cã ®iÒu kiÖn yi 0, i = 1, 2, ..., m1.
+ øng víi bµi to¸n gèc cã ®iÒu kiÖn xj 0, j = 1, 2,..., n1 th× t¬ng øng bµi
to¸n ®èi ngÉu cã ®iÒu kiÖn
m
i 1
aijyi cj, j = 1, 2, ..., n1.
+ øng víi bµi to¸n gèc cã ®iÒu kiÖn
n
j 1
aijxj bi , i = m1+1, ..., m2 th× t-
¬ng øng bµi to¸n ®èi ngÉu cã ®iÒu kiÖn yi 0, i = i = m1+1, ..., m2.
+ øng víi bµi to¸n gèc cã ®iÒu kiÖn xj 0, j = n1+1, ..., n2 th× t¬ng øng bµi
to¸n ®èi ngÉu cã ®iÒu kiÖn
m
i 1
aijyi cj, j = j = n1+1, ..., n2.
+ øng víi bµi to¸n gèc cã ®iÒu kiÖn
n
j 1
aijxj = bi , i = m2+1, ..., m th× t¬ng
øng bµi to¸n ®èi ngÉu cã biÕn yi tù do, i = m2+1, ..., m.
+ øng víi bµi to¸n gèc cã biÕn xj tù do, j = n2+1, ..., n th× t¬ng øng bµi to¸n
®èi ngÉu cã ®iÒu kiÖn
m
i 1
aijyi = cj, j = n2+1, ..., n.
Kh¸i niÖm bµi to¸n gèc vµ bµi to¸n ®èi ngÉu chØ lµ kh¸i niÖm t¬ng ®èi, nghÜa
lµ nÕu bµi to¸n nµy lµ gèc th× bµi to¸n kia lµ ®èi ngÉu vµ ngîc l¹i.
7) (§Þnh lý lÖch bï). Cho c¸c ph¬ng ¸n X*, Y* øng víi cÆp bµi to¸n ®ãi
ngÉu. Khi ®ã X*, Y* lµ tèi u khi vµ chØ khi t¬ng øng c¸c cÆp ®iÒu kiÖn ®èi ngÉu,
nÕu ®iÒu kiÖn nµy cã dÊu b»ng (=) th× ®iÒu kiÖn kia cã dÊu bÊt ®¼ng thøc (>
hoÆc <).
Ký hiÖu Ai (i I) lµ mét c¬ së cña cña hÖ vect¬ cét Aj trong ma trËn A cña
bµi to¸n quy ho¹ch tuyÕn tÝnh; xij lµ to¹ ®é thø i cña vect¬ Aj øng víi c¬ së Ai;
j = iI cixij - cj, j = 1, 2, ..., n.
6
8) (DÊu hiÖu tèi u) NÕu t¹i ph¬ng ¸n cùc biªn X0, cã j 0, j = 1, 2, ..., n,
th× X0 tèi u.
9) NÕu t¹i ph¬ng ¸n cùc biªn X0 , tån t¹i k > 0 vµ mäi xik 0 (i = 1, ..., m) th×
bµi to¸n kh«ng cã ph¬ng ¸n tèi u (hµm môc tiªu kh«ng bÞ chÆn trªn tËp ph¬ng
¸n).
10) NÕu t¹i ph¬ng ¸n cùc biªn X0, tån t¹i k > 0 vµ tån t¹i xik > 0 th× x©y dùng
®îc ph¬ng ¸n cùc biªn míi X1 tèt h¬n X0.
§Þnh nghÜa . Cho X M tËp c¸c ph¬ng ¸n, híng Z Rn ®îc gäi lµ chÊp
nhËn ®îc t¹i X nÕu tån t¹i sè thùc 0 > 0, sao cho
X + Z M, [0, 0].
Cho X M, híng Z chÊp nhËn ®îc t¹i X ®îc gäi lµ híng gi¶m tõ X nÕu f(X +
Z) < f(X).
Khi kh«ng xÈy ra j 0, tøc lµ tån t¹i k > 0, th× Xo cha kh¼ng ®Þnh ®îc
tèi u. Ta h·y ®i t×m híng gi¶m tõ Xo.
Ký hiÖu
Zk = (- Xk , 0, ..., 1, ..., 0) = (- x1k, ..., - xmk, 0, ..., 1, ..., 0)
trong ®ã sè 1 ë to¹ ®é thø k.
11) Víi mçi k mµ Ak kh«ng ph¶i lµ vect¬ c¬ së cña X0 th× vect¬ Zk lµ híng chÊp
nhËn ®îc t¹i X0 khi vµ chØ khi XB* - Xk 0 víi nµo ®ã, trong ®ã XB* = (xi)i I.
12) Víi ®iÒu kiÖn cña tÝnh chÊt 11, Zk lµ híng gi¶m tõ Xo khi vµ chØ khi k > 0.
NhËn xÐt: Tõ tÝnh chÊt 8, 9, 10, 11, 12, ta cã thuËt to¸n ®¬n h×nh nh sau:
1.1.1.3. ThuËt to¸n ®¬n h×nh
Bíc 0: (LËp b¶ng xuÊt ph¸t) Chän c¬ së AiiI vµ ph¬ng ¸n cùc biªn xuÊt
ph¸t X0; x¸c ®Þnh xi, xij, f(X0) vµ j .
Bíc 1: KiÓm tra tiªu chuÈn tèi u: j 0 ?, j = 1,…, n.
- NÕu cã, chuyÓn sang bíc 6.
- NÕu kh«ng, chuyÓn sang bíc 2.
Bíc 2. KiÓm tra kh¶ n¨ng v« nghiÖm: Tån t¹i j > 0 mµ xij 0 ?
- NÕu cã, chuyÓn sang bíc 6.
- NÕu kh«ng, chuyÓn sang bíc 3.
Bíc 3. Chän vect¬ vµo c¬ së: Chän k =
max
j 0
j, ®a Ak vµo c¬ së.
o
xio
x
Bíc 4. Chän vect¬ ra khái c¬ së: T×m 0 = min
=
, A ra khái c¬ së.
xik 0 x
x
ik
k
7
Bíc 5. X©y dùng p.a.c.b míi: X©y dùng ph¬ng ¸n cùc biªn míi X1.
G¸n X0 := X1 råi trë l¹i bíc 1.
Bíc 6. Dõng l¹i vµ tr¶ lêi cã hay kh«ng cã ph¬ng ¸n tèi u.
13) NÕu bµi to¸n quy ho¹ch tuyÕn tÝnh kh«ng suy biÕn th× thuËt to¸n ®¬n
h×nh kÕt thóc sau h÷u h¹n bíc lÆp.
Trong trêng hîp bµi to¸n suy biÕn th× thêng lµ cã nhiÒu vect¬ ®îc lùa chän
ra khái c¬ së. Trong trêng hîp nµy ngêi ta thêng chän vect¬ ra khái c¬ së mét
c¸ch ngÉu nhiªn trong c¸c vect¬ ®ång kh¶ n¨ng, ch¼ng h¹n c¸c vect¬ A vµ Ar.
Quy t¾c lùa chän ngÉu nhiªn nh vËy gäi lµ quy t¾c ngÉu nhiªn.
14) Dïng quy t¾c ngÉu nhiªn th× thuËt to¸n ®¬n h×nh kÕt thóc sau k bíc lÆp
víi x¸c suÊt
k
1
p1- ,
m
trong ®ã m lµ sè ph¬ng tr×nh ®éc lËp cña hÖ ®iÒu kiÖn buéc. Do ®ã x¸c suÊt kÕt
thóc thuËt to¸n sau k bíc lÆp dÇn tíi 1 khi k .
1.1.2. Quy ho¹ch låi vµ c¸c ph¬ng ph¸p gi¶i
1.1.2.1. Bµi to¸n quy ho¹ch låi. Cho bµi to¸n
min f(X)
víi ®iÒu kiÖn
XD
g1(X) 0, g2(X) 0, ..., gm(X) 0,
(1.14)
(1.15)
(1.16)
trong ®ã D lµ tËp hîp låi thuéc ℝn vµ f(X), g1(X), g2(X), ..., gm(X) lµ c¸c hµm låi.
Bµi to¸n (1.14)(1.15)(1.16) gäi lµ bµi to¸n quy ho¹ch låi.
§iÓm X D tho¶ m·n c¸c ®iÒu kiÖn (1.15), (1.16) ®îc gäi lµ ph¬ng ¸n (hay
lµ ®iÓm chÊp nhËn) cña bµi to¸n, ký hiÖu tËp ph¬ng ¸n lµ M. Ph¬ng ¸n X* tho¶
m·n f(X*) = min f(X), X M ®îc gäi lµ ph¬ng ¸n tèi u (hay lêi gi¶i hay
nghiÖm) cña bµi to¸n. Ta thÊy râ M lµ tËp låi.
§Þnh nghÜa. Ta nãi bµi to¸n (1.14)(1.15)(1.16) tho¶ m·n ®iÒu kiÖn chÝnh
quy nÕu cã Ýt nhÊt mét ®iÓm X0 D nghiÖm ®óng
g1(X0) < 0, ..., gm(X0) < 0.
(1.17)
Lóc nµy ta còng nãi tËp ph¬ng ¸n M tháa m·n ®iÒu kiÖn chÝnh quy.
1.1.2.2. TÝnh chÊt cña bµi to¸n quy ho¹ch låi
1) Trong mçi tËp låi ®ãng D M, nÕu f(X) cã cùc tiÓu vµ nÕu D cã ®Ønh th×
cùc tiÓu Êy ph¶i ®¹t ®îc t¹i Ýt nhÊt mét ®Ønh cña D.
Cho hµm f x¸c ®Þnh trªn tËp hîp låi M. §iÓm X0 M ®îc gäi lµ ®iÓm cùc
tiÓu ®Þa ph¬ng cña f trªn M nÕu tån t¹i l©n cËn Xo sao cho
8
f(X0) f(X), X M Xo.
NÕu M Xo M th× ta nãi X0 lµ ®iÓm cùc tiÓu tuyÖt ®èi (hay cùc tiÓu toµn
côc) cña f trªn M.
2) Mäi ®iÓm cùc tiÓu ®Þa ph¬ng cña hµm f(X) trong mét tËp låi ®ãng bÊt kú
D M ph¶i lµ ®iÓm cùc tiÓu trong toµn bé D.
§iÓm X0 M låi, ®îc gäi lµ ®iÓm trong cña M nÕu víi mçi X M th× tån t¹i
Y M mµ X0 = X + (1-)Y, 0 < < 1.
3) NÕu hµm låi f ®¹t cùc ®¹i t¹i ®iÓm trong X0 cña tËp låi M th× f kh«ng ®æi
trªn tËp M.
§Þnh nghÜa. Cho hµm låi f(X) x¸c ®Þnh trªn tËp låi M vµ híng S Rn, (S = 1).
Ta nãi f(X) cã ®¹o hµm theo híng S nÕu giíi h¹n sau ®©y tån t¹i h÷u h¹n.
lim
f ( X S ) f ( X )
0
vµ ta ký hiÖu
f (X, S) =
lim
0
f ( X S ) f ( X )
.
Ngêi ta ®· chøng minh ®îc r»ng: Hµm låi f(X) x¸c ®Þnh trªn tËp låi M, cã
t¹i mäi ®iÓm trong X M ®¹o hµm theo híng S bÊt kú.
Cho hµm f kh¶ vi, x¸c ®Þnh trªn tËp hîp låi M ℝn,
khi ®ã
f (X, S) = f , S.
'
'
'
trong ®ã f = f’(X) = ( f x1 , f x 2 ,..., f x n ).
Ngêi ta còng chøng minh ®îc r»ng híng S chÊp nhËn ®îc tõ X lµ h¬ng gi¶m
®èi víi hµm låi f, khi vµ chØ khi f (X, S) = f, S < 0.
4) Cho hµm låi f, kh¶ vi x¸c ®Þnh trªn tËp hîp låi, M ℝn, ®iÒu kiÖn ®Ó hµm
f ®¹t cùc tiÓu toµn côc t¹i X* M lµ
f(X*), X - X* 0, X M.
5) Cho hµm låi f x¸c ®Þnh trªn tËp hîp låi M ℝn, ®iÒu kiÖn cÇn vµ ®ñ ®Ó
hµm f ®¹t cùc tiÓu toµn côc t¹i X* M lµ f(X*) = 0.
Cho bµi to¸n quy ho¹ch låi (1.14)(1.15)(1.16). Ký hiÖu Y = (yi) ℝm, Y 0.
XÐt hµm
m
L(X, Y) = f(X) + yi fi(X).
i 1
Hµm L(X, Y) nh vËy gäi lµ hµm Lagrange cña bµi to¸n quy ho¹ch låi.
(1.17)
9
§iÓm (X*, Y*), víi X* M vµ Y* = (y*1, y*2, ..., y*m) 0, ®îc gäi lµ ®iÓm
yªn ngùa cña hµm Lagrange nÕu nã tho¶ m·n
L(X*, Y) L(X*, Y*) L(X, Y*), X M, Y = (y1, ..., ym) 0.
(1.18)
6) Hµm låi f ®¹t cùc tiÓu t¹i ®iÓm X* M khi vµ chØ khi tån t¹i ®iÓm Y*
ℝm, Y* 0, sao cho (X*, Y*) lµ ®iÓm yªn ngùa cña hµm Lagrange L(X, Y) (xem
[6]).
TÝnh chÊt 6 thêng gäi lµ ®Þnh lý ®iÓm yªn ngùa, hay cßn gäi lµ ®Þnh lý Kuhn
- Tucker.
Ngêi ta ®· chøng minh r»ng nÕu bµi to¸n quy ho¹ch låi tháa m·n ®iÒu kiÖn
chÝnh quy th× lu«n tån t¹i ®iÓm yªn ngùa.
Chó ý r»ng ®iÒu kiÖn chÝnh quy lµ cÇn thiÕt. NÕu bá ®iÒu kiÖn chÝnh quy th×
hµm Lagrange cã thÓ kh«ng tån t¹i ®iÓm yªn ngùa. Ch¼ng h¹n, trong ℝ, xÐt bµi
to¸n
min f(x) = - x, víi ®iÒu kiÖn: g(x) = x2 0; x 0.
TËp ph¬ng ¸n chØ cã mét ®iÓm x* = 0, kh«ng tháa m·n ®iÒu kiÖn chÝnh quy
vµ x* chÝnh lµ ph¬ng ¸n tèi u. Tuy nhiªn, hµm Lagrange
L(x, y) = - x + yx2
kh«ng cã ®iÓm yªn ngùa.
7) (§Þnh lý Farkas-Minlkowski më réng) Cho f(X), g i(X), (i = 1, 2, ..., k) lµ
nh÷ng hµm låi, x¸c ®Þnh trªn tËp låi D ℝn, hÖ
gi(X) < 0, i = 1, 2, ..., m
XD
cã nghiÖm, ®ång thêi hÖ
gi(X) 0, i = 1, 2, ..., m
f(X) < 0
v« nghiÖm trong M, th× tån t¹i nh÷ng sè thùc i 0, i = 1, 2, ..., m sao cho X
D tho¶ m·n gi(X) 0 th× cã
m
f(X) + i gi(X) 0.
(1.19)
i 1
Chó ý:
m
Tõ tÝnh chÊt 7, nÕu lÊy M = ℝn, gi(X) = - aijxi, f(X) = P, X, víi P, X ℝn,
i 1
Ký hiÖu A = (aij ) khi ®ã ta cã
10
NÕu ®èi víi ma trËn A tuú ý nµo ®ã, t×m ®îc vect¬ P sao cho víi mäi X tho¶
m·n bÊt ®¼ng thøc AX 0, cã ®îc P, X 0, th× khi ®ã ta t×m ®îc vect¬ U 0 mµ
P = ATU, (trong ®ã AT lµ ma trËn chuyÓn vÞ cña A).
§ã lµ néi dung cña Bæ ®Ò Farkas.
1.1.3. ThuËt to¸n gi¶i bµi to¸n quy ho¹ch låi
§Ó gi¶i bµi to¸n quy ho¹ch låi, ®· cã nhiÒu ph¬ng ph¸p chÝnh x¸c. Sau ®©y
chóng ta sÏ tr×nh bµy 2 ph¬ng ph¸p, víi gi¶ thiÕt ban ®Çu lµ:
1) D lµ tËp låi ®a diÖn, c¸c hµm gi(X) lµ tuyÕn tÝnh, ®iÒu ®ã cho thÊy r»ng M
lµ tËp låi ®a diÖn.
2) Hµm f(X) låi, kh¶ vi liªn tôc trªn M.
3) f (X, S) = f , S bÞ chÆn díi trªn M víi mäi X M vµ mäi híng S chÊp
nhËn ®îc.
T tëng cña ph¬ng ph¸p lµ: XuÊt ph¸t tõ ph¬ng ¸n X0 bÊt kú, x©y dùng d·y
c¸c ph¬ng ¸n tèt dÇn X0, X1, ..., Xk, sao cho f(X) gi¶m dÇn tíi gi¸ trÞ giíi h¹n
f(X*) = min f(X), X M.
Trªn c¬ së tÝnh chÊt 4, gi¶ sö ®· biÕt ph¬ng ¸n Xk. Khi ®ã nÕu
f(Xk) , X - Xk 0, X M
th× Xk tèi u.
Ngîc l¹i, nÕu cã X mµ f(Xk) , X - Xk < 0, ta ®i x©y dùng ph¬ng ¸n míi Xk+1
theo mét híng tôt x¸c ®Þnh ®Ó cã f(Xk+1) f(Xk).
1.1.3.1. ThuËt to¸n Frank-Wolfe
Bíc 0. Chän X bÊt kú thuéc M.
Bíc k (k = 1, 2, ...).
Gi¶ sö ®· biÕt ph¬ng ¸n Xk, ta gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh
min f(Xk), X - Xk, X M,
hay lµ bµi to¸n t¬ng ®¬ng
min f(Xk), X, X M.
(*)
~
Víi c¸c gi¶ thiÕt ®· nªu, bµi to¸n (*) cã ph¬ng ¸n tèi u X k .
Cã hai kh¶ n¨ng xÈy ra:
~
a) NÕu f(Xk) , X k - Xk 0, tøc lµ
~
f(Xk), X - Xk f(Xk), X k - Xk 0, X M,
ta ®îc Xk lµ ph¬ng ¸n tèi u cÇn t×m. KÕt thóc thuËt to¸n.
~
~
b) f(Xk), X k - Xk < 0, chøng tá f(X) gi¶m theo híng S = X k - Xk, nghÜa lµ
~
f(x) gi¶m trªn ®o¹n [Xk, X k ]. Ta ®i gi¶i bµi to¸n cùc tiÓu hµm mét biÕn sau ®©y
~
g(k) = min g() = f(Xk + ( X k - Xk)), [0, 1].
11
Chó ý r»ng g() lµ hµm låi x¸c ®Þnh trªn ®o¹n [0, 1]. Do vËy, ta chØ cÇn gi¶i
ph¬ng tr×nh
~
g'() = [f(Xk + ( X k - Xk))]' = 0.
§Æt
~
Xk+1 = Xk + k( X k - Xk).
Râ rµng
f(Xk+1) f(Xk).
G¸n Xk := Xk+1, råi trë l¹i bíc k.
1.1.3.2. (§Þnh lý vÒ tÝnh hiÖu qu¶ cña thuËt to¸n) Víi c¸c gi¶ thiÕt ®· nªu vµ
M compact, khi ®ã ta cã
a) f(Xk) gi¶m dÇn ®Õn = minf(X), X M.
~
b) 0 f(Xk) - f(Xk) , Xk - X k .
Chøng minh
a) Gäi I lµ tËp c¸c ®Ønh cña M cã mÆt trong d·y X(k). Khi ®ã, d·y X(0),
X(1), ..., X(k), ... n»m trong bao låi cña X(0) I. TËp X(0) I gåm h÷u h¹n ®iÓm
nªn nã lµ tËp compact. Do vËy d·y X(k) cã mét ®iÓm tô X* vµ tèt dÇn, nghÜa lµ
f(X(0)) > f(X(1)) > ... > f(X(k)) > ...., ngoµi ra f(X) lµ hµm liªn tôc, nªn
lim f(X(k)) = f(X*) = .
k
b) §Æt X = X(k) + (X - X(k)), ta cã
X M, f(X) - f(X(k)) = f(X + (X(k) - X)) - f(X(k))
~
f(X(k)), X - X(k) f(X(k)), X k - X(k).
Do ®ã
~
f(X) - f(X(k)) f(X(k)), X k - X(k) , X M.
Víi X = X* ta ®îc
~
f(X*) - f(X(k)) f(X(k)), X k - X(k).
Hay ®æi dÊu hai vÕ ta cã
~
0 f(X(k)) - f(X(k)), X(k) - X k .
§Þnh lý ®îc chøng minh.
Chó ý r»ng theo ®Þnh lý võa nªu cho thÊy, nÕu thuËt to¸n dõng ë bíc k vµ lÊy
Xk lµm nghiÖm gÇn ®óng cña bµi to¸n th× ®¸nh gi¸ sai sè sÏ lµ
~
f(Xk) - f(Xk) , Xk - X k .
1.1.3.3. ThuËt to¸n Rosen
12
ThuËt to¸n Frank-Wolfe chØ xÐt ®îc víi tËp M c¸c ph¬ng ¸n lµ låi ®a diÖn.
Trong trêng hîp tËp M låi tæng qu¸t th× phøc t¹p h¬n nhiÒu. Ta h·y xÐt bµi to¸n
min f(X)
(1.20)
víi ®iÒu kiÖn
g1(X) 0, g2(X) 0, ..., gm(X) 0,
(1.21)
trong ®ã f(X), gi(X), (i = 1, 2, ..., m) lµ nh÷ng hµm låi.
Tõ bµi to¸n (1.20), (1.21), ta gi¶ thiÕt r»ng
1) Hµm f(X), gi(X) låi, kh¶ vi liªn tôc trªn M.
2) C¸c hµm gi(X) tho¶ m·n ®iÒu kiÖn chÝnh quy, nghÜa lµ tån t¹i ph¬ng ¸n X0
M sao cho gi(X0) < 0, i = 1, 2, ..., m.
3) TËp ph¬ng ¸n M giíi néi.
T tëng chÝnh cña ph¬ng ph¸p còng gièng nh ®· lµm víi ph¬ng ph¸p FrankWolfe. Tuy nhiªn, vÊn ®Ò cã kh¸c lµ chän híng tôt thÕ nµo ®Ó b¶o ®¶m sù héi tô.
ThuËt to¸n Rosen
Bíc 0. XuÊt ph¸t tõ ph¬ng ¸n X0 nµo ®ã vµ vect¬ T x¸c ®Þnh cho tríc.
§Æt P(T) = X : gi(T), X - T gi(T), i = 1, ..., m .
DÔ dµng thÊy r»ng M P(T).
Ta x©y dùng híng chÊp nhËn ®îc nh sau:
Víi T M vµ X P(T), chän > 0, ®Ó híng Z = (X - T) + (X0 - T) lµ chÊp
nhËn ®îc tõ X0.
Bíc k, (k = 1, 2, ...). Gi¶ sö ta ®· cã Xk M.
Gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh phô
(A) min f(Xk), X - Xk : X P(Xk) Q.
trong ®ã Q lµ ®a diÖn låi nµo ®ã chøa M, th«ng thêng ë bíc 0, chän Q lµ mét
siªu hép, Q = x Rn : a x b, a, b lµ c¸c vect¬ h÷u h¹n nµo ®ã.
x
Gi¶ sö (A) cã phíng ¸n tèi u ~k .
~
Ký hiÖu k = f(Xk) , X k - Xk , khi ®ã
k f(Xk), X - Xk , X P(Xk) Q.
Cã hai kh¶ n¨ng xÈy ra:
a) NÕu k 0, tøc lµ
~
f(Xk) , X - Xk f(Xk) , X k - Xk 0, X M,
ta ®îc Xk lµ ph¬ng ¸n tèi u cÇn t×m. KÕt thóc thuËt to¸n.
13
~
b) NÕu k < 0, chøng tá f(X) gi¶m theo híng S = X k - Xk, nghÜa lµ f(X) gi¶m
~
trªn ®o¹n [Xk, X k ].
~
Ký hiÖu Xk = Xk + k( X k - Xk), trong ®ã k ®îc chän sao cho Zk lµ híng chÊp
nhËn ®îc tõ Xk.
g(k) = min g() = f(Xk + (Zk), [0, 1].
§Æt
Xk+1 = Xk + kZk.
Râ rµng
f(Xk+1) f(Xk).
G¸n Xk := Xk+1, råi trë l¹i bíc k.
T¬ng tù ta còng cã ®Þnh lý vÒ tÝnh hiÖu qu¶ cña thuËt to¸n nh ®· nªu ë ®Þnh
lý 1.1.3.2.
1.2.1. BiÕn ngÉu nhiªn vµ hµm ph©n phèi
1.2.1.1. BiÕn ngÉu nhiªn
Cho kh«ng gian ®o (, ℝ) vµ ℝ = ℝ-,+.
1) §Þnh nghÜa 1. Hµm thùc X = X() c¸c ®Þnh trªn , lÊy gi¸ trÞ trªn ℝ ®îc gäi lµ hµm ℝ- ®o ®îc (hoÆc biÕn ngÉu nhiªn suy réng) nÕu
: X() B = X –1(B) ℝ, víi mçi B ℝ(ℝ),
trong ®ã ℝ(ℝ) lµ - ®¹i sè c¸c tËp Borel cña trôc thùc ℝ.
NÕu X : ℝ = (- ; +) th× ta cã kh¸i niÖm biÕn ngÉu nhiªn.
2) §Þnh lý. Gi¶ sö X : ℝ. Khi ®ã c¸c mÖnh ®Ò sau lµ t¬ng ®¬ng
a) X lµ biÕn ngÉu nhiªn
b) : X() < x ℝ víi mäi x ℝ.
c) : X() x ℝ víi mäi x ℝ.
d) : a X < b ℝ víi a < b bÊt kú.
3) §Þnh lý. Gi¶ sö X, Y lµ c¸c biÕn ngÉu nhiªn. Khi ®ã X Y, XY, X Y, X
Y, X+ = X 0; X - = (-X) 0; ℝXℝ = X + + X – còng lµ c¸c biÕn ngÉu nhiªn. §Æc
biÖt, nÕu Y kh«ng triÖt tiªu th× X/Y lµ biÕn ngÉu nhiªn.
4) §Þnh nghÜa 2. Gi¶ sö (, ℝ) vµ (E, ) lµ hai kh«ng gian ®o. Nh ®· biÕt,
¸nh x¹ X : E, ℝ/ ®o ®îc cßn ®îc gäi lµ phÇn tö ngÉu nhiªn.
14
Th«ng thêng, E hoÆc lµ kh«ng gian mªtric hoÆc lµ kh«ng gian t«p«, cßn lµ
- ®¹i sè c¸c tËp Borel ( = ℝ(E)).
Khi E = ℝ, E = ℂ, E = ℝd víi - ®¹i sè c¸c tËp Borel t¬ng øng th× phÇn tö
ngÉu nhiªn t¬ng øng ®îc gäi lµ biÕn ngÉu nhiªn (thùc), biÕn ngÉu nhiªn phøc
hay vect¬ ngÉu nhiªn. Vect¬ ngÉu nhiªn d – chiÒu ®îc biÓu diÔn duy nhÊt díi
d¹ng
X = (X1, ..., Xn)
trong ®ã Xk = kX, víi k lµ ¸nh x¹ chiÕu tõ Rd lªn täa ®é thø k. V× k lµ c¸c hµm
liªn tôc nªn Xk lµ biÕn ngÉu nhiªn. §¶o l¹i, nÕu c¸c Xk lµ biÕn ngÉu nhiªn th× X lµ
vect¬ ngÉu nhiªn.
5) Ph©n phèi cña phÇn tö ngÉu nhiªn
Gi¶ sö X lµ phÇn tö ngÉu nhiªn x¸c ®Þnh trªn (, ℝ, ℝ) nhËn gi¸ trÞ trªn (E,
). Hµm tËp
ℝX(B) = ℝ(X –1(B)), B ,
®îc gäi lµ ph©n phèi gi¸ trÞ trªn (E, ). §ã lµ mét ®é ®o x¸c suÊt cßn ®îc gäi lµ
¶nh cña ℝ qua X, ký hiÖu lµ X(ℝ).
Khi (E, ) = (ℝT, B(ℝT)), phÇn tö ngÉu nhiªn X cßn ®îc gäi lµ hµm ngÉu
nhiªn. NÕu T ℝ th× X ®îc gäi lµ qu¸ tr×nh ngÉu nhiªn.
1.2.1.2. Hµm ph©n phèi x¸c suÊt cña biÕn ngÉu nhiªn
Gi¶ sö X lµ biÕn ngÉu nhiªn x¸c ®Þnh trªn (, ℝ, ℝ) nhËn gi¸ trÞ trªn ℝ = (-;
+).
1. §Þnh nghÜa. Hµm sè
FX(x) = ℝX < x, x ℝ
(1.22)
®îc gäi lµ hµm ph©n phèi cña biÕn ngÉu nhiªn X.
2. §Þnh nghÜa. Mét ®¹i lîng ngÉu nhiªn chØ nhËn h÷u h¹n hoÆc ®Õm ®îc gi¸
trÞ ®îc gäi lµ ®¹i lîng ngÉu nhiªn rêi r¹c
F(x) =
trong ®ã pi > 0;
i:xi x
pi
p = 1, víi S = x : 1 i < lµ tËp con kh«ng qu¸ ®Õm ®îc
i
i
i
cña ℝ.
3. §Þnh nghÜa. §¹i lîng ngÉu nhiªn X ®îc gäi lµ ®¹i lîng ngÉu nhiªn liªn tôc
nÕu hµm ph©n phèi F(x) lµ hµm liªn tôc vµ tån t¹i hµm p(x) 0 sao cho
15
x
F(x) =
p(t)dt, x ℝ.
Khi ®ã p(x) ®îc gäi lµ hµm mËt ®é cña X.
4. Mét sè hµm ph©n phèi thêng gÆp
1) Ph©n phèi nhÞ thøc: TiÕn hµnh mét d·y n phÐp thö Bernoulli víi x¸c suÊt
thµnh c«ng ë mçi phÐp thö lµ p, 0 p 1. Gi¶ sö X lµ sè lÇn thµnh c«ng trong n
phÐp thö ®ã. Râ rµng X lµ biÕn ngÉu nhiªn rêi r¹c víi miÒn gi¸ trÞ S = 0, 1, ..., n
k
vµ ℝ[X = k] = C n pk(1 – p)n – k, k S.
Khi ®ã, X ®îc gäi lµ cã ph©n phèi nhÞ thøc víi c¸c tham sè n, p hay nãi gän,
X cã ph©n phèi B(n, p) (ta cßn viÕt X ~ B(n, p)).
2) Ph©n phèi Poisson: BiÕn ngÉu nhiªn X gäi lµ cã ph©n phèi Poisson víi
tham sè > 0 (X ~ P()) nÕu X cã miÒn gi¸ trÞ S = N = 0, 1, ... vµ
ℝ[X = k] =
k .e
k!
, k = 0, 1, ...
3) Ph©n phèi nhÞ thøc ©m: §¹i lîng ngÉu nhiªn X ®îc gäi lµ cã ph©n phèi nhÞ
thøc ©m, ký hiÖu X ~ NB(r, p) nÕu X cã hµm x¸c suÊt:
r 1
ℝ[X = k] = C k 1 prqk – r , k = r, r +1, ...
4) Ph©n phèi chuÈn: §¹i lîng ngÉu nhiªn X ®îc gäi lµ cã ph©n phèi chuÈn
(Gauss) víi tham sè ℝ, > 0, ký hiÖu X ~ N(, 2) nÕu X cã hµm mËt ®é
y
2
p(x)
( x )
1
2 2 .
p(x) =
.e
2
0
p(x) =
x2
2
x
y
NÕu = 0, = 1 th× X ~ N(0, 1) ®îc gäi lµ ph©n phèi chuÈn t¾c vµ
1
.e
2
p(x)
.
0
x
5) Ph©n phèi mò. §¹i lîng ngÉu nhiªn X ®îc gäi lµ cã ph©n phèi mò víi tham
sè > 0, ký hiÖu X ~ () nÕu X cã hµm mËt ®é
p(x) =
0
nÕu x 0
e- x nÕu x > 0
6) Ph©n phèi ®Òu. BiÕn ngÉu nhiªn X ®îc gäi lµ cã ph©n phèi ®Òu trªn ®o¹n
[a, b] nÕu
16
1
p(x) = b a nÕu a x b
0
nÕu x [a, b].
1.2.2. C¸c sè ®Æc trng cña biÕn ngÉu nhiªn
Trong nhiÒu trêng hîp, ta kh«ng thÓ biÕt hµm ph©n phèi cña biÕn ngÉu nhiªn.
V× thÕ cÇn ph¶i biÕt mét sè ®Æc trng b»ng sè cña hµm ph©n phèi. Trong phÇn nµy
chóng ta sÏ nh¾c l¹i c¸c sè ®Æc trng quan träng nhÊt cña biÕn ngÉu nhiªn.
1.2.2.1. Kú väng to¸n. Kú väng to¸n, moment lµ c¸c ®Æc trng sè quan träng
cña biÕn ngÉu nhiªn, chóng cho biÕt mét phÇn, ®«i khi toµn bé vÒ ph©n phèi cña
biÕn ngÉu nhiªn
1) §Þnh nghÜa. Gi¶ sö X lµ ®¹i lîng ngÉu nhiªn khi ®ã kú väng cña X lµ EX ®îc x¸c ®Þnh bëi c«ng thøc sau:
nÕu X rêi r¹c
xi p i ,
i 1
EX =
nÕu X liªn tôc cã hµm mËt ®é lµ p(x).
xp ( x )dx,
ý nghÜa: EX b»ng gi¸ trÞ trung b×nh theo x¸c suÊt cña X.
2) TÝnh chÊt
a) NÕu X 0 th× EX 0
b) NÕu X = c th× EX = c
c) X Y th× EX EY
d) E(aX + bY) = aEX + bEY
®) NÕu X, Y ®éc lËp th× E(XY) = EX.EY
e) NÕu f(x) lµ hµm liªn tôc th× f(X) lµ ®¹i lîng ngÉu nhiªn vµ
nÕu X rêi r¹c
f ( xi ) p i ,
i
Ef(X) =
nÕu X liªn tôc, cã hµm mËt ®é p(x).
f ( x ) p ( x )dx,
1.2.2.2. Ph¬ng sai. Sè DX := E(X – EX)2 ®îc gäi lµ ph¬ng sai cña X.
1.2.2.3. §é lÖch chuÈn. Sè X = DX ®îc gäi lµ ®é lÖch chuÈn cña X.
1.2.2.4. Ph©n vÞ cÊp p (0 < p < 1). Gi¶ sö ®¹i lîng ngÉu nhiªn X cã hµm ph©n
phèi lµ F(x) liªn tôc th× khi ®ã sè xp (0 < p < 1) ®îc gäi lµ ph©n vÞ cÊp p cña X
nÕu F(xp) = p (tøc lµ p(X < xp) = p).
§Æc biÖt, nÕu p =
X = medX).
1 th× x1/2 = m : trung vÞ b»ng median cña X (ký hiÖu
2
17
1.2.2.5. Mode
§Þnh nghÜa. Gi¶ sö X lµ ®¹i lîng ngÉu nhiªn rêi r¹c, khi ®ã x0 = modX nÕu
p(X = x0) = max(X = xi).
Gi¶ sö X lµ ®¹i lîng ngÉu nhiªn liªn tôc cã hµm mËt ®é lµ p(x). Sè x0 = modX nÕu
p(x0) = max p(x).
xR
Chó ý:
a) NÕu X ~ B(n, p) th× EX = np; DX = npq víi p + q = 1.
b) NÕu X ~ p() ( > 0) th× EX = DX = .
c) NÕu X ~ NB(r, p) th× EX =
r ; DX = rq .
p
p2
d) NÕu X ~ N(, 2) th× EX = ; DX = 2.
d) NÕu X ~ () th× EX =
1 ; DX = 1 .
2
Ch¬ng 2
Quy ho¹ch ngÉu nhiªn hai giai ®o¹n
2.1. Bµi to¸n quy ho¹ch ngÉu nhiªn 2 giai ®o¹n
2.1.1. Quy ho¹ch ngÉu nhiªn, ph©n lo¹i c¸c bµi to¸n quy ho¹ch ngÉu
nhiªn
2.1.1.1. Quy ho¹ch ngÉu nhiªn
Trong thùc hµnh c¸c m« h×nh tiÒn ®Þnh, thêng kh«ng bao qu¸t ®îc c¸c qu¸
tr×nh thùc tiÔn trong kinh tÕ, ®iÒu ®ã thÓ hiÖn ë sù kh«ng ®Çy ®ñ cña th«ng tin.
Trong mét vµi trêng hîp mét sè hoÆc tÊt c¶ c¸c tham sè cña m« h×nh mang ®Æc
tÝnh ngÉu nhiªn. Trong c¸c trêng hîp kh¸c, th«ng tin cã ®îc kh«ng cho phÐp
thiÕt lËp ®îc ®Æc trng biÕn ®æi cña c¸c tham sè diÔn t¶ qu¸ tr×nh cÇn nghiªn cøu.
Nh÷ng t×nh huèng ®ã gäi chung lµ kh«ng x¸c ®Þnh. C¸c bµi to¸n tèi u khi thiÕt
lËp chóng mµ kh«ng cã sù cÆn kÏ cña d÷ liÖu vÒ c¸c ®iÒu kiÖn cña chóng gäi lµ
bµi to¸n ngÉu nhiªn. V× c¸c bµi to¸n ngÉu nhiªn buéc ph¶i thiÕt lËp vµ gi¶i trong
®iÒu kiÖn thiÕu th«ng tin nªn hiÖu qu¶ kinh tÕ cña lêi gi¶i nhËn ®îc sÏ bÞ h¹ thÊp.
§Ó nghiªn cøu c¸c t×nh huèng ®· nªu, cÇn x©y dùng c¸c ph¬ng ph¸p ®Æc biÖt,
tËp hîp l¹i trong mét lÜnh vùc cña quy ho¹ch to¸n häc gäi lµ quy ho¹ch ngÉu
nhiªn. Quy ho¹ch ngÉu nhiªn nghiªn cøu lý thuyÕt vµ c¸c ph¬ng ph¸p gi¶i bµi
to¸n cùc trÞ cã ®iÒu kiÖn khi kh«ng ®ñ th«ng tin vÒ c¸c ®iÒu kiÖn cña bµi to¸n.
C¸c bµi to¸n quy ho¹ch ngÉu nhiªn cã ý nghÜa thùc tiÔn lín.
2.1.1.2. Ph©n lo¹i c¸c bµi to¸n quy ho¹ch ngÉu nhiªn
C¸c bµi to¸n tèi u ®îc thiÕt lËp tõ thùc tÕ thêng gÆp ph¶i c¸c d÷ liÖu cã th«ng
tin kh«ng ®Çy ®ñ, phô thuéc vµo c¸c yÕu tè ngÉu nhiªn. C¸c bµi to¸n nh vËy ®îc
18
gäi lµ bµi to¸n quy ho¹ch ngÉu nhiªn. Quy ho¹ch ngÉu nhiªn ®îc ph©n thµnh
nhiÒu lo¹i, tuú thuéc vµo tiªu chuÈn ph©n lo¹i. Trong kho¸ luËn nµy, chóng t«i
muèn ®Ò cËp tíi mét sè d¹ng nh sau:
i) Quy ho¹ch ngÉu nhiªn thô ®éng vµ quy ho¹ch ngÉu nhiªn tÝch cùc
Quy ho¹ch ngÉu nhiªn thô ®éng: §ã lµ líp c¸c bµi to¸n QHNN cã c¸ch gi¶i
cho phÐp t×m nghiÖm vµ cùc trÞ cña hµm môc tiªu trong c¸c bµi to¸n tèi u ho¸
víi c¸c d÷ liÖu ngÉu nhiªn mét c¸ch trùc tiÕp (ch¼ng h¹n ph¬ng ph¸p dïng quy
ho¹ch tham sè).
QHNN tÝch cùc: §ã lµ líp c¸c bµi to¸n QHNN cã c¸ch gi¶i cho phÐp lùa
chän nghiÖm trong c¸c ®iÒu kiÖn khñng ho¶ng vµ kh«ng x¸c ®Þnh, nghiÖm cña
bµi to¸n cã thÓ ®iÒu chØnh theo tõng giai ®o¹n xuÊt hiÖn yÕu tè ngÉu nhiªn.
ii) Quy ho¹ch ngÉu nhiªn mét giai ®o¹n, hai giai ®o¹n vµ nhiÒu giai ®o¹n.
+ C¸c bµi to¸n quy ho¹ch ngÉu nhiªn mét giai ®o¹n: Lµ c¸c bµi to¸n trong ®ã
sù tuÇn tù xuÊt hiÖn th«ng tin xuÊt ph¸t kh«ng cã ý nghÜa khi chän nghiÖm vµ
nghiÖm ®îc nhËn mét lÇn sau ®ã nã kh«ng ®îc söa l¹i. C¸c bµi to¸n nh vËy cã
thÓ t¹o ra bëi c¸c bµi to¸n tèi u ho¸ tÊt ®Þnh khi c¸c d÷ liÖu bÞ mÊt tÝnh x¸c ®Þnh
vµ nhËn ®Æc trng ngÉu nhiªn.
Trong c¸c bµi to¸n mét giai ®o¹n, hµm môc tiªu vµ ®Æc trng cña c¸c rµng
buéc ®îc chän theo c¸c c¸ch kh¸c nhau. §Ó t×m hµm môc tiªu cã thÓ xÐt x¸c
suÊt r¬i cña nghiÖm vµo mét miÒn nãi chung lµ ngÉu nhiªn hoÆc lµ kú väng to¸n
häc cña mét hµm nµo ®ã ®èi víi nghiÖm. Trong mét sè c¸c trêng hîp, c¸c rµng
buéc cña bµi to¸n cã thÓ tho¶ m·n víi mäi gi¸ trÞ cã thÓ cña c¸c tham sè ngÉu
nhiªn. Trong c¸c trêng hîp kh¸c, ®ßi hái x¸c suÊt r¬i cña nghiÖm vµo miÒn chÊp
nhËn ®îc ph¶i kh«ng nhá h¬n mét sè ®· cho.
+ C¸c bµi to¸n quy ho¹ch ngÉu nhiªn hai giai ®o¹n: Lµ c¸c bµi to¸n xuÊt hiÖn
khi kÕ ho¹ch ho¸ viÖc s¶n xuÊt s¶n phÈm trong trêng hîp khi v¾ng c¸c d÷ liÖu vÒ
nhu cÇu cña nã. Trong t×nh huèng nµy, ®Çu tiªn nhËn ®îc nghiÖm s¬ bé vÒ khèi
lîng s¶n xuÊt trªn c¬ së th«ng tin cã ®îc tõ thùc nghiÖm tríc ®ã (giai ®o¹n 1)
sau ®ã víi sù thiÕt lËp nhu cÇu sÏ nhËn ®îc nghiÖm ®óng ®¾n (giai ®o¹n 2). Chó
ý r»ng nghiÖm s¬ bé kh«ng ®îc lµm mÊt kh¶ n¨ng cña viÖc hiÖu chØnh nã ë giai
®o¹n 2. Ngoµi ra, nghiÖm s¬ bé vµ nghiÖm hiÖu chØnh ph¶i phèi hîp sao cho b¶o
®¶m chi phÝ trung b×nh tèi thiÓu cho c¶ 2 giai ®o¹n.
§èi víi mét lo¹t c¸c thiÕt lËp cña quy ho¹ch ngÉu nhiªn hai giai ®o¹n, ®· x©y
dùng ®îc c¸c ph¬ng ph¸p gi¶i kh¸ tin cËy.
+ C¸c bµi to¸n quy ho¹ch ngÉu nhiªn nhiÒu giai ®o¹n. Trong c¸c bµi to¸n
nµy, theo møc ®é nhËn ®îc th«ng tin vÒ qu¸ tr×nh ph¸t triÓn cã kh¶ n¨ng chØnh lý
nhiÒu lÇn nghiÖm thu ®îc, cã kÓ ®Õn c¸c rµng buéc ban ®Çu vµ c¸c ®Æc trng ngÉu
nhiªn dù ®o¸n cña c¸c tham sè, diÔn t¶ qu¸ tr×nh t¹i mçi giai ®o¹n. C¸c bµi to¸n
nhiÒu giai ®o¹n cã thÓ xÐt víi c¸c rµng buéc cøng hoÆc c¸c rµng buéc x¸c suÊt.
VÝ dô vÒ c¸c bµi to¸n quy ho¹ch ngÉu nhiªn nhiÒu giai ®o¹n lµ c¸c bµi to¸n vÒ
lËp kÕ ho¹ch viÔn c¶nh, ®iÒu chØnh c¸c qu¸ tr×nh kü thuËt, ®iÒu khiÓn linh ho¹t
c¸c ®èi tîng vò trô...
19
2.1.2. Quy ho¹ch ngÉu nhiªn 2 giai ®o¹n
Bµi to¸n quy ho¹ch ngÉu nhiªn 2 giai ®o¹n lµ bµi to¸n xuÊt hiÖn khi lËp kÕ
ho¹ch s¶n xuÊt mµ d÷ liÖu cßn phô thuéc vµo c¸c biÕn ngÉu nhiªn. Bµi to¸n nµy
®îc gi¶i quyÕt theo hai giai ®o¹n:
Giai ®o¹n 1: X¸c ®Þnh nghiÖm mét c¸ch s¬ bé trªn c¬ së c¸c th«ng tin cã ®îc
tríc ®ã.
Giai ®o¹n 2: ChØnh lý nghiÖm theo nhu cÇu, cã chó ý ®Õn c¸c yÕu tè ngÉu
nhiªn.
Bµi to¸n quy ho¹ch ngÉu nhiªn hai giai ®o¹n ®· ®îc nhiÒu t¸c gi¶ nghiªn cøu
vµ ®a ra nhiÒu thuËt to¸n kh¸ hiÖu qu¶.
XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh
víi ®iÒu kiÖn
C’x min
Ax = b
x 0.
trong ®ã C vµ x lµ c¸c vect¬ cÊp n1, A lµ ma trËn cÊp mn, B lµ ma trËn bËc m1.
Gi¶ sö cha hoµn toµn biÕt b, nhng biÕt hµm ph©n phèi cña nã, víi kú väng
h÷u h¹n Eb. Râ rµng kh«ng thÓ x¸c ®Þnh x tõ c¸c ph¬ng tr×nh Ax = b. Sù kh¸c
nhau gi÷a Ax vµ b còng chÝnh lµ mét biÕn ngÉu nhiªn vµ cã hµm ph©n phèi phô
thuéc vµo x. Bµi to¸n cña ta lµ quyÕt ®Þnh lµm cùc tiÓu tæng Cx vµ c¸c møc ph¹t
cho sù kh¸c nhau gi÷a Ax vµ b. §iÒu ®ã cã nghÜa lµ, gi¶ sö d lµ vect¬ ph¹t, víi lîng ph¹t cÇn t×m y 0, sao cho ®¹t cùc tiÓu lîng ph¹t (mind’y) mµ tho¶ m·n
®iÒu kiÖn vÒ ®é lÖch
By = b – Ax.
Nh vËy, bµi to¸n quy ho¹ch ngÉu nhiªn hai giai ®o¹n ®îc m« t¶ nh sau:
C’x + Emind’y min
Ax + By = b
x, y 0,
trong ®ã C, x, A, B lµ c¸c ma trËn nh ®· nªu, d vµ y lµ c¸c ma trËn cÊp m 1.
Trong bµi to¸n nµy, ta ph¶i t×m vect¬ x tríc khi biÕt gi¸ trÞ thùc cña thµnh
phÇn cña b. Khi x ®· biÕt th× ph¶i x¸c ®Þnh y. §©y lµ giai ®o¹n 2 cña bµi to¸n. Tõ
®ã ta nghÜ tíi xÐt bµi to¸n
T×m y sao cho:
d’y min
By = b – Ax; y 0,
- Xem thêm -
.DOC 
32 
128 
50 
