QUI HOẠCH TUYẾN TÍNH

CHƯƠNG 2QUI HOẠCH TUYẾN TÍNHKết thúc chương này, sinh viên có thể: 1. Nắm được những thành phần và các dạng khác nhau của bài toán 2. Có thể thực hiện chuyển đổi giữa các dạng bài toán 3. Xây dựng bài toán 4. Nắm được các phương pháp giải các bài toán 5. Hiểu được bài toán đối ngẫu và thực hiện biến đổi giữa bài toán đối ngẫu và bài toán gốc 6. Hiểu được phân tích độ nhạy và sử dụng chúng trong phân tích 7. Biết được các bài toán qui hoạch nguyên và ứng dụng...
Nội dung trích xuất từ tài liệu:
QUI HOẠCH TUYẾN TÍNHCHƯƠNG 2 QUI HOẠCH TUYẾN TÍNHKết thúc chương này, sinh viên có thể: 1. Nắm được những thành phần và các dạng khác nhau của bài toán 2. Có thể thực hiện chuyển đổi giữa các dạng bài toán 3. Xây dựng bài toán 4. Nắm được các phương pháp giải các bài toán 5. Hiểu được bài toán đối ngẫu và thực hiện biến đổi giữa bài toán đối ngẫu và bài toán gốc 6. Hiểu được phân tích độ nhạy và sử dụng chúng trong phân tích 7. Biết được các bài toán qui hoạch nguyên và ứng dụng của nó 8. Sử dụng được các phần mềm phổ biến để giải các bài toán Mục lục 26 2.1. Đặt vấn đề 2.2. Những dạng bài toán qui hoạch2.3. Những phương pháp giải bài toán qui hoạch tuyến tính 2.4. Bài toán đối ngẫu 2.5. Phân tích độ nhạy 2.6. Qui hoạch nguyên 2.1. Đặt vấn đề 27Trong thực tế, tồn tại nhiều bài toán qui hoạch tuyến tính đápứng nhiều nhu cầu khác nhau trong nghiên cứu. Tuy nhiên, xéttheo hàm mục tiêu, các bài toán qui hoạch tuyến tính có thểchia thành hai bài toán cơ bản sau: Bài toán cực đại, Bài toán cực tiểu.Cách thức xây dựng, dạng và các thành phần của bài toán nàynhư thế nào? 2.1.1. Bài toán cực đại đơn giản 28 ABC là công ty nhỏ chuyên sản xuất sản phẩm hoá chất. Trong quá trình sản xuất, có 3 nguyên liệu thô được dùng để sản xuất 2 sản phẩm: chất phụ gia, bazơ hoà tan. Ba nguyên liệu thô được pha trộn thành chất phụ gia và bazơ hoà tan như trên Bảng: Sản phẩm Khả năng cung ứng (tấn) Chất phụ gia Bazơ hoà tanNguyên liệu 1 0,4 0,5 20Nguyên liệu 2 0,2 5Nguyên liệu 3 0,6 0,3 21Lợi nhuận mỗi tấn 40 30 Xây dựng bài toán 29Xác định biến quyết định F = số tấn chất phụ gia được sản xuất B = số tấn bazơ hoà tan được sản xuấtHàm mục tiêu : Max 40F + 30BCác ràng buộc 0,4F + 0,5B ≤ 20 Nguyên liệu 1 0,2B ≤ 5 Nguyên liệu 2 0,6F + 0,3B ≤ 21 Nguyên liệu 3 F, B ≥ 0 2.1.2. Bài toán cực tiểu đơn giản 30Công ty hoá chất M&D sản xuất 2 sản phẩm A và B để bán làmnguyên liệu cho các công ty sản xuất xà phòng. Dựa trên mứctồn kho hiện tại và nhu cầu tiềm tàng cho tháng tới, các nhàquản trị xác định tổng mức sản xuất trong tháng tới của cả haisản phẩm ít nhất 350 galông. Riêng sản phẩm A phải không íthơn 125 galông. Thời gian để sản xuất sản phẩm A, B tươngứng là 2 giờ/galông và 1giờ/galông. Trong tháng đến, tổng quỹthời gian là 600 giờ. Chi phí sản xuất sản phẩm A và B tươngứng là 2$/galông và 3$/galông. Mục tiêu của công ty M&D làcực tiểu tổng chi phí sản xuất. Xây dựng bài toán 31Ký hiệu: A = số galông sản phẩm A được sản xuất, B = số galông sản phẩm B được sản xuất.Bài toán: Min 2A+3B Ràng buộc 1A ≥ 125 Nhu cầu của sản phẩm A 1A+1B ≥ 350 Nhu cầu tổng 2 sản phẩm 2A+1B ≤ 600 Thời gian sản xuất A,B ≥ 0 2.1.3. Những ký hiệu chung của bài toán QHTT 32Ký hiệu: x1= số tấn chất phụ gia được sản xuất x2= số tấn chất bazơ hoà tan được sản xuấtKhi đó, bài toán RMC có dạng như sau: Max (40x1 + 30x2) Ràng buộc 0,4x1 + 0,5x2 ≤ 20 Nguyên liệu 1 0,2x2 ≤ 5 Nguyên liệu 2 0,6x1 + 0,3x2 ≤ 21 Nguyên liệu 3 x1, x2 ≥ 0 2.1.3. Những ký hiệu chung của bài toán QHTT 33Ký hiệu: x1= số galông sản phẩm A được sản xuất x2= số galông sản phẩm B được sản xuấtKhi đó, bài toán M&D sẽ có dạng như sau:Min (2x1+3x2)Ràng buộc 1x1 ≥ 125 Nhu cầu của sản phẩm A 1x1+1x2 ≥ 350 Nhu cầu tổng các sản phẩm 2x1+1x2 ≤ 600 Thời gian sản xuất x1, x2 ≥ 0 2.2. Những dạng bài toán qui hoạch 342.2.1. Những thành phần của bài toán2.2.2. Các dạng bài toán qui hoạch tuyến tính2.2.3. Biến đổi dạng của bài toán qui hoạch a. Đưa dạng tổng quát về dạng chính tắc b. Đưa dạng chính tắc về dạng chuẩn 2.2.1. Những thành phần của bài toán 35Hàm mục tiêu (Objective function), đ ...