Möc löc
trang
Mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Ch÷ìng 1. Mët sè ki¸n thùc cì sð . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1. Mët sè v§n · cì sð cõa lþ thuy¸t x¡c su§t . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1. σ-¤i sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
1.1.2. Khæng gian o v ë o x¡c su§t . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
1.1.3. ¤i l÷ñng ng¨u nhi¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4. Ký vång cõa ¤i l÷ñng ng¨u nhi¶n . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.5. Ph÷ìng sai cõa ¤i l÷ñng ng¨u nhi¶n . . . . . . . . . . . . . . . . . . . . . . . . .8
1.1.6. Ph¥n phèi cõa ¤i l÷ñng ng¨u nhi¶n v h m ph¥n phèi . . . . . . .8
1.1.7. Mët sè h m ph¥n phèi th÷íng g°p . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.8. Mët sè lo¤i hëi tö cì b£n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.9. Bê · Borel-Cantelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.10. ành lþ giîi h¤n trung t¥m Moivre-Laplace . . . . . . . . . . . . . . . . 12
1.1.11. Luªt sè lîn Bernoulli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2. B i to¡n quy ho¤ch tuy¸n t½nh ng¨u nhi¶n 2 giai o¤n . . . . . . . . . . . .12
1.2.1. B i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2. B i to¡n quy ho¤ch tuy¸n t½nh ng¨u nhi¶n hai giai o¤n . . . . 14
Ch÷ìng 2. X¥y düng l¤i h m gi¡ trà v h÷îng ti¸p cªn
gi£i b i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2
2.1. Thi¸t lªp b i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1. N¶u b i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2. C¡c gi£ thi¸t ban ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
2.2. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà b i to¡n quy ho¤ch
nguy¶n tuy¸n t½nh v quy ho¤ch nguy¶n bªc hai . . . . . . . . . . . . . 17
2.2.1. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà b i to¡n quy ho¤ch nguy¶n
tuy¸n t½nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà b i to¡n quy ho¤ch nguy¶n
bªc hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3. X¥y düng h m gi¡ trà cõa b i to¡n quy ho¤ch nguy¶n bªc hai
tham sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.1. Giîi thi»u chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2. X¥y düng h m gi¡ trà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3
Mð ¦u
Trong nhi·u b i to¡n s£n xu§t v ¦u t÷, khi c¡c thæng tin v· dú li»u
bi¸t rã th¼ vi»c tèi ÷u l¢i su§t ¢ ÷ñc nhi·u cæng tr¼nh khoa håc nghi¶n
cùu. Do nhi·u lþ do kh¡c nhau, m thæng tin v· dú li»u khæng ¦y õ, phö
thuëc ¤i l÷ñng ng¨u nhi¶n n o â. Lóc â b i to¡n °t ra c¦n nghi¶n cùu
s³ l b i to¡n tèi ÷u ng¨u nhi¶n. N¸u b i to¡n cán ái häi bi¸n sè nhªn gi¡
trà nguy¶n th¼ ta câ b i to¡n quy ho¤ch nguy¶n ng¨u nhi¶n. Chóng ta h¢y
l§y b i to¡n sau ¥y l m v½ dö: Mët Cæng ty lp r¡p m¡y t½nh câ thº lüa
chån mët lo¤i linh ki»n trong n cì sð s£n xu§t linh ki»n kh¡c nhau, vîi sè
vèn câ ÷ñc l b. C¡c linh ki»n n y c¦n gh²p c°p æi v o mët m¡y t½nh. Khi
mët c°p æi (i, j) ÷ñc gh²p th¼ s³ cho mët gi¡ trà l¢i l cij , (i, j = 1, ..., n).
Kh£ n«ng ti·n vèn b th÷íng thay êi, bi¸n ëng theo ¤i l÷ñng ng¨u nhi¶n
(LNN) b(ω). Häi n¶n ¦u t÷ s£n xu§t nh÷ th¸ n o º câ têng sè l¢i lîn
nh§t, vîi chi ph½ khæng v÷ñt qu¡ b(ω).
Khi â, n¸u kþ hi»u xi l linh ki»n mua cõa cì sð s£n xu§t i, i = 1, ..., n,
(xi b¬ng 1 n¸u ÷ñc lüa chån v b¬ng 0 n¸u ng÷ñc l¤i). Lóc n y ta câ b i
to¡n quy ho¤ch nguy¶n ng¨u nhi¶n vîi r ng buëc l : T¼m x = (xi) ∈ {0; 1}
sao cho
n
n
o
n
(P)
vîi i·u ki»n
max f (x) =
XX
cij xi xj
i=1 j=1
n
X
ai xi ≤ b(ω),
i=1
x = (xi ) ∈ {0; 1}n .
B i to¡n P câ d¤ng b i to¡n quy ho¤ch nguy¶n ng¨u nhi¶n bªc hai, vîi
v¸ ph£i r ng buëc ng¨u nhi¶n. º gi£i b i to¡n n y, ng÷íi ta th÷íng xû lþ
theo hai giai o¤n.
4
Vi»c nghi¶n cùu nh¬m t¼m ra líi gi£i tèi ÷u ang °t ra cho nhi·u nh
khoa håc nghi¶n cùu. Tòy thuëc v o sü thº hi»n cõa mæ h¼nh b i to¡n (P),
công nh÷ c¡c c¡ch ti¸p cªn kh¡c nhau m nhi·u cæng tr¼nh khoa håc ¢
cæng bè. Ch¯ng h¤n c¡c t¡c gi£ A. A. Gaivoronski, A. Lisser, R. Lopez and
H. Xu (2010); W. P. Adams, R. Forrester, F. Glover (2004); ...
G¦n ¥y, chóng tæi ti¸p cªn b i b¡o: Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides, cõa c¡c t¡c gi£ O. Y. Özaltm, O.
Prokopyev v A. J. Schaefer - USA [9], câ mæ h¼nh to¡n håc têng qu¡t b i
to¡n (P) ¢ n¶u. Chóng tæi hy vång r¬ng nhúng k¸t qu£ cõa b i b¡o s³
gióp chóng tæi ành h÷îng ÷ñc kh£ n«ng nghi¶n cùu cõa · t i luªn v«n.
â l lþ do chóng tæi chån · t i: "Lîp b i to¡n Quy ho¤ch nguy¶n
bªc hai, vîi v¸ ph£i r ng buëc ng¨u nhi¶n".
Luªn v«n ÷ñc chia l m hai ch÷ìng:
Ch÷ìng 1. Ki¸n thùc chu©n bà. Trong ch÷ìng n y, chóng tæi tr¼nh
b y nhúng kh¡i ni»m v ki¸n thùc cð sð cõa lþ thuy¸t x¡c su§t; b i to¡n
quy ho¤ch tuy¸n t½nh nguy¶n ng¨u nhi¶n hai giai o¤n. C¡c ki¸n thùc
chu©n bà n y nh¬m phöc vö cho vi»c nghi¶n cùu cõa · t i.
Ch÷ìng 2. X¥y düng l¤i h m gi¡ trà v h÷îng ti¸p cªn gi£i b i
to¡n. ¥y l nëi dung ch½nh cõa luªn v«n. Tr÷îc h¸t chóng tæi n¶u b i
to¡n, tø â ành d¤ng l¤i h m gi¡ trà. Ti¸p theo tr¼nh b y mët sè thuªt
to¡n gi£i b i to¡n ¢ cho.
Luªn v«n ÷ñc ho n th nh d÷îi sü h÷îng d¨n cõa th¦y gi¡o PGS.TS.
Tr¦n Xu¥n Sinh, nh¥n dàp n y tæi xin b y tä láng bi¸t ìn s¥u sc tîith¦y
v c£m ìn c¡c th¦y cæ gi¡o trong tê X¡c su§t thèng k¶ v to¡n ùng döng
¢ gi£ng d¤y, ch¿ b£o cho tæi trong suèt thíi gian håc tªp v nghi¶n cùu.
Công nh¥n dàp n y tæi xin gûi líi c£m ìn tîi th¦y gi¡o cæ gi¡o trong
khoa To¡n, Pháng Sau ¤i håc tr÷íng ¤i håc Vinh. Tæi xin b y tä líi
c£m ìn tîi b¤n b± v gia ¼nh ¢ t¤o i·u ki»n thuªn ti»n cho tæi ho n
5
th nh luªn v«n n y.
M°c dò ¢ cè gng song luªn v«n khæng thº tr¡nh khäi nhúng sai sât.
Chóng tæi mong nhªn ÷ñc nhúng âng gâp cõa quþ th¦y cæ gi¡o v c¡c
b¤n º luªn v«n ÷ñc ho n thi»n hìn.
Chóng tæi xin ch¥n th nh c£m ìn!
Vinh, th¡ng 10 n«m 2014
T¡c gi£
6
Ch֓ng 1
Mët sè ki¸n thùc cì sð
1.1. Mët sè v§n · cì sð cõa lþ thuy¸t x¡c su§t
1.1.1. σ-¤i sè
Gi£ sû Ω 6= ∅ v P (Ω) l hå t§t c£ c¡c tªp con cõa Ω. Khi â F ⊂ P (Ω)
÷ñc gåi l mët σ-¤i sè n¸u:
i) Ω ∈ F ;
ii) N¸u A ∈ F th¼ Ac = Ω \ A ∈ F ;
iii) N¸u An ∈ F, ∀n = 1, 2, ... th¼
S∞
n=1 An
∈ F.
1.1.2. Khæng gian o v ë o x¡c su§t
Gi£ sû Ω l mët tªp tòy þ kh¡c réng, F l mët σ-¤i sè c¡c tªp con cõa
Ω. Khi â c°p (Ω; F) ÷ñc gåi l mët khæng gian o. ¡nh x¤ P : F → R
÷ñc gåi l ë o x¡c su§t tr¶n F n¸u:
i) P(A) ≥ 0 v ∀A ∈ F (t½nh khæng ¥m);
ii) P(Ω) = 1 (t½nh chu©n hâa);
iii) N¸u An ∈ F, (n = 1, 2, ...), Ai
T
Aj = Ai Aj = ∅, (i 6= j)
[
X
∞
∞
P
An =
P(An ),
n=1
n=1
(t½nh cëng ¸m ÷ñc).
Lóc n y
(Ω, F, P) ÷ñc gåi l khæng gian x¡c su§t ;
th¼
7
σ -¤i
sè F ÷ñc gåi l σ-¤i sè c¡c bi¸n cè ;
Méi A ∈ F ÷ñc gåi l mët bi¸n cè ;
Bi¸n cè Ω ∈ F ÷ñc gåi l bi¸n cè chc chn ;
Bi¸n cè ∅ ∈ F gåi l bi¸n cè khæng thº câ ;
Bi¸n cè A = Ω \ A ÷ñc gåi l bi¸n cè èi lªp cõa bi¸n cè A;
N¸u A ∩ B = AB = ∅ th¼ A, B ÷ñc gåi l c¡c bi¸n cè xung khc ;
Khæng gian x¡c su§t (Ω; F; P) gåi l khæng gian x¡c su§t ¦y õ n¸u
måi tªp con cõa bi¸n cè câ x¡c su§t khæng, ·u l bi¸n cè.
1.1.3. ¤i l÷ñng ng¨u nhi¶n
Gi£ sû (Ω; F; P) l khæng gian x¡c su§t, G l σ-¤i sè con cõa σ ¤i
sè F, B(R) l σ-¤i sè Borel tr¶n ÷íng th¯ng thüc R. Khi â ¡nh x¤
X : Ω → R ÷ñc gåi l ¤i l÷ñng ng¨u nhi¶n G o ÷ñc n¸u vîi måi
B ∈ B(R) th¼ X −1 (B) = {ω : X(ω) ∈ B} ∈ G .
Trong tr÷íng hñp °c bi»t, khi X l ¤i l÷ñng ng¨u nhi¶n F o ÷ñc
th¼ X gåi l ¤i l÷ñng ng¨u nhi¶n.
1.1.4. Ký vång cõa ¤i l÷ñng ng¨u nhi¶n
Gi£ sû X : (Ω; F; P) → (R; B(R)) l ¤i l÷ñng ng¨u nhi¶n. Khi â, t½ch
ph¥n Lebesgue cõa X theo ë o P (n¸u tçn t¤i) ÷ñc gåi l ký vång cõa
X v kþ hi»u l EX . Vªy
Z
EX =
XdP.
Ω
Ký vång câ c¡c t½nh ch§t sau ¥y:
1. N¸u X ≥ 0 th¼ EX ≥ 0;
2. N¸u X = C h¬ng sè th¼ EX = C ;
3. N¸u tçn t¤i EX th¼ vîi måi C ∈ R, ta câ E(CX) = C(EX);
4. N¸u tçn t¤i EX v EY th¼ E(X ± Y ) = EX ± EY ;
8
5.
P
xi pi ,
i
n¸u X ríi r¤c nhªn c¡c gi¡ trà x1, x2, ....
EX =
vîi P(X = xi) = pi
R
+∞ xp(x)dx, n¸u X li¶n töc câ h m mªt ë p(x).
−∞
1.1.5. Ph÷ìng sai cõa ¤i l÷ñng ng¨u nhi¶n
Gi£ sû X : Ω → R l ¤i l÷ñng ng¨u nhi¶n. Khi â sè DX = E(X−EX)2
(n¸u tçn t¤i) gåi l ph÷ìng sai cõa X . Ph÷ìng sai câ t½nh ch§t:
1. DX = EX 2 − (EX)2;
2. DX ≥ 0;
3. DX = 0 khi v ch¿ khi X = EX = h¬ng sè h.c.c;
4. D(CX) = C 2DX , vîi C ∈ R.
1.1.6. Ph¥n phèi x¡c su§t cõa ¤i l÷ñng ng¨u nhi¶n v h m
ph¥n phèi
Gi£ sû (Ω; F; P) l khæng gian x¡c su§t, X : Ω → R l ¤i l÷ñng ng¨u
nhi¶n. Khi â h m tªp
P : B(R) → R
B → PX (B) = P (X −1 (B))
÷ñc gåi l ph¥n phèi x¡c su§t cõa X .
1.1.7. 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û Bernouli 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} v
P|X = k| = Ckn 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 vi¸t X ∼ B(n; p)).
9
2. Ph¥n phèi Poisson. Bi¸n ng¨u nhi¶n X ÷ñc 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
λk e−λ
P(X = k) =
, k = 0, 1, ...
k!
chu©n. Bi¸n ng¨u nhi¶n X ÷ñc gåi l
3. Ph¥n phèi
câ ph¥n phèi chu©n
(Gauss) vîi tham sè µ ∈ R; σ > 0, kþ hi»u X ∼ N (µ, σ2) n¸u X câ h m
mªt ë
(x−µ)2
1
p(x) = √ .e− 2σ .
σ 2π
N¸u µ = 0; σ = 1 th¼ X ∼ N (0; 1) ÷ñc gåi l ph¥n phèi chu©n tc v
x2
1
p(x) = √ e− 2 .
2π
4. Ph¥n phèi mô. Bi¸n 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 ë
n¸u x ≤ 0
n¸u x > 0.
5. Ph¥n phèi ·u. Bi¸n ng¨u nhi¶n X ÷ñc gåi l câ ph¥n phèi ·u tr¶n
[a, b] n¸u
1 , n¸u a ≤ x ≤ b,
p(x) = b−a
0, n¸u x 6∈ [a, b].
0,
p(x) =
λ.e−λx ,
1.1.8. Mët sè lo¤i hëi tö cì b£n
D¢y c¡c bi¸n ng¨u nhi¶n (Xn) ÷ñc gåi l hëi tö theo x¡c su§t ¸n bi¸n
ng¨u nhi¶n X n¸u vîi ε > 0 b§t k¼ th¼
lim P |Xn − X| > ε = 0.
n→∞
P
Kþ hi»u: Xn →
− X.
10
D¢y c¡c bi¸n ng¨u nhi¶n (Xn) ÷ñc gåi l hëi tö h¦u chc chn tîi bi¸n
ng¨u nhi¶n X n¸u
P( lim |Xn − X| = 0) = 1.
n→∞
Kþ hi»u: Xn −h.c.c
−→ X .
D¢y c¡c bi¸n ng¨u nhi¶n (Xn) ÷ñc gåi l hëi tö theo trung b¼nh c§p
p, (p > 0), tîi bi¸n ng¨u nhi¶n X n¸u
lim E|Xn − X|p = 0.
n→∞
Kþ hi»u: Xn −L→ X .
D¢y c¡c bi¸n ng¨u nhi¶n (Xn) ÷ñc gåi l hëi tö ¦y õ tîi bi¸n ng¨u
nhi¶n X n¸u vîi måi ε > 0 b§t ký th¼
p
∞
X
P(|Xn − X| > ε) < ∞.
n=1
c
− X.
Kþ hi»u: Xn →
D¢y c¡c bi¹n ng¨u nhi¶n (Xn) ÷ñc gåi l hëi tö y¸u (theo ph¥n phèi)
tîi bi¸n ng¨u nhi¶n X n¸u
lim Fn (x) = F (x), ∀x ∈ C(F ),
n→∞
trong â Fn(x) v F (x) t÷ìng ùng l h m ph¥n phèi cõa c¡c bi¸n ng¨u
nhi¶n Xn v X; C(F ) l tªp hñp c¡c iºm m t¤i â F (x) li¶n töc.
D
Kþ hi»u: Xn −→
X.
1.1.9. Bê · Borel-Cantelli
Gi£ sû (An, n ≥ 1), l d¢y c¡c bi¸n cè. Khi â
(i) N¸u
∞
X
th¼
P(lim sup An ) = 0.
n=1
P(An ) < ∞
11
(ii) N¸u
v
∞
X
An , n ≥ 1
ëc lªp th¼
P(An ) < ∞
n=1
P(lim sup An ) = 1, trong
∞ [
∞
\
Ak .
lim sup An =
â
n=1 k=n
Chùng minh. (i) Gi£ sû
∞
X
P(An ) < ∞.
n=1
Khi â
P(lim sup An ) = P
\
∞ [
∞
Ak
= lim P
n→∞
n=1 k=n
∞
X
≤ lim
n→∞
[
∞
Ak
k=n
P(Ak ) = 0.
k=n
(ii) Tr÷îc h¸t ta nhªn x²t r¬ng n¸u 0 ≤ x ≤ 1 th¼ 1 − x ≤ e−x.
Gi£ sû
∞
X
P(An ) = ∞.
n=1
Khi â, v¼ d¢y (An) ëc lªp n¶n d¢y (An) công ëc lªp. Do â vîi måi
n = 1, 2, ... v måi m > n ta câ
1−P
m
[
Ak = P
[
m
k=n
Ak
=P
m
\
k=n
=
m
Y
Ak
k=n
Pm
1 − P(Ak ) = e− k=n P(Ak ) .
k=n
Suy ra
0≤1−P
∞
\
k=n
Ak
m
\
= lim 1 − P
Ak
m→∞
≤ lim e−
m→∞
k=n
Pm
k=n
P(Ak )
= 0.
12
Do â P
A
∪∞
k=n k = 1,
vîi måi n = 1, 2, ... i·u n y k²o theo
P lim sup An = lim P
∞
[
n→∞
Ak = 1.
k=n
â l i·u ph£i chùng minh
1.1.10. ành lþ giîi h¤n trung t¥m Moivre-Laplace
Vîi måi ε > 0, ta câ
r
r
n
n
n(A)
P
− p ≤ ε ∼ Φ ε
−Φ −ε
,
n
pq
pq
trong â h m ph¥n phèi chu©n N (0, 1) ÷ñc x¡c ành
1
Φ(x) =
2π
Z
x
e
−t2
s dt
.
−∞
Chó þ: Ta suy ra pq ≤ 14 , d¨n ¸n ¡nh gi¡
r
r
√
n
n
−Φ −ε
≥ 2Φ 2ε n − 1.
Φ ε
pq
pq
Do vªy, khi n kh¡ lîn ta câ
2
n(A)
− p ≥ ε ≤ 2e−2ne .
P
n
Tø ành lþ giîi h¤n trung t¥m Moivre- Laplace ta câ ÷ñc ành lþ v· luªt
sè lîn Bernoulli.
1.1.11. Luªt sè lîn Bernoulli.
Ta câ
n(A)
lim P
− p ≤ ε = 1,
n
ngh¾a l t¦n su§t n(A)
n hëi tö theo x¡c su§t tîi p.
1.2. B i to¡n quy ho¤ch tuy¸n t½nh ng¨u nhi¶n 2 giai o¤n
1.2.1. B i to¡n.
13
B i to¡n quy ho¤ch tuy¸n t½nh têng qu¡t câ thº ÷a v· d¤ng
min f (x) = cT x ,
vîi i·u ki»n
Ax ≤ b
(LP )
.
x ≥ 0,
trong â x = (x1x2...xn) l ma trªn cët, cT = (c1c2...cn)T l ma trªn chuyºn
và cõa ma trªn cët c, b = (b1b2...bn) l ma trªn cët, A = aij l ma trªn cï
m × n.
B i to¡n quy ho¤ch tuy¸n t½nh tr¶n câ c¡c ph©n tû cõa ma trªn A; b; c
x¡c ành phö thuëc v o ¤i l÷ñng ng¨u nhi¶n th¼ ÷ñc b i to¡n quy ho¤ch
tuy¸n t½nh ng¨u nhi¶n. º nghi¶n cùu b i to¡n quy ho¤ch tuy¸n t½nh ng¨u
nhi¶n, tòy theo y¶u c¦u thüc t¸ cõa b i to¡n m câ nhi·u c¡ch ti¸p cªn
kh¡c nhau.
Thæng th÷íng, ng÷íi ta x²t tîi c¡c lîp b i to¡n 1:
Quy ho¤ch tuy¸n t½nh ng¨u nhi¶n 1 giai o¤n. â l lîp b i to¡n
÷ñc gi£i vîi thæng tin v· dú li»u ban ¦u x¡c ành n o â. Tr¶n cì sð
ph÷ìng ¡n tèi ÷u ¢ gi£i, khi chàu £nh h÷ðng cõa ¤i l÷ñng ng¨u nhi¶n,
ng÷íi ta sû döng c¡c ph÷ìng ph¡p trüc ti¸p (ch¯ng h¤n ph÷ìng ph¡p quy
ho¤ch tham sè, ph÷ìng ph¡p t¡i tèi ÷u....) i·u ch¿nh ph÷ìng ¡n tèi ÷u
cho phò hñp vîi thüc t¸.
Quy ho¤ch tuy¸n t½nh ng¨u nhi¶n 2 giai o¤n. â l lîp b i to¡n
ph÷ìng ¡n ÷ñc xem x²t hai l¦n. L¦n thù nh§t, vîi thæng tin x¡c ành n o
â, ng÷íi ta x¥y düng ph÷ìng ¡n b¬ng vi»c gi£i b i to¡n (*). Trong l¦n
thù nh§t, t¼m ÷ñc ph÷ìng ¡n tèi ÷u gåi l giai o¤n mët. L¦n thù hai,
tr¶n cì sð ph÷ìng ¡n tèi ÷u ¢ gi£i, khi chàu £nh h÷ðng cõa ¤i l÷ñng ng¨u
nhi¶n, ng÷íi ta i·u ch¿nh l¤i ph÷ìng ¡n tèi ÷u cho phò hñp vîi thüc t¸,
b¬ng vi»c t¼m l÷ñng "ph¤t" b² nh§t câ thº do ë l»ch t¤o n¶n tø giai o¤n
14
1. L¦n n y c¦n ¸n vi»c xû lþ dú li»u thæng qua kh¡i ni»m ký vång to¡n
v ÷ñc gåi l giai o¤n hai.
Têng hñp c£ hai giai o¤n, ng÷íi ta câ B i to¡n quy ho¤ch tuy¸n t½nh
ng¨u nhi¶n hai giai o¤n (2SSLP).
1.2.2. B i to¡n quy ho¤ch tuy¸n t½nh hai giai o¤n
(Two-Stage Stochastic Linear Programming)
B i to¡n quy ho¤ch tuy¸n t½nh ng¨u nhi¶n hai giai o¤n câ d¤ng:
min cT x + E(Q(x, ze))
vîi i·u ki»n:
Ax ≤ b
(2SSLP )
.
x ≥ 0,
trong â
Q(x, ze) = min q T y
vîi i·u ki»n
A(e
z )x + Dy = b(e
z)
y ≥ 0.
H m Q(x; ze) ÷ñc gåi l h m hi»u ch¿nh vîi ze ∈ Rn l vectì ng¨u nhi¶n;
E Q(x; ze) biºu di¹n ký vång cõa bi¸n ng¨u nhi¶n Q(x; ze); vectì x v y
t÷ìng ùng l bi¸n cõa giai o¤n thù nh§t v giai o¤n thù hai, D l ma trªn
c§p m×m (thæng th÷íng câ thº l§y ma trªn ìn và); y = (y1, y2, ..., ym); Dy
thº hi»n ë l»ch giúa Ax vîi b v q = (q1, q2, ..., qm) th÷íng gåi l vectì
ph¤t bði t¡c ëng cõa ¤i l÷ñng ng¨u nhi¶n ze.
Giai o¤n thù nh§t bi¸n x l tr¶n cì sð thæng tin câ ÷ñc tø thüc nghi»m.
Giai o¤n thù hai bi¸n y l nghi»m thu ÷ñc khi hi»u ch¿nh nghi»m sì bë
x cõa giai o¤n 1 vîi nhúng thæng tin óng n, tùc l ze nhªn gi¡ trà thüc.
15
Tø â cho th§y b i to¡n (2SSLP) t÷ìng ÷ìng vîi b i to¡n:
min cT x + E(q T y(e
z ))
vîi i·u ki»n
Ax ≤ b
A(e
z )x + Dy(e
z ) ≤ b(e
z)
x≥0
y(e
z) ≥ 0
y(.) ∈ Y − khæng gian
c¡c h m o ÷ñc.
16
Ch֓ng 2
X¥y düng l¤i h m gi¡ trà
v h÷îng ti¸p cªn gi£i b i to¡n
Trong ch÷ìng n y, tr÷îc h¸t chóng tæi giîi thi»u b i to¡n quy ho¤ch
nguy¶n bªc hai vîi v¸ ph£i r ng buëc phö thuëc LNN. º câ h÷îng ti¸p
cªn gi£i, trong luªn v«n n y tr¼nh b y vi»c x¥y düng l¤i h m gi¡ trà, tø â
n¶u ra thuªt to¡n nh¬m thüc hi»n qu¡ tr¼nh x¥y düng n y. Tø b i to¡n
÷ñc chuyºn êi h m gi¡ trà, chóng tæi b¼nh luªn th¶m v· vi»c gi£i b i
to¡n.
2.1. B i to¡n
2.1.1. N¶u b i to¡n
Chóng tæi nghi¶n cùu lîp b i to¡n quy ho¤ch nguy¶n bªc hai vîi v¸ ph£i
r ng buëc ng¨u nhi¶n. Tr÷îc h¸t ta ÷a ra c¡c kþ hi»u:
c ∈ Rn 1 ; b ∈ Rm 1 ; d ∈ Rn 2
A ∈ Rm1 ×n1 ; B ∈ Rm2 ×n1 ; W ∈ Rm2 ×n2
Λ ∈ Rn1 ×n1 ; Γ ∈ Rn2 ×n2 ; h(ω) ∈ Rm2 , ∀ω ∈ Ω.
Lóc n y b i to¡n quy ho¤ch nguy¶n bªc hai vîi v¸ ph£i r ng buëc ng¨u
nhi¶n ÷ñc chuyºn th nh:
(P1 )
max
n1
2
o
x ∧ x + c x + Ew Q(x, w)
T
T
x ∈ X,
trong â X :=
x ∈ Zn+1 |Ax ≤ b
(2.1)
(2.2)
v
Q(x, ω) = max
n1
2
T
T
y Γy + d y
o
(2.3)
17
vîi i·u ki»n
W y ≤ h(ω) − Bx
(2.4)
y ∈ Zn+2 .
(2.5)
B i to¡n (P1) câ thº vi¸t l¤i l
h1
i
1 T
T
T
T
max
x ∧ x + c x + Eω y(ω) Γy(ω) + d y(ω)
2
2
(2.6)
vîi i·u ki»n
x∈X
(2.7)
W y(ω) ≤ h(ω) − Bx, ∀ω ∈ Ω
(2.8)
y(ω) ∈ Rn+2 , ∀ω ∈ Ω.
(2.9)
2.1.2. C¡c gi£ thi¸t ban ¦u
Trong b i to¡n n y chóng tæi ÷a ra c¡c gi£ thi¸t sau ¥y:
A1. Bi¸n ng¨u nhi¶n ω tu¥n theo
quy luªt ph¥n phèi ríi r¤c húu h¤n.
A2. Trong giai o¤n ¦u X = x ∈ Zn+ |Ax ≤ b kh¡c réng v bà ch°n.
A3. Q(x; ξ(ω)) húu h¤n vîi måi x ∈ X v ω ∈ Ω.
A4. Ph¦n tû cõa c¡c ma trªn A, B, W ·u nguy¶n, ngh¾a l
1
A ∈ Zm1 ×n1 ; B ∈ Zm2 ×n1 ; W ∈ Zm2 ×n2 .
2.2. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà
Trong möc n y, tr÷îc h¸t chóng ta tr¼nh b y mët sè k¸t qu£ ¢ bi¸t v·
h m gi¡ trà cõa b i to¡n quy ho¤ch tuy¸n t½nh tham sè. Vi»c chùng minh
c¡c k¸t qu£ n y câ thº xem trong [8].
2.2.1. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà b i to¡n quy ho¤ch
nguy¶n tuy¸n t½nh
Cho G ∈ Zm×n v
sè sau:
γ ∈ Zn ,
x²t lîp b i to¡n quy ho¤ch tuy¸n t½nh tham
18
(P IP ) :
ξ(β) = max γ T x | x ∈ S(β)}
S(β) = {x ∈ Zn+ | Gx ≤ β , vîi β ∈ Rm .
H m ξ(.) : Zm+ → Z l h m gi¡ trà cõa b i to¡n quy ho¤ch nguy¶n tham
sè.
Chóng ta ành ngh¾a
c
opt(β)
= arg max{γ T x|Gx ≤ β, x ∈ Zn+ }
l tªp hñp c¡c ph÷ìng ¡n tèi ÷u cõa b i to¡n quy ho¤ch nguy¶n tham sè
vîi v¸ ph£i cho tr÷îc β . Cho SLP (β) = {x ∈ Rn+|Gx ≤ β} v ξLP (β) =
max{γ T x|x ∈ SLP (β)} l c¡c tªp ph÷ìng ¡n nîi läng tuy¸n t½nh cõa (P IP )
(khæng ái häi bi¸n x nguy¶n).
Sau ¥y l c¡c k¸t qu£ ¢ ÷ñc n¶u trong [8].
M»nh · 2.2.1.1. Ta câ ξ(0) ∈ {0, ∞}. N¸u ξ(0) = ∞ th¼ ξ(β) = ±∞
èi vîi ∀β ∈ Rm. N¸u ξ(0) = 0 th¼ ξ(β) < ∞ èi vîi ∀β ∈ Rm.
B i to¡n vîi ξ(β) = ±∞ l nhúng b i to¡n cì b£n khæng gi£i quy¸t ÷ñc.
V¼ vªy ta th÷íng gi£ thi¸t r¬ng ξ(0) = 0 v ξ(β) < ∞ èi vîi ∀β ∈ Rm.
M»nh · 2.2.1.2. °t gj v γj l¦n l÷ñt l c¡c h» sè cët j cõa ma trªn
G v h» sè cët j cõa h m möc ti¶u γ T x cõa b i to¡n quy ho¤ch nguy¶n
tham sè. Vªy ta câ ξ(gj ) ≥ γj vîi j = 1, ...., n.
M»nh · 2.2.1.3. H m gi¡ trà cõa b i to¡n quy ho¤ch nguy¶n tham sè
khæng gi£m tr¶n Zm.
M»nh · 2.2.1.4. H m gi¡ trà cõa b i to¡n quy ho¤ch nguy¶n tham sè
t«ng tr¶n D = {β ∈ Zm|S(β) 6= ∅}. Do â èi vîi ∀ β1, β2 ∈ D n¸u β1 +
β2 ∈ D th¼
ξ(β1 ) + ξ(β2 ) ≤ ξ(β1 + β2 ).
c
M»nh · 2.2.1.5. N¸u xb ∈ opt(β)
th¼
ξ(Gx) = γ T x
v
ξ(Gx) + ξ(β − Gx) = ξ(Gx) + ξ(G(b
x − x)) = ξ(β),
19
vîi ∀ x ∈ Zn+ sao cho x ≤ xb.
Mët h» qu£ ch½nh cõa m»nh · n y cho chóng ta câ h m gi¡ trà cõa
mët lîp b i to¡n quy ho¤ch nguy¶n tuy¸n t½nh vîi v¸ ph£i r ng buëc ng¨u
nhi¶n.
c
H» qu£ 2.2.1.6. N¸u ξ(gj ) ≥ γj th¼ ∀ β ∈ Zm v n¸u ∀ xb ∈ opt(β),
th¼
x
bj = 0.
2.2.2. C¡c t½nh ch§t cì b£n cõa h m gi¡ trà b i to¡n quy ho¤ch
nguy¶n bªc hai
Cho ma trªn èi xùng Q ∈ Zn×n v²ctì cët c ∈ Zn, β ∈ Zm v ma trªn
k²o theo G ∈ Zm×n. X²t b i to¡n quy ho¤ch nguy¶n bªc hai tham sè
(Parametric Quadratic Integer Programs, vi¸t tt (P QIP )).
(P QIP )
z(β) = max
n1
2
o
x Qx + c x | x ∈ S(β) .
T
T
(2.10)
H m z(.) : Zm+ → Z ÷ñc gåi l h m gi¡ trà cõa b i to¡n quy ho¤ch
nguy¶n bªc hai tham sè.
Chóng ta kþ hi»u
opt(β) = arg max
n1
2
T
T
x Qx + c x | x ∈ S(β)
o
l tªp hñp c¡c ph÷ìng ¡n tèi ÷u cõa b i to¡n quy ho¤ch nguy¶n bªc hai
tham sè vîi v¸ ph£i cho tr÷îc β . Chóng ta công kþ hi»u
zQP (β) = max
n1
2
o
x Qx + c x | x ∈ SLP (β)
T
T
l nîi läng cõa x trong b i to¡n (P QIP ).
Ngo i ra °t qi l cët thù i v qij l ph¦n tû thuëc h ng i cët j cõa ma
trªn Q.
Ti¸p theo ta thu ÷ñc hai k¸t qu£ t÷ìng tü nh÷ t½nh ch§t cõa h m ξ(.)
÷ñc ÷a ra ð M»nh · 2.2.1.3 v M»nh · 2.2.1.4.
M»nh · 2.2.2.1. z(gj ) ≥ cj + 21 qij .
M»nh · 2.2.2.2. z(β) khæng gi£m tr¶n Zm.
20
Tuy nhi¶n, t½nh t«ng cõa h m z(.) khæng kh¡i qu¡t ÷ñc, n¶n ph¦n ti¸p
theo ta ÷a ra i·u ki»n õ º £m b£o t½nh t«ng cõa h m z(.).
M»nh · 2.2.2.3. N¸u Q khæng ¥m th¼ z(β) t«ng tr¶n
D = β ∈ Zm | S(β) 6= ∅ .
Do â vîi ∀ β1, β2 ∈ D, n¸u β1 + β2 ∈ D th¼ z(β1) + z(β2) ≤ z(β1 + β2).
Ng÷ñc l¤i, n¸u Q câ mët ph¦n tû ¥m th¼ s³ câ mët ma trªn G m z(β)
khæng t«ng.
Chùng minh. °t x1 ∈ opt(β1) v x2 ∈ opt(β2) th¼
x1 + x2 ∈ S(β1 + β2 )
v
1
(x1 + x2 )T Q(x1 + x2 ) + cT (x1 + x2 )
2
1
1 T
= c1 Qx1 + xT2 Qx2 + xT1 Qx2 + cT x1 + cT x2
2
2
= z(β1 ) + z(β2 ) + xT1 Qx2 .
z(β1 + β2 ) ≥
(2.11)
i·u â câ ngh¾a l z(β1 + β2) ≥ z(β1) + z(β2), khi qij ≥ 0 ∀ i, j.
B¥y gií n¸u tçn t¤i i, j m qij < 0, khi â ta s³ x²t hai tr÷íng hñp:
+ N¸u i = j trong â qii < 0, x²t tªp hñp
X
S(β) = x ∈ Zn+
xk ≤ β1 , xi ≤ β2 , −xi ≤ β3 .
(2.12)
k: k6=i
°t β = (0, 1, −1)T . èi vîi måi c cho tr÷îc, ta câ z(β) = ci + 21 qii v
z(2β) = 2ci + 2qii = z(β) + z(β) + qii < z(β) + z(β).
M°t kh¡c, n¸u i 6= j v qij < 0. X²t tªp hñp
S(β) =
n
x ∈ Z+
X
xk ≤ β1 , xi ≤ β2 , −xi ≤ β3 , xj ≤ β4 , −xj ≤ β5 .
k:k6=i,k6=j
(2.13)
- Xem thêm -