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

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

Báo xấu

74
lượt xem 3
download

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

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" trình bày 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,... 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 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

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 1 Dạng chung của bài toán tuyến tính 2 Hình thành bài toán tuyến tính 3 Phương pháp hình học 4 Phương pháp bảng đơn hình 5 Phân tích độ nhạy 6 Chương trình tuyến tính đối ngẫu 7 Ứng dụng QHTT trong QH&QLNN
Dạng chung của LP  Dạng tổng quát n a ij x j / /= b j n j =1 Max or min: z= cjxj ràng 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í dụ: Max z = 5x1 + 8x2 Ràng buộc 2x1 + 3x2 ≥ 15 3x1 + 5x2 ≤ 60 x1 + x2 = 18 www.themegallery.com x1, x2 ≥ 0 Company Logo
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= cjxj 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= cjxj 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
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 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: (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) 5 10 20 Nguồn nước có sẵn (106l/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
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 Diện tích tối đa (acres) 400 600  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)? 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 Z 300 x A 500 xB Subjectto xA 400 (1) xA> 0 xA< 400 10 xB 600 (2) 3x A 2 xB 1800 (3) 8 xA 0 xB 0 (4) xB (100 acres) xB< 600 6 4 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 Objective Z 300x A 500x B Ví dụ 4 xA> 0 xA< 400 10 Z=3600=300xA +500xB (200, 600) xB (hundreds acres) 8 xB< 600 6 Z=2000=300xA +500xB 4 Z=1000=300xA +500xB 2 xB > 0 2 4 6 8 10 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 xA> 0 xA< 400 Maximize Z 300 x A 500 xB 10 Subjectto xA 400 (1) xB (hundreds acres) 8 unbounded xB 600 (2) 3x A 2 xB 1800 (3) 6 xA 0 xB 0 (4) Maximize Z 300 x A 500 xB 4 Subject to 2 xA 400 xB > 0 xA 0 xB 0 2 4 6 8 10 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) 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 Maximize Z 300 x A 500 xB Subjectto xA> 0 xA< 400 10 xA 400 (1) 3xA +2 xB > 3000 xB 600 (2) xB (hundreds acres) 8 3x A 2 xB 1800 (3) xA 0 xB 0 (4) xB< 600 6 Maximize Z 300 x A 500 xB 4 Subject to xA 400 2 xB > 0 xB 600 3x A 2 xB 3000 2 4 6 8 10 xA 0 xB 0 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 Z 300 x A 500 xB Subjectto xA> 0 xA< 400 xA 400 (1) 10 xB (hundreds acres) xB 600 (2) 3x A 2 xB 1800 (3) 8 Z=1800=300xA +200xB xA 0 xB 0 (4) xB< 600 6 Objective Z = 300 x A + 200 xB 4 3xA +2 xB < 1800 Subject to xA 400 (1) 2 xB 600 (2) xB > 0 3 x A + 2 xB 1800 (3) xA 0 xB 0 (4) 2 4 6 8 10 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.

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.