Luận văn: Về bài toán quy hoạch nguyên tuyến tính

Chia sẻ: Bfvhgfff Bfvhgfff | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

330
lượt xem 81
download

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

Luận văn: Về bài toán quy hoạch nguyên tuyến tính nhằm 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.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn: 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 ® 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ü) ® 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 ® 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 x 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 ® 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 ® 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 n T×m vect¬ x = (x1, x2,...., xn ) sao cho h m f(x) = ∑c x j =1 j j → min víi c¸c ®iÒu kiÖn: n  a x ≤ b ,i ∈I ∑ ij j i 1 (1.1) j =1  n  a x = b ,i ∈ I ∑ ij j i 2 (1.2)  j=1 n ∑aij x j ≥ bi , i ∈ I3 (1.3)  j=1  x j ≥ 0, j ∈ J1 (1.4) x ∈ R, j ∈ J (1.5)  j 2 x j ≤ 0, j ∈ J3  (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¶ m n 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 ® 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¶ m n: f(x) = ctx → min. -6-
 Ai x ≥ b , i ∈ I1  A x = b, i ∈ I  i 2  x ≥ 0, j ∈ J  j 1  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 (I)  x ≥ 0, j = 1, n  j -7-
• B−íc xuÊt ph¸t: T×m mét ph−¬ng ¸n cùc biªn x0 v c¬ së { } B = { A j ; j ∈ J B } t−¬ng øng, trong ®ã J B = j ∈ J / A ∈ B . T×m c¸c hÖ j 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ë ). xr0  xi0    - T×m dßng xoay: t×m θ= = min  , aij > 0  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 arj tö t−¬ng øng trong b¶ng cò chia cho phÇn tö xoay: a rj = , j∈J ars 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: arj a ij = aij − ais , i ∈ JB (i ≠ r) , j ∉ JB ( j ≠ s) ars a rj ∆ s ∆j =∆j − 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) g( y) = by → max  Ax = b  At y ≤ c   x ≥ 0 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 = AB1b ≥ 0 ). Ta gäi ph−¬ng ¸n c¬ së ®èi ngÉu t−¬ng øng víi c¬ së B l vect¬ y thu ®−îc b»ng c¸ch gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh AB y = cB (tøc l y = ( AB )−1 cB ) t t 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¶ m n tÊt c¶ c¸c r ng buéc cña b i to¸n ®èi ngÉu A y ≤ c hay At ( AB )−1 cB − c ≤ 0 t t (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¶ c1 ...... cj ..... cn së ph−¬ng ¸n 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 ® 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¶ m n 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ö ® 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ö a rj ë dßng −íc l−îng øng víi c¬ së míi sÏ l (∆ j − ∆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 ∆  s øng víi = min  j ; a rj < 0  . Cét As gäi l cét xoay. a rs  a rj  Sau khi ® 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− ® 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¬ cj c¬ Ph−¬ng ¸n c0 c1 ....... cj ....... cn ⌢ së B së ⌢ ⌢ ⌢ ⌢ M A0 A1 ....... Aj ....... Am ⌢ A0 c0 0 1 1 1 ⌢ A1 c1 b1 0 a1j a1n ..... ..... ..... ..... ..... ...... ⌢ Am cm bm 0 amj amn ∆0 ∆1 ...... ∆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 ® 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 m+1, j j (1.8) * NÕu x tho¶ m n 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¶ m n 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. C¬ së cj c¬ së Ph−¬ng c1 c2 ..... cj ... cn cn+1 ⌢ B ¸n ⌢ ⌢ ⌢ ⌢ ⌢ A1 A2 ..... Aj .... An An+1 ⌢ A1 c1 b1 a1 j 0 ⌢ A2 c2 b2 a2 j 0 .... .... .... ..... 0 ⌢ Am cm bm 0 a mj ⌢ cn+1 1 An+1 b m+1 a m+1, j ∆j ∆1 ∆2 .... ∆j .... ∆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 ® 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 l i 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 -