Báo cáo nghiên cứu khoa học: "Một số kết quả về sự hiệu chỉnh đầy đủ và hiệu chỉnh nửa đầy đủ trong các phương pháp xấp xỉ giải bài toán quy hoạch ngẫu nhiên."

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

79
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả: 3. Dương Xuân Giáp, Một số kết quả về sự hiệu chỉnh đầy đủ và hiệu chỉnh nửa đầy đủ trong các phương pháp xấp xỉ giải bài toán quy hoạch ngẫu nhiên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Một số kết quả về sự hiệu chỉnh đầy đủ và hiệu chỉnh nửa đầy đủ trong các phương pháp xấp xỉ giải bài toán quy hoạch ngẫu nhiên."

Mét sè kÕt qu¶ vÒ sù hiÖu chØnh ®Çy ®ñ vµ hiÖu chØnh nöa ®Çy ®ñ trong c¸c ph¬ng ph¸p xÊp xØ gi¶i bµi to¸n quy ho¹ch ngÉu nhiªn D¬ng Xu©n Gi¸p (a) Tãm t¾t. Trong bµi b¸o nµy, chóng t«i nghiªn cøu cÊu tróc cña ma trËn hiÖu chØnh ®Çy ®ñ, ma trËn hiÖu chØnh nöa ®Çy ®ñ, t×m c¸c mèi quan hÖ gi÷a chóng vµ ®a ra ®iÒu kiÖn cÇn vµ ®ñ ®Ó mét ma trËn hiÖu chØnh nöa ®Çy ®ñ lµ ma trËn hiÖu chØnh ®Çy ®ñ. 1 Giíi thiÖu LÜnh vùc tèi u hiÖn nay ®îc c¸c nhµ To¸n häc quan t©m nghiªn cøu c¶ trong lý thuyÕt còng nh trong thùc hµnh øng dông, chñ yÕu lµ bµi to¸n tèi u ngÉu nhiªn. §Æc biÖt, nhãm nghiªn cøu cña Chen mÊy n¨m gÇn ®©y tËp trung nghiªn cøu vµ c«ng bè nhiÒu bµi b¸o vÒ c¸c kÕt qu¶ thu ®îc c¶i tiÕn c¸c ph¬ng ph¸p xÊp xØ gi¶i bµi to¸n tèi u ngÉu nhiªn 2 giai ®o¹n vµ chøng tá tÇm quan träng c¶ trong lý thuyÕt vµ thùc tiÔn tÝnh to¸n, øng dông. Chen vµ c¸c céng sù chØ ra r»ng nh÷ng quy t¾c quyÕt ®Þnh tuyÕn tÝnh cã thÓ dÉn tíi nh÷ng trêng hîp kh«ng kh¶ thi cho bµi to¸n tèi u ngÉu nhiªn víi sù hiÖu chØnh ®Çy ®ñ. ViÖc nµy ®ßi hái chóng ta lµm mÞn quy t¾c quyÕt ®Þnh tuyÕn tÝnh vµ tõ ®ã Chen vµ nhãm nghiªn cøu cña m×nh ®· ®Ò xuÊt hai phÐp xÊp xØ. XÊp xØ ®Çu tiªn lµ "nh÷ng quy t¾c quyÕt ®Þnh tuyÕn tÝnh lÖch", nã phï hîp cho bµi to¸n tèi u ngÉu nhiªn víi c¸c biÕn hiÖu chØnh nöa ®Çy ®ñ. XÊp xØ thø hai lµ "nh÷ng quy t¾c quyÕt ®Þnh tuyÕn tÝnh c« lËp", nã phï hîp cho bµi to¸n tèi u ngÉu nhiªn víi hiÖu chØnh tæng qu¸t. §iÓm ®Æc biÖt liªn hÖ gi÷a hai quy t¾c nµy lµ chóng cã thÓ kÕt hîp víi nhau t¹o ra "quy t¾c quyÕt ®Þnh tuyÕn tÝnh lÖch-c« lËp" vµ nã xÊp xØ tèt h¬n (mÞn h¬n) c¶ xÊp xØ tuyÕn tÝnh vµ xÊp xØ tuyÕn tÝnh lÖch. Chen vµ c¸c céng sù chØ ra r»ng ma trËn hiÖu chØnh ®Çy ®ñ lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ (xem [1]). C©u hái chóng t«i ®Æt ra lµ: Víi ®iÒu kiÖn nµo th× ma trËn hiÖu chØnh nöa ®Çy ®ñ lµ ma trËn hiÖu chØnh ®Çy ®ñ? ThiÕt lËp ®iÒu kiÖn cÇn vµ ®ñ ®Ó ma trËn hiÖu chØnh nöa ®Çy ®ñ lµ ma trËn hiÖu chØnh ®Çy ®ñ. Tr¶ lêi triÖt ®Ó c©u hái nµy chÝnh lµ néi dung chÝnh cña bµi b¸o. KÕt qu¶ nµy sÏ ®em tíi hai ý nghÜa quan träng, bëi v×: NhËn bµi ngµy 25/9/2009. Söa ch÷a xong 26/11/2009. 1
Mét lµ, ®Þnh nghÜa ma trËn hiÖu chØnh ®Çy ®ñ khã ®Ó kiÓm tra còng nh khã ®Ó thiÕt lËp so víi ®Þnh nghÜa ma trËn hiÖu chØnh nöa ®Çy ®ñ. Hai lµ, bÊt kú bµi to¸n quy ho¹ch ngÉu nhiªn víi hiÖu chØnh ®Çy ®ñ lµ chÊp nhËn ®îc ®èi víi nh÷ng quy t¾c quyÕt ®Þnh tuyÕn tÝnh lÖch, tuy nhiªn quy t¾c quyÕt ®Þnh tuyÕn tÝnh lÖch vÉn cã thÓ chÊp nhËn ®îc nÕu thiÕu sù hiÖu chØnh ®Çy ®ñ - ®ã lµ c¸c biÕn hiÖu chØnh nöa ®Çy ®ñ nhng kh«ng hiÖu chØnh ®Çy ®ñ, c©u hái chóng ta ®Æt ra ë ®©y lµ ®iÒu ®ã x¶y ra khi nµo? Tõ ®ã, chóng t«i chØ ra ®îc ®iÒu kiÖn cÇn vµ ®ñ ®Ó mét ma trËn hiÖu chØnh nöa ®Çy ®ñ nhng kh«ng lµ ma trËn hiÖu chØnh ®Çy ®ñ. 2 Mét sè kh¸i niÖm, tÝnh chÊt §Þnh nghÜa. Ma trËn W cÊp m × n ®îc gäi lµ ma trËn hiÖu chØnh ®Çy ®ñ, nÕu 2.1 víi mçi vect¬ cét t cÊp m × 1 ®Òu tån t¹i vect¬ cét w = [w1 w2 . . . wn ]T cÊp n × 1 sao cho wj ≥ 0, ∀j = 1, ..., n vµ Ww = t (xem [1]). Ma trËn W cÊp m × n ®îc gäi lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ, nÕu tån t¹i vect¬ cét r = [r1 r2 . . . rn ]T cÊp n × 1 sao cho rj > 0, ∀j = 1, ..., n vµ Wr = 0. NhËn xÐt. Ta gäi W1 , W2 , . . . , Wn lµ c¸c vect¬ cét cña ma trËn W (ma trËn W lµ ma trËn hiÖu chØnh ®Çy ®ñ hoÆc lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ). Tõ §Þnh nghÜa 2.1 suy ra hÖ c¸c vect¬ cét {W1 , W2 , . . . , Wn } lµ phô thuéc tuyÕn tÝnh. Ta suy ra rank(W) ≤ min{m, n − 1}. MÖnh ®Ò. Trong kh«ng gian vect¬ k-chiÒu Rk , mét hÖ vect¬ {−1 , −2 , . . . , −s } cã →→ → 2.2 vv v h¹ng bÐ h¬n k th× ta lu«n cã thÓ bæ sung mét vect¬ vs+1 −→ ®Ó − rank {− , →, . . . , −→} = rank {− , − , . . . , − } + 1, →− v− →→ → v1 v2 v1 v2 vs s+1 nghÜa lµ vect¬ −→ kh«ng thuéc kh«ng gian vect¬ con sinh bëi hÖ vect¬ v− − , →, . . . , − →− → v1 v2 vs s+1 {− , − , . . . , − } →→ → v1 v2 vs MÖnh ®Ò. Ma trËn hiÖu chØnh ®Çy ®ñ lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ (xem [1]). 2.3 Tuy nhiªn, ®iÒu ngîc l¹i nãi chung kh«ng ®óng. VÝ dô. ∗ Ma trËn W lµ ma trËn kh«ng th× W lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ, bëi v× víi mäi vect¬ cét r = [r1 r2 . . . rn ]T cÊp n × 1 sao cho rj > 0, ∀j = 1, ..., n ®Òu tho¶ m·n Wr = 0. Tuy nhiªn, W l¹i kh«ng ph¶i lµ mét ma trËn hiÖu chØnh ®Çy ®ñ, v× ta chØ cÇn chän vect¬ cét t cÊp m × 1 kh¸c kh«ng th× ®Òu kh«ng x¶y ra ®¼ng thøc Ww = t, víi mäi c¸ch chän vect¬ cét w.
∗ Hai ma trËn sau ®©y còng ®îc c¸c t¸c gi¶ Chen vµ c¸c céng sù sö dông trong m« h×nh tÝnh to¸n minh ho¹ cho xÊp xØ gi¶i bµi to¸n tèi u ngÉu nhiªn cña m×nh (xem [2]), ®©y lµ hai ma trËn hiÖu chØnh nöa ®Çy ®ñ nhng kh«ng ph¶i lµ ma trËn hiÖu chØnh ®Çy ®ñ (b¹n ®äc cã thÓ trùc tiÕp kiÓm tra dùa vµo §Þnh nghÜa 2.1): 00 −1 1 W1 = ; W2 = . II 1 −1 Tuy nhiªn, nÕu ma trËn W cã cÊu tróc phøc t¹p th× viÖc dïng §Þnh nghÜa 2.1 ®Ó kiÓm tra W cã ph¶i lµ ma trËn hiÖu chØnh ®Çy ®ñ hay kh«ng, hoÆc thiÕt lËp ma trËn hiÖu chØnh ®Çy ®ñ lµ rÊt khã. Nh÷ng kÕt qu¶ chóng t«i thu ®îc sau ®©y ®· gi¶i quyÕt nh÷ng khã kh¨n nµy. 3 KÕt qu¶ chÝnh §Þnh lý. Ma trËn W cÊp m × n lµ ma trËn hiÖu chØnh ®Çy ®ñ th× m < n vµ ma 3.1 trËn W cã h¹ng b»ng m. Chøng minh. Gäi W1 , W2 , . . . , Wn lµ c¸c vect¬ cét cña ma trËn W, ®©y chÝnh lµ c¸c vect¬ trong kh«ng gian vect¬ Rm . Tríc tiªn, ta chøng minh m < n. ThËt vËy, gi¶ sö ngîc l¹i: Trêng hîp1: m > n. Khi ®ã, rank{W1 , W2 , . . . , Wn } < m. Theo MÖnh ®Ò 2.2, tån t¹i vect¬ cét t ∈ Rm ®Ó rank{W1 , W2 , . . . , Wn , t} = rank{W1 , W2 , . . . , Wn } + 1, nghÜa lµ t kh«ng thuéc kh«ng gian vect¬ W1 , W2 , . . . , Wn sinh bëi hÖ {W1 , W2 , . . . , Wn }. Tõ ®ã suy ra kh«ng tån t¹i vect¬ cét w ®Ó Ww = t. Nãi riªng, W kh«ng lµ ma trËn hiÖu chØnh ®Çy ®ñ, ta gÆp mét m©u thuÉn. Trêng hîp 2: m = n vµ rank(W) < m. LËp luËn hoµn toµn t¬ng tù trêng hîp 1. Trêng hîp 3: m = n vµ rank(W) = m. Khi ®ã, ma trËn W kh¶ nghÞch, suy ra hÖ {W1 , W2 , . . . , Wn } lµ c¬ së cña kh«ng gian vect¬ Rm . Theo gi¶ thiÕt, W lµ ma trËn hiÖu chØnh ®Çy ®ñ nªn ¸p dông MÖnh ®Ò 2.3 ta suy ra W lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ, nghÜa lµ tån t¹i vect¬ cét r = [r1 r2 . . . rn ]T cÊp n × 1 sao cho rj > 0, ∀j = 1, ..., n vµ Wr = 0 hay r1 W1 + r2 W2 + · · · + rn Wn = 0. §iÒu nµy m©u thuÉn víi hÖ {W1 , W2 , . . . , Wn } lµ c¬ së.
B©y giê ta chøng minh W cã h¹ng b»ng m. Gi¶ sö ngîc l¹i, ma trËn W cã h¹ng bÐ h¬n m, nghÜa lµ rank{W1 , W2 , . . . , Wn } < m. ¸p dông MÖnh ®Ò 2.2 suy ra tån t¹i vect¬ cét t ∈ Rm ®Ó rank{W1 , W2 , . . . , Wn , t} = rank{W1 , W2 , . . . , Wn } + 1, nghÜa lµ t kh«ng thuéc kh«ng gian vect¬ W1 , W2 , . . . , Wn sinh bëi hÖ {W1 , W2 , . . . , Wn }. Ta suy ra kh«ng tån t¹i vect¬ cét w ®Ó Ww = t. Nãi riªng, W kh«ng lµ ma trËn hiÖu chØnh ®Çy ®ñ, ta gÆp mét m©u thuÉn. 3.2 §Þnh lý. Cho tríc hai sè tù nhiªn m, n. Khi ®ã, lu«n tån t¹i ma trËn hiÖu chØnh nöa ®Çy ®ñ W cã cÊp m × n. H¬n n÷a, nÕu n > 1 th× víi sè tù nhiªn k bÊt k× sao cho k ≤ min{m, n − 1}, lu«n tån t¹i ma trËn hiÖu chØnh nöa ®Çy ®ñ W cã cÊp m × n vµ cã rank(W) = k . Chøng minh. ∗ NÕu n = 1 th× ta chän ma trËn W lµ ma trËn cét kh«ng (chÝnh lµ vect¬ kh«ng trong kh«ng gian vect¬ Rm ). Khi ®ã, ma trËn W tho¶ m·n ®iÒu kiÖn lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ. ∗ NÕu n > 1 th× ta chän tuú ý c¸c vect¬ cét W1 , W2 , . . . , Wn−1 ∈ Rm cã h¹ng b»ng k vµ c¸c sè thùc d¬ng tuú ý rj > 0, ∀j = 1, ..., n. Ta ®Æt r1 r2 rn−1 Wn−1 ∈ Rm Wn = − W1 − W2 − · · · − (1) rn rn rn ⇒ r1 W1 + r2 W2 + · · · + rn Wn = 0 (2) Gäi W lµ ma trËn gåm c¸c cét W1 , W2 , . . . , Wn . Khi ®ã, c«ng thøc (2) cho ta Wr = 0. Râ rµng ma trËn W cã cÊp m × n. Do hÖ vect¬ cét W1 , W2 , . . . , Wn−1 ∈ Rm cã h¹ng b»ng k vµ vect¬ cét Wn biÓu thÞ tuyÕn tÝnh qua hÖ c¸c vect¬ W1 , W2 , . . . , Wn−1 nªn suy ra rank(W) = k. Nh vËy, ma trËn W x©y dùng nh trªn lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ cã cÊp m × n vµ cã h¹ng b»ng k. 3.3 §Þnh lý. Gi¶ sö ma trËn W cã cÊp m × n (m < n), cã h¹ng b»ng m, tho¶ m·n ®iÒu kiÖn tån t¹i vect¬ cét r = [r1 r2 . . . rn ]T cÊp n × 1, víi rj ≥ 0, ∀j = 1, ..., n sao cho Wr = 0 vµ tËp c¸c vect¬ cét t¬ng øng víi c¸c hÖ sè rj > 0 cña ma trËn W tån t¹i mét hÖ c¸c vect¬ cét t¹o thµnh c¬ së cña kh«ng gian vect¬ Rm . Khi ®ã, W lµ ma trËn hiÖu chØnh ®Çy ®ñ. Chøng minh. Gäi W1 , W2 , . . . , Wn lµ c¸c vect¬ cét cña ma trËn W. Kh«ng mÊt tÝnh tæng qu¸t, ta gi¶ sö W1 , W2 , . . . , Wm lµ hÖ c¸c cét c¬ së t¬ng øng víi r1 > 0, r2 > 0, . . . , rm > 0. Theo gi¶ thiÕt th× r1 W1 + r2 W2 + · · · + rn Wn = 0 (3) ⇔ r1 W1 + r2 W2 + · · · + rm Wm = −rm+1 Wm+1 − rm+2 Wm+2 − · · · − rn Wn . (4)
Víi mäi vect¬ cét t cÊp m × 1 th× t biÓu diÔn ®îc qua c¬ së {W1 , W2 , . . . , Wm } lµ: t = t1 W1 + t2 W2 + · · · + tm Wm . (5) (∗) NÕu tj ≥ 0, j = 1, ..., m th× ta chän wj = tj , j = 1, ..., m (6) wj = 0, j = m + 1, ..., n ⇒ t = w 1 W1 + w 2 W2 + · · · + w n Wn , hay Ww = t (wj ≥ 0, j = 1, ..., n), ®©y chÝnh lµ ®iÒu ph¶i chøng minh. (∗) NÕu tr¸i l¹i, ∃tj < 0. Do rj > 0, j = 1, ..., m nªn tån t¹i min{ r t | tj < 0, j = j j 1, m}. Kh«ng mÊt tÝnh tæng qu¸t, ta gi¶ sö tj tm min{ | tj < 0, j = 1, ..., m = . (7) rj rm V× tm < 0, rm > 0 nªn r < 0. Ta ®Æt t m m tm wj = tj − .rj , (j = 1, ..., m) rm (8) tj tm ⇔ wj = rj − , (j = 1, ..., m) . rj rm (9) +) NÕu tj < 0 th× tõ c«ng thøc (7) vµ (9) suy ra tj tm tj tm ≥ ⇔ − ≥ 0 ⇒ wj ≥ 0. rj rm rj rm +) NÕu tj > 0 th× do r < 0 nªn t m m tm wj = tj − .rj ≥ 0. rm Tãm l¹i, theo c¸ch ®Æt ë c«ng thøc (8) th× wj ≥ 0, j = 1, ..., m. (10)
Tõ c«ng thøc (8) suy ra ®îc tm tj = w j + .rj , j = 1, .., m. (11) rm Thay tj trong c«ng thøc (11) vµo c«ng thøc (5) vµ sö dông c«ng thøc (4) ta cã: m t= tj .Wj j =1 m tm = wj + .rj Wj rm j =1 m−1 tm = wj + .rj Wj + tm .Wm rm j =1 m−1 m−1 tm tm = wj .Wj + .rj Wj + rm .Wm rm rm j =1 j =1 m−1 m tm = wj .Wj + rj .Wj rm j =1 j =1 m−1 m tm = wj .Wj + rj .Wj rm j =1 j =1 m−1 n tm = wj .Wj + − rj .Wj rm j =1 j =m+1 m−1 n tm = wj .Wj + − rj .Wj . rm j =1 j =m+1 B©y giê ta ®Æt tm wj = − .rj , j = 1, ..., n (12) rm Do tm < 0, rm > 0, rj ≥ 0 nªn ta suy ra wj ≥ 0, j = m + 1, ..., n. (13) Do ®ã, víi wj x¸c ®Þnh ë c«ng thøc (8) vµ c«ng thøc (??), ®ång thêi wm = 0 nªn ta cã n t= wj .Wj (wj ≥ 0, j = 1, ..., n) , j =1
hay Ww = t, cã nghÜa lµ W lµ ma trËn hiÖu chØnh ®Çy ®ñ. HÖ qu¶. Ma trËn W cÊp m × n (m < n), cã h¹ng b»ng m. Khi ®ã, W lµ ma trËn 3.4 hiÖu chØnh ®Çy ®ñ khi vµ chØ khi W lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ. Chøng minh. ∗ §iÒu kiÖn cÇn: V× W lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ nªn theo §Þnh nghÜa 2.1 suy ra ma trËn W tho¶ m·n tÊt c¶ gi¶ thiÕt cña §Þnh lý 3.3 nªn ¸p dông §Þnh lý 3.3 suy ra W lµ ma trËn hiÖu chØnh ®Çy ®ñ. ∗ §iÒu kiÖn ®ñ: Suy trùc tiÕp tõ MÖnh ®Ò 2.3. VÝ dô. Ma trËn W = [I, -I] cÊp n × 2n lµ ma trËn hiÖu chØnh ®Çy ®ñ (còng lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ), trong ®ã I lµ ma trËn ®¬n vÞ cÊp n. §iÒu nµy chóng ta cã thÓ suy ra ngay tõ §Þnh lý 3.3 vµ HÖ qu¶ 3.4 víi vect¬ cét r ë ®©y lµ r = [1 1 . . . 1]T . HoÆc chóng ta còng cã thÓ kiÓm tra trùc tiÕp dùa vµo §Þnh nghÜa 2.1. Ma trËn nµy ngêi ta gäi lµ ma trËn hiÖu chØnh ®¬n. 3.5 HÖ qu¶. Cho ma trËn W cÊp m × n lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ. Khi ®ã, ma trËn W lµ ma trËn hiÖu chØnh ®Çy ®ñ khi vµ chØ khi m < n vµ ma trËn W cã h¹ng b»ng m. Chøng minh. ∗ §iÒu kiÖn cÇn: Suy trùc tiÕp tõ HÖ qu¶ 3.4. ∗ §iÒu kiÖn ®ñ: Suy trùc tiÕp tõ §Þnh lý 3.1. Nhn xt. Tõ HÖ qu¶ 3.5, ta cã thÓ thiÕt lËp ma trËn hiÖu chØnh ®Çy ®ñ th«ng qua viÖc thiÕt lËp ma trËn hiÖu chØnh nöa ®Çy ®ñ b»ng c¸ch sö dông §Þnh lý 3.2 víi viÖc chän k = m. 3.6 Bµi to¸n quy ho¹ch ngÉu nhiªn víi rµng buéc tuyÕn tÝnh. Bµi to¸n quy ho¹ch ngÉu nhiªn cã rµng buéc tuyÕn tÝnh lµ bµi to¸n cã d¹ng min{f (x)} Ax = b víi ®iÒu kiÖn: (14) x ≥ 0, trong ®ã c¸c ma trËn x = [x1 x2 . . . xn]T cÊp n × 1, b = [b1 b2 . . . bm]T cÊp m × 1, A = [aij ] cÊp m × n, vµ c¸c phÇn tö cña c¸c ma trËn A, b; hµm môc tiªu f ®Òu phô thuéc vµo c¸c yÕu tè ngÉu nhiªn.
HÖ qu¶. Cho ma trËn A cÊp m × n víi m ≥ n, hoÆc m < n nhng ma trËn A cã 3.7 h¹ng bÐ h¬n m. Khi ®ã, tån t¹i c¸ch chän ma trËn cét b sao cho tËp ph¬ng ¸n {x | Ax = b, x ≥ 0} cña bµi to¸n quy ho¹ch ngÉu nhiªn víi rµng buéc tuyÕn tÝnh (14) lµ rçng. Chøng minh. Ta sÏ chøng minh b»ng ph¬ng ph¸p ph¶n chøng. Gi¶ sö ngîc l¹i, víi mäi c¸ch chän vect¬ cét b th× tËp ph¬ng ¸n {x | Ax = b, x ≥ 0} cña bµi to¸n quy ho¹ch ngÉu nhiªn lµ kh¸c rçng, nghÜa lµ ma trËn A lµ ma trËn hiÖu chØnh ®Çy ®ñ. Theo §Þnh lý 3.1 th× ma trËn A cÊp m × n cã m < n vµ ma trËn A cã h¹ng b»ng m, ta gÆp mét m©u thuÉn. 3.8 §Þnh lý. Ma trËn W cÊp m × n lµ ma trËn hiÖu chØnh ®Çy ®ñ khi vµ chØ khi " Víi sè thùc α bÊt kú, víi mçi vect¬ cét t cÊp m × 1 ®Òu tån t¹i vect¬ cét w = [w1 w2 . . . wn ]T víi c¸c biÕn bÞ chÆn díi bëi α, tøc lµ wj ≥ α, j = 1, ..., n tho¶ m·n Ww = t". Chøng minh. Gi¶ sö W lµ ma trËn hiÖu chØnh ®Çy ®ñ. Khi ®ã, víi mçi sè thùc α vµ víi mçi vect¬ cét t cÊp m × 1, ta ®Æt t∗ = t − Wα∗ , trong ®ã α∗ = [α α . . . α]T lµ vect¬ cét cÊp n × 1. Theo ®Þnh nghÜa ma trËn hiÖu chØnh ®Çy ®ñ, tån t¹i vect¬ cét y = [y1 y2 . . . yn ]T sao cho yj ≥ 0, j = 1, ..., n tho¶ m·n Wy = t∗ , hay Wy = t - Wα∗ , ®iÒu nµy t¬ng ®¬ng víi W(y + α∗ ) = t. §Æt w = y + α∗ = [w1 w2 . . . wn ]T víi wj = yj + α ≥ α th× ta cã Ww = t tho¶ m·n c¸c biÕn bÞ chÆn díi bëi α. Ngîc l¹i, ta dÔ dµng cã ®iÒu ph¶i chøng minh víi viÖc chän α = 0. 3.9 §Þnh lý. Ma trËn W cÊp m × n lµ ma trËn hiÖu chØnh ®Çy ®ñ khi vµ chØ khi " Víi sè thùc α bÊt kú, víi mçi vect¬ cét t cÊp m × 1 ®Òu tån t¹i vect¬ cét w = [w1 w2 . . . wn ]T víi c¸c biÕn bÞ chÆn trªn bëi α, tøc lµ wj ≤ α, j = 1, ..., n tho¶ m·n Ww = t". Chøng minh. Gi¶ sö W lµ ma trËn hiÖu chØnh ®Çy ®ñ. Khi ®ã, víi mçi sè thùc α vµ víi mçi vect¬ cét t cÊp m × 1, ta ®Æt t∗ = −t + Wα∗ , trong ®ã α∗ = [α α . . . α]T lµ vect¬ cét cÊp n × 1. Do W lµ ma trËn hiÖu chØnh ®Çy ®ñ nªn tån t¹i vect¬ cét y = [y1 y2 . . . yn ]T sao cho yj ≥ 0, j = 1, ..., n tho¶ m·n Wy = t∗ , hay Wy = - t + Wα∗ , ®iÒu nµy t¬ng ®¬ng víi W(−y + α∗ ) = t. §Æt w = - y + α∗ = [w1 w2 . . . wn ]T víi wj = −yj + α ≤ α, ta cã Ww = t tho¶ m·n c¸c biÕn bÞ chÆn trªn bëi α. Ngîc l¹i, ta chän α = 0. Víi mçi vect¬ cét t cÊp m × 1, ta ®Æt t∗ = −t. Theo gi¶ thiÕt, tån t¹i vect¬ cét x = [x1 x2 . . . xn ]T víi c¸c biÕn bÞ chÆn trªn bëi 0, tøc lµ xj ≤ 0, j = 1, ..., n tho¶ m·n Wx = t∗ , nghÜa lµ Ww = t víi w = - x = [w1 w2 . . . wn ]T sao cho wj = −xj ≥ 0, j = 1, ..., n. Theo §Þnh nghÜa 2.1, ma trËn W lµ ma trËn hiÖu chØnh ®Çy ®ñ.
Tµi liÖu tham kh¶o [1] Xin Chen, Melvyn Sim, Peng Sun and Jiawei Zhang, A Linear Decision-Based Approximation - Approach to Stochastic Programming, Operations Research, Vol.56, No.2, March-April 2008, pp. 344-357. [2] Xin Chen, Melvyn Sim, Peng Sun and Jiawei Zhang, A Tractable Approximation of Stochastic Programming via Robust Optimization, Working paper, University of Illinois at Urban-Champaign, February 2006. summary Some results on complete recourse and semicomplete recourse in approximately methods to solving stochastic optimization problems In this paper, we study the structure of a complete recourse matrix and a semicom- plete recourse matrix; consider the relationships between a complete recourse matrix and a semicomplete recourse matrix, and give an necessary and sufficient condition that a semicomplete recourse matrix is a complete recourse matrix. (a) cao häc 15, chuyªn ngµnh lý thuyÕt x¸c suÊt vµ thèng kª to¸n häc, trêng ®¹i häc vinh.