Luận văn Thạc sĩ Toán học: Phương pháp nhánh – cận cho bài toán quy hoạch nguyên

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

Thêm vào BST

Báo xấu

200
lượt xem 25
download

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

Luận văn Thạc sĩ Toán học: Phương pháp nhánh – cận cho bài toán quy hoạch nguyên bao gồm những nội dung về quy hoạch tuyến tính bài toán quy hoạch tuyến tính nguyên bộ phận, kĩ thuật được sử dụng trong thuật toán nhánh - cận và một số nội dung khác,

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp nhánh – cận cho bài toán quy hoạch nguyên

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Văn Thìa PHƯƠNG PHÁP NHÁNH – CẬN CHO BÀI TOÁN QUY HOẠCH NGUYÊN LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh – 2012
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Văn Thìa PHƯƠNG PHÁP NHÁNH – CẬN CHO BÀI TOÁN QUY HOẠCH NGUYÊN 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 Thành phố Hồ Chí Minh – 2012
LỜI CẢM ƠN Tác giả luận văn xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến thầy TS.Trịnh Công Diệu, Trưởng bộ môn Toán ứng dụng Trường Đại học Sư phạm Tp.Hồ Chí Minh đã tận tâm hướng dẫn, chỉ bảo tận tình trong suốt quá trình hoàn thành đề tài nghiên cứu. Xin chân thành cảm ơn các thầy, cô trong Ban giám hiệu trường, Phòng sau đại học, Khoa Toán – Tin Trường Đại học Sư phạm Tp.Hồ Chí Minh đã tạo điều kiện thuận lợi trong việc học tập, trang bị kiến thức để có thể hoàn thành luận văn. Bên cạnh đó, tôi xin cảm ơn các bạn bè, đồng nghiệp đã giúp đỡ tôi trong suốt quá trình nghiên cứu và hoàn thành luận văn. Cuối cùng, tôi xin cảm ơn gia đình và những người thân đã động viên giúp đỡ tôi trong quá trình nghiên cứu và hoàn thành luận văn. Tác giả luận văn Lê Văn Thìa
LỜI MỞ ĐẦU Quy hoạch nguyên (hay quy hoạch rời rạc) là một hướng quan trọng của quy hoạch toán học. Nó nghiên cứu lớp bài toán quy hoạch trong đó thêm điều kiện các biến chỉ nhận giá trị trên tập số nguyên. Lớp bài toán này rất phổ biến trong thực tế. Nó thu hút sự quan tâm của các nhà khoa học nghiên cứu trong các lĩnh vực: kinh tế, điều khiển, thiết kế, sinh học,… Chính trong các lĩnh vực đó các phương pháp liên tục tỏ ra kém hiệu quả khi nghiên cứu các đối tượng không thể chia nhỏ tùy ý, thì quy hoạch nguyên là công cụ chủ yếu nghiên cứu hiệu quả các lĩnh vực đó. Có thể nói quy hoạch nguyên bắt đầu khai sinh lịch sử của mình từ năm 1958, khi công bố thuật toán nổi tiếng của Gomory về phương pháp cắt. Sau đó một thời gian dài, phương pháp cắt là công cụ duy nhất để giải các bài toán quy hoạch nguyên. Nhưng từ khi phương pháp nhánh – cận xuất hiện trong [Land – Doig 1960] và nhất là dạng hoàn thiện của nó trong [Dakin 1965], nó trở nên ưu thế rõ rệt. Hiện nay phương pháp nhánh – cận là một trong những phương pháp chủ yếu để giải bài toán quy hoạch nguyên. Do đó, việc tìm hiểu về phương pháp nhánh – cận là cần thiết. Mục tiêu của luận văn là tìm hiểu và trình bày lại một cách chi tiết phương pháp nhánh – cận. Các vấn đề được đề cập trong luận văn được trình bày một cách chặt chẽ về mặt toán học. Nội dung luận văn gồm ba chương: Chương 1 “Một số kết quả của Quy hoạch tuyến tính và Giải tích lồi” trình bày lại một số khái niệm và tính chất của Quy hoạch tuyến tính và Giải tích lồi. Các khái niệm đối ngẫu, định lý đối ngẫu, tập lồi, tập lồi đa diện, điểm cực biên, tia cực biên của tập lồi đa diện. Đặc biệt là các tính chất về sự biễu diễn của mỗi tập
lồi đa diện hữu tỉ qua tia cực biên và điểm cực biên của nó, sẽ là cơ sở để chứng minh một số kết quả trong chương 2. Chương 2 “Thuật toán nhánh – cận giải bài toán Quy hoạch tuyến tính nguyên bộ phận” trình bày một cách chặt chẽ và chi tiết cơ sở lý luận của thuật toán và thuật toán được minh họa bởi việc giải bài toán thực tế. Chương 3 “Giải bài toán Quy hoạch nguyên tuyến tính trên Matlab” trình bày lại việc dùng phương pháp nhánh – cận giải bài toán Quy hoạch nguyên bằng ngôn ngữ Matlab. Giải một số bài toán Quy hoạch nguyên tuyến tính bằng chương trình Matlab R2009a. Do thời gian có hạn nên luận văn này mới chỉ dừng lại ở việc tìm hiểu tài liệu và sắp xếp trình bày lại các kết quả nghiên cứu theo một chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong quá trình xử lý văn bản chắc chắn không tránh khỏi những sai sót. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn.
MỤC LỤC MỤC LỤC ............................................................................................................................. 6 Chương 1 ............................................................................................................................... 1 1.1. Quy hoạch tuyến tính .................................................................................................. 1 1.2. Tập lồi - Tập lồi đa diện.............................................................................................. 9 1.3.Điểm cực biên. Tia cực biên ...................................................................................... 15 Chương 2 ............................................................................................................................. 22 2.1. Bài toán quy hoạch tuyến tính nguyên bộ phận (Mixed Integer Linear Programming). ................................................................................................................. 22 2.2. Thuật toán nhánh – cận giải bài toán quy hoạch tuyến tính nguyên bộ phận ........... 25 2.2.1. Cơ sở lý luận của thuật toán............................................................................... 25 2.2.2. Thuật toán nhánh – cận ...................................................................................... 31 2.3. Một số kĩ thuật được sử dụng trong thuật toán nhánh- cận ...................................... 31 2.3.1. Kĩ thuật Hậu tối ưu (Reoptimization)................................................................. 31 2.3.2. Quy tắc chọn bài toán phân nhánh và quy tắc phân nhánh ................................ 34 2.4. Ví Dụ......................................................................................................................... 34 Chương 3 ............................................................................................................................. 44 3.1. Bài toán Quy hoạch tuyến tính với Matlab .............................................................. 44 3.2. Lập trình thuật toán giải bài toán quy hoạch tuyến tính nguyên bộ phận trên Matlab ......................................................................................................................................... 47 3.3. Giải bài toán Quy hoạch tuyến tính nguyên bộ phận trên Matlab ............................ 50 KẾT LUẬN.......................................................................................................................... 53 TÀI LIỆU THAM KHẢO ................................................................................................... 54
1 Chương 1 Một số kết quả của Quy hoạch tuyến tính và Giải tích lồi 1.1. Quy hoạch tuyến tính Ta nhắc lại một số kết quả của quy hoạch tuyến tính mà chúng sẽ được sử dụng để chứng minh các kết quả phía sau. Định nghĩa 1.1.1. Bài toán Quy hoạch tuyến tính dạng tổng quát có dạng: n = f ( x) ∑c x j =1 j j → min thỏa hệ ràng buộc:  n ∑ aij x j (≤ =≥)bi , i = 1,..., m  j =1 x ≥ 0 , j = 1,..., n  j trong đó, c j , = = aij , bi , i 1,..., m; j 1,..., n là các hằng số cho trước. Định nghĩa 1.1.2. Tập D các điểm x = ( x1 ,..., xn ) thỏa hệ các ràng buộc gọi là tập phương án chấp nhận được của bài toán.  Điểm x* ∈ D sao cho f ( x) ≥ f ( x*) , ∀x ∈ D được gọi là phương án tối ưu của bài toán Quy hoạch tuyến tính. Định nghĩa 1.1.3. Bài toán Quy hoạch tuyến tính có thể phát biểu dưới dạng ma trận như sau: f ( x) =< c, x > → min thỏa hệ ràng buộc:  Ax (≤ =≥)b  x ≥ 0 trong đó, A là ma trận kích thước m × n .
2  Phương án x = ( x1 ,..., xn ) được gọi là phương án cơ sở nếu hệ các vectơ cột { Aj } của ma trận A ứng với các thành phần x j > 0 ( j = 1,..., n) là độc lập tuyến tính.  Phương pháp đơn hình: Xét bài toán Quy hoạch tuyến tính dạng chính tắc sau: n = f ( x) ∑c x j =1 j j → min thỏa hệ ràng buộc:  n ∑ = aij x j = bi , i 1,..., m  j =1 x ≥ 0 ,j= 1,..., n  j Giả sử đã biết một phương án cơ sở chấp nhận được náo đó: = X 0 (= xb1 a1 , x= b2 a2 ,..., x= bm am ), được xác định từ hệ vectơ cơ sở đơn vị m chiều Ab1 , Ab 2 ,..., Abm . - Khai triển mọi vectơ điều kiện Aj ( j = 1,..., n) theo hệ vec tơ cơ sở Ab1 , Ab 2 ,..., Abm có nghĩa là tính các hệ số x1 j , x2 j ,..., xmj , j = 1,..., n . - Tính các hiệu Z j − c j , j = 1,..., n, m trong đó = Z j C= b Aj ∑c i =1 x = , j 1,..., n . bi ij Để tiện tính toán người ta trình bày theo bảng sau:
3 Cơ Cb A0 c1 … cb1 … cb 2 … cbl … ck … cj … cbm … cn sở A1 … Ab1 … Ab 2 … Abl … Ak … Aj … Abm … An Ab1 cb1 xb1 x11 … 1 … 0 … 0 … x1k … x1 j … 0 … x1n Ab 2 cb 2 xb 2 x21 … 0 .. 1 … 0 … x2k … x2 j … 0 … x2n … … … … … … … … … … … … … … … … … … Abl cbl xbl xb1 … 0 … 0 … 1 … xlk … xlj … 0 … xln … … … … … … … … … … … … … … … … … … Abm cbm xbm xbm … 0 … 0 … 0 … xmk … xmj … 1 … xmn Z j − cj Z0 … … … … … … … - Nếu Z j − c j ≤ 0 , ∀j ∈ {1, 2,..., n} thì phương án cơ sở chấp nhận được là phương án tối ưu. - Nếu có một chỉ số j nào đó mà Z j − c j > 0 và hệ số xij ≤ 0 (∀i =1,..., m) thì dạng tuyến tính Z không bị chặn trên tập phương án chấp nhận được. - Nếu có một chỉ số j nào đó mà Z j − c j > 0 , và Aj có ít nhất một hệ số xij > 0 thì phương án cơ sở chấp nhận được chưa tối ưu và có thể cải thiện được bằng cách đưa vào cơ sở vectơ có ( Z j − c j ) max > 0 . Giả sử ( Z j − c j ) max = Z k − ck > 0 , khi đó đưa vectơ Ak vào cơ sở và loại ra khỏi cơ sở vectơ ứng với: xbi t = min xik > 0 xik
4 xbi xbl Giả= sử t min = , do đó Abl bị loại ra khỏi cơ sở. Cơ sở mới gồm m xik > 0 x xlk ik vectơ: ( Ab1 ,..., Abl −1 , AK , Abl +1 ,..., Abm ) . Phần tử xlk được gọi là phần tử giải được. Bằng phép biến đổi cơ bản và đơn giản biểu thức:  ′ xbl  xbi =xbi − x xik , (bi ≠ bl , l =1,..., m)  lk   x′ = xbl  k xlk  x  xij′ = xij − lj xik , bi ≠ bl  xlk   x′ = xlj  lj xlk Ta biến đổi vectơ Ak về vectơ đơn vị với xlk = 1. Khi hoàn thành phép biến đổi ta được bảng đơn hình mới và được tính theo cơ sở mới. Quá trình tính toán tương tự được tiếp tục cho đến khi tìm được phương án tối ưu. Định nghĩa 1.1.4. Giả sử ma trận A có vectơ hàng là ai và các vectơ cột là Aj . Giả sử bài toán gốc có cấu trúc ở bên trái trong bảng sau đây. Khi đó, bài toán đối ngẫu được định nghĩa với cấu trúc tương ứng bên phải Z = < c, x > → min , f = < b, y > → max Với ràng buộc Với ràng buộc < ai , x=> bi , i ∈ M 1 yi tự do, i ∈ M 1 < ai , x > ≤ bi , i ∈ M 2 yi ≤ 0, i ∈ M 2 < ai , x > ≥ bi , i ∈ M 2 yi ≥ 0, i ∈ M 3 x j ≥ 0, j ∈ N1 < y, Aj >≤ c j , j ∈ N1 x j ≤ 0, j ∈ N 2 < y, Aj > ≥ c j , j ∈ N 2 x j tự do j ∈ N 3 < y, A= j > c j , j ∈ N3 Định nghĩa 1.1.5.
5  Cặp bài toán đối ngẫu không đối xứng là cặp bài toán đối ngẫu mà trong đó những ràng buộc trong bài toán gốc được cho bằng đẳng thức và những ràng buộc của bài toán đối ngẫu được cho bằng bất đẳng thức.  Cặp bài toán đối ngẫu đối xứng là cặp bài toán đối ngẫu mà trong đó các biến của hai bài toán đều không âm và các ràng buộc đều là bất đẳng thức. Định lý 1.1.6.(Định lý đối ngẫu yếu) Cho A là ma trận cỡ m × n , b ∈  m và c ∈ n . P = {x ∈  n : Ax ≤ b} và Q = c, y ≤ 0} . Khi đó { y ∈  m : AT y = (i) Nếu x ∈ P và y ∈ Q thì < c, x > ≥ < b, y > . (ii) Nếu bài toán min{< c, x >: x ∈ P} không bị chặn dưới, thì Q = ∅ . (iii) Nếu bài toán max{< b, y >: y ∈ Q} không bị chặn trên thì P = ∅ . Chứng minh Giả sử ma trận A có vectơ hàng là ai (i = 1,..., m) và các vectơ cột là Aj ( j = 1,..., n) . (i) Ta đặt u= i yi (< ai , x > −bi ), v= j (c j − < y , A j >) x j . Theo định nghĩa của bài toán đối ngẫu thì yi và < ai , x > −bi cùng dấu, còn c j − < y, Aj > và x j cùng dấu. Do đó, ui ≥ 0, ∀i và v j ≥ 0, ∀j . Nhận xét rằng ∑u i i = < y, Ax − b >, ∑v j j = < c − yA, x > . Do đó, 0 ≤ ∑ ui + ∑ v j =< c, x > − < b, y > . i j (ii) Nếu bài toán min{< c, x >: x ∈ P} không bị chặn dưới thì tồn tại dãy {x k } các phương án chấp nhận được sao cho < c, x k >→ −∞ khi k → ∞ . Giả sử
6 ∃y 0 ∈ Q . Khi đó, theo (i) ta có < c, x k > ≥ < b, y 0 > , ∀k . Cho k → ∞ ta được < b, y 0 > ≤ −∞ (vô lí). Do đó, Q = ∅ . (iii) Nếu bài toán max{< b, y >: y ∈ Q} không bị chặn trên thì thì tồn tại dãy { y k } các phương án chấp nhận được sao cho < b, y k >→ +∞ khi k → ∞ . Giả sử ∃x 0 ∈ P . Khi đó, theo (i) ta có < c, x 0 > ≥ < b, y k > , ∀k . Cho k → ∞ ta được < c, x 0 > ≥ +∞ (vô lí). Do đó, P = ∅ . ⁯ Định lý 1.1.7.(Định lý đối ngẫu mạnh) Nếu bài toán quy hoạch tuyến tính gốc có nghiệm tối ưu thì bài toán quy hoạch đối ngẫu cũng có nghiệm tối ưu và giá trị mục tiêu tối ưu bằng nhau. Chứng minh Ta có thể đưa cặp bài toán đối ngẫu đối xứng về cặp bài toán đối ngẫu không đối xứng, do đó chỉ chứng minh cho cặp bài toán đối ngẫu không đối xứng. Giả sử bài toán đối ngẫu không đối xứng có phương án tối ưu nhận được bằng phương pháp đơn hình (xem trong tài liệu tham khảo [Cảnh 2004], [Khánh – Nương 2000], [Khánh 2002]). Hệ vectơ cơ sở tương ứng với phương án tối ưu gồm các vectơ Ab1 , Ab 2 ,..., Abm . Đặt Ab = ( Ab1 ,..., Abm ) ma trận được thành lập từ hệ các vectơ cơ sở. Khi đó, Aj = Ab X j . Biểu diễn D = ( X 1 ,..., X n ) ma trận được thành lập từ những hệ số của bảng đơn hình cuối cùng. Ta có: =A A= b D; D Ab−1 A (1.1) = Ab X opt A= 0; X opt Ab−1 A0 (1.2) = Z min C= b X opt Cb Ab−1 A0 , (1.3) trong đó X opt là phương án tối ưu của bài toán thuận. Xét vectơ Cb D − C = ( Z1 − c1 ,..., Z n − cn ) có các tọa độ là những hiệu Z j − c j . Vì là phương án tối ưu nên mọi hiệu Z j − c j ≤ 0,( j − 1,..., n) , do đó: Cb D − C ≤ 0 . (1.4)
7 Người ta chứng minh được rằng, phương án tối ưu của bài toán đối ngẫu nhận được theo công thức: Yopt = Cb Ab−1 . (1.5) Thật vậy, Xét vectơ Yopt A − C . Khi sử dụng liên tiếp các công thức (1.5), (1.1), (1.4) ta được Yopt A − C= Cb Ab−1 A − C= Cb D − C ≤ 0. Do đó, Yopt A ≤ C có nghĩa là Yopt là phương án chấp nhận được của bài toán đối ngẫu. Bây giờ tính giá trị của dạng tuyến tính f khi Y = Yopt . −1 f (= Yopt ) Y= opt A0 Cb A= b A0 Cb= X opt min Z (1.6) ở đây các công thức (1.5), (1.2), (1.3) được dùng liên tiếp. Biểu thức (1.6) chứng tỏ rằng: giá trị dạng tuyến tính của bài toán đối ngẫu (khi Y = Yopt ), f (Yopt ) trùng với giá trị tối ưu của bài toán gốc. Bây giờ cần chứng minh rằng: Yopt là phương án tối ưu của bài toán đối ngẫu. Ta có: f (= = Y ) YA0 YAX . Một phương án chấp nhận được bất kỳ Y của bài toán đối ngẫu phải thỏa mãn YA ≤ C , do đó: f (Y ) ≤ CX = Z ( X ). Suy ra max f (Y ) ≤ min Z ( X ). (1.7) Theo (1.6) với Y = Yopt thì bất đẳng thức (1.7) trở thành đẳng thức . Vì vậy Yopt là phương án tối ưu của bài toán đối ngẫu. ⁯ Định lý 1.1.8.(Điều kiện độ lệch bù) Cho x là nghiệm chấp nhận được của bài toán min{< c, x >: Ax ≤ b} và y là nghiệm chấp nhận được của bài toán
8 max{< b, y >: AT y = c, y ≤ 0} . Giả sử ma trận A có vectơ hàng là ai (i = 1,..., m) và các vectơ cột là Aj ( j = 1,..., n) . Khi đó, x, y là nghiệm tối ưu nếu và chỉ nếu yi (< ai , x > −bi )= 0 ∀i, (c j − < Aj , y >) x j = 0 ∀j. Chứng minh Ở chứng minh định lý 1.1.6 ta đã đặt u= i yi (< ai , x > −bi ), v= j (c j − < y , A j > ) x j Theo định nghĩa của bài toán đối ngẫu ta thấy rằng ui ≥ 0, v j ≥ 0 ∀i, ∀j . Đồng thời ta cũng có < c , x > − < b, = y> ∑u + ∑v . i i j j Theo định lý đối ngẫu mạnh , nếu x và y là phương án tối ưu thì < c, x > = < b, y > . Do đó, ui = v j = 0, ∀i, ∀j . Ngược lại, nếu ui = v j = 0, ∀i, ∀j thì < c, x > = < b, y > suy ra x, y là phương án tối ưu. ⁯ Định lý 1.1.9. (Bổ đề Farkas) Tập hợp {x : Ax = b, x ≥ 0} là tập khác rỗng khi và chỉ khi không tồn tại vectơ y sao cho AT y ≥ 0 và < b, y > < 0 . Chứng minh Theo Quy hoạch tuyến tính đối ngẫu ta có min{< c, x >: Ax = b, x ≥ 0} ≤ 0 khi và chỉ khi max{< b, y >: AT y ≤ c} ≤ 0. Chọn c = 0 , khi đó {x : Ax = b, x ≥ 0} ≠ ∅ khi và chỉ khi không tồn tại y sao cho AT y ≥ 0 và < b, y > < 0 . ⁯  Thuật toán đơn hình đối ngẫu: Thuật toán đơn hình đối ngẫu bắt đầu từ một phương án sơ sở chấp nhận được của bài toán đối ngẫu nhưng không chấp nhận được của bài toán gốc (vì có biến cơ sở âm). Bằng thuật toán đơn hình chuyển dần đến phương án tối ưu. Thuật toán đơn hình đối ngẫu có thể chia thành hai giai đoạn sau:
9 - Giai đoạn 1: Không quan tâm đến sự không âm của các biến cơ sở mà thuật toán đơn hình đưa bài toán đến một bảng đơn hình có ∀( Z j − c j ) ≤ 0 . + Nếu ∀xbi ≥ 0 thì ta có phương án ấy là phương án tối ưu và ngừng tính. + Thông thường thì phương án ấy không phải là phương án tối ưu, vì trong các biến cơ sở vẫn còn có biến âm, chuyển sang giai đoạn 2. - Giai đoạn 2: Khi các biến cơ sở còn biến âm ta cần khử các biến âm mà vẫn giữ được ∀( Z j − c j ) ≤ 0 . Phương án là tối ưu khi mọi biến cơ sở đều không âm. Giả sử xbl < 0 , khi đó ta loại vectơ Al khỏi cơ sở. Nếu trong hàng l không có thành phần xlj < 0 thì bài toán không có phương án chấp nhận được. Nếu có một vài xlj < 0 thì phương án có thể cải thiện được và đưa vectơ Ak vào cơ sở với k được xác định bởi: Z j − cj Z k − ck min = . xlj < 0 xlj xlk Việc chọn như vậy các hiệu Z j − c j vẫn không dương. Quá trình tính toán tương tự được tiếp tục đến khi nhận được phương án tối ưu. Trong trường hợp, nếu có vài biến cơ sở xbl < 0 thì việc chọn phần tử giải được chọn theo công thức: Z j − cj min . xij < 0 xij Phương pháp đơn hình đối ngẫu giảm nhẹ sự biến đổi các ràng buộc và do đó giảm kích thước bảng đơn hình, khối lượng tính toán được giảm một cách đáng kể. 1.2. Tập lồi - Tập lồi đa diện. Định nghĩa 1.2.1.  Cho tập X ⊂  n , tập X được gọi là tập lồi nếu với mọi x1 , x 2 ∈ X ta đều có λ x1 + (1 − λ ) x 2 ∈ X , ∀λ ∈ (0,1) .
10 m m  Tổ hợp tuyến tính x = ∑ λi x với = m , ∑ λi 1 được gọi là λi ≥ 0 ∀i 1,..,= i i =1 i =1 tổ hợp lồi của các vectơ x1 ,..., x m .  Cho tập X ⊂  n , bao lồi của X , được kí hiệu là conv( X ) là tập hợp tất cả tổ hợp lồi của các vectơ trong X . Tức là k k conv( X ) := ∑ λi vi : λi ≥ 0,∑ λi = {x = =i 1 =i 1 1, v1 ,..., vk ∈ X }. k Nếu = x ∑ λ v ∈ conv( X ) là tổ hợp lồi của các vectơ v ,..., v i =1 i i i k ∈ X thì k k < c, x > =< c, ∑ λi vi > = ∑ λi < c, vi > ≥ min{< c, vi >: i = 1,..., k}. =i 1 =i 1 Do đó, với bất kỳ tập X ⊂  n , c ∈  n ta luôn có min{< c, x >: x ∈ X }= min{< c, x >: x ∈ conv( X )}. (1.8) Định nghĩa 1.2.2. Một tập lồi đa diện là tập hợp con của  n được xác định bởi hữu hạn bất phương trình tuyến tính, tức là một tập lồi đa diện có dạng P ( A, b) := {x ∈  n : Ax ≤ b} , (1.9) trong đó A là ma trận cỡ m × n và b ∈  m .Tập lồi đa diện P được gọi là tập lồi đa diện hữu tỉ nếu = A (aij ), aij ∈ = , i 1,..., m,=j 1,..., n ; b ∈ m . Định nghĩa 1.2.3. Cho tập lồi đa diện P ⊂  n . Tập hợp F ⊂ P được gọi là diện của P nếu F= {x ∈ P :< w, x = > t} và P ⊆ {x ∈  n :< w, x > ≤ t} trong đó w ∈  n , t ∈  . Nếu F ≠ ∅ và F ≠ P thì F được gọi là diện không tầm thường. Ta thấy rằng mỗi diện F của đa diện P = P ( A, b) có dạng F= {x ∈  n : Ax ≤ b, < w, x >≤ t , − < w, x >≤ −t} , với một t ∈  nào đó. Do đó F cũng là tập lồi đa diện. Định nghĩa 1.2.4. Cho tập lồi đa diện = P P ( A, b) ⊆  n và M là tập chỉ số các dòng của A . Cho I ⊆ M ta xét tập hợp fa ( I ) := {x ∈ P : AI x = bI }, (1.10)
11 trong đó AI là ma trận được thành lập từ các dòng thứ i ∈ I của ma trận A . Khi đó fa ( I ) là diện của P và được gọi là diện cảm sinh bởi I . Định lý 1.2.5. Cho tập lồi đa diện khác rỗng = P P ( A, b) ⊆  n và M là tập chỉ số dòng của A . Tập F ⊆  n với F ≠ ∅ là diện của P nếu và chỉ nếu F= fa ( I ) = bI } với I ⊆ M . {x ∈ P : AI x = Chứng minh Ta có fa ( I ) là một diện của P với bất kỳ I ⊆ M . Ngược lại, nếu F= P ∩ {x ∈  n :< c, x >= t} là diện của P thì F là tập nghiệm tối ưu của bài toán quy hoạch tuyến tính max{< c, x >: Ax ≤ b} (1.11) . Theo định lý đối ngẫu mạnh, ta có bài toán quy hoạch đối ngẫu của (1.11) min{< b, y >: AT y = c, y ≥ 0} cũng có nghiệm tối ưu y * và thỏa < b, y* >= t . Đặt =I : {i : yi * > 0} . Theo điều kiện độ lệch bù, những nghiệm tối ưu x * của bài toán (1.11) thỏa Ai x*= bi , ∀i ∈ I . Vậy F = fa ( I ) . ⁯ Định nghĩa 1.2.6. (tập tương đương) Cho tập lồi đa diện = P P ( A, b) ⊆  n , S ⊆ P . Khi đó ta gọi eq ( S ) := {i ∈ M : Ai x = bi , ∀x ∈ S } là tập tương đương của S . Nhận xét: Cho S , S ' là hai tập con của tập lồi đa diện P . Nếu S ⊆ S ' thì eq ( S ) ⊇ eq ( S ') . Như vậy, với S là tập con khác rỗng của tập lồi đa diện P , nếu F là diện của P chứa S thì eq ( F ) ⊆ eq ( S ) . Thêm nữa là fa (eq ( S )) sẽ là diện của P và chứa S . Do đó, ta có mệnh đề sau: Mệnh đề 1.2.7. Cho tập lồi đa diện = P P ( A, b) ⊆  n và S là tập con khác rỗng của P . Diện nhỏ nhất chứa S của P là fa (eq ( S )) . Hệ quả 1.2.8. (i) Tập lồi đa diện P = P ( A, b) không có bất kỳ diện không tầm thường nào khi và chỉ khi eq ( P ) = M , trong đó M là tập chỉ số các dòng của A .
12 (ii) Nếu Ax < b thì x không chứa trong bất kỳ diện không tầm thường nào của P . Định nghĩa 1.2.9. k Tổ hợp affine của các vectơ v1 ,..., vk ∈  n là tổ hợp tuyến tính x = ∑ λi vi sao i =1 k cho ∑λ i =1 i = 1. Cho tập X ⊆  n , bao affine của X được định nghĩa là k k aff ( X = ) : {= x ∑ λ v : ∑ λ= i i =i 1 =i 1 i 1, v1 ,..., vk ∈ X } . k Hệ vectơ v1 ,..., vk ∈  n được gọi là độc lập affine nếu ∑λ v i =1 i i = 0 và k ∑λ i =1 i = 0 thì ta suy ra λ1= λ2= ...= λk= 0 . Bổ đề 1.2.10. Các mệnh đề sau tương đương (i) Hệ vectơ v1 ,..., vk ∈  n là độc lập affine. (ii) Hệ vectơ v2 − v1 ,..., vk − v1 ∈  n là độc lập tuyến tính. v  v  (iii) Hệ vectơ  1  ,...,  k  ∈  n +1 là độc lập tuyến tính. 1  1  Định nghĩa 1.2.11. Vectơ x ∈ P =P ( A, b) được gọi là điểm trong tương đối của tập lồi đa diện nếu nó không thuộc bất kỳ diện không tầm thường nào của đa diện P . Bổ đề 1.2.12. Cho F là một diện của tập lồi đa diện P ( A, b) và x ∈ F . Khi đó x là điểm trong tương đối của F khi và chỉ khi eq ({x }) = eq ( F ) . Chứng minh Gọi G là diện nhỏ nhất của F chứa x . Khi đó, x là điểm trong tương đối của F khi và chỉ khi F = G . Theo mệnh đề 1.2.7 ta có G = fa (eq ({x })) . Vậy x là điểm trong tương đối của F khi và chỉ khi fa (eq ({x })) = F . Suy ra x là điểm trong tương đối của F khi và chỉ khi eq ({x }) = eq ( F ) . ⁯
13 Do đó, ta có định nghĩa tương đương với định nghĩa 1.2.11 là : x ∈P =P ( A, b) là điểm trong tương đối của P nếu eq ({x }) = eq ( P ) . Bổ đề 1.2.13. Cho P = P ( A, b) là tập lồi đa diện khác rỗng. Khi đó, tập hợp các điểm trong tương đối của P cũng khác rỗng. Chứng minh Đặt M = {1,..., m} là tập chỉ số các dòng của A . I := eq ( P ) và J := M \ I . Khi đó, nếu J = ∅ thì I = M . Theo hệ quả 1.2.8 (i) ta có tập lồi đa diện P không có bất kỳ diện không tầm thường nào. Do đó, bất kỳ điểm nào của P cũng là điểm trong tương đối. Nếu J ≠ ∅ thì với mỗi j ∈ J ta tìm được x j ∈ P sao cho Ax j ≤ b và Aj x j < b j . 1 Do P là tập lồi nên y := ∑ x j (trong đó | J | là số phần tử của J ) cũng thuộc | J | j∈J P . Do đó, AJ y < bJ và AI y = bI suy ra eq ({ y}) = eq ( P ) . Ta được đpcm. ⁯ Định nghĩa 1.2.14. Số chiều của tập lồi đa diện P ⊆  n (kí hiệu là dim P ) là số bé hơn một đơn vị so với số lớn nhất các vectơ độc lập affine trong P . Ta có dim ∅ = −1 . Định lý 1.2.15. (Định lý về số chiều) Cho F ≠ ∅ là một diện của tập lồi đa diện P ( A, b) ⊆  n . Khi đó, ta có dim F= n − rankAeq ( F ) . Chứng minh Theo kết quả của Đại số tuyến tính, ta có =n rankAeq ( F ) + dim ker Aeq ( F ) , trong đó ker Aeq ( F ) là không gian nghiệm của hệ phương trình thuần nhất có ma trận hệ số là Aeq ( F ) . Do đó, ta chỉ cần chứng minh dim ker Aeq ( F ) = dim F . Để cho gọn ta đặt = = I : eq = ( F ); r : dim ker AI ; s : dim F .
14 “ r ≥ s ”: Chọn s + 1 vectơ độc lập affine x 0 , x1 ,..., x s ∈ F . Suy ra theo bổ đề 1.2.10 hệ vectơ x1 − x 0 ,..., x s − x 0 là độc lập tuyến tính và AI ( x j − x 0 ) = bI − bI = 0 , j = 1,..., s . Suy ra r ≥ s . “ r ≤ s ”: Vì F ≠ ∅ nên s ≥ 0 . Do đó ta cũng giả thiết r ≥ 0 . Do F ≠ ∅ Theo bổ đề 1.2.13 tồn tại một điểm trong tương đối x ∈ F mà theo bổ đề 1.2.12 ta = có eq ({ = x }) eq ( F ) I . Vậy với J := M \ I ta có AI x = bI và AJ x < bJ . Đặt {x1 ,..., x r } là cơ sở của ker AI . Khi đó, do AJ x < bJ ta có thể tìm được ε > 0 sao cho AJ ( x + ε x k ) < bJ và AI ( x + ε x k ) = bI với k = 1,..., r . Suy ra x + ε x k ∈ F với k = 1,..., r . Các vectơ ε x1 ,..., ε x r là độc lập tuyến tính , theo bổ đề 1.2.10 x , ε x1 + x ,..., ε x r + x là những vectơ độc lập affine trong F . Suy ra r ≤ s . ⁯ Định lý 1.2.16. (Hoffman - Kruskal) Cho = P P ( A, b) ⊆  n là tập lồi đa diện. Khi đó, tập khác rỗng F ⊆ P là diện nhỏ nhất của P khi và chỉ = khi F {= x : AI x bI } với I ⊆ M ( M là tập chỉ số các dòng của A ) và rank AI = rank A . Chứng minh “⇒”: Gọi F diện khác rỗng nhỏ nhất của P . Khi đó, theo định lý 1.2.5 và mệnh đề 1.2.7 ta có F = fa ( I ) , trong đó I = eq ( F ) . Đặt J := M \ I , ta có =F {x= : AI x bI , AJ x ≤ bJ } (1.12) . Ta cần chứng minh F = G , trong đó =G {= x : AI x bI } (1.13) . Theo (1.12) ta có F ⊆ G . Giả sử tồn tại y ∈ G \ F . Khi đó, tồn tại j ∈ J sao cho = AI y bI , Aj y > b j (1.14) . Do F ≠ ∅ nên theo bổ đề 1.2.13 tồn tại điểm trong tương đối của F , ta gọi điểm đó là x . Ta xét điểm z (τ ) =x +τ ( y − x) =(1 − τ ) x + τ y .