Bài tập quy hoạch tuyến tính chương 3có lời giải năm 2024

Uploaded by

Hồ Minh Dũng

0% found this document useful [0 votes]

640 views

16 pages

Copyright

© © All Rights Reserved

Available Formats

DOCX, PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

0% found this document useful [0 votes]

640 views16 pages

Bài toán Quy Hoạch Tuyến Tính

Uploaded by

Hồ Minh Dũng

Jump to Page

You are on page 1of 16

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

Uploaded by

Anh Vũ

0% found this document useful [0 votes]

456 views

23 pages

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

0% found this document useful [0 votes]

456 views23 pages

Bài tập nhóm 3

Uploaded by

Anh Vũ

Jump to Page

You are on page 1of 23

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

• 1. TUYẾN TÍNH
• 2. liệu này được tác giả tự biên soạn với mục đích ôn tập thi cuối kỳ môn Quy Hoạch Tuyến Tính cho riêng cá nhân và lớp VB2-Toán K1, Đại Học Sư Phạm TPHCM. Do thời gian gấp rút nên các chương từ thuật toán đơn hình về sau chỉ kịp giải bài tập, phần lý thuyết anh chị tự tìm hiểu thêm trong các tài liệu được Giảng Viên cung cấp. Do chỉ soạn trong thời gian ôn thi nên còn sơ sài, tác giả mong nhận được những chia sẻ, góp ý của anh chị để kỳ thi được kết quả tốt hơn. Chi tiết xin liên hệ qua địa chỉ mail: tranhuukhanh.edu@gmail.com Chân thành cảm ơn Tác giả TRẦN HỮU KHANH
• 3. MỘT SỐ KHÁI NIỆM VỀ GIẢI TÍCH LỒI................................................................1 Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH và CÁC TÍNH CHẤT CỦA NÓ .............9 Chương 3: PHƯƠNG PHÁP ĐƠN HÌNH....................................................................................26 Chương 4: BÀI TOÁN ĐỒI NGẪU .............................................................................................38 Chương 5: BÀI TOÁN VẬN TẢI ................................................................................................39 TÀI LIỆU THAM KHẢO.............................................................................................................47
• 4. SỐ KHÁI NIỆM VỀ GIẢI TÍCH LỒI 1. Đường thẳng Giả sử 1 2 , n x x  . Đường thẳng qua 1 x và 2 x được định nghĩa là tập     1 2 1 , x x x x         hay   1 2 1 2 1 2 1 2 , , , 1 x x p x p x p p p p        Nếu viết lại định nghĩa đầu tiên theo dạng     1 2 1 , x x x x x        Khi 2 x phương trình trên có dạng   1 2 1 x x x x     , đây là phương trình tham số của đường thẳng qua 1 x và 2 x trong hình học giải tích. 2. Đoạn thẳng Giả sử 1 2 , n x x  . Ta định nghĩa đoạn thẳng nối hai điểm 1 x và 2 x như sau: [i] Đoạn thẳng đóng     1 2 1 2 ; 1 ,0 1 x x x x x x               [ii] Đoạn thẳng mở       1 2 1 2 ; 1 ,0 1 x x x x x x           [iii] Nửa đoạn thẳng đóng – mở      1 2 1 2 ; 1 ,0 1 x x x x x x             [iv] Nửa đoạn thẳng mở – đóng      1 2 1 2 ; 1 ,0 1 x x x x x x             Hiển nhiên 1 2 ; x x     là một đoạn của đường thẳng qua 1 x và 2 x nằm giữa và bao gồm hai điểm 1 x và 2 x .   1 2 ; x x không bao gồm 1 x và 2 x ,  1 2 ; x x   không bao gồm 2 x và  1 2 ; x x   không bao gồm 1 x Hình 2. Đường thẳng và đoạn thẳng qua 1 x và 2 x 3. Tập lồi Một tập n    là tập lồi nếu  chứa hai điểm nào đó thì  chứa cả đoạn thẳng nối hai điểm ấy. Ta nói một tập n    là lồi nếu: 1 2 , ,0 1 x x              1 2 1 x x     
• 5. a] Tập lồi, b] Tập không lồi 4. Nửa không gian mở, đóng Giả sử n c , 0 c  và   . Tập   , n x x cx      [hoặc   , n x x cx      ] được gọi là nửa không gian mở trong n  , và tập   , n x x cx      [hoặc   , n x x cx      ] được gọi là nửa không gian đóng trong n  5. Siêu phẳng Giả sử n c , 0 c  và   . Tập   , n x x cx      được gọi là siêu phẳng trong n  . 6. Không gian con Một tập n    là không gian con nếu 1 2 1 2 , , x x p p        1 2 1 2 p x p x   7. Tổ hợp lồi Một điểm n b gọi là tổ hợp lồi của hệ 1 ,..., m n a a  nếu tồn tại m số thực 1,..., m p p sao cho 1 2 1 2 ... m m b p a p a p a     với 1,..., 0 m p p  và 1 ... 1 m p p    Hoặc, nếu chúng ta định nghĩa một ma trận A cỡ m n  có hàng thứ i là i i A a  và nếu ta lấy   1,..., n m p p p   và e là một m -vectơ thì ta có b là một tổ hợp lồi của hàng thứ i của A nếu ' , 0, 1 b A p p ep    có một nghiệm m p Chú ý rằng nếu b là một tổ hợp lồi của hai điểm 1 2 , n a a  , điều này tương đương với 1 2 , b a a     8. Bao lồi Giả sử n    . Bao lồi của  ký hiệu là    là giao của tất cả các tập lồi trong n  chứa  . Hiển nhiên, nếu  là lồi thì     
• 6.  và bao lồi của nó    9. Đỉnh [điểm cực biên] Giả sử  là tập lồi trong n  . Điểm x được gọi là đỉnh [hay điểm cực biên] của  nếu x không thể biểu diễn được dưới dạng tổ hợp lồi thực sự của hai điểm phân biệt 1 2 , x x  . Một tập lồi n    có thể không có đỉnh [ví dụ như mặt phẳng   , n x x cx      và quả cầu mở   B x  không có đỉnh], số đỉnh có thể là hữu hạn [ví dụ như tập   , 0, 1 n x x x ex      , với e trong một n -vectơ, có n đỉnh i e , 1,2,..., i n  , với i e là một n - vectơ với 1 i i e  và 0 i j e  , i j  ], hay số đỉnh có thể là vô hạn [ví dụ như quả cầu đóng   n B x    là vô hạn số đỉnh được cho bởi   , n x x x x       10. Đa diện và khối đa diện Một tập trong n  mà giao của hữu hạn nửa khoảng đóng trong n  được gọi là đa diện. Nếu một đa diện là giới nội [nghĩa là, mỗi x trong đa diện x   cho vài giá trị không đổi   ] nó được gọi là khối đa diện. BÀI TẬP: Bài 1.1: Chứng minh tập hợp rỗng  là tập lồi? Ta cần chứng minh: 1 2 , ,0 1 x x              1 2 1 x x      Xét hai mệnh đề: 1 2 , x x  và   1 2 1 x x      Đây là các mệnh đề sai Do đó mệnh đề: 1 2 , ,0 1 x x              1 2 1 x x      là mệnh đề đúng.
• 7. tập lồi. Bài 1.2: Chứng minh nửa không gian mở, đóng đều là các tập lồi? Chứng minh nửa không gian mở là tập lồi Đặt   , n x x cx        là nửa không gian mở, ta cần chứng minh: 1 2 , ,0 1 x x              1 2 1 x x      Vì 1 2 , x x  nên có 1 cx   và 2 cx   Do đó:     1 2 1 1 2 1 2 1 1 c x x cx c x c x cx cx cx                  Mặt khác: 2 1 0 cx cx       nên   2 1 0 cx cx    [vì 0 1    ] Do đó:     1 2 1 2 1 1 0 c x x cx cx cx                  Suy ra:   1 2 1 x x      Vậy: Nửa không gian mở   , n x x cx        là tập lồi. [Chứng minh tương tự cho trường hợp nửa không gian đóng] Bài 1.3: Chứng minh mỗi siêu phẳng trong n  là một tập lồi? Đặt   , n x x cx        là siêu phẳng trong n  , ta cần chứng minh: 1 2 , ,0 1 x x              1 2 1 x x      Vì 1 2 , x x  nên 1 cx   và 2 cx   Do đó:     1 2 1 1 2 1 2 1 1 c x x cx c x c x cx cx cx                  Mặt khác: 2 1 0 cx cx       nên   2 1 0 cx cx    Do đó:     1 2 1 2 1 1 0 c x x cx cx cx                  Suy ra:   1 2 1 x x      Vậy: Siêu phẳng   , n x x cx        là tập lồi. Bài 1.4: Chứng minh rằng quả cầu đóng và quả cầu mở là các tập lồi? Chứng minh quả cầu đóng là tập lồi: Xét quả cầu đóng     , n B x x x x x         quanh điểm n x . Ta cần chứng minh:   1 2 , ,0 1 x x B x                   1 2 1 x x B x      
• 8.      1 2 1 2 1 1 1 x x x x x x x                                 1 2 1 x x x x        Áp dụng bất đẳng thức tam giác ta có:           1 2 1 2 1 1 x x x x x x x x              Mà:          1 1 1 1 1 1 x x x x x x            [vì 0 1    ] và:       2 2 2 x x x x x x         [vì 0 1    ] Nên:       1 2 1 2 1 1 x x x x x x x                 Vì :   1 2 , x x B x   nên có: 1 x x    và 2 x x    Do đó:     1 2 1 1 x x x                Hay:   1 2 1 x x x            Suy ra:     1 2 1 x x B x       Vậy: Quả cầu đóng là tập lồi [Chứng minh tương tự cho trường hợp quả cầu mở] Bài 1.5: Chứng minh rằng: Nếu   i i I   là một họ [hữu hạn hoặc vô hạn] tập lồi trong n  , thì giao của chúng i i I    là một tập lồi? Lấy 1 2 , i i I x x     và 0 1    . Khi đó mỗi i I  , 1 2 , i x x  Với mọi 0 1    ta có   1 2 1 i x x      [vì i  là tập lồi] Suy ra   1 2 1 i i I x x         Vậy: i i I    là một tập lồi. Bài 1.6: Chứng minh rằng tổng của hai tập lồi là tập lồi? Giả sử  và  là hai tập lồi trong n  . Ta chứng minh tổng của  và  , kí hiệu là    , là một tập lồi. Lấy 1 2 , z z    , với 1 1 1 2 2 2 , z x y z x y     , trong đó 1 2 , x x  và 1 2 , y y  Với mọi 0 1    ta có:        1 2 1 1 2 2 1 1 z z x y x y                1 2 1 2 1 1 x x y y         
• 9.  là các tập lồi nên có:   1 2 1 x x     và   1 2 1 y y      Do đó:     1 2 1 2 1 1 x x y y            Hay là:   1 2 1 z z        Vậy:    là một tập lồi. Bài 1.7: Chứng minh rằng hiệu của hai tập lồi là tập lồi? Chứng minh tương tự bài 1.6 Bài 1.8: Chứng minh rằng tích của một số thực với một tập lồi là tập lồi? Giả sử  là tập lồi trong n  và   . Ta chứng minh tích của  và  , kí hiệu  , là tập lồi Lấy 1 2 , z z   , với 1 1 2 2 , z x z x     , trong đó 1 2 , x x  Với mọi 0 1    ta có:     1 2 1 2 1 1 z z x x             1 2 1 x x           Suy ra:   1 2 1 z z        Vậy:  là một tập lồi. Bài 1.9: Chứng minh rằng đường thẳng trong n  là tập lồi? Đường thẳng  qua hai điểm 1 x và 2 x được định nghĩa là tập     1 2 1 , x x x x x        Lấy hai điểm bất kỳ thuộc  là   1 2 1 1 x x x    và   1 2 1 2 x x x    Với mọi 0 1    ta có:       1 2 1 1 2 1 1 2 1 x x x x x x                           1 1 2 1 2 1 1 2 1 1 x x x x x x                  1 2 1 1 2 1 x x x              Vậy: Đường thẳng trong n  là tập lồi. Bài 1.10: Chứng minh rằng đoạn thẳng qua hai điểm trong n  là tập lồi? Thay 0 1    trong bài 1.9 ta được kết quả Bài 1.11: Cho   1 2 ; ;...; m x x x  là tổ hợp lồi của các vectơ 1 2 ; ;...; m x x x . Chứng minh  là tập lồi? Ta cần chứng minh:
• 10. x p p p p            1 1 ... m m p x p x    [1] Điều kiện đủ: hiển nhiên. Chẳng hạn lấy 2 m  thì  lồi theo bài 1.10. Điều kiện cần: chứng minh theo quy nạp.  Kiểm tra 1 m  ta có [1] đúng [hiển nhiên]  Giả sử [1] đúng với m k  , ta cần chứng minh [1] đúng với 1 m k   Lấy 1 1 1 1 1 1 ,..., ,..., 0 ... 1 k k k x x p p p p              - Nếu 1 0 k p   thì 1 1 1 1 1 1 ... ... k k k k k k p x p x p x p x p x          . Do đó [1] đúng với mọi m k  - Nếu 1 1 k p   thì 1 2 ... 0 k p p p     . Mà 0 i p  nên 1 1 ... 0 k p p p      1 2 ... 0 k p p p     Do đó: 1 1 1 1 1 1 1 ... k k k k k k k p x p x p x p x x            - Nếu 1 0 1 k p    thì chúng ta có thể viết: 1 1 1 1 1 1 1 1 1 ... k k k k i k k k i i k i i i i i i p p x x p x p p x p p                         Vậy: Tổ hợp lồi là tập lồi. Bài 1.12: Chứng minh rằng đa diện lồi là tập lồi? Giả sử đa diện lồi  sinh bởi các điểm   0, i x i m  là: 1 m i i i x p x    , trong đó 1 1 m i i p    ; 0 i p  , 0, i m  . Lấy 1 1 m i i i x x     , 2 1 m i i i x x     thuộc  [ 1 1 1 m m i i i i         ; 0 i   , 0 i   , 0, i m  ] Với mọi 0 1    ta có:     1 2 1 1 1 1 m m i i i i i i x x x x                    1 1 1 1 1 m m m i i i i i i i i i i i x x x x                         1 1 m i i i i x            
• 11.    1 1 1 1 1 1 1 m m m m m i i i i i i i i i i i i i                                        Và:   1 0 i i       [vì 0 i   , 0 i   , 0, i m  và 0 1    ] Do đó:     1 2 1 1 1 m i i i i x x x                  Vậy:  là một tập lồi. Bài 1.13: Cho các tập lồi 1 A , 2 A ,…, m A và các số thực 1  , 2  ,…, m  . Chứng minh rằng: tập 1 1 2 2 ... m m A A A       cũng là tập lồi? - Trước hết ta chứng minh các 1 1 A  là tập lồi Lấy 1 2 1 1 , z z A   , với 1 1 2 2 1 1 , z x z x     , trong đó 1 2 1 , x x A  Với mọi 0 1    ta có:     1 2 1 2 1 1 1 1 z z x x             1 2 1 1 x x           Vì 1 A là tập lồi nên có:   1 2 1 1 x x A     Suy ra:   1 2 1 1 1 1 x x A            Hay là:   1 2 1 1 1 z z A       Do đó: 1 1 A  là tập lồi. Tương tự ta cũng có 2 2 A  , …, m m A  cũng là các tập lồi. - Tiếp theo ta chứng minh 1 1 2 2 A A    là tập lồi Lấy 1 2 1 1 2 2 , u u A A     , với 1 1 1 2 2 2 1 2 1 2 , u x y u x y         , trong đó 1 2 1 1 1 1 , x x A     và 1 2 2 2 2 2 , y y A     Với mọi 0 1    ta có:        1 2 1 1 2 2 1 2 1 2 1 1 u u x y x y                    1 2 1 2 1 2 1 1 x x y y                    Vì 1 1 A  và 2 2 A  lồi nên có:   1 2 1 1 1 1 x x A           và   1 2 2 2 1 1 y y A            Do đó:     1 2 1 2 1 2 1 1 2 2 1 1 x x y y A A                       Hay là:   1 2 1 1 2 2 1 u u A A         Do đó: 1 1 2 2 A A    là tập lồi. Tương tự ta sẽ chứng minh được 1 1 2 2 3 3 A A A      là tập lồi Từ đó suy ra 1 1 2 2 ... m m A A A       là tập lồi Vậy: 1 1 2 2 ... m m A A A       là tập lồi.
• 12. TOÁN QUY HOẠCH TUYẾN TÍNH và CÁC TÍNH CHẤT CỦA NÓ 1. Các ký hiệu thường dùng trong quy hoạch tuyến tính [QHTT] Giả sử ma trận   11 12 1 21 22 2 1 2 ... ... ... ... ... ... ... n n ij m m mn a a a a a a A a a a a               là ma trận cấp m n  . Ta ký hiệu:    1 2 ; ;...; i i i in A a a a  là ma trận dòng [hay vectơ dòng] thứ i của A  1 2 ... j j j mj a a A a                là ma trận cột [hay vectơ cột] thứ j của A  T A là ma trận chuyển vị của A  1 2 ... j j jm B A A A      là ma trận vuông được thành lập từ m cột của A  1 B là ma trận nghịch đảo của B    1 2 ; ;...; n n u x x x      1 2 ; ;...; n n v y y y      1 2 ; ;...; n n c c c c      1 2 ; ;...; n n b b b b    Tích vô hướng của hai vectơ   1 2 ; ;...; n n c c c c   và   1 2 ; ;...; n n u x x x   được định nghĩa và ký hiệu như sau: 1 1 2 2 , ... n n c u c x c x c x     2. Bài toán QHTT tổng quát Dạng:     , min max f x c u   i i Au b  [1] i i Au b  [2] i i Au b  [3] 0 j x  [4] 0 j x  [5] j x  [6]
• 13. x được gọi là hàm mục tiêu; Mỗi ràng buộc loại [1], [2] và [3] được gọi là ràng buộc cưỡng bức; Mỗi ràng buộc loại [4], [5] và [6] được gọi là ràng buộc tự nhiên; Mỗi vectơ thỏa mãn mọi ràng buộc gọi là một phương án; 3. Bài toán QHTT dạng chuẩn tắc và chính tắc Dạng chuẩn tắc Dạng chính tắc   , min f x c u   Au b  0 u    , min f x c u   Au b  0 u  Bằng phép biến đổi đơn giản dưới đây có thể đưa bài toán quy hoạch tuyến tính bất kỳ về hoặc là dạng chuẩn tắc, hoặc là dạng chính tắc:  Mỗi ràng buộc i i Au b  có thể đưa về 1 i n i Au x b    với 1 0 n x    Mỗi ràng buộc i i Au b  có thể đưa về 1 i n i Au x b    với 1 0 n x    Mỗi ràng buộc i i Au b  có thể viết thành hệ các ràng buộc i i Au b  và i i Au b     Mỗi ẩn j x không có ràng buộc về dấu được viết thành hiệu của hai ẩn mới không âm:   0, 0 j j j j j x x x x x          Mỗi ẩn 0 j x  ta đặt   0 j j j x t t    4. Bài toán QHTT đối ngẫu Các bài toán quy hoạch tuyến tính P và Q sau đây được gọi là đối ngẫu của nhau Bài toán gốc P Bài toán đối ngẫu Q   , min f x c u   i i Au b  i i Au b  i i Au b  0 j x  0 j x  j x    , max T T f y b v   0 j y  0 j y  j y  j j vA c  j j vA c  j j vA c  Nếu bài toán P [bài toán gốc] có các dạng đặc biệt thì bài toán đối ngẫu Q của nó, theo định nghĩa, được xác định như sau:
• 14. P Bài toán đối ngẫu Q   , min f x c u   Au b  0 u    , max T T f y b v   T T T A v c    , max f x c u   Au b  0 u    , min T T f y b v   T T T A v c  Đối với bài toán QHTT bất kỳ, bằng một số phép biến đổi đã biết, có thể đưa hệ ràng buộc về dạng:   , 0 Au b u   Khi đó ta nói hệ ràng buộc đã được chính tắc hóa. 5. Điểm cực biên Giả sử  là tập lồi trong n  . Điểm x được gọi là điểm cực biên của  nếu x không thể biểu diễn được dưới dạng tổ hợp lồi thực sự của hai điểm phân biệt 1 2 , x x  . Định lí: [Tìm điểm cực biên]   : n M u Au b     trong đó A là ma trận cấp m n  là tập lồi đa diện. v M  là điểm cực biên của M khi và chỉ khi tồn tại   1 2 ; ;...; 1;2;...; n i i i m  sao cho   1 2 ; ;...; n i i i a a a là độc lập tuyến tính và v là nghiệm của hệ phương trình , 1;2;...; t t i i a u b t n        , trong đó t i a là hàng thứ t i của ma trận A . 6. Giải bài toán QHTT bằng thuật toán điểm cực biên Xét bài toán QHTT dạng tổng quát:     , min : , n f u c u TT Au b u           Trong đó A là ma trận m n  , n b , n c Gọi: M là tập các phương án chấp nhận được của   TT   ext M là tập các điểm cực biên của M * M là tập các phương án tối ưu của   TT Định lí: * M   khi và chỉ khi M   và hàm mục tiêu   f u bị chặn dưới trên M [nếu   max f u  thì thay điều kiện bị chặn dưới của   f u bởi điều kiện bị chặn trên]
• 15. cực biên giải bài toán QHTT - Bước 1: Kiểm tra * M   - Bước 2: Tìm   ext M - Bước 3: Xác định       min , f u u ext M  [hoặc       max , f u u ext M  ] BÀI TẬP: Bài 2.1: Trong các bài toán sau, bài toán nào là QHTT a] 2 3 min 2 5 1 x y x y y           b] 2 2 max 2 10 3 x y x y xy           c] 5 max 2 2 x y x y           d] 5 max 2 2 x y x y           a] Xét ánh xạ:   2 : ; 2 3 f x y f x y       Lấy:   1 1 ; u x y  và   2 2 ; v x y  Ta có:     1 1 1 1 ; 2 3 f u f x y x y        2 2 2 2 ; 2 3 f v f x y x y                1 2 1 2 1 1 2 2 ; 2 3 3 f u v f x x y y x y x y f u f v           Lại có:         1 1 1 1 1 1 ; 2 3 2 3 f u f x y x y x y f u              Do đó: f là ánh xạ tuyến tính Chứng minh tương tự ta cũng được   ; 2 5 g x y x y    và   ; 1 h x y y   cũng là các ánh xạ tuyến tính Hơn nữa tập         ; : 2 5 ; : 1 G x y x y x y y      là giao của hai tập lồi nên là tập lồi [xem chương 1] Vậy: a] là bài toán QHTT b] Xét ánh xạ:   2 2 2 : ; f x y f x y       Lấy:   1 1 ; u x y  và   2 2 ; v x y 
• 16.    2 2 1 1 1 1 ; f u f x y x y        2 2 2 2 2 2 ; f v f x y x y                        2 2 1 2 1 2 1 2 1 2 2 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 ; 2 2 f u v f x x y y x x y y x y x y x x y y f u f v x x y y f u f v                     Lại có:           2 2 2 2 2 2 2 2 1 1 1 1 1 1 ; f u f x y x y x y f u f u                Do đó: f không là ánh xạ tuyến tính Vậy: b] không là bài toán QHTT c] Ta có: 2 2 x y    2 2 2 2 x y x y         Chứng minh tương tự câu a] ta được   ; 5 g x y x y    ,   ; 2 2 g x y x y    và   ; 2 2 h x y x y    là các ánh xạ tuyến tính Hơn nữa tập         ; : 2 2 ; : 2 2 G x y x y x y x y        là giao của hai tập lồi nên là tập lồi [xem chương 1] Vậy: c] là bài toán QHTT d] Ta có: 2 2 x y    2 2 2 2 x y x y         Chứng minh tương tự câu a] ta được   ; 5 g x y x y    ,   ; 2 2 g x y x y    và   ; 2 2 h x y x y    là các ánh xạ tuyến tính Xét tập         ; : 2 2 ; : 2 2 G x y x y x y x y        Lấy   0;2 u G   và   0; 2 v G    . Chọn 1 2   . Khi đó:         1 1 1 0;2 0; 2 0;0 2 2 u v G          Nên G không là tập lồi Vậy: d] không là bài toán QHTT Bài 2.2: Đưa bài toán sau về dạng chuẩn tắc và chính tắc     1 2 3 1 2 3 1 2 3 1 2 3 1 2 2 min 3 4 5 7 4 0, 0 f x x x x x x x TT x x x x x x x x                        
• 17. toán   TT về dạng chuẩn tắc   TcT : - Đổi dấu hàm mục tiêu để đưa về dạng min   1 2 3 2 min f x x x x      - Đổi dấu ràng buộc thứ hai để đổi chiều bất đẳng thức 1 2 3 7 x x x      - Thay ràng buộc thứ ba bởi hệ hai bất đẳng thức 1 2 3 1 2 3 16 16 x x x x x x            - Ẩn 3 x không có ràng buộc về dấu được viết thành hiệu của hai ẩn mới không âm   3 3 3 3 3 0, 0 x x x x x         Đặt 1 1 x y  , 2 2 x y  , 3 3 x y   , 3 4 x y   ta được bài toán dạng chuẩn tắc là:     1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 2 min 3 4 4 5 7 4 4 0, 1,4 i f y y y y y y y y y y y y y TcT y y y y y y y y y i                                        Đưa bài toán chuẩn tắc   TcT về dạng chính tắc   ToT : - Đưa vào ràng buộc thứ nhất ẩn 5 0 y  ta được: 1 2 3 4 5 3 4 4 5 y y y y y      - Đưa vào ràng buộc thứ hai ẩn 6 0 y  ta được: 1 2 3 4 6 7 y y y y y        Viết lại: 1 2 3 4 6 7 y y y y y      - Thay ràng buộc thứ ba và thứ tư bởi đẳng thức 1 2 3 4 4 y y y y     Ta được bài toán dạng chính tắc là:     1 2 3 4 1 2 3 4 5 1 2 3 4 6 1 2 3 4 2 min 3 4 4 y 5 7 4 0, 1,6 i f y y y y y y y y y ToT y y y y y y y y y y i                              
• 18. bài toán đối ngẫu của bài toán sau     1 2 3 4 1 2 3 4 1 2 3 1 2 3 4 1 3 2 5 min 3 2 4 5 3 7 2 3 2 8 0, 0 f x x x x x x x x x TT x x x x x x x x x                               Ta có:                   1 2 3 4 1 2 3 4 1 1 2 3 2 1 2 3 4 3 1 2 3 4 2 5 min 3 2 4 1 0 5 3 7 2 0 2 3 2 8 3 0 4 5 0 6 7 f x x x x x x x x x y x x x y x x x x y TT x x x x                                                Nên bài toán đối ngẫu là:              1 2 3 1 2 3 1 1 2 3 2 1 2 3 3 1 3 4 1 2 4 7 8 max 3 5 2 2 4 0 2 3 1 5 3 3 6 2 5 7 0, 0 f y y y y y y y x y y y x TT y y y x y y x y y                                           Bài 2.4: Xác định tập các điểm cực biên của các tập lồi đa diện được xác định bởi các hệ sau: a] 1 2 1 2 1 2 1 2 3 2 12 3 15 0, 0 x x x x x x x x                 b] 1 2 1 2 1 2 3 6 4 5 20 0 x x x x x           c] 1 2 3 1 2 3 1 2 3 3 2 15 0, 0, 0 x x x x x x x x x                d] 1 2 3 1 2 3 1 3 2 15 0 x x x x x x x                : n M u Au b     trong đó A là ma trận cấp m n  là tập lồi đa diện. v M  là điểm cực biên của M khi và chỉ khi tồn tại   1 2 ; ;...; 1;2;...; n i i i m  sao cho   1 2 ; ;...; n i i i a a a là độc lập tuyến tính và v là nghiệm của hệ phương trình , 1;2;...; t t i i a u b t n        , trong đó t i a là hàng thứ t i của ma trận A .
• 19. toán bằng hình học Ta có:   1 2 1 2 2 1 2 1 2 1 2 3 2 12 ; : 3 15 0 0 x x x x M x x x x x x                                   Tập M là đa diện lồi OABCD với 5 đỉnh   0;0 O ,   0;3 A ,   2;5 B ,   6;3 C và   5;0 D [mỗi đường thẳng với phần gạch chéo chỉ rõ nửa mặt phẳng bị bỏ đi]. 3 5 2 x 2 6 1 x Vậy: Các điểm cực biên cần tìm là:   0;0 ,   0;3 ,   2;5 ,   6;3 và   5;0 b] Ta có:   1 2 2 1 2 1 2 1 2 3 6 ; : 4 5 20 0 x x M x x x x x                       Ma trận 2 3 4 5 1 0 A               và ma trận 6 20 0 b              Thiết lập các hệ con độc lập tuyến tính gồm đúng 2 vectơ trong hệ gồm 3 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 1 2 2 3 6 1 : 4 5 20 x x x x            . Giải hệ ta được: 1 45 8 ; 48 11 v        -   1 2 1 2 3 6 2 : 0 x x x         . Giải hệ ta được:   2 0; 2 v   -   1 2 1 4 5 20 3 : 0 x x x         . Giải hệ ta được:   3 0;4 v  Kiểm tra ta có 1 2 3 , , v v v M  Vậy: Các điểm cực biên cần tìm là 45 8 ; 48 11       ,   0; 2  và   0;4 c] Ta có:   1 2 3 1 2 3 3 1 2 3 1 2 3 3 2 15 ; ; : 0 0 0 x x x x x x M x x x x x x                                 
• 20. 1 1 1 1 1 0 0 0 1 0 0 0 1 A                      và ma trận 3 15 0 0 0 b                   Thiết lập các hệ con độc lập tuyến tính gồm đúng 3 vectơ trong hệ gồm 5 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 3 1 2 3 1 3 1 : 2 15 0 x x x x x x x                . Giải hệ ta được:   1 0;12; 9 v   -   1 2 3 1 2 3 2 3 2 : 2 15 0 x x x x x x x                . Giải hệ ta được:   2 6;0;9 v  -   1 2 3 1 2 3 3 3 3 : 2 15 0 x x x x x x x                . Giải hệ ta được:   3 3;6;0 v  -   1 2 3 1 2 3 4 : 0 0 x x x x x            . Giải hệ ta được:   4 0;0;3 v  -   1 2 3 1 3 3 5 : 0 0 x x x x x            . Giải hệ ta được:   5 0;3;0 v  -   1 2 3 2 3 3 6 : 0 0 x x x x x            . Giải hệ ta được:   6 3;0;0 v   -   1 2 3 1 2 2 15 7 : 0 0 x x x x x             . Giải hệ ta được:   7 0;0;15 v  -   1 2 3 1 3 2 15 8 : 0 0 x x x x x             . Giải hệ ta được: 8 15 0; ;0 2 v        -   1 2 3 2 3 2 15 9 : 0 0 x x x x x             . Giải hệ ta được:   9 15;0;0 v 
• 21. : 0 0 x x x         . Giải hệ ta được:   10 0;0;0 v  Kiểm tra ta có 2 3 4 5 7 8 9 10 , , , , , , , v v v v v v v v M  Vậy: Các điểm cực biên cần tìm là   6;0;9 ,   3;6;0 ,   0;0;3 ,   0;3;0 ,   0;0;15 , 15 0; ;0 2       ,   15;0;0 và   0;0;0 d] Ta có:   1 2 3 3 1 2 3 1 2 3 1 3 ; ; : 2 15 0 x x x M x x x x x x x                        Ma trận 1 1 1 1 1 1 1 0 0 A                và ma trận 3 15 0 b             Thiết lập các hệ con độc lập tuyến tính gồm đúng 3 vectơ trong hệ gồm 3 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 3 1 2 3 1 3 1 : 2 15 0 x x x x x x x                . Giải hệ ta được:   1 0;12; 9 v   Kiểm tra ta có 1 v M  Vậy: Điểm cực biên cần tìm là   0;12; 9  Bài 2.5: Cho bài toán QHTT             1 2 1 2 1 2 1 2 2 2 max 2 2 1 1 2 1 2 4 3 3 0 4 f x x x x x TT x x x x x                       Trong các phương án sau   1 1;0 x   , 2 2 1 ; 3 6 x          ,   3 7; 1 x    và 4 7 1 ; 9 9 x          , phương án nào là phương án cực biên, phương án nào là phương án tối ưu, phương án nào là phương án cực biên tối ưu? Ta có:       1 2 4 1 f x f x f x     và   3 9 f x   Suy ra:           3 1 2 4 f x f x f x f x    Do đó 3 x không phải là phương án tối ưu [vì   max f x  ]
• 22.   2 cho ta   1 2 1, , f x x x    . Suy ra: 1 x , 2 x và 4 x là các phương án tối ưu. Hơn nữa: 1 x thỏa dấu = với hai ràng buộc   2 và   4 , chúng độc lập tuyến tính. Do đó 1 x là phương án cực biên tối ưu. 2 x thỏa dấu = với hai ràng buộc   1 và   2 , chúng độc lập tuyến tính. Do đó 2 x là phương án cực biên tối ưu. 4 x chỉ thỏa dấu = với một ràng buộc   2 , không đủ hai ràng buộc độc lập tuyến tính. Do đó 4 x là phương án tối ưu không cực biên. 3 x chỉ thỏa dấu = với một ràng buộc   3 , không đủ hai ràng buộc độc lập tuyến tính. Do đó 3 x không phải là phương án cực biên. Bài 2.6: Giải bài toán QHTT sau bằng thuật toán điểm cực biên           1 2 1 2 1 2 1 2 min 2 3 6 1 4 5 20 2 0 3                 f x x x x x TT x x x  Chứng minh * M   - Chứng minh M   Dễ thấy   1;1 là một phương án của bài toán nên M   . - Chứng minh hàm mục tiêu bị chặn dưới Từ ràng buộc [1] ta được: 2 1 2 2 2 3      x x [vì 1 0  x ] Từ ràng buộc [2] ta được: 1 2 5 2 10 2     x x Suy ra: 1 2 2 7 2 10 2      x x x Tức là:     1 2 2 7 7 2 10 10 2 17 2 2             f x x x x [vì 2 2   x ] Do đó hàm mục tiêu   1 2 2    f x x x bị chặn dưới - Suy ra: * M   [vì M   và   f x bị chặn dưới].  Tìm   ext M Ta có:   1 2 2 1 2 1 2 1 2 3 6 ; : 4 5 20 0 x x M x x x x x                      
• 23. 5 1 0 A               và ma trận 6 20 0 b              Thiết lập các hệ con độc lập tuyến tính gồm đúng 2 vectơ trong hệ gồm 3 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 1 2 2 3 6 1 : 4 5 20 x x x x            . Giải hệ ta được: 1 45 8 ; 11 11        v -   1 2 1 2 3 6 2 : 0 x x x         . Giải hệ ta được:   2 0; 2 v   -   1 2 1 4 5 20 3 : 0 x x x         . Giải hệ ta được:   3 0;4 v  Kiểm tra ta được 1 2 3 , , v v v M  Suy ra: Điểm cực biên cần tìm là 45 8 ; 48 11       ,   0; 2  và   0;4  Tìm   min f v   1 45 8 45 8 82 ; 2. 1. 11 11 11 11 11             f v f       2 0; 2 2.0 1. 2 2         f v f     3 0;4 2.0 1.4 4      f v f Ta có:       1 2 3   f v f v f v Nên phương án tối ưu là * 45 8 ; 48 11        x và   * 82 11   f x Vậy:   * 82 11 f x   ứng với * 45 8 ; 11 11 x        Bài 2.7: Giải bài toán QHTT sau bằng thuật toán điểm cực biên             1 2 1 2 2 1 2 1 2 2 max 2 2 1 1 0 2 2 1 3 4 3 4                       f x x x x x TT x x x x x  Chứng minh * M   - Chứng minh M   Dễ thấy   1;0  là một phương án của bài toán nên M   .
• 24. hàm mục tiêu bị chặn trên Từ ràng buộc [3] ta được:     1 2 1 2 2 1 ,      f x x x x x Do đó hàm mục tiêu   1 2 2    f x x x bị chặn trên - Suy ra: * M   [vì M   và   f x bị chặn trên].  Tìm   ext M Ta có:   1 2 2 2 1 2 1 2 1 2 2 2 1 0 ; : 2 1 4 3                             x x x M x x x x x x Ma trận 2 2 0 1 1 2 1 4                   A và ma trận 1 0 1 3               b Thiết lập các hệ con độc lập tuyến tính gồm đúng 2 vectơ trong hệ gồm 4 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 2 2 2 1 1 : 0         x x x . Giải hệ ta được: 1 1 ;0 2         v -   1 2 1 2 2 2 1 2 : 2 1          x x x x . Giải hệ ta được: 2 2 1 ; 3 6          v -   1 2 1 2 2 2 1 3 : 4 3          x x x x . Giải hệ ta được: 3 1 5 ; 3 6        v -   2 1 2 0 4 : 2 1         x x x . Giải hệ ta được:   4 1;0   v -   2 1 2 0 5 : 4 3         x x x . Giải hệ ta được:   5 3;0   v -   1 2 1 2 2 1 6 : 4 3          x x x x . Giải hệ ta được: 5 5 1 ; 3 3         v Kiểm tra ta có 2 4 5 , ,  v v v M Suy ra: Điểm cực biên cần tìm là 2 1 ; 3 6         ,   1;0  và   3;0   Tìm   max f v   2 2 1 2 1 ; 1. 2. 1 3 6 3 6                            f v f
• 25.    4 1;0 1. 1 2.0 1        f v f       5 3;0 1. 3 2.0 3        f v f Ta có:       5 2 4   f v f v f v Nên phương án tối ưu là * 2 1 ; 3 6          x hoặc   * 1;0   x và   * 1   f x Vậy:   * 1   f x ứng với * 2 1 ; 3 6          x hoặc   * 1;0   x Bài 2.8: Giải bài toán sau bằng thuật toán điểm cực biên:     1 2 3 1 2 3 1 2 3 2 3 1 2 2 4 5 2 max 2 2 1 5 2 2 0 f x x x x x x x x x x TT x x x x x                            Chứng minh * M   - Chứng minh M   Dễ thấy   1;1;1 là một phương án của bài toán nên M   . - Chứng minh hàm mục tiêu bị chặn trên Lấy ràng buộc [1] + [2] + [4] ta được: 1 2 3 4 5 x x x    [6] Nhân ràng buộc [3] với 3 ta được: 2 3 3 3 15 x x   [7] Lấy [6] + [7] ta được: 1 2 3 4 2 2 20 x x x    [8] Cộng hai vế của [8] với 2 7x  ta được: 1 2 3 2 4 5 2 20 7 x x x x     Vì 2 0 x  nên 1 2 3 4 5 2 20 x x x    Do đó hàm mục tiêu   1 2 3 4 5 2 f x x x x    bị chặn trên - Suy ra: * M   [vì M   và   f x bị chặn trên].  Tìm   ext M Ta có:   1 2 3 1 2 3 3 1 2 3 2 3 1 2 2 2 2 1 ; ; : 5 2 2 0 x x x x x x M x x x x x x x x                                        
• 26. 2 1 1 1 0 1 1 2 1 0 0 1 0 A                         và ma trận 2 1 5 2 0 b                      Thiết lập các hệ con độc lập tuyến tính gồm đúng 3 vectơ trong hệ gồm 5 vectơ hàng của A , sau đó biểu thị tuyến tính của vectơ b qua chúng ta được: -   1 2 3 1 2 3 2 3 2 2 1 : 1 5 x x x x x x x x                    . Giải hệ ta được: 1 12 16 9 ; ; 5 5 5 v        -   1 2 3 1 2 3 1 2 2 2 2 : 1 2 2 x x x x x x x x                   . Giải hệ ta được:   2 1; 7; 5 v     -   1 2 3 1 2 3 2 2 2 3 : 1 0 x x x x x x x                 . Giải hệ ta được: 3 4 1 ;0; 3 3 v         -   1 2 3 2 3 1 2 2 2 4 : 5 2 2 x x x x x x x                  . Giải hệ ta được: 4 18 22 13 ; ; 7 7 7 v        -   1 2 3 2 3 2 2 2 5 : 5 0 x x x x x x                . Giải hệ ta được:   5 12;0;5 v  -   1 2 3 1 2 2 2 2 6 : 2 2 0 x x x x x x                . Giải hệ ta được: 6 1 1;0; 2 v         -   1 2 3 2 3 1 2 1 7 : 5 2 2 x x x x x x x                  . Giải hệ ta được: 7 8 10 5 ; ; 3 3 3 v        -   1 2 3 2 3 2 1 8 : 5 0 x x x x x x                . Giải hệ ta được:   8 4;0;5 v   -   1 2 3 1 2 2 1 9 : 2 2 0 x x x x x x                . Giải hệ ta được:   9 1;0;0 v 
• 27. 3 1 2 2 5 10 : 2 2 0 x x x x x               . Giải hệ ta được:   10 1;0;5 v  Kiểm tra ta có 1 6 8 9 , , , v v v v M  Suy ra: Điểm cực biên cần tìm là 12 16 9 ; ; 5 5 5       , 1 1;0; 2        ,   4;0;5  và   1;0;0  Tìm   max f v   1 12 16 9 12 16 9 14 ; ; 4. 5. 2. 5 5 5 5 5 5 5 f v f               6 1 1 1;0; 4.1 5.0 2. 3 2 2 f v f                          8 4;0;5 4. 4 5.0 2.5 6 f v f             9 1;0;0 4.1 5.0 2.0 4 f v f      Ta có:         8 1 6 9 f v f v f v f v    Nên phương án tối ưu là   * 1;0;0 x  và   * 4 f x  Vậy:   * 4 f x  ứng với   * 1;0;0 x  Bài 2.9: Cho bài toán QHTT         1 2 1 2 1 2 max 1 1 0, 0 2 f x x x TT ax bx x x             Tìm tất cả các giá trị của tham số a và b sao cho: a] Tập phương án khác rỗng? b] Bài toán đã cho có phương án tối ưu? c] Hàm mục tiêu không bị chặn? a] Với mọi a và b bài toán luôn nhận vectơ   0;0 O làm một phương án, nghĩa là tập phương án luôn khác rỗng. b] Xét ba trường hợp: - Nếu 0 a  và 0 b  , từ các ràng buộc suy ra 1 0 1 ax   và 2 0 1 bx   Hay: 1 1 0 x a   và 2 1 0 x b   Từ đó ta có:   1 2 1 1 f x x x a b     bị chặn trên
• 28.   max f x  , bị chặn trên và tập phương án khác rỗng [theo câu a] nên bài toán có phương án tối ưu. - Xét trường hợp ít nhất một trong các bất đẳng thức 0 a  , 0 b  xãy ra. Giả sử 0 a  . Khi đó   ;0 u t  là phương án với mọi 0 t  Từ đó ta có:   1 2 f x x x t      không bị chặn trên. Tương tự ta cũng có kết luận như vậy nếu 0 b  - Xét trường hợp còn lại: cả hai 0 a  , 0 b  xãy ra. Tương tự ta cũng có   f x không bị chặn Vậy: Bài toán có phương án tối ưu khi 0 a  và 0 b  c] Theo câu b thì khi cả hai 0 a  , 0 b  hoặc một trong hai 0 a  , 0 b  xãy ra thì hàm mục tiêu không bị chặn:
• 29. PHÁP ĐƠN HÌNH Giải các bài toán QHTT sau: Bài 3.1:           1 2 1 2 1 2 1 2 min 2 3 6 1 4 5 20 2 0 3                 f x x x x x TT x x x a] Cách 1: Dùng thuật toán đơn hình dạng chuẩn  Bước 1: Đưa bài toán về dạng chính tắc bằng cách: - Thêm ẩn mới 3 0 x  vào ràng buộc thứ nhất; - Thêm ẩn mới 4 0 x  vào ràng buộc thứ hai; - Thay ẩn 2 x không ràng buộc về dấu bởi 2 2 x x    ; - Đặt 1 1 x y  , 2 2 x y   ; 2 3 x y   , 3 4 x y  , 4 5 x y  ta được bài toán dạng chính tắc sau:     1 2 3 1 2 3 4 1 1 2 3 5 2 min 2 3 3 6 4 5 5 20 0, 1,5 i f y y y y y y y y TT y y y y y i                        Bước 2: Tìm ma trận cực   1 TT thỏa bài toán dạng chuẩn nên có Ta có:   2;1; 1;0;0 c    2 3 3 1 0 4 5 5 0 1 A          và 6 20 b        Chọn: 4 5 1 0 0 1 B A A             Suy ra: 1 1 0 0 1 B        và 1 6 . 20         B b Do đó:   4;5 B J  ,   0;0 B c  và   6;20;0;0;0 B u   Bước 3: Lập bảng giải bài toán   1 TT
• 30. 1 2 3 4 5 Ghi chú B u –2 1 –1 0 0 1 1 4 0 6 2 –3 3 1 0 0 1  j 2 5 0 20 4 5 –5 0 1 0 1 i  0 0 2 –1 1 0 0 3   2 1 1 –2 3 1 3 2  3 2 1 2 0 0 2 j  2 5 0 8 0 11 –11 –2 1 0 2 i  0 -6 0 2 –2 –1 0 8 11   3 1 1 –2 45 11 1 0 0 5 22 3 22 2 2 1 8 11 0 1 –1 2 11  1 11 0 82 11  0 0 0 7 11  2 11   Bước 4: Kết luận Ở bước lặp 3, các 0, j j    nên * 45 8 ; ;0;0;0 11 11 y        là phương án tối ưu và   * 82 11 f y   Suy ra: Phương án tối ưu của bài toán   TT là * 45 8 ; 11 11 x        và   * 82 11 f x   Vậy:   * 82 11 f x   ứng với * 45 8 ; 11 11 x        Nhận xét: Từ bảng thuật toán đơn hình trên ta có nhận xét: bản chất của các công thức đổi cơ sở chính là biến đổi sơ cấp ma trận ở bảng đơn hình bước lặp trước sao cho cột j mới là vectơ đơn vị [phần tử 1 thế chỗ 0 0 i j x ], sau đó ta chỉ cần tính các ước lượng j  . Nếu đề bài không cho trước ma trận cực B là ma trận đơn vị thì ta phải biến đổi sơ cấp ma trận mở rộng để được ma trận đơn vị. Tuy nhiên cần chú ý là phải biến đổi sao cho cột b luôn luôn dương thì mới thỏa mãn giả thiết của phương pháp [xem thêm các bài tập bên dưới].
• 31. Dùng thuật toán đơn hình dạng ma trận nghịch đảo  Bước 1 và Bước 2: giống thuật toán đơn hình dạng chuẩn  Bước 3: Lập bảng giải bài toán   1 TT Ta lập hai bảng đồng thời cùng một lúc Bảng 1 Bước lặp i B J B c 1 B 1 B c B 1 B b  0 1 j B a  0 i 1 1 4 0 1 0 0 6 2 0 1  i 2 5 0 0 1 0 20 4 2 1 1 –2 1 2 0 –1 3 3 2  2 5 0 –2 1 0 8 11 0 2  i 3 1 1 –2 5 22 3 22 7 11  45 11 0 2 2 1 2 11  1 11 2 11  8 11 1 Bảng 2 Bước lặp i 1 2 3 4 5 b –2 1 –1 0 0 1 2 –3 3 1 0 6 2 4 5 –5 0 1 20 1 0 2 –1 1 0 0 0 1  j 2 –6 0 2 –2 –1 0 0 2  j 3 82 11  0 0 0 7 11  2 11   Bước 4: Kết luận Ở bước lặp 3 [bảng 2], các 0, j j    nên * 45 8 ; ;0;0;0 11 11 y        [bảng 1] là phương án tối ưu và   * 82 11 f y   [bảng 2]
• 32. án tối ưu của bài toán   TT là * 45 8 ; 11 11 x        và   * 82 11 f x   Vậy:   * 82 11 f x   ứng với * 45 8 ; 11 11 x        Nhận xét: Từ bảng thuật toán đơn hình gốc và bảng thuật toán đơn hình ma trận nghịch đảo ta có nhận xét: - Cột 0 1 j B a  trong bảng ma trận nghịch đảo chính là cột xoay trong bảng đơn hình gốc; - Cột 1 B b  trong bảng ma trận nghịch đảo chính là cột B u trong bảng đơn hình gốc; - Các cột của ma trận 1 K trong bảng ma trận nghich đảo chính là các cột tương ứng trong bảng đơn hình gốc. Chẳng hạn, từ bài tập trên ta thấy cột 4 x và 5 x trong bảng đơn hình gốc sẽ xuất hiện ở ma trận 1 K trong bảng ma trận nghich đảo; - Các giá trị j  của bảng đơn hình gốc không thay đổi cho bảng đơn hình nghịch đảo; - Như vậy, nếu gặp khó khăn khi tính với ma trận nghịch đảo thì có thể dùng bảng đơn hình gốc để tính, sau đó dùng những nhận xét trên để điền vào bảng đơn hình dạng ma trận nghịch đảo; - Bản chất của vấn đề này đã được đề cập trong lý thuyết, bạn đọc tự tìm hiểu thêm. Bài 3.2:         1 3 4 1 3 4 1 2 3 4 3 max 2 1 1 2 4 2 2 2 0, 1,4                      j f x x x x x x x TT x x x x x j Dùng thuật toán đơn hình dạng chuẩn để giải  Bước 1: Đưa bài toán về dạng chính tắc bằng cách: - Đổi dấu hàm mục tiêu để đưa về dạng min.         1 3 4 1 3 4 1 2 3 4 3 min 2 1 1 2 4 2 2 2 0, 1,4                       j f x x x x x x x TT x x x x x j  Bước 2: Tìm ma trận cực - Biến đổi sơ cấp ma trận mở rộng của hệ phương trình trong ràng buộc để đưa về dạng chuẩn 2 1 2 2 1 0 1 2 1 1 0 1 2 1 2 1 4 2 2 0 1 6 6 0                     h h h Ta có:   1;0;3; 1    c
• 33. 2 0 1 6 6          A và 1 0        b Chọn: 1 2 1 0 0 1             B A A Suy ra: 1 1 0 0 1 B        và 1 1 . 0         B b Do đó:   1;2  B J ,   1;0   B c và   1;0;0;0  B u  Bước 3: Lập bảng giải bài toán   1 TT Bước lặp i B J B c 0 1 2 3 4 Ghi chú B u –1 0 3 –1 1 1 1 –1 1 1 0 –1 2 2 2 0 0 0 1 6 –6 0 –1 0 0 –2 –1  Bước 4: Kết luận Ở bước lặp 1, các 0, j j    nên   1;0;0;0  x là phương án tối ưu và   1   f x Suy ra: Phương án tối ưu của bài toán   TT là   * 1;0;0;0 x  và   * 1  f x Vậy:   * 1  f x ứng với   * 1;0;0;0 x  Bài 3.3:           2 4 6 1 4 5 6 2 4 5 3 4 5 6 3 2 2 min 5 2 10 1 3 2 5 3 8 1 3 0, 1,6                              j f x x x x x x x x TT x x x x x x x x j a] Cách 1: Dùng thuật toán đơn hình dạng chuẩn  Bước 1: Đưa bài toán về dạng chính tắc: - Bái toán đã cho ở dạng chính tắc nên không cần biến đổi  Bước 2: Tìm ma trận cực - Biến đổi sơ cấp ma trận mở rộng của hệ phương trình trong ràng buộc để đưa về dạng chuẩn
• 34. 5 1 2 10 0 1 0 1 1 0 3 0 0 1 5 3 8 1               1 2 2 1 3 3 5 1 0 0 5 1 2 10 1 5 0 0 6 2 25 1 0 1 0 2 10 11                     h h h h h h 1 1 2 2 5 5 1 1 2 0 0 1 2 5 5 5 1 6 2 1 0 0 5 5 5 5 1 0 1 0 2 10 11                           h h h h Ta có:   0; 3;0;2;0;2   c 1 1 2 0 0 1 5 5 5 1 6 2 1 0 0 5 5 5 1 0 1 0 2 10                        A và 2 5 11            b Chọn: 4 2 3 1 0 0 0 1 0 0 0 1                 B A A A Suy ra: 1 1 0 0 0 1 0 0 0 1             B và 1 2 . 5 11             B b Do đó:   4;2;3  B J ,   2; 3;0   B c và   0;5;11;2;0;0  B u  Bước 3: Lập bảng giải bài toán   TT ở dạng chuẩn [sau khi đã biến đổi sơ cấp] Bước lặp i B J B c 0 1 2 3 4 5 6 Ghi chú B u 0 –3 0 2 0 2 1 1 4 2 2 1 5  0 0 1 1 5 2 5 2 2 –3 5 1 5  1 0 0 6 5 2 5 3 3 0 11 –1 0 1 0 –2 10 0 –11 1 5 0 0 0 16 5  12 5   Bước 4: Kết luận
• 35. 1, ta có 1 1 0 5    mà 1 1 1 ; ; 1 0 5 5            x , đó là dấu hiệu chứng tỏ bài toán có tập phương án khác rỗng nhưng hàm mục tiêu không bị chặn. Vậy: Bài toán   TT có hàm mục tiêu không bị chặn b] Cách 2: Dùng thuật toán đơn hình hai pha [dùng ẩn giả]  Bước 1: Đưa bài toán về dạng chính tắc - Bài toán đã cho ở dạng chính tắc nên không cần biến đổi  Bước 2: Thêm ẩn giả - Thêm ẩn giả 7 0  x ta được bài toán dạng chuẩn sau:           2 4 6 7 1 4 5 6 7 1 2 4 5 3 4 5 6 3 2 2 min 5 2 10 1 3 2 5 3 8 1 3 0, 1,7                                 j f x x x x x x x x x x TT x x x x x x x x j  Bước 3: Tìm ma trận cực Ta có:   0; 3;0;2;0;2;   c 1 0 0 5 1 2 1 0 1 0 1 1 0 0 0 0 1 5 3 8 0                A và 10 3 1            b Chọn: 7 2 3 1 0 0 0 1 0 0 0 1                 B A A A Suy ra: 1 1 0 0 0 1 0 0 0 1             B và 1 10 . 3 1             B b Do đó:   7;2;3  B J ,   ; 3;0    B c và   0;3;1;0;0;10  B u  Bước 4: Lập bảng giải bài toán   1 TT
• 36. 1 2 3 4 5 6 7 Ghi chú B u 0 –3 0 2 0 2  1 1 7  10 –1 0 0 5 1 2 1 0 4  j 2 2 –3 3 0 1 0 –1 1 0 0 0 1  i 3 3 0 1 0 0 1 –5 –3 8 0 2   0   0 0 5 1   1   2 2   0 2 1 4 2 2 1 5  0 0 1 1 5 2 5 1 5 2 2 –3 5 1 5  1 0 0 6 5 2 5 1 5 3 3 0 11 –1 0 1 0 –2 10 1 0 –11 1 5 0 0 0 16 5  12 5  1 5     Bước 5: Kết luận Ở bước lặp 2, ta có 1 1 0 5    mà 1 1 1 ; ; 1 0 5 5            x , đó là dấu hiệu chứng tỏ bài toán có tập phương án khác rỗng nhưng hàm mục tiêu không bị chặn. Suy ra: Bài toán   TT có hàm mục tiêu không bị chặn Vậy: Bài toán   TT có hàm mục tiêu không bị chặn c] Cách 3: Dùng thuật toán đơn hình dạng ma trận nghịch đảo  Bước 1 và Bước 2: Giống phần đơn hình dạng chuẩn  Bước 3: Lập bảng đơn hình dạng ma trận nghịch đảo. Ta lập hai bảng sau [hai bảng đồng thời]:
• 37. i B J B c 1 B 1 B c B 1 B b  0 1 j B a  0 i 1 1 4 2 1 0 0 2 2 1 5  2 2 –3 0 1 0 –3 5 1 5  3 3 0 0 0 1 0 11 –1 Bảng 2 Bước lặp i 1 2 3 4 5 6 b 0 –3 0 2 0 2 1 1 5  0 0 1 1 5 2 5 2 2 1 5  1 0 0 6 5 2 5 5 3 –1 0 1 0 –2 10 11 1 –11 1 5 0 0 0 16 5  12 5  0 1  j  Bước 4: Kết luận Ở bước lặp 1, ta có 1 1 0 5    mà 1 1 1 ; ; 1 0 5 5            x , đó là dấu hiệu chứng tỏ bài toán có tập phương án khác rỗng nhưng hàm mục tiêu không bị chặn. Vậy: Bài toán   TT có hàm mục tiêu không bị chặn Bài 3.4:           1 2 3 4 1 2 4 1 2 2 3 4 2 4 max 3 4 1 2 3 2 4 3 3 0, 1,4                            j f x x x x x x x x TT x x x x x x j Dùng thuật toán đơn hình dạng chuẩn để giải  Bước 1: Đưa bài toán về dạng chính tăc bằng cách: - Đổi dấu hàm mục tiêu để đưa về dạng min;
• 38. mới 5 0  x vào ràng buộc thứ nhất; - Thêm ẩn mới 6 0  x vào ràng buộc thứ hai; - Thêm ẩn mới 7 0  x vào ràng buộc thứ ba. - Ta được bài toán dạng chính tắc [và thỏa dạng chuẩn] sau:           1 2 3 4 1 2 4 5 1 1 2 6 2 3 4 7 2 4 min 3 4 1 2 3 2 4 3 3 0, 1,7                              j f x x x x x x x x x TT x x x x x x x x j  Bước 2: Tìm ma trận cực Ta có:   2; 4; 1; 1;0;0;0      c 1 3 0 1 1 0 0 2 1 0 0 0 1 0 0 1 4 1 0 0 1            A và 4 3 3            b Chọn: 5 6 7 1 0 0 0 1 0 0 0 1                 B A A A Suy ra: 1 1 0 0 0 1 0 0 0 1             B và 1 4 . 3 3             B b Do đó:   5;6;7  B J ,   0;0;0  B c và   0;0;0;0;4;3;3  B u  Bước 3: Lập bảng giải bài toán   1 TT
• 39. 1 2 3 4 5 6 7 Ghi chú B u –2 –4 –1 –1 0 0 0 1 1 5 0 4 1 3 0 1 1 0 0 0 2  j 2 6 0 3 2 1 0 0 0 1 0 0 1  i 3 7 0 3 0 1 4 1 0 0 1 4 3   0 0 2 4 1 1 0 0 0 2 1 2 –4 4 3 1 3 1 0 1 3 1 3 0 0 0 3  j 2 6 0 5 3 5 3 0 0 1 3  1 3  1 0 0 3  i 3 7 0 5 3 1 3  0 4 2 3 1 3  0 1 5 12   0 16 3  2 3 0 1 1 3  4 3  0 0 3 1 2 –4 4 3 1 3 1 0 1 3 1 3 0 0 0 1  j 2 6 0 5 3 5 3 0 0 1 3  1 3  1 0 0 2  i 3 3 –1 5 12 1 12  0 1 1 6 1 12  0 1 4 1   0 23 4  3 4 0 0 1 2  5 4  0 4 1 2 –4 1 0 1 0 2 5 2 5 1 5  0 2 1 –2 1 1 0 0 1 5  1 5  3 5 0 3 3 –1 1 2 0 0 1 3 20 1 10  1 20 1 4 0 13 2  0 0 0 7 20  11 10  9 20  1 4 
• 40. Kết luận Ở bước lặp 4, các 0, j j    nên 1 1;1; ;0;0;0;0 2        x là phương án tối ưu và   13 2   f x Suy ra: Phương án tối ưu của bài toán   TT là * 1 1;1; ;0 2 x        và   * 13 2  f x Vậy:   * 13 2  f x ứng với * 1 1;1; ;0 2 x       
• 41. TOÁN ĐỒI NGẪU
• 42. TOÁN VẬN TẢI Giải các bài toán vận tải sau Bài 1: 1 T 2 T 3 T 4 T Dự trữ 1 P 4 7 12 7 50 2 P 5 9 6 1 70 3 P 8 2 9 1 41 Nhu cầu 30 60 46 25  Bước 1: Kiểm tra điều kiện cân bằng thu phát - Tổng thu: 30 60 46 25 161      T - Tổng phát: 50 70 41 161     P - Ta có 161     T P nên bài toán luôn có phương án tối ưu.  Bước 2: Tìm phương án cực biên ban đầu - Sử dụng phương pháp góc Tây Bắc để tìm phương án cực biên ban đầu 1 T 2 T 3 T 4 T Dự trữ 1 P 30 4 20 7 0 12 0 7 50 2 P 0 5 40 9 30 6 0 1 70 3 P 0 8 0 2 16 9 25 1 41 Nhu cầu 30 60 46 25 Ta được: 1 30 20 0 0 0 40 30 0 0 0 16 25            X Số ô chọn là   6 1 m n    nên phương án cực biên ban đầu không suy biến và các ô chọn không lập thành một chu trình nên phương án cực biên ban đầu chấp nhận được. Suy ra:   1 4 30 7 20 9 40 6 30 9 16 1 25 969              f X - Kiểm tra phương án cực biên ban đầu tối ưu hay chưa?
• 43. vị trong phương án cực biên ban đầu 1 X 1 1 1 2 2 2 2 3 3 3 3 4 4 7 9 6 9 1                        u v u v u v u v u v u v  1 2 3 1 2 3 4 0 2 5 4 7 4 4                    u u u v v v v  13 1 3 13 14 1 4 14 21 2 1 21 24 2 4 24 31 3 1 31 32 3 2 32 0 4 12 8 0 4 7 11 2 4 5 1 2 4 1 3 5 4 8 1 5 7 2 10                                                            u v c u v c u v c u v c u v c u v c Các 21 31 32 , , 0     nên phương án cực biên ban đầu chưa tối ưu. Ta xây dựng phương án cực biên mới 2 X không xấu hơn 1 X  Bước 3: Xây phương án cực biên mới 2 X - Ta có:   32 21 31 32 10 max ; ;       nên bổ sung ô     * * ; 3;2  i j vào chu trình ta được           3;2 ; 3;3 ; 2;3 ; 2;2  T 1 T 2 T 3 T 4 T Dự trữ 1 P 30 4 20 7 0 12 0 7 50 2 P 0 5 40- 9 30+ 6 0 1 70 3 P 0 8 0+ 2 16- 9 25 1 41 Nhu cầu 30 60 46 25 Lượng điều chỉnh là:     min , ; 16      ij x i j T Ta được phương án cực biên mới 2 30 20 0 0 0 24 46 0 0 16 0 25            X Suy ra:   2 4 30 7 20 9 24 6 46 2 16 1 25 809              f X Tìm các thế vị trong phương án cực biên 2 X
• 44. 2 2 3 3 2 3 4 4 7 9 6 2 1                        u v u v u v u v u v u v  1 2 3 1 2 3 4 0 2 5 4 7 4 6                    u u u v v v v  13 1 3 13 14 1 4 14 21 2 1 21 24 2 4 24 31 3 1 31 33 3 3 33 0 4 12 8 0 6 7 1 2 4 5 1 2 6 1 7 5 4 8 9 5 4 9 2                                                               u v c u v c u v c u v c u v c u v c Các 21 24 , 0    nên phương án cực biên 2 X chưa tối ưu. Ta xây dựng phương án cực biên mới 3 X không xấu hơn 2 X  Bước 4: Xây phương án cực biên mới 3 X - Ta có:   24 21 24 7 max ;      nên bổ sung ô     * * ; 2;4  i j vào chu trình ta được           2;4 ; 2;2 ; 3;2 ; 3;4  T 1 T 2 T 3 T 4 T Dự trữ 1 P 30 4 20 7 0 12 0 7 50 2 P 0 5 24- 9 46 6 0+ 1 70 3 P 0 8 16+ 2 0 9 25- 1 41 Nhu cầu 30 60 46 25 Lượng điều chỉnh là:     min , ; 24      ij x i j T Ta được phương án cực biên mới 3 30 20 0 0 0 0 46 24 0 40 0 1            X Suy ra:   3 4 30 7 20 6 46 1 24 2 40 1 1 641              f X Tìm các thế vị trong phương án cực biên 3 X 1 1 1 2 2 3 2 4 3 2 3 4 4 7 6 1 2 1                        u v u v u v u v u v u v  1 2 3 1 2 3 4 0 5 5 4 7 11 6                     u u u v v v v  13 1 3 13 14 1 4 14 21 2 1 21 22 2 2 22 31 3 1 31 33 3 3 33 0 11 12 1 0 6 7 1 5 4 5 6 5 7 9 7 5 4 8 9 5 11 9 3                                                                    u v c u v c u v c u v c u v c u v c
• 45. nên phương án cực biên 3 X là phương án tối ưu  Bước 5: Kết luận Vậy: Phương án tối ưu là: * 30 20 0 0 0 0 46 24 0 40 0 1            X Giá trị tối ưu của hàm mục tiêu là   * 641  f X Bài 2: 1 T 2 T 3 T 4 T Dự trữ 1 P 12 9 5 1 75 2 P 5 8 16 2 45 3 P 7 1 5 8 18 4 P 6 5 7 4 110 Nhu cầu 60 48 105 60  Bước 1: Kiểm tra điều kiện cân bằng thu phát - Tổng thu: 60 48 105 60 273      T - Tổng phát: 75 45 18 110 248 P       - Ta có    T P nên bài toán không cân bằng thu phát. Do đó, ta lập thêm một trạm phát giả với lượng phát là 5 273 248 25 P T P        và cước phí là 0 ta được: 1 T 2 T 3 T 4 T Dự trữ 1 P 12 9 5 1 75 2 P 5 8 16 2 45 3 P 7 1 5 8 18 4 P 6 5 7 4 110 5 P 0 0 0 0 25 Nhu cầu 60 48 105 60  Bước 2: Tìm phương án cực biên ban đầu
• 46. phương pháp góc Fo – ghen để tìm phương án cực biên ban đầu 1 T 2 T 3 T 4 T Dự trữ 1 P 0 12 0 9 15 5 60 1 75 2 P 35 5 10 8 0 16 0 2 45 3 P 0 7 18 1 0 5 0 8 18 4 P 0 6 20 5 90 7 0 4 110 5 P 25 0 0 0 0 0 0 0 25 Nhu cầu 60 48 105 60 Ta được: 1 0 0 15 60 35 10 0 0 0 18 0 0 0 20 90 0 25 0 0 0 X                  Số ô chọn là   8 1 m n    nên phương án cực biên ban đầu không suy biến và các ô chọn không lập thành một chu trình nên phương án cực biên ban đầu chấp nhận được. Suy ra:   1 5 15 1 60 5 35 8 10 1 18 5 20 7 90 0 25 1138 f X                  - Kiểm tra phương án cực biên ban đầu tối ưu hay chưa? Tìm các thế vị trong phương án cực biên ban đầu 1 X 1 3 1 4 2 1 2 2 3 2 4 2 4 3 5 1 5 1 5 8 1 5 7 0 u v u v u v u v u v u v u v u v                               1 2 3 4 5 1 2 3 4 0 5 2 2 0 0 3 5 1 u u u u u v v v v                           11 1 1 11 12 1 2 12 23 2 3 23 24 2 4 24 31 3 1 31 33 3 3 33 34 3 4 34 41 4 1 41 44 4 4 44 0 0 12 12 0 3 9 6 5 5 16 6 5 1 2 4 2 0 7 9 2 5 5 2 2 1 8 9 2 0 6 4 2 1 4 u v c u v c u v c u v c u v c u v c u v c u v c u v c                                                                                  52 5 2 52 53 5 3 53 54 5 4 54 1 0 3 0 3 0 5 0 5 0 1 0 1 u v c u v c u v c                                            
• 47. 53 54 , , , 0      nên phương án cực biên ban đầu chưa tối ưu. Ta xây dựng phương án cực biên mới 2 X không xấu hơn 1 X  Bước 3: Xây phương án cực biên mới 2 X - Ta có:   53 24 52 53 54 5 max ; ; ;        nên bổ sung ô     * * ; 5;3 i j  vào chu trình ta được           2;4 ; 2;3 ; 4;3 ; 4;4 T  1 T 2 T 3 T 4 T Dự trữ 1 P 0 12 0 9 15 5 60 1 75 2 P 35+ 5 10- 8 0 16 0 2 45 3 P 0 7 18 1 0 5 0 8 18 4 P 0 6 20+ 5 90- 7 0 4 110 5 P 25- 0 0 0 0+ 0 0 0 25 Nhu cầu 60 48 105 60 Lượng điều chỉnh là:     min , ; 10 ij x i j T      Ta được phương án cực biên mới 2 0 0 15 60 45 0 0 0 0 18 0 0 0 30 80 0 15 0 10 0 X                  Suy ra:     2 1 53 1088 f X f X      Tìm các thế vị trong phương án cực biên 2 X
• 48. 1 3 2 4 2 4 3 5 1 5 3 5 1 5 1 5 7 0 0 u v u v u v u v u v u v u v u v                               1 2 3 4 5 1 2 3 4 0 0 2 2 5 5 3 5 1 u u u u u v v v v                            11 1 1 11 12 1 2 12 22 2 2 22 23 2 3 23 24 2 4 24 31 3 1 31 33 3 3 33 34 3 4 34 41 4 1 41 0 5 12 7 0 3 9 6 0 3 8 5 0 5 16 11 0 1 2 1 2 5 7 4 2 5 5 2 2 1 8 9 2 5 u v c u v c u v c u v c u v c u v c u v c u v c u v c                                                                                   44 4 4 44 52 5 2 52 54 5 4 54 6 1 2 1 4 1 5 3 0 2 5 1 0 4 u v c u v c u v c                                                 41 0   nên phương án cực biên 2 X chưa tối ưu. Ta xây dựng phương án cực biên mới 3 X không xấu hơn 2 X  Bước 4: Xây phương án cực biên mới 3 X - Ta có: 41 1   nên bổ sung ô     * * ; 4;1 i j  vào chu trình ta được           2;4 ; 2;3 ; 4;3 ; 4;4 T  1 T 2 T 3 T 4 T Dự trữ 1 P 0 12 0 9 15 5 60 1 75 2 P 45 5 0 8 0 16 0 2 45 3 P 0 7 18 1 0 5 0 8 18 4 P 0+ 6 30 5 80- 7 0 4 110 5 P 15- 0 0 0 10+ 0 0 0 25 Nhu cầu 60 48 105 60 Lượng điều chỉnh là:     min , ; 15 ij x i j T      Ta được phương án cực biên mới 3 0 0 15 60 45 0 0 0 0 18 0 0 15 30 65 0 0 0 25 0 X                 
• 49.    3 2 41 1073 f X f X      Tìm các thế vị trong phương án cực biên 3 X 1 3 1 4 2 1 3 2 4 1 4 2 4 3 5 3 5 1 5 6 5 5 7 0 u v u v u v u v u v u v u v u v                               1 2 3 4 5 1 2 3 4 0 1 2 2 5 4 3 5 1 u u u u u v v v v                            11 1 1 11 12 1 2 12 22 2 2 22 23 2 3 23 24 2 4 24 31 3 1 31 33 3 3 33 34 3 4 34 44 4 4 44 0 4 12 8 0 3 9 6 1 3 8 4 1 5 16 10 1 1 2 0 2 4 7 5 2 5 5 2 2 1 8 9 2 1 4 u v c u v c u v c u v c u v c u v c u v c u v c u v c                                                                                  1 2 3 4 5 1 2 3 51 5 1 51 4 52 5 2 52 54 5 4 54 0 1 2 2 5 4 3 1 5 5 4 0 1 1 5 3 0 2 5 1 0 4 u u u u u v v v u v c v u v c u v c                                                                              Các 0   ij nên phương án cực biên 3 X là phương án tối ưu  Bước 5: Kết luận Vậy: Phương án tối ưu là: * 0 0 15 60 45 0 0 0 0 18 0 0 15 30 65 0 0 0 25 0 X                  Giá trị tối ưu của hàm mục tiêu là   * 1073 f X 
• 50. KHẢO [1]. Bộ môn Toán ứng dụng, khoa Toán, Đại Học Sư Phạm TP HCM: Giáo trình Quy Hoạch Tuyến Tính giảng dạy lớp VB2-Toán [2]. Phí Mạnh Ban: Bài Tập Quy Hoạch Tuyến Tính, NXB Đai Học Sư Phạm, 2011 [3]. Hoang Tuy: Convex Analysis and Global Optimization, Institute of Mathematics, Hanoi, Vietnam [4] Olvi. Mangasarian: Nonlinear Programming