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

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.
Nội dung trích xuất từ tài liệu:
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 TNNKỹthuậttốiưutrongTNN Mộtsốkỹthuậtcụthể QuyhoạchtuyếntínhtrongTNN Contents1 Dạng chung của bài toán tuyến tính2 Hình thành bài toán tuyến tính3 Phương pháp hình học4 Phương pháp bảng đơn hình5 Phân tích độ nhạy6 Chương trình tuyến tính đối ngẫu7 Ứng dụng QHTT trong QH&QLNN DạngchungcủaLP Dạng tổng quát n a ij x j / /=b j n j =1Max 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 = 18www.themegallery.com x1, x2 ≥ 0 CompanyLogo 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= cjxj 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= cjxj 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à Max 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) 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 HaidạngcơbảncủaLPVí dụ:Max z = 5x1 + 7x2Với ràng buộc 3x1 + 4x2 ≤ 15 2x1 + 3x2 ≥ 6 x1, x2 ≥ 0 HìnhthànhbàitoánLPVí 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ìnhthànhbàitoánLPVí 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) để ...