Thuyết trình: Quy hoạch tuyến tính

Thuyết trình: q nêu Các yêu cầu của 1 bài toán quy hoạch tuyến tính, xây dựng bài toán quy hoạch tuyến tính, cách giải bài toán quy hoach tuyến tính bằng đồ thị, thể hiện các ràng buộc trên đồ thị ,phương pháp giải dùng đường đẳng nhuận, phương pháp góc - điểm.
Nội dung trích xuất từ tài liệu:
Thuyết trình: Quy hoạch tuyến tính Quy Hoạch Tuyến Tính Linear Programming GVHD: TS. Phạm Văn Lâm Nhóm 8 Bùi Hồng Ngọc Nguyễn Văn Thuận Phan Thanh Hải Hồ Nguyễn Phước Thành Lê Nguyên Khôi © 2008 Prentic e Hall, Inc . B–1 Nội dung  Các yêu cầu của 1 bài toán Quy Hoạch Tuyến Tính  Xây dựng bài toán Quy Hoạch Tuyến Tính  Ví dụ về Shader Electronics © 2008 Prentice Hall, Inc . B–2 Nội dung  Cách giải bài toán Quy Hoach Tuyến Tính bằng đồ thị  Thể hiện các Ràng buộc trên đồ thị  Phương pháp giải dùng Đường Đẳng Nhuận  Phương pháp Góc-Điểm © 2008 Prentice Hall, Inc . B–3 Nội dung  Phân tích mức độ nhạy cảm  Bản mô tả mức độ nhạy cảm  Thay đổi giá trị nguồn lực phía bên phải.  Thay đổi hệ số hàm mục tiêu  Giải bài toán Tối thiểu hóa © 2008 Prentice Hall, Inc . B–4 Nội dung  Ứng dụng Bài toán Quy Hoạch Tuyến Tính  Bài toán Kết hợp sản xuất  Bài toán về chế độ thức ăn  Bài toán về kế hoạch làm việc nhân công  Phương pháp đơn hình © 2008 Prentic e Hall, Inc . B–5 Mục tiêu Khi hoàn thành, bạn sẽ có khả năng: 1. Xây dựng các mô hình bài toán LP, gồm một hàm mục tiêu và hệ ràng buộc. 2. Giải bài toán bằng đồ thị, dung phương pháp Đường đẳng nhuận. 3. Giải bài toán bằng đồ thị, dùng phương pháp Góc-Điểm. © 2008 Prentic e Hall, Inc . B–6 Mục tiêu Khi hoàn thành, bạn có thể: 4. Phân tích độ nhạy và các mức giá ảo 5. Xây dựng và giải bài toán Tối thiểu hóa (minimization) 6. Xây dựng bài toán Kết hợp sản xuất, bài toán Chế độ thức ăn, và bài toán Kế hoạch làm việc cho nhân công. © 2008 Prentice Hall, Inc . B–7 Quy Hoạch Tuyến Tính (LP)  Một phương pháp toán học giúp lên kế hoạch và ra các quyết định về bố trí các nguồn lực.  Giúp tìm ra giá trị tối đa hoặc tối thiểu của đối tượng.  Đảm bảo cách giải quyết tối ưu cho mô hình được xây dựng. © 2008 Prentic e Hall, Inc . B–8 Các ứng dụng của LP 1. Lên lịch chạy cho xe buýt trường học để giảm thiểu tổng quãng đường di chuyển. 2. Bố trí các đơn vị tuần tra cảnh sát đến những khu tội phạm trọng điểm để giảm thiểu thời gian trả lời các cuộc gọi 911 3. Lên kế hoạch làm việc cho Giao dịch viên tại các ngân hàng nhằm đáp ứng nhu cầu trong mọi thời điểm trong khi giảm thiểu chi phí nhân công. © 2008 Prentic e Hall, Inc . B–9 Các ứng dụng của LP 4. Lựa chọn kết hợp sản phẩm tại 1 nhà máy để sử dụng hiệu quả nhất các thiết bị máy móc trong khi tối đa hóa lợi nhuận. 5. Pha trộn nguyên liệu trong máy nghiền thức ăn để tạo ra hỗn hợp thức ăn với chi phí thấp nhất 6. Quyết định hệ thống phân phối sao cho chi phí vận chuyển ở mức thấp nhất © 2008 Prentic e Hall, Inc . B – 10 Các ứng dụng của LP 7. Xây dựng quy trình sản xuất thỏa mãn nhu cầu tương lai về sản phẩm của 1 doanh nghiệp đồng thời tối thiểu hóa chi phí sản xuất và chi phí tồn kho 8. Phân bố không gian kết hợp cho các khách thuê trong một trung tâm thương mại để tối đa hóa doanh thu cho một công ty chuyên cho thuê bất động sản. © 2008 Prentic e Hall, Inc . B – 11 Các yêu cầu của một bài toán LP 1. Bài toán LP hướng đến việc tối đa hóa hoặc Tối thiểu hóa một giá trị nào đó (thường là lợi nhuận hoặc chi phí). Đây là Hàm Mục Tiêu. 2. Các Ràng buộc (Constraint) giới hạn mức độ của mục tiêu mà ...