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

Nội dung text: 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

1. Chương 5 Kỹ thuật tối ưu trong TNN Quy hoạch tuyến tính trong TNN
2. Dạng chung của LP v 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 Ví dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0 www.themegallery.com Company Logo
3. Hai dạng cơ bản của LP 1. Dạng chuẩn tắc (standard form) Max/ Min Ràng buộc Ví dụ (1) 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 (2) Tất cả hệ số RHS của biểu thức ràng buộc là không âm, bj ≥ 0 (3) Biến quyết định xj là không âm (4) Hàm mục tiêu hoặc là Max hoặc Min
4. Hai dạng cơ bản của LP 2. Dạng chính tắc (canonical form) Max Ràng buộc (1) Tất cả các biến quyết định xj là không âm (2) Tất cả các biểu thức ràng buộc thuộc loại bất đẳng thức ≤ (3) Hàm mục tiêu là Max Ví dụ
5. 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 (1) Max f(x) = Min [-f(x)] (2) 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 (3) Để 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
6. 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?
7. 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ố - Trong dự án quy hoạch đô thị của thành phố đó, cấp nước cho thành phố tối thiểu đạt150 l/ngày vào cuối năm 2020 - Dự án đó nhận dạng có 3 nguồn cấp nước khác nhau, cụ thể: + Từ một con suối chảy qua thành phố (nguồn 1) + Từ nguồn nước ngầm (nguồn 2) + Từ một con sông cách xa thành phố (nguồn 3) Số liệu chi tiết của 3 nguồn này được liệt kê như sau: Nguồn 1 Nguồn 2 Nguồn 3 Chi phí (1000$/l/ngày) 5 10 20 Nguồn nước có sẵn (l/ngày) 25 120 100 Độ cứng (mg/l) 100 1150 350 - Tổng độ cứng cho phép của nước cấp vào thành phố là 600mg/l Tìm lượng nước cần lấy từ mỗi nguồn sao cho đáp ứng yêu cầu nước tương lai của thành phố với chi phí tối thiểu, trong khi vẫn duy trì chất lượng của nước trong giời hạn cho phép
8. Hình thành bài toán LP 1. Những ví dụ Bài toán tuyến tính cho ví dụ 1 - Xác định biến ra quyết định: Diện tích mà cây trồng 1 và cây trồng 2 nên được trồng x1 (ha) và x2 (ha) - Xác định hàm mục tiêu: Tối đa lơi nhuận thực thu được từ việc trồng 2 loại cây trồng đó Max Z = 2x1 + x2 - Những rằng buộc + Ràng buộc về giới hạn diện tích đất x1 + x2 ≤ 200 + Ràng buộc về giới hạn qũy: 3x1 + x2 ≤ 300 + Rằng buộc về biến quyết định không âm x1, x2 ≥ 0 Max z = 2x1 + x2 Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0
9. Hình thành bài toán LP 1. Những ví dụ Bài toán tuyến tính cho ví dụ 2 - Xác định biến ra quyết định: Lượng nước cần lấy từ mỗi nguồn (nguồn 1, nguồn 2 và nguồn 3) x1(ml/ngày), x2 (ml/ngày) và x3 (ml/ngày) - Xác định hàm mục tiêu: Chi phí cấp nước phải là tối thiểu Min Z = 5x1 + 10x2 + 20x3 - Những rằng buộc + Rằng buộc về việc đáp ứng khả năng cấp nước tối thiểu x1 + x2 + x3 ≤ 150 + Rằng buộc về giới hạn nguồn nước cấp x1 ≤ 25; x2 ≤ 120; x3 ≤ 100 + Rằng buộc về đáp ứng chất lượng nước + Rằng buộc về biến quyết định không âm x1, x2, x3 ≥ 0
10. Giải LP bằng phương pháp hình học vTất cả những mô hình tuyến tính 2 chiều (2 biến quyết định) đều có thể giải được bằng phương pháp hình học vPhương pháp hình học cho một cái nhìn bên trong về hình dạng của những mô hình tuyến tính và việc đạt được nghiệm vGiúp chúng ta hiểu phương pháp đơn hình tốt hơn
11. Giải LP bằng phương pháp hình học Giải ví dụ 1 Max z = 2x1 + x2 Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0 x2 3x 1 + x 2 = 300 2x 1 + x Điểm tối ưu (50,150) 2 x = 0 1 + x 2 = 200 x1
12. Giải LP bằng phương pháp hình học Trường hợp 1: Không gian nghiệm Nghiệm tối ưu x2 x2 =4 Max z = x1 + x2 4 Ràng buộc x1 + 2x2 ³ 2 3 Vùng x1 £ 3 x =3 nghiệm 1 2 x2 £ 4 khả thi x1 ³ 0 x2 ³ 0 1 x 1 + 2x 2 = 2 0 x1 0 1 2 3
13. Giải LP bằng phương pháp hình học Trường hợp 2: Đa nghiệm x2 Đa Min z = x1 – x2 nghiêm 4 Rằng buộc 4 = 1/3 3 2 x 1/3 x1 + x2 £ 4 2x 1 + x + 2 = 1 4 -2x -2x1 + 2x2 £ 4 2 x1 £ 3 Vùng nghiệm x1 = 3 x1 ³ 0 x2 ³ 0 1 khả thi 0 0 1 2 3 x1
14. Giải LP bằng phương pháp hình học Trường hợp 3: Nghiệm tối ưu không biên x Max z = -2x + 6x 2 1 2 4 Rằng buộc 1 = 3 2 -x1 - x2 £ -2 x + -x 1 -x1 + x2 £ 1 2 x1 ³ 0 x2 ³ 0 1 -x 1 - x 2 = -2 0 0 1 2 3 4 x1
15. Giải LP bằng phương pháp hình học Trường hợp 4: Vô nghiệm x2 Max z = x + x 1 2 4 Rằng buộc -1 £ 3 2 -x + x £ -1 - x 1 2 1 x x - x £ -1 -1 1 2 2 = x 2 + 1 -x x1 ³ 0 x2 ³ 0 x 1 1 + x 2 = 1 0 0 1 2 3 x1
16. Giải LP bằng phương pháp hình học v Nếu bài toán tuyến tính có một nghiệm tối ưu, nghiệm đó luôn luôn nằm trong một của những điểm góc thuộc không gian nghiệm khả thi v Nếu bài toán tuyến tính có nhiều nghiệm tối ưu, khi đó có ít nhất 2 điểm cực trị khả thi cạnh nhau v Nếu một điểm cực trị là tốt hơn tất của những điểm xung quanh, khi đó nó sẽ tốt hơn tất cả những điểm cực trị khác v Thuật toán cho việc giải bài toán LP: - Xác định điểm xuất phát tìm kiếm cho nghiệm tối ưu: nên bắt đầu với điểm gốc (0,0) - Tìm nghiệm tốt hơn bằng việc so sánh giá trị hàm mục tiêu tương ứng vớ những điểm cực trị khả thi lân cận
17. Giải LP bằng phương pháp hình học vCho bài toán 3 biến quyết định trở lên
18. Giải LP bằng phương pháp hình học vNhững biểu thức rằng buộc xác định hình dạng hình học của không gian nghiệm – khối đa diện vNghiệm tối ưu nằm tại một trong những điểm góc của khối đa diện đó vCần nhận dạng tất cả các điểm góc, đánh giá hàm mục tiêu tại những điểm góc đó và xác định nghiệm tối ưu vPhương pháp đơn hình: di chuyển từ một điểm góc tới điểm góc khác cho đến khi nghiệm tối ưu được tìm thấy.
19. Ứng dụng của LP trong TNN
20. Ứng dụng LP trong TNN Ứng dụng LP giải quyết một số trường hợp đơn giản của: I. Bài toán về mô hình quản lý chất lượng nước II. Bài toán về phân bổ nước III. Bài toán về xác định mối quan hệ Dung tích hồ ~ lượng xả cho nhu cầu IV. Bài toán về xác định chính sách vận hành hồ tối ưu
21. Ứng dụng LP trong TNN I. Bài toán về mô hình quản lý chất lượng nước Nước thải đi vào: W2 Nước thải đi vào: W1 Nước thải được loại bỏ: x2W2 Nước thải được loại bỏ: x1W1 Site 1 Park Site 2 Site 3 Vị trí 2 3 Chất lượng nước tồn tại (D0-mg/l) q2 q3 Chất lượng nước mong muốn (D0-mg/l) Q2 Q3 Chỉ số chất lượng nước tại vị trị j được cải thiện a12 a13 và a23 nhờ một đơn vị nước thải được loại bỏ tại i (aij) Chi phí để loại bỏ một đơn vị tỷ lệ nước thải (tỷ C1 C2 lệ nước thải được loại bỏ là xi) Ghi chú: Yêu cầu ít nhất 30% nước thải phải được loại bỏ khỏi 2 vị trị và Hiệu quả xử lý tối đa là 95%
22. Ứng dụng LP trong TNN II. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh - Mục tiêu: Tối ưu phân bổ nước trong và giữa các ngành của một vùng cụ thể để hỗ trỡ quá trình quyết định trong viêc đánh giá giá nước và sự phân bổ hiện hành với giá nước và sự phân bổ tối ưu dọc theo các ngành khác nhau Trích từ: Quba’a, R., EL-Fadel, M., Darwihs, M. R. W (2002). Water pricing for multi-sectoral allocation: A case study. Journal of Water Resources Development, 18 (4), 523-544. - Hàm mục tiêu là tối đa lợi nhuận thực thu được từ việc phân bổ nước tối ưu cho các ngánh sử dụng nước khác nhau - Những giả sử được ứng dụng trong mô hình: (1) Sử dụng nước cạnh tranh của vùng gồm 3 ngành: Nông nghiệp, sinh hoạt và công nghiệp (2) Hàm mục tiêu xác định lượng nước cho các ngành dựa trên tối đa lợi nhuận thực thu được từ phân bổ cây trồng trong ngành nông nghiệp và từ việc tiêu thụ nước trên đầu người từ 2 ngành còn lại (3) Sự phân bổ nước được thực thi trong thời đoạn là tháng. (4) Lợi nhuận thu được từ việc sử dụng của bất cứ ngành nào là độc lập với số lượng nước được phân bổ tới ngành sử dụng nước khác
23. Ứng dụng LP trong TNN II. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh 1. Biến quyết định: - Lượng nước được phân bổ ứng với mỗi loại cây trồng i trong tháng j: gij*Xij ü Trong đó: gij: Lượng nước yêu cầu cho một đơn vị ha cây trồng i trong tháng j (m3/ha) ü Xij: Diện tích được trồng bởi cây trồng i trong tháng j (ha) - Lượng nước được phân bổ trên đầu ngườ i trong tháng j cho sinh hoạt. Yj (m3/người) - Lượng nước được phân bổ trên đầu người trong tháng j cho du lịch, Zj (m3/người) 2. Hàm mục tiêu Tối đa tổng lợi nhuận thực thu được từ việc phân bổ nước
24. Ứng dụng LP trong TNN II. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh 2. Hàm mục tiêu Tối đa tổng lợi nhuận thực thu được từ việc phân bổ nước N: Lợi nhuận thực hàng năm (annual net revenue) thu được từ mô hình phân bổ nước ($) i: cây trồng i; n: tổng số cây trồng j: tháng thứ j; k: tổng số tháng trong năm (k =12) Xij, Yj, Zj ri: tổng thu nhập hàng năm của cây trồng i trên ha ($/ha/year) Ci: Tổng chi phí hàng năm cho cây trồng i trên ha ($/ha/year): chuẩn bị đất, gieo hạt (trồng cây), phân bón, thuốc trừ sâu, thu hoạch, lưu trữ và nhân công vv. Si: Tổng chi phí quản lý hàng năm của cây trồng i trên ha ($/ha/year) t: giá nước áp dụng cho việc cung cấp 1m3 nước sạch ($/m3) p: tổng dân số trong vùng a: Giá nước áp dụng cho việc cung cấp 1m3 nước cho du lịch Fj: Số khách du lịch được mong chờ trong tháng j
25. Ứng dụng LP trong TNN III. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh 3. Rằng buộc (1) Rằng buộc vào diện tích đất dành cho nông nghiệp trong vùng (A) (2) Rằng buộc vào tài nguyên nước có sẵn cho mỗi tháng (Qj – m3/tháng) (3) Rằng buộc về lượng nước cấp tối thiểu (qmin) và tối đa (qmax) cho sinh hoạt (m3/người/tháng) (4) Một số rằng buộc khác: phụ thuộc vào ngữ cảnh
26. Ứng dụng LP trong TNN III.1: Bài toán tìm dung tích hồ (capacity), biết lượng nước xả cố định cho nhu cầu (yield) (bỏ qua bốc hơi và thấm) St: dung tích hiệu dụng của hồ chứa (active reservoir storage) tại thời kỳ t K: tổng dung tích hiệu dụng của hồ (active storage volume capacity) Qt: Dòng chảy vào hồ tại thời kỳ t (inflow volume) Y: Lượng xả cho nhu cầu trong mỗi thời kỳ t (yield) S Rt Xả thừa từ hồ chứa tại thời kỳ t (excess release) t Hàm mục tiêu Y Qt Min K Rt K Rằng buộc: (1) Rằng buộc về phương trình liên tục St + Qt – Y – Rt = St+1 St+1 = S1 Cho mỗi thời kỳ t = 1, 2, 3, ,T, T+1 = 1 (2) Rằng buộc vào khả năng trữ của hồ St ≤ K cho tất cả t
27. Ứng dụng LP trong TNN III.1: Bài toán tìm lượng nước xả cho nhu cầu Y(hằng số) (yield) biết dung tích hồ (capacity), (bỏ qua bốc hơi và thấm) Ví dụ 3.1 Cho Q (m3): Q1 = 10; Q2 = 5; Q3 = 30; Q4 = 20; Q5 = 15; Với K(m3) tùy ý ( K = 0, 5; 10; 15; 16 vv) Tìm Y sao cho Ymax (1) Biến quyết định Y, S1, S2, S3, S4, S5, R1, R2, R3, R4, R5 (2) Hàm mục tiêu: MaxY (3) Rằng buộc - Rằng buộc về phương trình liên tục S1 + Q1 – Y – R1 = S2; S2 + Q2 – Y – R2 = S3; S3 + Q3 – Y – R3 = S4; S5 + Q5 – Y – R5 = S1 - Rằng buộc vào khả năng trữ của hồ S1 < K; S2 < K; S3 < K; S4 < K; S5 < K - Rằng buộc về các biến không âm
28. Ứng dụng LP trong TNN III.1: Bài toán tìm lượng nước xả cho nhu cầu Y(hằng số) (yield) biết dung tích hồ (capacity), (bỏ qua bốc hơi và thấm) Ví dụ 3.1: Kết quả (hoặc ứng dụng Lingo hoặc ứng dụng excel solver) Y (m3) K (m3) 5 0 10 5 12.5 10 15 15 16 18
29. Ứng dụng LP trong TNN III.3: Bài toán tìm dung tích hồ (capacity), biết lượng nước xả cố định cho nhu cầu (yield) (bỏ qua bốc hơi và thấm) Hàm mục tiêu: Min K Rằng buộc: (1) Rằng buộc về phương trình liên tục St + Qt – Y – Rt = St+1 St+1 = S1 Cho mỗi thời kỳ t = 1, 2, 3, ,T, T+1 = 1 (2) Rằng buộc vào khả năng trữ của hồ St ≤ K cho tất cả t Ví dụ 3.2 Tương tự như ví dụ 3.1 Cho Q (m3): Q1 = 10; Q2 = 5; Q3 = 30; Q4 = 20; Q5 = 15; Biết K (K chọn tùy ý) Tìm K, sao cho Kmin Cách giải tương tự như ví dụ 2.1
30. Ứng dụng LP trong TNN III.3: Bài toán tìm dung tích hồ (capacity), biết lượng nước xả cho nhu cầu Yt (yield) (bỏ qua bốc hơi và thấm) Ví dụ 3.3 Cho Q (m3): Q1 = 4; Q2 = 8; Q3 = 7; Q4 = 3; Q5 = 2; Q6 = 0 Cho Y (m3): Y1 = 5; Y2 = 0; Y3 = 5; Y4 = 6; Y5 = 2; Y6 = 6 Giải tương tự như ví dụ 1 cho K = 10
31. Ứng dụng LP trong TNN IV. Bài toán về xác định chính sách vận hành hồ tối ưu (Reservoir Rule Curve) Tìm đường St+1 ~ t Hàm mục tiêu: Rằng buộc (1) Rằng buộc về phương trình liên tục St + Qt – Yt - Et– Rt = St+1 St+1 = S1 Cho mỗi thời kỳ t = 1, 2, 3, ,T, T+1 = 1 (2) Rằng buộc vào khả năng trữ của hồ St ≤ K cho tất cả t (3) Rằng buộc vào đáp ứng nhu cầu cấp nước Yt ≤ Dt (4) Rằng buộc vào biến không âm St ≥ 0 Rt ≥ 0
32. Ứng dụng LP trong TNN IV. Bài toán về xác định chính sách vận hành hồ tối ưu (Reservoir Rule Curve) Ví dụ: Tìm đường St+1 ~ t bằng LP biết K = 350
33. Ứng dụng LP trong TNN IV. Bài toán về xác định chính sách vận hành hồ tối ưu (Reservoir Rule Curve) Kết quả từ Ví dụ: Tìm đường St+1 ~ t bằng LP
34. www.themegallery.com