Luận văn Thạc sĩ Toán học: Quy hoạch nguyên với mô hình tuyến tính bất kỳ

Luận văn trình bày về các nội dung: cấu trúc tập ràng buộc của bài toán quy hoạch tuyến tính, bài toán quy hoạch tuyến tính nguyên, thuật toán cắt Gomory giải bài toán quy hoạch tuyến tính nguyên, thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên. Để biết rõ hơn về nội dung chi tiết, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Quy hoạch nguyên với mô hình tuyến tính bất kỳBỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINHLUẬN VĂN THẠC SĨ TOÁN HỌCNăm 2011BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINHChuyên ngành : TOÁN GIẢI TÍCHMã số: 60 46 01LUẬN VĂN THẠC SĨ TOÁN HỌCNgười hướng dẫn khoa họcTS. TRỊNH CÔNG DIỆUNăm 2011Mở đầuNhiều vấn đề của thực tế cuộc sống hoặc trong các lĩnh vực khoa học kỹ thuật, kinh tế…dẫn đến việc giải quyết các bài toán tối ưu hóa. Trong số các mô hình tối ưu hóa thì hệtuyến tính liên tục là trường hợp đã có các kết quả tương đối trọn vẹn. Tình hình tương tựcũng xảy ra đối với hệ tuyến tính rời rạc, đó là trường hợp mà tất cả hoặc một số biến chỉnhận giá trị nguyên. Tuy nhiên các thuật toán giải hệ tuyến tính rời rạc đều áp dụng cho cácmô hình có tập phương án bị chặn, cơ sở lý luận cho trường hợp không bị chặn chưa có kếtquả nào . Việc hoàn chỉnh cơ sở lý luận cho các thuật toán giải quy hoạch nguyên là mộtviệc làm cần thiết. Luận văn này sẽ góp phần làm điều đó.Luận văn được chia làm 4 chương:Chương 1: Cấu trúc tập ràng buộc của bài toán quy hoạch tuyến tínhChương 2: Bài toán quy hoạch tuyến tính nguyênChương 3: Thuật toán cắt Gomory giải bài toán quy hoạch tuyến tính nguyênChương 4: Thuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên.Luận văn trình bày chi tiết một số kết quả của quy hoạch tuyến tính nguyên. Việc nghiêncứu quy hoạch nguyên với mô hình tuyến tính bất kỳ đã có thêm một số kết quả (không cótrong các tài liệu, giáo trình về quy hoạch tuyến tính nguyên đang lưu hành) như sau:+ Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bàitoán quy hoạch tuyến tính (không có điều kiện nguyên) tương ứng (định lý 2.4,2.5).+ Mở rộng điều kiện sử dụng phương pháp nhánh cận (định lý 4.6), do đó cho phépthuật toán nhánh cận giải bài toán quy hoạch tuyến tính nguyên có thể áp dụng cho một lớpbài toán rộng hơn các kết quả đã có.Trong luận văn này có thể xem các kết quả trên là đóng góp của tác giả cho việc khảosát bài toán quy hoạch tuyến tính nguyên.Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến Tiến sĩ Trịnh Công Diệu, Thầy đã tậntình hướng dẫn và tạo điều kiện thuận lợi giúp tôi hoàn thành luận văn này.Tôi xin gởi lời cảm ơn chân thành đến quý thầy cô trường Đại học Sư phạm Tp. Hồ ChíMinh đã nhiệt tình giảng dạy tôi trong suốt quá trình học tập.Tôi cũng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ tôi trong quátrình học tập cũng như thực hiện luận văn này.Mục lụcMở đầu ......................................................................................................... 3Mục lục ........................................................................................................ 4Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUYHOẠCH TUYẾN TÍNH ............................................................................ 61.1. Tập lồi, tập affine và tập nón.................................................................................. 61.1.1. Tập lồi ........................................................................................................................61.1.2. Tập affine ...................................................................................................................61.1.3. Tập nón ......................................................................................................................71.2. Tập lồi đa diện ........................................................................................................ 71.2.1. Điểm và phương cực biên của tập lồi, đóng ..............................................................71.2.2. Tập lồi đa diện ...........................................................................................................9Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN...... 202.1. Khái niệm bài toán quy hoạch tuyến tính nguyên ................................................ 202.2. Mối liên hệ giữa dạng chuẩn tắc và chính tắc của bài toán quy hoạch tuyến tínhnguyên ......................................................................................................................... 202.3. Mối liên hệ về tính có nghiệm giữa bài toán quy hoạch tuyến tính nguyên và bàitoán quy hoạch tuyến tính tương ứng .......................................................................... 22Chương 3: THUẬT TOÁN CẮT GOMORY GIẢI BÀI TOÁN QUYHOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 253.1. Bảng đơn hình ...................................................................................................... 253.1.1. Khái niệm .................................................................................................................253.1.2. Phép biến đổi cơ bản của bảng đơn hình .................................................................263.2. So sánh theo nghĩa từ vựng ...