Tài liệu Luận văn thạc sĩ phương pháp nhánh và cận trong tối ưu rời rạc

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC CAO TRẦN DŨNG PHƯƠNG PHÁP NHÁNH VÀ CẬN TRONG TỐI ƯU RỜI RẠC LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC CAO TRẦN DŨNG PHƯƠNG PHÁP NHÁNH VÀ CẬN TRONG TỐI ƯU RỜI RẠC Chuyên ngành: TOÁN ỨNG DỤNG Mã số : 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. TRẦN VŨ THIỆU Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LỜI NÓI ĐẦU 1 2 3 i 1 PHƯƠNG PHÁP NHÁNH VÀ CẬN TRONG TỐI ƯU RỜI RẠC 4 1.1 Bài toán quy hoạch nguyên tuyến tính . . . . . . . . . . . . 4 1.2 Sơ đồ tổng quát của phương pháp nhánh cận . . . . . . . . 10 1.3 Thuật toán Land-Doig giải quy hoạch nguyên tuyến tính . . 14 BÀI TOÁN CÁI TÚI 23 2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Thuật toán nhánh và cận 2.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 30 . . . . . . . . . . . . . . . . . . 26 BÀI TOÁN NGƯỜI DU LỊCH 33 3.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Thuật toán nhánh và cận . . . . . . . . . . . . . . . . . . . 35 3.3 3.2.1 Thủ tục tính cận . . . . . . . . . . . . . . . . . . . 36 3.2.2 Thủ tục phân nhánh . . . . . . . . . . . . . . . . . 38 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 41 Kết luận 48 Tài liệu tham khảo 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI NÓI ĐẦU Tối ưu rời rạc (Discrete Optimization), còn gọi là tối ưu tổ hợp (Combinatorial Optimization), đề cập tới các bài toán tối ưu trong đó một phần hay toàn bộ biến nhận các giá trị nguyên hay rời rạc (không liên tục). Các bài toán tối ưu rời rạc đã và đang được quan tâm nghiên cứu cả về lý thuyết lẫn phương pháp giải, vì chúng có những ứng dụng đa dạng, phong phú trong thực tiễn và nhiều vấn đề lý thuyết cũng như thực tiễn có thể diễn đạt dưới dạng một bài toán tối ưu rời rạc. Một lớp bài toán tối ưu rời rạc đáng chú ý là bài toán tối ưu với các biến số chỉ nhận hai giá trị 0 hoặc 1, gọi là qui hoạch 0 - 1 hay qui hoạch biến Boole. Nhiều bài toán điển hình của tối ưu rời rạc được phát biểu dưới dạng bài toán qui hoạch 0 - 1, như bài toán phân việc, bài toán cái túi, bài toán người du lich, bài toán phân hoạch tập, phủ tập, sắp xếp tập, bài toán cây Steiner trên đồ thị, ... . Hơn nữa về nguyên tắc, mọi bài toán với biến số nguyên hay rời rạc bị chặn đều có thể đưa được về bài toán qui hoạch 0 - 1. Có nhiều phương pháp giải bài toán tối ưu rời rạc, trong đó đáng chú ý và có hiệu quả hơn cả là các phương pháp nhánh cận, đặc biệt đối với một số bài toán điển hình của tối ưu rời rạc: bài toán qui hoạch 0 - 1, bài toán cái túi, bài toán người du lịch. Cho đến nay phương pháp nhánh cận với nhiều cải tiến khác nhau vẫn là công cụ chủ yếu để giải các bài toán tối ưu rời rạc. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Mục tiêu của luận văn này là tìm hiểu và trình bày lược đồ tổng quát của phương pháp nhánh cận trong tối ưu rời rạc và áp dụng lược đồ đó vào giải một số bài toán tối ưu rời rạc điển hình nói trên. Nội dung đề cập tới trong luận văn được trình bày một cách chặt chẽ về mặt toán học, các thuật toán giải nêu ra đều có kèm theo ví dụ số minh hoạ. Việc tìm hiểu phương pháp nhánh cận trong tối ưu rời rạc sẽ giúp ích cho việc đi sâu tìm hiểu sau này về nội dung và phương pháp giải các bài toán của tối ưu rời rạc nói chung và những ứng dụng của chúng nói riêng. Nội dung luận văn được chia thành ba chương. Chương 1 với tiêu đề "Phương pháp nhánh cận trong tối ưu rời rạc" giới thiệu về bài toán qui hoạch nguyên tuyến tính và bài toán qui hoạch tuyến tính 0 - 1 như trường hợp riêng quan trọng. Tiếp đó trình bày lược đồ tổng quát của phương pháp nhánh cận và áp dụng lược đồ đó vào bài toán qui hoạch nguyên tuyến tính. Chương 2 với tiêu đề "Bài toán cái túi" trình bày nội dung và ý nghĩa thực tiễn của bài toán cái túi. Đó là bài toán qui hoạch tuyến tính 0 - 1 với một ràng buộc chính duy nhất, dạng đẳng thức hay bất đẳng thức tuyến tính. Bài toán này tuy đơn giản, nhưng lại là bài toán điển hình trong tối ưu rời rạc. Phương pháp nhánh cận là phương pháp thích hợp nhất để giải bài toán nầy. Thuật toán nhánh cận trình bày ở chương này khá độc đáo. Cách tính cận chỉ dựa trên việc giải bài toán qui hoạch tuyến tính đơn giản. Chương 3 với tiêu đề "Bài toán người du lịch" trình bày nội dung và ý nghĩa của bài toán người du lịch. Đó là một bài toán rất quen thuộc và có tầm quan trọng đặc biệt trong tối ưu rời rạc, vì nó là mô hình toán học cho nhiều vấn đề thực tiễn khác nhau và là một trong những bài toán khó, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 hiện vẫn được nhiều người quan tâm nghiên cứu. Thuật toán nhánh cận đầu tiên của Little, Murty, Sweeney và Karel được giới thiệu ở chương này có nhiều ý tưởng độc đáo, đặc biệt trong cách phân nhánh và cách tính cận. Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập tới những nội dung cơ bản của phương pháp nhánh và cận trong tối ưu rời rạc, chưa đi sâu vào các chi tiết thực thi thuật toán. Trong quá trình viết luận văn cũng như trong xử lý văn bản chắc chắn không tránh khỏi những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng dấn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn Tác giả xin trân trọng cảm ơn các thầy, cô giáo Trường Đại học Khoa học- Đại học Thái Nguyên, Viện Toán học-Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Tác giả cũng xin chân thành cảm ơn Ban giám hiệu, tổ toán –tin Trường THPT Số 1 TP Lào Cai và tập thể bạn bè đồng nghiệp cùng gia đình đã quan tâm giúp đỡ, động viên tác giả hoàn thành tốt luận văn này. Thái Nguyên, tháng 07 năm 2012. Người thực hiện Cao Trần Dũng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chương 1 PHƯƠNG PHÁP NHÁNH VÀ CẬN TRONG TỐI ƯU RỜI RẠC Chương này giới thiệu về bài toán qui hoạch nguyên tuyến tính và lược đồ tổng quát của phương pháp nhánh cận trong tối ưu rời rạc. Cuối chương, áp dụng lược đồ nhánh cận vào bài toán qui hoạch nguyên tuyến tính. Nội dung của chương dựa chủ yếu trên các tài liệu [1], [4] và [6]. 1.1 Bài toán quy hoạch nguyên tuyến tính Qui hoạch nguyên tuyến tính (Integer Linear Programming Problem, viết tắt ILP) là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính trên một tập hợp điểm rời rạc, thường là tập điểm nguyên:  (ILP) min f (x) = cT x : Ax = b, xj ≥ 0 nguyên, j = 1, ..., n , trong đó A ∈ Rm.n , b ∈ Rm và c ∈ Rn cho trước. Khi chỉ có một số, chứ không phải tất cả, các biến là nguyên thì ta gọi đó là bài toán qui hoạch nguyên hỗn hợp (Mixed Integer Programming Problem, viết tắt MIP). Cũng như trong qui hoạch tuyến tính, f được gọi là hàm mục tiêu, tập  D = x ∈ Rn : Ax = b, xj ≥ 0 nguyên, j = 1, ..., n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 gọi là miền ràng buộc hay miền chấp nhận được. Điểm x ∈ D gọi là một nghiệm chấp nhận được hay một phương án của bài toán. Một phương án đạt cực tiểu (hay cực đại) của hàm mục tiêu gọi là một nghiệm tối ưu hay một phương án tối ưu. Nghiên cứu cấu trúc tập ràng buộc D và xây dựng các thuật toán tìm nghiệm tối ưu của bài toán ILP là đối tượng của qui hoạch nguyên tuyến tính. Sau đây là hai ví dụ đơn giản về bài toán qui hoạch nguyên tuyến tính. Ví dụ 1.1. Giả sử ta cần đưa qua sông 3 kiện hàng với trọng lượng lần lượt là 3 tạ, 2 tạ và 4 tạ và trị giá mỗi kiện hàng tương ứng là 1, 2 và 3 triệu đồng. Nhưng chỉ có một chiếc thuyền nhỏ, mỗi chuyến chở được tối đa 5 tạ. Hỏi nên xếp lên thuyền những kiện hàng nào để số hàng chuyển được có trị giá lớn nhất? Bằng cách đưa vào các biến số:  1 nếu chọn kiện j xj = , j = 1, 2, 3, 0 nếu ngược lại ta có thể diễn đạt vấn đề nêu trên như một qui hoạch nguyên ILP như sau: ( x1 + 2x2 + 3x3 → max 3x1 + 2x2 + 4x3 ≤ 5 0 ≤ xj ≤ 1, nguyên, j = 1, 2, 3. Nếu đòi hỏi rằng các kiện hàng 1 và 2 không được xếp cùng nhau trên thuyền thì phải đặt bài toán như thế nào? Trả lời: thêm vào bài toán trên bất đẳng thức: x1 + x2 ≤ 1 (Vì thế, nếu x1 = 1 thì x2 = 0, còn nếu x2 = 1 thì x1 = 0). Nếu đòi hỏi rằng chỉ một trong 3 kiện hàng được xếp lên thuyền thì mô Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 hình bài toán ra sao? Trả lời: thêm vào mô hình ban đầu đẳng thức: x1 + x2 + x3 = 1 (Vì thế, hoặc x1 = 1, x2 = x3 = 0 hoặc x2 = 1, x1 = x3 = 0 hoặc x3 = 1, x1 = x2 = 0). Như vậy ta đã thấy qui hoạch nguyên ILP rất tiện dùng để mô hình hoá các ràng buộc lôgic (chẳng hạn, nếu sự kiện A xảy ra thì sự kiện B không xảy ra, ...). Ví dụ 1.2. Một hãng hàng không dự định mua một số máy bay Airbus A-3200 và Boing 777 để mở rộng hoạt động. Mỗi máy bay Airbus giá 5 triệu đô và có thời gian sử dụng 6 năm, mỗi máy bay Boing giá 9 triệu đô và có thời gian sử dụng 8 năm (các con số có tính ước lệ). Hãng ước tính chỉ cần mua tối đa 6 máy bay và số tiền để mua máy bay không quá 46 triệu đô. Hỏi hãng nên mua bao nhiêu máy bay mỗi loại để tổng thời gian phục vụ của chúng được lâu nhất? Bằng cách đưa vào hai biến: x1 là số máy bay Airbus cần mua và x2 là số máy bay Boing cần mua, ta có thể diễn đạt vấn đề này như một bài toán nguyên tuyến tính ILP sau (Đáp số: 2 Airbus và 4 Boing, fmax = 44 năm):  6x1 + 8x2 → max        x1 + x2 ≤ 6  5x1 + 9x2 ≤ 46       x1 , x2 ≥ 0, nguyên Một lớp qui hoạch nguyên quan trọng là bài toán qui hoạch tuyến tính 0 - 1. Đó là bài toán qui hoạch tuyến tính, trong đó mọi biến chỉ lấy giá trị 0 hay 1. Bài toán này còn được biết với tên gọi bài toán nhị nguyên tuyến tính hay bài toán qui hoạch tuyến tính biến Boole. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 . Nhiều bài toán tối ưu rời rạc có thể diễn đạt dưới dạng một qui hoạch tuyến tính 0 - 1. Chẳng hạn: bài toán phân việc, bài toán cái túi, bài toán người du lịch, bài toán phân hoạch tập, phủ tập, sắp xếp tập, bài toán cây Steiner trên đồ thị ... Một số ứng dụng trong công nghiệp như định vị tiện ích (facility location), bài toán với phụ phí cố định, bài toán xếp lịch, thiết kế mạng ... được diễn đạt và giải bằng kỹ thuật qui hoạch tuyến tính 0 1. Qui hoạch tuyến tính 0 - 1 có nhiều ứng dụng trong thực tiễn, đặc biệt trong lập kế hoạch triến khai các dự án với hạn chế về các nguồn lực (vốn, lao động, vật tư, v.v ...). Để minh hoạ ta nêu đại diện mô hình bài toán “cái túi” nhiều chiều: x0 = c1 x1 + c2 x2 + ... + cn xn → max (MKP) với các điều kiện: ( ai1 x1 + ai2 x2 + ... + ain xn ≤ bi , i = 1, 2, ..., m xj ∈ {0, 1} , j = 1, 2, ..., n, trong đó aij , bi , cj ∈ Z (i = 1, 2, . . . , m; j = 1, 2, . . . , n) là những số cho trước và xj (j = 1, 2, . . . , n) là biến nhị nguyên (biến 0 - 1). Trong mô hình trên aij biểu thị lượng tài nguyên i cần dùng để thực hiện dự án j, bi biểu thị lượng tài nguyên i có thể sử dụng và cj biểu thị lợi ích thu được khi thực hiện dự án j. Biến quyết định xj = 1 nếu dự án j được chọn thực hiện và xj = 0 nếu trái lại. Qui hoạch tuyến tính 0 - 1 còn được chú ý là vì về nguyên tắc, mọi bài toán với biến nguyên hay rời rạc bị chặn đều có thể đưa được về bài toán Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 với biến 0 - 1. Sau đây nêu một vài cách biến đổi đáng chú ý. • Đưa biến nguyên về biến 0 - 1 Cho một bài toán tối ưu rời rạc, ta có thể diễn đạt nó theo nhiều mô hình toán học khác nhau. Về mặt tính toán, một cách diễn đạt 0 - 1 tốt là rất quan trọng. Nếu giả thiết các biến nguyên trong bài toán là bị chặn thì có thể đưa bài toán đó về một qui hoạch 0 - 1. Nhưng cách đưa thế nào cho khéo mới là quan trọng. Để thấy rõ vấn đề này, ta hãy lấy ví dụ về bài toán cái túi: (KP) với các điều kiện x0 = 16x1 + 24x2 + 7x3 + 2x4 → max  4x1 + 7x2 + 3x3 + x4 ≤ 27     xj ≥ 0, j = 1, 2, 3, 4     x nguyên, j = 1, 2, 3, 4. j Các biến x1 , x2 , x3 , x4 trong bài toán là không âm và nguyên. Ràng buộc của bài toán cho thấy 0 ≤ x1 ≤ 6, 0 ≤ x2 ≤ 3, 0 ≤ x3 ≤ 9, 0 ≤ x4 ≤ 27. Có một cách đơn giản để thực hiện phép đổi biến số là đặt P6 x1 = i=1 λi , λi ∈ {0, 1} , i = 1, ..., 6, tức là x1 trong bài toán đã xét được thay bởi X6 i=1 λi , λi ∈ {0, 1} , i = 1, ..., 6. Áp dụng ý tưởng này cho các biến x2 , x3 , x4 còn lại ta nhận được 6 + 3 + 9 + 27 = 45 biến nhị nguyên trong bài toán cái túi 0 - 1 tương đương. Cách biểu diễn này chưa phải là tối ưu. Thật vậy, giả sử x ∈ Z+ , p ∈ Z+ và 0 ≤ x ≤ p . Ý tưởng tốt hơn là tìm q ∈ Z+ sao cho 2q ≤ p < 2q+1 và đặt x= q X 2i−1 λi + [p − (2q − 1)]λq+1 , λi ∈ {0, 1} , i = 1, 2, ..., q + 1 i=1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Đối với bài toán cái túi đã xét ta có thể viết x1 = λ1 + 2λ2 + 3λ3 (q = 2) x2 = λ4 + 2λ5 (q = 1) x3 = λ6 + 2λ7 + 4λ8 + 2λ9 (q = 3) x4 = λ10 + 2λ11 + 4λ12 + 8λ13 + 12λ14 (q = 4) λi ∈ {0, 1} , i = 1, 2, ..., 14. Kết quả là trong bài toán cái túi 0 - 1 tương đương chỉ gồm 14 biến nhị nguyên (thay cho 45 biến lúc đầu). Cụ thể là bài toán: (KP) x0 = 16λ1 + 32λ2 + 48λ3 + 24λ4 + 48λ5 + 7λ6 + 14λ7 + 28λ8 + 14λ9 + 2λ10 + 4λ11 + 8λ12 + 16λ13 + 24λ14 → max với các điều kiện: 4λ1 + 8λ2 + 12λ3 + 7λ4 + 14λ5 + 3λ6 + 6λ7 + 12λ8 + 6λ9 + λ10 + 2λ11 + 4λ12 + 8λ13 + 12λ14 ≤ 27 λi ∈ {0, 1} , i = 1, 2, ..., 14. • Đưa biến rời rạc về biến 0 – 1 Trong một số ứng dụng, biến x có thể lấy giá trị rời rạc hay liên tục. Chẳng hạn, x ∈ X = {2} ∪ [5; 7] ∪ {10} ∪ [15; +∞) . Giả sử x có cận trên M. Khi đó ta có thể viết x như là hàm của các biến nhị nguyên :λ1 , λ2 , λ3 , λ4 ( 2λ1 + 5λ2 + 10λ3 + 15λ4 ≤ x ≤ 2λ1 + 7λ2 + 10λ3 + M λ4 λ1 + λ2 + λ3 + λ4 = 1, λj ∈ {0; 1} , j = 1, 2, 3, 4. Nếu λ1 = 1 thì 2 ≤ x ≤ 2, nếu λ2 = 1 thì 5 ≤ x ≤ 7, nếu λ3 = 1 thì 10 ≤ x ≤ 10, nếu λ4 = 1 thì 15 ≤ x ≤ M Cách biểu diễn dùng biến nhị nguyên đôi khi là công cụ hữu ích cho bài toán tối ưu rời rạc. Nhờ dùng biến nhị nguyên, ta có thể diễn đạt được Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 rất nhiều bài toán tối ưu, nhưng ta không đảm bảo được rằng có thể giải được hết các bài toán đó trong thời gian hợp lý, bởi lẽ số các nghiệm nhị nguyên chấp nhận được và không chấp nhận được là cực kỳ lớn. Giả sử có 100 biến nhị nguyên trong bài toán thì số nghiệm nhị nguyên cần xem xét có thể lên tới cỡ 2100 . Ta hãy thử hình dung lượng thời gian một máy tính cỡ lớn cần dùng để kiểm tra tính chấp nhận được của 2100 nghiệm 0 - 1 trong bài toán này nhiều như thế nào. Mặc dầu vậy trên thực tế, người ta vẫn có thể giải trôi chảy các bài toán qui hoạch tuyến tính 0 -1 cỡ lớn, nhờ dùng lược đồ nhánh cận cài đặt trên phần mềm thương mại giải qui hoạch nguyên hỗn hợp (chẳng hạn, người ta đã giải được bài toán thiết kế mạng với 150.000 biến, trong đó 2.000 biến 0 - 1 và 45.000 ràng buộc). 1.2 Sơ đồ tổng quát của phương pháp nhánh cận Xét bài toán tối ưu rời rạc tổng quát : min {f (x) : x ∈ D} (1.1) trong đó f : Rn → R, và D ⊂ Rn là một tập gồm hữu hạn phần tử. Bởi vì D là tập hữu hạn nên bài toán (1.1) luôn có phương án tối ưu ký hiệu là x∗ Xét hàm số γ : 2D \φ → R thỏa mãn hai điều kiện i) γ(A) ≤ min {f (x) : x ∈ A} ii) γ(A1 ) ≥ γ(A2 ), nếu A1 ⊂ A2 ⊂ D Định nghĩa 1.1. Giá trị γ(A) trên tập A⊂D được gọi là cận dưới của tập A. Việc lựa chon γ(A) phụ thuộc vào từng bài toán cụ thể. Thông thường ta chọn γ(A) sao cho việc tính toán γ(A) dễ hơn giải bài toán min {f (x) : x ∈ A} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 và sao cho γ(A) gần với giá trị tối ưu của bài toán này. Trong nhiều trường hợp hai yêu cầu này đối lập nhau. Ta phân hoạch D thành các tập con (1) (1) (1) D1 , D2 , ..., Dn1 : (1) (1) (1) 1 D = ∪ni=1 Di , Di ∩ Dj = φ nếu i 6= j (1.2) Từ (i) và (ii) ta có: n o (1) f (x ) = min {f (x) : x ∈ D} ≥ min γ(Di ) : 1 ≤ i ≤ n1 = γ(Di10 ) ∗ (1.3) Giả sử x là phương án chấp nhận được bất kì, x* là phương án tối ưu. Khi đó (1) f (x) − f (x∗ ) ≤ f (x) − γ(Di0 ) = ε(x) (1.4) với số ε0 cho trước, nếu: ε(x) ≤ ε0 (1.5) Thì x có thể coi là lời giải gần đúng. Định nghĩa 1.2. Phương án chấp nhận được x ∈ D thỏa mãn − f (x) − f (x∗ ) ≤ ε được gọi là phương án ε -tối ưu của bài toán. Nếu ta tìm được x ∈ D sao cho: (1) f (x) = γ(Di0 ) (1.6) thì từ (1.4) suy ra: (1) f (x) = γ(Di0 ) tức là x là phương án tối ưu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 (1) (1) Tập Di0 là có triển vọng chứa phương án tối ưu hơn các tập Di (i 6= i0 ) của phân hoạch (1.2). Nếu không có thông tin nào khác về phương án tối ưu của bài toán (1.1) thì điều kiện:  (1) γ(Di0 ) = min γ(Di1 ) : 1 ≤ i ≤ n1 (1) (1.7) (1) (1) sẽ được nhận làm quy tắc chọn tập Di0 trong các tập D1 , ..., Dn1 của phân hoạch (1.2) để điểm diện trước. (1) Giả sử có thể phân hoạch tập Di0 thành các tập con (1) l(i ) (2) (2) (2) Di0 = ∪i=10 Di , Dk ∩ Dl = φ khi k 6= l Khi đó ta có một phân hoạch mới của D: (1) (1) (1) (2) 2 D1 , ..., Di0 −1 , Di0 +1 , ..., Dn(1)1 , D1 , ..., Dl(i 0) Sau khi thay đổi kí hiệu ta có: n2 (2) D = ∪ Di i=1 (2) Theo tiêu chuẩn (1.7), trong phân hoạch mới ta lại tìm ra tập Di0 có chứa cận dưới nhỏ nhất. Nếu tiêu chuẩn (1.5) hay (1.6) chưa được thỏa (2) mãn, thì ta lại có thể tiếp tục quá trình với tập Di0 Tóm lại ta có lược đồ sau đây: Sơ đồ thuật toán nhánh cận (0) a) Bước chuẩn bị: Đặt D1 = D, n0 = 1. Chọn ε0 là độ chính xác của lời giải cần tìm b) Bước k = 0,1,2. . . : Giả sử ở bước lặp này ta đã có phân hoạch nk (k) D = ∪ Di i=1 o n (k) (k) Tìm γ(Di0 ) = min γ(Di ) : 1 ≤ i ≤ nk Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 Nếu ta tìm được x ∈ D thỏa mãn: (k) εk (x) = f (x) − γ(Di0 ) ≤ ε0 thì x là phương án ε0 tối ưu, thuật toán kết thúc. (k) Ngược lại, ta tiến hành phân hoạch tậpDi0 và thu được phân hoạch của tập D cho bước k+1. Bởi vì tập D là hữu hạn và   n o n o  (k)   (k+1)  min Di  : 1 ≤ i ≤ nk ≥ min Di  : 1 ≤ i ≤ nk+1 . Cho nên với k đủ lớn, ta sẽ thu được phân hoạch tập D thành các tập con chỉ gồm một phần tử. Do đó, ta suy ra tính hữu hạn của thuật toán này. (k) Chú ý rằng trong quá trình phân hoạch các tập Di0 ta có thể tìm được − các phương án chấp nhận được của bài toán. Kí hiệu x là phương án chấp nhận được có giá trị hàm mục tiêu là nhỏ nhất trong số các phương án − chấp nhận được tìm được. Ta sẽ gọi x là lời giải tốt nhất hiện có, hay gọi − − tắt là kỉ lục, còn giá trị f = f (x) được gọi là giá trị kỉ lục. − Giả sử ở bước k ta đã có kỉ lục x . Khi đó, ta có thể loại khỏi quá trình (k) duyệt tất cả các tập con Di có giá trị cận dưới lớn hơn hoặc bằng giá trị kỉ lục. Khi áp dụng sơ đồ trên cho một bài toán tối ưu rời rạc cụ thể, ta cần phải xây dựng được hai thủ tục chính sau: (k) 1) Thủ tục phân hoạch tập Di0 ra thành các tập con (còn gọi là thủ tục phân nhánh) 2) Thủ tục tính cận dưới γ(A). Do vậy, từ sơ đồ tổng quát trên ta có thể thu được các thuật toán khác nhau vơi hiệu quả khác nhau để giải bài toán đặt ra. Sau đây ta sẽ trình bày một áp dụng của lược đồ trên vào việc giải bài toán quy hoạch nguyên tuyến tính. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 1.3 Thuật toán Land-Doig giải quy hoạch nguyên tuyến tính Xét bài toán quy hoạch nguyên tuyến tính sau đây  Pn  j=1 cj xj → min,     P    nj=1 aij xj ≤ bi , (i = 1, ..., m) (1.8)   xj ≥ 0, (j = 1, ..., n)       xj − nguyên(j = 1, ..., n) Ký hiệu: x = (x1 , ..., xn )T , c = (c1 , ..., cn )T , b = (b1 , ..., bm )T , A = (aij ) (với T là ký hiệu chuyển vị véc tơ hay ma trận). Khi đó bài toán trên được viết dưới dạng ma trận như sau:   cT x → min, Ax ≤ b  x ≥ 0, nguyên (1.9) Để áp dụng lược đồ tổng quát trong mục trước, ta xác định hai thủ tục chính là phân nhánh và tính cận. Ta xét cách xây dựng hai thủ tục này của Land-Doig. Đặt  D = x : Ax ≤ b, x ≥ 0, nguyên Ta có D là miền chấp nhận được của bài toán (1.9). Ta sẽ ký hiệu P0 là bài toán (1.9) Giải bài toán quy hoạch tuyến tính tương ứng với P0 ta sẽ thu được phương án tối ưu x0 , x0 nói chung không nguyên. Ta có f (x0 ) = min {f (x) : Ax ≤ b, x ≥ 0} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15  ≤ min f (x) : Ax ≤ b, x ≥ 0, nguyên = f∗ Vì thế giá trị f (x0 ) có thể dùng làm cận dưới cho giá trị tối ưu f∗ của bài toán P0 Như vậy ta đã có thủ tục để tính cận dưới: đặt giá trị cận dưới của bài toán qui hoạch nguyên tuyến tính bằng giá trị tối ưu của bài toán quy hoạch tuyến tính tương ứng với nó: γ(D) = min {f (x) : Ax ≤ b, x ≥ 0} . Ta phân chia tập chấp nhận được của bài toán P0 thành hai tập bằng cách đưa vào hai ràng buộc loại trừ lẫn nhau như sau: Giả sử x0i (1 ≤ i ≤ n) là một thành phần không nguyên nào đó của x0 . Ký hiệu:    D1 = x ∈ D : xi ≤ x0i    D2 = x ∈ D : xi ≥ x0i + 1 , (1.10) (1.11)   trong đó x0i là phần nguyên của x0i Khi đó D = D1 ∪ D2 , D1 ∩ D2 = φ. (1.12) Như vậy, ta đã xác định được thủ tục phân hoạch theo các công thức (1.10) - (1.12). Gọi P1 là bài toán min {f (x) : x ∈ D1 } . Gọi P2 là bài toán min {f (x) : x ∈ D2 } . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Rõ ràng đây là các bài toán quy hoạch nguyên tuyến tính. Khi giải các bài toán quy hoạch tuyến tính tương ứng với các bài toán Pi (i = 1, 2), để tính cận dưới cho các tập Di , ta có thể gặp một trong các tình huống sau đây: 1) Bài toán không có phương án chấp nhận được. 2) Tìm được phương án tối ưu xi nguyên. 3) Tìm được phương án tối ưu xi không nguyên. Trường hợp 1): Bài toán Pi cũng không có phương án chấp nhận được, tức là Di = φ. Khi đó, ta có thể loại bỏ tập Di khỏi quá trình xét tiếp theo. Trường hợp 2): xi cũng là phương án của bài toán Pi . Vì vậy xi là phương án chấp nhận được của bài toán xuất phát. Trong trường hợp này, ta có thể cải thiện được kỷ lục, còn tập Di cũng sẽ bị loại bỏ không cần xét tiếp. Trường hợp 3) Ta thu được cận dưới của tập Di là γ(Di ) = f (xi ). Tập Di cần được xem xét tiếp: Ta có thể mô tả thuật toán Land-Doig để giải bài toán quy hoạch nguyên tuyến tính (1.9) như sau: Thuật toán Land-Doig Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 Bước chuẩn bị: Giải bài toán quy hoạch tuyến tính tương ứng với P0 và thu được phương án tối ưu x0 . Giả sử x0 là không nguyên. Đặt cận dưới của P0 là f (x0 ) và danh mục các bài toán cần xét là P = {P0 }. Nếu biết x là phương án chấp nhận được của bài toán thì đặt f = f (x) và ngược lại, ta đặt f = ∞. Bước lặp k = 1,2,. . . 1) Nếu P = φ thuật toán kết thúc. Khi đó, nếu f < ∞ thì f là giá trị tối ưu và x là phương án tối ưu của bài toán. Trong trường hợp ngược lại, bài toán không có phương án chấp nhận được. 2) Nếu P 6= φ : Chon Pk là bài toán có cận dưới nhỏ nhất trong P. Gọi Dk là miền chấp nhận được, xk là phương án tối ưu của bài toán quy hoach tuyến tính tương ứng với nó. 2.1. Giả sử xkt là một thành phần không nguyên nào đó của xk . Phân hoạch tập Dk thành hai tập:    Dk1 = x ∈ Dk : xt ≤ xkt ,    Dk2 = x ∈ Dk : xt ≥ xkt + 1 . Gọi Pk1 là bài toán: min {f (x) : x ∈ Dk1 } và Pk2 là bài toán: min {f (x) : x ∈ Dk2 } . Đây là các bài toán quy hoạch nguyên tuyến tính. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn