tailieunhanh - QUY HOẠCH RỜI RẠC - CHƯƠNG 6

THUẬT TOÁN NHÁNH CẬN 1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN . Trong các phương pháp giải bài toán qui hoạch nguyên, phương pháp nhánh cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land và Doig xây dựng năm 1960 giải bài toán qui hoạch nguyên (trình bày Tiết 2), đến 1963 được Little , Murty , Sweeney và Karen C sử dụng thành công giải bài toán người du lịch (trình bày trong Tiết 3). . | Bùi Thế Tâm Quy hoạch rời rạc Chương 6 THUẬT TOÁN NHÁNH CẬN 1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN . Trong các phương pháp giải bài toán qui hoạch nguyên phương pháp nhánh cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land và Doig xây dựng năm 1960 giải bài toán qui hoạch nguyên trình bày Tiết 2 đến 1963 được Little Murty Sweeney và Karen C sử dụng thành công giải bài toán người du lịch trình bày trong Tiết 3 . Năm 1979 Giáo sư Hoàng Tụy đã ứng dụng thành công phương pháp này vào giải bài toán qui hoạch lõm. Đây là thuật toán ứng dụng rộng rãi để giải các bài toán tối ưu khó. Xét bài toán qui hoạch rời rạc min Z f X 1 X e G G là tập hữu hạn 2 . Tư tưởng của phương pháp nhánh cận gồm các phép xây dựng sau cho phép giảm bớt khối lượng lựa chọn. 1. Tính cận dưới. Tìm cận dưới của hàm mục tiêu f x trên tập các phương án G hoặc trên tập con G nào đó của G tức là số z G hay z G sao cho f x z G với Vx e G hay f x z G với Vx e G . 2. Chia thành các tập con rẽ nhánh . Chia dần dần tập phương án G thành cây các tập con các nhánh . Việc chia nhánh thực hiện theo sơ đồ nhiều bước sau Bước 0. Đặt G0 G. Bằng một cách nào đó G0 được chia thành một số hữu hạn các tập con thường là không giao nhau G 1 g2 . G . Bước k 1. Có tập Gk G2 . Gr cần chia nhánh. Ta chọn tập G k theo một qui tắc nào đó và chia thành một số hữu hạn các tập con Gk k 1 g k 2 . Gk k s k gồm có s k tập. Khi đó tập cần chia nhánh tiếp theo là k k k k k k k k G1 G2 . G k-1 G k 1 . Grk Gs k 1 Gs k 2 . Gs k s k Ta đánh số lại là GỈ 1 G2k 1 . G 1. 3. Tính lại đánh giá Nếu tập G1 c G2 thì min f X min f X . X eG1 7 X G 7 Vì vậy khi chia tập G thành G1 G2 . GS sao cho G uGi thì cận của bất i 1 kì tập G ị đều có Z Gi z G i 1 . s . Trong các tình huống cụ thể ta thường nhận được các đánh giá tốt tức là đối với một i nào đó z Gị z G . Bùi Thế Tâm Quy hoạch rời rạc 4. Tính phương án Đối với các bài toán cụ thể có thể chỉ ra các phương pháp khác nhau để tìm ra các .