Thuật toán gần đúng cho bài toán tối ưu tổ hợp - ThS. Nguyễn Mạnh Hùng

Nhằm giúp các bạn chuyên ngành Toán học có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu, mời các bạn cùng tham khảo nội dung bài viết "Thuật toán gần đúng cho bài toán tối ưu tổ hợp" dưới đây. Nội dung bài viết trình bày về thuật toán gần đúng, ứng dụng thuật toán gần đúng,...
Nội dung trích xuất từ tài liệu:
Thuật toán gần đúng cho bài toán tối ưu tổ hợp - ThS. Nguyễn Mạnh HùngThuËt to¸n -gÇn ®óng cho bµi to¸n tèi u tæ hîp Ths. NguyÔn M¹nh Hïng - Khoa CNTT - §H Thuû LîiI. Giíi thiÖu.Bµi to¸n t×m cùc ®¹i hoÆc cùc tiÓu cña th¬ng hai hµm thùc trªn tËp D cña kh«ng gian Rn ®îc gäi lµbµi to¸n quy ho¹ch ph©n tuyÕn. Bµi to¸n quy ho¹ch ph©n tuyÕn cã nhiÒu øng dông trong thùc tÕnhng rÊt khã t×m nghiÖm chÝnh x¸c, v× thÕ ngêi ta quan t©m ®Õn viÖc x©y dùng c¸c thuËt gi¶i gÇn®óng. Mét thuËt to¸n ®îc gäi lµ -gÇn ®óng nÕu nã lu«n cho lêi gi¶i -tèi u tøc lµ lêi gi¶i cã saisè t¬ng ®èi so víi gi¸ trÞ tèi u bÞ chÆn trªn bëi mét h»ng sè d¬ng . XÐt bµi to¸n quy ho¹ch rêi r¹c ph©n tuyÕn sau: a0  axP: Max { R(x)= , xD } b0  bxtrong ®ã a0, b0 thuéc R, a = (a1,....,an)Rn, b=(b1,...,bn)Rn, x=(x1,x2,...,xn) Rn, D lµ tËp con h÷u h¹nkh¸c rçng cña Rn.Ta cã c¸c gi¶ thiÕt sau ®©y: 1) bx 0  xD. 2) b0 >0 vµ a0  0 3) R(x) > a0/b0 víi mét x D nµo ®ã.Gi¶ thiÕt 1) vµ 2) ®¶m b¶o r»ng mÉu sè cña R(x) lµ d¬ng trªn D vµ gi¶ thiÕt 3) chØ ra r»ng gi¸ trÞ tèiu * cña bµi to¸n P lµ lín h¬n a0/b0.XÐt bµi to¸n phô Q() víi tham sè  : Q() : max{ (a-b)x : xD}.Khi ®ã bµi to¸n P lµ t¬ng ®¬ng víi viÖc t×m =* sao cho Q(*) cã gi¸ trÞ tèi u *b0 - a0 (trongtrêng hîp nµy * chÝnh lµ gi¸ trÞ tèi u cña bµi to¸n P vµ [3] ®· giíi thiÖu thuËt to¸n gi¶i Q(*) mµkh«ng cÇn biÕt tríc * ).Sau ®©y ta sÏ nªu ra mét thuËt to¸n gäi lµ Frac() cho P khi ®· biÕt mét thuËt to¸n PARA(,) t×mnghiÖm -gÇn ®óng cho bµi to¸n Q(). Gäi * vµ () lµ gi¸ trÞ gi¸ trÞ tèi u cña P vµ Q() t¬ng øng.C¸c tÝnh chÊt cña bµi to¸n bæ trî :TÝnh chÊt 1. () lµ liªn tôc, tuyÕn tÝnh tõng khóc, kh«ng t¨ng vµ låi.TÝnh chÊt 2. () > b0-a0 nÕu vµ chØ nÕu  < *, () =b0-a0 nÕu vµ chØ nÕu =*, () < b0-a0 nÕuvµ chØ nÕu >*.§Þnh lý 1. Tån t¹i mét kho¶ng [e,f] sao cho * [e,f] vµ () > 0 [e,f].Chøng minh. V× tÝnh liªn tôc cña () nªn chØ cÇn chøng minh (*) > 0 V× b0 >0 vµ bx 0, nªn tõgi¶ thiÕt (3 ) suy ra : (a-(a0/b0 )b)x > 0 víi mét x nµo ®ã thuéc D,  (a0/b0 ) >0. 1V× vËy ta cã (a0/b0 )b0 -a0 =0 < (a0/b0 )  theo tÝnh chÊt 2 th× : a0/b0 0.TiÕp theo, thay cho viÖc gi¶i chÝnh x¸c P, ta t×m mét nghiÖm gÇn ®óng cña P b»ng c¸ch sö dôngnghiÖm - gÇn ®óng x cña Q(). §Æt  =(a-b)x. Khi ®ã tõ ®Þnh nghÜa vÒ nghiÖm - gÇn ®óng tacã :   () vµ (()- ) /()  .Chó ý cã thÓ gi¶ sö 1 mµ kh«ng mÊt tÝnh tæng qu¸t b»ng c¸ch h¹n chÕ nh÷ng gi¸ trÞ  tho¶ m·n() >0 vµ  >0. V× vËy : (1-)()   () vµ   ()   / (1-).KÕt hîp víi tÝnh chÊt 2, ta suy ra :§Þnh lý 2. (A)  > b0-a0 kÐo theo  < *, (B)  < (1-)(b0-a0 ) kÐo theo  >*, vµ(C)Trong trêng hîp (1-)(b0-a0 )    b0-a0 ta kh«ng thÓ kh¼ng ®Þnh ®îc * >  hay *  .H×nh vÏ díi ®©y m« t¶ c¸c trêng hîp (A),(B) vµ (C) cña ®Þnh lý. v( v() b0-a0 b0-a0) (A) (A) (C) (C)  (B) a0/b0  II. ThuËt to¸n -gÇn ®óng.Trong phÇn nµy, chóng ta m« t¶ thuËt to¸n gÇn ®óng gi¶i P cã sö dông PARA(,). NÕu gi¸ trÞ -gÇn®óng  cña Q() víi  ®· cho tho¶ m·n ®iÒu kiÖn (C) cña ®Þnh lý 2 , chóng ta cã thÓ hiÓu  lµ gÇnvíi *. V× vËy môc tiªu cña chóng ta lµ t×m mét  tho¶ m·n ®iÒu kiÖn (C) cña ®Þnh lý 2. Ta thùc hiÖnPARA(*,) mµ kh«ng biÕt * theo ph¬ng ph¸p Megiddo ë [2].Tõ ®Þnh lý 1, tån t¹i mét kho¶ng [e,f] sao cho * [e,f] vµ () >0 [e,f].Gi¶ sö [e,f] cã s¼n tõ ®Çu, ta ¸p dông PARA(*,) mµ chØ cÇn biÕt * [e,f].Trong qu¸ tr×nh ¸p dông PARA(*,), [e,f] tù ®éng gi¶m nhng vÉn gi÷ tÝnh chÊt * [e,f]. D÷ liÖucña Q() cho kho¶ng khëi ®Çu [e,f] lµ ai-bi, i=1,2,...n. TÊt c¶ ®Òu tuyÕn tÝnh theo . Nã sÏ ®îcchøng minh b»ng qui n¹p r»ng tÊt c¶ c¸c d÷ liÖu cÇn thiÕt ®Ó thùc hiÖn PARA(*, ) cho kho¶ng hiÖnthêi [e,f] tiÕp tôc tuyÕn tÝnh theo  trong qu¸ tr×nh rót gän. Qu¸ tr×nh thùc hiÖn PARA(*,) sÏ sinh ra 2hai hµm tuyÕn tÝnh so s¸nh ®îc lµ g1 ...