Bài giảng Kỹ thuật tối ưu trong tài nguyên nước - Một số kỹ thuật cụ thể

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 
Contents 
Phân tích độ nhạy 
5 
Dạng chung của bài toán tuyến tính 
1 
Hình thành bài toán tuyến tính 
2 
Phương pháp hình học 
3 
Phương pháp bảng đơn hình 
4 
Ứng dụng QHTT trong QH&QLNN 
7 
Chương trình tuyến tính đối ngẫu 
6 
Company Logo 
www.themegallery.com 
Dạng chung của LP 
Dạng tổng quát 
Max or min:	 ràng buộc 
	 c j : Hệ số hàm mục tiêu 
	a ij : Hệ số trong các biểu thức ràng buộc 
	b j : hệ số vế bên phải của biểu thức ràng buộc (RHS) 
Ví dụ: Max z = 5x 1 + 8x 2 
	 Ràng buộc 
	2x 1 + 3x 2 ≥ 15 
	3x 1 + 5x 2 ≤ 60 
	x 1 + x 2 = 18 
	x 1 , x 2 ≥ 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 x j 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 x j 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 
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 
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 
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. 
Để 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 = 5x 1 + 7x 2 
Với ràng buộc 
	3x 1 + 4x 2 ≤ 15 
	2x 1 + 3x 2 ≥ 6 
	x 1 , x 2 ≥ 0 
Hai dạng cơ bản của LP 
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 m 3 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: 
Tầng ngậm nước ngầm và 
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 150x10 6 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: 
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 
Nguồn 1 
Nguồn 2 
Nguồn 3 
Chi phí (1000$/10 6 l/ngày) 
5 
10 
20 
Nguồn nước có sẵn (10 6 l/ngày) 
25 
120 
100 
Độ cứng (mg/l) 
100 
1150 
350 
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 
Dự án tưới 
Lượng nước tối đa: 1800 acre-feet/năm 
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 
x A = Diện tích cây trồng A nên trồng (acres)? 
x B = Diện tích cây trồng B nên trồng (acres)? 
1,800 acre feet = 2,220,267 m 3 
400 acre = 1,618,742 m 2 
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 
Diện tích tối đa (acres) 
400 
600 
Ví dụ 4 
Giải LP bằng phương pháp hình học 
Ví dụ 4 
2 
4 
6 
8 
10 
2 
4 
6 
8 
10 
x A (100 acres) 
x B (100 acres) 
x B < 600 
x A > 0 
x A < 400 
3x A +2 x B < 1800 
x B > 0 
Giải LP bằng phương pháp hình học 
Ví dụ 4 
2 
4 
6 
8 
10 
2 
4 
6 
8 
10 
x A (hundreds acres) 
x B (hundreds acres) 
x B < 600 
x A > 0 
x A < 400 
x B > 0 
Z=3600=300x A +500 x B 
Z=2000=300x A +500 x B 
Z=1000=300x A +500 x B 
(200, 600) 
Giải LP bằng phương pháp hình học 
Nghiệm không bị chặn (Unounded Solution) 
2 
4 
6 
8 
10 
2 
4 
6 
8 
10 
x A (hundreds acres) 
x B (hundreds acres) 
x A > 0 
x A < 400 
x B > 0 
unbounded 
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 
Giải LP bằng phương pháp hình học 
Vô nghiệm hay nghiệm không khả thi (Infeasibility) 
2 
4 
6 
8 
10 
2 
4 
6 
8 
10 
x A (hundreds acres) 
x B (hundreds acres) 
x B < 600 
x A > 0 
x A < 400 
3x A +2 x B > 3000 
x B > 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 
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. 
2 
4 
6 
8 
10 
2 
4 
6 
8 
10 
x A (hundreds acres) 
x B (hundreds acres) 
x B < 600 
x A > 0 
x A < 400 
x B > 0 
Z=1800=300x A +200 x B 
3x A +2 x B < 1800 
Giải LP bằng phương pháp hình học 
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) 
Max/Min Ràng buộc 
Số biến quyết định: n 
Số phương trình: m 
n > m: hệ phương trình bất định 
Phương pháp bảng đơn hình 
Những khái niệm : Ví dụ: 
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ở 
Max z = 2x 1 + x 2 
Với rằng buộc 
	x 1 + x 2 ≤ 200 
	3x 1 + x 2 ≤ 300 
	x 1 , x 2 ≥ 0 
Max z = 2x 1 + x 2 
Với rằng buộc 
	x 1 + x 2 + x 3 = 200 
	3x 1 + x 2 + x 4 = 300 
	x 1 , x 2 , x 3 , x 4 ≥ 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ó: 
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ị 
Phương án cơ sở khả thi: Điểm góc của không gian nghiệm khả thi 
x 1 
x 2 
x 1 + x 2 = 200 
3x 1 + x 2 = 300 
Điểm tối ưu (50,150) 
Vùng nghiệm khả thi 
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: 
Đ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 
Đ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ở 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ố  i là nhỏ nhất (cho cả bài toán tìm Max và Min) 
 Với tất cả a ik > 0 
	a ik : 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 x k 
	b i : 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 đó 
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) 
Vận hành Gauss 
Gọi a ij 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à a kl có thể được tính toán bằng công thức sau: 
a kl ’ = (a kl a ij – a kj a il )/a ij 
Phương pháp bảng đơn hình 
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 
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 
(5) 	Tính toán: với a ik > 0 
	 Biến cơ sở tương ứng với min( i ), được chọn là biến đi ra 
 Dòng tương ứng với min( i ) gọi là dòng xoay 
(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. 
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 
z - 300x 1 - 500x 2 - 0.x 3 - 0.x 4 - 0.x 5 = 0 
x 1 + x 3 = 400 (Giới hạn về diện tích đất cho cây trồng 1) 
x 2 + x 4 = 600 (Giới hạn về diện tích đất cho cây trồng 2) 
3x 1 + 2x 2 +x 5 = 1800 (Giới hạn về diện tích đất cho cả 2 cây trồng) 
 x 1 , x 2 , x 3 , x 4 ,x 5 ≥ 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: x 1 = 0 và x 2 = 0; x 3 = 200 và x 4 = 300 
Tên biến cơ sở 
Hệ số của 
x 1 
x 2 
x 3 
x 4 
x5 
RHS (bi) 
b i /a ik 
x 3 
1 
0 
1 
0 
0 
400 
- 
x 4 
0 
1 
0 
1 
0 
600 
600 
x 5 
3 
2 
0 
0 
1 
1800 
900 
z 
-300 
-500 
0 
0 
0 
0 
Bảng đơn hình xuất phát 
z - 300x 1 - 500x 2 - 0.x 3 - 0.x  ... ở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 
	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 
Phân tích độ nhạy – Tình trạng của nguồn 
Tên biến cơ sở 
Hệ số của 
x 1 
x 2 
x 3 
x 4 
RHS (bi) 
b i /a ik 
x 2 
0 
1 
3/2 
-1/2 
150 
x 1 
1 
0 
-1/2 
1/2 
50 
z 
0 
0 
1/2 
1/2 
250 
Bảng đơn hình cuối cùng 
Từ ví dụ 1 
z - 2x 1 - x 2 - 0.x 3 - 0.x 4 = 0 
(1) x 1 + x 2 + x 3 = 200 (Giới hạn về diện tích đất) 
(2) 3x 1 + x 2 + x 4 = 300 (Giới hạn về quỹ) 
 x 1 , x 2 , x 3 , x 4 ≥ 0 (Biến quyết định không âm) 
Phương án nghiệm tối ưu: 
x 1 = 50; x 2 = 150; x 3 = 0; x 4 = 0 
Z = 250 
Ràng buộc chặt: 1 và 2 
“Nguồn” được sử dụng hết 
	 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): z/ b i : 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, z/ b i = 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, z/ b i ≠ 0 
Ví dụ z/ b 1 = 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 
Phân tích độ nhạy – Giá bóng 
Tên biến cơ sở 
Hệ số của 
x 1 
x 2 
x 3 
x 4 
RHS (bi) 
b i /a ik 
x 2 
0 
1 
3/2 
-1/2 
150 
x 1 
1 
0 
-1/2 
1/2 
50 
z 
0 
0 
1/2 
1/2 
250 
Bảng đơn hình cuối cùng 
Từ ví dụ 1 
z - 2x 1 - x 2 - 0.x 3 - 0.x 4 = 0 
(1) x 1 + x 2 + x 3 = 200 (Giới hạn về diện tích đất) 
(2) 3x 1 + x 2 + x 4 = 300 (Giới hạn về quỹ) 
 x 1 , x 2 , x 3 , x 4 ≥ 0 (Biến quyết định không âm) 
Ràng buộc chặt: 1 và 2 
 z/ b 1 = 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ị 
 z/ b 2 = 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ộ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 
Mô hình tuyến tính đối ngẫu (Dual LP Model) 
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 
Bài toán đối ngẫu tương ứng 
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 
Bài toán đối ngẫu tương ứng 
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 = 3x 1 + 4x 2 
Ràng buộc 
	5x 1 + x 2 ≥ 45 
	3x 1 + 5x 2 ≤ 72 
	2x 1 + x 2 ≤ 24 
	x 1 , x 2 ≥ 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 = 3x 1 + 2x 2 
Ràng buộc 
	2x 1 + x 2 ≥ 10 
	-3x 1 + 2x 2 ≤ 6 
	x 1 + x 2 ≥ 6 
	x 1 , x 2 ≥ 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 = 10y 1 – 6y 2 + 6y 3 
Ràng buộc 
	2y 1 + 3y 2 + y 3 ≤ 3 
	y 1 - 2y 2 + y 3 ≤ 2 
	y 1 , y 2 , y 3 ≥ 0 
Xây dựng mô hình tuyến tính đối ngẫu 
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 
X1 
1 
0 
-1 
0 
1 
4 
X4 
0 
0 
-5 
1 
7 
14 
X2 
0 
1 
1 
0 
-2 
2 
Z 
0 
0 
-1 
0 
-1 
16 
y1 
y2 
y3 
y4 
y5 
b 
Y1 
1 
5 
0 
1 
-1 
1 
Y3 
0 
-7 
1 
-1 
-2 
1 
W 
0 
14 
0 
4 
2 
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:  
	Optimization modeling tool for linear, non-linear, and integer programming 
