Giáo trình tối ưu hoá ứng dụng

Chia sẻ: Ho Dung | Ngày: | Loại File: PDF | Số trang:59

Thêm vào BST

Báo xấu

1.059
lượt xem 395
download

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

Giáo trình tối ưu hoá ứng dụng nhằm mục đích giới thiệu cho người đọc những vấn đề cơ bản nhằm xác lập một vấn đề tối ưu dưới những ràng buộc nhất định và từ đó tìm kỹ thuật giải thích hợp. Nội dung giáo trình mô tả phần cơ sở lý thuyết ngắn gọn, đủ dùng cho phương pháp tính và thuật toán.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình tối ưu hoá ứng dụng

TRƯỜNG………………….. Khoa…………………. ----- ----- Giáo trình tối ưu hoá ứng dụng
Lêi nãi ®Çu C¸c bµi to¸n tèi −u nh»m nghiªn cøu gi¶i bµi to¸n cùc trÞ cña mét hµm d−íi nh÷ng rµng buéc nµo ®ã. C¸c ph−¬ng ph¸p tèi −u lµ mét c«ng cô h÷u hiÖu gióp chóng ta cã nh÷ng gi¶i ph¸p tèt nhÊt ®Ó gi¶i quyÕt mét vÊn ®Ò. Ngµy nay, víi sù ph¸t triÓn cña kü thuËt tin häc, ph¹m vi øng dông cña tèi −u hãa ngµy cµng më réng. Gi¸o tr×nh Tèi −u hãa øng dông nh»m môc ®Ých giíi thiÖu cho ng−êi ®äc nh÷ng vÊn ®Ò c¬ b¶n nh»m x¸c lËp mét vÊn ®Ò tèi −u d−íi nh÷ng rµng buéc nhÊt ®Þnh vµ tõ ®ã t×m kü thuËt gi¶i thÝch hîp. Néi dung gi¸o tr×nh m« t¶ phÇn c¬ së lý thuyÕt ng¾n gän, ®ñ dïng cho ph−¬ng ph¸p tÝnh vµ thuËt to¸n. Mét sè vÝ dô minh häa cho ph−¬ng ph¸p gi¶i vµ c¸c bµi tËp øng dông. NguyÔn §¾c Lùc 1
Môc lôc Lêi nãi ®Çu 1 Môc lôc 2 Ch−¬ng 1: C¬ së cña ®¹i sè tuyÕn tÝnh 3 1.1. Ma trËn vµ c¸c phÐp tÝnh ma trËn 3 1.2. §Þnh thøc vµ c¸c tÝnh chÊt cña chóng 4 1.3. Ma trËn nghÞch ®¶o vµ h¹ng cña ma trËn 5 1.4. HÖ ph−¬ng tr×nh tuyÕn tÝnh 7 Ch−¬ng 2: Kh¸i niÖm vÒ c¸c bµi to¸n tèi −u hãa 9 2.1. Bµi to¸n tèi −u hãa tæng qu¸t 9 2.2. C¸c bµi to¸n tèi −u 9 Ch−¬ng 3: Bµi to¸n tèi −u tuyÕn tÝnh 11 3.1. Mét sè vÝ dô vÒ bµi to¸n tèi −u 11 3.2. Ph¸t biÓu bµi to¸n 11 3.3. TÝnh ®èi ngÉu vµ ®Þnh lý c¬ b¶n cña tèi −u tuyÕn tÝnh 12 3.4. C¸c ph−¬ng ph¸p gi¶i bµi to¸n tèi −u tuyÕn tÝnh 13 3.5. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n tèi −u tæng qu¸t 18 Ch−¬ng 4: Bµi to¸n tèi −u nguyªn tuyÕn tÝnh 21 4.1. Bµi to¸n tèi −u nguyªn tuyÕn tÝnh 21 4.2. Mét sè m« h×nh thùc tiÔn 21 Ch−ong 5; Bµi to¸n tèi −u ®éng 25 5.1. B¶n chÊt bµi to¸n tèi −u ®éng 25 5.2. Qu¸ tr×nh ph©n phèi nhiÒu b−íc 26 5.3. CÊu tróc qu¸ tr×nh tèi −u ®éng 33 5.4. Ph−¬ng tr×nh ®iÒu khiÓn tèi −u c¸c dù tr÷ 39 Ch−¬ng 6: Bµi to¸n tèi −u phi tuyÕn kh«ng rµng buéc 41 6.1. Më ®Çu 41 6.2. §iÒu kiÖn tèi −u cña bµi to¸n kh«ng rµng buéc 41 6.3. C¸c ph−ong ph¸p dïng ®¹o hµm 42 6.4. C¸c ph−¬ng ph¸p dïng ®¹o hµm 45 Ch−¬ng 7: Bµi to¸n tèi −u phi tuyÕn cã rµng buéc 49 7.1. Më ®Çu 49 7.2. Ph−¬ng ph¸p Gradient 50 7.3. Ph−¬ng ph¸p hµm ph¹t 53 Ch−¬ng 8: Quy ho¹ch thùc nghiÖm 55 8.1. Kh¸i niÖm vÒ nhËn d¹ng m« h×nh thèng kª 55 8.2. Ph−¬ng ph¸p b×nh ph−¬ng bÐ nhÊt 55 8.3. M« h×nh håi quy tuyÕn tÝnh béi 56 Tµi liÖu tham kh¶o 59 2
Ch−¬ng 1: C¥ Së §¹I Sè TUYÕN TÝNH ViÖc nghiªn cøu c¸c bµi to¸n tèi −u tuyÕn tÝnh ®ßi hái ph¶i sö dông mét phÇn cña to¸n häc, mµ nh÷ng phÇn ®ã ch−a ®−îc nghiªn cøu trong c¸c gi¸o tr×nh c¬ së. Trong ®ã tr−íc hÕt ph¶i nãi ®Õn ®¹i sè tuyÕn tÝnh. KiÕn thøc quan träng nhÊt ®Ó nghiªn cøu c¸c bµi to¸n tèi −u tuyÕn tÝnh lµ c¸c phÐp tÝnh vÒ ma trËn, c¸ch gi¶i c¸c hÖ ph−¬ng tr×nh vµ bÊt ph−¬ng tr×nh tuyÕn tÝnh. ë ®©y sÏ kh«ng chøng minh mét sè mÖnh ®Ò mµ chØ kh¼ng ®Þnh. 1.1. Ma trËn vµ c¸c phÐp tÝnh ®èi víi ma trËn 1.1.1. Ma trËn: Ma trËn lµ mét b¶ng ch÷ nhËt gåm m.n sè s¾p thµnh m hµng n cét d−íi d¹ng: a11 a12 .... a1n a21 a22 .... a2n ... ... .... ... am1 am2 .... amn PhÇn tö cña ma trËn ký hiÖu aij, chØ sè thø nhÊt ký hiÖu chØ sè hµng, chØ sè thø hai chØ sè cét cña ma trËn chøa phÇn tö aij. Sè hµng (m) vµ sè cét (n) cña ma trËn x¸c ®Þnh kÝch thø¬c cña ma trËn, ta nãi ma trËn cã kÝch th−íc m.n. Ma trËn gåm c¸c phÇn tö aij th−êng ®−îc ký hiÖu b»ng ch÷ in hoa: A. Ma trËn cã nhiÒu ký hiÖu kh¸c nhau. Ma trËn A cã thÓ ®−îc viÕt d−íi d¹ng: ⎡a 11 a 12 ... a 1n ⎤ A= ⎢...21 ⎢ a a 22 ... ... ... a 2n ⎥ ... ⎥ (1.1) ⎢a m1 ⎣ a m2 ... a mn ⎥ ⎦ Ma trËn cã sè hµng b»ng sè cét (m=n) ®−îc gäi lµ ma trËn vu«ng. Lóc ®ã, ng−êi ta nãi r»ng ma trËn vu«ng cã cÊp n. Ma trËn mµ c¸c cét cña nã lµ c¸c hµng t−¬ng øng cña ma trËn ban ®Çu A th× ®−îc gäi lµ ma trËn chuyÓn vÞ cña ma trËn A vµ ®−îc ký hiÖu lµ AT, tøc lµ: ⎡a 11 a 21 ... a m1 ⎤ ⎢a 12 a 22 ... a m2 ⎥ AT = ⎢... ... ... ... ⎥ (1.2) ⎢a 1n ⎣ a 2n ... a mn ⎥ ⎦ 1.1.2. C¸c d¹ng ma trËn: Ma trËn chØ cã mét cét ®−îc gäi lµ vect¬ cét, cßn ma trËn chØ cã mét hµng gäi lµ vect¬ hµng. Ma trËn vu«ng cã d¹ng: ⎡α 1 ... 0 ⎤ ⎢ 0 α ... 0 ⎥ ⎢ 2 ⎥ ⎢ ............... ⎥ ⎢ ⎥ ⎣0 0 αn ⎦ §−îc gäi lµ ma trËn ®−êng chÐo. NÕu ma trËn ®−êng chÐo cã tÊt c¶ αi= 1 th× ®−îc gäi lµ ma trËn ®¬n vÞ vµ th−êng ®−îc ký hiÖu lµ E. VÝ dô: 3
⎡1 0 0 0⎤ ⎢0 1 0 0⎥ E= ⎢ ⎥ ⎢0 0 1 0⎥ ⎢ ⎥ ⎣0 0 01 ⎦ Hai ma trËn b»ng nhau chØ trong tr−êng hîp chóng cã cïng kÝch th−íc vµ c¸c phÇn tö t−¬ng øng b»ng nhau. NÕu ma trËn A cã ®Þnh thøc kh¸c kh«ng th× ®−îc gäi lµ ma trËn kh«ng kú dÞ (kh«ng suy biÕn). Trong tr−êng hîp ng−îc l¹i ma trËn A ®−îc gäi lµ ma trËn kú dÞ hoÆc lµ ma trËn suy biÕn. 1.1.3. PhÐp tÝnh ®èi víi ma trËn Muèn nh©n ma trËn víi mét h»ng sè (v« h−íng) ta nh©n mçi phÇn tö cña ma trËn víi sè ®ã. ⎡αa 11 αa 12 ... αa 1n ⎤ ⎢αa αa ... αa ⎥ αA = ⎢... 21 .... 22 ... ... 2n ⎥ (1.3) ⎢αa m1 αa m2 ... αa mn ⎥ ⎣ ⎦ Tæng cña hai ma trËn A vµ B cã cïng kÝch th−íc lµ ma trËn C míi mµ mçi phÇn tö cña nã b»ng tæng c¸c phÇn tö t−¬ng øng cña ma trËn A vµ B tøc lµ: ⎡a 11 a 12 ... a 1n ⎤ ⎡ b11 b12 ... b1n ⎤ ⎡ a 11 + b11 a 12 + b12 ...a 1n + b1n ⎤ ⎢ a 21 a 22 ... a 2n ⎥ ⎢ b 21 b 22 ... b 2n ⎥ ⎢ a 21 + b21 a 22 + b22 ...a 2n + b2 n ⎥ A+B = ⎢ ... ... ... ... ⎥ + ⎢ ... ... ... ... ⎥ = ⎢ ... ... ... ... ... ... ... ⎥ = C (1.4) ⎢ a m1 a m2 ... a mn ⎥ ⎢ b m1 b m2 ... b mn ⎥ ⎢ a m1 + bm1 a m2 + bm 2 ...a mn + bmn ⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ Ma trËn A nh©n ®−îc víi ma trËn B chØ trong tr−êng hîp sè cét cña ma trËn A b»ng sè hµng cña ma trËn B. NÕu ma trËn A cã kÝch th−íc m.n, cßn ma trËn B lµ n.l, th× kÝch th−íc cña ma trËn C lµ tÝch ma trËn Avµ B sÏ lµ m.l. Vµ mçi phÇn tö cña ma trËn C ®−îc tÝnh theo c«ng thøc: cij = ai1b1j +ai2b2j + ... + ain bnj (1.5) ë ®©y ai1, ai2 ..., ain lµ c¸c phÇn tö hµng thø i cña ma trËn A; cßn b1j, b2j ..., bnj lµ c¸c phÇn tö cét thø j cña ma trËn B. 1/ TÝch ma trËn kh«ng cã tÝnh chÊt giao ho¸n, tøc lµ nãi chung: AB ≠ BA; 2/ (AB)C = A(BC) (luËt kÕt hîp); 3/ (A+B)C = AC + BC; C (A+B) = CA + CB (luËt ph©n bè); 4/ α(AB) = (αA)B = A(αB); 5/ AE = EA = A; PhÐp chuyÓn vÞ ma trËn cã tÝnh chÊt sau: 1/ (A + B)T = AT + BT 2/ (AB)T = BT.AT Lòy thõa ma trËn vu«ng A ®−îc ®Þnh nghÜa nh− sau: Ak = A.A...A k lÇn vµ: Ak1Ak2 = Ak1+k2 1.2. §Þnh thøc vµ c¸c tÝnh chÊt cña chóng 1.2.1. Kh¸i niÖm vÒ ho¸n vÞ: Ta lÊy n sè ®Çu tiªn: 1,2 ... , n. Mçi c¸ch s¾p xÕp c¸c sè Êy theo mét thø tù nµo ®ã ®−îc gäi lµ ho¸n vÞ cña n sè. Nh− ta ®· biÕt sè c¸c ho¸n vÞ kh¸c nhau sÏ b»ng n!. 4
Sè αi vµ αj t¹o thµnh mét nghÞch thÓ trong hãan vÞ ®· cho nÕu αi > αj víi i < j. Sè c¸c nghÞch thÕ trong ho¸n vÞ I = (α1, α2 ,..., αn) b»ng: k1 + k2 + ... + kn-1 ë ®©y ks lµ sè tr−êng hîp αs lín h¬n αs+1, αs+2 , ... αn (s = 1, 2, ..., n-1) trong ho¸n vÞ I. Ho¸n vÞ ®−îc gäi lµ ho¸n vÞ ch½n nÕu sè nghÞch thÓ trong ho¸n vÞ I lµ sè ch½n, vµ ®−îc gäi lµ hãan vÞ lÎ nÕu sè c¸c nghÞch thÓ lµ sè lÎ. VÝ dô ®èi víi ho¸n vÞ 5, 2, 3, 4,1 th× sè tÊt c¶ c¸c nghÞch thÕ b»ng: k1 + k2 + k3 + k4 = 4 +1 +1 +1 = 7. V× vËy, hãan vÞ nµy lµ hãan vÞ lÎ. 1.2.2. Kh¸i niÖm vÒ ®Þnh thøc vµ phÐp tÝnh cña chóng: Sè b»ng tæng ®¹i sè cña tÊt c¶ c¸c tÝch nh÷ng phÇn tö ma trËn vu«ng A mµ trong ®ã mçi tÝch chØ gåm c¸c phÇn tö kh¸c hµng, kh¸c cét cña ma trËn, tøc lµ tæng c¸c tÝch cã d¹ng: a1j1 a2j2 ... anjn (1.6) ®−îc gäi lµ ®Þnh thøc cña ma trËn A (Sè tÝch ®ã b»ng n!). Mçi tÝch nh− thÕ lÊy dÊu céng nÕu ho¸n vÞ t−¬ng øng lµ ch½n, cßn lÊy dÊu trõ, nÕu lÎ. Khi t×m h¹ng cña ma trËn, ma trËn nghÞch ®¶o vµ gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh ta sÏ cÇn ®Õn ®Þnh thøc. §Þnh thøc cña ma trËn A th−êng ®−îc ký hiÖu lµ ∆n hoÆc |A|. a11 a12 ...a1n ∆n = |A| = .............a 2 n = | aij a 21 a 22 n ... 1 (1.7) a n1 a n 2 ...a nn C¸c phÇn tö, c¸c hµng, c¸c cét vµ cÊp cña ma trËn A t−¬ng øng víi c¸c phÇn tö, c¸c hµng, c¸c cét vµ cÊp cña ®Þnh thøc |A|. VÝ dô: ta tÝnh ®Þnh thøc cÊp 3 theo quy t¾c võa nªu ra: a11a12 a13 ∆3 = a21a22 a23 = a11a22a33 + a12a23a31 + a13a21a32 - a13a22a31 - a12a21a33 - a11a23a32 a31a32 a33 Ba sè h¹ng ®Çu lÊy dÊu céng, cßn ba sè h¹ng sau lÊy dÊu trõ, bëi v× ho¸n vÞ 1,2,3; 2,3,1 vµ 3,1,2 lµ ch½n (sè nghÞch thÓ t−¬ng øng lµ 0, 2 vµ 2) cßn c¸c hãan vÞ 3,2,1 ; 2,1,3 vµ 1,3,2 lµ hãan vÞ lÎ (sè nghÞch thÓ t−¬ng øng lµ 3,1 vµ 1). VÝ dô: 2 4 1 ∆3 = 3 0 - 1 = 2.0.3 + 4(-1) .1 +1.3(-2) -[1.0.1+4.3.3+2(-1).(-2)] = -50. 1 -2 3 1.2.2. §Þnh thøc con vµ phÇn phô ®¹i sè: §Þnh thøc cÊp (n-1) cã tõ ®Þnh thøc cÊp n (∆n) b»ng c¸ch bá hµng i cét j ®−îc gäi lµ ®Þnh thøc con øng víi phÇn tö aij cña ®Þnh thøc ∆n vµ ®−îc ký hiÖu lµ Mij. Ta coi ®Þnh thøc cÊp n: a 11 a 12 ... a 1j ... a 1n a 21 a 22 ... a 2j ... a 2n ... ∆n = a ... ... ... ... ... i1 a i2 ... a ij ... a in ... ... ... ... ... ... a n1 a n2 ... a nj ... a nn Khi ®ã ®Þnh thøc con cña phÇn tö aij sÏ lµ ®Þnh thøc cÊp (n-1): 5
a 11 a 12 ... a 1j-1 a 1j+1 ... a 1n a 21 a 22 ... a 2j-1 a 2j+1 ... a 2n ... ... ... ... ... ... Mij = a i-11a i-12 ... a i-1, j-1 a i-1, j+1 ... a i-1,n a i-11a i-12 ... a i-1, j-1 a i-1, j+1 ... a i-1,n ... ... ... ... ... .... ..... a n1 a n2 ... a nj-1 a nj+1 ... a nn VÝ dô: ®Þnh thøc con cña phÇn tö a22 cña ®Þnh thøc: 2 4 1 2 1 ∆3= 3 0 - 1 sÏ lµ: M22 = = 2.3 -1.1 = 6-1 = 5 1 2 1 -2 3 §Þnh thøc con cña phÇn tö aij nh©n víi (-1) víi sè mò b»ng tæng c¸c chØ sè cña phÇn tö ®ã (i + j) ®−îc gäi lµ phÇn phô ®¹i sè cña phÇn tö aij vµ ®−îc ký hiÖu lµ Aij. V× vËy: Aij = (-1)i+j Mij (1.10) Ch¼ng h¹n, phÇn phô ®¹i sè cña phÇn tö a22 ë vÝ dô võa råi sÏ lµ: A22=(-1)2+2.5=5 1.3. Ma trËn nghÞch ®¶o vµ h¹ng cña ma trËn 1.3.1. Ma trËn nghÞch ®¶o: §èi víi mçi ma trËn A kh«ng suy biÕn sÏ tån t¹i mét ma trËn (ký hiÖu A-1) tháa m·n ®iÒu kiÖn: A-1A = AA-1 = E (1.17) Ma trËn A-1 ®−îc gäi lµ ma trËn nghÞch ®¶o cña ma trËn A vµ ®−îc tÝnh theo c«ng thøc: A* A-1 = (1.18) | A| §«i khi ma trËn A* ®−îc gäi lµ ma trËn phô hîp cña ma trËn A. PhÇn tö hµng i cét j cña ma trËn A* lµ phÇn phô ®¹i sè cña phÇn tö aij cña ma trËn A. Tõ ®ã: ⎡ A 11 A 21 A n1 ⎤ ⎢ | A | | A | ... | A | ⎥ A-1 = ⎢ ... ... ... ... ⎢A A ⎥ ⎥ (1.18a) ⎢ 1n 2n A ⎥ ... nn ⎢ |A| |A| |A| ⎣ ⎥ ⎦ ⎡2 3 2 ⎤ VÝ dô ta lÊy ma trËn cÊp 3: A = ⎢ 1 2 1⎥ ⎢ ⎥ ⎢3 1 ⎥ ⎣ ⎦ Tr−íc khi ®i tÝnh ma trËn nghÞch ®¶o, cÇn x¸c ®Þnh ma trËn A cho ë ®©y kh«ng ph¶i lµ ma trËn suy biÕn, tøc lµ ®Þnh thøc cña nã kh¸c kh«ng. §Þnh thøc cña ma trËn ®ã sÏ b»ng: | A | = 2.2.1 +3.1.3 +2.1.1 - 2.2.3 -3.1.1 - 2.1.1= -2 Sau ®ã ta tÝnh c¸c phÇn phô ®¹i sè cña c¸c phÇn tö cña ma trËn A11 = ( -1)1+1 1 1 = 2.1-1.1 =1 2 1 A12 = ( -1)1+2 1 1 = -(1.1-3.1) = 2 3 1 A13 = ( -1)1+3 1 2 =1.1-2.3 = -5 3 1 T−¬ng tù ta t×m ®−îc c¸c Aij cßn l¹i: A21 = -1 ; A22 = - 4; A23 = 7; A31 = -1 ; A32 = 0; A33= 1. 6
⎡- 1/2 - 1 5/2 ⎤ Do ®ã ta cã: A -1 = ⎢ - 1 2 7/2⎥ ⎢ ⎥ ⎢ 1/2 0 - 1/2⎥ ⎣ ⎦ ¸p dông quy t¾c nh©n ma trËn, ®em nh©n ma trËn A víi ma trËn A-1 võa t×m ®−îc ta dÔ dµng thÊy ®−îc kÕt qu¶ lµ mét ma trËn ®¬n vÞ. Vµ cã thÓ dïng c¸ch nµy ®Ó kiÓm tra viÖc tÝnh ma trËn nghÞch ®¶o cã ®óng kh«ng. Ma trËn nghÞch ®¶o cña ma trËn ®¬n vÞ còng lµ ma trËn ®¬n vÞ. §iÒu nµy suy ra tõ viÖc nh©n ma trËn bÊt kú víi ma trËn ®¬n vÞ ®−îc ®óng ma trËn ®ã. Dïng c¸c quy t¾c ®· nªu ë trªn ta nh©n hai ma trËn ®¬n vÞ víi nhau. ⎡ 1 0 0⎤ ⎡ 1 0 0⎤ ⎡ 1 0 0⎤ EE = ⎢ 0 1 0⎥ ⎢ 0 1 0⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ 0 1 0⎥ ⎢ ⎥ ⎢ 0 0 0⎥ ⎢ 0 0 0⎥ ⎣ ⎦ ⎣ ⎦ ⎢ 0 0 0⎥ ⎣ ⎦ Tõ ®ã suy ra r»ng E-1 = E Còng cã thÓ chøng minh ®iÒu ®ã b»ng c¸ch tÝnh trùc tiÕp ma trËn nghÞch ®¶o theo c«ng thøc (1.18). 1.4. HÖ ph−¬ng tr×nh tuyÕn tÝnh 1.4.1. D¹ng cña hÖ ph−¬ng tr×nh tuyÕn tÝnh: D¹ng tæng qu¸t cña hÖ ph−¬ng tr×nh tuyÕn tÝnh ®−îc viÕt nh− sau: a11x1 + a12x2 + ... a1nxn = b1 a21x1 + a22x2 + ... a2nxn = b2 (1.20) ..................................... am1x1 + am2x2 + ... amnxn = bm HÖ nµy ®−îc viÕt d−íi d¹ng ma trËn lµ: AX = B (1.20a) ë ®©y A lµ ma trËn ®−îc thµnh lËp tõ c¸c hÖ sè cña c¸c biÕn: A = (aij) víi i = 1,2,..., m; j = 1, 2,..., n. X - lµ vÐct¬ cét cña c¸c biÕn ⎡ x1 ⎤ ⎢ x2 ⎥ X =⎢ . ⎥ (1.21) ⎢ xn ⎥ ⎣ ⎦ B - lµ vÐct¬ cét c¸c sè h¹ng tù do ⎡ b1 ⎤ ⎢ b2 ⎥ B = ⎢. ⎥ (1.22) ⎢bm ⎥ ⎣ ⎦ HÖ ph−¬ng tr×nh tuyÕn ®−îc gäi lµ: ThuÇn nhÊt, nÕu tÊt c¶ c¸c bi = 0 (i = 1, 2 .... m) vµ kh«ng thuÇn nhÊt, nÕu cã Ýt nhÊt mét bi ≠ 0. T−¬ng thÝch, nÕu hÖ cã Ýt nhÊt mét nghiÖm, tøc lµ tån t¹i mét bé sè mµ khi thay vµo ph−¬ng tr×nh sÏ cã mét ®ång nhÊt thøc, vµ gäi lµ kh«ng t−¬ng thÝch nÕu kh«ng cã mét nghiÖm nµo; x¸c ®Þnh nÕu hÖ chØ cã mét nghiÖm duy nhÊt, vµ bÊt ®Þnh nÕu tån t¹i qu¸ mét nghiÖm. Muèn gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh, th× tr−íc hÕt ph¶i x¸c ®Þnh xem hÖ ®· cho t−¬ng thÝch hay lµ kh«ng t−¬ng thÝch. NÕu lµ hÖ t−¬ng thÝch th× l¹i ph¶i xem hÖ lµ x¸c ®Þnh hay bÊt ®Þnh. 7
NÕu hÖ ph−¬ng tr×nh lµ x¸c ®Þnh th× ta ®i t×m nghiÖm duy nhÊt cña nã. 1.4.2. Gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh: Khi gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh cã thÓ x¶y ra hai tr−êng hîp: n =m vµ n ≠m. Tr−íc hÕt lµ ta xÐt tr−êng hîp n = m. Lóc ®ã ma trËn A sÏ cã d¹ng: ⎡a 11 a 12 ... a 1n ⎤ ⎢ a 21 a 22 ... a 2n ⎥ A = ⎢ ... ... ... ... ⎥ ⎢ a n1 ⎣ a n2 ... a nn ⎥ ⎦ Gi¶ thiÕt ma trËn A kh«ng suy biÕn, tøc lµ | A| ≠ 0, khi ®ã sÏ tån t¹i ma trËn nghÞch ®¶o A-1. Ta nh©n vÕ tr¸i vµ vÕ ph¶i cña ®¼ng thøc (1.20a) víi A-1 vÒ bªn tr¸i. Ta sÏ ®−îc: A-1AX = A-1B. Bëi v× A-1A = E mµ nh©n bÊt cø ma trËn nµo víi E sÏ ®−îc ®óng ma trËn ®ã, nªn: X = A-1B (1.23) Sau khi thÕ A-1 bëi biÓu thøc (1.18a) vµ thay c¸c vÐct¬ cét X vµ B ë (1.21) vµ (1.22) råi nh©n ma trËn A-1 víi B ta cã: ⎡ x1 ⎤ ⎡ A11b1 + A21b2 + ... + An1bn ⎤ ⎢ x 2 ⎥ = 1 ⎢ A12 b1 + A22 b2 + ... + An 2 bn ⎥ ⎢ . ⎥ | A| ⎢ . . . ⎥ ⎢ xn ⎥ ⎣ ⎦ ⎢ A1n b1 + A2 n b2 + ... + Ann bn ⎥ ⎣ ⎦ V× hai ma trËn chØ b»ng nhau khi c¸c phÇn tö t−¬ng øng cña chóng b»ng nhau, nªn 1 x1 = (A11b1 + A21b2 + ... An1bn) | A| ....................................................... 1 xi = (A1ib1 + A2ib2 + ... Anibn) (1.23a) | A| ....................................................... 1 xn = (A1nb1 + A2nb2 + ... Annbn) | A| Ta xÐt tr−êng hîp thø hai (m ≠n). Ta gäi ma trËn: ⎡a 11 a 12 ... a 1n ⎤ A = ⎢ ... ... ... ... ⎥ lµ ma trËn c¬ së cña hÖ. ⎢ a m1 a m2 ... a mn ⎥ ⎣ ⎦ Sau khi thªm cét c¸c sè h¹ng tù do vµo ma trËn A ta lËp ®−îc ma trËn më réng B: ⎡a 11 a 12 ... a 1n b1 ⎤ B = ⎢ ... ... ... ... ⎥ (1.26) ⎢ a m1 a m2 ... a mn bm ⎥ ⎣ ⎦ Tõ ®ã, ta cã ®Þnh lý Cr«necke - Capeli: §Ó hÖ ph−¬ng tr×nh tuyÕn tÝnh lµ t−¬ng thÝch, ®iÒu kiÖn cÇn vµ ®ñ lµ h¹ng cña ma trËn c¬ së vµ ma trËn më réng b»ng nhau. NÕu h¹ng cña chóng b»ng nhau vµ sè Èn b»ng h¹ng cña ma trËn c¬ së th× hÖ cã nghiÖm duy nhÊt. NÕu h¹ng cña ma trËn A nhá h¬n sè Èn th× hÖ cã v« sè nghiÖm. HÖ ph−¬ng tr×nh tuyÕn tÝnh thuÇn nhÊt lu«n lu«n t−¬ng thÝch, bëi v× lu«n lu«n cã nghiÖm kh«ng, ®−îc gäi lµ nghiÖm tÇm th−êng. NÕu h¹ng cña ma trËn b»ng sè Èn th× hÖ thuÇn nhÊt chØ cã duy nhÊt mét nghiÖm lµ kh«ng. Muèn hÖ tån t¹i nghiÖm kh¸c kh«ng th× h¹ng cña ma trËn c¬ së ph¶i nhá h¬n sè Èn. 8
Ch−¬ng 2: Kh¸i niÖm vÒ c¸c bµi to¸n tèi −u ho¸ 2.1. Bµi to¸n tèi −u ho¸ tæng qu¸t 2.1.1. Ph¸t biÓu: T×m tr¹ng th¸i tèi −u cña mét hÖ thèng sao cho ®¹t ®−îc môc tiªu mong muèn vÒ chÊt l−îng theo mét nghÜa nµo ®ã. 2.1.2. C¸c yÕu tè cña mét bµi to¸n tèi −u ho¸: Mét bµi to¸n tèi −u ho¸ cã ba yÕu tè c¬ b¶n sau: * Tr¹ng th¸i: m« t¶ tr¹ng th¸i cña hÖ thèng cÇn tèi −u ho¸. * Môc tiªu: ®Æc tr−ng cho tiªu chuÈn hoÆc hiÖu qu¶ mong muèn (chi phÝ Ýt nhÊt, hiÖu suÊt cao nhÊt, träng l−îng nhá nhÊt, thêi gian ng¾n nhÊt, ...). * Rµng buéc: thÓ hiÖn c¸c ®iÒu kiÖn kinh tÕ, kü thuËt ... mµ hÖ thèng ph¶i tháa m·n. 2.2. C¸c bµi to¸n tèi −u 2.2.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh: HÖ thèng ë tr¹ng th¸i tÜnh cã c¸c biÕn tr¹ng th¸i lµ: x = [ x1, x2 , ..., xn]T (2.1) Môc tiªu ®−îc diÔn ®¹t bëi hµm môc tiªu cã d¹ng tuyÕn tÝnh: Z = c.x; víi c = [c1, c2, ..., cn]T (2.2) C¸c rµng buéc ®−îc diÔn ®¹t bëi nh÷ng ph−¬ng tr×nh, bÊt ph−¬ng tr×nh tuyÕn tÝnh: A.x = b; A.x ≤ b (2.3) A = (aij), i = 1, ... , m ; j = 1, ...., n ; b = [b1, b2,..., bm] . T Bµi to¸n: T×m tr¹ng th¸i tèi −u x* = [x * , x *2 , ..., x * ]T cña tr¹ng th¸i (2.1) víi c¸c rµng buéc 1 n (2.3) sao cho hµm môc tiªu (2.2) ®¹t gi¸ trÞ nhá nhÊt (Min) hoÆc gi¸ trÞ lín nhÊt (Max). 2.2.2. Bµi to¸n quy ho¹ch phi tuyÕn: HÖ thèng ë tr¹ng th¸i tÜnh. T×m tr¹ng th¸i tèi −u x* khi hµm môc tiªu ®−îc diÔn ®¹t bëi mét hµm phi tuyÕn f(x) hoÆc cã Ýt nhÊt mét rµng buéc phi tuyÕn: gr (x) ≤ 0; r = 1,...., m. 2.2.3. Bµi to¸n cùc trÞ phiÕm hµm: HÖ thèng ë tr¹ng th¸i tÜnh hoÆc tr¹ng th¸i ®éng. BiÕn tr¹ng th¸i lµ z(x) víi x lµ biÕn ®éc lËp. Môc tiªu ®−îc diÔn ®¹t bëi phiÕm hµm môc tiªu: x1 . J(z) = ∫ L( z, z, x)dx xn . . . . . víi z = [z1(x), z2(x),.... zn(x)]T; z = [ z1 ( x), z 2 ( x),...., z n ( x)]T ; z i ( x) = dz i / dx Rµng buéc cã thÓ lµ c¸c hµm phi tuyÕn, c¸c ph−¬ng tr×nh ®¹i sè hoÆc c¸c ph−¬ng tr×nh vi ph©n. 2.2.4. Bµi to¸n ®iÒu khiÓn tèi −u: * §èi víi hÖ liªn tôc: HÖ thèng ë tr¹ng th¸i ®éng, tr¹ng th¸i ®−îc m« t¶ bëi hÖ ph−¬ng tr×nh vi ph©n: & x = f(t,x,u); t - thêi gian trong ®ã x = [ x1 , x 2 ..., x n ]T; x i = dxi /dt; & & & & & T u = [u1,..., un] ; u - ®iÒu khiÓn Môc tiªu cã d¹ng phiÕm hµm: t1 J(u) = ∫ L (t, x, x, u) dt & tn * §èi víi hÖ rêi r¹c: 9
HÖ thèng ë tr¹ng th¸i ®éng, tr¹ng th¸i ®−îc m« t¶ bëi ph−¬ng tr×nh: xk+1 = f(xk,uk); x(0) = x0, x(N,T0) = xN ∈ X Môc tiªu cã d¹ng: N −1 J(u) = ∑f k =0 0 ( x k , u k ) → min; uk∈Ω Bµi to¸n ®Æt ra: CÇn ph¶i t×m ®iÒu khiÓn tèi −u u* vµ tr¹ng th¸i tèi −u x* ®Ó hÖ thèng chuyÓn tõ tr¹ng th¸i ®Çu ®Õn tr¹ng th¸i cuèi sao cho môc tiªu J(u) ®¹t Min hoÆc Max. C¸c bµi to¸n tèi −u cã tr¹ng th¸i tÜnh ®−îc gäi lµ bµi to¸n tèi −u ho¸ tÜnh, c¸c bµi to¸n cã tr¹ng th¸i phô thuéc thêi gian ®−îc gäi lµ bµi to¸n tèi −u ho¸ ®éng. Tr¹ng th¸i cña hÖ thèng cã thÓ ë d¹ng liªn tôc hoÆc gi¸n ®o¹n. Trong bµi to¸n tèi −u cã thÓ ®Æt ra mét môc tiªu hoÆc nhiÒu môc tiªu. 10
Ch−¬ng 3: bµi to¸n tèi −u tuyÕn tÝnh 3.1. Mét sè vÝ dô vÒ bµi to¸n tèi −u tuyÕn tÝnh 3.1.1. Bµi to¸n vËn t¶i: Cã m ®iÓm s¶n xuÊt cïng 1 lo¹i s¶n phÈm a vµ n ®iÓm tiªu thô b. Cho r»ng trong 1 m n ®¬n vÞ thêi gian l−îng cung vµ cÇu b»ng nhau: ∑ ai = ∑ b j i =1 j =1 Gäi xij ≥ 0 vµ cij lÇn l−ît lµ l−îng s¶n phÈm vµ chi phÝ vËn chuyÓn tõ ®iÓm i ®Õn j.. T×m ph−¬ng ¸n chuyªn chë sao cho chi phÝ chuyªn chë lµ nhá nhÊt. m n Z= ∑∑ i =1 j =1 cijxij → Min 3.1.2. Bµi to¸n ph©n phèi kÕ ho¹ch s¶n xuÊt: Cã n xÝ nghiÖp s¶n xuÊt m lo¹i chi tiÕt. Gäi: ai: sè chi tiÕt lo¹i i; bj: quü thêi gian giµnh cho s¶n xuÊt ë xÝ nghiÖp j; xij: sè chi tiÕt lo¹i i cña xÝ nghiÖp j; cij: chi phÝ cho chi tiÕt i ë xÝ nghiÖp j; λij: thêi gian s¶n xuÊt 1 chi tiÕt lo¹i i ë xÝ nghiÖp j. T×m xij, (i = 1 ÷m; j = 1 ÷ n) sao cho hoµn thµnh khèi l−îng trong quü thêi gian cho phÐp víi chi phÝ Ýt nhÊt, nghÜa lµ: m n Hµm môc tiªu Z = ∑∑ i =1 j =1 cij xij → min C¸c ®iÒu kiÖn rµng buéc: n m ∑ xij = ai ; i = 1 ÷ m ; j =1 ∑λ j =1 ij ≤ b j ; x ij ≥ 0. 3.1.3. Bµi to¸n thùc ®¬n: ChÊt dinh d−ìng Nhu cÇu tèi thiÓu hµng ngµy Lo¹i thøc ¨n P1 P2 N1 b1 a11 a12 N2 b2 a21 a22 N3 b3 a31 a32 N4 b4 a41 a42 Gi¸ tiÒn ®¬n vÞ thøc ¨n c1 c2 TiÒn thøc ¨n hµng ngµy: Z = c1x1 + c2x2. T×m l−îng x1, x2 cña tõng lo¹i thøc ¨n sao cho Z → Min víi c¸c rµng buéc: a11 x1 + a12 x2 ≥ b1 ........................... a41 x1 + a42 x2 ≥ b4 xi ≥ 0 3.2. Ph¸t biÓu bµi to¸n 3.2.1. §Þnh nghÜa: Bµi to¸n tèi −u tuyÕn tÝnh chuyªn nghiªn cøu ph−¬ng ph¸p t×m gi¸ trÞ nhá nhÊt (Min) hoÆc gi¸ trÞ lín nhÊt (Max) cña mét hµm tuyÕn tÝnh theo mét sè biÕn, tho¶ m·n mét sè h÷u h¹n rµng buéc ®−îc biÓu diÔn b»ng hÖ ph−¬ng tr×nh vµ bÊt ph−¬ng tr×nh tuyÕn tÝnh. 3.2.2. Hai d¹ng c¬ b¶n cña bµi to¸n tèi −u tuyÕn tÝnh: 1. D¹ng chÝnh t¾c: rµng buéc ë d¹ng ®¼ng thøc. 11
⎡a11 ........a1n ⎤ §Æt A = ⎢................. ⎥ ⎢a m1 ........a mn ⎥ ⎣ ⎦ A ®−îc gäi lµ ma trËn hÖ sè cña c¸c rµng buéc. ⎡x1 ⎤ ⎡c1 ⎤ ⎡b1 ⎤ ⎢ x 2 ⎥ ; x ≥ 0; c = ⎢c 2 ⎥ ; b = ⎢b2 ⎥ x = ⎢. ⎥ j ⎢. ⎥ ⎢. ⎥ ⎢ xn ⎥ ⎣ ⎦ ⎢c n ⎥ ⎣ ⎦ ⎢bm ⎥ ⎣ ⎦ T×m c¸c gi¸ trÞ tèi −u x* = [x*1 , ....,x*n]T sao cho hµm môc tiªu: n Z = cx = ∑c j =1 j x j → Max víi c¸c rµng buéc: Ax = b x≥0 2. D¹ng chuÈn: rµng buéc ë d¹ng bÊt ®¼ng thøc. T×m x sao cho Z = c.x → Max víi c¸c rµng buéc: Ax ≤ b x≥0 3.2.3. ChuyÓn bµi to¸n tèi −u tuyÕn tÝnh vÒ d¹ng chuÈn hoÆc d¹ng chÝnh t¾c 1. Thªm vµo c¸c biÕn phô: w = [xn +1, ..., xn+m]T Khi ®ã A.x ≤ b → A.x + E.w = b ; E: ma trËn ®¬n vÞ. VÝ dô: 2x 1 + x 2 ≤ 15 2x 1 + x 2 + x 3 = 15 0,5x 1 + 3x 2 ≤ 18 0,5x 1 + 3 x 2 + x 4 = 18 x1 ≤ 12 x1 + x5 = 12 x2 ≤ 9 → x2 + x6 = 9 x1 ≥ 0 ; x 2 ≥ 0 x j ≥ 0 ; j =1÷ 6 Z = 4 x1 + 7 x 2 Z = 4 x1 + 7 x 2 + 0.x3 + ... + 0.x6 2. NÕu rµng buéc ë d¹ng A.x ≥ b: nh©n hai vÕ víi (-1): n - ∑a j =1 ij x j ≤ −bi khi ®ã ta cã: A1.x ≤ B1 3. NÕu rµng buéc ë d¹ng ®¼ng thøc: A.x = b cã thÓ thay b»ng hai rµng buéc bÊt ®¼ng thøc A.x ≤ b vµ -A.x ≤ -b. 3.2.4. Quan hÖ gi÷a bµi to¸n Min vµ bµi to¸n Max: Trong bµi to¸n min: Z = c.x → Min NÕu ®Æt Z1 = - c.x → Max. Gäi x* lµ tr¹ng th¸i tèi −u Z1 tøc lµ - c.x* = Max(Z1) khi ®ã: - c.x* ≥ - c.x hay c.x* ≤ c.x Chøng tá x còng lµ tr¹ng th¸i tèi −u cña bµi to¸n Min. Min (Z) = c.x* = - Max (Z1) = - Max (-Z). 3.3. TÝnh ®èi ngÉu vµ ®Þnh lý c¬ b¶n cña bµi to¸n tèi −u tuyÕn tÝnh 3.3.1. Bµi to¸n ®èi ngÉu: Bµi to¸n gèc (d¹ng chuÈn): t×m x = [x1,....,xn]T ®Ó hµm môc tiªu: Z = c.x → Max; c = [c1,..., cn)T; b = [b1,...,bm]T 12
⎧ Ax ≤ b Víi rµng buéc: ⎨ ⎩ x≥0 Ta cã bµi to¸n ®èi ngÉu t−¬ng ®−¬ng víi bµi to¸n d¹ng chuÈn: T×m y = [y1,...,ym]T ®Ó hµm môc tiªu V = b.y → Min ⎧ AT . y ≥ c Víi rµng buéc: ⎨ ⎩ y≥0 ChuÈn S¬ ®å ®èi ngÉu: x1 x2 ..... xn a1n ≤ b1 ®èi ngÉu y1 a11 a12 ...... y2 a21 a22 ...... a2n ≤ b2 ... ........................ ym am1 am2 ...... amn ≤ bm ≥ ≥ ≥ Min c1 c2 ...... cn Max Ng−êi ta ®· chøng minh ®−îc: Gi¸ trÞ tèi −u cña bµi to¸n chuÈn còng lµ gi¸ trÞ tèi −u cña bµi to¸n ®èi ngÉu, nghÜa lµ: c.x* = b.y*. 3.3.2. §Þnh lý c¬ b¶n cña bµi to¸n tèi −u tuyÕn tÝnh: §Þnh lý: Ph−¬ng ¸n tèi −u cña bµi to¸n tèi −u tuyÕn tÝnh chøa mét sè biÕn d−¬ng ®óng b»ng sè c¸c rµng buéc d¹ng ®¼ng thøc ®éc lËp ®−îc tho¶ m·n, c¸c biÕn cßn l¹i cã gi¸ trÞ kh«ng. VÝ dô: x = [x1, x2,..., x5]T → n=5 ⎧a11 x1 + .... + a15 x5 = b1 ⎪ C¸c rµng buéc: ⎨................................ → m = 3 ⎪a x + .... + a x = b ⎩ 31 1 35 5 3 do ®ã nghiÖm tèi −u cã 3 biÕn kh¸c kh«ng x* = [*, *, *, 0, 0]T. 3.4. C¸c ph−¬ng ph¸p gi¶i bµi to¸n tèi −u tuyÕn tÝnh 3.4.1. Ph−¬ng ph¸p ®å thÞ: Ph−¬ng ph¸p nµy ®−îc dïng khi sè biÕn sè ≤ 3. 1. Bµi to¸n ph¼ng: VÝ dô: T×m x* = [x1*, x2*] T sao cho Z = c1x1 + c2x2 → Max C¸c rµng buéc: a11 x1 + a12 x2 ≤ b1 a21x1 + a22 x2 ≤ b2 x1 ≥ 0, x2 ≥ 0 Gi¶i: VÏ miÒn chÊp nhËn ®−îc (miÒn D mµ x tho¶ m·n c¸c rµng buéc h×nh 3.1): + NÕu rµng buéc lµ ®¼ng thøc th× miÒn chÊp nhËn ®−îc lµ ®iÓm A, giao ®iÓm cña ®−êng N1M1 vµ N2M2. + NÕu lµ bÊt ®¼ng thøc th× miÒn chÊp nhËn ®−îc lµ h×nh AN1OM2, bao gåm c¶ biªn AN1, AM2. VÏ c¸c ®−êng cïng môc tiªu (®−êng møc): 13
z 0 c1 + Cho mét gi¸ trÞ cô thÓ Z = Z0. VÏ ®−êng x 2 = − x1 c1 c 2 Thay ®æi gi¸ trÞ Z0 ta ®−îc c¸c ®−êng song song. Trªn mçi ®−êng, hµm môc tiªu cã cïng gi¸ trÞ. Gi¸ trÞ Z0 cµng lín th× ®−êng x2 cµng xa 0. T×m nghiÖm tèi −u: + NghiÖm cùc ®¹i ®−îc x¸c ®Þnh bëi to¹ ®é ®iÓm A. + NÕu ®−êng cïng môc tiªu tiÕp xóc mét ®Ønh th× nghiÖm tèi −u lµ ®¬n trÞ. + NÕu ®−êng cïng môc tiªu tiÕp xóc 2 ®Ønh (1 c¹nh) th× nghiÖm lµ ®a trÞ. + NÕu miÒn chÊp nhËn ®−îc nh− h×nh 2.2 th× to¹ ®é ®iÓm A x¸c ®Þnh gi¸ trÞ cùc tiÓu. x2 x2=z9/c1 - (c1/c2)x1 x2 x2=z9/c1 - (c1/c2)x1 N2 N2 D N1 N1 A A x2* x2 D * O x1* M2 M1 x1 O x1* M2 M1 x1 H×nh 2.1 H×nh 2.2 2. Më réng: §èi víi bµi to¸n cã n biÕn x1,... , xn, chÞu m rµng buéc: 1/ NghiÖm tèi −u lµ to¹ ®é cña mét ®Ønh hay nhiÒu ®Ønh cña miÒn cho phÐp. MiÒn cho phÐp lµ mét ®a diÖn låi (n - m) chiÒu. 2/ NghiÖm lµ ®¬n trÞ nÕu 1 ®Ønh cña ®a diÖn cho phÐp tiÕp xóc víi mÆt cïng môc tiªu. 3/ NghiÖm lµ ®a trÞ nÕu tiÕp xóc t¹i k ®Ønh (k >1); k ®Ønh nµy t¹o nªn 1 ®¬n h×nh (k-1) chiÒu. Do ®ã cã thÓ lÊy (k-1) gi¸ trÞ c¸c biÕn tuú ý, cßn n - (k-1) biÕn kh¸c lµ hµm tuyÕn tÝnh cña (k-1) biÕn tuú ý. §ã sÏ lµ c¬ së cña ph−¬ng ph¸p ®¬n h×nh. Chó ý: §¬n h×nh lµ 1 h×nh cã sè ®Ønh nhiÒu h¬n 1 so víi sè chiÒu cña kh«ng gian. ThÝ dô, trong kh«ng gian 2 chiÒu th× ®¬n h×nh lµ tam gi¸c, trong kh«ng gian 3 chiÒu th× ®¬n h×nh lµ tø diÖn. 3.4.2. Ph−¬ng ph¸p ®¬n h×nh: Ph−¬ng ph¸p nµy do nhµ to¸n häc Mü G.B. Dantzig ®−a ra n¨m 1948. Néi dung: T×m ®Ønh tèi −u cña ®a diÖn c¸c nghiÖm cho phÐp b»ng ph−¬ng ph¸p lÇn l−ît thö c¸c ®Ønh cña ®a diÖn. §Ó viÖc thö kh«ng ph¶i mß mÉm, ng−êi ta ®−a ra thuËt to¸n ®Ó ®i tõ nghiÖm xÊu h¬n tíi nghiÖm tèt h¬n tøc ®i dÇn tíi nghiÖm tèi −u. 1. Néi dung ph−¬ng ph¸p ®¬n h×nh: Gi¶ sö cã m rµng buéc ®éc lËp ®−îc cho ë d¹ng chÝnh t¾c: A.x = b (3.1) 1) Chän biÕn c¬ së: ®Çu tiªn ta chän mét ®iÓm tuú ý cña ®a diÖn c¸c nghiÖm cho phÐp, ®ã lµ tËp n sè (x1, ...., xn). Theo ®Þnh lý c¬ b¶n cña bµi to¸n tèi −u tuyÕn tÝnh th× cã m sè d−¬ng, cßn nh÷ng sè kh¸c b»ng kh«ng; gäi c¸c biÕn d−¬ng cña ®iÓm xuÊt ph¸t lµ biÕn c¬ së: (x1, x2,..., xm, 0, 0,..., 0). 2) T×m nghiÖm xuÊt ph¸t (nghiÖm thö thø 1): Thay c¸c biÕn c¬ së vµo c¸c rµng buéc (3.1) ®−îc m ph−¬ng tr×nh chøa m Èn: ar1 x1 + ar2 x2 + ... armxm = br; r = 1, 2 , .... , m. 14
⎧a11 x1 + ... + a1m x m = b1 ⎪ hay: ⎨......................... (3.2) ⎪a x + .... + a x = b ⎩ m1 1 mm m m Tõ ®ã t×m ®−îc nghiÖm xuÊt ph¸t (hay nghiÖm thö thø 1): ( x1 0 ) , x 20 ) ,...., x m0 ) ) . ( ( ( 3) Chän nghiÖm thö thø 2: a) Thö thªm vµo biÕn xm+1, lóc nµy rµng buéc cã d¹ng: {a r1 x1 + a r 2 x2 + ... + a rm xm + ar ,m+1 xm+1 = br ; r = 1, 2, ..., m (3.3) HÖ (3.3) gåm m ph−¬ng tr×nh víi m+1 biÕn, (3.3) cã nghiÖm ®¬n trÞ khi c¸c ph−¬ng tr×nh t¹o thµnh hÖ phô thuéc, do ®ã cét cuèi cïng phô thuéc tuyÕn tÝnh vµo c¸c cét cßn l¹i víi hÖ sè yi: ar,m+1 = y1ar1 + ...+ ymarm hay ar1y1 + ... + armym = ar,m+1 (3.4) (0 ) (0 ) (0 ) HÖ (3.4) cã nghiÖm duy nhÊt lµ: y1 , y 2 ,....., y m . b) LÊy c¸c sè h¹ng t−¬ng øng cña ph−¬ng tr×nh (3.3) trõ ®i béi sè cña (3.4) ký hiÖu béi sè ®ã lµ λ > 0, ta cã: ar1(x1 - λy1) + ar2 (x2 - λy2) + .... + arm (xm - λym) + ar,m+1λ = br (3.5) r = 1,2, ... m. HÖ (3.5) lµ biÕn thÓ cña (3.4) chØ cã c¸c Èn lµ kh¸c nhau. c) Chän nghiÖm thö thø 2 cho (3.5) lµ: ( x1( 0 ) − λ. y1( 0) ), (x (0) − λ. y 20 ) ),...., ( x m0 ) − λ. y m0 ) ), λ 2 ( ( ( (3.6) V× cã m+1 biÕn, do ®ã mét trong c¸c biÕn ph¶i nhËn gi¸ trÞ kh«ng. Ngoµi ra c¸c biÕn cßn l¹i xm+2 ,..., xn còng ph¶i b»ng kh«ng. Muèn biÕt biÕn nµo trong (3.6) b»ng kh«ng, cÇn ph¶i: ** TÝnh gi¸ trÞ cña hµm môc tiªu víi nghiÖm thö thø 1 vµ thö nghiÖm thø 2: Z0 = c1x1(0) + c2x2(0) +...., + cmxm(0) Z1 = c1 ( x1( 0) − λ. y1( 0) ) + c2 ( x20) − λ. y 20) ) + .... + cm ( xm0) − λ. y m0) ) + cm+1λ ( ( ( ( §Æt sè gia: ∆Z1 = Z1 - Z0 ∆Z1 = λ [c m +1 − (c1 y1( 0) + c 2 y 20) + .... + c m y m0) )] = λ [c m +1 − γ m +1 ] ( ( trong ®ã: γm+1 = c1 y1( 0) + c 2 y 20) + .... + c m y m0) ( ( [cm+1 −ym+1] ®−îc gäi lµ hiÖu suÊt. (3.7) Cã ba tr−êng hîp x¶y ra: * ∆Z1 = 0: nghiÖm xuÊt ph¸t vµ nghiÖm míi tèt nh− nhau. Suy ra cã hai ®Ønh tiÕp xóc gi÷a ®a diÖn cho phÐp vµ mÆt cïng môc tiªu. * ∆Z1 < 0: nghiÖm míi xÊu h¬n nghiÖm xuÊt ph¸t. * ∆Z1 > 0: nghiÖm míi tèt h¬n nghiÖm xuÊt ph¸t. ** Khi ®· chän ®−îc nghiÖm míi b»ng hoÆc tèt h¬n (∆Z1 ≥ 0) ta ®−a nã vµo c¬ së vµ cÇn ph¶i lo¹i bá bít mét nghiÖm trong biÕn xuÊt ph¸t (theo ®Þnh lý c¬ b¶n), chØ cã m nghiÖm d−¬ng). Gi¶ thiÕt ®· ®−a biÕn míi thø (m +1) vµo c¬ së, khi ®ã cã thÓ viÕt c¸c biÕn míi cña ph−¬ng ¸n theo (3.6). Mét biÕn thø i nµo ®ã ph¶i tho¶ m·n ph−¬ng tr×nh: x i( 0 ) x i( 0 ) − λ y i(0) = 0 tõ ®ã λ = (3.8) y i( 0 ) cßn ®èi víi c¸c biÕn j ≠ i th×: x (j 0 ) − λ y (0) > 0 j (3.9) Tõ ®ã suy ra ph¶i lo¹i trõ biÕn nµo øng víi λ > 0 vµ nhá nhÊt: 15
x i( 0 ) 0 < λ = Min y i( 0 ) 4) Thùc hiÖn liªn tôc c¸c thuËt to¸n ë trªn: ®−a vµo biÕn ch−a dïng m+2, m+3..., tÝnh ∆Z2, ∆Z3 ,... cho ®Õn khi thö hÕt c¸c biÕn c¬ së. ∆Z1 = λ [cm+1 - γm+1] ∆Z2 = λ [cm+2 - γm+2] ∆Zi = λ [cm+i - γm+i ] ë mçi b−íc cÇn tÝnh hiÖu suÊt (cm+1 - γm+1), kiÓm tra ∆Zi vµ rót ra kÕt luËn t−¬ng øng. Sau (n-m) lÇn lÆp, ta chän ®−îc nghiÖm tèi −u. Ph−¬ng ph¸p ®¬n h×nh cã −u ®iÓm lµ thuËt to¸n ®¬n gi¶n. Khi cã Ýt Èn cã thÓ tÝnh b»ng tay (trùc tiÕp hoÆc lËp b¶ng). Khi cã nhiÒu Èn vµ nhiÒu rµng buéc ph¶i dïng m¸y tÝnh.. Râ rµng ë ®©y môc tiªu ®¹t ®−îc ph¶i lu«n ®o ®−îc. Trong hµm môc tiªu Z = c.x ®· gi¶ thiÕt c¸c hÖ sè c1 > 0 nh−ng ng−êi ta gi¶ thiÕt tån t¹i c¶ nh÷ng biÕn “cã h¹i” tøc lµ hÖ sè c1 < 0. §iÒu ®ã gióp Ých cho nghiªn cøu vµ kh«ng ¶nh h−ëng ®Õn b−íc gi¶i. 3.4.3. Mét sè thÝ dô gi¶i trùc tiÕp: VÝ dô: (∆Zi < 0 , ∀i). T×m x* (x1, x2, x3, x4) sao cho hµm môc tiªu: Z = x1 + 2x2 - 3x3 + 4x4 → Max víi c¸c rµng buéc: ⎧ x1 − x 2 + 7 x 3 + x 4 = 100 ⎪ ⎨2 x1 + 3 x 2 − x 3 + 10 x 4 = 800 ⎪x ≥ 0, i = 1 ÷ 4 ⎩ 1 Gi¶i: 1. Chän biÕn c¬ së: V× sè rµng buéc m = 2, ta gi¶ thiÕt x1 > 0, x2 > 0, x3 = x4 = 0: (x1, x2, 0, 0) 2. T×m nghiÖm xuÊt ph¸t: thay biÕn c¬ së vµo ph−¬ng tr×nh rµng buéc: ⎧ x1 − x 2 = 100 ⎨ ⎩2 x1 + 3 x 2 = 800 gi¶i ®−îc: x1(0) = 220; x2(0) = 120 do ®ã nghiÖm xuÊt ph¸t lµ: (220, 120, 0, 0) vµ Z0 = 220 + 2x120 = 460 3. Thö ®−a x3 vµo c¬ së: Ph−¬ng tr×nh rµng buéc: ⎧ x1 − x 2 + 7 x 3 = 100 ⎨ ⎩2 x1 + 3 x 2 − x 3 = 800 §ã lµ hÖ ph−¬ng tr×nh phô thuéc, nªn hÖ sè cña cét thø ba phô thuéc vµo cét 1 vµ cét 2 víi hÖ sè yi: ⎧ y1 − y 2 = 7 ⎨2 y + 3 y = −1 ⎩ 1 2 gi¶i ®−îc y1( 0) = 4 ; y (0) = −3 2 TÝnh hiÖu suÊt cña x3: γ3 = c1 y1 + c 2 y 2 = y1 0 ) + 2 y 20 ) = −2 (0) (0) ( ( HiÖu xuÊt c3 - γ3 = -3 + 2 < 0 nªn ∆Z1 = λ(c3 - γ3) = λ(-3 + 2) < 0 Nh− vËy nÕu ®−a x3 vµo c¬ së th× ph−¬ng ¸n xÊu h¬n ph−¬ng ¸n xuÊt ph¸t. 16
4. Thö ®−a x4 vµo c¬ së: Rµng buéc: ⎧x1 − x2 + x4 = 100 ⎨ ⎩2x1 + 3x2 + 10x4 = 800 tõ ®ã: ⎧ y1 − y 2 = 1 ⎨ → y1(0) = 2,6 ; y(0) = 1,6 ⎩2 y1 + 3 y 2 = 10 2 TÝnh hiÖu suÊt cña x4: γ4 = c1 y1 + c2 y2 = 2,6 + 2.1,6 = 5,8 (0) (0) HiÖu suÊt: (c4 - γ4) = 4 - 5,8 < 0 → ∆Z2 = λ(c4 - γ4) < 0 do ®ã nÕu ®−a x4 vµo c¬ së th× sÏ cã ph−¬ng ¸n xÊu h¬n. Nh− vËy nghiÖm tèi −u chÝnh lµ nghiÖm xuÊt ph¸t: x* = [ x1 , x2 ,0,0] = [ 220,120,0,0] * * T T Hµm môc tiªu: Z* = 220 + 2.120 = 460 3.4.4. Ph−¬ng ph¸p lËp b¶ng: Dïng phÐp xoay (Pivotage) cña ®¹i sè tuyÕn tÝnh. VÝ dô: T×m (x1, x2, x3, x4) sao cho hµm môc tiªu: Z = 500x1 + 300x2 + 200x3 + 280x4 → Max C¸c rµng buéc: ⎧10 x1 + 5 x 2 + 4x 3 + 2x 4 ≤ 2000 ⎪ ⎨8 x1 + 5 x 2 + 1,2x 3 + 5,6x 4 ≤ 1800 ⎪5 x + 8 x + 2,5 x + 10x ≤ 2000 ⎩ 1 2 5 4 Gi¶i: BiÕn ®æi vÒ d¹ng chÝnh t¾c ⎧10 x1 + 5 x2 + 4x 3 + 2x 4 + x 5 = 2000 ⎪ ⎨8 x1 + 5 x2 + 1,2x 3 + 5,6x 4 + x6 = 1800 ⎪5 x + 8 x + 2,5x + 10x + x 7 = 2000 ⎩ 1 2 5 4 Z - 500x1 - 300x2 - 200x3 - 280x4 + 0x5 + 0x6 + 0x7 = 0 LËp b¶ng 1: Chän mét biÕn kh¸c ®Ó ®−a vµo c¬ së: B¶ng 1. s (cét xoay) BiÕn c¬ x1 x2 x3 x4 x5 x6 x7 së r→ x5 10 5 4 2 1 0 0 2000 (dßng xoay) ars x6 8 5 1,2 5,6 0 1 0 1800 x7 5 8 2,5 10 0 0 1 2000 ais Z -500 -300 -200 -280 0 0 0 0 Trªn dßng Z, chän mét cét nµo cã gi¸ trÞ < 0 vµ trÞ sè lín nhÊt, gäi lµ cét s (cét xoay). 17
2000 1800 2000 XÐt c¸c tû sè: = 200 ; = 225; = 400 dßng nµo cã tû sè nhá nhÊt gäi lµ 10 8 5 dßng r (dßng xoay). ars = 10: gäi lµ phÇn tö xoay (pivot). LËp b¶ng 2: §−a biÕn x1 vµo c¬ së thay cho x5. T¹o dßng chÝnh: chia dßng r ë b¶ng I cho pivot ars C¸c yÕu tè cña c¸c dßng kh¸c ®−îc tÝnh theo c«ng thøc: aij(míi) = aij(cò) - ais.arj, cã nghÜa: yÕu tè dßng míi = yÕu tè dßng cò - ais*yÕu tè dßng chÝnh (øng víi phÇn tö cÇn t×m) VÝ dô ë b¶ng 2: dßng chÝnh lµ dßng chøa x1. C¸c phÇn tö cña dßng 2 lµ: 0 = 8 - 8x1; 1 = 5 - 8 x 0,5; - 2 = 1,2 - 8x0,4 ... B¶ng 2. BiÕn c¬ x1 x2 x3 x4 x5 x6 x7 së dßng chÝnh x1 1 0,5 0,4 0,2 0,1 0 0 200 x6 0 1 -2 4 -0,8 1 0 200 x7 0 5,5 0,5 9 -0,5 0 1 1000 Z 0 -50 0 -180 50 0 0 100000 LËp b¶ng 3: B¶ng 3. BiÕn c¬ x1 x2 x3 x4 x5 x6 x7 së x1 1 0,45 0,5 0 0,14 0,05 0 190 dßng chÝnh x4 0 0,25 -0,5 1 -0,2 0,25 0 50 x7 0 3,25 5 0 -1,3 2,25 1 550 Z 0 -5 -90 0 1,4 4,5 0 109000 LËp b¶ng 4: B¶ng 4. BiÕn c¬ x1 x2 x3 x4 x5 x6 x7 së x1 1 1,125 0 0 0,001 0,175 0,1 135 x4 0 0,575 0 1 -0,07 0,025 0,1 105 dßng chÝnh x3 0 0,65 1 0 -0,26 0,45 0,2 110 Z 0 53,3 0 0 37,4 4,5 18 118900 ë b¶ng 4, c¸c hÖ sè cña Z ®Òu ≥ 0, do ®ã dõng vµ kh«ng cÇn ph¶i tiÕn hµnh b¶ng 5. BiÕn c¬ së lµ tèi −u, c¸c biÕn kh¸c cã gi¸ trÞ 0, do ®ã: x* = [x1, x4, x3 ]T = [135, 105, 110 ]T; Z* = 500x135 + 200x110 + 280x250 = 118900. 3.5. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n tèi −u tuyÕn tÝnh tæng qu¸t 3.5.1. Ph¸t biÓu bµi to¸n: Hµm môc tiªu: 18
f (x) = ∑c x j i j → Min; j = 1,2,...., n. C¸c rµng buéc: ∑a j ij x j ≤ bi ; i = 1,2 ,...., m1 . ∑a j ij x j ≥ bi ; i = m1 + 1, m1 + 2 ,...., m1 + m2 . ∑a j ij x j = bi ; i = m1 + m2 + 1, m1 + m2 + 2 ,...m xj ≥ 0 ; bi ≥ 0 ; i = 1,2 ,....., m. 3.5.2. BiÕn ®æi c¸c rµng buéc vµ hµm môc tiªu: §èi víi c¸c rµng buéc: ∑aijxj ≤ bi ta ph¶i thªm biÕn bï xn+i ≥ 0 §èi víi c¸c rµng buéc: ∑aijxj = bi ta ph¶i thªm biÕn gi¶ t¹o xn+i ≥ 0 §èi víi c¸c rµng buéc: ∑aijxj ≥ bi ta ph¶i thªm biÕn gi¶ t¹o råi biÕn bï. BiÕn bï øng víi rµng buéc: ≤ ®−îc ®¸nh tõ sè n+1 ®Õn n+m1; c¸c biÕn gi¶ t¹o øng víi rµng buéc ≥ vµ = ®−îc ®¸nh sè tõ n+m1+1 ®Õn n+m; c¸c biÕn bï øng víi rµng buéc ≥ ®−îc ®¸nh sè tõ n+m+1 ®Õn n+m+m2. Trong hµm môc tiªu, c¸c hÖ sè øng víi biÕn bï xj lµ cj = 0, c¸c hÖ sè øng víi biÕn gi¶ t¹o xj lµ cj > 0 ®ñ lín, cã thÓ chän cj = M = max {|aij,|bi,|cj|}. VÝ dô: T×m (x1, x2) sao cho hµm môc tiªu: Z = 30x1 + 45x2 → Max C¸c rµng buéc: 1) x1 ≤ 6000 2) x2 ≤ 4000 3) 2,5x1 + 2x2 ≤ 24000 4) x1 ≥ 1000 5) x2 ≥ 1000 6) 3x1 - x2 ≥ 0 7) 2,5x1 + 2x2 ≥ 10000 Gi¶i: Trong thuËt to¸n, ta ®−a bµi to¸n vÒ d¹ng chÝnh t¾c b»ng c¸ch thªm c¸c biÕn bï x3, x4, x5; c¸c biÕn gi¶ t¹o x6, x7, x8 ,x9 vµ c¸c biÕn bï x10, x12, x13. C¸c rµng buéc: 1) x1 + x3 = 6000 2) x2 +x4 = 4000 3) 2,5x1+2x2 +x5 = 24000 4) x1 -x6 +x10 = 1000 5) x2 -x7 +x11 = 1000 6) 3x1 - x2 -x8 +x12 =0 7) 2,5x1+2x2 -x9 +x13 = 10000 Hµm môc tiªu: Z = 30x1+45x2+0x3+0x4+0x5-Mx6-Mx7 = Mx8-Mx9+0x10+0x1+0x12+0x13 chän M ≥ 24000. Sau khi gi¶i bµi to¸n chÝnh t¾c ta ®−îc: x1=6000, x2=4000, x5=1000, x10=5000, x11=3000, x12=14000, x13=13000, Z=360000. 19