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 fX = ( ) (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 0 G G≡ . Bằng một cách nào đó 0 G được chia thành một số hữu hạn các tập con ( thường là không giao nhau) 1 11 1 1 2 , ,...., GG Gr . Bước k ≥1. Có tập 1 2 , ,...., k kk k GG Gr cần chia nhánh. Ta chọn tập ( ) k 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 : () () () ,1 ,2 , ( ) , ,...., kk k GG G ϑϑ ϑ k k k sk , gồm có s( ) k tập. Khi đó, tập cần chia nhánh tiếp theo là 12 1 1 , ,...., , ,..., kk k kk k k k GG G G G ϑ ϑ − + r , () () ()() ,1 ,2 , , ,...., kk k GG G ϑϑ ϑ k k k sk Ta đánh số lại là 1 11 1 1 2 , ,...., k kk k GG Gr + ++ + . 3. Tính lại đánh giá Nếu tập G G 1 2 ⊂ thì ( ) ( ) 1 2 min min XG XG f X fX ∈ ∈ ≥ . Vì vậy khi chia tập G′ thành 1 2 , ,...., GG Gs ′ ′ ′ sao cho 1 ' s i i G G = =∪ ′ thì cận của bất kì tập Gi ′ đều có ζ ζ (G Gi s i ′ ′ ) ≥ = ( ), 1,.., ( ). 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 đó ( ) ( ). G G i ζ ζ ′ ; ′ 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 đó. 5. Tiêu chuẩn tối ưu. Giả sử 1 s i i G G = =∪ và phương án X G∈ ϑ thỏa mãn điều kiện: ( ) ( ) ( ), 1,.., i f X G G is ϑ = ≤ ∀= ζ ζ thì X là phương án tối ưu của bài toá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ử ( ) 1,.., 1 , min s i i i s i GG G ζ ζ = = = = ∪ . Nếu X là một phương án của bài toán xuất phát thì min ( ) ( ) x G ζ f X fX ∈ ≤ ≤ . Nếu f X( ) −ζ đủ nhỏ thì X có thể lấy làm lời giải xấp xỉ với đánh giá độ xấp xỉ là ∆= − f X( ) ζ . 1.3. Lược đồ tổng quát của phương pháp nhánh cận. Chia tập phương án G thành cây tập con. Bước 0. Tính ( ) ( ) 0 ζ ζ G G = . Nếu tìm được phương án X sao cho f ( X G ) = ζ ( ) thì X là phương án tối ưu. Ngược lại, chia 0 G = 1 11 1 1 2 .... GG G ∪ ∪∪ r , tức là chia thành các tập con (thường là không giao nhau). Bước k ≥1. Tính các đánh giá ( ), 1,.., k Gi r i k ζ = . Nếu tìm được phương án X , k X G∈ r sao cho ( ) ( ) ( ), k k r i fX G G = ≤ ζ ζ với 1,2,.., k ∀i r = , thì X là phương án tối ưu, quá trình kết thúc. Ngược lại, chọn ( ) k Gϑ k để chia, theo tiêu chuẩn ( ( ) ) ( ) 1,.., min k k k k i i r G G ϑ ζ ζ = = . Ta chia tập ( ) k Gϑ k thành một số tập con () () () ()() ,1 ,2 , .... kk k k GG G G ϑϑ ϑ ϑ k k k k sk = ∪ ∪∪ . Tập cần chia tiếp theo là 12 1 1 , ,...., , ,..., kk k kk k k k GG G G G ϑ ϑ − + r , () () () ,1 ,2 , , ,...., k kk k GG G ϑϑ ϑ k k ks Sau đó ta đánh số lại là 1 11 1 1 2 , ,...., k kk k GG Gr + + + + và sang bước k+1.
