Bài giảng Kỹ thuật tối ưu trong TNN - Một số kỹ thuật cụ thể: Quy hoạch tuyến tính trong TNN

ậ ố ư

i u trong TNN ậ ụ ể

ộ ố ỹ

ỹ K thu t t M t s k thu t c th

ạ

ế Quy ho ch tuy n tính trong TNN

Dạng chung của bài toán tuyến tính

Hình thành bài toán tuyến tính

Phương pháp hình học

Phương pháp bảng đơn hình

Phân tích độ nhạy

Chương trình tuyến tính đối ngẫu

Ứng dụng QHTT trong QH&QLNN

ủ

ạ

D ng chung c a LP

/= b

a x ij

= (cid:0)

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

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

c x ràng buộc j

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í 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

ủ

ạ

ơ ả Hai d ng c b n c a LP

a x = b j

= (cid:0)

c x j

(cid:0)

1. Dạng chuẩn tắc (standard form) 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)

ủ

ạ

ơ ả Hai d ng c b n c a LP

= (cid:0)

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

c x j

Ràng buộc

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

(cid:0)

ủ

ạ

ơ ả 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) Một phương trình đẳng thức có thể thay thế bởi hai bất đẳng thức có dấu ngược nhau. Ví dụ, một phương trình g(x) = b có thể được thay thế bởi g(x) ≤ b và g(x) ≥ b

(4) Một bất đẳng thức có dấu giá trị tuyệt đối có thể được thay thế

bẳng hai bất đẳng thức không có dấu tuyệt đối. Ví dụ |g(x)| ≤ b, có thể thay thế bởi g(x) ≤ b và g(x) ≥ -b.

(5) Để 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

ủ

ạ

ơ ả Hai d ng c b n c a LP

Ví dụ: Max z = 5x1 + 7x2 Với ràng buộc 3x1 + 4x2 ≤ 15 2x1 + 3x2 ≥ 6 x1, x2 ≥ 0

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

Ví dụ 1: - Hai loại cây trồng được trồng trên diện tích đất tối đa là 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 phân bổ cho 2 loại cây trồng là: 300 đơn vị - Tìm diện tích tối ưu cho mỗi loại cây trồng 1 và 2 để lợi nhuận thực

đạt được tối đa?

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

Ví dụ 2: - Một khu công nghiệp dự kiến xây dựng, yêu cầu tối thiểu 10,000 m3 nước trong suốt một thời kỳ cụ thể. Nguồn nước này được cung cấp bởi hai nguồn:

(1) Tầng ngậm nước ngầm và (2) Hồ chứa trên sông - Tổng nồng độ chất rắn hòa tan (TDS) trong tầng ngậm nước và hồ

chứa lần lượt là 980 và 100 mg/l (g/m3)

- Nồng độ TDS cho phép tối đa đối với nguồn nước vào sử dụng là

500 mg/l

- Do khả năng giới hạn của giếng nước ngầm và công trình khai thác nước từ hồ chứa nên lượng nước có thể được lấy tối đa từ hai nguồn lần lượt là nước ngầm: 6000m3 và hồ chứa: 10000m3 - Hiện nay, quyết định vận hành là dựa vào việc tối thiểu số lượng nước được lấy từ hồ chứa chất lượng tốt hơn (nồng độ TDS thấp hơn) để tối đa chất lượng nước tốt này cho sử dụng tương lai

- Tìm quyết định vận hành đó.

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

Ví dụ 3: - Trong dự án quy hoạch đô thị của một thành phố, yêu cầu cấp nước cho thành phố tăng tối thiểu tới 150x106 l/ngày vào cuối năm 2020 để đối phó với sự tăng trưởng dân số trong vùng.

- Dự án đó nhận dạng có 3 nguồn cấp nước khác nhau, cụ thể: + Từ một con sông chảy qua thành phố, với chi phí thấp, chất lượng nước tốt ,

nhưng khả năng khai thác trong tương lai lại thấp (nguồn 1)

+ Từ nguồn nước ngầm, chất lượng nước kém hơn (nguồn 2) + Từ một con sông cách xa thành phố, với chi phí đắt (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$/106l/ngày)

