Tài liệu Nghiên cứu quy hoạch nguyên với mô hình tuyến tính bất kỳ

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH LUẬN VĂN THẠC SĨ TOÁN HỌC Năm 2011 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Chuyên ngành : TOÁN GIẢI TÍCH Mã số : 60 46 01 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học TS. TRỊNH CÔNG DIỆU Năm 2011 Mở đầu Nhiều vấn đề của thực tế cuộc sống hoặc trong các lĩnh vực khoa học kỹ thuật, kinh tế… dẫn đến việc giải quyết các bài toán tối ưu hóa. Trong số các mô hình tối ưu hóa thì hệ tuyến tính liên tục là trường hợp đã có các kết quả tương đối trọn vẹn. Tình hình tương tự cũng xảy ra đối với hệ tuyến tính rời rạc, đó là trường hợp mà tất cả hoặc một số biến chỉ nhận giá trị nguyên. Tuy nhiên các thuật toán giải hệ tuyến tính rời rạc đều áp dụng cho các mô hình có tập phương án bị chặn, cơ sở lý luận cho trường hợp không bị chặn chưa có kết quả nào . Việc hoàn chỉnh cơ sở lý luận cho các thuật toán giải quy hoạch nguyên là một việc làm cần thiết. Luận văn này sẽ góp phần làm điều đó. Luận văn được chia làm 4 chương: Chương 1: Cấu trúc tập ràng buộc của bài toán quy hoạch tuyến tính Chương 2: Bài toán quy hoạch tuyến tính nguyên Chương 3: Thuật toán cắt Gomory giải bài toán quy hoạch tuyến tính nguyên Chương 4: Thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên. Luận văn trình bày chi tiết một số kết quả của quy hoạch tuyến tính nguyên. Việc nghiên cứu quy hoạch nguyên với mô hình tuyến tính bất kỳ đã có thêm một số kết quả (không có trong các tài liệu, giáo trình về quy hoạch tuyến tính nguyên đang lưu hành) như sau: + Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bài toán quy hoạch tuyến tính (không có điều kiện nguyên) tương ứng (định lý 2.4,2.5). + Mở rộng điều kiện sử dụng phương pháp nhánh cận (định lý 4.6), do đó cho phép thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên có thể áp dụng cho một lớp bài toán rộng hơn các kết quả đã có. Trong luận văn này có thể xem các kết quả trên là đóng góp của tác giả cho việc khảo sát bài toán quy hoạch tuyến tính nguyên. Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến Tiến sĩ Trịnh Công Diệu, Thầy đã tận tình hướng dẫn và tạo điều kiện thuận lợi giúp tôi hoàn thành luận văn này. Tôi xin gởi lời cảm ơn chân thành đến quý thầy cô trường Đại học Sư phạm Tp. Hồ Chí Minh đã nhiệt tình giảng dạy tôi trong suốt quá trình học tập. Tôi cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn này. Mục lục Mở đầu ......................................................................................................... 3 Mục lục ........................................................................................................ 4 Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ............................................................................ 6 1.1. Tập lồi, tập affine và tập nón.................................................................................. 6 1.1.1. Tập lồi ........................................................................................................................6 1.1.2. Tập affine ...................................................................................................................6 1.1.3. Tập nón ......................................................................................................................7 1.2. Tập lồi đa diện ........................................................................................................ 7 1.2.1. Điểm và phương cực biên của tập lồi, đóng ..............................................................7 1.2.2. Tập lồi đa diện ...........................................................................................................9 Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN...... 20 2.1. Khái niệm bài toán quy hoạch tuyến tính nguyên ................................................ 20 2.2. Mối liên hệ giữa dạng chuẩn tắc và chính tắc của bài toán quy hoạch tuyến tính nguyên ......................................................................................................................... 20 2.3. Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bài toán quy hoạch tuyến tính tương ứng .......................................................................... 22 Chương 3: THUẬT TOÁN CẮT GOMORY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 25 3.1. Bảng đơn hình ...................................................................................................... 25 3.1.1. Khái niệm .................................................................................................................25 3.1.2. Phép biến đổi cơ bản của bảng đơn hình .................................................................26 3.2. So sánh theo nghĩa từ vựng .................................................................................. 27 3.2.1. Các khái niệm cơ bản ...............................................................................................27 3.2.2. Các tính chất cơ bản .................................................................................................27 3.2.3. Tối ưu theo nghĩa từ vựng........................................................................................28 3.3. Bảng đơn hình l-chuẩn ......................................................................................... 29 3.4. Thuật toán đơn hình đối ngẫu từ vựng tìm phương án tối ưu từ vựng................. 30 3.5. Thuật toán cắt Gomory ......................................................................................... 41 3.5.1. Điều kiện để sử dụng thuật toán Gomory ................................................................41 3.5.2. Thuật toán cắt Gomory ............................................................................................42 3.5.3. Cơ sở lí luận của thuật toán......................................................................................43 3.5.4. Ví dụ.........................................................................................................................48 Chương 4: THUẬT TOÁN NHÁNH CẬNGIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 52 4.1. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính ....................... 52 4.2. Kỹ thuật tái tối ưu hóa .......................................................................................... 53 4.3. Thuật toán nhánh cận ........................................................................................... 54 4.3.1. Điều kiện để sử dụng thuật toán nhánh cận .............................................................54 4.3.2. Thuật toán nhánh cận ...............................................................................................54 4.3.3. Cơ sở lí luận của thuật toán......................................................................................56 4.3.4. Ví dụ.........................................................................................................................61 Kết luận ..................................................................................................... 65 Tài liệu tham khảo.................................................................................... 66 Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1. Tập lồi, tập affine và tập nón 1.1.1. Tập lồi + Đoạn thẳng: Tập hợp {λ x + (1 − λ ) y : λ ∈ [ 0;1]} với x, y ∈  n được gọi là đoạn thẳng nối x và y và được ký hiệu là [ x; y ] . Nhận xét: [ x; y ] = [ y; x ] . + Tập lồi: A ⊂  n được gọi là tập lồi nếu x, y ∈ A ⇒ [ x; y ] ∈ A . Ví dụ: ∅,  n là các tập lồi. + Bao lồi: Giao của tất cả các tập lồi chứa A được gọi là bao lồi của A . Kí hiệu bao lồi của A là convA . Nhận xét: - Bao lồi của A là tập lồi nhỏ nhất (theo nghĩa bao hàm) chứa A .  k   i =1  - conv { x1 , x2 ,..., xk= } λ1 x1 + λ2 x2 + ... + λk xk : ∑ λ=i 1, λi ≥ 0∀=i 1, k  1.1.2. Tập affine + Đường thẳng: Tập hợp {λ x + (1 − λ ) y : λ ∈ } với x, y ∈  n được gọi là đường thẳng đi qua x và y . + Tập affine: - A ⊂  n gọi là tập affine nếu x, y ∈ A thì đường thẳng đi qua x, y cũng nằm trong A . Định lý 1.1: [4, tr.7-8] Nếu A là tập affine và a ∈ A thì tập L = { y : ∃x ∈ A, y = x − a} là không gian con của  n đồng thời L là duy nhất đối với A và không phụ thuộc vào a . Ta cũng viết A= a + L . - Số chiều của tập affine: Số chiều của tập affine A là số chiều của không gian con L gắn với A , tức là A= a + L .Kí hiệu số chiều của A là dim A . - Bao affine: Giao của tất cả các tập affine chứa A được gọi là bao affine của A . Kí hiệu bao affine của A là affA . Nhận xét: Bao affine của A là tập affine nhỏ nhất (theo nghĩa bao hàm) chứa A . + Số chiều của một tập bất kỳ: Số chiều của tập A ⊂  n là số chiều của bao affine của A . 1.1.3. Tập nón + Tập nón: A ⊂  n được gọi là là tập nón nếu x ∈ A ⇒ λ x ∈ A, ∀λ > 0 . + Tập nón hữu hạn sinh: - Tập hợp {λ1 x1 + λ2 x2 + ... + λk xk : λi ≥ 0, ∀i ∈1, k} với xi ∈  n được gọi là nón sinh bởi { x1 , x2 ,..., xk } , ký hiệu là cone { x1 , x2 ,..., xk } . - Tổ hợp tuyến tính λ1 x1 + λ2 x2 + ... + λk xk với λi ≥ 0, ∀i ∈1, k được gọi là tổ hợp nón của x1 , x2 ,..., xk . Nhận xét: Tập nón hữu hạn sinh là một tập nón và cũng là tập lồi. 1.2. Tập lồi đa diện 1.2.1. Điểm và phương cực biên của tập lồi, đóng Cho A là tập lồi và đóng. 1.2.1.1. Điểm cực biên của tập lồi, đóng + x ∈ A được gọi là điểm cực biên của A nếu không tồn tại y, z ∈ A, y ≠ z sao cho x ∈ [ y; z ] \ { y, z} ,tức là không tồn tại y, z ∈ A, y ≠ z và λ ∈ ( 0;1) sao cho x = λ y + (1 − λ ) z . + Tập hợp các điểm cực biên của A được kí hiệu là extA . 1.2.1.2. Phương vô tận của tập lồi, đóng u ∈  n được gọi là phương vô tận của A nếu u ≠ 0 và x + λu ∈ A, ∀x ∈ A, λ > 0 . Nhận xét: Nếu u là phương vô tận của thì λu cũng là phương vô tận của A với mọi λ > 0 . Như vậy tập hợp các phương vô tận của A là tập nón. Vì thế ta thường gọi tập các phương vô tận của A là nón các phương vô tận của A . Định lý 1.2: Một tập lồi đóng và không bị chặn thì có phương vô tận. Chứng minh: Xét A ⊂  n là tập lồi đóng và không bị chặn. Vì A không bị chặn nên tồn tại dãy {ak } ⊂ A sao cho compact {x ∈  n lim ak = +∞ . Xét dãy {bk } xác định bởi bk = k →∞ ak . Dãy {bk } nằm trong tập ak : x = 1} nên chứa dãy con hội tụ. Không giảm tổng quát, ta có thể xem lim bk = u . Ta chứng minh u là phương vô tận của A. k →∞ Đầu tiên, ta thấy u ≠ 0 ( u = 1) do lim bk = u và bk = 1, ∀k . k →∞ Xét x ∈ A và λ > 0 cho trước. Do lim ak = +∞ nên với k đủ lớn ta có 0 < k →∞ λ ak < 1. Do A lồi nên ta có  λ  λ ak ∈ A . 1 −  x + ak  ak   λ  λ Mặt khác, ta có lim 1 − ak = x + λu và do A đóng nên x + λu ∈ A .  x + k →∞ ak  ak  Vậy u là phương vô tận của A. 1.2.2.2. Phương cực biên của tập lồi, đóng + u ∈  n được gọi là phương cực biên của A nếu u là phương vô tận của A và không tồn tại 2 phương vô tận độc lập tuyến tính v, w của A và α , β > 0 sao cho = u αv + β w . Nhận xét: Vì nếu u là phương vô tận của A thì λu cũng là phương vô tận của A với λ > 0 nên ta có thể định nghĩa phương cực biên của tập lồi, đóng như sau: + u ∈  n được gọi là phương cực biên của A nếu u là phương vô tận của A và không tồn tại 2 phương vô tận độc lập tuyến tính v, w của A sao cho u= v + w . 1.2.2. Tập lồi đa diện 1.2.2.1. Khái niệm tập lồi đa diện + Tích vô hướng trong  n : Tích vô hướng của 2 véc tơ x, y ∈  n là số thực x, y = x1 y1 + x2 y2 + ... + xn yn , với x = x1 , x2 ,..., xn ) , y ( y1 , y2 ,..., yn ) . (= + Siêu phẳng: Tập hợp có thể quy về dạng { x ∈  n : a, x = b} ( a ≠ 0, b ∈  ) được gọi là siêu phẳng trong  n . Nhận xét: Siêu phẳng là một tập affine. + Nửa không gian đóng : Tập hợp có thể quy về dạng { x ∈  n : a, x ≤ b} ( a ≠ 0, b ∈  ) được gọi là nửa không gian đóng trong  n . Nhận xét: Nửa không gian đóng là một tập lồi và đóng. + Tập lồi đa diện: D ⊂  n được gọi là tập lồi đa diện nếu D là giao của hữu hạn các nửa không gian đóng. Nhận xét: Tập lồi đa diện là một tập lồi và đóng. m Cho D ⊂  n là tập lồi đa diện. D =  H i trong đó H i là các nửa không gian đóng. i =1 Biểu diễn  b1   a11  a1n    Hi = { x ∈  : ai , x ≤ bi } ; ai = ( ai1 , ai 2 ,..., ain ) ; A =      , b =   . a  b   m1  amn   m n Khi ấy, ta có thể biểu diễn tập lồi đa diện D dưới dạng D= {x ∈  n } : ai , x ≤ bi , ∀i = 1, m ( ∗) hoặc D= { x ∈  n : Ax ≤ b} . (∗∗) Chú ý: Trong chương này kể từ về sau khi đề cập đến tập lồi đa diện D thì ta hiểu D được cho dưới dạng ( ∗) hoặc ( ∗∗) . Như nhận xét trên, tập lồi đa diện là một tập lồi đóng. Do đó tập lồi đa diện cũng có các khái niệm điểm cực biên, phương vô tận và phương cực biên. Phần tiếp theo ta sẽ nghiên cứu các khái niệm ấy của tập lồi đa diện 1.2.2.3. Điểm cực biên của tập lồi đa diện Bổ đề 1.3: Cho D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Khi ấy, nếu x thuộc D và x không phải là điểm cực biên thì tồn tại y thuộc D thỏa + Nếu ai , x = bi thì ai , y = bi . + Tồn tại i ∈1, m sao cho ai , x < bi và ai , y = bi . Chứng minh: + Vì x ∉ extD nên tồn tại y, z ∈ D, y ≠ z và λ ∈ ( 0;1) sao cho x = λ y + (1 − λ ) z . Vậy nếu ai , x = bi thì ta có λbi ≥ λ ai , = y ai , x − (1 − λ ) ai , z ≥ bi − (1 − λ )= bi λbi Suy ra ai , y = bi . Tương tự đối với z . Vậy ta có a= i, y = ai , z = ai , x bi . + Trước hết ta chứng tỏ tồn tại i ∈1, m sao cho ai , x < bi . Giả sử ngược lại, ai , x = bi với mọi i ∈1, m . Theo như chứng minh phần trên, ta có ai , y = ai , z = ai , x = bi , ∀i = 1, m . Vậy với mọi λ > 0 , ta có ai , λ y + (1 − λ ) z = λ ai , y + (1 − λ ) ai , z = bi , ∀i = 1, m . Suy ra D chứa đường thẳng qua y,z . Điều này mâu thuẫn với giả thiết D không chứa đường thẳng. Vậy tồn tại i ∈1, m sao cho ai , x < bi . Do D không chứa đường thẳng nên đoạn thẳng [ y; z ] không thể kéo dài mãi về 2 phía (mà vẫn còn nằm trong D ). Không mất tính tổng quát ta xem đường thẳng qua y,z thoát ra khỏi D tại y. Giả sử với mọi i ∈1, m nếu ai , x < bi thì ta cũng có ai , y < bi . Không mất tính tổng quát ta giả sử ai , y = ai , x = bi , ∀i = 1, k , ai , y < bi , ai , x < bi , ∀i = k + 1, m . Với mỗi t > 0 , ta đặt yt =y + t ( y − x ) . Với mỗi i ∈ k + 1, m , chọn bi′ < bi sao cho ai , y < bi′ . Khi ấy, với t > 0 đủ nhỏ, ta có ai , yt = ai , y + t ai , y − x < bi′ + t ai , y − x < bi , ∀i =k + 1, m . Mặt khác, ai , yt = bi , ∀i = 1, k do ai , y = ai , x = bi , ∀i = 1, k . Vậy nên yt ∈ D với t > 0 đủ nhỏ. Như vậy đoạn thẳng [ y; z ] có thể kéo dài về phía y tới yt sao cho nó vẫn còn nằm trong D . Điều này mâu thuẫn với giả sử đường thẳng qua y,z thoát ra khỏi D tại y. Định lý 1.4: Tập lồi đa diện khác rỗng nếu không chứa đường thẳng thì có điểm cực biên. Chứng minh: Xét D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Chọn x ∈ D bất kỳ. Nếu x ∈ extD , ta có điều phải chứng minh.Ngược lại, giả sử x ∉ extD . Theo bổ đề 1.3 có x1 ∈ D sao cho tồn tại i ∈1, m thoả mãn ai , x < bi và ai , x1 = bi . Đặt H i = bi } . Ta có x ∉ H i . Đặt D1 = H i  D . { x ∈  n : ai , x = Ta chứng minh dim D1 < dim D . Thậy vậy, giả sử dim D1 = dim D . Vì D1 ⊂ D nên affD1 ⊂ affD . Lại có dim D1 = dim D nên affD1 = affD . Vì D1 ⊂ H i nên affD1 ⊂ affH i = H i . Suy ra affD ⊂ H i . Điều này mâu thuẫn vì x ∈ D ⊂ affD nhưng x ∉ H i . Ta chứng minh extD1 ⊂ extD . Xét x ∈ extD1 . Giả sử x ∉ extD . Khi ấy tồn tại H i  D nên ai , x = bi . Do y, z ∈ D, y ≠ z và λ ∈ ( 0;1) sao cho x = λ y + (1 − λ ) z . Vì x ∈ D1 = x = λ y + (1 − λ ) z với λ ∈ ( 0;1) nên ta cũng có a= i, y = ai , z bi . Suy ra y, z ∈ D  H i nghĩa là y, z ∈ D1 . Vậy tồn tại y, z ∈ D1 , y ≠ z và λ ∈ ( 0;1) sao cho x = λ y + (1 − λ ) z . Điều này mâu thuẫn với giả thiết x ∈ extD1 . Do đó extD1 ⊂ extD . Vậy nếu x1 là điểm cực biên của D1 thì x1 cũng là điểm cực biên của D. Ta có điều phải chứng minh. Ngược lại nếu x1 không phải là điểm cực biên của D1 thì ta lập luận như trên và giảm được dim D1 vì D1 cũng là tập lồi đa diện khác rỗng và không chứa đường thẳng. Quá trình lập luận này phải dừng lại ở một bước k nào đó mà xk là điểm cực biên của Dk . Do extDk ⊂ ... ⊂ extD1 ⊂ extD nên xk là điểm cực biên của D. Định lý 1.5: Cho tập lồi đa diện D khác rỗng . Nếu x là điểm cực biên của D thì tồn tại hệ gồm n vectơ độc lập tuyến tính {a j , a j ,..., a j } lấy từ hệ {a1 , a2 ,..., am } sao cho a j , x = b j , ∀i= 1, n . 1 2 n i i Chứng minh: Giả sử ngược lại có tối đa k < n vectơ độc lập tuyến tính {a j , a j ,..., a j } lấy từ hệ 1 {a1 , a2 ,..., am } sao cho 2 k a ji , x = b ji , ∀i= 1, k . Đặt L = a j , a j ,..., a j . Vì dim L⊥ = n − dim L = n − k ≥ 1 nên tồn tại h ∈ L⊥ , h ≠ 0 . Vậy 1 2 k với ε > 0 đủ nhỏ, ta có ai , x ± ε h = ai , x ≤ bi nếu ai ∈ L và ai , x ± ε h < bi nếu ai ∉ L . Như vậy x ± ε h ∈ D và x + ε h ≠ x − ε h do h ≠ 0 . Mặt khác, ta có x = 1 1 ( x + ε h ) + ( x − ε h ) . Điều 2 2 này mâu thuẫn với x là điểm cực biên. Số cách chọn n vectơ từ m vectơ là hữu hạn. Do đó ta có hệ quả sau Hệ quả 1.6: Tập hợp các điểm cực biên của tập lồi đa diện có hữu hạn phần tử. 1.2.2.4. Phương vô tận của tập lồi đa diện Định lý 1.7: Cho tập lồi đa diện D khác rỗng. Khi ấy u là phương vô tận của D nếu và chỉ nếu u ≠ 0 và Au ≤ 0 . Chứng minh: Nếu u là phương vô tận của D thì u ≠ 0 và với x ∈ D , ta có A( x + λu ) ≤ b, ∀λ > 0 . Nghĩa là ai , x + λu ≤ bi , ∀λ > 0 . Nếu ai , u > 0 thì với λ đủ lớn, ta có ai , x + λu > bi . Như vậy, ta phải có ai , u ≤ 0, ∀i =1, m hay Au ≤ 0 . Nếu u ≠ 0 và Au ≤ 0 thì với x ∈ D , ta có A( x + λu ) = Ax + λ Au ≤ b, ∀λ > 0 do Ax ≤ b, Au ≤ 0, λ > 0 . Vậy u là phương vô tận của D. 1.2.2.5. Phương cực biên của tập lồi đa diện Định lý 1.8: Cho tập lồi đa diện D khác rỗng. Nếu u là phương cực biên của D thì tồn tại hệ n − 1 vectơ độc lập tuyến tính {a j , a j ,..., a j 1 2 n−1 } lấy từ hệ {a , a ,..., a } sao cho 1 2 m a ji , u = 0, ∀i = 1, n − 1 . Chứng minh: Giả sử ngược lại có tối đa k < n − 1 vectơ độc lập tuyến tính {a j , a j ,..., a j } lấy từ hệ 1 {a1 , a2 ,..., am } sao cho 2 k a ji , u = 0, ∀i = 1, k . Đặt L = a j , a j ,..., a j . Ta có u ∈ L⊥ ; ai , u = 0 nếu ai ∈ L và ai , u < 0 nếu ai ∉ L . 1 2 k Vì dim L⊥ = n − dim L = n − k ≥ 2 nên tồn tại h ∈ L⊥ độc lập tuyến tính với u. Vậy với 0 nếu ai ∈ L và ai , u + ε h < 0 nếu ai ∉ L .Do vậy theo định ε > 0 đủ nhỏ, ta có ai , u + ε h = lý 1.4, hai vectơ u ± ε h là các phương vô tận và là các phương vô tận độc lập tuyến tính do 2 vectơ u,h độc lập tuyến tính. Mặt khác, ta có u = 1 1 ( u + ε h ) + ( u − ε h ) . Điều này mâu thuẫn với u là phương cực 2 2 biên. Hệ quả 1.9: Tập hợp các phương cực biên của tập lồi đa diện ( không kể các phương cực biên cùng phương) có hữu hạn phần tử. 1.2.2.6. Cấu trúc của tập lồi đa diện không chứa đường thẳng Định lý 1.10: Tập lồi đa diện bị chặn chính là bao lồi của các điểm cực biên của nó. Chứng minh: Xét D tập lồi đa diện bị chặn. Ta sẽ chứng minh D = conv ( extD ) . Vì D là tập lồi chứa extD nên conv ( extD ) ⊂ D . Ta chứng minh D ⊂ conv ( extD ) (*) bằng quy nạp theo n = dim D . (*) đúng với n = 0 vì khi ấy D có một phần tử duy nhất. Giả sử (*) đúng với mọi n < k , ta chứng minh (*) cũng đúng với n = k . Thật vậy, xét x ∈ D . Nếu x ∈ extD thì ta có điều phải chứng minh. Giả sử x ∉ extD . Khi ấy tồn tại y, z ∈ D, y ≠ z và λ ∈ ( 0;1) sao cho x = λ y + (1 − λ ) z . Do D bị chặn nên đường thẳng qua y,z thoát ra khỏi D tại 2 điểm. Không mất tính tổng quát ta giả sử hai điểm đó là y và z. Theo bổ đề 1.3, ta có tồn tại i ∈1, m thoả mãn ai , x < bi và ai , y = bi . Đặt H i = bi } . Đặt D1 = H i  D . Như trong chứng minh định lý 1.4, ta { x ∈  n : ai , x = có dim D1 < dim D và extD1 ⊂ extD .Theo giả thiết quy nạp ta có D1 ⊂ conv ( extD1 ) . Suy ra y ∈ D1 ⊂ conv ( extD1 ) ⊂ conv ( extD ) ( extD1 ⊂ extD ) . Tương tự ta cũng có z ∈ conv ( extD ) . Vậy x ∈ [ y; z ] ⊂ conv ( extD ) . Định lý 1.11: Tập lồi đa diện D khác rỗng và không chứa đường thẳng có thể biểu diễn dưới dạng = D conv ( extD ) + {u ∈  n : Au ≤ 0} . Chứng minh: Vì conv ( extD ) ⊂ D nên conv ( extD ) + {u ∈  n : Au ≤ 0} ⊂ D . Ta chứng minh D ⊂ conv ( extD ) + {u ∈  n : Au ≤ 0} (*) bằng quy nạp theo n = dim D . Rõ ràng (*) đúng với n = 0 . Giả sử (*) đúng với mọi n < k , ta chứng minh (*) cũng đúng với n = k . Nếu D bị chặn thì theo định lý 1.7, D = conv ( extD ) . Ta có điều phải chứng minh. Ngược lại, giả sử D không bị chặn thì theo định lý 1.2 , D có phương vô tận hay tồn tại v ≠ 0, v ∈ {u ∈  n : Au ≤ 0} . Xét x ∈ D . Ta có tia { x − λ v : λ ≥ 0} phải thoát khỏi D tại một điểm y nào đó vì nếu không D sẽ chứa toàn bộ đường thẳng qua x phương v – đường thẳng { x + λ v : λ ∈ } . Theo bổ đề 1.3, ta có tồn tại i ∈1, m thoả mãn ai , x + v < bi và ai , y = bi . Đặt H i = bi } . Đặt D1 = H i  D . Như trong chứng minh định lý 1.4, ta { x ∈  n : ai , x = có dim D1 < dim D và extD1 ⊂ extD . Vì D1 cũng là tập lồi đa diện không chứa đường thẳng nên theo giả thiết quy nạp, ta có D1 ⊂ conv ( extD1 ) + {u ∈  n : Au ≤ 0, ai , u = 0} . Do extD1 ⊂ extD nên D1 ⊂ conv ( extD ) + {u ∈  n : Au ≤ 0} . Đặt y = x − λ0 v ( λ0 > 0 ) . Ta có x = y + λ0 v ∈ D1 + {u ∈  n : Au ≤ 0} D1 ⊂ conv ( extD ) + {u ∈  n : Au ≤ 0} . Vậy D ⊂ conv ( extD ) + {u ∈  n : Au ≤ 0} . Bổ đề 1.12: Nếu D là tập lồi đa diện không chứa đường thẳng thì nón các phương vô hạn – tập hợp {u ∈  n : Au ≤ 0} là tập nón hữu hạn sinh. Chứng minh: Ta chứng minh G = {u ∈  n : Au ≤ 0} là tập nón hữu hạn sinh (*) bằng quy nạp theo n = dim G . G Nếu n = 0 thì = 0} {= cone {0} .Vậy (*) đúng với n = 0 . Giả sử (*) đúng với mọi n < k ( k ≥ 1) , ta chứng minh (*) cũng đúng với n = k . Do dim G= k ≥ 1 nên tồn tại v ∈ G, v ≠ 0 . Xét x ∈ G . Ta có tia { x − λ v : λ ≥ 0} phải thoát khỏi G tại một điểm y nào đó vì nếu không sẽ chứa toàn bộ đường thẳng qua x phương v – đường thẳng { x + λ v : λ ∈ } và khi ấy D cũng chứa đường thẳng. Theo bổ đề 1.3, ta có tồn tại i ∈1, m thoả mãn ai , x + v < 0 và ai , y = 0 . Đặt H i = {x ∈  n : ai , x = 0} , ∀i = 1, m . Đặt Gi = H i  G . Như trong chứng minh định lý 1.4, ta có dim Gi < dim G . Vậy theo giả thiết quy nạp, ta có Gi = coneRi với Ri là tập hữu hạn. Đặt y = x − λ0 v ( λ0 > 0 ) . Ta có x =y + λ0 v ∈ cone ( Ri  {v} ) . Do số ràng buộc ai , x = 0 là hữu hạn ( m ràng buộc) nên G ⊂ coneR với R là tập hữu hạn. Vì R ⊂ G nên coneR ⊂ G . Vậy G = coneR . Định lý 1.13: Nếu D là tập lồi đa diện không chứa đường thẳng thì nón các phương vô hạn – tập hợp {u ∈  n : Au ≤ 0} là tập nón sinh bởi các phương cực biên của D. Chứng minh: Theo bổ đề 1.12, ta giả sử rằng {u ∈  n : Au ≤ 0} = cone { x1 ,..., xk } . Ta nhận xét rằng nếu x1 có thể biểu diễn thành tổ hợp nón của các xi còn lại thì ta có thể loại nó ra khỏi { x1 ,..., xk } vì khi ấy ta có cone { x1 , x2 ,..., xk } = cone { x2 ,..., xk } .Vậy ta giả thiết rằng { x1 ,..., xk } gồm các phần tử mà mỗi phần tử không thể biểu diễn thành tổ hợp nón của các phần tử còn lại. Khi ấy ta có xi là phương cực biên với mọi i ∈1, k . Thậy vậy, giả sử x1 không phải là phương cực biên. Vậy tồn tại 2 phương vô tận độc lập tuyến tính y1 , z1 của A sao cho x= y1 + z1 . 1 Vì y1 , z1 ∈ {u ∈  n : Au ≤ 0} = cone { x1 ,..., xk } nên ta có thể biểu diễn y1 =λ1 x1 + y2 ; z1 =λ2 x1 + z2 với y2 , z2 ∈ cone { x2 ,..., xk } . Khi ấy, ta có x1 = y1 + z1 = ( λ1 + λ2 ) x1 + ( y2 + z2 ) . Suy ra {1 − ( λ + λ )} x 1 2 1 = y2 + z 2 . Nếu 1 − ( λ1 + λ2 ) < 0 thì = − x1 1 {( λ + λ ) − 1} 1 ( y2 + z2 ) ∈ cone { x2 ,..., xk } ⊂ {u ∈  n : Au ≤ 0} . 2 Suy ra D chứa đường thẳng. Vậy ta phải có 1 − ( λ1 + λ2 ) ≥ 0 . Nếu 1 − ( λ1 + λ2 ) > 0 thì = x1 1 {1 − ( λ + λ )} 1 ( y2 + z2 ) ∈ cone { x2 ,..., xk } . 2 Điều này mâu thuẫn với giả sử ban đầu của ta là x1 không thể biểu diễn thành tổ hợp 0 . Điều này dẫn đến y2 + z2 = nón của các phần tử x2 ,..., xk . Vậy ta phải có 1 − ( λ1 + λ2 ) = 0. ra y1 λ= Mà vì D không chứa đường thẳng nên y= z= 0 . Suy = λ2 x1 . Điều này mâu 2 2 1 x1 ; z1 thuẫn với tính độc lập tuyến tính của y1 và z1 . Vậy x1 là phương cực biên. Chứng minh hoàn toàn tương tự với các xi còn lại, ta có xi là phương cực biên với mọi i ∈1, n . Vậy nón các phương vô hạn – tập hợp {u ∈  n : Au ≤ 0} là tập nón sinh bởi các phương cực biên của D. Từ các định lý 1.10, 1.11, 1.13 ta rút ra kết quả quan trọng sau Định lý 1.14: Cho D là tập lồi đa diện khác rỗng và không chứa đường thẳng. Gọi u1 ,..., uk là các điểm cực biên của D và v1 ,..., vl là các phương cực biên của D. Ta có + Nếu D bị chặn thì k   D = λ1u1 + λ2u2 + ... + λk uk : ∑ λ= 1, λi ≥ 0∀= i 1, k  . i i =1   + Nếu D không bị chặn thì l k  k  1,α i ≥ 0∀= D= ∑ α i ui + ∑ β j v j : ∑ α= i 1, k , β j ≥ 0∀= j 1, l  . i =  i 1 =j 1 =i 1  1. Bài toán quy hoạch tuyến tính 1.1 Bài toán tối ưu Cho hàm số f xác định trên tập hợp X . Bài toán tối ưu max { f ( x ) : x ∈ X } là bài toán tìm giá trị lớn nhất của hàm số f trên X. Hàm mục tiêu: Hàm số f được gọi là hàm mục tiêu của bài toán. Phương án: Nếu x ∈ X thì x được gọi là phương án của bài toán. Tập ràng buộc: X được gọi là tập ràng buộc hay tập các phương án của bài toán. Phương án tối ưu và giá trị tối ưu: Nếu tồn tại x∗ ∈ X sao cho f ( x ) ≤ f ( x∗ ) với mọi x ∈ X thì x∗ được gọi là phương án tối ưu của bài toán và giá trị f ( x∗ ) được gọi là giá trị tối ưu của bài toán. 1.2 Bài toán quy hoạch tuyến tính Cho E ={ x ∈  n : Ax ≤ b, x ≥ 0} và c ∈  n , c ≠ 0 . Bài toán quy hoạch tuyến tính dạng chuẩn tắc là bài toán có dạng max { c, x : x ∈ E} .  c, x → max .  Ax ≤ b, x ≥ 0 Bài toán thường được viết dưới dạng  Bài toán quy hoạch tuyến tính dạng chính tắc là bài toán có dạng  c, x → max .  = b, x ≥ 0  Ax Nhận xét: Vì ràng buộc Ax = b có thể thay thế bởi các ràng buộc Ax ≤ b, ( − A ) x ≤ −b nên một bài toán quy hoạch tuyến tính dạng chính tắc cũng là bài toán quy hoạch tuyến tính dạng chuẩn tắc. Định lý sau đưa ra một điều kiện cần và đủ để một bài toán quy hoạch tuyến tính dạng chuẩn tắc có phương án tối ưu. Định lý 1.16:  c, x → max có phương án tối ưu khi  Ax ≤ b, x ≥ 0 Bài toán quy hoạch tuyến tính dạng chuẩn tắc  và chỉ khi tập các phương án của bài toán khác rỗng và hàm mục tiêu bị chặn trên trên tập các phương án của bài toán. Chứng minh: ⇒ ) Hiển nhiên. ⇐) + Nếu D bị chặn thì D là tập compact nên hàm liên tục c, x đạt giá trị lớn nhất trên D . Vậy bài toán có phương án tối ưu. + Nếu D không bị chặn. Xét v là phương vô tận của D thì ta có c, v ≤ 0 . Thật vậy, giả sử ngược lại c, v > 0 . Lấy cố định x ∈ D . Ta có c, x += λv c, x + λ c, v → +∞ ( λ → +∞ ) . Điều này mâu thuẫn với giả thiết hàm mục tiêu bị chặn trên. Tập các phương án của bài toán D ={ x ∈  n : Ax ≤ b, x ≥ 0} là tập lồi đa diện khác rỗng, không chứa đường thẳng và không bị chặn. Gọi u1 ,..., uk là các điểm cực biên của D và v1 ,..., vl là các phương cực biên của D. Theo định lý 1.11, ta có với mỗi x ∈ D tồn tại các số α i , β j sao cho x= k l   k ∑ α iui + ∑ β j v j  ∑ α=i 1,α i ≥ 0∀=i 1, k , β j ≥ 0∀=j 1, l  .   =i 1 =j 1 =i 1 Suy ra k l k c, x = ∑ α i c, ui + ∑ β j c, v j ≤ ∑ α i c, ui ≤ max c, ui . =i 1 =j 1 =i 1 Vậy bài toán có phương án tối ưu. 1≤i ≤ k Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN 2.1. Khái niệm bài toán quy hoạch tuyến tính nguyên Bài toán quy hoạch tuyến tính nguyên ( toàn phần) là bài toán quy hoạch tuyến tính có thêm ràng buộc các biến phải là các số nguyên. Dạng chuẩn tắc của bài toán quy hoạch tuyến tính nguyên:  c, x → max  n  Ax ≤ b, x ≥ 0, x ∈   c, x → max được gọi là bài toán quy hoạch tuyến tính tương ứng với bài  Ax ≤ b, x ≥ 0 Bài toán  toán trên. Dạng chính tắc của bài toán quy hoạch tuyến tính nguyên:  c, x → max ( P′ )   Ax = b, x ≥ 0, x ∈  n  c, x → max được gọi là bài toán quy hoạch tuyến tính tương ứng với = b, x ≥ 0  Ax Bài toán ( P )  bài toán ( P′ ) . Chú ý: Từ đây về sau ta chỉ xét trường hợp các dữ liệu của bài toán đều là các số nguyên nghĩa là các ma trận A, b , vectơ c có các thành phần là các số nguyên. 2.2. Mối liên hệ giữa dạng chuẩn tắc và chính tắc của bài toán quy hoạch tuyến tính nguyên Vấn đề đặt ra là liệu có thể giải bài toán quy hoạch tuyến tính nguyên dạng chuẩn tắc nếu biết cách giải bài toán quy hoạch tuyến tính nguyên dạng chính tắc không. Xét bài toán quy hoạch tuyến tính nguyên dạng chuẩn tắc  c, x → max ( P′ )   Ax ≤ b, x ≥ 0, x ∈  n Ta xét bài toán phụ sau  c, x → max .  n m  Ax + y= b, x ≥ 0, y ≥ 0, x ∈  , y ∈ 