Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Phân tích hệ thống tài nguyên nước - Chương 5: Kỹ thuật tối ưu trong TNN (Quy hoạch tuyến tính trong TNN)" trình bày các dạng chung của LP, hai dạng cơ bản của LP, hình thành bài toán LP, giải LP bằng phương pháp hình học,. nội dung chi tiết. | Chương 5 Kỹ thuật tối ưu trong TNN Quy hoạch tuyến tính trong TNN Company Logo www.themegallery.com Dạng chung của LP Dạng tổng quát Max or min: ràng buộc cj: Hệ số hàm mục tiêu aij: Hệ số trong các biểu thức ràng buộc bj: hệ số vế bên phải của biểu thức ràng buộc (RHS) Ví dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0 Hai dạng cơ bản của LP Dạng chuẩn tắc (standard form) Max/ Min Ràng buộc Ví dụ Tất cả các biểu thức ràng buộc là đẳng thức ngoại trừ những biểu thức ràng buộc không âm tương ứng với biến quyết định Tất cả hệ số RHS của biểu thức ràng buộc là không âm, bj ≥ 0 Biến quyết định xj là không âm Hàm mục tiêu hoặc là Max hoặc Min Hai dạng cơ bản của LP 2. Dạng chính tắc (canonical form) Max Ràng buộc Tất cả các biến quyết định xj là không âm Tất cả các biểu thức ràng buộc thuộc loại bất đẳng thức ≤ Hàm mục tiêu là Max Ví dụ Hai dạng cơ bản của LP 3. Chuyển một mô hình tuyến tính về dạng mong muốn Max f(x) = Min [-f(x)] Bất đẳng thức ràng buộc dạng ≥ có thể chuyển thành dạng ≤ , bằng cách nhân với (-1) vào cả hai vế của bất đẳng thức Để chuyển biểu thức ràng buộc dạng bất đẳng thức về dạng đẳng thức: Ràng buộc thuộc loại ≤ , một biến bù không âm (slack variable), s, được cộng vào vế bên trái của biểu thức tương ứng Ràng buộc thuộc loại ≥ một biến dư không âm (surplus variable), s, được trừ bởi vế bên trái của biểu thức tương ứng Ví dụ: Max z = 5x1 + 8x2 Với ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0 Hình thành bài toán LP 1. Những ví dụ Ví dụ 1: Hai cây trồng được trồng trên diện tích đất 200 ha. Chi phí cho cây trồng 1 là 3 đơn vị (tiền tệ)/ha, trong khi cho cây trồng 2 là 1 đơn vị/ha Lợi nhuận đạt được từ cây trồng 1 là 5 đơn vị/ha và từ cây trồng 2 là 2 đơn vi/ha Tổng số tiền có sẵn để nuôi dưỡng 2 cây trồng là: 300 đơn vị Tìm diện tích tối ưu để trồng cho mỗi loại cây trồng 1 và 2 nhằm để lợi nhuận thực đạt được tối đa? Hình thành bài toán LP 1. Những ví dụ Ví dụ 2: Một thành phố gia tăng dân số | Chương 5 Kỹ thuật tối ưu trong TNN Quy hoạch tuyến tính trong TNN Company Logo www.themegallery.com Dạng chung của LP Dạng tổng quát Max or min: ràng buộc cj: Hệ số hàm mục tiêu aij: Hệ số trong các biểu thức ràng buộc bj: hệ số vế bên phải của biểu thức ràng buộc (RHS) Ví dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0 Hai dạng cơ bản của LP Dạng chuẩn tắc (standard form) Max/ Min Ràng buộc Ví dụ Tất cả các biểu thức ràng buộc là đẳng thức ngoại trừ những biểu thức ràng buộc không âm tương ứng với biến quyết định Tất cả hệ số RHS của biểu thức ràng buộc là không âm, bj ≥ 0 Biến quyết định xj là không âm Hàm mục tiêu hoặc là Max hoặc Min Hai dạng cơ bản của LP 2. Dạng chính tắc (canonical form) Max Ràng buộc Tất cả các biến quyết định xj là không âm Tất cả các biểu thức ràng buộc thuộc loại bất đẳng thức ≤ Hàm mục tiêu là Max Ví dụ Hai dạng cơ bản của LP 3. Chuyển một mô hình tuyến tính về dạng mong muốn Max f(x) = Min [-f(x)] Bất đẳng thức ràng .
