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.

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.
Nội dung trích xuất từ tài liệu:
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«ngbè 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¸ntè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ùctiÔ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 ®ÞnhtuyÕ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Éunhiª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 ®ÞnhtuyÕ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µito¸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µito¸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¹ora 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Ønhnö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ÖuchØnh nöa ®Çy ®ñ lµ ma trËn hiÖu chØnh ®Çy ®ñ? ThiÕt lËp ®iÒu kiÖn cÇn vµ ®ñ ®Ó matrË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µychÝ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 ®ÞnhtuyÕ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¸cbiÕ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Õu2.1ví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 saocho 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µ matrËn hiÖu chØnh ®Çy ®ñ hoÆc lµ ma trËn hiÖu chØnh nöa ®Çy ®ñ). Tõ §Þnh nghÜa 2.1suy 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 vh¹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+1nghÜ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 ®Ç ...