Tài liệu Về bài toán quy hoạch nguyên tuyến tính

Môc Lôc Néi dung Trang Më ®Çu 2 Ch−¬ng 1: C¸c kiÕn thøc bæ trî 1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t 5 1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh 7 1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c 9 Ch−¬ng 2: Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh 2.1. Bµi to¸n tèi −u rêi r¹c 19 2.2. Mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh 26 Ch−¬ng 3: Bµi tËp vËn dông 3.1. Bµi tËp vËn dông thuËt to¸n c¾t Gomory 50 3.2. Bµi tËp vËn dông thuËt to¸n Land - Doig 58 3.3. Bµi tËp ®−a bµi to¸n vÒ bµi to¸n c¸i tói ®Ó gi¶i 64 Tµi liÖu tham kh¶o 74 -1- Lêi Nãi ®Çu 1. LÝ do chän ®Ò tµi Tèi −u ho¸ lµ mét lÜnh vùc to¸n häc nghiªn cøu lý thuyÕt vÒ thuËt to¸n gi¶i c¸c bµi to¸n cùc trÞ. Nã lµ mét phÇn kiÕn thøc kh«ng thÓ thiÕu ®−îc cho nh÷ng ng−êi lµm viÖc trong c¸c lÜnh vùc øng dông cña khoa häc vµ kü thuËt. Trong lý thuyÕt tèi −u, mét trong nh÷ng líp bµi to¸n ®Çu tiªn ®−îc nghiªn cøu trän vÑn c¶ vÒ ph−¬ng diÖn lý thuyÕt lÉn thuËt to¸n lµ bµi to¸n quy ho¹ch tuyÕn tÝnh. Ngay tõ khi ra ®êi, quy ho¹ch tuyÕn tÝnh ®Q chiÕm mét vÞ trÝ hÕt søc quan träng; nã lµ m«n to¸n øng dông rÊt cÇn thiÕt ®èi víi sinh viªn thuéc nhiÒu ngµnh häc kh¸c nhau. C¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh kh«ng nh÷ng gióp gi¶i quyÕt c¸c bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t cì lín mµ nã cßn lµ ®iÓm xuÊt ph¸t quan träng trong viÖc nghiªn cøu lý thuyÕt gi¶i c¸c bµi to¸n tèi −u tæng qu¸t. Trong lý thuyÕt tèi −u ta gÆp mét líp bµi to¸n mµ ®èi t−îng cña nã kh«ng thÓ chia c¾t nhá tuú ý, trong líp bµi to¸n nµy tÊt c¶ (hoÆc mét bé phËn) c¸c biÕn chØ nhËn gi¸ trÞ nguyªn, ®ã lµ bµi to¸n quy ho¹ch nguyªn. Trong bµi to¸n quy ho¹ch nguyªn, nÕu hµm môc tiªu vµ hÖ rµng buéc lµ c¸c hµm tuyÕn tÝnh th× ta cã bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. §èi víi c¸c bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh, c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t c¬ b¶n hÇu hÕt kh«ng thÓ sö dông ®−îc n÷a do yªu cÇu vÒ tÝnh nguyªn cña c¸c biÕn sè. N¨m 1958 Gomory (nhµ to¸n häc ng−êi mü) ®Q c«ng bè thuËt to¸n c¾t nèi tiÕng ®Ó gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh më ®Çu cho sù ra ®êi vµ ph¸t triÓn cña lý thuyÕt bµi to¸n quy ho¹ch nguyªn. TiÕp ®ã, mét sè kÕt qu¶ nghiªn cøu vÒ tËp nghiÖm vµ lêi gi¶i cho líp bµi to¸n nµy lÇn l−ît ®−îc ra ®êi. Tuy xuÊt hiÖn sau thuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh gÇn ba thËp kû nh−ng c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh ®Q cã nh÷ng ®ãng gãp kh«ng nhá cho lÜnh vùc nghiªn cøu lý thuyÕt tèi −u tæng qu¸t. Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh lµ phÇn kiÕn thøc kh¸ míi mÎ ®èi víi sinh viªn s− ph¹m to¸n. Víi mong muèn khai th¸c s©u kiÕn thøc m«n quy ho¹ch tuyÕn tÝnh nãi riªng; më réng tÇm hiÓu biÕt cña b¶n th©n vÒ tri thøc to¸n -2- nãi chung, viÖc nghiªn cøu lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh lµ hÕt søc cÇn thiÕt. V× nh÷ng lý do trªn chóng t«i chän "VÒ bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh" lµm ®Ò tµi nghiªn cøu. 2. Môc ®Ých nghiªn cøu HÖ thèng l¹i mét c¸ch chi tiÕt c¸c vÊn ®Ò lý thuyÕt vÒ bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh; x©y dùng hÖ thèng bµi tËp vËn dông, ®Ó tõ ®ã thÊy ®−îc tÇm quan träng vµ tÝnh thiÕt thùc cña lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh ®èi víi c¸c lÜnh vùc khoa häc kü thuËt, c¸c ho¹t ®éng thùc tiÔn cña ®êi sèng xQ héi. 3. NhiÖm vô nghiªn cøu • Nghiªn cøu c¸c kiÕn thøc liªn quan ®Õn bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t, mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh. • Nghiªn cøu c¸c ph−¬ng ph¸p gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. • Nghiªn cøu mét sè bµi tËp vËn dông ph−¬ng ph¸p gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. 4. §èi t−îng vµ ph¹m vi nghiªn cøu §èi t−îng nghiªn cøu: Lý thuyÕt tèi −u ho¸. Ph¹m vi nghiªn cøu: Nghiªn cøu lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. 5. Ph−¬ng ph¸p nghiªn cøu • Ph−¬ng ph¸p nghiªn cøu lý luËn: §äc c¸c tµi liÖu vÒ m«n quy ho¹ch tuyÕn tÝnh, c¸c tµi liÖu liªn quan ®Õn tèi −u ho¸, c¸c kho¸ luËn tèt nghiÖp vÒ quy ho¹ch tuyÕn tÝnh cña c¸c kho¸ tr−íc ë tr−êng §¹i häc Hïng V−¬ng. • Ph−¬ng ph¸p lÊy ý kiÕn chuyªn gia: Tham kh¶o ý kiÕn cña gi¶ng viªn h−íng dÉn vµ c¸c gi¶ng viªn d¹y tèi −u ho¸; quy ho¹ch tuyÕn tÝnh cña tr−êng. • Ph−¬ng ph¸p tæng kÕt kinh nghiÖm: Tæng kÕt kinh nghiÖm cña b¶n th©n qua qu¸ tr×nh häc häc phÇn quy ho¹ch tuyÕn tÝnh vµ cña c¸c b¹n sinh viªn ®Q häc tèi −u hãa cña c¸c líp s− ph¹m vµ c¸c líp qu¶n trÞ kinh doanh trong tr−êng. -3- 6. ý nghÜa khoa häc vµ thùc tiÔn S¶n phÈm khoa häc: HÖ thèng l¹i mét sè kiÕn thøc cña lý thuyÕt tèi −u tuyÕn tÝnh, giíi thiÖu mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh, x©y dùng hÖ thèng bµi tËp vËn dông lý thuyÕt ®Q x©y dùng. S¶n phÈm thùc tiÔn: Khãa luËn lµ tµi liÖu tham kh¶o cho sinh viªn to¸n, tin häc vµ sinh viªn c¸c ngµnh kinh tÕ, qu¶n trÞ kinh doanh. 7. Bè côc kho¸ luËn Khãa luËn gåm 74 trang, ngoµi phÇn môc lôc, më ®Çu, kÕt luËn vµ tµi liÖu tham kh¶o néi dung chÝnh cña kho¸ luËn bao gåm 3 ch−¬ng Ch−¬ng 1. C¸c kiÕn thøc bæ trî 1.1. Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh tæng qu¸t 1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh 1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c Ch−¬ng 2. Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh 2.1. Bµi to¸n tèi −u rêi r¹c 2.2. Mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh • ThuËt to¸n c¾t cña Gomory • Ph−¬ng ph¸p nh¸nh cËn (ThuËt to¸n Land - Doig) • Ph−¬ng ph¸p ph−¬ng tr×nh truy to¸n cña quy ho¹ch ®éng gi¶i bµi to¸n c¸i tói Ch−¬ng 3. Bµi tËp vËn dông 3.1. Bµi tËp vËn dông thuËt to¸n c¾t cña Gomory 3.2. Bµi tËp vËn dông thuËt to¸n Land - Doig 3.3. Bµi tËp ®−a bµi to¸n vÒ bµi to¸n c¸i tói ®Ó gi¶i -4- CH¦¥NG 1 C¸C KIÕN THøC Bæ TRî 1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t 1.1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t T×m vect¬ x = (x1, x2,...., xn ) sao cho hµm f(x) = n ∑c x j =1 j j → min víi c¸c ®iÒu kiÖn: n  a x ≤ b ,i ∈I 1 ∑ ij j i j =1  n  a x = b ,i ∈ I ij j i 2 ∑  j=1 n ∑aij x j ≥ bi , i ∈ I3  j=1  x j ≥ 0, j ∈ J1 x ∈ R, j ∈ J 2  j x j ≤ 0, j ∈ J3 (1.1) (1.2) (1.3) (1.4) (1.5) (1.6) Víi I1 ⊂ I; I2 ⊂ I; I3 ⊂ I; I={ 1,.., m}; I1∪ I2 ∪I3 = I; Ii ∩ Ik =Ø; i ≠ k; i, k = 1,2,3. J1⊂ J; J2 ⊂ J; J3 ⊂ J; J = { 1,.., n}; J = J1 ∪ J2 ∪J3, Ji ∩Jk = Ø; I ≠ k; i,k = 1,2,3. bi, cj, aij lµ c¸c h»ng sè cho tr−íc. Trong bµi to¸n trªn: • f ®−îc gäi lµ hµm môc tiªu. • Mçi hÖ thøc ë (1.1), (1.2), (1.3), (1.4), (1.5), (1.6) gäi lµ mét rµng buéc. • Mçi rµng buéc (1.1), (1.2), (1.3) gäi lµ rµng buéc c−ìng bøc (hay c¬ b¶n). • Rµng buéc (1.4), (1.5), (1.6) gäi lµ rµng buéc tù do (hay rµng buéc dÊu). + Mçi vect¬ x = (x1, x2,...., xn ) ∈ Rn tho¶ mQn mäi rµng buéc cña bµi to¸n gäi lµ mét ph−¬ng ¸n. TËp hîp tÊt c¶ c¸c ph−¬ng ¸n (ký hiÖu D) gäi lµ miÒn rµng -5- buéc hay miÒn chÊp nhËn ®−îc. Ph−¬ng ¸n lµm cho hµm môc tiªu ®¹t cùc tiÓu hoÆc cùc ®¹i ®−îc gäi lµ ph−¬ng ¸n tèi −u hay mét lêi gi¶i cña bµi to¸n ®Q cho. + Gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh lµ t×m ph−¬ng ¸n tèi −u cña bµi to¸n (cã thÓ lµ ph−¬ng ¸n tèi −u duy nhÊt hoÆc v« sè ph−¬ng ¸n tèi −u) hoÆc chøng tá bµi to¸n v« nghiÖm. 1.1.2. Mét sè kÝ hiÖu quy −íc a) NÕu A lµ ma trËn cì (m,n) th× Ai =(ai1,ai2,...,ain) lµ vect¬ dßng (ma trËn dßng) thø i (i = 1,2,...., m) cña A; Aj = (a1j, a2j,..,amj) lµ vect¬ cét (ma trËn cét) thø j (j = 1,2,...,n) cña A. b) At lµ ma trËn chuyÓn vÞ cña A. c) NÕu A = (aij) vµ B = (bij) lµ hai ma trËn cïng kiÓu th× bÊt ®¼ng thøc ma trËn A ≥ B ®−îc hiÓu lµ aij ≥ bij víi ∀ i,j. §Æc biÖt víi vect¬ (ma trËn) x = (x1, x2,...., xn ) th× x ≥ 0 ®−îc hiÓu lµ xj ≥ 0 ∀ j. d) Mçi vect¬ ®−îc xem nh− ma trËn cét trong c¸c phÐp tÝnh ma trËn ( nÕu kh«ng nãi g× thªm hoÆc kh«ng cã quy −íc g× kh¸c). e) BiÓu thøc tÝch v« h−íng cña hai vect¬ x = (x1, x2,...., xn ) ; y = (y1, y2, ..., yn) n ®−îc viÕt: (x, y) = ∑x j =1 j yj n g) NÕu xem c vµ x lµ hai ma trËn cét th× c x = ∑ c j x j lµ ma trËn cÊp 1 ( ct lµ t j =1 ma trËn chuyÓn vÞ cña c). Víi nh÷ng quy −íc nh− trªn bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t ®−îc viÕt gän nh− sau: T×m vect¬ x = (x1, x2,...., xn) ∈ Rn tho¶ mQn: f(x) = ctx → min. -6-  Ai x ≥ b , i ∈ I1  A x = b, i ∈ I 2  i  x ≥ 0, j ∈ J 1  j  x j ∈ R, j ∈ J 2  Trong ®ã A = (aij) lµ hai ma trËn cì (m,n). 1.1.3. D¹ng chÝnh t¾c vµ d¹ng chuÈn t¾c cña bµi to¸n quy ho¹ch tuyÕn tÝnh D¹ng chuÈn t¾c: f(x) = ctx→min Ax ≥ b  x j ≥ 0, j ∈ J D¹ng chÝnh t¾c: f(x) = ctx → min  Ax = b   x j ≥ 0, j ∈ J 1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c (bµi to¸n I) n f ( x) = ∑ c j x j → min j =1  n  ∑ aij x j = bi  j =1  x ≥ 0, j = 1, n  j (I) -7- • B−íc xuÊt ph¸t: T×m mét ph−¬ng ¸n cùc biªn { x0 vµ c¬ së } j B = { A j ; j ∈ J B } t−¬ng øng, trong ®ã J B = j ∈ J / A ∈ B . T×m c¸c hÖ sè khai triÓn aij vµ c¸c −íc l−îng ∆ j ( aij : hÖ sè khai triÓn vect¬ Ai qua c¸c vect¬ Aj). • B−íc 1:KiÓm tra dÊu hiÖu tèi −u: a) NÕu ∆ j ≤ 0 ∀ j ∈ J th× x lµ ph−¬ng ¸n tèi −u. ThuËt to¸n kÕt thóc. 0 b) NÕu ∃ ∆ j > 0 th× chuyÓn sang b−íc hai. • B−íc 2: KiÓm tra dÊu hiÖu hµm môc tiªu gi¶m v« h¹n. Víi mçi j ∉ JB mµ ∆ j > 0 th× kiÓm c¸c hÖ sè khai triÓn aij cña cét A j t−¬ng øng. a) NÕu tån t¹i ∆ j > 0 mµ tÊt c¶ aij ≤ 0 ∀ j ∈ J th× kÕt luËn hµm môc tiªu gi¶m v« h¹n trªn miÒn rµng buéc. Bµi to¸n kh«ng cã lêi gi¶i h÷u h¹n. ThuËt to¸n kÕt thóc. b) NÕu víi mçi j ∉ JB mµ ∆ j > 0 ®Òu tån t¹i Ýt nhÊt mét hÖ sè aij > 0 th× tiÕn hµnh t×m ph−¬ng ¸n cùc biªn míi tèt h¬n víi c¬ së J 1 = ( J B \ r ) ∪ s theo quy t¾c sau: • B−íc 3: { - T×m cét xoay: T×m ∆s = max ∆ j > 0, j ∉ J B } Cét As gäi lµ cét xoay (cét ®−a vµo c¬ së ).  xi0  xr0 θ = = min , a > 0 - T×m dßng xoay: t×m   ij ars  aij  Dßng Ar gäi lµ dßng xoay. -8- PhÇn tö n»m trªn giao cña dßng xoay vµ cét xoay cña b¶ng ®¬n h×nh ®−îc gäi lµ phÇn tö xoay. • B−íc 4: Thùc hiÖn phÐp biÕn ®æi ®¬n h×nh chuyÓn tõ ph−¬ng ¸n c¬ së chÊp nhËn ®−îc x sang ph−¬ng ¸n c¬ së chÊp nhËn ®−îc x : B¶ng ®¬n h×nh t−¬ng øng víi x (gäi t¾t lµ b¶ng míi) cã thÓ thu ®−îc tõ b¶ng ®¬n h×nh t−¬ng øng víi x (gäi t¾t lµ b¶ng cò) theo c¸c quy t¾c biÕn ®æi sau ®©y: a) C¸c phÇn tö ë vÞ trÝ dßng xoay trong b¶ng míi ( a rj ) b»ng c¸c phÇn tö t−¬ng øng trong b¶ng cò chia cho phÇn tö xoay: a rj = arj ars , j∈J b) C¸c phÇn tö ë vÞ trÝ cét xoay trong b¶ng míi, ngo¹i trõ phÇn tö n»m trªn vÞ trÝ phÇn tö xoay b»ng 1, cßn tÊt c¶ lµ b»ng 0. c) C¸c phÇn tö cÇn tÝnh cßn l¹i trong b¶ng míi (aij , ∆ j ) ®−îc tÝnh tõ c¸c phÇn tö t−¬ng øng trong b¶ng cò theo c¸c c«ng thøc sau: a ij = aij − arj ars ∆j =∆j − ais , i ∈ JB (i ≠ r) , j ∉ JB ( j ≠ s) a rj ∆ s a rs 1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c 1.3.1. C¬ së chÊp nhËn ®−îc ®èi ngÉu XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c (P) vµ bµi to¸n ®èi ngÉu (Q). (P) f ( x ) = c t x → min (Q)  Ax = b  x ≥ 0 g( y) = by → max  At y ≤ c  y∈R Gi¶ thiÕt r»ng rankA = m. Gi¶ sö B = { A j ; j ∈ J } lµ mét hÖ gåm m vect¬ cét ®éc lËp tuyÕn tÝnh cña ma trËn A. Ta gäi hÖ vect¬ nµy lµ c¬ së cña ma trËn A. -9- Ký hiÖu N = { A1 , A2 ,..., An } \ B. Ph−¬ng ¸n c¬ së (xB, xN) cña bµi to¸n (P) t−¬ng øng víi c¬ së B thu ®−îc b»ng c¸ch gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh xN = 0, ABxB = b. §Þnh nghÜa : Ta gäi B lµ c¬ së chÊp nhËn ®−îc gèc nÕu ph−¬ng ¸n c¬ së t−¬ng øng víi nã lµ ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n gèc, (tøc lµ nÕu xB = AB−1b ≥ 0 ). Ta gäi ph−¬ng ¸n c¬ së ®èi ngÉu t−¬ng øng víi c¬ së B lµ vect¬ y t thu ®−îc b»ng c¸ch gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh AB y = cB (tøc lµ y = ( ABt )−1 cB ) C¬ së B ®−îc gäi lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu nÕu ph−¬ng ¸n c¬ së ®èi ngÉu øng víi nã lµ ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n ®èi ngÉu. NÕu ph−¬ng ¸n c¬ së t−¬ng øng víi B lµ ph−¬ng ¸n tèi −u th× B sÏ ®−îc gäi lµ c¬ së tèi −u. Nh− vËy nÕu B lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu th× ph−¬ng ¸n c¬ së ®èi t −1 ngÉu t−¬ng øng víi nã y = ( AB ) cB ph¶i tho¶ mQn tÊt c¶ c¸c rµng buéc cña bµi t to¸n ®èi ngÉu A y ≤ c hay At ( ABt )−1 cB − c ≤ 0 (1.7) DÔ thÊy nÕu B lµ c¬ së chÊp nhËn ®−îc gèc, th× ®iÒu kiÖn (1.7) chÝnh lµ tiªu chuÈn tèi −u. Nh− vËy, c¬ së B sÏ lµ tèi −u nÕu nh− nã võa lµ chÊp nhËn ®−îc gèc võa lµ chÊp nhËn ®−îc ®èi ngÉu. NhËn xÐt • ThuËt to¸n ®¬n h×nh gèc lµ b¾t ®Çu tõ mét c¬ së chÊp nhËn ®−îc gèc, sau mét sè h÷u h¹n lÇn chuyÓn c¬ së sÏ ®i ®Õn c¬ së tèi −u. • ThuËt to¸n ®¬n h×nh ®èi ngÉu l¹i b¾t ®Çu tõ mét c¬ së chÊp nhËn ®èi ngÉu nh−ng ch−a ph¶i chÊp nhËn ®−îc gèc, ta tiÕn hµnh dÞch chuyÓn sang c¸c c¬ së chÊp nhËn ®−îc ®èi ngÉu míi cho ®Õn khi gÆp ®−îc c¬ së tèi −u th× dõng l¹i. 1.3.2. ThuËt to¸n ®¬n h×nh ®èi ngÉu khi ®· biÕt c¬ së chÊp nhËn ®−îc ®èi ngÉu - 10 - XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c. f(x) = ctx→ min  Ax = b  x ≥ 0 Gi¶ sö B lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu. Kh«ng gi¶m tæng qu¸t ta coi B = (A1,A2,....,Am). Ta lËp b¶ng ®¬n h×nh øng víi c¬ së B cña bµi to¸n gèc. C¬ cj c¬ së Gi¶ ph−¬ng ¸n së c1 ...... cj ..... cn A1 ...... Aj ..... An A1 c1 b1 a1 j A2 c2 b2 a2 j ..... ..... ..... ...... Am cm bm a mj ∆j ∆ B¶ng 1 Trong ®ã: b = (b1,b2,...,bm)' = B−1b j A = (a1 j , a2 j ,...., amj ) = B−1 A j , j = 1, n ∆ j = cB B −1 A j − c j ; j = 1, n Cét gi¶ ph−¬ng ¸n cã thÓ chøa c¸c thµnh phÇn ©m v× B ch−a ch¾c ®Q lµ mét c¬ së chÊp nhËn ®−îc gèc. - 11 - Do B lµ mét c¬ së chÊp nhËn ®−îc ®èi ngÉu nªn ∆ j ≤ 0 ∀ j = 1, n C¸c b−íc cña thñ tôc ®¬n h×nh ®èi ngÉu. B−íc 1: KiÓm tra tiªu chuÈn tèi −u. C¬ së ®ang xÐt sÏ lµ tèi −u nÕu mäi thµnh phÇn b i , i = 1, m cña cét gi¶ ph−¬ng ¸n ®Òu kh«ng ©m v× khi ®ã c¬ së ®ang xÐt sÏ chÊp nhËn ®−îc gèc vµ v× thÕ nã lµ tèi −u. • NÕu bi ≥ 0 ∀ i = 1, m th× gi¶ ph−¬ng ¸n (xB, xN) lµ mét ph−¬ng ¸n tèi −u. ThuËt to¸n kÕt thóc. • NÕu ∃ i, i = 1, m mµ b i < 0 th× ta t×m br = min{ b i , i = 1, m }. NÕu cã nhiÒu chØ sè cïng ®¹t cùc tiÓu th× chän r lµ mét chØ sè tuú ý trong sè ®ã. B−íc 2: KiÓm tra ®iÒu kiÖn ®Ó tËp ph−¬ng ¸n cña bµi to¸n lµ kh«ng rçng: nÕu cã i = 1, m mµ b i < 0 th× trªn dßng i ph¶i tån t¹i Ýt nhÊt mét phÇn tö aij < 0 . • NÕu cã dßng øng víi b i < 0 (i = 1,2,...,m) mµ aij ≥ 0 ∀ j = 1, n . Khi ®ã bµi to¸n gèc (P) kh«ng cã ph−¬ng ¸n. ThËt vËy. Gi¶ sö (P) cã ph−¬ng ¸n, tøc lµ ∃ x ∈ Rn tho¶ mQn Ax = b, x≥ 0 n hay ∑a j =1 ij x j = bi , (i = 1, m) (*) (*) kh«ng thÓ x¶y ra v× aij ≥ 0, xj ≥ 0 ( j = 1, n ) cßn bi < 0. VËy bµi to¸n (P) kh«ng cã ph−¬ng ¸n. • NÕu trªn mçi dßng øng víi b i < 0 ®Òu tån t¹i Ýt nhÊt mét phÇn tö aij ≤ 0 . Khi ®ã ta tiÕn hµnh mét b−íc lÆp ®¬n h×nh ®èi ngÉu ®Ó chuyÓn sang mét c¬ së chÊp nhËn ®−îc ®èi ngÉu míi. Gi¶ sö ®Q chän dßng xoay r. Ta t×m cét ®−a vµo c¬ së thay cho cét Ar. Cét ®−a vµo thay cho Ar ph¶i ®¶m b¶o sao cho c¬ së míi vÉn lµ c¬ së chÊp nhËn - 12 - ®−îc ®èi ngÉu. Gi¶ sö cét As ®−îc ®−a vµo thay cho cét Ar, khi ®ã phÇn tö trôc ars vµ sau khi thùc hiÖn tÝnh to¸n ®æi c¬ së th× c¸c phÇn tö ë dßng −íc l−îng øng víi c¬ së míi sÏ lµ (∆ j − a rj ∆s) a rs Do ®ã muèn c¬ së míi vÉn lµ chÊp nhËn ®−îc ®èi ngÉu ta ph¶i chän chØ sè s øng víi ∆  ∆s = min  j ; a rj < 0  . Cét As gäi lµ cét xoay. a rs  a rj  Sau khi ®Q x¸c ®Þnh ®−îc dßng xoay, cét xoay ta tiÕn hµnh c¸c tÝnh to¸n trong phÐp biÕn ®æi ®¬n h×nh gièng nh− ®Q lµm trong bµi to¸n gèc. 1.3.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu khi ch−a biÕt c¬ së xuÊt ph¸t chÊp nhËn ®−îc ®èi ngÉu XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c sau: f(x) = ctx → min  Ax = b  x ≥ 0 Gi¶ sö c¬ së chÊp nhËn ®−îc ®èi ngÉu lµ ch−a biÕt. Tuy vËy ta cã thÓ t×m ®−îc c¬ së B cña ma trËn A. Kh«ng gi¶m tæng qu¸t ta coi r»ng B = {A1, A2,..., Am}. Gi¶ sö c¬ së B kh«ng ph¶i lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu (cã thÓ nã còng kh«ng chÊp nhËn ®−îc gèc). §−a thªm vµo mét biÕn gi¶ x0 ≥ 0 víi hÖ sè hµm môc tiªu c0 = 0, vµ thªm vµo hÖ rµng buéc cña bµi to¸n xuÊt ph¸t mét rµng buéc gi¶ sau: x0 + xm +1 + ...........+ xn = M trong ®ã (xm+1,......, xn) lµ vect¬ c¸c biÕn phi c¬ së, cßn M lµ mét sè d−¬ng lín h¬n bÊt kú mét sè cô thÓ nµo cÇn so s¸nh víi nã. Bµi to¸n thu ®−îc ta sÏ gäi lµ - 13 - bµi to¸n më réng. §èi víi bµi to¸n më réng ta cã mét c¬ së cña nã lµ ⌢ ⌢ ⌢ ⌢ B = ( A0 , A1,...., Am ) ⌢ Ta x©y dùng b¶ng ®¬n h×nh t−¬ng øng víi c¬ së B cña bµi to¸n më réng. C¬ ⌢ së B cj c¬ Ph−¬ng ¸n c0 c1 ....... cj ....... cn M ⌢ A0 ⌢ A1 ....... ⌢ Aj ....... ⌢ Am ⌢ A0 c0 0 1 ⌢ A1 c1 b1 0 ..... ..... ..... ..... ⌢ Am cm bm 0 së ∆0 ∆1 ...... 1 1 a1j a1n ..... ...... amj amn ∆j ∆n Chó ý r»ng, khi tÝnh gi¸ trÞ c¸c thµnh phÇn cña cét ph−¬ng ¸n ta viÕt nã ⌢ ⌢ d−íi d¹ng bi + bi M . Khi ®ã trong b¶ng ®¬n h×nh cét ph−¬ng ¸n ®−îc t¸ch ra lµm ⌢ ⌢ hai cét, mét cét ghi hÖ sè bi cña M, cßn cét kia ghi hÖ sè tù do bi . ⌢ Gi¶ sö ∆s = max { ∆ j ; j = 1, n }. Do B kh«ng ph¶i lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu cña bµi to¸n nªn ∆s > 0. Thùc hiÖn mét phÐp biÕn ®æi ®¬n h×nh víi phÇn tö xoay a0s (nghÜa lµ ®−a biÕn xs vµo c¬ së cßn ®−a x0 ra khái c¬ së) ta sÏ ®i ®Õn b¶ng ®¬n h×nh míi mµ trong ®ã tÊt c¶ c¸c phÇn tö cña dßng −íc l−îng ∆ j ; j = 1, n ®Òu lµ kh«ng d−¬ng tøc lµ thu ®−îc b¶ng ®¬n h×nh ®èi ngÉu víi c¬ së chÊp nhËn ®−îc ®èi ngÉu nªn ta cã thÓ tiÕn hµnh thñ tôc ®¬n h×nh ®èi ngÉu víi c¬ së chÊp nhËn ®−îc ®èi ngÉu ®Ó gi¶i bµi to¸n më réng. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n më réng sÏ kÕt thóc ë mét trong c¸c tr−êng hîp sau. - 14 - 1) Bµi to¸n më réng kh«ng cã ph−¬ng ¸n. Khi ®ã bµi to¸n xuÊt ph¸t còng kh«ng cã ph−¬ng ¸n. ThËt vËy, nÕu bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n chÊp nhËn ®−îc x = (x1, x2,...., xn) th× râ rµng x = (x0, x1,...., xn) víi x0 = M xm+1 -..........- xn còng lµ mét ph−¬ng ¸n cña bµi to¸n më réng. 2) Bµi to¸n më réng cã ph−¬ng ¸n tèi −u x = ( x0 , x1,...., xn ) vµ x0 lµ biÕn c¬ së. Trong tr−êng hîp nµy hµm môc tiªu cña bµi to¸n kh«ng phô thuéc vµo M, do ®ã (x1,...., xn ) lµ ph−¬ng ¸n tèi −u cña bµi to¸n ban ®Çu. 3) Bµi to¸n më réng cã ph−¬ng ¸n tèi −u x = ( x 0 , x1 ,...., x n ) vµ x0 kh«ng lµ biÕn c¬ së. Trong tr−êng hîp nµy c¸c biÕn c¬ së sÏ phô thuéc vµo M. Cã hai kh¶ n¨ng x¶y ra • NÕu gi¸ trÞ hµm môc tiªu cña bµi to¸n më réng phô thuéc vµo M th× khi M → ∞ gi¸ trÞ hµm môc tiªu sÏ dÇn ®Õn ∞.Trong tr−êng hîp nµy bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n chÊp nhËn ®−îc nh−ng hµm môc tiªu kh«ng bÞ chÆn d−íi nªn bµi to¸n kh«ng cã lêi gi¶i. • NÕu gi¸ trÞ hµm môc tiªu cña bµi to¸n më réng kh«ng phô thuéc vµo M th× bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n tèi −u vµ cã thÓ chÊp nhËn ®−îc nã b»ng c¸ch bá x0 vµ gi¶m dÇn gi¸ trÞ M cho ®Õn khi cã mét trong c¸c x1 , x2 ,...., xn trë thµnh 0. 1.3.4. ¸p dông thuËt to¸n ®¬n h×nh ®èi ngÉu ®Ó gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh víi sè rµng buéc t¨ng dÇn XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh (I): Gi¶ sö ta ®Q gi¶i bµi to¸n (I) b»ng thuËt to¸n ®¬n h×nh vµ thu ®−îc ph−¬ng * ¸n tèi −u c¬ së x víi c¬ së tèi −u B. Kh«ng gi¶m tæng qu¸t ta cã thÓ coi r»ng B = { A1, A2,..., Am} . Ta cã b¶ng ®¬n h×nh tèi −u lµ b¶ng 1 phÇn 1.3.2. - 15 - B©y giê bæ sung vµo hÖ rµng buéc cña bµi to¸n mét ph−¬ng tr×nh: n ∑a j=1 x ≤ bm+1 (1.8) m+1, j j * NÕu x tho¶ mQn rµng buéc ( 1.8) th× nã vÉn lµ ph−¬ng ¸n tèi −u cña bµi * to¸n cã rµng buéc bæ sung nµy. Gi¶ sö x kh«ng tho¶ mQn rµng buéc bæ sung, tøc lµ: n ∑ am+1, j x j > bm+1 * (1.9) j =1 * VÊn ®Ò ®Æt ra: LiÖu ta cã thÓ sö dông ph−¬ng ¸n tèi −u x vµ c¬ së tèi −u B ®Ó gi¶i bµi to¸n víi rµng buéc bæ sung hay kh«ng? §−a thªm vµo biÕn phô x n +1 ≥ 0 chuyÓn rµng buéc (1.8) vÒ d¹ng ®¼ng thøc ta thu ®−îc: n ∑a j =1 m +1, j x j + xn +1 = bm+1 (1.10) XÐt bµi to¸n (I) víi rµng buéc bæ sung (1.10) mµ ta sÏ gäi lµ bµi to¸n bæ sung. n f ( x) = ∑c j x j + 0xn+1 → min j =1  n  ∑ aij x j = bi ; i = 1, m  j =1  n  ∑ a m +1, j x j + x n +1 = bm +1  j =1  x ≥ 0; j = 1, n + 1  j  - 16 - ⌢ ⌢ ⌢ ⌢ ⌢ §èi víi bµi to¸n bæ sung c¬ së cña nã lµ B = ( A1 , A2 ,..., A m , A n +1 ) . B¶ng ®¬n h×nh t−¬ng øng víi c¬ së nµy cã thÓ thu ®−îc tõ b¶ng ®¬n h×nh tèi −u cña bµi to¸n ban ®Çu vµ cã d¹ng sau. cj c¬ së C¬ së ⌢ B Ph−¬ng c1 c2 ..... cj ... cn cn+1 ¸n ⌢ A1 ⌢ A2 ..... ⌢ Aj .... ⌢ An ⌢ An+1 ⌢ A1 c1 b1 a1 j 0 ⌢ A2 c2 b2 a2 j 0 .... .... .... ..... 0 ⌢ Am cm bm a mj ⌢ An+1 cn+1 b m+1 a m+1, j ∆j ∆1 ∆2 .... ∆j 0 1 .... ∆n 0 Trong ®ã: m am+1, j = am+1, j − ∑am+1,i aij ; j = m +1, n i=1 a m+1, j = 0; j = 1, m m bm+1 = bm+1 − ∑ am+1,i bi i =1 Do (1.9) nªn b¶ng ®¬n h×nh thu ®−îc kh«ng ph¶i lµ chÊp nhËn ®−îc gèc. ThÕ nh−ng râ rµng nã lµ chÊp nhËn ®−îc ®èi ngÉu. V× vËy ta cã thÓ ¸p dông thuËt to¸n ®¬n h×nh ®èi ngÉu tõ b¶ng nµy ®Ó gi¶i bµi to¸n bæ sung. Kü thuËt võa m« t¶ ë trªn ®−îc gäi lµ " kÜ thuËt t¸i tèi −u ho¸". - 17 - KÕt luËn ch−¬ng 1 Ch−¬ng 1 ®Q tr×nh bµy mét sè vÊn ®Ò c¬ së cña lý thuyÕt tèi −u: bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t, thuËt to¸n ®¬n h×nh gèc gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh, thuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh. §©y lµ c¸c néi dung c¬ b¶n lµm c¬ së ®Ó tiÕn hµnh nghiªn cøu c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh ë ch−¬ng 2. - 18 - Ch−¬ng 2 bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh 2.1. Bµi to¸n tèi −u rêi r¹c 2.1.1. X©y dùng m« h×nh tèi −u rêi r¹c Tr−íc tiªn chóng ta bµn vÒ nh÷ng nguyªn nh©n dÉn ®Õn tÝnh rêi r¹c cña biÕn sè trong viÖc x©y dùng m« h×nh tèi −u ho¸ cho c¸c bµi to¸n thùc tÕ. Mét trong nh÷ng nguyªn nh©n ®Çu tiªn dÉn ®Õn tÝnh rêi r¹c cña biÕn sè lµ tÝnh kh«ng chia c¾t ®−îc cña ®èi t−îng nghiªn cøu. Ngoµi ra, trong nhiÒu bµi to¸n thùc tÕ chÝnh do cÊu tróc tæ hîp ban ®Çu cña bµi to¸n mµ c¸c biÕn sè chØ cã thÓ nhËn c¸c gi¸ trÞ rêi r¹c. Cuèi cïng, tÝnh rêi r¹c cña c¸c biÕn sè cã thÓ xuÊt hiÖn tõ tÝnh kh«ng liªn tôc, ®a cùc trÞ cña hµm môc tiªu cña bµi to¸n. Ta sÏ minh ho¹ cho c¸c vÊn ®Ò võa bµn tíi ë c¸c vÝ dô sau nµy. M« h×nh bµi to¸n tèi −u rêi r¹c tæng qu¸t Bµi to¸n tèi −u rêi r¹c tæng qu¸t cã thÓ ph¸t biÓu nh− sau: f ( x1, x2 ,...., xn ) → min(max) , (2.1) x = (x1, x2 ,...., xn ) ∈ D ⊂ Rn Trong ®ã D lµ tËp c¸c vect¬ x = (x1, x2,...., xn ) mµ mét sè (hoÆc tÊt c¶) c¸c thµnh phÇn cña nã chØ nhËn gi¸ trÞ rêi r¹c. Th«ng th−êng tËp D ®−îc x¸c ®Þnh bëi mét hÖ thèng c¸c ph−¬ng tr×nh vµ bÊt ph−¬ng tr×nh víi ®iÒu kiÖn bæ sung vÒ tÝnh nguyªn cña c¸c biÕn sè sau ®©y: gi ( x) = 0, i = 1, 2,...., m1 , (2.2) g i ( x ) ≤ 0, i = m1 + 1,....., m (2.3) - 19 - xj - nguyªn, j = 1,2,..., n1 (2.4) Khi ®ã bµi to¸n (2.1) - (2.4) ®−îc gäi lµ bµi to¸n quy ho¹ch nguyªn. NÕu n1 = n ta cã bµi to¸n quy ho¹ch nguyªn hoµn toµn, cßn nÕu n1 < n ta cã bµi to¸n quy ho¹ch nguyªn bé phËn. Mét tr−êng hîp riªng quan träng cña bµi to¸n quy ho¹ch nguyªn lµ bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh thu ®−îc tõ bµi to¸n tæng qu¸t khi c¸c hµm f ( x) vµ g i ( x) (i = 1,2,...,m) lµ tuyÕn tÝnh. 2.1.2. Mét sè t×nh huèng th−êng gÆp khi x©y dùng c¸c m« h×nh thùc tÕ cña tèi −u rêi r¹c 2.1.2.1. Bµi to¸n ®iÒu kiÖn kh«ng chia c¾t ®−îc Trong viÖc m« h×nh ho¸ nhiÒu vÊn ®Ò øng dông, tõ ý nghÜa thùc tÕ c¸c biÕn sè ph¶i nhËn gi¸ trÞ nguyªn. Ch¼ng h¹n, xÐt bµi to¸n lËp kÕ ho¹ch s¶n xuÊt víi s¶n phÈm cuèi cïng lµ kh«ng chia c¾t ®−îc. Mét nhµ m¸y cã kh¶ n¨ng s¶n xuÊt n lo¹i s¶n phÈm. §Ó s¶n xuÊt c¸c lo¹i s¶n phÈm nµy cÇn sö dông m lo¹i nguyªn liÖu. BiÕt aij (i = 1, m; j = 1, n) - chi phÝ nguyªn liÖu lo¹i i ®Ó s¶n xuÊt ra mét s¶n phÈm lo¹i j bi (i = 1, m) - dù tr÷ nguyªn liÖu lo¹i i cña nhµ m¸y ; c j ( j = 1, n ) - tiÒn lQi tõ viÖc b¸n mét s¶n phÈm lo¹i j ; NÕu nh− s¶n phÈm ®−îc s¶n xuÊt víi sè l−îng lín (vÝ dô nh− bi xe ®¹p hay nan hoa xe ®¹p) th× viÖc bá qua tÝnh nguyªn cña biÕn sè kh«ng dÉn ®Õn nh÷ng sai lÖch ®¸ng kÓ. ThÕ nh−ng nÕu s¶n phÈm ®−îc s¶n xuÊt víi sè l−îng kh«ng lín vµ gi¸ trÞ mét s¶n phÈm lµ cao (vÝ dô cç m¸y kÐo), th× tÝnh nguyªn cña biÕn sè - 20 -