- TÓM TẮT LUẬN VĂN THẠC SĨĐề tài: Tiếp cận tối ưu toàn cục giải bài toán quy hoạch tích lồiTác giả luận văn: Nguyễn Thị Mai Thương Khóa Người hướng dẫn: PGS. - Nguyễn Thị Bạch KimNội dung tóm tắt:Bài toán quy hoạch tích lồi là tìm cực tiểu tích p hàm lồi fj(x), j =1. - Bài toán nàythuộc lớp bài toán tối ưu toàn cục, tức nghiệm tối ưu địa phương chưa chắcđã là nghiệm tối ưu toàn cục. - Hơn nữa, đây là bài toán NP khó, thậm chítrong trường hợp đơn giản nhất là khi p = 2, các hàm fj, j = 1, 2, là tuyếntính và G là tập lồi đa diện. - p, p ≥ 2, làtuyến tính và tập chấp nhận được G ⊂ Rnlà tập lồi đa diện khác rỗng thìta nhận được một trường hợp đặc biệt của bài toán quy hoạch tích lồi, đólà lớp bài toán quy hoạch tích các hàm tuyến tính, hay gọi tắt là bài toánquy hoạch tích tuyến tính. - Bài toán quy hoạch tích lồi là mô hình toánhọc của nhiều bài toán nảy sinh trong các lĩnh vực thực tế khác nhau như:phân tích kinh tế, xây dựng, thiết kế chip VLSI. - ngoài ra nó còn đượcứng dụng trong tối ưu đa mục tiêu.Ngoài phần Lời mở đầu, Lời cảm ơn, Danh mục các kí hiệu và chữ viếttắt, Kết luận chung, Danh mục tài liệu tham khảo, nội dung chính của luậnvăn được trình bày trong ba chương.Chương 1 "Bài toán quy hoạch tích lồi" trình bày mô hình toán họcvà một số khái niệm, kết quả liên quan đến bài toán quy hoạch tích lồi vàmột dạng bài toán tương đương của nó.Chương 2 "Thuật toán nhánh cận giải bài toán quy hoạch tíchlồi" trình bày thuật toán nhánh cận theo tiếp cận nón giải bài toán quyhoạch tích lồi mở rộng, do H. - Meyer đề xuất.1 Chương 3 "Thuật toán Heuristic giải bài toán quy hoạch tíchtuyến tính" trình bày thuật toán Heuristic giải bài toán quy hoạch tíchcác hàm tuyến tính do nhóm tác giả H. - Boger đề xuấtnăm 1997.Luận văn này đã nghiên cứu:i) Mô hình toán học của bài toán quy hoạch tích lồi (CMP. - các kháiniệm và kết quả cơ bản liên quan đến bài toán này.ii) Mối quan hệ giữa bài toán quy hoạch tích lồi trên không gian ảnh(PY) và tập điểm hữu hiệu của tập ảnh Y .iii) Tính tương đương của bài toán cực tiểu hàm tựa lõm (QCM) trênkhông gian ảnh với bài toán (CMP. - Kết quả này được sử dụng để xâydựng thuật toán giải bài toán quy hoạch tích lồi được giới thiệu trongChương 2.iv) Cơ sở lý thuyết và chi tiết thuật toán nhánh cận SMP giải bài toánquy hoạch tích lồi mở rộng (M PG): việc xây dựng nón ban đầu K0, cáchchia nhánh, tính cận, được giới thiệu đầy đủ.v) Mối liên hệ giữa bài toán quy hoạch tích các hàm tuyến tính (M LP )và bài toán quy hoạch đa mục tiêu tương ứng (MOLP ).vi) Thuật toán HES thuộc dạng Heuristic được giới thiệu trong Chương3 cho phép giải bài toán quy hoạch tích các hàm tuyến tính.vii) Một số ví dụ cụ thể để minh họa cho thuật toán.2
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt