zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

» Môi trường

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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PPTX | Số trang:34

Báo xấu

84
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương 5 Kỹ thuật tối ưu trong TNN Quy hoạch tuyến tính trong TNN
Dạng chung của LP v Dạng tổng quát n a ij x j / /= b j n j =1 Max 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
Hai dạng cơ bản của LP 1. Dạng chuẩn tắc (standard form) n n a ij x j = b j j =1 Max/ Min z= cj xj Ràng buộc j =1 xj 0, 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
Hai dạng cơ bản của LP 2. Dạng chính tắc (canonical form) n Max z= cj xj j =1 Rà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à Max Ví dụ
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) Để 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ình thành bài toán 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 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/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 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 100 x1 + 1150 x2 + 350 x3 + Rằng buộc về đáp ứng chất lượng nước 600 x1 + x2 + x3 + Rằng buộc về biến quyết định không âm x1, x2, x3 ≥ 0
Giải LP bằng phương pháp hình học 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 hơn
Giải LP bằng phương pháp hình học Giải ví dụ 1 Max z = 2x1 + x2 Với rằng buộc x1 + x2 ≤ 200 3x1 + x2 ≤ 300 x1, x2 ≥ 0 x2 3x +1 x2 =3 00 Điểm tối ưu (50,150) 2x 1 + x1 x2 +x 2= = 20 0 0 x1
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 Max z = x1 + x2 x2 = 4 4 Ràng buộc x1 + 2x2 ≥ 2 3 x1 ≤ 3 Vùng x1 = 3 2 nghiệm x2 ≤ 4 khả thi x1 ≥ 0 x2 ≥ 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 Đa Min z = x1 – x2 nghiêm 4 Rằng buộc 4 1/3 = 1/3 x1 + x2 ≤ 4 x1 + 2 3 2x x2 = 4 + x1 -2x1 + 2x2 ≤ 4 -2 x1 ≤ 3 2 Vùng x1 ≥ 0 x2 ≥ 0 nghiệm x1 = 3 1 khả thi 0 0 1 2 3 x1
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 1 = -x1 - x2 ≤ -2 3 x2 + 1 -x -x1 + x2 ≤ 1 2 x1 ≥ 0 x2 ≥ 0 1 -x 1 -x 2 = -2 0 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 ≤ 2 -x1 + x2 ≤ -1 3 -x x1 x1 - x2 ≤ -1 -1 2 = x2 + x1 ≥ x2 ≥ 1 0 0 -x x1 1 + x2 = 1 0 0 1 2 3 x1
Giải LP bằng phương pháp hình học 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 góc của khối đa diện đó v 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 v 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.
Ứ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 III. Bài toán về xác định mối quan hệ Dung tích hồ ~ lượng xả cho nhu cầu IV. Bài toán về xác định chính sách vận hành hồ tối ưu

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.