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.
Nội dung trích xuất từ tài liệu:
Tiểu luận: Thuật toán nhánh cận 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 PI 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 cl 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 2.1 Phân ho ch . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Bài toán con . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 C n dư i - c n trên . . . . . . . . . . . . . . . . . . . . . 4 2.4 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính 5 2.5 Bài toán quy ho ch nguyên . . . . . . . . . . . . . . . . 6 3 Thu t toán nhánh c n 7 3.1 Ý tư ng c a thu t toán nhánh c n . . . . . . . . . . . . 7 3.2 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 3.3 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. 3 T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 2 M t s khái ni m cơ b n và ki n th c b tr 2.1 Phân ho ch M t h P ch a h u h n các t p con c a t p D, P := {Di ⊆ D | i ∈ I}, trong đó I là t p h u h n các ch s , đư c g i là m t phân ho ch c a D n u D= Di và Di ∩ Dj = ∅ i = j. i∈I Nói r ng ta phân ho ch t p D b i các t p con Di , i ∈ I có nghĩa là ta có {Di ⊆ D | i ∈ I} là m t phân ho ch c a D. 2.2 Bài toán con Xét bài toán quy ho ch nguyên sau: maxf (x) v.đ.k. x∈D (IP ) trong đó D là t p ch p nh n đư c. Bài toán maxf (x) v.đ.k. x ∈ Di (IPi ) đư c g i là bài toán con c a bài toán quy ho ch nguyên (IP ) (cùng hàm m c tiêu nhưng t p ch p nh n đư c bé hơn ). 2.3 C n dư i - c n trên • S th c α đư c g i là c n dư i c a bài toán (IP ) n u α ≤ fopt . N u tìm đư c phương án ch p nh n đư c x ∈ D thì f (x) ≤ fopt . Khi đó x đư c g i là k l c và f (x) đư c g i là m t giá tr k l c. • S th c β đư c g i là c n dư i c a bài toán (IP ) n u β ≥ fopt . N u tìm đư c phương án ch p nh n đư c x ∈ D và m t c n trên β c a bài toán (IP ) sao cho f (x) = β thì x chính là nghi m t i ưu c a bài toán. 4 T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 2.4 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính Xét bài toán quy ho ch tuy n tính chính t c không suy bi n f (x) = cT x → min (LP ) v.đ.k. x ∈ D, n trong đó c ∈ R , và t p ch p nh n đư c là t p l i đa di n không suy bi n xác đ nh b i D = {x ∈ Rn |Ax = b, x ≥ 0}, trong đó b = (b1 , b2 , · · · , bm )T ≥ 0, A là ma tr n c p m × n, v i m < n. Gi s ta đã bi t phương án c c biên x0 = (x0 , x0 , · · · , x0 )T . Ký hi u 1 2 n J(x0 ) := {j ∈ {1, 2, · · · , n}|x0 > 0}. j H các véc tơ đ c l p tuy n tính {Aj |j ∈ J(x0 )} là cơ s duy nh t c a ma tr n A tương ng v i x0 . Vì v y m i véc tơ Ak đư c bi u di n dư i d ng Ak = zjk Aj ...