Bài giảng Mô hình quy hoạch tuyến tính

Chương 5 Mô hình quy hoạch tuyến tính Mục tiêu Hiểu các giả định căn bản và các tính chất của quy hoạch tuyến tính (LP). Giải các bài toán về Quy hoạch tuyến tính ở mức độ nhỏ và trung. Giải bằng đồ thị các bài toán quy hoạch tuyến tính gồm hai biến bằng phương pháp điểm góc và Isoline Mục tiêu (tt) Hiểu các trường hợp đặc biệt của quy hoạch tuyến tính: Tính không khả thi (infeasibility), không giới hạn (unboundedness), thừa (redundancy) và nhiều phương án tối ưu (alternative optima). Hiểu vai trò của phân tích độ nhạy. Sử dụng Excel để giải quyết các bài toán về quy hoạch tuyến tính. Ví dụ về ứng dụng LP thành công 1. Xây dựng một kế hoạch sản xuất đáp ứng được nhu cầu trong tương lai và đồng thời tối thiểu hóa chi phí sản xuất và lưu kho 2. Chọn lựa những sự kết hợp tối ưu về sản phẩm, về nguyên vật liệu để tối ưu hóa khả năng khai thác thời gian làm việc của máy móc và nhân công đồng thời tối đa hóa được lượng sản phẩm của doanh nghiệp. Ví dụ về ứng dụng LP thành công 3. Chọn cách tổ hợp nguyên vật liệu để đưa ra sản phẩm đạt yêu cầu với chi phí thấp nhất 4. Xác định được hệ thống phân phối sao cho tối thiểu hóa chi phí giao nhận từ nhiều kho đến nhiều điểm thị trường Các yêu cầu của LP Tất cả các vấn đề liên quan đến LP là để tìm kiếm giá trị tối đa hay tối thiểu lượng nào đó (hàm mục tiêu). Các hạn chế, ràng buộc là giới hạn cho phép để chúng ta đạt đến giá trị mục tiêu. Phải có phương án để chọn. Mục tiêu và giới hạn trong vấn đề quy hoạch tuyến tính phải được trình bày dưới dạng phương trình hoặc bất phương trình tuyến tính. Các giả định cơ bản của LP Tính chắc chắn Tính tỉ lệ Chia được Không âm Dữ liệu Cty Flair Furniture LN $7 $5 Giới hạn: 4T + 3C 240 (Mộc) 2T + 1C 100 (Sơn, đánh bóng) Mục tiêu : Max: 7T + 5C Các ràng buộc Bàn Miền nghiệm (feasible region) Đường Isoprofit Giải pháp tối ưu Giải pháp tối ưu Ví dụ Ví dụ Điểm góc Ví dụ Đường Isocost Các trường hợp đặc biệt của LP Hiện tượng không khả thi Nghiệm không giới hạn Hiện tượng thừa ràng buộc Nhiều hơn một nghiệm tối ưu Hiện tượng không có miền nghiệm Miền nghiệm không giới hạn (về phía phải) Hiện tượng thừa ràng buộc Hiện tượng nhiều nghiệm tối ưu Phân tích độ nhạy Các thay đổi ở hàm mục tiêu Hệ số hàm Các thay đổi nguồn lực