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ẠO<br /> TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH<br /> <br /> LUẬN VĂN THẠC SĨ TOÁN HỌC<br /> <br /> Năm 2011<br /> <br /> BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH<br /> <br /> Chuyên ngành : TOÁN GIẢI TÍCH<br /> Mã số<br /> <br /> : 60 46 01<br /> <br /> LUẬN VĂN THẠC SĨ TOÁN HỌC<br /> Người hướng dẫn khoa học<br /> TS. TRỊNH CÔNG DIỆU<br /> <br /> Năm 2011<br /> <br /> Mở đầu<br /> Nhiề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ế…<br /> 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ệ<br /> 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ự<br /> 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ỉ<br /> 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ác<br /> mô 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ết<br /> quả 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ột<br /> việc làm cần thiết. Luận văn này sẽ góp phần làm điều đó.<br /> Luận văn được chia làm 4 chương:<br /> 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ính<br /> Chương 2: Bài toán quy hoạch tuyến tính nguyên<br /> Chương 3: Thuật toán cắt Gomory giải bài toán quy hoạch tuyến tính nguyên<br /> Chươ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.<br /> 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ên<br /> cứ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ó<br /> 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:<br /> + 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ài<br /> toá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).<br /> + 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ép<br /> thuậ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ớp<br /> bài toán rộng hơn các kết quả đã có.<br /> 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ảo<br /> sát bài toán quy hoạch tuyến tính nguyên.<br /> 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ận<br /> tì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.<br /> 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í<br /> Minh đã nhiệt tình giảng dạy tôi trong suốt quá trình học tập.<br /> 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á<br /> trình học tập cũng như thực hiện luận văn này.<br /> <br /> Mục lục<br /> Mở đầu ......................................................................................................... 3<br /> Mục lục ........................................................................................................ 4<br /> Chương 1: CẤU TRÚC TẬP RÀNG BUỘC CỦA BÀI TOÁN QUY<br /> HOẠCH TUYẾN TÍNH ............................................................................ 6<br /> 1.1. Tập lồi, tập affine và tập nón.................................................................................. 6<br /> 1.1.1. Tập lồi ........................................................................................................................6<br /> 1.1.2. Tập affine ...................................................................................................................6<br /> 1.1.3. Tập nón ......................................................................................................................7<br /> <br /> 1.2. Tập lồi đa diện ........................................................................................................ 7<br /> 1.2.1. Điểm và phương cực biên của tập lồi, đóng ..............................................................7<br /> 1.2.2. Tập lồi đa diện ...........................................................................................................9<br /> <br /> Chương 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN...... 20<br /> 2.1. Khái niệm bài toán quy hoạch tuyến tính nguyên ................................................ 20<br /> 2.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ính<br /> nguyên ......................................................................................................................... 20<br /> 2.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ài<br /> toán quy hoạch tuyến tính tương ứng .......................................................................... 22<br /> <br /> Chương 3: THUẬT TOÁN CẮT GOMORY GIẢI BÀI TOÁN QUY<br /> HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 25<br /> 3.1. Bảng đơn hình ...................................................................................................... 25<br /> 3.1.1. Khái niệm .................................................................................................................25<br /> 3.1.2. Phép biến đổi cơ bản của bảng đơn hình .................................................................26<br /> <br /> 3.2. So sánh theo nghĩa từ vựng .................................................................................. 27<br /> 3.2.1. Các khái niệm cơ bản ...............................................................................................27<br /> 3.2.2. Các tính chất cơ bản .................................................................................................27<br /> 3.2.3. Tối ưu theo nghĩa từ vựng........................................................................................28<br /> <br /> 3.3. Bảng đơn hình l-chuẩn ......................................................................................... 29<br /> 3.4. Thuật toán đơn hình đối ngẫu từ vựng tìm phương án tối ưu từ vựng................. 30<br /> 3.5. Thuật toán cắt Gomory ......................................................................................... 41<br /> <br /> 3.5.1. Điều kiện để sử dụng thuật toán Gomory ................................................................41<br /> 3.5.2. Thuật toán cắt Gomory ............................................................................................42<br /> 3.5.3. Cơ sở lí luận của thuật toán......................................................................................43<br /> 3.5.4. Ví dụ.........................................................................................................................48<br /> <br /> Chương 4: THUẬT TOÁN NHÁNH CẬNGIẢI BÀI TOÁN QUY<br /> HOẠCH TUYẾN TÍNH NGUYÊN ........................................................ 52<br /> 4.1. Thuật toán đơn hình đối ngẫu giải bài toán quy hoạch tuyến tính ....................... 52<br /> 4.2. Kỹ thuật tái tối ưu hóa .......................................................................................... 53<br /> 4.3. Thuật toán nhánh cận ........................................................................................... 54<br /> 4.3.1. Điều kiện để sử dụng thuật toán nhánh cận .............................................................54<br /> 4.3.2. Thuật toán nhánh cận ...............................................................................................54<br /> 4.3.3. Cơ sở lí luận của thuật toán......................................................................................56<br /> 4.3.4. Ví dụ.........................................................................................................................61<br /> <br /> Kết luận ..................................................................................................... 65<br /> Tài liệu tham khảo.................................................................................... 66<br /> <br />