Bài giảng Giải thuật nâng cao: Quy hoạch tuyến tính - TS. Ngô Quốc Việt

Bài giảng này trang bị cho người học những kiến thức về quy hoạch tuyến tính. Nội dung chính trình bày trong bài giảng gồm có: Giới thiệu chung về quy hoạch tuyến tính, giải quy hoạch tuyến tính dựa trên đồ thị, bài toán đối ngẫu, giải thuật Simplex, Max-Flow dựa trên LP. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Giải thuật nâng cao: Quy hoạch tuyến tính - TS. Ngô Quốc ViệtQUY HOẠCH TUYẾN TÍNH TS. NGÔ QUỐC VIỆT 2015 Nội dung1. Giới thiệu2. Giải quy hoạch tuyến tính dựa trên đồ thị3. Bài toán đối ngẫu4. Giải thuật Simplex5. Max-Flow dựa trên LP Giải thuật nâng cao-Quy hoạch tuyến tính 2Giới thiệu Mục tiêu kinh doanh thường: maximizing profit hoặc minimizing costs. Quy hoạch tuyến tính (Linear programming) sử dụng các quan hệ tuyến tính để biểu diễn các quyết định, với business objective, và các constraints. Linear Programming model tìm maximize hoặc minimize linear function, thỏa mãn linear constraints. Giải thuật nâng cao-Quy hoạch tuyến tính 3Quy hoạch tuyến tính• Nhiều vấn đề thực tế có dạng linear programming.• Các vấn đề thực khác có thể xấp xỉ theo linear models.• Có nhiều ứng dụng trong : • Manufacturing, Marketing, Finance (investment), Advertising, Agriculture, Energy, etc.• Có nhiều kỹ thuật hiệu quả nhằm tìm nghiệm của linear programming models. Giải thuật nâng cao-Quy hoạch tuyến tính 4Giới thiệuChuyển vấn đề sang LP1. Xác định vấn đề có thể giải bằng linear programming.2. Lập mô hình toán của unstructured problem theo các bước a. Xác định hàm mục tiêu b. Xác định các biến quyết định c. Xác định ràng buộc3. Giải mô hình dựa trên một số kỹ thuật. Giải thuật nâng cao-Quy hoạch tuyến tính 5 Quy hoạch tuyến tính-ví dụ 1 MAX 4X1 + 7X3 - 6X4 2X1 + 3X2 - 2X4 = 20 -2X2 + 9X3 + 7X4  10 -2X1 + 3X2 + 4X3 + 8X4  35Ràng buộc X2  5 Mọi X  0 X1  0, X2  0, X3  0, X4  0 Giải thuật nâng cao-Quy hoạch tuyến tính 6 Quy hoạch tuyến tính-ví dụ 2• Resource 40 giờ công mỗi ngày Availability: 120 lbs đất sét• Decision x1 = số chén (bowl) sản xuất mỗi ngày Variables: x2 = số ca (mug) sản xuất mỗi ngày• Objective Maximize Z = $40x1 + $50x2 Function: với Z = lợi nhuận mỗi ngày• Resource 1x1 + 2x2  40 (giờ công) Constraints: 4x1 + 3x2  120 lbs đất sét• Non-Negativity x1  0; x2  0 Constraints: Giải thuật nâng cao-Quy hoạch tuyến tính 7Quy hoạch tuyến tính-ví dụ 2 (tt)Mô hình tuyến tínhMaximize Z = $40x1 + $50x2Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Giải thuật nâng cao-Quy hoạch tuyến tính 8 Quy hoạch tuyến tính-ví dụ 3• Post office cần số nhân viên theo từng ngày trong tuần, được xác định trong bảng cụ thể.• Quy định: mỗi nhân viên phải làm 5 ngày liên tục, rồi nghỉ hai ngày.• Yêu cầu: lập LP sao cho post office có thể sử dụng ít nhân viên nhất. Giải thuật nâng cao-Quy hoạch tuyến tính 9 Quy hoạch tuyến tính-ví dụ 3• Đặt: x1, x2,…, x7 là số nhân viên làm việc bắt đầu tương ứng vào Monday, Tue, …, Sun (x1 làm từ Mon đến Fri)• Hàm mục tiêu: z=Min (x1+x2+…+x7)• Ràng buộc: x1+ +x4+x5+x6+x7 >=17 x1+ x2+ +x5+x6+x7 >=13 x1+x2+x3+ +x6+x7 >=15 x1+x2+x3+ x4+ +x7 >=19 x1+x2+x3+x4+x5 >=14 x2+x3+x4+x5+x6 >=16 x3+x4+x5+x6+x7 >=11 Giải thuật nâng cao-Quy hoạch tuyến tính 10Các thành phần của mô hình• Các biến quyết định – ký hiệu toán biểu diễn các trạng thái/mức độ của một vấn đề cụ thể. Các biến quyết định là độc lập• Hàm mục tiêu – quan hệ tuyến tính mô tả mục tiêu, theo các decision variable – yêu cầu là cần cực đại/tiểu hàm này.• Ràng buộc – các yêu cầu hay hạn chế ràng buộc bài toán, thể hiện quan hệ tuyến tính giữa các decision variable.• Tham số - các hệ số và hằng của hàm mục tiêu và ràng buộc. Giải thuật nâng cao-Quy hoạch tuyến tính 11Phương pháp đồ thị cho LP• Phương pháp graphical phù hợp cho các môhình linear programming chỉ có hai decisionvariables• Phương pháp graphical thể hiện trực quanlời giải của linear programming problem. Giải thuật nâng cao-Quy hoạch tuyến tính 12 Phương pháp đồ thị cho LP • Xét ví dụ 2 X2: số mugMaximize Z = $40x1 + $50x2Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 X1: số bowl Giải thuật nâng cao-Quy hoạch tuyến tính 13 Phương pháp đồ thị cho LP (tt)Maximize Z = $40x1 + $50x2Thỏa mãn: 1x1 + 2x2  40 4x1 + 3x2  120 x1, x2  0 Đồ thị ràng buộc giờ công ...