Phân tích hệ thống tài nguyên nước - Chương 5: Kỹ thuật tối ưu trong tài nguyên nước

Chương 5Kỹ thuật tối ưu trong TNNQuy hoạch tuyến tính trong TNNCompany Logowww.themegallery.comDạng chung của LPDạ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 ≥ 0Hai dạng cơ bản của LPDạ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 địnhTất cả hệ số RHS của biểu thức ràng buộc là không âm, bj ≥ 0Biến quyết định xj là không âmHàm mục tiêu hoặc là Max hoặc MinHai dạng cơ bản của LP2. Dạng chính tắc (canonical form) MaxRàng buộcTất cả các biến quyết định xj là không âmTấ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à MaxVí dụHai dạng cơ bản của LP3. Chuyển một mô hình tuyến tính về dạng mong muốnMax 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 ứngRà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 ứngVí dụ: Max z = 5x1 + 8x2 Với ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0Hình thành bài toán LP1. 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ị/haLợ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/haTổ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 LP1. 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 2020Dự á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:Tổng độ cứng cho phép của nước cấp vào thành phố là 600mg/lTì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épNguồn 1Nguồn 2Nguồn 3Chi phí (1000$/l/ngày)51020Nguồn nước có sẵn (l/ngày)25120100Độ cứng (mg/l)1001150350Hình thành bài toán LP1. Những ví dụBài toán tuyến tính cho ví dụ 1Xá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 + x2Những rằng buộc+ Ràng buộc về giới hạn diện tích đấtx1 + 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 âmx1, x2 ≥ 0Max z = 2x1 + x2Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0Hình thành bài toán LP1. Những ví dụBài toán tuyến tính cho ví dụ 2Xá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ểuMin Z = 5x1 + 10x2 + 20x3Những rằng buộc+ Rằng buộc về việc đáp ứng khả năng cấp nước tối thiểux1 + x2 + x3 ≤ 150+ Rằng buộc về giới hạn nguồn nước cấpx1 ≤ 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 âmx1, x2, x3 ≥ 0Giải LP bằng phương pháp hình họcTấ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ọcPhươ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ệmGiúp chúng ta hiểu phương pháp đơn hình tốt hơnGiải LP bằng phương pháp hình họcGiải ví dụ 1Max z = 2x1 + x2Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0x1x22x1 + x2 = 0x1 + x2 = 2003x1 + x2 = 300Điểm tối ưu (50,150)Giải LP bằng phương pháp hình họcTrường hợp 1: Không gian nghiệmRàng buộcx13012x201243Vùng nghiệm khả thiNghiệm tối ưuMax z = x1 + x2x1 + 2x2 ³ 2x1 £ 3x2 £ 4x1 ³ 0 x2 ³ 0x1 + 2x2 = 2x1 =3x2 =4Giải LP bằng phương pháp hình họcTrường hợp 2: Đa nghiệmRằng buộcVùng nghiệm khả thiĐa nghiêm41x1312x20203Min z = x1 – x21/3 x1 + x2 £ 4-2x1 + 2x2 £ 4x1 £ 3x1 ³ 0 x2 ³ 0x1 = 3-2x1 + 2x2 = 41/3 x1 + x2 = 4Giải LP bằng phương pháp hình họcTrường hợp 3: Nghiệm tối ưu không biênRằng buộc312x20124034Max z = -2x1 + 6x2-x1 - x2 £ -2-x1 + x2 £ 1x1 ³ 0 x2 ³ 0-x1 - x2 = -2-x1 + x2 = 1x1Giải LP bằng phương pháp hình họcTrường hợp 4: Vô nghiệmRằng buộcMax z = x1 + x2-x1 + x2 £ -1 x1 - x2 £ -1x1 ³ 0 x2 ³ 041x1312x20203x1 + x2 = 1-x1 + x2 = -1 x1 - x2 £ -1Giải LP bằng phương pháp hình họcNế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ả thiNế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 nhauNế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ácThuậ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ậnGiải LP bằng phương pháp hình họcCho bài toán 3 biến quyết định trở lênGiải LP bằng phương pháp hình họcNhữ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ệnNghiệm tối ưu nằm tại một trong những điểm góc của khối đa diện đóCầ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 ưuPhươ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.Ứng dụng của LP trong TNNỨng dụng LP giải quyết một số trường hợp đơn giản của:Bài toán về mô hình quản lý chất lượng nướcBài toán về phân bổ nướcBài toán về xác định mối quan hệ Dung tích hồ ~ lượng xả cho nhu cầuBài toán về xác định chính sách vận hành hồ tối ưu Ứng dụng LP trong TNNBài toán về mô hình quản lý chất lượng nước Ứng dụng LP trong TNNNước thải đi vào: W1Nước thải được loại bỏ: x1W1Nước thải đi vào: W2Nước thải được loại bỏ: x2W2Site 1Site 2Site 3ParkVị trí23Chất lượng nước tồn tại (D0-mg/l)q2q3Chất lượng nước mong muốn (D0-mg/l)Q2Q3Chỉ số chất lượng nước tại vị trị j được cải thiện nhờ một đơn vị nước thải được loại bỏ tại i (aij)a12a13 và a23Chi phí để loại bỏ một đơn vị tỷ lệ nước thải (tỷ lệ nước thải được loại bỏ là xi)C1C2Ghi 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%II. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranhMụ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 nhauNhững giả sử được ứng dụng trong mô hình: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ệpHà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ạiSự phân bổ nước được thực thi trong thời đoạn là tháng.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 Ứng dụng LP trong TNNII. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranhBiế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*XijTrong đó: 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êuTối đa tổng lợi nhuận thực thu được từ việc phân bổ nước Ứng dụng LP trong TNNII. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh2. Hàm mục tiêuTối đa tổng lợi nhuận thực thu được từ việc phân bổ nướcN: 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ồngj: tháng thứ j; k: tổng số tháng trong năm (k =12)Xij, Yj, Zjri: 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ùnga: Giá nước áp dụng cho việc cung cấp 1m3 nước cho du lịchFj: Số khách du lịch được mong chờ trong tháng j Ứng dụng LP trong TNNIII. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh3. Rằng buộcRằng buộc vào diện tích đất dành cho nông nghiệp trong vùng (A)Rằng buộc vào tài nguyên nước có sẵn cho mỗi tháng (Qj – m3/tháng)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)Một số rằng buộc khác: phụ thuộc vào ngữ cảnh Ứng dụng LP trong TNNIII.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ỳ tK: 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)Rt Xả thừa từ hồ chứa tại thời kỳ t (excess release)Hàm mục tiêuMin KRằng buộc:(1) Rằng buộc về phương trình liên tụcSt + Qt – Y – Rt = St+1St+1 = S1Cho 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 Ứng dụng LP trong TNNQtRtKStYIII.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.1Cho 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 YmaxBiến quyết định Y, S1, S2, S3, S4, S5, R1, R2, R3, R4, R5Hàm mục tiêu: MaxYRằng buộcRằng buộc về phương trình liên tụcS1 + Q1 – Y – R1 = S2;S2 + Q2 – Y – R2 = S3;S3 + Q3 – Y – R3 = S4;S5 + Q5 – Y – R5 = S1Rằng buộc vào khả năng trữ của hồS1 < K; S2 < K; S3 < K; S4 < K; S5 < KRằng buộc về các biến không âm Ứng dụng LP trong TNNIII.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) Ứng dụng LP trong TNNY (m3)K (m3)5010512.51015151618III.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 KRằng buộc:(1) Rằng buộc về phương trình liên tụcSt + Qt – Y – Rt = St+1St+1 = S1Cho 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ả tVí dụ 3.2 Tương tự như ví dụ 3.1Cho 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 KminCách giải tương tự như ví dụ 2.1 Ứng dụng LP trong TNNIII.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.3Cho Q (m3): Q1 = 4; Q2 = 8; Q3 = 7; Q4 = 3; Q5 = 2; Q6 = 0Cho Y (m3): Y1 = 5; Y2 = 0; Y3 = 5; Y4 = 6; Y5 = 2; Y6 = 6Giải tương tự như ví dụ 1 cho K = 10 Ứng dụng LP trong TNNIV. 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 ~ tHàm mục tiêu:Rằng buộc(1) Rằng buộc về phương trình liên tụcSt + Qt – Yt - Et– Rt = St+1St+1 = S1Cho 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ướcYt ≤ Dt(4) Rằng buộc vào biến không âmSt ≥ 0Rt ≥ 0 Ứng dụng LP trong TNNBà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 Ứng dụng LP trong TNNBà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 Ứng dụng LP trong TNNwww.themegallery.com Thank You !