Bài giảng Phân tích hệ thống tài nguyên nước: Chương 5

ươ Ch

ậ ố ư ỹ K thu t t ng 5 i u trong TNN

ạ

ế Quy ho ch tuy n tính trong TNN

ủ ạ D ng chung c a LP

/= b

a x ij

c x j

(cid:0) (cid:0) (cid:0)

v Dạng tổng quát Max or min:

= (cid:0) ràng buộc

j 1 jx i = 1,2,...,m

j = 1,2,...,n

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)

(cid:0)

v Ví dụ: Max z = 5x1 + 8x2 Ràng buộc

2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0

Company Logo

www.themegallery.com

1. Dạng chuẩn tắc (standard form)

ủ ạ ơ ả Hai d ng c b n c a LP

a x = b j

= (cid:0)

c x j

(cid:0)

n Max/ Min Ràng buộc = j 1

j 1 jx i = 1,2,...,m j = 1,2,...,n

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

(cid:0)

2. Dạng chính tắc (canonical form)

= (cid:0)

c x j

Max

Ràng buộc

ủ ạ ơ ả Hai d ng c b n c a LP

a x ij

(cid:0) (cid:0)

j 1 jx i = 1,2,...,m

j = 1,2,...,n

(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ụ

(cid:0)

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

ủ ạ ơ ả Hai d ng c b n c a 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ố

)

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)

Nguồn nước có sẵn (l/ngày)

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

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

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

100

350

x 3

Hình thành bài toán LP

600

x 2 +

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 x 1150 + Rằng buộc về đáp ứng chất lượng nước 1 + x 2

x 3

x 1

+ Rằng buộc về biến quyết định không âm x1, x2, x3 ≥ 0

(cid:0)

v Tấ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

v Phươ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

v Giúp chúng ta hiểu phương pháp đơn hình tốt

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

hơn

Giải ví dụ 1

Max z = 2x1 + x2 Với rằng buộc

x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0

Điểm tối ưu (50,150)

1 + x

2 = 0

x1 + x2 = 200

ả ươ ọ 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

4 Max z = x1 + x2 Ràng buộc

3

2

3 x1 = 3

2

4 Vùng nghiệm khả thi

x1 + 2x2 ‡ x1 £ x2 £ x1 ‡

x2 ‡

0 0

1 x1 + 2x2 =

2

0 x1

0

1

2

3

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

Trường hợp 2: Đa nghiệm

x2

Min z = x1 – x2

Đa nghiêm

4 Rằng buộc

3 1/3 x1 + x2 £

4 1/3 x1 + x2 =

4 -2x1 + 2x2 = 4

2 -2x1 + 2x2 £ x1 £

3 x1 = 3

x1 ‡

0 x2 ‡

0 Vùng nghiệm khả thi

1

0 x1

0

1

2

3

ả ươ ọ 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

x2

Max z = -2x1 + 6x2

4 Rằng buộc

3 -2

-x 1 + x 2 = 1

1

2 -x1 - x2 £ -x1 + x2 £ x1 ‡ 0 x2 ‡ 0

1 - x

1 - x 2

=

-

2

0

1

2

3 4 x1

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

Trường hợp 4: Vô nghiệm

x2

Max z = x1 + x2

4 Rằng buộc

-1

3 -x1 + x2 £

-1

x 1 - x 2 £

x1 - x2 £

-1

2 -x1 + x2 = -1

x1 ‡ 0 x2 ‡ 0

x

1 1 + x

2 = 1

0 x1

0

1

2

3

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

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

v Cho bài toán 3 biến quyết định trở lên

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

v Nhữ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

v Nghiệm tối ưu nằm tại một trong những điểm

ả ươ ọ Gi ằ i LP b ng ph ng pháp hình h c

v Cần nhận dạng tất cả các điểm góc, đánh giá

góc của khối đa diện đó

v Phương pháp đơn hình: di chuyển từ một điểm

hàm mục tiêu tại những điểm góc đó và xác định nghiệm tối ưu

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 trong TNN

Ứng dụng LP giải quyết một số trường hợp đơn giản của:

II.

III.

IV.

Bài toán về mô hình quản lý chất lượng nước Bài toán về phân bổ nước Bài toán về xác định mối quan hệ Dung tích hồ ~ lượng xả cho nhu cầu Bài toán về xác định chính sách vận hành hồ tối ưu

Ứ

ụ

ng d ng LP trong TNN

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 được loại bỏ: x2W2

I. Nước thải đi vào: W1 Nước thải được loại bỏ: x1W1

Park

Site 1

Site 2

Site 3

Vị trí

Chất lượng nước tồn tại (D0-mg/l)

Chất lượng nước mong muốn (D0-mg/l)

a12

a13 và a23

Chỉ 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)

Chi 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)

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%

Ứ

ụ

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)

(2)

(3)

(4)

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: 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 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 Sự 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 TNN

II. Bài toán về phân bổ nước và đất cho nhu cầu cạnh tranh

))

ü)

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

ax N =

(r c s )X + i

aF Z j

� � t pY + p

��

= 1

j=1

= 1

Ứ

ụ

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

ax N =

(r c s )X + i

aF Z j

� � t pY + p

��

= 1

j=1

= 1

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

Ứ

ụ

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)

(cid:0)�� X

= 1

(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)

g X i

F Y Q j J

= 1

(5)

(cid:0) (cid:0)

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) q m

Y j

min

(6) Một số rằng buộc khác: phụ thuộc vào ngữ cảnh

(cid:0) (cid:0)

Ứ

ụ

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

St

Y Rt

K

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) Rt Xả thừa từ hồ chứa tại thời kỳ t (excess release) Qt 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

Ứ

ụ

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)

(2)

(3)

Biến quyết định Y, S1, S2, S3, S4, S5, R1, R2, R3, R4, R5 Hàm mục tiêu: MaxY 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

Ứ

ụ

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 10 12.5 15 16

0 5 10 15 18

Ứ

ụ

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

Ứ

ụ

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

Ứ

ụ

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:

Max

Y t

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

(cid:0)