Giáo trình tối ưu hóa - Chương 4

Quy hoạch nguyên 1. Phương pháp cắt Gomory giải bài toán quy hoạch tuyến tính nguyên 1.1. Phát biểu bài toán quy hoạch tuyến tính nguyên Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy hoạch tuyến tính nguyên hay bài toán quy hoạch tuyến tính nguyên (BTQHTT nguyên), mà trong đó chúng ta muốn tối ưu hoá / cực đại hoá hay cực tiểu hoá hàm mục tiêu với điều kiện các biến quyết định là các biến nguyên: ...
Nội dung trích xuất từ tài liệu:
Giáo trình tối ưu hóa - Chương 4 Chương IV Quy hoạch nguyên 1. Phương pháp cắt Gomory giải bài toán quy hoạch tuyến tính nguyên 1.1. Phát biểu bài toán quy hoạch tuyến tính nguyên Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình quy hoạch tuyến tính nguyên hay bài toán quy hoạch tuyến tính nguyên (BTQHTT nguyên), mà trong đó chúng ta muốn tối ưu hoá / cực đại hoá hay cực tiểu hoá hàm mục tiêu với điều kiện các biến quyết định là các biến nguyên: z = c1x1 + c2x2 + .... + cnxn → Max (Min), với các điều kiện ràng buộc a11x1 + a12x2 + ... + a1nxn ≤ b1 a21x1 + a22x2 + ... + a2nxn ≤ b2 ... am1x1 + am2x2 + ... + amnxn ≤ bm x1, x2, ..., xn ≥ 0 (điều kiện không âm) x1, x2, ..., xn nguyên (điều kiện nguyên). Trong trường hợp tổng quát, BTQHTT nguyên có thể bao gồm các ràng buộc dạng ≥, ≤ hoặc dạng =, các biến có thể có dấu ≥ 0, ≤ 0 hoặc dấu tùy ý. Ví dụ 1. Xét BTQHTT: Max z = x1 + 4x2 với các ràng buộc 2x1 + 4x2 ≤ 7 10x1 + 3x2 ≤ 15 x1 , x2 ≥ 0 x1, x2 nguyên . 81 Cần tìm các giá trị nguyên của các biến quyết định x1, x2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. 1.2. Minh họa phương pháp Gomory bằng đồ thị Chúng ta đi tìm phương án tối ưu cho BTQHTT nguyên trong ví dụ 1 bằng đ ồ th ị . Bước 1: Vẽ miền các phương án khả thi (còn gọi là miền ràng buộc) là tập hợp các phương án khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ số (x1, x2), thoả mãn tất cả các ràng buộc đã có kể cả điều kiện không âm và điều kiện nguyên của các biến (xem hình IV.1). – Trước hết chúng ta vẽ đường thẳng có phương trình là 2x1 + 4x2 = 7. Đường thẳng này chia mặt phẳng làm hai nửa mặt phẳng. Một phần gồm các điểm (x1, x2) thoả mãn: 2x1 + 4x2 ≤ 7, phần còn lại thoả mãn: 2x1 + 4x2 ≥ 7. Ta tìm được nửa mặt phẳng thoả mãn: 2x1 + 4x2 ≤ 7. x2 10x1 + 3x2 = 15 A 7/4 B(39/34;20/17) 1D F 2x1 + 4x2 = 7 E G C O x1 1 1,5 7/2 Hình IV.1. Phương pháp đồ thị giải BTQHTT nguyên – Tương tự, có thể tìm nửa mặt phẳng thoả mãn: 2x1 + 4x2 ≤ 48. – Lúc này, giao của hai nửa mặt phẳng tìm được trên cho ta tập hợp các điểm (x1, x2) thoả mãn các ràng buộc. Tuy nhiên, để thoả mãn điều kiện không âm và điều kiện nguyên của các biến, ta chỉ xét các điểm nằm trong góc phần tư thứ nhất có các tọa độ đều nguyên. Vậy miền các phương án khả thi là miền gồm các điểm với tọa độ nguyên được giới hạn bởi tứ giác OABC. Bước 2: Trong miền (OABC) ta tìm điểm (x1, x2) với các tọa độ nguyên sao cho z = x1 + 4x2 đạt giá trị lớn nhất. Dễ thấy đó là điểm F(1, 1) Kết luận. Trong các phương án khả thi thì phương án tối ưu là (x1 = 1, x2 = 1). Tại phương án này, giá trị hàm mục tiêu là lớn nhất zmax = 1 × 1 + 4 × 1 = 5. Tóm tắt phương pháp Gomory Chúng ta quy định gọi BTQHTT như cho trong ví dụ 1 nhưng bỏ qua điều kiện nguyên của các biến là BTQHTT không nguyên tương ứng với BTQHTT nguyên đã cho. Trước khi giải 82 BTQHTT nguyên cho trong ví dụ 1 bằng bảng đơn hình theo phương pháp Gomory, chúng ta có thể mô tả phương pháp này bằng đồ thị như sau: – Khi giải BTQHTT không nguyên chúng ta chỉ xét các điều kiện ràng buộc sau: 2x1 + 4x2 ≤ 7 10x1 + 3x2 ≤ 15 x1, x2 ≥ 0. Ta có z(O) = z(0, 0) = 0, z(C) = z(1,5, 0) = 1,5, z(B) = z(39/34, 20/17) = 199/34 và z(A) = z(0, 7/4) = 7. Vậy phương án tối ưu (chưa xét điều kiện nguyên là (0, 7/4) với zmax = 7. – Tuy nhiên phương án (0, 7/4) chưa thỏa mãn điều kiện nguyên do tọa độ x2 = 7/4 chưa nguyên. Chúng ta đưa thêm vào điều kiện x2 ≤ 1 hoặc x2 ≥ 2. Chúng ta gọi hai điều kiện bổ sung này là hai lát cắt L1 và L1’. Làm như vậy, tuy chúng ta thu hẹp miền phương án của BTQHTT không nguyên, nhưng vẫn giữ nguyên miền phương án của BTQHTT nguyên đã cho. Vậy miền ràng buộc trở thành 2x1 + 4x2 ≤ 7 10x1 + 3x2 ≤ 15 x2 ≤ 1 (L1) hoặc x2 ≥ 2 (L1’) x1 , x2 ≥ 0. Miền này chính là miền ODEC = miền OABC ∩ {miền {(x1, x2) ∈ R2: x2 ≤ 1} ∪ miền {(x1, x2) ∈ R2: x2 ≥ 2}}. Nhìn vào hình IV.1 có ...