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

Bài giảng "Phân tích hệ thống tài nguyên nước - Chương 5: Kỹ thuật tối ưu trong TNN (Quy hoạch tuyến tính trong TNN)" trình bày các dạng chung của LP, hai dạng cơ bản của LP, hình thành bài toán LP, giải LP bằng phương pháp hình học,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích hệ thống tài nguyên nước: Chương 5 - Ngô Lê An Chương5 KỹthuậttốiưutrongTNNQuyhoạchtuyếntínhtrongTNN DạngchungcủaLPv Dạng tổng quát n a ij x j / /=b j n j =1Max or min: z= c j xràng j buộc j =1 xj 0, 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)v Ví dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 x1, x2 ≥ 0 HaidạngcơbảncủaLP1. Dạng chuẩn tắc (standard form) n n a ij x j =b j j =1Max/ Min z= cj xj Ràng buộc j =1 xj 0, i = 1,2,...,m j = 1,2,...,nVí 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 HaidạngcơbảncủaLP2. Dạng chính tắc (canonical form) nMax z= cj xj j =1Ràng buộc n a ij x j b i j =1 xj 0, 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à MaxVí dụ HaidạngcơbảncủaLP3. 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 HìnhthànhbàitoánLP1. 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ìnhthànhbàitoánLP1. 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 Nguồn được liệt 1 kê như sau: 2 Nguồn Nguồn 3 Chi phí (1000$/l/ngày) 5 10 20 Nguồn nước có sẵn (l/ngày) 25 120 100 Độ cứng (mg/l) 100 1150 350()) Tổng độ cứng cho phép của nước cấp vào thành phố là 600mg/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ươnglai của thành phố với chi phí tối thiểu, trong khi vẫn duy trì chất lượng củanước trong giời hạn cho phép HìnhthànhbàitoánLP1. 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)) ...