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 1.1. 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 A.H và Doig A.G 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 J.D, Murty K.G, Sweeney D.W 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ội dung trích xuất từ tài liệu:
QUY HOẠCH RỜI RẠC - CHƯƠNG 6 Bùi Thế Tâm VI.1 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 1.1. 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 A.H và Doig A.G 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 J.D, Murty K.G, Sweeney D.W 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 ∈ G ( G là tập hữu hạn ) (2) 1.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ố ζ ( G ) hay ζ ( G′ ) sao cho: f ( x ) ≥ ζ ( G ) với ∀x ∈ G ( hay f ( x ) ≥ ζ ( G′ ) với ∀x ∈ 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 G 0 ≡ G . Bằng một cách nào đó G 0 được chia thành một số hữu 11 1 hạn các tập con ( thường là không giao nhau) G1 , G2 ,...., Gr1 . k k k k Bước k ≥ 1 . Có tập G1 , G2 ,...., Grk cần chia nhánh. Ta chọn tập Gϑ ( k ) theo một k k k qui tắc nào đó và chia thành một số hữu hạn các tập con : Gϑ ( k ),1 , Gϑ ( k ),2 ,...., Gϑ ( 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 , Gϑ ( k ),1 , Gϑ ( k ),2 ,...., Gϑ ( k ),s( k ) Ta đánh số lại là G1 +1 , G2 +1 ,...., Grk+1 . k k k1 + 3. Tính lại đánh giá thì min f ( X ) ≥ min f ( X ) . Nếu tập G1 ⊂ G2 X ∈G1 X ∈G2 s sao cho G ' = ∪ Gi′ thì cận của bất ′ ′ ′ Vì vậy khi chia tập G ′ thành G1 , G2 ,...., Gs i =1 kì tập Gi′ đều có ζ ( Gi′ ) ≥ ζ ( 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 đó ζ ( Gi′ ) ζ ( G′ ) . http://www.ebook.edu.vn Bùi Thế Tâm VI.2 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 phương án trong các tập con được chia liên tiếp. Phương pháp này dựa trên đặc thù của mỗi bài toán cụ thể. Nhờ phương án mới tìm được ở mỗi bước ta có thể cải tiến cận trên (ban đầu gán cho cận trên giá trị là +∞ ) bằng cách gán cho cận trên giá trị hàm mục tiêu tốt nhất tại thời điểm đó. s 5. Tiêu chuẩn tối ưu. Giả sử G = ∪ Gi và phương án X ∈ Gϑ thỏa mãn điều i =1 () f X = ζ ( Gϑ ) ≤ ζ ( Gi ) , ∀ i = 1,.., s thì X là phương án tối ưu của bài toán kiện: (1)-(2). Qui tắc này được ứng dụng ở giai đoạn chia nhánh . 6. Đánh giá độ chính xác của lời giải xấp xỉ. Giả sử s ζ = min ζ ( Gi ) . G = ∪ Gi , i =1,.., s i =1 () Nếu X là một phương án của bài toán xuất phát thì ζ ≤ min f ( X ) ≤ f X . Nếu x∈G () f X − ζ đủ nhỏ thì X có thể lấy làm lời gi ...