Bài giảng Phương pháp nhánh cận giải bài toán quy hoạch nguyên - Nguyễn Hữu Thương

QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN NGUYỄN HỮU THƯƠNG KHOA TOÁN - TIN HỌC, ĐẠI HỌC KHOA HỌC TỰ NHIÊN Giảng viên hướng dẫn: PGS. TS. TRẦN HUỆ NƯƠNG Date 28/07/2009 NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB NỘI DUNG 1 QUY HOẠCH NGUYÊN GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ 2 PHƯƠNG PHÁP NHÁNH CẬN CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN 3 GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Giới thiệu Quy hoạch nguyên (Integer programming - IP) là bài toán quy hoạch trong đó tất cả hoặc một phần các biến bị ràng buộc chỉ lấy giá trị nguyên. Đây là lớp bài toán rất phổ biến trong thực tế. Quy hoạch nguyên có hai dạng: Quy hoạch nguyên hoàn toàn (pure integer programming) và Quy hoạch nguyên bộ phận (mixed integer programming - MIP). Quy hoạch nguyên có rất nhiều dạng mô hình bài toán trong thực tế: The Schwindle Cycle Company, Large Airline Tend, The Travelling Salesperson Problem, The Linear Ordering Problem, The Quadratic Assignment Problem, ... Nhưng ở đây tác giả chỉ xét hai dạng bài toán điển hình của Quy hoạch nguyên: Knapsack Problem và Capital Budgeting Problem. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ (Bài toán Balo - Knapsack Problem) Một nhà thám hiểm chỉ được mang theo một ba lô trọng lương không quá b, Có n loại vật dụng nên mang theo. Loại vật j có trọng lượng mỗi vật là aj và giá trị sử dụng mỗi vật là cj . Hỏi ông phải mang thế nào để có giá trị sử dụng lớn nhất? Gọi xj là số lượng vật j mang theo thì mô hình toán học của bài toán balo này là quy hoạch nguyên sau: max z = n∑ j=1 cjxj , n∑ j=1 ajxj ≤ b, xj ≥ 0 và nguyên, j = 1, . . . , n. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ (Capital Budgeting problem) Giả sử chúng ta ước đầu tư một giá trị tối đa b và có n mục tiêu đầu tư. Đầu tư mục tiêu j yêu cầu aj sẽ có giá trị "present" (giá trị chiết khấu kỳ hạn) là cj . Chúng ta nên đầu tư như thế nào để tổng giá trị "present" đạt maximum. Đây là dạng bài toán đầu tư "có - không" nên ta sẽ đưa về quy hoạch nguyên nhị phân: max z = n∑ j=1 cjxj , n∑ j=1 ajxj ≤ b, xj = { 0 không đầu tư 1 đầu tư xj là nguyên,j = 1, . . . , n. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Quy hoạch nguyên trong thực tế Ý tưởng giải một bài toán nguyên trong thực tế: (i) Giải bài toán tuyến tính gốc (LP) sau khi bỏ đi điều kiện biến nguyên, (ii) Giả sử được nghiệm tối ưu xk = t. Nếu nghiệm tối ưu đạt được thoả ràng buộc nguyên thì kết thúc bước lặp. Ngược lại đến bước 3, (iii) Chia bài toán thành hai phần: LP1: LP thêm điều kiện xk ≤ [t] max z = cx , Ax ≤ b, xk ≤ [t], x ≥ 0. LP2: LP thêm điều kiện xk ≥ [t] + 1 max z = cx , Ax ≤ b, xk ≥ [t] + 1, x ≥ 0. (iv) Giải LP1 và LP2 một cách riêng rẽ, (v) Nếu với bất kỳ bài toán con, nghiệm tối ưu nguyên đạt được thì bài toán không chia nhánh nữa. Mặt khác quay trở lại Bước 3.NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Ta xét và giải bài toán Balo hai biến cụ thể như sau: Một học sinh mang theo balo trọng lượng không quá 12kg, mang theo hai vật, trọng lượng vật một là 3kg, trọng lượng vật hai tương ứng là 2kg, giá trị sử dụng của cả hai vật là 1. Gọi x1, x2 là số lượng vật một và hai mang theo, sao cho vật hai mang không quá hai cái. Hỏi phải mang theo bao nhiêu để giá trị sử dụng lớn nhất? Mô hình bài toán: max z = x1 + x2, 3x1 + 2x2 ≤ 12, x2 ≤ 2, x1, x2 ≥ 0 và nguyên. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Áp dụng ý tưởng trên, ta thực hiện các bước giải cho nghiêm tối ưu của bài toán: x∗ = (4, 0), z∗ = 4 Sơ đồ cây cho quá trình giải bài toán: NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Ta xét bài toán Capital-Budgeting cụ thể như sau: với khoản đầu tư mơ ước tối đa b = 14, 000 USD, có bốn mục tiêu đầu tư, mục tiêu đầu tư một a1 = 5, 000 USD có giá trị c1 = 8, 000 USD, mục tiêu đầu tư hai a2 = 7, 000 USD có giá trị c2 = 11, 000 USD, mục tiêu đầu tư ba a3 = 4, 000 USD có giá trị c1 = 6, 000 USD, mục tiêu đầu tư bốn a4 = 3, 000 USD có giá trị c1 = 4, 000 USD. Hỏi phải đầu tư như thế nào để tổng giá trị "present" đạt max? Mô hình bài toán: max z = 8x1 + 11x2 + 6x3 + 4x4, 5x1 + 7x2 + 4x3 + 3x4 ≤ 14, xj ∈ {0, 1}, j = 1, . . . , 4. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU QUY HOẠCH NGUYÊN TRONG THỰC TẾ Áp dụng ý tưởng trên, ta thực hiện các bước giải cho nghiêm tối ưu của bài toán: x∗ = (0, 1, 1, 1)z∗ = 21 Sơ đồ cây cho quá trình giải bài toán: NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN Chia nhánh - đặt cận - chạm đáy Mọi thuật toán nhánh - và - cận đều gồm ba thủ tục chia nhánh, đặt cận, chạm đáy. Mỗi thủ tục được linh động trong cách thực hiện nên có các dạng thuật toán khác nhau. "Chia nhánh" là chọn một trong các bài toán con còn phải xét để chia tiếp ra. "Chọn" có thể lấy bất kỳ. Một quy tắc phổ biến là chọn trong các bài toán con mới lập. "Chia" có nghĩa phổ biến là lấy một biến chia nhánh xj để chia ra hai bài toán con với ràng buộc thêm xj ≤ [a] và xj ≥ [a] + 1 tương ứng. Với bài toán nhị phân thì hai ràng buộc thêm sẽ là xj = 0 và xj = 1. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN Chia nhánh - đặt cận - chạm đáy Mọi thuật toán nhánh - và - cận đều gồm ba thủ tục chia nhánh, đặt cận, chạm đáy. Mỗi thủ tục được linh động trong cách thực hiện nên có các dạng thuật toán khác nhau. "Chia nhánh" là chọn một trong các bài toán con còn phải xét để chia tiếp ra. "Chọn" có thể lấy bất kỳ. Một quy tắc phổ biến là chọn trong các bài toán con mới lập. "Chia" có nghĩa phổ biến là lấy một biến chia nhánh xj để chia ra hai bài toán con với ràng buộc thêm xj ≤ [a] và xj ≥ [a] + 1 tương ứng. Với bài toán nhị phân thì hai ràng buộc thêm sẽ là xj = 0 và xj = 1. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Đặt cận" thường thực hiện bằng giải bài toán nới lỏng. Như phương pháp trên đây thì phải dùng LP - nới lỏng để đặt cận. Với các thuật toán nhánh - và - cận khác, còn có các kiểu bài toán nới lỏng khác. Chẳng hạn thuật toán nhánh - và - cận cho quy hoạch nhị phân có thể áp dụng Lagrange nới lỏng (Lagrange relaxation). Định nghĩa tổng quát Lagrangian nới lỏng: Giả sử cần xét quy hoạch nguyên max z = cT x , Ax < b, xj ∈ Z+, j = 1, . . . , n. Ở đây x ∈ Rn, A cấp mxn. Lấy một λ ≥ 0, λ ∈ Rm cố định. Khi đó Lagrangian nới lỏng được định nghĩa là bài toán max x≥0 L = cT x − λT (Ax − b). Ta có quan hệ hai mục tiêu tối ưu z∗ ≤ L∗, tức là L∗ là một cận trên (có sát z∗ hay không còn phụ thuộc λ đã chọn) NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Đặt cận" thường thực hiện bằng giải bài toán nới lỏng. Như phương pháp trên đây thì phải dùng LP - nới lỏng để đặt cận. Với các thuật toán nhánh - và - cận khác, còn có các kiểu bài toán nới lỏng khác. Chẳng hạn thuật toán nhánh - và - cận cho quy hoạch nhị phân có thể áp dụng Lagrange nới lỏng (Lagrange relaxation). Định nghĩa tổng quát Lagrangian nới lỏng: Giả sử cần xét quy hoạch nguyên max z = cT x , Ax < b, xj ∈ Z+, j = 1, . . . , n. Ở đây x ∈ Rn, A cấp mxn. Lấy một λ ≥ 0, λ ∈ Rm cố định. Khi đó Lagrangian nới lỏng được định nghĩa là bài toán max x≥0 L = cT x − λT (Ax − b). Ta có quan hệ hai mục tiêu tối ưu z∗ ≤ L∗, tức là L∗ là một cận trên (có sát z∗ hay không còn phụ thuộc λ đã chọn) NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Chạm đáy" có ba tiêu chuẩn như sau (cho bài toán tìm max): (-) Tiêu chuẩn 1: Nếu cận của bài toán con ≤ mục tiêu kỷ lục, hoặc nói chung hơn là nếu mọi mục tiêu chấp nhận được của bài toán con ≤ mục tiêu kỷ lục, thì bài toán này chạm đáy. (-) Tiêu chuẩn 2: Nếu bài toán con không chấp nhận được thì nó chạm đáy. (-) Tiêu chuẩn 3: Nghiệm tối ưu của LP - nới lỏng của bài toán con là nguyên thì nó chạm đáy. Rõ ràng nếu bài toán là tìm min thì ở Tiêu chuẩn 1 chỉ việc đổi dấu thành ≥, còn hai tiêu chuẩn kia giữ nguyên dạng. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Chạm đáy" có ba tiêu chuẩn như sau (cho bài toán tìm max): (-) Tiêu chuẩn 1: Nếu cận của bài toán con ≤ mục tiêu kỷ lục, hoặc nói chung hơn là nếu mọi mục tiêu chấp nhận được của bài toán con ≤ mục tiêu kỷ lục, thì bài toán này chạm đáy. (-) Tiêu chuẩn 2: Nếu bài toán con không chấp nhận được thì nó chạm đáy. (-) Tiêu chuẩn 3: Nghiệm tối ưu của LP - nới lỏng của bài toán con là nguyên thì nó chạm đáy. Rõ ràng nếu bài toán là tìm min thì ở Tiêu chuẩn 1 chỉ việc đổi dấu thành ≥, còn hai tiêu chuẩn kia giữ nguyên dạng. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Chạm đáy" có ba tiêu chuẩn như sau (cho bài toán tìm max): (-) Tiêu chuẩn 1: Nếu cận của bài toán con ≤ mục tiêu kỷ lục, hoặc nói chung hơn là nếu mọi mục tiêu chấp nhận được của bài toán con ≤ mục tiêu kỷ lục, thì bài toán này chạm đáy. (-) Tiêu chuẩn 2: Nếu bài toán con không chấp nhận được thì nó chạm đáy. (-) Tiêu chuẩn 3: Nghiệm tối ưu của LP - nới lỏng của bài toán con là nguyên thì nó chạm đáy. Rõ ràng nếu bài toán là tìm min thì ở Tiêu chuẩn 1 chỉ việc đổi dấu thành ≥, còn hai tiêu chuẩn kia giữ nguyên dạng. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Chạm đáy" có ba tiêu chuẩn như sau (cho bài toán tìm max): (-) Tiêu chuẩn 1: Nếu cận của bài toán con ≤ mục tiêu kỷ lục, hoặc nói chung hơn là nếu mọi mục tiêu chấp nhận được của bài toán con ≤ mục tiêu kỷ lục, thì bài toán này chạm đáy. (-) Tiêu chuẩn 2: Nếu bài toán con không chấp nhận được thì nó chạm đáy. (-) Tiêu chuẩn 3: Nghiệm tối ưu của LP - nới lỏng của bài toán con là nguyên thì nó chạm đáy. Rõ ràng nếu bài toán là tìm min thì ở Tiêu chuẩn 1 chỉ việc đổi dấu thành ≥, còn hai tiêu chuẩn kia giữ nguyên dạng. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN "Chạm đáy" có ba tiêu chuẩn như sau (cho bài toán tìm max): (-) Tiêu chuẩn 1: Nếu cận của bài toán con ≤ mục tiêu kỷ lục, hoặc nói chung hơn là nếu mọi mục tiêu chấp nhận được của bài toán con ≤ mục tiêu kỷ lục, thì bài toán này chạm đáy. (-) Tiêu chuẩn 2: Nếu bài toán con không chấp nhận được thì nó chạm đáy. (-) Tiêu chuẩn 3: Nghiệm tối ưu của LP - nới lỏng của bài toán con là nguyên thì nó chạm đáy. Rõ ràng nếu bài toán là tìm min thì ở Tiêu chuẩn 1 chỉ việc đổi dấu thành ≥, còn hai tiêu chuẩn kia giữ nguyên dạng. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN Thuật toán Xét bài toán quy hoạch nguyên tìm max. Gọi z là cận dưới - kỷ lục. Bước khởi động đặt i = 0 và đặt z = −∞. Ở một bước lập tổng quát có hai đoạn như sau. - Đoạn 1: (Chạm đáy/đặt cận). Chọn LPi là bài toán con sẽ xét. Giải và xét nó có chạm đáy hay không. (a) Nếu LPi chạm đáy theo tiêu chuẩn 3 thì cập nhật z để được cận dưới mới. Trái lại, theo tiêu chuẩn khác, thì chọn bài toán con LPi mới và lặp như trên. Nếu không còn bài toán con chưa xét thì dừng. Nghiệm tối ưu của LP là tương ứng với cận dưới - kỷ lục cuối cùng, nếu có nghiệm như vậy. (b) Nếu LPi không chạm đáy, chuyển sang Đoạn 2 để chia nhánh LPi . - Đoạn 2: (Chia nhánh). Chọn một trong các biến xj mà x ∗ j ở nghiệm tối ưu LPi chưa là số nguyên. Lập hai bài toán con LP - nới lỏng bằng cách thêm ràng buộc tương ứng xj ≤ [x∗j ] và xj ≥ [x∗j ] + 1 Chuyển sang Đoạn 1.NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN Thuật toán Xét bài toán quy hoạch nguyên tìm max. Gọi z là cận dưới - kỷ lục. Bước khởi động đặt i = 0 và đặt z = −∞. Ở một bước lập tổng quát có hai đoạn như sau. - Đoạn 1: (Chạm đáy/đặt cận). Chọn LPi là bài toán con sẽ xét. Giải và xét nó có chạm đáy hay không. (a) Nếu LPi chạm đáy theo tiêu chuẩn 3 thì cập nhật z để được cận dưới mới. Trái lại, theo tiêu chuẩn khác, thì chọn bài toán con LPi mới và lặp như trên. Nếu không còn bài toán con chưa xét thì dừng. Nghiệm tối ưu của LP là tương ứng với cận dưới - kỷ lục cuối cùng, nếu có nghiệm như vậy. (b) Nếu LPi không chạm đáy, chuyển sang Đoạn 2 để chia nhánh LPi . - Đoạn 2: (Chia nhánh). Chọn một trong các biến xj mà x ∗ j ở nghiệm tối ưu LPi chưa là số nguyên. Lập hai bài toán con LP - nới lỏng bằng cách thêm ràng buộc tương ứng xj ≤ [x∗j ] và xj ≥ [x∗j ] + 1 Chuyển sang Đoạn 1.NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN Thuật toán Xét bài toán quy hoạch nguyên tìm max. Gọi z là cận dưới - kỷ lục. Bước khởi động đặt i = 0 và đặt z = −∞. Ở một bước lập tổng quát có hai đoạn như sau. - Đoạn 1: (Chạm đáy/đặt cận). Chọn LPi là bài toán con sẽ xét. Giải và xét nó có chạm đáy hay không. (a) Nếu LPi chạm đáy theo tiêu chuẩn 3 thì cập nhật z để được cận dưới mới. Trái lại, theo tiêu chuẩn khác, thì chọn bài toán con LPi mới và lặp như trên. Nếu không còn bài toán con chưa xét thì dừng. Nghiệm tối ưu của LP là tương ứng với cận dưới - kỷ lục cuối cùng, nếu có nghiệm như vậy. (b) Nếu LPi không chạm đáy, chuyển sang Đoạn 2 để chia nhánh LPi . - Đoạn 2: (Chia nhánh). Chọn một trong các biến xj mà x ∗ j ở nghiệm tối ưu LPi chưa là số nguyên. Lập hai bài toán con LP - nới lỏng bằng cách thêm ràng buộc tương ứng xj ≤ [x∗j ] và xj ≥ [x∗j ] + 1 Chuyển sang Đoạn 1.NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN NHẬN XÉT. Nếu quy hoạch là tim min, thì ở thuật toán chỉ việc thay cận dưới z bởi cận trên z và ở bước khởi động đặt z = +∞. Các chi tiết khác không đổi. Sơ đồ khối thuật toán: NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB CHIA NHÁNH - ĐẶT CẬN - CHẠM ĐÁY THUẬT TOÁN NHÁNH CẬN NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB Giới thiệu MatLab Matlab là chương trình phần mềm trợ giúp cho việc tính toán và hiển thị. Matlab có thể chạy trên hầu hết các hệ máy tính từ máy tính cá nhân đến máy tinh khổng lồ - super computer. Các lệnh của Matlab rất mạnh và hiệu quả cho phép giải các loại hình bài toán khác nhau và đặc biệt hiệu quả cho hệ phương trình tuyến tính cũng như các thao tác trên các bài toán ma trận. NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB Đây là một số lĩnh vực mà Matlab đang giải quyết: - Nghiên cứu và phát triển trong lĩnh vực công nghiệp - Giảng dạy, nghiên cứu lập các chương trình ứng dụng trong giảng dạy cho các môn như toán, lý, hoá, ... trong các trường phổ thông nhằm nâng cao khả năng tiếp thu cũng như ý sáng tạo trong học sinh - Giảng dạy, nghiên cứu lập các chương trình về toán đặc biệt là các loại hình nguyên lý cơ bản và các phương trình tuyến tính cho sinh viên cũng như học sinh các trường kỹ thuật - Giảng dạy và nghiên cứu trong lĩnh vực kỹ thuật và khoa học như: điện tử, lý thuyết điều khiển, vật lý, đồ hoạ, xử lý ảnh, vật liệu, ... - Giảng dạy và nghiên cứu trên mọi lĩnh vực có xuất hiện tính toán bao gồm toán kinh tế, hoá, cơ học, sinh học, ... NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB Lập trình thuật toán Thuật toán "IP.m" (Integer Programming) giải quy hoạch nguyên bằng phương pháp nhánh cận trên MatLab. Thuật toán cần thêm những Toolbox hỗ trợ trong MatLab: - Optimazition Toolbox, - Thuật toán giải bài toán đơn hình gốc trên MatLab: "linprog.m", NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB Giải bài toán nguyên trên Matlab Ví dụ 1: Xét bài toán "knapsack problem" ở phần trên bằng phương pháp nhánh cận trên Matlab. Mô hình bài toán: max z = x1 + x2, 3x1 + 2x2 ≤ 12, x2 ≤ 2, x1, x2 ≥ 0 và nguyên. Chuyển thành ngôn ngữ Matlab, ta có:, f = [−1,−1]; dãy các hệ số lấy phủ định từ bài toán max A = [3 2; 0 1]; B = [12; 2]; lb = [0 0]; ub = [inf inf ]; M = [1, 2]; vecto chỉ số cho biến mà có ràng buộc nguyên Giải bằng Matlab cho nghiệm tối ưu của bài toán: x1 = 4, x2 = 0 với z = 4 NGUYỄN HỮU THƯƠNG PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN QUY HOẠCH NGUYÊN PHƯƠNG PHÁP NHÁNH CẬN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB GIỚI THIỆU MATLAB LẬP TRÌNH THUẬT TOÁN GIẢI BÀI TOÁN NGUYÊN TRÊN MATLAB Ví dụ 2: Xét bài toán "Capital Budgeting" ở phần trên bằng phương pháp nhánh cận trên Matlab . Mô hình bài toán: max z = 8x1 + 11x2 + 6x3 + 4x4, 5x1 + 7x2 + 4x3 + 3x4 ≤ 14, xj ∈ 0, 1, j = 1, . . . , 4. Chuyển thành ngôn ngữ Matlab, ta có:, f = [−8,−11,−6,−4]; dãy các hệ số lấy phủ