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

  • Số trang: 48 |
  • Loại file: PDF |
  • Lượt xem: 24 |
  • Lượt tải: 0
nganguyen

Đã đăng 34173 tài liệu

Mô tả:

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à ta có thể theo đuổi. © 2008 Prentic e Hall, Inc . B – 12 Các yêu cầu của bài toán LP 3. Phải có các phương án hành động thay thế để doanh nghiệp lựa chọn. 4. Mục tiêu và Các ràng buộc trong bài toán LP phải được mô tả dưới dạng phương trình tuyến tính hay bất đẳng thức. © 2008 Prentic e Hall, Inc . B – 13 Xây dựng bài toán LP Bài toán kết hợp sản phẩm tại Shader Electronics  Hai sản phẩm 1. Shader Walkman 2. Shader Watch - TV  Quyết định cách phối hợp các sản phẩm để tạo ra lợi nhuận cao nhất © 2008 Prentic e Hall, Inc . B – 14 Xây dựng bài toán LP Số giờ cần thiết để sx 1 đv sp Bộ phận Kĩ thuật điện tử Lắp ráp Lợi nhuận của 1 đv sp Walkman (X1) Watch TV (X2) 4 2 3 1 $7 $5 Số giờ có trong tuần Các biến số quyết định: X1 = số lượng Walkman cần sx X2 = số lượng Watch-TV cần sx © 2008 Prentic e Hall, Inc . 240 100 B – 15 Xây dựng bài toán LP Hàm mục tiêu: Tối đa hóa lợi nhuận = $7X1 + $5X2 Có 3 loại ràng buộc  Cận trên quy định nguồn lực sử dụng ≤ nguồn lực hiện có  Cận dưới quy định nguồn lực sử dụng ≥ nguồn lực hiện có  Đẳng thức thể hiện nguồn lực sử dụng = nguồn lực hiện có © 2008 Prentic e Hall, Inc . B – 16 Xây dựng bài toán LP Ràng buộc 1: Thời gian sx kĩ thuật điện tử dùng đến ≤ Thời gian sx điện tử có sẵn 4X1 + 3X2 ≤ 240 (số giờ của sx điện tử) Ràng buộc 2: Thời gian lắp ráp dùng đến ≤ Thời gian lắp ráp có sẵn 2X1 + 1X2 ≤ 100 (số giờ lắp ráp) © 2008 Prentic e Hall, Inc . B – 17 Cách giải bằng đồ thị  Có thể dùng khi có 2 biến số quyết định 1. Phác họa các phương trình giới hạn tại các mức giới hạn bằng cách chuyển các phương trình thành đẳng thức. 2. Xác định miền khả thi 3. Xác định một đường đẳng nhuận (đường thể hiện lợi nhuận bằng nhau) dựa trên hàm mục tiêu. 4. Di chuyển đường này ra ngoài cho đến khi xác định được điểm tối ưu © 2008 Prentic e Hall, Inc . B – 18 Cách giải bằng đồ thị X2 100 – Số lượng Watch-TV – 80 – Lắp ráp (Ràng buộc B) – 60 – – 40 – Điện tử (Ràng buộc A) – 20 – Miền khả thi – |– 0 | | 20 | | 40 | | 60 | | 80 | | 100 X1 Số lượng Walkman © 2008 Prentic e Hall, Inc . B – 19 Cách giải bằng đồ thị Phương pháp sử dụng đường đẳng nhuận (Iso-Profit Line) Chọn 1 giá trị khả thi cho hàm mục tiêu $210 = 7X1 + 5X2 Tìm ra trục chặn của hàm và vẽ ra X2 = 42 © 2008 Prentic e Hall, Inc . X1 = 30 B – 20
- Xem thêm -