Tài liệu Một thuật toán tìm nghiệm tối ưu của bài toán quy hoạch song tuyến tính

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ————————————————— NGUYỄN THỊ HẢI NHƯ MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HOC ————————————————— NGUYỄN THỊ HẢI NHƯ MỘT THUẬT TOÁN TÌM NGHIỆM TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học GS. TS. TRẦN VŨ THIỆU Thái Nguyên - Năm 2017 i Lời cảm ơn Tôi xin bày tỏ lòng biết ơn tới GS.TS Trần Vũ Thiệu, người đã định hướng chọn đề tài và tận tình hướng dẫn, cho tôi những nhận xét quý báu để tôi có thể hoàn thành luận văn. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới phòng Sau Đại học, các thầy cô giáo dạy cao học chuyên ngành Toán ứng dụng trường Đại học Khoa Học Đại học Thái Nguyên đã giúp đỡ và tạo điều kiện cho tôi trong suốt quá trình học tập và nghiên cứu khoa học. Nhân dịp này tôi cũng xin gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình học tập. Thái Nguyên, tháng 6 năm 2017 Người viết luận văn Nguyễn Thị Hải Như ii Mục lục Lời cảm ơn i Mục lục i Một số ký hiệu viết tắt 1 Mở đầu 1 1 Bài toán quy hoạch song tuyến tính 5 1.1 Đối ngẫu trong quy hoạch tuyến tính . . . . . . . . . . . . . . 5 1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính . . . . . . . . 8 1.2.1 Hàm lõm và tính chất . . . . . . . . . . . . . . . . . . . 8 1.2.2 Bài toán quy hoạch lõm Bài toán quy hoạch song tuyến tính . . . . . . . . . . . . . . . 11 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Quan hệ với bài toán quy hoạch lõm . . . . . . . . . . . 13 1.3.3 1.4 10 1.3.1 1.3 . . . . . . . . . . . . . . . . . Tính chất nghiệm của bài toán song tuyến tính . . . . . 15 Tìm nghiệm cực tiểu địa phương . . . . . . . . . . . . . . . . . 16 iii 2 Thuật toán giải quy hoạch song tuyến tính 2.1 19 Cơ sở lý thuyết của thuật toán . . . . . . . . . . . . . . . . . . 19 2.1.1 Biến đổi bài toán quy hoạch song tuyến tính . . . . . . 19 2.1.2 Điều kiện tối ưu của thuật toán . . . . . . . . . . . . . 23 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 Các bước của thuật toán . . . . . . . . . . . . . . . . . 25 2.2.2 Suy biến . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.3 Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Cách tiếp cận siêu phẳng cắt . . . . . . . . . . . . . . . . . . . 34 2.4 Ví dụ minh họa thuật toán . . . . . . . . . . . . . . . . . . . . 36 2.2 Tài liệu tham khảo 46 1 Một số ký hiệu viết tắt R Tập số thực hay đường thẳng thực. Rn Không gian Euclid n chiều. Rm×n Tập các ma trận thực cấp (m × n). x∈C x thuộc tâp C (x là một phần tử của tập C). ∅ Tập rỗng (Tập không chứa phần tử nào). C ∪D Hợp của tập C và tập D. C ∩D Giao của tập C và tập D. C⊂D C là tập con của tập D. C⊆D C là tập con (có thể bằng) của tập D. xT y Tích vô hướng cuả x và y. x0 , x1 , x2 , ......, xn Các tọa độ của điểm hay thành phần của véctơ x ( cùng chỉ số dưới ). x1 , x2 , x3 Liệt kê các véctơ có cùng số chiều (cùng chỉ số trên). AT Ma trận chuyển vị của ma trận A. A−1 Ma trận nghịch đảo của ma trận A. 2 Mở đầu Hàm f (x, y) được gọi là một hàm song tuyến tính (bilinear function) nếu nó là hàm tuyến tính khi cố định véctơ biến x hay véctơ biến y ở một giá trị cụ thể. Tổng quát, hàm song tuyến tính có dạng: f (x, y) = aT x + xT Qy + bT y, trong đó a, x ∈ Rn , b, y ∈ Rm và Q là ma trận cấp n × m. Có thể thấy hàm song tuyến tính là một trường hợp riêng của hàm toàn phương và hàm song tuyến tính nói chung không lồi, cũng như không lõm. Bài toán cực tiểu một hàm song tuyến tính với các ràng buộc tuyến tính đối với các biến x và biến y được gọi là một quy hoạch song tuyến tính (bilinear programming problem). Như vậy, có thể xem quy hoạch song tuyến tính là một bài toán quy hoạch toàn phương đặc biệt. Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong các bài toán trò chơi ma trận có ràng buộc, bài toán bù tuyến tính và bài toán phân việc 3-chiều. Đáng chú ý là bài toán quy hoạch lõm, tuyến tính từng khúc và các bài toán luồng trên mạng với phụ phí cố định (rất quen thuộc trong quản lý các chuỗi cung ứng) cũng có thể giải nhờ dùng cách diễn đạt song tuyến tính (xem [4]). 3 Luận văn xét bài toán quy hoạch song tuyến tính, ký hiệu là (BP): min x∈X, y∈Y f (x, y) = aT x + xT Qy + bT y, (BP ) trong đó X, Y là các tập lồi đa diện, khác rỗng. Có nhiều thuật toán khác nhau để giải (BP). Luận văn tìm hiểu và trình bày một thuật toán cơ bản, nêu ở tài liệu [3] để giải bài toán. Để hiểu rõ bài toán quy hoạch song tuyến tính và thuật toán sẽ trình bày, luận văn nhắc lại một số kiến thức tối ưu có liên quan: đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm và tính chất, bài toán tối ưu toàn cục, ... Các kiến thức cơ bản về quy hoạch song tuyến sẽ được nêu ở chương 1 của luận văn. Nội dung chính của luận văn là thuật toán [3] giải quy hoạch song tuyến tính: các bước thuật toán, sự hội tụ của thuật toán và ví dụ minh họa thuật toán. Các nội dung này sẽ được trình bày chi tiết ở chương 2 của luận văn. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [6] hiện có và gồm hai chương: Chương 1: Bài toán quy hoạch song tuyến tính nhắc lại các kiến thức về đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm với ràng buộc tuyến tính, khái niệm hàm lõm (hàm tựa lõm) và tính chất cơ bản của hàm lõm. Tiếp đó, giới thiệu bài toán quy hoạch song tuyến tính, tính chất nghiệm của bài toán và mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. Cuối chương giới thiệu "thuật toán xuống núi" tìm nghiệm cực tiểu địa phương của bài toán quy hoạch song tuyến tính và đưa ra ví dụ minh họa thuật 4 toán. Chương 2: Thuật toán giải bài toán quy hoạch song tuyến tính trình bày thuật toán được nêu ở tài liệu tham khảo [3] để giải bài toán quy hoạch song tuyến tính. Thuật toán này biến đổi bài toán ban đầu về bài toán tối ưu trên một tập không lồi và giải bài toán đó, dựa trên điều kiện tối ưu cần và đủ đưa ra và chứng minh sự hội tụ về nghiệm đúng của bài toán quy hoạch song tuyến tính ban đầu. Thuật toán trình bày được minh họa bằng ví dụ số cụ thể. 5 Chương 1 Bài toán quy hoạch song tuyến tính Chương này nhắc lại các kết quả về đối ngẫu trong quy hoạch tuyến tính, bài toán quy hoạch lõm ràng buộc tuyến tính. Tiếp đó đề cập tới bài toán quy hoạch song tuyến tính, tính chất nghiệm bài toán và mối liên hệ với bài toán cực tiểu hàm lõm, tuyến tính từng khúc. Cuối chương nêu thuật toán tìm cực tiểu địa phương của bài toán. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [5] - [6]. 1.1 Đối ngẫu trong quy hoạch tuyến tính A. Trong quy hoạch tuyến tính người ta hay xét hai dạng bài toán sau đây. • Dạng chuẩn tắc: min f (x) = cT x : Ax Trong đó A ∈ Rm×n , b ∈ Rn , x ràng buộc D = {x ∈ Rn : Ax b, x 0 , n 0 có nghĩa x ∈ R+ . Trong bài toán này tập b, x 0} là một tập lồi đa diện. 6 • Dạng chính tắc: min f (x) = cT x : Ax = b, x 0 , trong đó A, b, c và x được xác định như ở trên. Trong bài toán này tập ràng buộc D = {x ∈ Rn : Ax = b, x 0} cũng là một tập lồi đa diện. Có thể dễ dàng chuyển từ dạng chuẩn tắc sang dạng chính tắc và ngược lại. Trong các bài toán trên f(x) được gọi là hàm mục tiêu. Mỗi bất phương trình (Ax)i bi hay phương trình (Ax)i = bi gọi là một ràng buộc chính, xj ≥ 0, j = 1, ..., n, gọi là các ràng buộc không âm hay ràng buộc về dấu. Véctơ (điểm) x ∈ D gọi là một nghiệm chấp nhận được hay một phương án. Một phương án đạt cực tiểu của hàm mục tiêu f(x) gọi là một phương án tối ưu hay một nghiệm tối ưu của bài toán. Mỗi bài toán quy hoạch tuyến tính đã cho, gọi là bài toán gốc, luôn đi kèm với một bài toán quy hoạch tuyến tính thứ hai, gọi là bài toán đối ngẫu. Hai bài toán này quan hệ mật thiết với nhau và từ nghiệm tối ưu của bài toán này có thể suy ra nghiệm tối ưu bài toán kia và ngược lại. B. Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp. • Đối ngẫu của qui hoạch tuyến tính dạng chuẩn tắc (bài toán gốc) (P) min f (x) = cT x : Ax b, x 0 là bài toán qui hoạch tuyến tính (bài toán đối ngẫu): (Q) max g (y) = bT y : AT y c, y 0 ( AT là ma trận chuyển vị của ma trận A ). • Đối ngẫu của qui hoạch tuyến tính dạng chính tắc (bài toán gốc): 7 (P) min f (x) = cT x : Ax = b, x 0 là bài toán qui hoạch tuyến tính (bài toán đối ngẫu): (Q) max g (y) = bT y : AT y c . Dễ kiểm tra lại rằng lấy đối ngẫu của bài toán đối ngẫu ta được lại bài toán gốc. Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu nhau. C. Các kết quả sau đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ. Định lý 1.1.1. (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì f (x) = c1 x1 + c2 x2 + ... + cn xn g (y) = b1 y1 + b2 y2 + ... + bm ym , nghĩa là giá trị mục tiêu của một phương án gốc bất kỳ (bài toán min) không nhỏ hơn giá trị mục tiêu của một phương án đối ngẫu bất kỳ (bài toán max). Định lý 1.1.2. (Đối ngẫu mạnh). Nếu một qui hoạch có nghiệm tối ưu thì qui hoạch đối ngẫu của nó cũng có nghiệm tối ưu và hai giá trị tối ưu bằng nhau. Các định lý trên suy ra các quan hệ sau giữa hai bài toán gốc và đối ngẫu Định lý 1.1.3. (Định lý đối ngẫu cơ bản). Đối với một cặp bài toán qui hoạch tuyến tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây: (a) Cả hai bài toán đều không có nghiệm chấp nhận được. (b) Cả hai bài toán đều có nghiệm chấp nhận được. Khi đó, cả hai đều có nghiệm tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau. (c) Một bài toán có nghiệm chấp nhận được và bài toán kia không có nghiệm 8 chấp nhận được. Khi đó, bài toán có nghiệm chấp nhận được sẽ có giá trị tối ưu vô cực ( +∞ hay −∞ tùy theo bài toán max hay min). Quan hệ giữa cặp bài toán đối ngẫu nhau còn thẻ hiện ở định lý sau đây. Định lý 1.1.4. (Định lý độ lệch bù). Một cặp nghiệm chấp nhận được x, y của hai qui hoạch tuyến tính đối ngẫu nhau (P) và (Q) là cặp nghiệm tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: n aij xj − bi yi = 0, ∀i = 1, 2, ...., m ⇔ y T (Ax − b) = 0 j=1 m x j cj − aij yj = 0, ∀j = 1, 2, ...., m ⇔ xT c − AT y = 0 i=1 1.2 Bài toán quy hoạch lõm với ràng buộc tuyến tính 1.2.1 Hàm lõm và tính chất Trước khi phát biểu bài toán quy hoạch lõm, ta nhắc lại khái niệm hàm lõm (hàm tựa lõm) trong Rn và một số tính chất cơ bản của hàm này. Định nghĩa 1.2.1. Hàm f: Rn → R gọi là lõm nếu: f (λx + (1 − λ) y) λf (x) + (1 − λ) f (y) ∀x, y ∈ Rn , ∀λ ∈ [0, 1] Với n = 1, bất đẳng thức này có thể diễn tả như sau: dây cung nối hai điểm bất kỳ trên đồ thị của hàm phải nằm dưới đồ thị của hàm nằm trong đoạn đó. Định nghĩa 1.2.2. Hàm f: Rn → R gọi là tựa lõm nếu: f (λx + (1 − λ) y) min {f (x) , f (y)} ∀x, y ∈ Rn , ∀λ ∈ [0, 1] Bất đẳng thức trên có nghĩa là giá trị của hàm f tại một điểm bất kỳ trên đoạn thẳng [x, y] không nhỏ hơn giá trị nhỏ nhất của hàm tại hai đầu mút của đoạn 9 thẳng đó. Từ các định nghĩa trên cho thấy một hàm lõm là hàm tựa lõm, nhưng điều ngược lại không chắc đúng. Ví dụ, f(x) = x3 (x ∈ R) là hàm tựa lõm, nhưng hàm này không là hàm lõm trên R. Như vậy lớp hàm tựa lõm rộng hơn lớp hàm lõm. Khác với hàm lồi, điểm cực tiểu địa phương của hàm lõm trên (trên một tập lồi) không nhất thiết là điểm cực tiểu toàn cục. Nói chung, thông tin địa phương không đủ để xác định điểm cực tiểu toàn cục của một hàm lõm. Định lý 1.2.3. Với mọi hàm lõm f: Rn → R ta có các kết luận sau: a) Cực tiểu của f trên một đoạn thẳng đạt tại một đầu mút của đoạn đó. b) Nếu f hữu hạn và bị chặn dưới trên một nửa đường thẳng thì cực tiểu của f trên nửa đường thẳng này đạt tại điểm gốc của nó. c) Nếu f hữu hạn và bị chặn dưới trên một tập afin thì f bằng hằng số trên tập afin đó. Định lý 1.2.4. Giả sử C ⊂ Rn là một tập lồi và f: C ⊂ Rn là hàm lõm. Nếu f(x) đạt cực tiểu trên C tại điểm trong tương đối x∗ của C ( x∗ ∈ ri C ) thì f(x) bằng hằng số trên C. Tập Argminx∈C f (x) là hợp của một số diện của C. trong đó V(C) là tập các điểm cực biên của C, nghĩa là nếu cực tiểu của f(x) đạt được trên C thì cực tiểu cũng đạt được trên V(C). Định lý 1.2.5. Giả sử C là tập lồi, đóng và f: C → R là hàm lõm. Nếu C không chứa đường thẳng nào và f(x) bị chặn dưới trên mọi nửa đường thẳng trong C thì 10 inf {f (x) : x ∈ C} = inf {f (x) : x ∈ V (C)} , trong đó V(C) là tập các điểm cực biên của C, nghĩa là nếu cực tiểu của f(x) đạt được trên C thì cực tiểu cũng đạt được trên V(C). Hệ quả 1.2.6. Cho hàm lõm f(x) trên tập lồi đa diện D, không chứa đường thẳng nào. Khi đó, hoặc f(x) không bị chặn dưới trên một cạnh vô hạn nào đó của D, hoặc f(x) đạt cực tiểu tại một đỉnh nào đó của D. Hệ quả 1.2.7. Hàm lõm f(x) trên tập lồi compac C đạt cực tiểu tại một điểm cực biên của C. Nhận xét 1. Thực ra, tính chất nêu trong Hệ quả 1.2.7 cũng đúng cho lớp hàm rộng hơn. Cụ thể là các hàm tựa lõm, nghĩa là các hàm f : Rn → [−∞, +∞] sao cho các tập mức trên Lβ = {x ∈ Rn : f (x) β} là lồi với mọi β ∈ R. Cũng có thể chứng minh được rằng cận dưới của một họ hàm tựa lõm là hàm tựa lõm, nhưng tổng của hai hàm tựa lõm không chắc là hàm tựa lõm. Nhận xét 2. Do hàm lồi là đối của hàm lõm nên các kết luận trên đây (phát biểu cho hàm lõm) cũng đúng cho hàm lồi chỉ cần thay cực tiểu bởi cực đại và bị chặn dưới bằng bị chặn trên. 1.2.2 Bài toán quy hoạch lõm (Cực tiểu hàm lõm hay cực đại hàm lồi) Xét bài toán tối ưu có dạng: (CP) min {f (x) : x ∈ C}, trong đó f(x) là hàm lõm (hay tựa lõm), C là tập lồi đóng, chẳng hạn 11 C = {x : g(x) 0} với g(x) là một hàm lồi. Đặc biệt quan trọng là trường hợp C là tập lồi đa diện. Khi đó bài toán được gọi là một quy hoạch lõm với ràng buộc tuyến tính. Quy hoạch tuyến tính và quy hoạch lồi thuộc lớp bài toán một cực trị ( hàm mục tiêu của bài toán có nhiều nhất một giá trị cực tiểu ). Một bài toán sở dĩ có nhiều giá trị cực tiểu khác nhau là do nó không lồi. Nói chung, một bài toán càng có nhiều yếu tố không lồi thì càng khó. Bài toán quy hoạch lõm thuộc lớp bài toán như thế. Quy hoạch lõm vừa nêu trên là bài toán cơ bản của tối ưu toàn cục, vì tính phổ biến của nó và vì nhiều bài toán tối ưu toàn cục quy được về nó hoặc dựa ít nhiều trên phép giải của nó. Mục tiếp sau sẽ chỉ ra rằng bài toán quy hoạch song tuyến tính có thể phát biểu như một bài toán quy hoạch lõm với hàm mục tiêu lõm, tuyến tính từng khúc và với các ràng buộc tuyến tính. 1.3 Bài toán quy hoạch song tuyến tính Định nghĩa 1.3.1. Hàm f(x, y) được gọi là một hàm song tuyến tính ( bilinear funcyion ) nếu nó là hàm tuyến tính khi cố định véctơ x hay véctơ y ở một giá trị cụ thể. Tổng quát, hàm song tuyến tính có dạng: f (x, y) = aT x + xT Qy + bT y, trong đó a, x ∈ Rn , b, y ∈ Rm và Q là ma trận cấp n × m. Dễ dàng thấy rằng các hàm song tuyến tính tạo nên một lớp con các hàm toàn phương. 12 1.3.1 Phát biểu bài toán Ta gọi bài toán tối ưu với hàm mục tiêu song tuyến tính và các hàm ràng buộc song tuyến tính là bài toán song tuyến tính (bilinear problem) và các bài toán này có thể xem như một lớp con của quy hoạch toàn phương (quadratic programming). Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong các trò chơi ma trận có ràng buộc, bài toán bù và bài toán phân việc 3 - chiều, Markovian. Nhiều bài toán nguyên 0 - 1 có thể phát biểu như các bài toán song tuyến tính. Bài toán quy hoạch lõm tuyến tính từng khúc và bài toán luồng trên mạng với phụ phí cố định, rất quen thuộc trong quản lý các chuỗi cung ứng, cũng có thể giải bằng cách dùng cách diễn đạt song tuyến tính. Tuy có nhiều dạng bài toán quy hoạch song tuyến tính, song phần lớn các bài toán thực tiễn gồm hàm mục tiêu song tuyến tính và với các ràng buộc tuyến tính và các kết quả lý thuyết được đưa ra trong trường hợp này. Trong luận văn chúng tôi xét bài toán song tuyến tính sau đây, ký hiệu bài toán là BP: min x∈X, y∈Y f (x, y) = aT x + xT Qy + bT y, (BP ) trong đó X, Y là các tập lồi đa diện, khác rỗng. Bài toán BP còn được biết với tên gọi bài toán song tuyến tính với miền ràng buộc rời nhau , bởi vì tính chấp nhận của x(y) độc lập với việc chọn véctơ y(x). 13 1.3.2 Quan hệ với bài toán quy hoạch lõm Dưới đây ta sẽ đề cập tới một số kết quả lý thuyết về sự tương đương giữa bài toán song tuyến tính và bài toán cực tiểu lõm. Cho V (x) và V (y) lần lượt là tập đỉnh của X và Y , và g(x) = miny∈Y f (x, y) = aT x + miny∈Y xT Qy + bT y . Trong đó miny∈Y f (x, y) là bài toán tuyến tính. Bởi vì nghiệm của bài toán tuyến tính đạt tại đỉnh của miền chấp nhận được nên: g(x) = miny∈Y f (x, y) = miny∈V (Y ) f (x, y). Sử dụng ký hiệu này, bài toán BP có thể phát biểu lại thành: min f (x, y) = min { min f (x, y)} = min { min f (x, y)} = min g(x) x∈X,y∈Y x∈X y∈Y x∈X y∈V (Y ) x∈X (1) Nhận xét rằng tập của Y là hữu hạn, cho mỗi y ∈ Y , f (x, y) là môt hàm tuyến tính theo x; vì thế hàm g(x) là hàm lõm tuyến tính từng khúc. Từ nhận xét này cho thấy BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc với ràng buộc tuyến tính. Ngược lại, có thể chỉ ra rằng bất kì bài toán cực tiểu hàm mục tiêu lõm, tách biến và tuyến tính từng khúc có thể quy được về bài toán quy hoạch song tuyến tính. Để thiết lập mối quan hệ này, ta xét bài toán tối ưu dưới đây: min x∈X i Φi (xi ) (2) Trong đó X là tập hợp các vectơ tùy ý khác rỗng, gồm các vectơ chấp nhận được, và Φi (xi ) là hàm lõm, tuyến tính từng khúc chỉ của một biến xi tức là 14 Φi (xi ) =   1  c xi + s1 (= Φ1 (xi )), xi ∈ λ0 , λ1  i i i i i      2  c xi + s2 (= Φ2 (xi )), xi ∈ λ0 , λ2 i i i i i   ...............................................      ni  c x + sni (= Φni (x )), x ∈ λni −1 , λni  i i i i i i i i Với c1 > c2 > ... > cni . Cho Ki = {1, 2, ..., ni }. Hàm có thể viết lại như sau: i i i Φi (xi ) = min Φk (xi ) = min ck xi + sk . i i i k∈Ki (3) k∈Ki Lập bài toán quy hoạch song tuyến tính sau đây: min f (x, y) = x∈X,y∈Y Trong đó Y = [0, 1] i k∈Ki i |Ki | k Φk (xi )yi = i i k∈Ki k (ck xi + sk )yi . i i (4) . Chứng minh định lý sau đây được suy trực tiếp từ phương trình (3). Định lý 1.3.2. Nếu (x∗ , y ∗ ) là một nghiệm tói ưu của bài toán (4) thì x∗ là một nghiệm tối ưu của bài toán (2) Chú ý là không đòi hỏi X là một đa diện lồi. Nếu X là một đa diện lồi thì cấu trúc của bài toán (4) là tương đương với (BP). Hơn nữa, ta có thể chỉ ra rằng có thể đưa bất kì bài toán cực tiểu hàm lõm toàn phương về bài toán quy hoạch song tuyến tính. Nói riêng, xét bài toán tối ưu sau đây : min Φ(x) = 2aT x + xT Qx. x∈X (5) Trong đó Q là một ma trận bán đối xứng, nửa xác định âm. Ta xây dựng bài toán quy hoạch song tuyến tính như sau: min f (x, y) = aT x + aT x + xT Qy. x∈X,y∈Y Trong đó Y = X . (6) 15 Định lý 1.3.3. Nếu x∗ là một nghiệm của bài toán (5) thì (x∗ , x∗ ) là một nghiệm của bài toán (6). Nếu (x, y) là một nghiệm của bài toán (6) thì x và y là các nghiệm của bài toán (5) 1.3.3 Tính chất nghiệm của bài toán song tuyến tính Mục trước cho thấy rằng BP tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc. Mặt khác, ta lại biết rằng cực tiểu của hàm lõm trên một tập lồi đa diện luôn đạt tại một đỉnh. Định lý sau đây được suy ra từ nhận xét này: Định lý 1.3.4. Nếu X và Y bị chặn thì tồn tại một nghiệm tối ưu của BP là (x∗ , y ∗ ) với mỗi x∗ ∈ V (X) và y ∗ ∈ V (Y ) Giả sử (x∗ , y ∗ ) là một nghiệm của (BP). Khi cố định x = x∗ , Bài toán BP trở thành bài toán tuyến tính và y ∗ là một nghiệm của bài toán nhận được. Từ tính đối xứng của bài toán, kết quả tương tự cũng đúng khi cố định y = y ∗ . Định lý sau đây là một điều kiện cần của tối ưu. Định lý 1.3.5. Nếu (x∗ , y ∗ ) là một nghiệm của bài toán BP, thì minx∈X f (x, y ∗ ) = f (x∗ , y ∗ ) = minx∈X f (x∗ , y). (7) Tuy nhiên, (7) không phải là một điều kiện đầy đủ. Trong thực tế nó đảm bảo tối ưu địa phương của (x∗ , y ∗ ) theo một yêu cầu bổ sung. Cụ thể y ∗ là một nghiệm tối ưu nhất của bài toán minx∈X f (x, y ∗ ). Từ đó suy ra rằng f (x∗ , y ∗ ) < f (x∗ , y), ∀y ∈ V (y), y = y ∗ . Do hàm f(x, y) liên tục nên với mọi ∀y ∈ V (y), y = y ∗ , f (x∗ , y ∗ ) < f (x, y) trong lân cận Uy đủ nhỏ của điểm x∗ . Đặt: