tailieunhanh - Luận văn Thạc sĩ Toán học: Một phương pháp xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính theo phương pháp nhánh cận và ứng dụng

Luận văn trình bày một số mô hình bài toán thực tế có dạng bài toán quy hoạch nguyên tuyến tính, phương pháp nhánh cận Land-Doig và thuật toán nón xoay xấp xỉ ngoài tái tối ưu hóa TTH giải bài toán quy hoạch tuyến tính dạng chuẩn. Mời các bạn tham khảo! | i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC - ĐÀO MINH BẰNG MỘT PHƢƠNG PHÁP XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH THEO PHƢƠNG PHÁP NHÁNH CẬN VÀ ỨNG DỤNG Chuyên ngành Toán ứng dụng Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu ĐHTN http ii MỤC LỤC MỤC LỤC .i Mở đầu . iv Chương 1. BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN. 1 . Một số mô hình thực tế thuộc dạng bài toán quy hoạch nguyên tuyến tính dạng chuẩn . 1 . Bài toán pha cắt vật liệu . 1 . Bài toán lập kế hoạch sản xuất . 2 . Bài toán cái túi . 2 . Mô hình phân bố máy bay cực tiểu tổng chi phí trên toàn mạng đường bay hàng không . 3 . Bài toán mua thuê máy bay tối ưu . 6 . Bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phương pháp giải. 7 . Bài toán quy hoạch nguyên tuyến tính . 7 . Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính . 9 . Bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính . 15 . Phương pháp nón xoay xấp xỉ ngoài tuyến tính . 16 Thuật toán xấp xỉ ngoài LP . 16 . Bảng lặp giải bài toán quy hoạch tuyến tính bởi thuật toán nón xoay xấp xỉ ngoài tuyến tính . 18 . Bài toán quy hoạch tuyến tính tái tối ưu hóa và thuật toán TTH. 22 Chương 2. THUẬT TOÁN NHÁNH CẬN XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG . 28 . Thuật toán nhánh cận xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính . 28 . Minh họa ứng dụng thuật toán nhánh cận xấp xỉ ngoài ILP giải bài toán quy hoạch nguyên tuyến tính có số chiều nhỏ với miền ràng buộc là hệ bất phương trình tuyến tính . 31 KẾT LUẬN . 52 TÀI LIỆU THAM KHẢO . 54 Số hóa bởi Trung tâm Học liệu ĐHTN http iii Số hóa bởi Trung tâm Học liệu ĐHTN http iv Mở đầu Như chúng ta đã biết nhiều bài toán thực tế dẫn đến chúng ta phải đi giải các bài toán quy hoạch nguyên tuyến tính và một trong những phương pháp hiệu quả để giải .