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

Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước, nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó, không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó, chỉ ghi nhận các kết quả tốt hơn lúc ban đầu. | 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 NHÁNH CẬN TỐI ƯU Tổ HỢP I Chuyên ngành TOÁN TIN ỨNG DỤNG Thầy hướng dẫn TS. Nguyễn Quang Thuận Sinh viên thực hiện Vũ Hữu Ninh Lớp Toán Tin 2 - K54 HÀ NỘI - 2012 Tối ưu tố hợp I - Thuật toán nhánh cận Vũ Hữu Ninh Mục lục 1 Lời nói đầu 3 2 Một số khái niệm cơ bản và kiến thức bổ trỢ 4 Phân hoạch. 4 Bài toán con. 4 Cận dưới - cận trên. 4 Thuật toán đơn hình giải bài toán quy hoạch tuyến tính 5 Bài toán quy hoạch nguyên . 6 3 Thuật toán nhánh cận 7 Ý tưởng của thuật toán nhánh cận. 7 Thuật toán nhánh cận Land-Doig giải bài toán quy hoạch nguyên hoàn toàn. 8 Thuật toán nhánh cận giải bài toán cái túi. 14 4 Kết luận 17 5 Tài liệu tham khảo 18 2 Tối ưu tố hợp I - Thuật toán nhánh cận Vũ Hữu Ninh 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 các lĩnh vực khác nhau. Tuy nhiên khác với baiftoans 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 tối ưu nào thực sự hữu hiệu để giải tất cả các bài toán quy hoạch nguyên. Năm 1960 Land và Doig đưa ra thuật toán nhánh cận dể giải bài toán quy hoạch nguyên. Đến năm 1965 Dakin đã hoàn thiện phương pháp nhánh cận và nó trở thành phương pháp ưu thê rõ rệt so với các phương pháp trước để giải bài toán quy hoạch nguyên. Nội dung chính trong báo cáo này của em chủ yếu là nói về thuật toán nhánh cận để giải bài toán quy hoạch nguyên.