GAMS:  
( General Algebraic Modeling System) 
Ứ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ước 
Bài toán về phân bổ nước và đất 
Bài toán về thiết kế hồ chứa 
Bài toán về vận hành hồ chứa 
Ứng dụng LP trong TNN 
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), q i (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; q 2 = 3, q 3 = 2; Q 2 = 7; Q 3 = 6 
a 12 = 0.025; a 13 = 0.0125; a 23 = 0.025 
C 1 = 10; C 2 = 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 
Bài toán về mô hình quản lý chất lượng nước. Ví dụ 1.1 
Ứng dụng LP trong TNN 
Nước thải tại vt1 trước khi xử lý : W 1 
Nước thải được loại bỏ: x 1 W 1 
Nước thải đi tại vt2 trước khi xử lý: W 2 
Nước thải được loại bỏ: x 2 W 2 
Site 1 
Site 2 
Site 3 
Park 
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 nhờ một đơn vị nước thải được loại bỏ tại i (a ij ) 
a 12 
a 13 và a 23 
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à x i ) 
C 1 
C 2 
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% 
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 
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 
Ứng dụng LP trong TNN 
Vị trí 
1 
2 
3 
4 
Tải ô nhiễm được hình thành bởi thành phố (1,000 kg/ngày) 
510 
430 
960 
920 
Chi phí xử lý ($/1000kg được loại bỏ) 
2.50$ 
1.80$ 
4.00$ 
3.50$ 
Hiệu suất lớn nhất của nhà máy 
0.92 
0.90 
0.91 
0.92 
Tổng dòng chảy qua thành phố (m3/s) 
39.1 
45.5 
98.2 
115 
Tổng dòng chảy được chuyển thành 1000m3/ngày 
3,378 
3,931 
8,484 
9,936 
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ã 
Bảng 2-2 Giới hạn về đất, nước và lãi suất cho mỗi cây trồng 
Ứng dụng LP trong TNN 
Xã 
Đất có sẵn cho cây trồng (ha) 
Nước có sẵn cho phân bổ (m3) 
A1 
200 
800000 
A2 
250 
1000000 
A3 
150 
500000 
Cây trồng 
Diện tích tối đa dành cho cây trồng (ha) 
Nhu cầu nước cho cây trồng (m3/ha) 
Lãi thực ($/ha) 
Lúa 
240 
9500 
2500 
Mía 
200 
6000 
1800 
Ngô 
150 
3000 
600 
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à 750x10 6 và 900x10 6 
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à 460x10 6 và 215x10 6 
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 
Ứng dụng LP trong TNN 
x 1 
x 2 
x 3 
x 4 
x 5 
x 6 
x 7 
x 8 
x 9 
x 10 
x 11 
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 
Ứng dụng LP trong TNN 
Bảng 2.4 Số liệu về nguồn cung cấp và nhu cầu 
Nhánh 
1-4 
2-3 
3-4 
4-5 
Dưới 5 
Dòng chảy (10 6 m 3 ) 
0 
5 
10 
10 
30 
Vị trí/nút 
Lượng trữ ban đầu (10 6 m 3 ) 
Dòng chảy đến (nhập lưu) (10 6 m 3 ) 
Nhu cầu nước (10 6 m 3 ) 
Quyền ưu tiên theo chỉ số 
1 
460 
375 
90 
4 
2 
215 
290 
125 
3 
3 
- 
25 
475 
2 
4 
- 
75 
- 
- 
5 
- 
120 
360 
5 
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 
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 
S t + Q t – Y – R t = S t+1 
S t+1 = S 1 
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ồ 
S t ≤ K cho tất cả t 
Ứng dụng LP trong TNN 
Q t 
R t 
K 
S t 
Y 
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) 
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 
Biến quyết định K, S1, S2, S3, S4, S5, R1, R2, R3, R4, R5 
Hàm mục tiêu: MinK 
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; 
S4 + Q4 – Y – R4 = S5 
S5 + Q5 – Y – R5 = S1 
Radng 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.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) 
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 
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; 
S4 + Q4 – Y – R4 = S5 
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.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) 
Ứng dụng LP trong TNN 
Y (m3) 
K (m3) 
5 
0 
10 
5 
12.5 
10 
15 
15 
16 
18 
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 
S t + Q t – Y t - E t – R t = S t+1 
S t+1 = S 1 
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ồ 
S t ≤ K cho tất cả t 
(3) Ràng buộc vào đáp ứng nhu cầu cấp nước 
Y t ≤ D t 
(4) Ràng buộc vào biến không âm 
St ≥ 0 
Rt ≥ 0 
Ứng dụng LP trong TNN 
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ụ 4.1: Tìm đường St+1 ~ t bằng LP biết K = 350 
Ứng dụng LP trong TNN 
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 
Ứng dụng LP trong TNN