Nguồn nước có sẵn (106l/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

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

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

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

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

hơn

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

Ví d 4ụ  Dự án tưới

 Lượng nước tối đa: 1800 acre-feet/năm

Cây trồng A Cây trồng B

Yêu cầu nước (Acre feet/acre) 3 2

Lợi nhuận thực ($/acre) 300 500

 Yêu cầu tìm diện tích tưới cho mỗi loại cây trồng để lợi nhuận

đạt được tối đa.  Biến quyết định

 xA = Diện tích cây trồng A nên trồng (acres)?  xB = Diện tích cây trồng B nên trồng (acres)?

Diện tích tối đa (acres) 400 600

1,800 acre feet = 2,220,267 m3 400 acre = 1,618,742 m2

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

Ví d 4ụ

Maximize

300

500

Subject

(cid:0) (cid:0)

400

(1)

(cid:0)

xA< 400

(cid:0)

xA> 0

600

(2)

10

B x

1800

(3)

(cid:0) (cid:0)

3 x

B x

(4)

(cid:0) (cid:0)

8 xB< 600

6

4 ) s e r c a 0 0 1 ( B x

3xA +2 xB < 1800

2 xB > 0

2

4

6

8

10 xA (100 acres)

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

Ví d 4ụ

Objective Z (cid:0) 300x A

(cid:0) 500x B

xA< 400

xA> 0

10

(cid:0) (cid:0)

Z=3600=300xA +500xB

(200, 600)

8 xB< 600

6 Z=2000=300xA +500xB

4 Z=1000=300xA +500xB

) s e r c a s d e r d n u h ( B x

2 xB > 0

2

8

10 6 4 xA (hundreds acres)

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

ệ

ặ

ị

Nghi m không b ch n (Unounded Solution)

Bỏ ràng buộc 2 và 3 của ví dụ 4, hàm mục tiêu có thể tăng và không bị chặn

Maximize

300

500

(cid:0) (cid:0)

xA< 400

xA> 0

10

Subject

400

(1)

(cid:0)

unbounded

8

600

(2)

(cid:0)

B x

1800

(3)

(cid:0) (cid:0)

6

3 x

B x

(4)

(cid:0) (cid:0)

A Z

300

500

Maximize

(cid:0) (cid:0)

4

Subject

) s e r c a s d e r d n u h ( B x

to x

400

(cid:0)

2

(cid:0) (cid:0)

xB > 0

2

8

10 6 4 xA (hundreds acres)

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

ệ

ả

Vô nghi m hay nghi m không kh thi (Infeasibility)

Maximize

300

Subject

(cid:0) (cid:0) Thay đổi ràng buộc 3 tới >= 3000, khi đó, không có phần giao của những ràng buộc tồn tại và nghiệm khả thi không thể đạt được 500

xA< 400

xA> 0

400

(1)

(cid:0)

10

600

(2)

(cid:0)

3xA +2 xB > 3000

B x

1800

(3)

(cid:0) (cid:0)

8

3 x

B x

(4)

(cid:0) (cid:0)

xB< 600

6

Maximize

300

500

(cid:0) (cid:0)

4

Subject

) s e r c a s d e r d n u h ( B x

to x

400

(cid:0)

2

600

(cid:0)

xB > 0

B x

3000

(cid:0) (cid:0)

2

8

10

3 x

B x

(cid:0) (cid:0)

6 4 xA (hundreds acres)

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

ệ

Đa nghi m (Multiple Optima)

Thay đổi hệ số hàm mục tiêu tới 200, khi đó hàm mục tiêu có cùng độ dốc với ràng buộc 3 và đa nghiệm tồn tại.

Maximize

300

500

Subject

(cid:0) (cid:0)

xA< 400

xA> 0

10

400

(1)

(cid:0)

600

(2)

(cid:0)

8 Z=1800=300xA +200xB

B x

1800

(3)

(cid:0) (cid:0)

3 x

B x

(4)

(cid:0) (cid:0)

xB< 600

6 ) s e r c a s d e r d n u h ( B x

Objective

300

200

4 3xA +2 xB < 1800

Subject to

400 (1)

(cid:0)

2

(cid:0)

xB > 0

600 (2) +

B x

1800 (3)

(cid:0)

(cid:0) (cid:0)

2

8

10

B x

0 (4)

6 4 xA (hundreds acres)

ả

ươ

ọ

Gi

ằ i LP b ng ph

ng pháp hình h c

 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

 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

 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

 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ới 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

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

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

Nghiệ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 ưu

Phươ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.

ươ

ơ

ả

Ph

ng pháp b ng đ n hình (Simplex Method)

Phương pháp đơn hình ứng dụng với dạng

chuẩn tắc của LP (Standard form)

a x = b j

= (cid:0)

c x j

Max/Min Ràng buộc

(cid:0)

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

Số biến quyết định: n Số phương trình: m n > m: hệ phương trình bất định

(cid:0)

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

 Những khái niệm: Ví dụ:

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

x1 + x2 + x3 = 200 3x1 + x2 + x4 = 300 x1, x2, x3, x4 ≥ 0

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

Hệ pt tất định: - Số biến, n = 4; số phương trình m = 2 - Nghiệm có thể đạt được bằng cách: Đặt (n-m) biến = 0; và giải hệ pt với m biến chưa biết ví dụ x1 = 0 và x2 = 0, giải hệ pt với x3 và x4 chưa biết, khi

đó:

 Biến x1 và x2 gọi là biến tự do  Biến x3 và x4 gọi là biến cơ sở

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

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

 Biến cơ sở và biến tự do  (n-m) biến quyến định được đặt = 0 biến tự do  m biến quyết định còn lại, và giá trị của nó đạt được bằng giải

hệ m phương trình với m ẩn số

biến cơ sở  Phương án cơ sở

Phương án cơ sở đạt đươc bằng cách đặt (n-m) biến chưa biết bằng 0 và tiến hành giải những đẳng thức rằng buộc cho m biến còn lại. 1 tập biến cơ sở đạt được sẽ tạo nên 1 PACS tương ứng

 Phương án cơ sở khả thi (phương án cơ sở chấp nhận

đươc): là phương án cơ sở đat được ứng với biến cơ sở nhận các giá trị không âm (≥ 0)  Số phương án cơ cở có thể có:

)

n ( m n m !

- Ví dụ n = 4; m = 2 Số phương án cơ sở tối đa = 6

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Về mặt hình học:  Phương án cơ sở: Điểm giao của 2 đường thẳng: các điểm cực trị

1 + x

 Phương án cơ sở khả thi: Điểm góc của không gian nghiệm khả thi

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

Vùng nghiệm khả thi

2 = 200

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình

Thuật toán tìm kiếm nghiệm tối ưu của bài toán LP tuân theo 2 điều kiện cơ bản:

(1)Điều kiện tối ưu: Điều kiện này đảm bảo rằng những phương án “không xấu” (so với phương án hiện hành) từng được xét đến

(2)Điều kiện khả thi: Điều kiện này đảm bảo rằng, xuất phát từ một phương án cơ sở khả thi, chỉ những phương án cở sở khả thi được liệt kê trong suốt quá trình tính toán

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình:  Chọn phương án cơ sở khả thi xuất phát: xuất phát từ bất cứ phương án cơ sở khả thi nào (thường lấy tại gốc tọa độ)

 Di chuyển từ một phương án cơ sở khả thi tới phương án cơ sở khả thi khác, vẫn duy trì tính khả thi và cải thiện hàm mục tiêu cho đến khi điểm tối ưu tìm được  Di chuyển từ một phương án cơ sở khả thi tới phương án cơ sở khả thi khác bằng việc thay thế một trong những biến cơ sở với một biến tự do và tính toán những thay đổi tương ứng trong biến cơ sở Biến đi vào: Biến cơ sở mới được thay thế cho biến cơ sở cũ Biến đi ra: Biến cơ sở cũ được loại bỏ để cho biến cơ sở mới thay vào

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình: Lựa chọn biến đi vào và biến đi ra  Biến đi vào: - Điều kiện tối ưu: lựa chọn một biến đi vào có tiềm năng

để cải thiện giá trị hiện hành của hàm mục tiêu. Biến đi vào được lựa chọn từ biến tự do trong dòng chứa hàm mục tiêu có hệ số âm lớn nhất cho bài toán tìm Max và hệ số dương lớn nhất cho bài toán tìm Min Độ lớn của hệ số hàm mục tiêu trình bày tốc độ thay đổi của hàm mục tiêu đó nhờ thay đổi một đơn vị trong biết quyết định Trong trường hợp có 2 hoặc nhiều hơn một biến đều thỏa mãn điều kiện chọn biến đi vào, khi đó có thể chọn tùy ý một trong số những biến đó

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình: Lựa chọn biến đi vào và biến đi ra  Biến đi ra: - Dựa trên điều kiện khả thi: chỉ những phương án cơ sở

i là

khả thi được liệt kê trong suốt quá trình tính toán Biến đi ra: biến cơ sở trong đó tương ứng có tỷ số(cid:0) nhỏ nhất (cho cả bài toán tìm Max và Min)

q = i

b i Với tất cả aik > 0 a ik

aik: hệ số trong biểu thức ràng buộc tương ứng với cột có chứa biến đi vào xk bi: hằng số bên phải (RHS) của các biểu thức ràng buộc Trong trường hợp 2 hoặc nhiều hơn một biến đều thỏa mãn điều kiện chọn biến đi ra, khi đó có thể chọn tùy ý một trong số những biến đó

(cid:0)

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình: Lựa chọn biến đi vào và biến đi ra

 Cột tương ứng với biến đi vào gọi là cột xoay  Dòng tương ứng với biến đi ra gọi là dòng xoay  Phần tử được đặt tại giao của cột xoay và dòng

xoay được gọi là phần tử xoay

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Thuật toán đơn hình: Tìm phương án cơ sở khả thi mới  Giá trị của những phần tử mới trong bảng đơn hình tương ứng với biến cơ sở và biến tự do mới được tính toán bằng phương pháp vận hành dòng (phương pháp Gauss- Jordan) Nguyên lý: Chuyển bảng đơn hình đi vào một bảng mới có giá trị là 1 tại phần tử xoay và giá trị là 0 tại những vị trí khác trong cột tương ứng với biến cơ sở mới, bao gồm cả dòng hàm mục tiêu Vận hành cho dòng xoay:

Dòng xoay mới = (Dòng xoay hiện tại) / (phần tử xoay) Vận hành cho các dòng còn lại (bao gồm cả dòng hàm mục tiêu)

Dòng mới = (Dòng hiện tại) – (Hệ số của cột xoay của dòng hiện tại) x (Dòng xoay mới)

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Vận hành Gauss

 Gọi aij trong dòng i và cột j là phần tử xoay  Giá trị của phần tử được đặt tại dòng k và cột l, là akl có thể được tính toán bằng công thức sau: •akl’ = (aklaij – akjail)/aij

ươ

ơ

ả

Ph

ng pháp b ng đ n hình

Kiểm tra điều kiện tối ưu

Phương án cơ sở khả thi hiện tại là tối ưu khi và chỉ khi mọi hệ số trong dòng hàm mục tiêu không âm (≥0) cho bài toán tìm Max và không dương (≤ 0) cho bài toán tìm Min

ươ

ơ

ả

ướ

ả

Ph

ng pháp b ng đ n hình: Các b

c gi

i

c x j

= j

(1) Chuyển LP gốc về dạng chuẩn tắc và thành lập bảng đơn hình.  Hàm mục tiêu được chuyển như sau:  Chọn phương án cơ sở khả thi xuất phát: nhận dạng ma trận đơn vị (2) Xét hệ số của dòng hàm mục tiêu z,

Nếu tất cả các phần tử trong dòng hàm mục tiêu đó là không âm (≥0) cho bài toán tìm Max và không dương (≤0) cho bài toán tìm Min, dừng tính toán, nghiệm tối ưu đã tìm được. Ngược lại, sang bước 3. (3) Lựa chọn biến đi vào: biến tự do trong dòng hàm mục tiêu có hệ số âm lớn nhất cho bài toán tìm Max và hệ số dương lớn nhất cho bài toán tìm Min. Cột chứa chứa biến tự do gọi là cột xoay.

(4) Xét hệ số của cột xoay: Nếu tất cả hệ số này là không dương (≤0),

nghiệm này là không biên. Nếu có ít nhất một phần tử là dương (>0), sang bước 5

b i a ik

q = (5) Tính toán: với aik > 0 i Biến cơ sở tương ứng với min((cid:0)

i), được chọn là biến đi ra

i) gọi là dòng xoay

Dòng tương ứng với min((cid:0) (6) Thiết lập bảng đơn hình mới dựa trên vận hành dòng (Gauss-Jordan) Lặp lại bước 1 cho đến khi tìm được phương án cơ sở tối ưu.

- (cid:0)

ươ

ơ

ả

ụ

Ph

ng pháp b ng đ n hình: ví d

Giải ví dụ 4 bằng phương pháp đơn hình

ZMax

300

500

x 1

Subject

(cid:0) (cid:0)

400

(cid:0)

x 1 x

600

(cid:0)

1800

2 x 1

(cid:0) (cid:0)

3 x 1

z - 300x1 - 500x2 - 0.x3 - 0.x4 - 0.x5 = 0 x1 + x3 = 400 (Giới hạn về diện tích đất cho cây trồng 1) x2 + x4 = 600 (Giới hạn về diện tích đất cho cây trồng 2) 3x1 + 2x2 +x5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) x1, x2, x3, x4,x5 ≥ 0 (Biến quyết định không âm) Số biến, n = 4; Số phương trình m = 2 Số biến tự do = 2; Số biến cơ sở = 2 Phương án cơ sở khả thi xuất phát: x1 = 0 và x2 = 0; x3= 200 và x4 = 300

(cid:0) (cid:0)

ươ

ơ

ả

ụ

Ph

ng pháp b ng đ n hình: ví d

Bảng đơn hình xuất phát

Hệ số của

bi/aik

Tên biến cơ sở

RHS (bi)

400

600

1800

900

x3 x4 x5 z

-300

-500

ươ

ơ

ả

ụ

Ph

ng pháp b ng đ n hình: ví d

Bảng đơn hình thứ 2

Hệ số của

bi/aik

Tên biến cơ sở

RHS (bi)

400

600

-2

600

200

x3 x2 x5 z

-300

500

300000

ươ

ơ

ả

ụ

Ph

ng pháp b ng đ n hình: ví d

Bảng đơn hình thứ cuối cùng

Hệ số của

bi/aik

Tên biến cơ sở

RHS (bi)

2/3

-1/3

200

600

-2/3

1/3

200

x3 x2 x1 z

100

300

360000

Phương án nghiệm tối ưu: 0 x1 = 200; x2 = 600; x3 = 200; x4 = 0, x= = 0 Z = 360000

ươ

ơ

ế

ạ

ả

Ph

ng pháp b ng đ n hình: Bi n nhân t o

Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0

Dạng chính tắc Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 – x3 = 15 3x1 + 5x2 + x4 = 60 x1 + x2 = 18 x1, x2, x3, x4 ≥ 0

 Phương án cơ sở khả thi xuất phát? (Biến cơ sở xuất phát)  Biến nhân tạo

ươ

ơ

ế

ạ

ả

Ph

ng pháp b ng đ n hình: Bi n nhân t o

 Trong bài toán LP mà biểu thức ràng buộc có dạng ≥, chúng ta phải tìm kiếm một phương án cơ sở khả thi xuất phát để ứng dụng thuật toán đơn hình thông thường

 Phương pháp nhân tạo đơn giản là một phép lừa toán học thông qua những biến nhân tạo, nhằm tạo khả năng ứng dụng thuật toán đơn hình thông thường để giải quyết bài toán LP

 Cho những biểu thức rằng buộc có dạng ≥, những rằng

buộc được viết như sau:

a x s +R =b i

j = 1

 Cho những biểu thức rằng buộc có dạng =, chúng

được viết lại như sau:

(cid:0)

a x +R =b

j= 1

Ri: Biến nhân tạo không âm (≥ 0)

(cid:0)

ươ

ơ

ế

ạ

ả

Ph

ng pháp b ng đ n hình: Bi n nhân t o

Ví dụ Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0

Dạng chính tắc Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 – x3 + R1 = 15 3x1 + 5x2 + x4 = 60 x1 + x2 + R2 = 18 x1, x2, x3, x4, R1, R2 ≥ 0

ươ

ơ

ế

ạ

ả

Ph

ng pháp b ng đ n hình: Bi n nhân t o

 Để giải bài toán có biến nhân tạo, ứng dụng phương

pháp đơn hình 2 giai đoạn (two-phase simplex method)  Giai đoạn 1: Ứng dụng phương pháp đơn hình để tìm

Min của hàm mục tiêu sau:

= (cid:0)

Min W

= 1

Ràng buộc: Những biểu thức ràng buộc của mô hình gốc dưới dạng chính tắc (bao gồm cả biến nhân tạo) K: tổng số biến nhân tạo trong mô hình,

 Giai đoạn 2: Bắt đầu từ phương án cơ sở khả thi đã

nhận dạng trong giai đoạn 1, ứng dụng phương pháp đơn hình để tối ưu bài toán gốc

 Trong trường hợp giai đoạn 1 kết thúc (nghĩa là tối ưu cho giai đoạn 1 đã đạt được), mà giá trị của W ≠ 0, khi đó bài toán gốc là vô nghiệm

ươ

ạ

ụ ử ụ Ví d s d ng ph

ế ng pháp bi n nhân t o

Dạng chuẩn tắc Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 – x3 + R1 = 15 3x1 + 5x2 + x4 = 60 x1 + x2 + R2 = 18 x1, x2, x3, x4, R1, R2 ≥ 0

Ví dụ 5 Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0

Giai đoạn 1

Tìm Min W = R1 + R2 Ràng buộc 2x1 + 3x2 – x3 + R1 = 15 3x1 + 5x2 + x4 = 60 x1 + x2 + R2 = 18 x1, x2, x3, x4, R1, R2 ≥ 0

ả

ươ

ạ

Gi

ế ng pháp bi n nhân t o

ử ụ ụ i ví d 5 s d ng ph Giai đoạn 1

Bảng đơn hình xuất phát cho giai đoạn 1

Hệ số của

x1 x2 x3 x4 R1 R2 RHS bik/ai Tên biến CS

Biến đi ra

2 3 -1 0 1 0 15 15/3 R1

3 5 0 1 0 60 60/5 x4 0 B

1 1 0 0 0 1 18 18/1 R2

W 3 4 0 0 0 33

Z -5 -8 -1 Biến đi vào 0 0 0 0 0

ả

ử ụ

ươ

ạ

Gi

ế ng pháp bi n nhân t o

ụ i Ví d 5 s d ng ph Giai đoạn 1

Bảng đơn hình cuối cùng cho giai đoạn 1

Hệ số của

Tên biến CS x1 x2 x3 x4 R1 R2 RHS bik/ai

1 1 0 0 0 1 18 x1

0 2 0 1 10/3 -3 6 x4

0 -1 1 0 -1 2 21 x3

B W 0 0 0 -1 -1 0

Z 0 -3 0 0 5 90

0 Giai đoạn 2 0 Bảng đơn hình xuất phát cho giai đoạn 2

Hệ số của

Tên biến CS x1 x2 x3 x4 RHS bik/ai

1 1 0 0 18 18/1 x1

0 2 0 1 6 6/2 x4

0 -1 1 0 21 - x3

Z 0 -3 0 0 90

ươ

ạ

ụ ử ụ Ví d s d ng ph

ế ng pháp bi n nhân t o

Giai đoạn 2

Bảng đơn hình cuối cùng cho giai đoạn 2

Hệ số của

Tên biến CS x1 x2 x3 x4 RHS bik/ai

B 1 0 0 -1/2 15 x1

0 1 0 1/2 3 x2

0 0 1 1/2 24 x3

Z 0 0 0 3/2 99

Phương án nghiệm tối ưu: x1 = 15; x2 = 3; Z = 99

ươ

ộ ố ườ

ả

ợ

ặ

ệ

Ph

ơ ng pháp b ng đ n hình: M t s tr

ng h p đ c bi

t

(1) Nghiệm suy thoái -

Một phương án nghiệm cơ sở khả thi là suy thoái nếu một vài biến cơ sở của nó có giá trị bằng 0 Sự hiện diện của nghiệm suy thoái chỉ ra rằng có tới hai hoặc nhiều hơn những phương án cơ sở cho giá trị hàm mục tiêu là như nhau Sự hiện diện của nghiệm suy thoái có thể dẫn tới một vài bước lặp bổ sung mà giá trị hàm mục tiêu vẫn không được cải thiện

Lặp BCS x4 RHS x1 x2 x3

1 4 1 0 8 0 X3

1 2 0 1 4 X4

-3 -9 0 0 0 Z

1/4 1 1/4 0 2 1 X2

1/2 0 -1/2 1 0 X4

-3/4 0 9/4 0 18 Z

0 1 1/2 -1/2 2 X2

1 0 -1 2 0 X1 2 (Nghiệm tối ưu)

0 0 3/2 3/2 18 Z

ươ

ộ ố ườ

ả

ợ

ặ

ệ

Ph

ơ ng pháp b ng đ n hình: M t s tr

ng h p đ c bi

t

(2) Phương án nghiệm không khả thi (vô nghiệm): Trong

bài toán có biến nhân tạo, nếu kết thúc của giai đoạn 1, tổng của các biến nhân tạo > 0, khi đó phương án là không khả thi.

BCS x1 x2 x3 x4 R1 RHS (b)

R1 -2 0 -1 -1 1 1

X2 0 1 0 1 0 1

W -2 0 -1 -1 0 1

Z -9 0 0 1 0 1

ươ

ộ ố ườ

ả

ợ

ặ

ệ

Ph

ơ ng pháp b ng đ n hình: M t s tr

ng h p đ c bi

t

(3) Nghiệm không bị chặn (nghiệm không biên):

Nghiệm không bị chặn có thể nhận dạng nếu tại bất cứ bước lặp nào, bất cứ ứng cử viên nào cho việc lựa chọn biến đi vào có hệ số là ≤ 0 trong những biểu thức rằng buộc

Tên biến cơ sở

RHS (bi)

bi/aik

Hệ số của x4

-1

x3 x4 z

-1

-2

ươ

ộ ố ườ

ả

ợ

ặ

ệ

Ph

ơ ng pháp b ng đ n hình: M t s tr

ng h p đ c bi

t

(4) Đa nghiệm: Nếu một trong những biến tự do có hệ số là 0 trong dòng hàm mục tiêu, đa nghiệm xuất hiện

Lặp BCS x1 x2 x3 x4 RHS

0 X3 1 2 1 0 5

X4 1 1 0 1 4

Z -2 -4 0 0 0

X2 1/2 1 1/2 0 5/2

X4 1/2 0 -1/2 1 3/2 1 (Nghiệm tối ưu)

Z 0 0 2 0 10

X2 0 1 1 -1 1

X1 1 0 -1 2 3 2 (Nghiệm thay thế)

Z 0 0 2 0 10

ộ

ạ

Phân tích đ nh y

Mục đích: Tìm hiểu ảnh hưởng của những thay đổi trong dữ liệu của mô hình tuyến tính gốc vào nghiệm tối ưu  Những thay đổi có thể diễn ra trong

• Những hệ số của hàm mục tiêu • Giá trị bên phải của những rằng buộc

 Nhận dạng tình trạng của nguồn và giá bóng

của chúng

ủ

ồ

ộ

ạ

Phân tích đ nh y – Tình tr ng c a ngu n

Trong nhiều bài toán LP, hệ số RHS trình bày giới hạn của nguồn, đặc biệt cho những ràng buộc loại ≤ - Ràng buộc không chặt (ràng buộc lỏng) (non-binding

constraints): Khi bài toán LP gốc đạt nghiệm tối ưu, trong phương án nghiệm tối ưu đó tồn tại một biến phụ có giá trị ≠ 0, biểu thức ràng buộc tương ứng với biến phụ đó gọi là ràng buộc không chặt Ràng buộc không chặt mang hàm ý nguồn là dư thừa

- Ngược lại là ràng buộc chặt (binding constraints): Ràng buộc chặt mang hàm ý nguồn là khan hiếm

Từ ví dụ 1 z - 2x1 - x2 - 0.x3 - 0.x4 = 0 (1) x1 + x2 + x3 = 200 (Giới hạn về diện tích đất) (2) 3x1 + x2 + x4 = 300 (Giới hạn về quỹ) x1, x2, x3, x4 ≥ 0 (Biến quyết định không âm)

Bảng đơn hình cuối cùng

Tên biến cơ sở

RHS (bi)

bi/aik

Hệ số của x4

3/2

-1/2

150

-1/2

1/2

x2 x1 z

1/2

250

Phương án nghiệm tối ưu: x1 = 50; x2 = 150; x3 = 0; x4 = 0 Z = 250 Ràng buộc chặt: 1 và 2 “Nguồn” được sử dụng hết

ộ

ạ

Phân tích đ nh y – Giá bóng

Trên một đơn vị giá trị của nguồn (Per unit worth of resources hoặc shadow price hoặc dual price) Trên một đơn vị giá trị của nguồn: Giá bóng (Shadow price): (cid:0) z/(cid:0) bi : tạo khả năng để ưu tiên phân bổ quỹ tương lai tới những nguồn khác Ràng buộc không chặt tương ứng với nguồn là dư thừa: Một sư tăng hoặc giảm của một đơn vị nguồn sẽ không có bất cứ ảnh hưởng nào vào quyết định phân bổ tối ưu hiện hành, (cid:0) z/(cid:0) bi = 0 Ràng buộc chặt tương ứng với nguồn là khan hiếm, khi đó mỗi đơn vị giá trị của nguồn (Giá bóng) không phải là bằng 0, (cid:0) z/(cid:0) bi ≠ 0 Ví dụ (cid:0) z/(cid:0) b1 = 2 Ý nghĩa: Một sự tăng nguồn 1 bởi một đơn vị, sẽ gây ra một sự tăng trong giá trị hàm mục tiêu là 2 đơn vị Thông tin này có thể được sử dụng để ưu tiên phân bổ tài chính bổ sung cho việc mở rộng quy mô hoặc vận hành

Từ ví dụ 1 z - 2x1 - x2 - 0.x3 - 0.x4 = 0 (1) x1 + x2 + x3 = 200 (Giới hạn về diện tích đất) (2) 3x1 + x2 + x4 = 300 (Giới hạn về quỹ) x1, x2, x3, x4 ≥ 0 (Biến quyết định không âm)

Bảng đơn hình cuối cùng

Tên biến cơ sở

RHS (bi)

bi/aik

Hệ số của x4

3/2

150

-1/2

1/2

250

1/2

x2 x1 z 0 Ràng buộc chặt: 1 và 2 (cid:0) z/(cid:0) b1 = 1/2 (Giới hạn về diện tích đất): Một sự tăng của một đơn vị diện tích đất (b1), có thể tăng giá trị của z bởi 0.5 đơn vị (cid:0) z/(cid:0) b2 = 1/2 (Giới hạn về quỹ): Một sự tăng của một đơn vị tiền tệ (b2), có thể tăng giá trị của z bởi 0.5 đơn vị

ế

ẫ

ố Mô hình tuy n tính đ i ng u (Dual LP Model)

Một mô hình tuyến tính đều có 2 vấn đề tương ứng với nó: - Mô hình tuyến tính gốc (Primal LP model) - Mô hình tuyến tính đối ngẫu (Dual LP model) Mối quan hệ giữa 2 mô hình này giúp: - Giảm mức độ tính toán so với mô hình tuyến tính gốc trong

một số trường hợp Ví dụ:

+ Nếu mô hình tuyến tính gốc có một số biến quyết định (n) ít nhưng số các biểu thức rằng buộc (m) lại nhiều (m > n) + Trong một số trường hợp giải LP gốc phải giới thiệu biến

nhân tạo

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

 Nếu LP gốc là bài toán tìm Max, khi đó Đối ngẫu là bài toán tìm Min (và ngược lại)

 Trong Đối ngẫu: Bài toán tìm Max sẽ có ràng

buộc loại ≤ và bài toán tìm Min sẽ có ràng buộc loại ≥

 Mỗi biểu thức ràng buộc trong LP gốc, sẽ tương ứng với một biến trong Đối ngẫu

 Mỗi hê số RHS của biểu thức rằng buộc trong LP gốc, sẽ là hệ số hàm mục tiêu tương ứng trong Đối ngẫu

 Mỗi biến trong LP gốc, sẽ tương ứng với một biểu thức rằng buộc tương ứng trong Đối ngẫu

 Biến quyết định trong cả LP gốc và đối ngẫu

đều không âm

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

Bài toán LP gốc dạng chính tắc

ax z =

c x j

Rang

buoc

(cid:0)

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

b i

(cid:0) (cid:0)

j x

(cid:0)

Bài toán đối ngẫu tương ứng

Min

b y i i

y = 0

1 buoc

Rang m

(cid:0)

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

y i

(cid:0) (cid:0)

= i y i

(cid:0)

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

Bài toán LP gốc dạng chuẩn tắc

ax z =

c x j

Rang

buoc

(cid:0)

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

b i

(cid:0)

j x

(cid:0)

Bài toán đối ngẫu tương ứng

Min

b y i i

y = 0

1 buoc

Rang m

(cid:0)

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

y i

(cid:0) (cid:0)

= i y i

(cid:0)

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

Ví dụ 6 Xây dựng mô hình tuyến tính đối ngẫu của Tìm Max

z = 3x1 + 4x2

Ràng buộc

5x1 + x2 ≥ 45 3x1 + 5x2 ≤ 72 2x1 + x2 ≤ 24 x1, x2 ≥ 0

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

Ví dụ 7 Xây dựng mô hình tuyến tính đối ngẫu của Tìm Min

z = 3x1 + 2x2

Ràng buộc

2x1 + x2 ≥ 10 -3x1 + 2x2 ≤ 6 x1 + x2 ≥ 6 x1, x2 ≥ 0

ự

ố

ế

ẫ

Xây d ng mô hình tuy n tính đ i ng u

Đối ngẫu của LP trong ví dụ 7 Max

w = 10y1 – 6y2 + 6y3

Ràng buộc

2y1 + 3y2 + y3 ≤ 3 y1 - 2y2 + y3 ≤ 2 y1, y2, y3 ≥ 0

ệ ữ

ẫ ạ ả

ố

ơ

M i quan h gi a LP g c và Đ i ng u t

ố i b ng đ n hình cu i cùng

x1 x2 x3 x4 x5 b y1 y2 y3 y4 y5 b

X1 1 0 -1 0 1 4 1 Y1 5 0 1 -1 1

X4 0 0 -5 1 7 14 0 Y3 -7 1 -1 -2 1

X2 0 1 1 0 -2 2 W 0 14 0 4 2 16

Z 0 0 -1 0 -1 16

LP gốc Đối ngẫu

Biến quyết định Biến phụ

Biến phụ Biến quyết định

Nghiệm tự do Nghiệm cơ sở

Nghiệm cơ sở Nghiệm tự do

X1, x2 Y4, y5

X3, x4, x5 Y1, y2, y3

ả

ề

ầ

Gi

ằ i bài toán LP b ng ph n m m

 Excel Solver

 Lingo: http://www.lindo.com/

Optimization modeling tool for linear, non-linear, and integer programming

 GAMS: http://www.gams.com/download/ (General Algebraic Modeling System)

Ứ

ủ

ụ

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:

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 và đất III. Bài toán về thiết kế hồ chứa IV. Bài toán về vận hành hồ chứa

Ứ

ụ

ng d ng LP trong TNN

I. Bài toán về mô hình quản lý chất lượng nước. Ví dụ 1.1: Một con sông nhận nước thải từ hai nguồn (site 1 và site 2).

Hiện nay, với không có bất cứ biện pháp xử lý nào tại những vị trí này, chỉ số chất lượng nước (như DO), qi (mg/l) tại vị trí 2 và 3 tiếp tục dưới nồng độ mong muốn Qi (chất lượng nước tại i được đo đạc ngay tại thượng lưu của điểm xả thải tại i). Cho mỗi đơn vị nước thải được loại bỏ tại i thượng lưu của j, chất lượng nước tại j được cải thiện bởi những hệ số chuyển đổi aij.

Vấn đề đặt ra là tìm mức độ xử lý nước thải tại vị trí 1 và 2 để đạt được nồng độ mong muốn tại vị trí 2 và 3 với tổng chi phí tối thiểu. Biết hiệu suất của nhà máy xử lý nước thải tại cả hai vị trí chỉ đạt 95% và yêu cầu tối thiểu 30% chất thải phải được loại bỏ tại cả hai vị trí trước khi chảy vào sông.

 W1 = 200; W2 = 100; q2 = 3, q3 = 2; Q2 = 7; Q3 = 6  a12 = 0.025; a13 = 0.0125; a23 = 0.025  C1 = 10; C2 = 6 (chi phí trên một đơn vị tỷ lệ nước thải

được loại bỏ)

Ứ

ụ

ng d ng LP trong TNN

I. Bài toán về mô hình quản lý chất lượng nước. Ví dụ 1.1 Nước thải tại vt1 trước khi xử lý : W1 Nước thải được loại bỏ: x1W1

Nước thải đi tại vt2 trước khi xử lý: W2 Nước thải được loại bỏ: x2W2

Park Site 1

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

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)

C1 C2

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

I. Bài toán về mô hình quản lý chất lượng nước. Ví dụ 1.2: Các nhà chức trách đã áp đặt tiêu chuẩn chất lượng nước đổ vào sông, như nồng độ của một chất gây ô nhiễm cụ thể không vượt qúa 120mg/l (0.12kg/m3) tại bất cứ điểm nào trong hệ thống sông như thể hiện trong hình vẽ 1-2. Bốn nhà máy đổ nước thải đã xử lý đi vào sông. Tải ô nhiễm từ những nguồn khác ngoài 4 nguồn trên giả sử bỏ qua. Những phương tiện xử lý được vận hành nhằm đáp ứng tiêu chuẩn chất lượng nước, với mục tiêu tối thiểu chi phí vận hành kết hợp hàng ngày của tất cả các nhà máy. Khi nước chảy xuống dưới hạ lưu, những quá trình tự nhiên cũng góp phần làm giảm tải ô nhiễm. Khối lượng chất ô nhiễm được giảm là phần trăm Pi,j nhờ các quá trình tự nhiên giữa vị trí i và ví trí j như sau

P1,3 = 10%; P2,3 = 20%; P3,4 = 15% Hiệu suất xử lý ô nhiễm của nhà máy sẽ giới hạn phần trăm tải ô

nhiễm có thể được loại bỏ trước khi đổ vào sông.

Số liệu được cho trong bảng 1-2. Tìm lượng chất ô nhiễm cần được loại bỏ tại mỗi nhà máy xử lý

trước khi đi vào sông với tối thiểu tổng chi phí xử lý.

Ứ

ụ

ng d ng LP trong TNN

I. Bài toán về mô hình quản lý chất lượng nước: Ví dụ 1.2

Hình 1-2: Minh họa cho ví dụ 1-2

Bảng 1-2 Số liệu cho ví dụ 1-2

Vị trí 1 2 3 4

510 430 960 920

Tải ô nhiễm được hình thành bởi thành phố (1,000 kg/ngày)

2.50$ 1.80$ 4.00$ 3.50$

Chi phí xử lý ($/1000kg được loại bỏ)

Hiệu suất lớn nhất của nhà máy 0.92 0.90 0.91 0.92

39.1 45.5 98.2 115

Tổng dòng chảy qua thành phố (m3/s)

3,378 3,931 8,484 9,936

Tổng dòng chảy được chuyển thành 1000m3/ngày

Ứ

ụ

ng d ng LP trong TNN

II. Bài toán về phân bổ nước Ví dụ 2.1: Phân bổ diện tích cây trồng -

Một huyện A gồm 3 xã: A1, A2 và A3. Văn phòng quy hoạch huyện hiện nay đang quy hoạch diện tích sản xuất nông nghiệp trong năm tới cho 3 xã Sản lượng nông nghiệp của mỗi xã bị giới hạn bởi diện tích đất trồng và sự phân bổ nước có sẵn cho tưới như bảng 2-1 Những cây trồng phù hợp cho huyện A này bao gồm: Lúa, Mía, Ngô với đặc tính yêu cầu cho mỗi loại cây trồng này như bảng 2-2 Tìm diện tích mỗi loại cây trồng nên được trồng cho mỗi xã của huyện A nhằm tối đa tổng lợi nhuận thực cho huyện đó?

Ứ

ụ

ng d ng LP trong TNN

II. Bài toán về phân bổ nước Ví dụ 2.1: Phân bổ diện tích cây trồng Bảng 2-1 Giới hạn về đất và nước cho mỗi xã

Xã

ướ ổ

ấ ẵ Đ t có s n cho cây ồ tr ng (ha) 200 250 150

ẵ N c có s n cho phân b (m3) 800000 1000000 500000

A1 A2 A3

ệ

ố

Bảng 2-2 Giới hạn về đất, nước và lãi suất cho mỗi cây trồng Cây tr ngồ i đa

ự Lãi th c ($/ha)

c cho

ầ ướ Nhu c u n ồ cây tr ng (m3/ha)

Di n tích t dành cho cây ồ tr ng (ha) 240 200 150

9500 6000 3000

2500 1800 600

Lúa Mía Ngô

Ứ

ụ

ng d ng LP trong TNN

II. Bài toán về phân bổ nước Ví dụ 2.2: Phân bổ nước giữa các nút nhu cầu -

Một lược đồ về hệ thống sông/ hồ chứa được trình bày như hình vẽ 2.1 Hồ chứa A và B được đặt tại vị trí 1 và 2, có tổng dung tích trữ lần lượt là 750x106 và 900x106 Lượng trữ ban đầu trong hồ chứa A và B tại bắt đầu của thời ký lần lượt là là 460x106 và 215x106 Xả nước từ hồ chứa phục vụ cho duy trì dòng chảy tối thiểu trong sông và tới mức độ có thể để đáp ứng mục tiêu cấp nước tại các nút nhu cầu. Dòng chảy tối thiểu cần được duy trì cho thời kỳ cụ thể đươc trình bày trong bảng 2.3 Nguồn cung cấp và nhu cầu được trình bày trong bảng 2.4 cho mỗi nút tương ứng với hình vẽ 2.1 Nếu nguồn cung cấp là không đủ để đáp ứng tất cả nhu cầu, phân bổ nước được tiến hành dựa vào quyền ưu tiên tương đối giữa các nút như trình bày trong bảng 2.4(quyền ưu tiên cao nhất ứng với chỉ số tương đối cao nhất). Tìm quyết định vận hành

Ứ

ụ

ng d ng LP trong TNN

II. Bài toán về phân bổ nước Ví dụ 2.2: Phân bổ nước giữa các nút nhu cầu Một lược đồ về hệ thống sông/ hồ chứa được trình bày như hình vẽ 2.1

x11

x10 x8

Ứ

ụ

ng d ng LP trong TNN

II. Bài toán về phân bổ nước Ví dụ 2.2: Phân bổ nước giữa các nút nhu cầu Bảng 2.3 Số liệu về yêu cầu dòng chảy tối thiểu tại các đoạn sông

14 0

23 5

34 10

ch y ả

45 10

D i 5ướ 30

Nhánh Dòng (106m3) Bảng 2.4 Số liệu về nguồn cung cấp và nhu cầu

ị ữ ế ướ V trí/nút tr ban ầ c u n c u tiên

6m3)

ậ ư ượ ng L ầ đ u (10 ả Dòng ch y đ n (nh p l u) (10 Nhu (106m3) ề ư Quy n ỉ ố theo ch s

1 2 3 4 5 460 215 375 290 25 75 120 90 125 475 360 4 3 2 5

Ứ

ụ

ng d ng LP trong TNN

III. Bài toán thiết kế hồ chứa 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

Qt

Y Rt

K

K: tổng dung tích của hồ (active storage volume capacity) Qt: Dòng chảy vào hồ tại thời kỳ t (inflow volume) Yt: 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ê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 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)

Ràng buộc về phương trình liên tục

Radng buộc vào khả năng trữ của hồ

Ví dụ 3.1 Cho Q (m3): Q1 = 10; Q2 = 5; Q3 = 30; Q4 = 20; Q5 = 15; Biết Y (Y chọn tùy ý) Tìm K, sao cho Kmin (1) Biến quyết định K, S1, S2, S3, S4, S5, R1, R2, R3, R4, R5 (2) Hàm mục tiêu: MinK (3) Ràng buộc - S1 + Q1 – Y – R1 = S2; S2 + Q2 – Y – R2 = S3; S3 + Q3 – Y – R3 = S4; S4 + Q4 – Y – R4 = S5 S5 + Q5 – Y – R5 = S1 - 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.2: 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.2 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ụ 3.1 cho K = 10

Ứ

ụ

ng d ng LP trong TNN

III.3: 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)

Rằng buộc về phương trình liên tục

Rằng buộc vào khả năng trữ của hồ

Ví dụ 3.3 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 - S1 + Q1 – Y – R1 = S2; S2 + Q2 – Y – R2 = S3; S3 + Q3 – Y – R3 = S4; S4 + Q4 – Y – R4 = S5 S5 + Q5 – Y – R5 = S1 - 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.3: 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.3: 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

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)