Tài liệu Thuật toán tìm nghiệm hữu hiệu của bài toán tối ưu hai cấp tuyến tính đa mục tiêu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN ĐỖ QUỲNH TRANG THUẬT TOÁN TÌM NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU HAI CẤP TUYẾN TÍNH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN ĐỖ QUỲNH TRANG THUẬT TOÁN TÌM NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU HAI CẤP TUYẾN TÍNH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành :Toán ứng dụng Mã số : 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. Trần Vũ Thiệu THÁI NGUYÊN - 2016 i Mục lục Mở đầu 1 Chương 1. Kiến thức chuẩn bị về tối ưu đa mục tiêu 4 1.1 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Bài toán tối ưu đa mục tiêu tuyến tính . . . . . . . . . . . . . . . . . 8 1.3 Tìm các đỉnh và cạnh hữu hiệu . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Tìm đỉnh hữu hiệu ban đầu . . . . . . . . . . . . . . . . . . . 11 1.3.2 Tìm các đỉnh hữu hiệu và cạnh hữu hiệu . . . . . . . . . . . . 12 Chương 2. Bài toán tối ưu hai cấp tuyến tính đa mục tiêu 14 2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Xác định các điểm hữu hiệu của (BMPP’) . . . . . . . . . . . . . . . 16 2.3 Thực thi thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Bài toán tối ưu hai cấp tuyến tính đa mục tiêu . . . . . . . . . . . . . 21 2.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Tài liệu tham khảo 32 1 Mở đầu Bài toán tối ưu hai cấp có thể hiểu đơn giản là bài toán tối ưu mà trong ràng buộc của nó lại là một bài toán tối ưu khác. Bài toán tối ưu hai cấp xuất hiện trên sách báo, tạp chí có liên quan tới các hệ thống phân cấp, bài toán hai cấp nảy sinh từ nhiều ứng dụng đa dạng chẳng hạn trong hoạt động vận tải, kinh tế, sinh thái học, kỹ thuật, . . . Khi các hàm mục tiêu và các hàm ràng buộc trong bài toán là các hàm tuyến tính, thì ta có bài toán tối ưu hai cấp tuyến tính. Chúng được phân ra thành: bài toán một mục tiêu (được nghiên cứu và ứng dụng nhiều hơn), bài toán đa mục tiêu (khó ứng dụng hơn do ít có thuật toán hiệu quả) và bài toán tối ưu trên tập Pareto là trường hợp riêng biệt. Tối ưu hai cấp thuộc lớp các bài toán tối ưu toàn cục, nói chung rất phức tạp và khó giải. Nói riêng nó bao hàm bài toán tối ưu trên tập Pareto như một trường hợp cụ thể. Nhiều phương pháp đã được đề xuất, tuy nhiên hiệu quả không cao và chủ yếu đối với các bài toán tuyến tính hai cấp với một hay nhiều mục tiêu. Bài toán tối ưu hai cấp có một số dạng chính sau: • Bài toán tối ưu hai cấp một mục tiêu (Bilevel Programming Problem - BPP)     G(x) 6 0,      miny∈Y f (x, y) (BPP) min F(x, y) với x∈X   y nghiệm đúng     với g(x, y) 6 0.  với x ∈ X ⊂ Rn , y ∈ Y ⊂ Rm và F, f : X ×Y → R lần lượt là hàm mục tiêu của bài toán ngoài (bài toán cấp trên) và bài toán trong (bài toán cấp dưới), G : X → R, g : X ×Y → R là các hàm ràng buộc. 2 Khi F, f và G, g tuyến tính, bài toán gọi là bài toán tối ưu tuyến tính hai cấp (Bilevel Linear Programming Problem - BLPP) hay trò chơi Stackelberg tuyến tính (Linear Stackelberg Game - LSG). • Bài toán tối ưu đa mục tiêu hai cấp (Bilevel Multi-Objective Programming Problem - BMPP): Nếu F và f là các véctơ hàm (hàm giá trị véctơ), tức là F : Rn × Rm → R p và f : Rn × Rm → Rq Bài toán tối ưu đa mục tiêu hai cấp (BMPP) được viết như sau   min F(x, y) = min F1 (x, y), · · · , Fp (x, y) với x∈X x∈X    G(x) 6 0, x ∈ X          min f (x, y) = min f1 (x, y), · · · , fq (x, y) (BMPP)  y∈Y y∈Y  y nghiệm đúng       với g(x, y) 6 0, y ∈ Y. Khi F, f , G, g là các ánh xạ tuyến tính thì ta có bài toán tối ưu tuyến tính hai cấp đa mục tiêu. Bài toán này bao gồm trường hợp riêng là bài toán tối ưu trên tập nghiệm hữu hiệu. Đề tài luận văn “Thuật toán tìm nghiệm hữu hiệu của bài toán tối ưu hai cấp tuyến tính đa mục tiêu” có mục đích tìm hiểu và trình bày một số kết quả lý thuyết liên quan tới bài toán tối ưu hai cấp đa mục tiêu và giới thiệu thuật toán tìm nghiệm hữu hiệu của bài toán tối ưu hai cấp tuyến tính đa mục tiêu (khái niệm min được hiểu theo nghĩa Pareto sẽ được định nghĩa ở phần sau). Luận văn được viết dựa trên các tài liệu tham khảo [1]-[6] hiện có và chủ yếu nhằm giới thiệu thuật toán được đưa ra ở hai tài liệu [5] và [6]. Nội dung luận văn gồm hai chương: • Chương 1. Kiến thức chuẩn bị về tối ưu đa mục tiêu. Chương này nhắc lại một số khái niệm về tập lồi và tập lồi đa diện (đỉnh, cạnh và diện của tập lồi đa diện), khái niệm nghiệm hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu tuyến tính đa mục tiêu, tính chất tập nghiệm hữu hiệu và giới thiệu thuật toán tìm các nghiệm hữu hiệu của bài toán. 3 • Chương 2. Bài toán tối ưu hai cấp tuyến tính đa mục tiêu có nội dung: – Phát biểu bài toán tối ưu hai cấp tuyến tính đa mục tiêu. – Khái niệm nghiệm hữu hiệu. – Tính chất nghiệm hữu hiệu của bài toán. – Thuật toán tìm các nghiệm hữu hiệu của bài toán. Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong soạn thảo văn bản chắc chắn không tránh khỏi có những sai sót nhất định. 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. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán-Tin, Trường Đại học Khoa học Thái Nguyên và của Viện Toán học đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, ngày 20 tháng 5 năm 2015 Tác giả Nguyễn Đỗ Quỳnh Trang 4 Chương 1 Kiến thức chuẩn bị về tối ưu đa mục tiêu Chương này nhắc lại một số kiến thức về tập lồi đa diện, khái niệm nghiệm hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu tuyến tính đa mục tiêu và giới thiệu cách tìm các đỉnh và cạnh hữu hiệu của bài toán, dựa trên phương pháp nón pháp tuyến. Nội dung của chương được tham khảo từ các tài liệu [1], [4] và [6]. 1.1 Tập lồi đa diện Trước hết ta nêu lại một số khái niệm có liên quan. Định nghĩa 1.1.1 (Tập afin). Tập M ⊆ Rn được gọi là một tập afin nếu có λ a + (1 − λ )b ∈ M với mọi a, b ∈ M và mọi λ ∈ R, tức là nếu M chứa hai điểm nào đó thì M chứa cả đường thẳng đi qua hai điểm ấy. Định nghĩa 1.1.2. Bao afin của một tập E ⊂ Rn là giao của tất cả các tập afin chứa E, ký hiệu aff(E). Đó là tập afin nhỏ nhất chứa E. Định nghĩa 1.1.3. Thứ nguyên (hay số chiều) của một tập afin M được định nghĩa bằng số chiều của không gian con song song với M. Định nghĩa 1.1.4 (Tập lồi). Tập C ⊆ Rn được gọi là một tập lồi nếu với mọi x1 , x2 ∈ C và mọi λ ∈ [0, 1] ta có λ x1 + (1 − λ )x2 ∈ C. Thứ nguyên của tập lồi C, ký hiệu dimC, được định nghĩa bằng thứ nguyên của affC (bao afin của C). Bổ đề 1.1.5. Giao của một họ bất kỳ các tập lồi trong Rn là một tập lồi. 5 Định nghĩa 1.1.6 (Siêu phẳng). Cho véctơ a ∈ Rn (a 6= 0) và số b ∈ R. Tập  H = x ∈ R n | aT x = a1 x 1 + . . . + an x n = b gọi là một siêu phẳng trong Rn . Đó là tập nghiệm của một phương trình tuyến tính trong Rn . Ví dụ 1.1.7. Trong không gian 3 chiều R3 , phương trình ax + by + cz = d, với a, b, c, d ∈ R không cùng bằng 0, xác định một siêu phẳng (mặt phẳng) trong R3 . Định nghĩa 1.1.8. Cho véctơ a ∈ Rn (a 6= 0) và số b ∈ R. Khi đó, các tập  H1 = x ∈ Rn | aT x = a1 x1 + . . . + an xn ≤ b ,  H1 = x ∈ Rn | aT x = a1 x1 + . . . + an xn ≥ b , gọi là các nửa không gian đóng, xác định bởi siêu phẳng aT x = b. Ví dụ 1.1.9. Trong mặt phẳng R2 , Siêu phẳng x1 + x2 = 2 tạo ra hai nửa không gian (nửa mặt phẳng) đóng  H1 = x ∈ R2 | x1 + x2 ≤ 2 và  H2 = x ∈ R2 | x1 + x2 ≥ 2 Bổ đề 1.1.10. Mọi siêu phẳng và nửa không gian đóng là các tập lồi. Định nghĩa 1.1.11 (Tập da diện). Nếu P ⊆ Rn là giao của một số hữu hạn các nửa không gian đóng thì P được gọi là một tập đa diện. Một cách hình thức, cho a1 , . . . , am ∈ Rn là tập hữu hạn các véctơ cột và b1 , . . . , bm là các hằng số. Xét các nửa m   T không gian đóng Hi = x ∈ Rn | ai , x ≥ bi . Khi đó, P = Hi là một tập đa diện. i=1 i  Mỗi bất phương trình a , x ≥ bi gọi là một ràng buộc cuả P. Ta nói điểm x0 ∈ P thỏa ∗  mãn chặt ràng buộc i∗ nếu ai , x ≥ bi∗ . Bổ đề 1.1.12. Tập đa diện là một tập lồi. Một tập đa diện có thể không bị chặn. Một tập đa diện bị chặn còn được gọi là một đa diện lồi. Các đa giác lồi theo nghĩa thông thường trong mặt phẳng (tam giác, hình chữ nhật, hình thang, . . . ) là những ví dụ cụ thể về đa diện lồi. 6 Định nghĩa 1.1.13 (Đường thẳng). Cho hai véctơ x0 , d ∈ Rn (d 6= 0). Đường thẳng đi qua x0 theo phương d là tập các điểm x(λ ) = x0 + λ d với λ ∈ R. Véctơ d gọi là véctơ chỉ phương của đường thẳng. Định nghĩa 1.1.14 (Tia). Cho điểm x0 ∈ Rn và véctơ chỉ phương d ∈ Rn (d 6= 0). Tia  đi từ x0 theo hướng d là tập điểm Γ = x | x = x0 + λ d, λ ≥ 0 .. Định nghĩa 1.1.15 (Nón lồi). Cho tập lồi K ⊆ Rn . Khi đó, K là một nón lồi nếu với mọi x ∈ K và mọi λ > 0, ta có λ x ∈ K. Một tập lồi đa diện mà đồng thời là một nón lồi gọi là một nón lồi đa diện. Định nghĩa 1.1.16 (Hướng lùi xa). Cho một tập lồi C ⊆ Rn . Véctơ d ∈ Rn , d 6= 0 gọi là một hướng lùi xa của C nếu  x | x = x0 + λ d, λ ≥ 0 ⊆ C với mọi x0 ∈ C. Có quan hệ đáng chú ý sau giữa ma trận A xác định P và hướng lùi xa của P. Định lí 1.1.17. Giả sử P ⊆ Rn là một tập đa diện xác định bởi P = {x ∈ Rn : Ax ≥ b, x ≥ 0} . Khi đó, d là một hướng lùi xa của P khi và chỉ khi Ad ≥ 0, d ≥ 0, d 6= 0. Hệ quả 1.1.18. Nếu P0 = {x ∈ Rn : Ax = b, x ≥ 0}. Khi đó, d là một hướng lùi xa của P khi và chỉ khi Ad = 0, d ≥ 0, d 6= 0. Định nghĩa 1.1.19 (Nón lùi xa). Nón lồi tạo nên bởi tập tất cả các hướng lùi xa của một tập lồi C và véctơ 0 gọi là nón lùi xa của C, ký hiệu recC. Ví dụ 1.1.20. Với các tập đa diện P và P0 vừa xét ở trên thì rec P = {d ∈ Rn : Ad ≥ 0, d ≥ 0} và rec P0 = {d ∈ Rn : Ad = 0, d ≥ 0} . Định lí 1.1.21. Tập đa diện P không bị chặn khi và chỉ khi rec P 6= {0}. 7 Định nghĩa 1.1.22 (Diện của tập lồi). Một tập con lồi F của một tập lồi C gọi là một diện (face) của C nếu x, y ∈ C mà λ x + (1 − λ )y ∈ F, với một λ ∈ (0, 1) thì [x, y] ⊆ F, nghĩa là một đoạn thẳng bất kỳ thuộc C mà có một điểm bên trong nó thuộc F thì cả đoạn thẳng ấy phải nằm trọn trong F. Một diện của C, khác rỗng và khác C, gọi là một diện thực sự của C. Ví dụ, các diện thực sự của khối lập phương trong R3 là 8 đỉnh, 12 cạnh và 6 mặt của nó. Định nghĩa 1.1.23 (Điểm cực biên). Một diện có thứ nguyên (số chiều) 0 gọi là một điểm cực biên của C. Nói cách khác, x0 ∈ C là một điểm cực biên của C nếu không tồn tại x1 , x2 ∈ C, x1 6= x0 hoặc x2 6= x0 sao cho x0 = λ x1 + (1 − λ )x2 với λ ∈ (0, 1). Điểm cực biên của tập đa diện P gọi là một đỉnh của P. Định nghĩa 1.1.24 (Đỉnh suy biến). Cho tập đa diện P = {x ∈ Rn : Ax ≥ b}. Giả sử x0 là một đỉnh của P. Nếu x0 thỏa mãn chặt (với dấu bằng) đúng n ràng buộc xác định P thì x0 gọi là một đỉnh không suy biến, trái lại (x0 thỏa mãn chặt nhiều hơn n ràng buộc) thì x0 gọi là một đỉnh suy biến. Cho tập đa diện P 6= ∅ xác định bởi hệ bất phương trình tuyến tính i  a , x ≥ bi, i = 1, 2, . . . , m.   Với x ∈ P, ký hiệu I(x) = i : ai , x = bi là tập chỉ số những ràng buộc mà x thỏa   mãn chặt. Đặt I0 = i : ai , x = bi với x ∈ P . Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của P được cho trong định lý sau. Định lí 1.1.25 (Diện của tập đa diện). Một tập con lồi khác rỗng F ⊂ P là một diện thực sự của P khi và chỉ khi   F = x : ai , x = bi , i ∈ I, i  a , x ≥ bi , i ∈ /I với I là tập chỉ số sao cho I0 ⊂ I ⊂ {1, . . . , m} (I gọi là tập chỉ số xác định diện F). Hơn nữa, ta có dim F = n − rank{ai : i ∈ I} và dim P = n − rank{ai : i ∈ I0 }. 8 Định nghĩa 1.1.26 (Cạnh và đỉnh kề). Một diện của tập đa diện P có thứ nguyên 1 gọi là một cạnh: cạnh là hữu hạn nếu diện đó là một đoạn thẳng, cạnh là vô hạn nếu diện đó là một nửa đường thẳng (tức tia) hay cả đường thẳng. Hai đỉnh của P gọi là kề nhau nếu chúng được nối với nhau bằng một cạnh hữu hạn.  Hệ quả 1.1.27. Cho P là tập đa diện xác định bởi hệ ai , x ≥ bi , với i = 1, . . . , m: (a) Điểm x0 ∈ P là một đỉnh của P khi và chỉ khi rank{ai : i ∈ I(x0 )} = n, nghĩa là x0 thỏa mãn chặt n ràng buộc độc lập tuyến tính của P; (b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) Γ ⊂ P là một cạnh của P thì Γ được xác định bởi một tập chỉ số I sao cho rank{ai : i ∈ I} = n − 1. 1.2 Bài toán tối ưu đa mục tiêu tuyến tính Xét bài toán tối ưu đa mục tiêu có dạng Vmin h(x) = [h1 (x), . . . , h p (x)] với x ∈ U, (MOPP) h : Rn → R p là véctơ hàm mục tiêu, U ⊆ Rn là tập ràng buộc của bài toán. Để giải (MOPP), ta cần phải so sánh các véctơ hàm mục tiêu [h1 (x), . . . , h p (x)] đối với các x ∈ U khác nhau. Vì thế, ta cần xác định một quan hệ thứ tự trên h(U), dùng để só sánh. Vì với p ≥ 2, trong R p không có thứ tự toàn phần như trong R1 nên ta chỉ có thể xác định một thứ tự bộ phận trên h(U). Giả sử K là một nón tùy ý sao cho K ⊂ R p , một quan hệ nhị nguyên (hai ngôi) theo nón K, ký hiệu ≤K , được xác định bởi a ≤K b khi và chỉ khi (b − a) ∈ K. Quan hệ thứ tự bộ phận tạo ra bởi các nón lồi, đóng và nhọn hay được sử dụng nhất. Do không thể tìm được một nghiệm mà là tối ưu đồng thời cho mọi hàm mục tiêu, nên ta dùng một khái niệm yếu hơn, đó là khái niệm điểm không bị vượt trội. Định nghĩa 1.2.1. Điểm y0 ∈ h(U) gọi là điểm không bị vượt trội (non-dominated point) trên h(U)theo nón K nếu không tồn tại điểm y ∈ h(U), y 6= y0 sao cho y ≤K y0 . 9 Nếu y∗ ∈ h(U) là điểm không bị vượt trội theo nón K thì x∗ ∈ U sao cho y∗ = h(x∗ ) gọi là điểm tối ưu Pareto (Pareto-optimal point) theo nón K. Định nghĩa sau đây về các điểm hữu hiệu hay được sử dụng trên thực tế. Định nghĩa 1.2.2. Điểm x∗ ∈ U gọi là điểm tối ưu Pareto hay nghiệm hữu hiệu (efficiant solution) của bài toán (BMPP) nếu không tồn tại x ∈ U sao cho [h1 (x), . . . , h p (x)] ≤ [h1 (x∗ ), . . . , h p (x∗ )], và [h1 (x), . . . , h p (x)] 6= [h1 (x∗ ), . . . , h p (x∗ )]. Nếu x∗ là một điểm tối ưu Pareto thì h(x∗ ) gọi là một điểm không bị vượt trội (theo p nón K ≡ R+ \ {0 p }). Khi đó các nghiệm hữu hiệu, hay nghiệm tối ưu Pareto, là những nghiệm mà không thể cải tiến theo một mục tiêu nào đó mà lại không làm thiệt hại ít nhất một mục tiêu khác (Ví dụ xe khách chạy một lúc sẽ tạo ra trên xe trạng thái tối ưu Pareto). Ta nhận xét là Định nghĩa 1.1.22 là một trường hợp đặc biệt của Định nghĩa 1.1.19 p với nón được sử dụng là R+ \ {0 p }. Giải một bài toán tối ưu đa mục tiêu có nghĩa là tìm một phần hay toàn bộ tập điểm hữu hiệu và đệ trình nó cho người ra quyết định xem xét, đánh giá và lựa chọn. Khi đó, nghiệm do người ra quyết định lựa chọn (chẳng hạn theo một tiêu chuẩn nào đó) được xem là nghiệm tối ưu của bài toán tối ưu đa mục tiêu đã cho. Khi h(x) là một ánh xạ tuyến tính và U là một tập lồi đa diện thì ta có bài toán tối ưu tuyến tính đa mục tiêu, ký hiệu là (MOLP). Có thể phát biểu như sau: Vmin {Cx : x ∈ D} (MOLP) với C là ma trận cấp p × n và D ⊆ Rn là một tập lồi đa diện được xác định bởi hệ i  a , x ≥ bi , i = 1, 2, . . . , m. với ai ∈ Rn và bi ∈ R (i = 1, . . . , m) cho trước. Sau đây là một số khái niệm về nghiệm của bài toán (MOLP). (1.1) 10 Định nghĩa 1.2.3. Ta nói x0 ∈ D là một nghiệm hữu hiệu của (MOLP) nếu không có x ∈ D với Cx0 ≥ Cx và Cx0 6= Cx. Nếu mọi điểm thuộc diện F ⊆ D là nghiệm hữu hiệu thì ta nói F là một diện nghiệm hữu hiệu, hay đơn giản, diện hữu hiệu. Nếu diện hữu hiệu F là một đỉnh (hay cạnh) của D thì để đơn giản, ta nói F là một đỉnh hữu hiệu (hay cạnh hữu hiệu) của (MOLP). Định nghĩa 1.2.4. Ta nói x0 ∈ D là một nghiệm hữu hiệu yếu của (VP) nếu không có x ∈ D với Cx0 > Cx. Ta còn nói x0 ∈ D là một nghiệm hữu hiệu lý tưởng nếu Cx0 ≤ Cx với mọi x ∈ D. Hình 1.1: D1 và D2 : x1 , x2 - đỉnh hữu hiệu, [x1 , x2 ] - cạnh hữu hiệu; trong D2 : [x0 , x1 ) - hữu hiệu yếu; trong D3 : x0 - hữu hiệu lý tưởng Hình 1.1 minh họa tập nghiệm hữu hiệu trong R2 khi C = I2 (ma trận đơn vị). Rõ ràng một nghiệm hữu hiệu cũng là nghiệm hữu hiệu yếu, nhưng điều ngược lại không chắc đúng. Chương này quan tâm chủ yếu tới các nghiệm hữu hiệu của bài toán (MOLP). Ta có kết quả quan trọng sau đây. Bổ đề 1.2.5. Điểm x0 ∈ D là một nghiệm hữu hiệu của (MOLP) khi và chỉ khi có véctơ dương λ ∈ R p (λ > 0) sao cho x0 là nghiệm cực tiểu của hàm tuyến tính f (x) = λ T Cx trên D. Bổ đề 1.2.6. Nếu tập D bị chặn thì bài toán (MOLP) luôn có nghiệm hữu hiệu. Sau đây là một điều kiện cần và đủ để một điểm là nghiệm hữu hiệu. Bổ đề 1.2.7. x0 ∈ D là một nghiệm hữu hiệu của (MOLP) khi và chỉ khi nón pháp tuyến của D tại x0 là pháp tuyến âm, tức là ND(x0 ) có chứa véctơ C-âm. 11 Từ đó suy ra một số hệ quả sau về nghiệm hữu hiệu của bài toán (MOLP). Hệ quả 1.2.8. Giả sử I(F) là tập chỉ số xác định diện F ⊆ D. Khi đó, F là diện hữu hiệu khi và chỉ khi I(F) là tập chuẩn tắc âm, theo nghĩa
  cone −ai : i ∈ I ∩ ri − cone c1 , . . . , c p = ∅ Hệ quả 1.2.9. Tập nghiệm hữu hiệu của (MOLP) là rỗng khi và chỉ khi [
 ND (x) ∩ ri − cone c1 , . . . , c p = ∅. x∈D Nếu giao này khác rỗng thì mỗi phần tử v thuộc giao sinh ra một nghiệm hữu hiệu  của (VP), đó là nghiệm cực tiểu của bài toán min −vT x : x ∈ D . Hệ quả 1.2.10. Tập nghiệm hữu hiệu của (MOLP) là liên thông đường gấp khúc, nghĩa là với bất kỳ hai nghiệm hữu hiệu x, y ∈ D, tồn tại hữu hạn nghiệm hữu hiệu x1 , . . . , xk sao cho x0 = x, xk = y và mọi đoạn [xi , xi+1 ], i = 0, . . . , k − 1, là hữu hiệu. 1.3 Tìm các đỉnh và cạnh hữu hiệu Mục này nhắc lại tóm tắt thuật toán tìm đỉnh và cạnh hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu (MOLP), dựa theo phương pháp nón pháp tuyến [4]. Ta nêu lại bài toán (MOLP) Vmin {Cx : x ∈ D} với C ⊂ R p×n và   D = x ∈ Rn : ai , x ≥ bi, i = 1, 2, . . . , m trong đó ai ∈ Rn , bi ∈ R (i = 1, . . . , m) cho trước. Giả thiết D 6= ∅ và mọi đỉnh của D đều không suy biến (xem Định nghĩa 1.1.24). 1.3.1 Tìm đỉnh hữu hiệu ban đầu Giải hệ p m ∑ µia i=1 i = ∑ λk ck , k=1 µi ≥ 0, i = 1, . . . , m, λk > 0, k = 1, . . . , p. 12 Nếu hệ vô nghiệm thì dừng: Bài toán (MOLP) không có nghiệm hữu hiệu. Trái lại, giả sử λ > 0 là một nghiệm. Đặt v = CT λ . Nếu v = 0 thì dừng: Tập D là hữu hiệu (tức là mọi x ∈ D là nghiệm hữu hiệu). Còn nếu v 6= 0, giải bài toán qui hoạch tuyến tính: min{vT x : x ∈ D}. Ta thu được nghiệm tối ưu, chẳng hạn đỉnh x0 , và x0 là một đỉnh hữu hiệu ban đầu của bài toán (MOLP). 1.3.2 Tìm các đỉnh hữu hiệu và cạnh hữu hiệu Giả sử x0 là một đỉnh hữu hiệu. Ký hiệu   I(x0 ) = i ∈ {1, . . . , m} : ai , x0 = bi . Bất kỳ tập con I ⊂ I(x0 ) với |I| = n − 1 và {ai : i ∈ I} độc lập tuyến tính, xác định một  hướng v 6= 0 từ hệ phương trình ak , x = 0, k ∈ I. Để biết cạnh đi từ x0 theo hướng v là hữu hiệu, ta kiểm tra: (a) I là tập chuẩn tắc âm hay nón sinh bởi {−ai : i ∈ I} có chứa véctơ C-âm. (b) I là tập chuẩn tắc hay hệ i  a , x = bi , i  a , x ≥ bi , i ∈ I; i ∈ {1, . . . , m} \ I. Ta nói tập chỉ số I ⊆ {1, . . . , m} là chuẩn tắc âm nếu nón sinh bởi {−ai : i ∈ I} có chứa véctơ C-âm (tức là véctơ biểu diễn được thành tổng các véctơ hàng của C với các hệ số âm). THUẬT TOÁN. Tìm các cạnh hữu hiệu đi từ đỉnh hữu hiệu x0 Bước 0 (khởi sự). Xác định tập chỉ số tích cực:   I(x0 ) = i ∈ {1, . . . , m} ai , x = bi . Nếu |I(x0 )| = n, chuyển sang Bước 1. Trái lại (tức là |I(x0 )| > n), chuyển tới Bước 2. 13 Bước 1. (Đỉnh x0 không suy biến). Chọn tập I ⊂ I(x0 ) với |I| = n − 1 (n tập). 1a) Kiểm tra I chuẩn tắc âm: Giải hệ p m ∑ µia i = i=1 ∑ λk ck , µi ≥ 0, i = 1, . . . , m, λk > 0, k = 1, . . . , p. k=1 Nếu hệ này vô nghiệm thì chọn một tập I ⊂ I(x0 ) khác (|I| = n − 1) và quay lại thực hiện 1a). Trái lại, I là tập chuẩn tắc âm và chuyển sang thực hiện 1b). 1b) Tìm cạnh hữu hiệu tương ứng: Tìm hướng v của cạnh đi từ x0 bằng cách   giải hệ ak , v = 1, k ∈ I(x0 ) \ I, ai , v = 0, i ∈ I. Đặt   ti = max t : ai , x0 + tv ≥ bi , t ≥ 0 , i ∈ {1, . . . , m} \ I, t0 = min {ti : i ∈ {1, . . . , m} \ I} . 1c) Nếu 0 < t0 < ∞ thì x0 + t0 v là một đỉnh hữu hiệu và [x0 , x0 + t0 v] là một cạnh hữu hiệu kề x0 . Lưu giữ đỉnh và cạnh hữu hiệu nếu trước đó chúng chưa được lưu giữ. Chọn một tập I ⊂ I(x0 ) khác (|I| = n − 1) và quay lại thực hiện 1a). 1d) Nếu t0 = ∞ thì {x0 + tv : t ≥ 0} là một tia hữu hiệu. Ghi lại kết quả. Chọn một tập I ⊂ I(x0 ) khác (|I| = n − 1) và quay lại thực hiện 1a). Thuật toán sẽ dừng khi mọi tập con I ⊂ I(x0 ), |I| = n − 1, đã được xét. Kết luận Chương 1 Chương 1 đã đề cập tới bài toán tối ưu đa mục tiêu và trường hợp riêng là bài toán tối ưu tuyến tính đa mục tiêu, nhắc lại một số khái niệm có liên quan đến bài toán như: tập lồi đa diện và các đỉnh, cạnh, diện của tập lồi đa diện, khái niệm điểm tối ưu Pareto hay nghiệm hữu hiệu của bài toán đa mục tiêu và giới thiệu tóm tắt thuật toán xác định các đỉnh và cạnh hữu hiệu của bài toán, dựa theo phương pháp nón pháp tuyến. 14 Chương 2 Bài toán tối ưu hai cấp tuyến tính đa mục tiêu Chương này đề cập tới bài toán tối ưu hai cấp đa mục tiêu và trường hợp riêng là bài toán tối ưu hai cấp tuyến tính đa mục tiêu. Phần đầu trình bày một số kết quả lý thuyết liên quan tới bài toán tối ưu hai cấp đa mục tiêu. Sau đó giới thiệu thuật toán giải bài toán tối ưu hai cấp tuyến tính đa mục tiêu và xét một ví dụ minh họa cho thuật toán giải trình bày. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [5] và [6]. 2.1 Phát biểu bài toán Bài toán tối ưu hai cấp một mục tiêu (Bilevel Programming Problem) có thể phát biểu như sau: min F(x, y) với x∈X     G(x) 6 0,      miny∈Y f (x, y)   y nghiệm đúng     với g(x, y) 6 0.  (BPP) với x ∈ X ⊂ Rn , y ∈ Y ⊂ Rm và F, f : X ×Y → R lần lượt là hàm mục tiêu của bài toán ngoài (bài toán cấp trên) và bài toán trong (bài toán cấp dưới), G : X → R, g : X ×Y → R là các hàm ràng buộc bất đẳng thức. Khi các hàm mục tiêu (F, f ) và các hàm ràng buộc (G, g) trong bài toán cấp trên và bài toán cấp dưới là hàm tuyến tính thì bài toán lúc đó gọi là bài toán tối ưu tuyến 15 tính hai cấp (Bilevel Linear Programming Problem, viết tắt là BLPP) hay trò chơi Stackelberg tuyến tính (Linear Stackelberg Game). Nếu F và f là các véctơ hàm (hàm giá trị véctơ), tức là F : Rn × Rm → R p và f : Rn × Rm → Rq thì ta có bài toán tối ưu đa mục tiêu hai cấp (Bilevel Multi-Objective Program-ming Problem, viết tắt BMPP). Bài toán tối ưu đa mục tiêu hai cấp (BMPP) có thể phát biểu như sau:   min F(x, y) = min F1 (x, y), · · · , Fp (x, y) x∈X x∈X    G(x) 6 0, x ∈ X           (BMPP) với min f (x, y) = min f1 (x, y), · · · , fq (x, y)  y∈Y y∈Y  y nghiệm đúng       với g(x, y) 6 0, y ∈ Y. Với mỗi quyết định x của cấp trên, ký hiệu R(x) là tập phương án của cấp dưới. Tập này thường được xác định là tập điểm tối ưu Pareto của bài toán: min f (x, y) = ( f1 (x, y), . . . , fq (x, y)) y∈Y với g(x, y) ≤ 0. Với các ký hiệu đó, ta có thể phát biểu bài toán (BMPP) dưới dạng: F(x, y) = [F1 (x, y), . . . , Fp (x, y)] với G(x) ≤ 0, y ∈ R(x). Ký hiệu Ω là tập chấp nhận được (feasible space) của (BMPP), xác định bởi Ω = {(x, y) ∈ X ×Y ⊆ Rn × Rm | G(x) ≤ 0 và y ∈ R(x)} . Phát biểu ngắn gọn bài toán (BMPP) như sau: min F(x, y) = [F1 (x, y), . . . , Fp (x, y)]. (x,y)∈Ω Ta có định nghĩa sau. (BMPP’) 16 Định nghĩa 2.1.1. (x∗ , y∗ ) là một điểm (hay nghiệm) hữu hiệu (efficient point/solution) của (BMPP’) khi và chỉ khi (x∗ , y∗ ) ∈ Ω và không tồn tại (x, y) ∈ Ω sao cho [F1 (x, y), . . . , Fp (x, y)] ≤ [F1 (x∗ , y∗ ), . . . , Fp (x∗ , y∗ )] và [F1 (x, y), . . . , Fp (x, y)] 6= [F1 (x∗ , y∗ ), . . . , Fp (x∗ , y∗ )]. Mục đích chính là xác định các điểm hữu hiệu của bài toán (BMPP). Để cho tiện, sau đây tập điểm hữu hiệu của bài toán tối ưu đa mục tiêu, xác định bởi hàm giá trị véctơ h trên tập chấp nhận được U theo nón K, sẽ được ký hiệu là E(h,U, ≤K ). Nếu khi nói về điểm hữu hiệu mà không nhắc tới nón cụ thể nào thì p điểm hữu hiệu được hiểu theo Định nghĩa 1.2.2. Ta còn sử dụng các ký hiệu: K1 = R− \  n n {0 p }, K2 = Rq+ \{0q }, X = Rn+ , Y = Rm + , Z = (x, y) ∈ R+ × R+ | G(x) ≤ 0 và y ∈ R(x) và S chỉ toàn bộ tập điểm hữu hiệu của bài toán (BMPP’). 2.2 Xác định các điểm hữu hiệu của (BMPP’) Xét bài toán tối ưu đa mục tiêu (cấp dưới), được xây dựng từ dữ liệu của bài toán (BMPP’). min f¯(x, y) = ( f1 (x, y), . . . , fq (x, y), x) với (x, y) ∈ Z. x,y Giả sử K3 = Rq+ \ {0q } × {0n } và Ω là tập được xác định như trước đây. Định lí 2.2.1. Ω = E( f¯, Z, ≤K ). Chứng minh. Xem Pieume C. O. et al [6, p.291]. Khi đó, việc giải (BMPP’) tương đương với giải bài toán: min F(x, y) = [F1 (x, y), . . . , Fp (x, y)] x∈X Điều này dẫn một cách tự nhiên đến hệ quả sau. Hệ quả 2.2.2. S = E(F, E( f¯, Z, ≤K3 ), ≤K1 ). với (x, y) ∈ E( f¯, Z, ≤K ). (MPP2 ) 17 Tìm E( f¯, Z, ≤K ) không phải là việc dễ dàng ít nhất là vì hai lý do: Thứ nhất, rất khó để xác định được toàn bộ tập hữu hiệu E( f¯, Z, ≤K ) vì tập này có vô số điểm và thứ hai, trong các tài liệu không có phương pháp xác định các điểm hữu hiệu đối với nón đặc biệt K3 = Rq+ \ {0q } × {0n }. Thông thường chỉ có các phương pháp tìm các nghiệm hữu hiệu đối với các nón dạng Rn+ \ {0n }, n ∈ N. Đặt K4 = Rq+n + \ {0q+n } (Rõ ràng là K4 ⊃ K3). Ta có kết quả sau. Định lí 2.2.3. E( f¯, Z, ≤K4 ) ⊂ E( f¯, Z, ≤K3 ). Chứng minh. Giả sử X = (x, y) ∈ E( f¯, Z, ≤K4 ). Khi đó, không tồn tại X 0 = (x0 , y0 ) ∈ Z sao cho (X 0 ) − (X) ∈ K4 . Do K3 ⊂ K4 nên không tồn tại X 0 = (x0 , y0 ) sao cho (X 0 ) − (X) ∈ K3 . Do đó X = (x, y) ∈ E( f¯, Z, ≤K3 ). Suy ra định lý. Định lý 2.2.3 gợi ý cách tìm một tập con của E( f¯, Z, ≤K3 ) nhờ giải bài toán min F(x, y) = [F1 (x, y), . . . , Fp (x, y)] x∈X với (x, y) ∈ E( f¯, Z, ≤K ). (BMPP”) Rõ ràng từ cách phát biểu này và Hệ quả 2.2.2 dẫn đến hệ quả sau. Hệ quả 2.2.4. E(F, E( f¯, Z, ≤K4 ), ≤K1 ) ⊆ S. Ngay cả khi nón dùng trong cách phát biểu cuối cùng này là K1 = Rn+ \ {0n }, n ∈ N, thì bài toán tối ưu nhiều hàm mục tiêu trên tập điểm hữu hiệu cũng không dễ dàng. Các tác giả bài báo [6] đưa ra một bài toán mới dễ giải hơn và việc giải nó có thể cho phép tìm được một tập con các nghiệm hữu hiệu của (BMPP"). Xét bài toán tối ưu đa mục tiêu sau đây. min F(x, y) = [F1 (x, y), . . . , Fp (x, y)] x∈X với (x, y) ∈ Z. (MPP1 ) Định lí 2.2.5. E( f¯, Z, ≤K4 ) ∩ E(F, Z, ≤K1 ) ⊆ E(F, E( f¯, Z, ≤K4 ), ≤K1 ). Chứng minh. Giả sử (x, y) ∈ E( f¯, Z, ≤K4 )∩E(F, Z, ≤K1 ), nghĩa là (x, y) ∈ E( f¯, Z, ≤K4 ) và (x, y) ∈ E(F, Z, ≤K1 ). Giả sử phản chứng rằng (x, y) ∈ / E(F, E( f¯, Z, ≤K4 ), ≤K1 ).