- LÊ LỆ HẰNG TOÁN TIN TỐI ƯU HÓA HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU CỦA BÀI TOÁN QUY HOẠCH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: TOÁN TIN 2010B HÀ NỘI – 2012 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI. - LÊ LỆ HẰNG TỐI ƯU HÓA HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU CỦA BÀI TOÁN QUY HOẠCH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: TOÁN TIN Người hướng dẫn khoa học: PGS. - v CHƯƠNG 1: BÀI TOÁN TỐI ƯU TRÊN TẬP PARETO. - 1 1.1 Bài toán quy hoạch tuyến tính đa mục tiêu. - 1 1.1.1 Phát biểu bài toán. - 8 1.1.3 Biểu diễn diện hữu hiệu thông qua tập mô tả. - 10 1.2 Bài toán tối ưu trên tập Pareto. - 12 CHƯƠNG 2: BÀI TOÁN QUY HOẠCH SONG TUYẾN TÍNH. - 14 2.1 Phát biểu bài toán. - 14 2.2 Bài toán tương đương. - 14 2.3 Thuật toán giải bài toán song tuyến tính. - 22 CHƯƠNG 3: THUẬT TOÁN SONG TUYẾN TÍNH GIẢI BÀI TOÁN (Q. - 36 iii LỜI MỞ ĐẦU Bài toán quy hoạch tuyến tính đa mục tiêu là bài toán tối ưu đồng thời p ≥ 2 hàm mục tiêu tuyến tính , trong đó. - độc lập với nhau trên một tập lồi đa diện khác rỗng. - Đây là bài toán có ý nghĩa quan trọng trong thực tế, đặc biệt trong lý thuyết quyết định, kinh tế, tài chính, quản lý, công nghiệp. - .Cho đến nay, rất nhiều tác giả đã đề xuất các thuật toán để xác định toàn bộ hoặc một phần tập nghiệm hữu hiệu EP của bài toán quy hoạch tuyến tính đa mục tiêu, chẳng hạn xem Một bài toán quan trọng có liên quan chặt chẽ với bài toán quy hoạch tuyến tính đa mục tiêu là bài toán tối ưu trên tập Pareto, ký hiệu là (Q. - Đó là bài toán tối ưu một hàm thực f(x) trên tập nghiệm hữu hiệu EP của bài toán quy hoạch tuyến tính đa mục tiêu. - Việc giải bài toán này giúp ta chọn được nghiệm hữu hiệu tốt nhất theo một chuẩn nào đó mà không nhất thiết phải xác định toàn bộ tập EP. - Bài toán này được Philip đề xuất năm 1972. - Đây là bài toán khó và thuộc lớp bài toán tối ưu toàn cục, tức là nghiệm tối ưu địa phương chưa chắc đã là nghiệm tối ưu toàn cục. - Tuy nhiên, do nhu cầu ứng dụng, bài toán (Q) đã thu hút được sự quân tâm đặc biệt của rất nhiều tác giả. - Nhiều thuật toán theo các tiếp cận khác nhau đã được đề xuất để giải bài toán này, như H.Benson [5], H.Benson và Sayin [6] và một số tác giả khác, xem danh mục tài liệu tham khảo kèm theo.Mục đích chính của luận văn này là trình bày thuật toán để giải bài toán tối ưu trên tập Pareto. - Chương 1 "Bài toán tối ưu trên tập Pareto". - Trình bày một số khái niệm và tính chất cơ bản của bài toán quy hoạch tuyến tính đa mục tiêu (MOLP) như điểm hữu hiệu, nghiệm hữu hiệu, điều kiện hữu hiệu, cấu trúc tập nghiệm của bài toán, biểu diễn diện hữu hiệu thông qua tập mô tả. - Tiếp đó, giới thiệu mô hình toán học của bài toán tối ưu trên tập Pareto. - iv Chương 2 "Bài toán song tuyến tính". - Trình bày một số khái niệm, tính chất cơ bản, dạng tương đương của bài toán song tuyến tính cũng như thuật toán giải bài toán quy hoạch song tuyến tính theo phương pháp siêu phẳng cắt do R.Horst và H.Tuy [9] đề xuất. - Chương 3 "Thuật toán song tuyến tính giải bài toán (Q. - Trình bày cơ sở lý thuyết và thuật toán song tuyến tính để giải bài toán (Q. - F là tập con thực sự của tập A. - Giao của tập A và B EP Tập tất cả các nghiệm hữu hiệu của bài toán (MLOP. - Tập tất cả các diện hữu hiệu của bài toán (MOLP. - Điểm trong tương đối của tập A. - Nón pháp tuyến của tập X tại điểm x0. - Bao a fin của tập A vi. - 0 intA Phần trong tương đối của A xt Véc tơ chuyển vị của véc tơ x At Ma trận chuyển vị của ma trận A v.đ.k Viết tắt của cụm từ "với điều kiện" (Q) Kí hiệu của Bài toán tối ưu trên tập Pareto (LPx) Kí hiệu của Bài toán quy hoạch tuyến tính (BLP) Kí hiệu của Bài toán quy hoạch song tuyến tính (BLPT) Kí hiệu của Bài toán tương đương với bài toán quy hoạch song tuyến tính (MOLP) Kí hiệu của Bài toán quy hoạch tuyến tính đa mục tiêu 1 Chương 1: BÀI TOÁN TỐI ƯU TRÊN TẬP PARETO Mục đích chính của chương này là giới thiệu vài nét cơ bản về bài toán tối ưu trên tập Pareto như mô hình toán học, nghiệm hữu hiệu, điều kiện hữu hiệu, cấu trúc tập nghiệm, biểu diễn diện hữu hiệu thông qua tập mô tả. - 1.1 Bài toán quy hoạch tuyến tính đa mục tiêu 1.1.1 Phát biểu bài toán Thông thường, trong RP với p ≥ 2, người ta sử dụng thứ tự sau: Cho. - Bài toán quy hoạch tuyến tính đa mục tiêu được phát biểu như sau: VMax Cx, với. - (MOLP) Trong đó C là ma trận mục tiêu cấp pxn, p ≥ 2 với p hàng là. - là tập lồi đa diện khác rỗng. - Theo định nghĩa, tập lồi đa diện. - Nói cách khác, tập lồi đa diện X là tập nghiệm của một hệ hữu hạn các bất đẳng thức tuyến tính. - Tập lồi đa diện bị chặn được gọi là đa diện. - được gọi là nghiệm hữu hiệu của bài toán (MOLP) nếu. - Nghiệm hữu hiệu còn được gọi là nghiệm tối ưu Pareto. - Ký hiệu: 2 ◊ EP là tập tất cả các nghiệm hữu hiệu của bài toán (MOLP. - Định lý sau đây cho phép ta tìm được một nghiệm hữu hiệu của bài toán (MOLP) thông qua việc giải một quy hoạch tuyến tính thông thường . - là nghiệm hữu hiệu của bài toán (MOLP) khi và chỉ khi tồn tại một véc tơ. - ≫0) sao cho x0 là nghiệm tối ưu của bài toán quy hoạch tuyến tính vô hướng sau. - Cho tập lồi khác rỗng. - Xét bài toán quy hoạch tuyến tính đa mục tiêu (MOLP). - Cho tập F là một diện của tập lồi đa diện X. - và x0 là nghiệm hữu hiệu (tức là. - Một diện F là một diện hữu hiệu (efficient face) nếu tất cả các phần tử của F đều là nghiệm hữu hiệu của bài toán (MOLP). - là nghiệm hữu hiệu của bài toán (MOLP) được phát biểu theo ngôn ngữ nón pháp tuyến. - là nghiệm hữu hiệu của bài toán (MOLP) khi và chỉ khi. - là nón pháp tuyến của tập lồi đa diện X tại điểm x0 và. - Giả sử tập lồi đa diện X là tập nghiệm của hệ bất đẳng thức tuyến tính. - là nghiệm hữu hiệu của bài toán (MOLP), trong đó X được xác định bởi (1.1), khi và chỉ khi hệ sau có nghiệm. - Xét bài toán quy hoạch tuyến tính hai mục tiêu. - tập chấp nhận được và nón pháp tuyến tại một số điểm của tập chấp nhận được minh họa ở Hình 1.1. - tập chấp nhận được và nón pháp tuyến tại một số điểm của tập chấp nhận được minh họa ở Hình 1.2. - khi và chỉ khi với x=x0, quy hoạch tuyến tính (LPx) sau. - s≥0 có một giá trị tối ưu vx=0, trong đó. - của bài toán quy hoạch tuyến tính đa mục tiêu (MOLP) là đa diện, tức là tập lồi đa diện X bị chặn, thì bài toán (MOLP) luôn có nghiệm hữu hiệu. - là đa diện thì tập nghiệm hữu hiệu EP của bài toán (MOLP) là tập compact khác rỗng. - là tập lồi đa diện không bị chặn thì bài toán (MOLP) chưa chắc đã có nghiệm hữu hiệu. - Kết quả sau cho phép xác định được sự tồn tại nghiệm hữu hiệu của bài toán (MOLP) và tìm được một nghiệm hữu hiệu đầu tiên trong trường hợp. - là tập lồi đa diện xác định bởi hệ bất đẳng thức (1.1). - Tập nghiệm hữu hiệu EP của bài toán (MOLP) bằng rỗng khi và chỉ khi hệ. - thì bài toán max〈λc,x〉,x ∈X (LP) có nghiệm tối ưu và mỗi nghiệm tối ưu của (LP) là một nghiệm hữu hiệu của bài toán (MOLP). - Xét lại bài toán cho ở Ví dụ 1.1. - theo Mệnh đề 1.5 ta có bài toán quy hoạch tuyến tính sau max. - Theo hình học giải quy hoạch tuyến tính (Hình 1.3), ta có. - Như vậy, ta thấy mỗi nghiệm tối ưu của bài toán (LP) là một nghiệm hữu hiệu của bài toán (MOLP). - 1.1.2 Cấu trúc tập nghiệm Định lý 1.3 [2] Tập nghiệm hữu hiệu EP của bài toán quy hoạch tuyến tính đa mục tiêu (MOLP) là liên thông đường gấp khúc và là hợp của một số hữu hạn các diện đóng của tập lồi đa diện ràng buộc X
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt