tailieunhanh - Tiểu luận: Thuật toán Gomory

Ảnh hưởng của sai số làm tròn có thể dẫn đến lời giải sai khi dùng phương pháp đơn hình giải bài toán quy hoạch tuyến tính. Khi giải bài toán quy hoạch tuyến tính nguyên ảnh hưởng sai số làm tròn tăng mạnh | TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIÊN TOÁN ỨNG DỤNG VÀ TIN HỌC THUẬT TOÁN GOMORY TỐI ƯU Tổ HỢP I Chuyên ngành TOÁN TIN ỨNG DỤNG Thầy hướng dẫn TS. NGUYEN QUANG THUẬN Sinh viên thực hiện GIÁP VĂN HIỆP Lớp TOÁN TIN 2 - K54 HÀ NỘI - 2012 Tối ưu tố hợp I Giáp Văn Hiệp Mục lục 1 Lời nói đầu 3 2 Nhắc lại một số kiến thức trong quy hoạch tuyến tính 4 Điều kiện tối ưu. 4 Thuật toán đơn hình giải bài toán quy hoạch tuyến tính chính tắc. 5 Bảng đơn hình . 6 Thuật toán đơn hình dạng bảng. 7 Thuật toán đơn hình hai pha . 8 3 Thuật toán Gomory 8 Bài toán quy hoạch nguyên . 8 Ý tưởng của thuật toán Gomory. 9 Áp dụng thuật toán Gomory để giải bài toán quy hoạch tuyến tính nguyên . 13 Thuật toán Gomory . 14 Ví dụ . 15 Cài đạt. 18 4 Kết luận 25 5 Tài liệu tham khảo 26 2 Tối ưu tố hợp I Giáp Văn Hiệp 1 Lời nói đầu Quy hoạch nguyên là mô hình toán học của rất nhiều bài toán nảy sinh trong thực tế như bài toán pha cắt vật liệu bài toán với điều kiện không chia cắt được các bài toán với điều kiện logic. Khác với bài toán quy hoạch tuyến tính thông thường bài toán quy hoạch nguyên rất khỏ giải. Thực tế chưa có một thuật toán nào hữu hiệu để giải tất cả các bài toán quy hoạch nguyên.