Tài liệ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

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 l­p 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 s­c 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è g­ng 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è ch­c ch­n ; 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 kh­c ; 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 t­c 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 ch­c ch­n 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 t­t (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)