tailieunhanh - 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,. nội dung chi tiết. | 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 Dạng chung của LP Dạng tổng quát Max or min: ràng buộc 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 x1, x2 ≥ 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 xj 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 xj 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 = 5x1 + 7x2 Với ràng buộc 3x1 | 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 Dạng chung của LP Dạng tổng quát Max or min: ràng buộc 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 x1, x2 ≥ 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 xj 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 .