Chương 4: Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu

Chia sẻ: Hoang Nam | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

3.159
lượt xem 576
download

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

Thuật toán đơn hình đối ngẫu là thuật toán đơn hình áp dụng vào giải toán đối ngẫu của quy hoạch tuyến tính đã cho nhưng các bước tiến hành lại được diễn tả trên bài toán gốc. Sau đây ta tìm hiểu nội dung của thuật toán đơn hình đối ngẫu.

Chủ đề:

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

Lưu

Nội dung Text: Chương 4: Bài toán quy hoạch tuyến tính đối ngẫu và thuật toán đơn hình đối ngẫu

Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Chương 4. BÀI TOÁN QUY HO CH TUY N TÍNH Đ I NG U VÀ THU T TOÁN ĐƠN HÌNH Đ I NG U 4.1. Bài toán quy ho ch tuy n tính đ i ng u Đ nh nghĩa 4.1.1 (Bài toán đ i ng u). Cho các bài toán quy ho ch tuy n tính: f (x) = cT x → min g (x) = bT y → max    AT x bi ; i ∈ M1 0 , i ∈ M1  yi i        AT x b ;i ∈ M 0, i ∈ M y i 2 i 2 i     T (a)  Ai x = bi ; i ∈ M3 (b)  yi ∈ R , i ∈ M3     y T AJ 0 ; j ∈ N1 cj , j ∈ N1  xj         y T AJ 0 ; j ∈ N2 cj , j ∈ N2 xj       y T AJ = cj , j ∈ N3   xj ∈ R; j ∈ N3   Ngư i ta g i bài toán (a) là bài toán g c và (b) là bài toán đ i ng u. Trong đó AT là véc tơ dòng i c a ma tr n A, Aj là véc tơ c t j c a ma tr m A. i M i ràng bu c b t đ ng th c c a bài toán này ng v i m t bi n trong ràng bu c v d u c a bài toán kia, g i là c p ràng bu c đ i ng u. Đ ng th i các chi u c a b t đ ng th c có quan h v i nhau th hi n b ng sau: 42
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Góc min max Đ i ng u ∈R = bi Ràng bu c ≤ bi ≤0 Bi n ≥ bi ≥0 ≥0 ≤ ci ≤0 ≥ ci Ràng bu c Bi n ∈R = ci Ví d 4.1.2. Xét quy ho ch tuy n tính bên trái và bài toán đ i ng u bên ph i, các bài toán sau: g (y ) = 5y1 + 6y2 + 4y3 → max f (x) = x1 + x2 + 3x3 → min    −x1 +3x2  −y1 +2y2 =5 1         (a) (b) −x2 − y2 2x1 +3x3 6 3y1 1       x3 4 3y2 +y3 = 3     y2 0, y3 0 x1 0, x2 0 Nh n xét 4.1.3. Quan h đ i ng u gi a các bài toán quy ho ch tuy n tính có tính ch t đ i x ng. Đ nh lý 4.1.4 (Đ i ng u y u). N u x, y l n lư t là phương án c a bài toán quy ho ch tuy n tính g c và đ i ng u thì g (y ) ≤ f (x). Ch ng minh. Ta đ t ui = yi (AT x − bi ), i = 1, . . . , m i (4.1.1) vj = (cj − y T Aj )xj , j = 1, . . . , n Theo đ nh nghĩa bài toán đ i ng u, thì yi và AT x − bi cùng d u, cj − y T Aj và i xj cùng d u. Do đó, ui ≥ 0 và vj ≥ 0 v i m i i, j . Ta có m ui = y T Ax − y T b; i=1 n vj = cT x − y T Ax; j =1 43
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp vj = cT x − y T b = f (x) − g (y ) ⇒ g (y ) Do đó, 0 ui + f (x) i j H qu 4.1.5. Gi s x, y là phương án c a bài toán g c và đ i ng u. N u f (x) = g (y ) thì x, y l n lư t là phương án t i ưu c a bài toán g c và đ i ng u. Ch ng minh. Đ i v i m i x, y là phương án bài toán g c và đ i ng u thì g (y ) ≤ f (x) = g (y ) ≤ f (x). Ch ng t tính t i ưu c a x, y. Đ nh lý 4.1.6 (Đ i ng u m nh). M t c p bài toán đ i ng u, n u bài toán này có phương án t i ưu thì bài toán kia cũng có phương án t i ưu và giá tri t i ưu c a chúng b ng nhau. Ch ng minh. Gi s bài toán g c có phương án t i ưu. Do đó bài toán d ng chính t c tương T ∧−1 0 x0 c0 v i ma tr n cơ s B . Khi đó, y = ng nó có phương án t i ưu là B là phương án c a bài toán đ i ng u. G i x0 là phương án t i ưu bài toán g c thu đư c t x0 . Ta có: g (y 0 ) = y 0T b = (c0T B −1 )b = c0T x0 = f (x0 ) V y, y 0 là phương án t i ưu bài toán đ i ng u. Đ nh lý 4.1.7 (S t n t i phương án). Đ i v i c p bài toán g c-đ i ng u c a quy ho ch tuy n tính ch có m t trong ba trư ng h p sau x y ra: (i) C hai cùng có t p phương án r ng. (ii) C hai cùng có phương án t i ưu và giá tr hàm m c tiêu c a chúng b ng nhau. (iii) Bài toán này có hàm m c tiêu không b ch n, còn bài toán kia có t p phương án r ng Ch ng minh. Theo đ nh lí đ i ng u m nh, ta có (ii). N u không có (ii) thì x y ra (i) ho c (iii). Theo đ nh lí đ i ng u y u, thì có (iii). B ng ví d ch ra có (i). 44
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Đ nh lý 4.1.8 (Đ l ch bù). Gi s x và y là phương án c a bài toán g c-đ i ng u tương ng. Khi đó, x và y là t i ưu khi và ch khi yi (AT x − bi ) = 0 ∀i (4.1.2) i cj − y T AJ xj = 0 ∀j (4.1.3) Ch ng minh. vj = cT x − y T b = f (x) − g (y ) và x, y là c p phương án t i Ta có 0 ui + i j ưu thì f (x) = g (y ). Khí đó, ui = 0 và vj = 0 v i m i i, j . Do đó yi (AT x − bi ) = 0 ∀i (4.1.4) i cj − y T A J x j = 0 ∀j (4.1.5) Đ nh lý đư c ch ng minh. Ví d 4.1.9. Ki m tra tính t i ưu c a phương án x∗ = (2, 0, 1, −2, 3) c a bài toán quy ho ch tuy n tính. f (x) = −4x1 + 9x2 + 16x3 − 8x4 − 20x5 → min  −x3  5x1 +4x2 +3x4 +x5 5     −x +4x3 −2x4 −5x5 −9 +2x 1 2     −x1 −2x2 −x3 +2x4 +3x5 = 2  xj 0, j = 1, 2, 3 Gi i G i y = (y1 , y2 , y3 ) là phương án bài toán đ i ng u tương ng x∗ . Ta có A1 x∗ = 6 > 5, A2 x∗ = −9, A3 x∗ = 2 nên y1 = 0. M t khác, xét x∗ ta có x∗ , x∗ , x∗ , x∗ khác 0 nên 1345     −4   −1 −1           4 −1  y2     16 y = 4   2  ⇔   =       −2 2   −8  y3  y3 = 0          −5 3 −20 45
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp và f (x∗ ) = −36, g (y ) = −36. V y, x∗ là phương án t i ưu. Ví d 4.1.10. Cho bài toán quy ho ch tuy n tính f (x) = 6x1 + 2x2 + 7x3 + 8x4 − 5x5 − 9x6 → min   −2x1 −x3 +x2 +3x4 +2x5 7     −3x2 +2x3 +4x4 −x5 − 3x6 −8    −2x2 +4x3 −3x4 −5x5 − 3x6 = −22 x1   xj 0, j = 1, 2, 3, 4, 5, 6 (a) Ch ng t x∗ = (0, 0, 9, 0, 8, 6), y ∗ = (3, 1, 2) tương ng là phương án t i ưu c a bài toán đã cho và bài toán đ i ng u c a nó. (b) Tìm t p phương án t i ưu c a bài toán đã cho. Gi i (a) Xét x∗ , ta th y x∗ ≥ 0 v i m i j . j A1 x∗ = 7, A2 x∗ = −8, A3 x∗ = −22. Nên x∗ là phương án và f (x∗) = −31. Tương t , xét y ∗ , ta th y yi ≥ 0 v i m i i. ∗ AT y ∗ = −4 ≤ 6, AT y ∗ = −4 ≤ 2, AT y ∗ = 7 ≤ 7 1 2 3 AT y ∗ = 7 ≤ 8, AT y ∗ = −5 ≤ −5, AT y ∗ = −9 ≤ −9 4 5 6 Do đó, y ∗ là phương án và g (y ∗ ) = −31. V y x∗ , y ∗ tương ng là phương án t i ưu c a bài toán đã cho và bài toán đ i ng u c a nó. (b) Tìm t p phương án t i ưu c a bài toán đã cho. G i x(xi ) là phương án t i ưu bài toán đã cho tương ng y ∗ . T AT y ∗ = −4 < 6, AT = −4 < 2, AT = 7 < 8 mà ta l i có x1 = x2 = x4 = 0 1 2 4 46
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp và  f (x) = 7x3 − 5x5 − 9x6 = −31        −x3 + 2x5 ≥ 7      2x3 − x5 − 3x6 ≥ −8    4x − 5x − 3x = −22  3 5 6      xj ≥ 0, =; j = 3, 5, 6    x3 − 2x6 = −3        −x5 + x6 = −2      ⇒ −x3 + 2x5 ≥ 7     2x − x − 3x ≥ −8  3 5 6      x ≥ 0, =; j = 3, 5, 6  j   x3 = −3 + 2t        x = 2 + t 5  ⇒  x = t 6      t ≥ 3/2   V y, t p phương án t i ưu c a bài toán đã cho là T = {(0, 0, −3 + 2t, 0, 2 + t, t) : t ≥ 3/2} 4.2. Thu t toán đơn hình đ i ng u Thu t toán đơn hình đ i ng u là thu t toán đơn hình áp d ng vào gi i bài toán đ i ng u c a quyb ho ch tuy n tính đã cho nhưng các bư c ti n hành l i đư c di n t trên bài toán g c. Sau đây ta tìm hi u n i dung c a thu t toán đơn hình đ i ng u. 47
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 4.2.1 Cơ s lí lu n D u hi u t i ưu. Ta xét bai toán d ng chính t c f (x) = cT x −→ min (4.2.6) Ax = b (4.2.7) x≥0 (4.2.8) và bài toán đ i ng u c a nó g (y ) = bT y −→ max AT y ≤ c Trong đó A là ma tr n c m × n và A có h ng là m. B = {Aj : j ∈ JB } là m t cơ  T j y A = c ; j ∈ J j  s c a ma tr n A. B đư c g i là cơ s đ i ng u n u ,t c T j y A ≤ C ; j ∈ J /B j  là t n t i phương án c c biên y ng v i cơ s B c a bài toán đ i ng u. Nh n xét. • Ta có y T = c0T B −1 , suy ra y T Aj = (c0T B −1 )Aj = c0T (B −1 Aj ) = c0T xj = ∆j + cj v y B là cơ s đ i ng u khi và ch khi ∆j ≤ 0, ∀j .   khi j ∈ jB x = x j 0j • Gi phương án. Đ t x0 = B −1 b = (x0j ), j ∈ jB và x = khi j ∈ jB  x = 0 / j Ta g i x là gi phương án c a bài toán g c thì đó là phương án c c biên t i ưu. T đó ta có d u hi u t i ưu sau. Đ nh lý 4.2.2 (D u hi u t i ưu). B là cơ s đ i ng u c a quy ho ch tuy n tính. N u x0 = B −1 b ≥ 0 thì y là phương án t i ưu c a bài toán đ i ng u và gi phương án x là phương án t i ưu c a bài toán g c. Đ nh lý 4.2.3 (D u hi u t p phương án r ng). N u t n t i j ∈ Jb sao cho x0j < 0 và xji ≥ 0 v i m i i thì bài toán đ i ng u có hàm m c tiêu không b ch n. Cho nên bài toán g c có t p phương án r ng. 48
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Đ nh lý 4.2.4 (D u hi u phương án c c bi n t t hơn). N u t n t i j sao cho x0j < 0, đ ng th i v i t n t i i sao cho xji < 0 thì có th xây d ng đư c phương án c c biên cho bài toán đ i ng u t t hơn. 4.2.5 Thu t toán đơn hình đ i ng u Gi s đã có s n m t cơ s đơn v là cơ s đ i ng u c a bài toán (4.2.1), (4.2.2), (4.2.3). Ta l p b ng đơn hình gi ng như thu t toán đơn hình g c theo các bư c sau: Bư c 1. Đ t xj = Aj , (j = 0, 1, . . . , n), tính ∆j = ct xj − cj , j = 1, 2, . . . , n và ct0 x0 . Chuy n sang bư c 2. Bư c 2. N u x0 ≥ 0 thì gi phương án x là phương án t i ưu và k t thúc thu t toán. N u trái l i chuy n sang bư c 3. Bư c 3. N u t n t i i ∈ J0 sao cho x10 < 0 và xij ≥ 0 v i m i j = 1, 2, . . . , n thì k t lu n t p phương án là r ng. N u trái l i thì ch n ∆s0 = min{x10 : i ∈ J0 } và gi s ∆k ∆k θ= = min : xsj < 0 (4.2.9) xsk xsk Chuy n sang bư c 4. Bư c 4. Th c hi n phép quay xung quanh ph n tr c xsk ta thu đư c gi phương án m i, coi nó như gi phương án ban đ u r i quay l i bư c 2. Chú ý 4.2.6. B ng đơn hình đư c l p như trong thu t toán đơn hình g c, ch c t x0 không ghi f (x) như khác nhau ch , t i v trí ghi giá tr hàm m c tiêu trư c mà là g (y ), riêng b ng đã xu t hi n d u hi u t i ưu thì hai giá tr nói trên trùng nhau. 49
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Ví d 4.2.7. Gi i bài toán f (x) = 4x1 + 6x2 + 5x3 + 3x4 → min x1 + x2 + 3x3 + 2x4 ≥ 5 x1 + 4x2 + 2x3 + x4 ≥ 3 xj ≥ 0, j = 1, 2, 3, 4. Gi i Đưa vào hai n bù không âm x5 , x6 ta đư c h ràng bu c m i.   −x1 −x2 −3x3 −2x4 +x5 = −5  −x −4x −2x −4x +x6 = −3 1 2 3 4 xj ≥ 0, j = 1, 2, 3, 4, 5, 6. Các ràng bu c c a bài toán đ i ng u là: t yA1 = −y1 − y2 ≤ 4 t yA2 = −y1 − 4y2 ≤ 6 t yA3 = −3y1 − 2y2 ≤ 5 t yA4 = −2y1 − y2 ≤ 3 t yA5 = −y1 ≤ 4 t yA6 = y2 ≤ 0 Ta th y ngay y = (0, 0) là phương án c c biên c a bài toán đ i ng u vì d = đ i v i hai ràng bu c đ c th y nó là phương án, ngoài ra còn th a mãn d u l p tuy n tính cu i cùng; cơ s đ i ng u tương ng là cơ s đơn v g m hai vectơ A5 , A6 . ng v i cơ s đó là gi phương án x = (0, 0, 0, 0, −5, −3). Các k t qu tính toán đư c th hi n trên các b ng đơn hình dư i đây. bư c l p đ u tiên ta th y x0 = (−5, −3) < 0, min(x50 , x60 ) = min(−5, −3) = −5. Do dó A5 ra kh i cơ s . Vì −4 −6 −5 −3 ∆j ∆4 min : x5j < 0 = min , , , = (4.2.10) −1 −1 −3 −2 x5j x54 nên đưa A4 vào cơ s thay A5 . Th c hi n phép quay xung quanh ph n t tr c x54 = −2 ta có bư c l p th hai. 50
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp bư c cu i, ta th y x0 = (1, 1) > 0, t đó ta thu đư c phương án t i ưu x∗ = (0, 0, 1, 1). c0 Cơ x0 x1 x2 x3 x4 x5 x6 s 4 6 5 3 0 0 A5 (-5) (-2) 0 -1 -1 -3 1 0 A6 0 -3 -1 -4 -2 -1 0 1 0 -4 -6 -5 -3 0 0 A4 3 5/2 1/2 1/2 3/2 1 -1/2 0 A6 (-1/2) -1/2 -7/2 (-1/2) 0 0 -1/2 1 15/2 -5/2 -9/2 -1/2 0 -3/2 0 A4 3 1 -1 -10 0 1 -2 3 A3 5 1 1 7 1 0 1 -2 8 -2 -1 0 0 -1 -1 Ví d 4.2.8. Cho bài toán f (x) = x1 + 10x2 + 8x3 → min − x1 + 2x2 + 3x3 = 1 x1 + x2 + 2x3 = 1 xj ≥ 0, j = 1, 2, 3. (a) Hãy tìm t t c các cơ s đ i ng u. Trong các cơ s đ i ng u đó, cơ s nào là cơ s t i ưu c a bài toán đã cho và khi đó hãy xác đ nh phương án t i ưu. (b) Xu t phát t cơ s đ i ng u không ph i là cơ s t i ưu, gi i bài toán đã cho b ng thu t toán đơn hình đ i ng u. Gi i 51
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp (a) Bài toán đ i ng u f (x) = y1 + y2 → max − y1 + y2 ≤ 1 2y1 + y2 ≤ 10 y1 + 2 y 2 ≤ 8 xj ≥ 0, j = 1, 2, 3.     −1 2 1 A1 =   , A2 =   A2 , A3 =   và h {A3 , A1 } đ u đ c l p Các h 0 1 2 tuy n tính. • Xét h {A1 , A2 }:    t 1   −y + y = 1  yA = c y = 3 1 1 2 1  ⇐⇒ ⇐⇒ (4.2.11) t 2    yA = c 2y + y = 10 y = 4 2 1 2 2  Vectơ (3, 4) không th a mãn ràng bu c (3) nên h {A1 , A2 } không ph i là cơ s đ i ng u. • Xét h {A1 , A3 }:    t 1   − y + y = 1  yA = c y = 2 1 1 2 1  ⇐⇒ ⇐⇒ (4.2.12) t 3    yA = c y + 2 y = 8 y = 3 3 1 2 2  Vectơ (2, 3) th a mãn ràng bu c (2) nên h {A1 , A2 }là cơ s đ i ng u. Ta tìm phương án tương ng: Các thành ph n cơ s c a gi phương án đư c xác đ nh b i h x1 A1 + x3 A3 = b, t c là h :     −x + x = 1 x = −1/3 1 3 1 ⇐⇒ ⇐⇒ (4.2.13)   x + 2 x = 1 x = 2/3 1 3 2 trong gi phương án có thành ph n âm nên {A1 , A3 } không ph i là cơ s t i ưu c a bài toán đã cho. 52
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp • Xét h {A2 , A3 }:    t 2    yA = c 2y + y = 10 y = 4 2 1 2 1  ⇐⇒ ⇐⇒ (4.2.14) t 3    yA = c y + 2 y = 8 y = 2 3 1 2 2  Vectơ (2, 3) th a mãn ràng bu c (1) nên h {A2 , A3 }là cơ s đ i ng u. Các thành ph n cơ s c a gi phương án đư c xác đ nh b i h x2 A2 + x3 A3 = b, t c là h     2x1 + x3 = 1 x1 = 1/3   ⇐⇒ ⇐⇒ (4.2.15)   x + 2 x = 1 x = 1/3 1 3 2 Vì đó là nghi m không âm c a h trên nên x = (0, 1/3, 1/3) là phương án t i ưu. (b) Ta s gi i bài toán đã cho b ng thu t toán đơn hình đ i ng u v i cơ s đ i ng u xu t phát {A1 , A3 }. Th c hi n phép bi n đ i sơ c p trên các dòng c a ma tr n ràng bu c A đ đưa m t ma tr n có cơ s đơn v tương ng vơi A1 , A3 .         −1 2 1 1 0332 0 1 1 3/2 0 1 1 3/2 → → →   1 −1 0 −1/3 1 121 1121 112 1 Ta có b ng đơn hình sau (đ đơn gi n cách vi t mà v n không làm thay đ i b n ch t, ta v n dùng các ký hi u như thu t toán đơn hình trư c đây). c0 x0 cơ 1 10 8 x1 x2 x3 s A1 8 2/3 0 1 1 A1 -1/3 (-1) 1 1 0 0 -3 0 A3 8 1/3 1 0 1 10 A2 1/3 -1 1 0 6 -3 0 0 11 bư c 2, do x0 ≥ 0 nên suy ra x = 0, , là phương án t i ưu. 33 53
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 4.3. Vnđ tìm phương án c c biên xu t phát c a bài toán đ i ng u T lý lu n và các ví d trên đây ta th y r ng, đ ti n hành gi i bài toán (1), (2), (3) b ng thu t toán đơn hình đ i ng u ta c n ph i bi t m t phương án c c biên c a bài toán đ i ng u (coi nó là phương án c c biên xu t phát đ ti n hành thu t toán). 1) Trư ng h p th nh t Gi i s c n gi i bài toán (đư c g i là bài toán chính): f (x) =t cx → min Ax ≥ b x≥0 trong đó c ≥ 0; A là ma tr n c m × n. Đưa bài toán trên v bài toán d ng chính t c, nó có d ng: f (x, w) =t cx → min − Ax + w = −b x ≥ 0, w ≥ 0, trong đó w = (xn+1 , xn+2 , . . . , xn+m ). Các ràng bu c c a bài toán đ i ng u c a bài toán d ng chính t c là: t y (−Aj ) ≤ cj (j = 1, 2, . . . , n) t yI i ≤ 0 (i = 1, 2, . . . , m) D th y r ng y = 0 là phương án c c biên c a bài toán đ i ng u đó, ng v i cơ s đ i ng u là cơ s đơn v , gi phương án tương ng là x = (0, −b). Xu t phát t phương án c c biên đó ta ti n hành thu t toán đơn hình đ i ng u đ gi i bài toán đã cho. 2) Trư ng h p t ng quát Đ i v i bài toán (1), (2), (3), gi s chưa bi t m t cơ s đ i ng u nào nhưng đã 54
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp bi t m t h đ c l p tuy n tính g m m c t c a ma tr n A, đó là h H = {A j : j ∈ J 0 } (4.3.16) Chúng ta xét hai trư ng h p sau đây. (a) N u bi t đư c r ng h  t i i ∈ J0 A =c i  t j A ≤c j ∈ J0 / j  có nghi m ho c bi t đư c r ng ∆j ≤ 0 v i m i j ( ng v i H ) thì H chính là m t cơ s đ i ng u. N u may m n g p trư ng h p trên thì: Th c hi n phép bi n đ i sơ c p trên các dòng c a ma tr n [A|b] đ thu đư c ma tr n m i có m c t vectơ đơn v khác nhau tương ng v i cơ s đ i ng u H . Xu t phát t đó ti n hành thu t toán đơn hình đ i ng u đ gi i bài toán đã cho. N u H không ph i là cơ s đ i ng u ho c chưa bi t nó có ph i là cơ s đ i ng u hay không thì ta xét bài toán sau đây mà ta g i là bài toán m r ng. F (x0 , x) =t cx → min x0 + xj = M j ∈J0 / Ax = b x ≥ 0, x0 ≥ 0. trong đó x0 là m t n m i đư c b sung, M là tham s dương đư c coi là r t l n. Ví d 4.3.1. Gi i bài toán sau b ng thu t toán đơn hình đ i ng u f (x) = −x1 − 2x2 + x3 → min − x1 + 4x2 − 2x3 ≤ 6 x1 + x2 + 2x3 ≥ 6 2x1 − x2 + 2x3 = 4 xj ≥ 0, j = 1, 2, 3. 55
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Gi i Đưa vào hai n bù x4 và x5 ta đư c bài toán d ng chính t c f (x) = −x1 − 2x2 + x3 → min − x1 + 4x2 − 2x3 + x4 = 6 x1 + x2 + 2x3 − x5 = 6 2x1 − x2 + 2x3 = 4 xj ≥ 0, j = 1, 2, 3, 4, 5. Có th th y h g m 3 vectơ A1 , A4 , A5 là đ c l p tuy n tính. B sung vào bài toán trên m t ràng bu c gi t o ta có bài toán f (x0 , x) = −x1 − 2x2 + x3 → min −x1 + 4x2 − 2x3 + x4 = 6 x0 + x2 + x3 = M x1 + x2 + 2x3 − x5 = 6 2x1 − x2 + 2x3 = 4 xj ≥ 0, j = 0, 1, 2, 3, 4, 5. B ng cách gi i h Bxj = Aj v i j = 0, 2, 3, ta đư c: 17 3 x0 = (2, 8, −4) x2 = − , ,− 22 2 ho c có th tìm đư c chúng b ng cách th c hi n các phép bi n sơ c p trên các dòng c a ma tr n. Vi c tính toán đư c th hi n trên b ng dư i đây. Do các thành ph n c a gi phương án có d ng pM + q nên c t x0 và h s p trùng nhau. c0 x0 x0 x1 x2 x3 x4 x5 cơ s M 0 -1 -2 1 0 0 A0 (1) 0 0 1 1 0 1 0 0 -1 A1 2 0 0 1 -1/2 1 0 0 A4 0 8 0 0 0 7/2 -1 1 0 A5 0 -4 0 0 56 -3/2 0 -1 0 1
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 0 0 0 5/2 -2 0 0 -2 A2 0 1 1 0 1 1 0 0 -1 A1 2 1/2 1/2 1 0 3/2 0 0 A4 (-7/2) 0 8 -7/2 0 0 -9/2 1 0 A5 0 -4 3/2 3/2 0 0 1/2 0 1 -5/2 0 0 -9/2 0 0 -2 A2 16/7 0 0 0 1 -2/7 2/7 0 -1 A1 22/7 0 0 1 0 6/7 1/7 0 A0 -16/7 0 1 1 0 0 9/7 -2/7 0 A5 (-10/7) 0 -4/7 0 0 0 0 3/7 0 0 0 0 -9/7 -5/7 0 -2 A2 12/5 0 0 0 1 0 1/5 -1/5 -1 A1 14/5 0 0 1 0 0 2/5 3/5 A0 -14/5 0 1 1 0 0 0 1/10 9/10 A3 1 2/5 0 0 0 0 1 -3/10 -7/10 -36/5 0 0 0 0 -11/10 -9/10 Vì A0 thu c cơ s ng v i phương án t i ưu đó nên phương án t i ưu c a bài 14 12 2 toán ban đ u là x∗ = ,,. 555 4.4. V n đ h u t i ưu H!H u t i ưu Gi s ta đã gi i xong bài toán f (x) =t cx → min Ax = b x≥0 b ng thu t toán đơn hình và thu đư c phương án t i ưu x ng v i cơ s J0 khi d u hi u t i ưu đã xu t hi n (m i ư c lư ng đ u không dương). Gi s x0 là vectơ các thành ph n cơ s c a x và B là ma tr n g m các vectơ trong cơ s t i ưu. 57
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Trong th c t thư ng phát sinh các trư ng h p c n x lí sau đây: 1) Trư ng h p th nh t Thay đ i v ph i c a h ràng bu c cư ng b c, trư c là b, bây gi là b và ta có bài toán c n ph i gi i là f (x) =t cx → min Ax = b x≥0 Khi đó không c n gi i bài toán m i t đ u mà ch c n tính x0 = B −1 b. N u x0 ≥ 0 thì B v n là cơ s t i ưu đ i v i bài toán m i và x0 chính là vectơ các thành ph n cơ s trong phương án t i ưu c a bài toán m i. N u trái l i, t c là x0 có ít nh t m t thành ph n âm thì trong b ng đơn hình cu i cùng ta thay x0 b i x0 và như v y ta có b ng đơn hình xu t phát đ gi i bài toán m i b ng thu t toán đơn hình đ i ng u. 2) Trư ng h p th hai m am+1,j xj ≤ bm+1 , t c là c n gi i B sung vào bài toán ban đ u ràng bu c j =1 bài toán m i sau đây: f (x) =t cx → min Ax = b m am+1,j xj ≤ bm+1 j =1 x≥0 N u x th a mãn ràng bu c b sung thì nó cũng là phương án t i ưu c a bài toán m i. Trong trư ng h p ngư c l i, ta s dùng các ràng bu c cư ng b c c a bài toán ban đ u, có m t dư i d ng tương đương ngay trong b ng đơn hình cu i cùng, đ kh các n cơ s xj , j ∈ J0 trong ràng bu c b sung: m am+1,j xj + xn+1 = bm+1 (4.4.17) j =1 58
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp trong đó xn+1 là n bù không âm. Sau đó đ t dòng các h s m i c a ràng bu c b sung vào dòng cu i cùng (t c dòng th m + 1) c a b ng đơn hình cu i cùng. Và như v y, do các ư c lư ng v n không thay đ i và ∆n+1 = 0 (lưu ý r ng h s c a n bù xn+1 trong hàm m c tiêu b ng 0) ta có b ng đơn hình xu t phát đ gi i bài toán m i b ng thu t toán đơn hình đ i ng u. N u J0 = {1, 2, . . . , m} thì b ng đơn hình xu t phát đó là 59
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp c0 x0 ··· ··· ··· ··· c1 ci cm cj cơ 0 x1 xi xm xj xn+1 ··· ··· ··· ··· s A1 ··· ··· ··· ··· c1 x10 x1j 1 0 0 0 ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· Ai ··· ··· ··· ··· ci xi0 xij 0 1 0 0 ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· ··· Am ··· ··· ··· ··· cm xm0 xmj 0 0 1 0 An+1 bm+1 ··· ··· ··· ··· 0 xm+1,j 0 1 0 1 ··· ··· ··· ∆j ≤ 0 · · · 0 1 0 0 trong đó: m bm+1 = bm+1 − am+1,i xi0 (4.4.18) i=1 m xm+1,j = am+1,j − am+1,i xij (j = 1, 2, . . . , n). (4.4.19) i=1 Nói cách khác là nhân dòng i, (i = 1, 2, . . . , m) c a b ng cu i cùng v i −am+1,j c ng t t c l i, r i c ng v i h s tương ng c a ràng bu c b sung, k t qu đư c đ t vào dòng m + 1. Ví d 4.4.1. Cho bài toán f (x) = −x1 + 3x2 + x3 + 2x4 + x5 → min  +2x4 −9x5  x1 +3x2 =5     3x2 −2x3 +2x4 −7x5 ≤ 19    3x2 −3x3 +x5 ≤ 15   xj ≥ 0, j = 1, 2, 3, 4, 5. (a) Gi i bài toán đã cho. (b) Gi i bài toán đã cho khi v ph i b = (5, 19, 15) đư c thay b i b = (3, 14, 6). Gi i 60
Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Ta dùng thu t toán hai pha. Đưa vào hai n gi i x6 , x7 ta có bài toán ph f (x) = −x1 + 3x2 + x3 + 2x4 + x5 → min  +2x4 −9x5  x1 +3x2 =5     3x2 −2x3 +2x4 −7x5 +x6 = 19    3x2 −3x3 +x5 +x7 = 15   xj ≥ 0, j = 1, 2, 3, 4, 5, 6, 7. Ta có b ng sau: c0 x0 cơ -1 3 1 2 1 1 1 x1 x2 x3 x4 x5 x6 x7 b b s A1 0 5 1 0 3 2 -9 0 0 A6 19 1 0 3 -2 2 -7 1 0 A7 15 (3) 1 0 -3 0 1 0 1 0 6 -5 2 -6 0 0 A1 0 5 1 0 3 2 -9 0 A6 (2) 1 4 0 0 1 -8 1 A2 0 5 0 1 -1 0 1/3 0 0 0 1 2 -8 0 -1 A1 -5 (-1) 1 1 0 2 0 A4 4 2 2 0 0 1/2 1 -4 A2 2 3 5 0 1 -1 0 1/3 18 0 0 -5 0 -7 A5 5 1 -1 0 -2 0 1 A4 24 2 -4 0 -15/2 1 0 A2 1/3 1/3 3 1 -1/3 0 0 54 -7 0 -19 0 0 Đ i v i bài toán đã cho, bư c 3 đã xu t hi n d u hi u t i ưu v i phương án t i ưu là x∗ = (1, 5, 0, 2, 0) và f (x) = 18. 61