Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. nội dung chi tiết. | 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 .
