Phương pháp chia đôi giải bài toán tối ưu trên tập Pareto tuyến tính

Báo cáo trình bày các tính chất quan trọng của bài toán (LP), cơ sở lý thuyết, điều kiện dừng của thuật toán chia đôi. Cuối cùng báo cáo nêu một ví dụ minh họa cho thuật toán. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Phương pháp chia đôi giải bài toán tối ưu trên tập Pareto tuyến tính Kỷ yếu công trình khoa học 2015 - Phần I PHƯƠNG PHÁP CHIA ĐÔI GIẢI BÀI TOÁN TỐI ƯU TRÊN TẬP PARETO TUYẾN TÍNH Nguyễn Lâm Tùng Bộ môn Toán Đại học Thăng Long Email: nguyenlamtung01@gmail.com Tóm tắt. Báo cáo trình bày một số cải tiến trong thuật toán chia đôi giải bài toán tối ưu một hàm tuyến tính trên tập Pareto [1]. Bài toán được phát biểu như sau: max ⟨d, x⟩, (P) x∈E(C,X) trong đó d ∈ R , E(C, X) là tập Pareto của bài toán tối ưu đa mục tiêu tuyến tính: V max Cx, (LP) n x∈X với C là ma trận p × n, p là số hàm mục tiêu tuyến tính, X là đa diện lồi bị chặn trong R n . Báo cáo trình bày các tính chất quan trọng của bài toán (LP), cở sở lý thuyết, điều kiện dừng của thuật toán chia đôi. Cuối cùng báo cáo nêu một ví dụ minh họa cho thuật toán. Từ khóa: đa diện lồi, tập Pareto, tối ưu, hàm tuyến tính, thuật toán chia đôi, nghiệm tối ưu. 1 Mở đầu Định nghĩa 1. Cho R n = {x ∈ R n |xi ≥ 0, ∀i = 1, n} là nón các phần + n tử không âm của R . Ta nói điểm x ∈ X cực đại Pareto của bài toán (LP) nếu: Cy − Cx ∈ R n , ∀y ∈ X, y ̸= x, tập tất cả các điểm cực đại Pareto / + của bài toán (LP) ký hiệu là E(C,X), gọi tắt là tập Pareto hay tập hữu hiệu. Định lý 1.Tập Pareto E(C, X) của bài toán (LP) là đóng, liên thông đường và bao gồm một số diện của X. Định lý 2. Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến tính ¯ (LP) khi và chỉ khi tồn tại λ ∈ Λ0 sao cho: ¯ ¯ λT Cx0 ≥ λT Cx, ∀x ∈ X với Λ = {λ = (λ1 , . . . , λp ) | λ1 + · · · + λp = 1, λi ≥ 0, ∀i = 1, p} Λ0 là phần trong tương đối của Λ. Trường Đại học Thăng Long 141 Kỷ yếu công trình khoa học 2015 - Phần I Nhận xét: Theo định lý trên, bài toán (P ) có thể mô tả thành bài toán sau: max{dT x |λT Cx ≥ g(λ), x ∈ X, λ ∈ Λ0 } trong đó g(λ) = max{λT Cy |y ∈ X}. Định lý 3.[Philip] Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến ¯ tính (LP) khi và chỉ khi tồn tại M > 0 và λ ∈ ΛM sao cho: ¯ ¯ λT Cx0 ≥ λT Cx, ∀x ∈ X với ΛM = {λ = (λ1 , . . . , λp ) | λ1 +· · ·+λp ≤ M, λi ≥ 1, ∀i = 1, p}. Trong bài báo [1], tác giả đã sử dụng định lý 3 để đưa ra thuật toán tìm kiếm chia đôi, tuy nhiên thuật toán đó có nhược điểm là: Thứ nhất, trong định lý 3 chỉ khẳng định sự tồn tại của M chứ không đưa cách xác định M, do đó khi áp dụng vào ví dụ cụ thể, việc lấy giá trị M nào đó là thiếu chặt chẽ. Thứ hai, thuật toán hội tụ chậm và chưa đưa ra được nghiệm chính xác. Bài báo cáo này chỉ dùng định lý 2, không sử dụng định lý 3 nên thuật toán chặt chẽ hơn, đồng thời đưa ra điều kiện dừng của thuật toán làm cho thuật toán dừng rất nhanh và có nghiệm chính xác. 2 Thuật toán tìm kiếm chia đôi Đặt: d∗ = max ⟨d, x⟩, γ0 = min⟨d, x⟩, β0 = max⟨d, x⟩ x∈E(C,X) x∈X x∈X trong đó E(C, X) là tập Pareto của bài toán đa mục tiêu tuyến tính (LP), X là đa diện lồi bị chặn. Dễ thấy γ0 ≤ d∗ ≤ β0 , ý tưởng của thuật toán là áp dụng một sơ đồ chia đôi miền giá trị của hàm mục tiêu để định vị giá trị d∗ . Bắt đầu từ đoạn [γ0 , β0 ] chứa d∗ , qua mỗi bước lặp k sẽ co ngắn đoạn γk , βk còn một nửa bằng cách giải bài toán: Tìm x ∈ E(C, X) sao cho dT x ≥ αk với αk = (γk + βk )/2 (Pk ) • Nếu bài toán (Pk ) có nghiệm là xk thì đặt γk+1 = dT xk , βk+1 = βk • Nếu bài toán (Pk ) vô nghiệm thì đặt γk+1 = γk , βk+1 = αk Sau khi giải bài toán (Pk ) ta có d∗ ∈ [γk+1 , βk+1 ], quá trình này sẽ kết thúc khi βk − γk ≤ ϵ cho trước. Cho α ∈ R , ký hiệu: E α = {x ∈ E(C, X) | ⟨d, x⟩ ≥ α} Trường Đại học Thăng Long 142 Kỷ yếu công trình khoa học 2015 - Phần I Ta có: E α = {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ λT Cy, ∀y ∈ X, ⟨d, x⟩ ≥ α} = {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ g(λ), ⟨d, x⟩ ≥ α} trong đó g(λ) = max{λT Cy | y ∈ X}. Đặt: hα (λ) = max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α}. Dễ dàng chứng minh được hα (λ) là hàm lồi theo λ. Xây dựng các tập: Λ = {(λ1 , λ2 , . . . , λp ) | λ1 + λ2 + · · · + λp = 1, λi ≥ 0, ∀i = 1, ..., p} Λ0 = {(λ1 , λ2 , . . . , λp ) | λ1 +λ2 +· · ·+λp = 1, λi > 0, ∀i = 1, ..., p} Ω = {(λ, t) | λ ∈ Λ0 , t ≥ g(λ)} Ωα = {(λ, t) | λ ∈ Λ0 , t > hα (λ)} ¯ Ωα = {(λ, t) | λ ∈ Λ0 , t ≥ hα (λ)} Mệnh đề 1. a. Ω và Ωα là hai tập lồi, ¯ b. Ω ⊂ Ωα , c. E α (C, X) ̸= ∅ khi và chỉ khi Ω \ Ωα ̸= ∅. Chứng minh: a. Các Ω và Ωα lồi do nó là trên đồ thị của các hàm lồi g(λ) và hα (λ). b. Hiển nhiên do g(λ) ≥ hα (λ). c. Giả sử x ∈ E α (C, X) khi đó tồn tại λ ∈ Λ0 sao cho g(λ) ≤ λT Cx. Lấy t = g(λ) suy ra (λ, t) ∈ Ω. Hơn nữa: t ≤ λT Cx, x ∈ X, ⟨d, x⟩ ≥ α nên: t ≤ max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α} = hα (λ) do đó t − hα (λ) ≤ 0 suy ra (λ, t) ∈ Ωα . / Do vậy (λ, t) ∈ Ω \ Ωα hay Ω \ Ωα ̸= ∅ . Ngược lại, giả sử (λ, t) ∈ Ω \ Ωα , theo định nghĩa ta có: t ≥ g(λ), λ ∈ Λ0 , t ≤ hα (λ) Trường Đại học Thăng Long 143 Kỷ yếu công trình khoa học 2015 - Phần I Gọi x∗ là nghiệm tối ưu của bài toán: max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α} ta có: t ≤ hα (λ) = λT Cx∗ , ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X suy ra g(λ) ≤ λT Cx∗ , λ ∈ Λ, ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X, tức là x∗ ∈ E α (C, X) hay E α (C, X) ̸= ∅. Giả sử x0 ∈ X và Sk = {(λ, t) | λ ∈ Λ, t ≥ λT Cx0 , }, k ...