›
›

Bài giảng Quản lý vận hành - Module B: Quy hoạch tuyến tính

ppt 29 trang ngocly 790
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Quản lý vận hành - Module B: Quy hoạch tuyến tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_quan_ly_van_hanh_module_b_quy_hoach_tuyen_tinh.ppt

Nội dung text: Bài giảng Quản lý vận hành - Module B: Quy hoạch tuyến tính

  1. Quản lý Vận hành Quy hoạch tuyến tính Module B Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-1 07458 Management, 7e
  2. Những điểm chính YÊU CẦU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH THIẾT LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH  Ví dụ Shader Electronics GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BẰNG ĐỒ THỊ  Biểu diễn các ràng buộc bằng đồ thị  Phương pháp giải bằng đường đồng lợi nhuận (Iso-Profit Line Solution Method)  Phương pháp giải bằng điểm góc (Corner-Point Solution Method) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-2 07458 Management, 7e
  3. Những điểm chính – Tiếp theo PHÂN TÍCH ĐỘ NHẠY  Báo cáo độ nhạy  Thay đổi nguồn lực của các giá trị vế phải  Thay đổi hệ số trong hàm mục tiêu  GIẢI BÀI TOÁN CỰC TIỂU  CÁC ỨNG DỤNG QUY HOẠCH TUYẾN TÍNH  Ví dụ sản xuất hỗn hợp  Ví dụ bài toán thực đơn ăn kiêng  Ví dụ điều độ sản xuất  Ví dụ điều độ lao động  PHƯƠNG PHÁP ĐƠN HÌNH CỦA LP Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-3 07458 Management, 7e
  4. Các mục tiêu học tập Khi học xong chương này bạn sẽ có thể: Nhận biết được hoặc định nghĩa:  Hàm mục tiêu  Các ràng buộc  Vùng nghiệm khả dĩ hay chấp nhận được  Phương pháp đường đồng lợi nhuận/đồng chi phí  Giải pháp điểm góc (Corner-point solution)  Giá ngầm hay giá mờ (Shadow price) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-4 07458 Management, 7e
  5. Các mục tiêu học tập – Tiếp theo Khi học xong chương này bạn sẽ có thể: Mô tả hoặc giải thích:  Các thiết lập mô hình quy hoạch tuyến tính  Phương pháp đồ thị trong quy hoạch tuyến tính  Cách giải thích phân tích độ nhạy Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-5 07458 Management, 7e
  6. Quy hoạch tuyến tính là gì?  Kỹ thuật toán học  Chứ không phải lập trình bằng máy tính (Not computer programming)  Phân bổ các nguồn lực khan hiếm để đạt được một mục tiêu  Được khai sinh bởi (Pioneered by) George Dantzig trong Thế Chiến II  Đã đưa ra cách giải khả thi (workable solution) được gọi là phương pháp đơn hình vào năm 1947 Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-6 07458 Management, 7e
  7. Các ví dụ về ứng dụng LP thành công  Điều độ xe buýt chở học sinh nhằm cực tiểu tổng khoảng cách di chuyển khi chở học sinh  Phân các đội tuần tra của cảnh sát đến các khu vực có tỷ lệ tội phạm cao nhằm cực tiểu thời gian đáp lại các cú điện thoại đến số 911  Điều độ những người thu ngân tại các ngân hàng sao cho nhu cầu được đáp ứng trong mỗi giờ của ngày mà vẫn cực tiểu tổng chi phí lao động Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-7 07458 Management, 7e
  8. Các ví dụ về ứng dụng LP thành công – Tiếp theo  Chọn hỗn hợp nguyên liệu thô ở máy nghiền nạp liệu (feed mills) để làm ra các hỗn hợp nạp liệu hoàn chỉnh với chi phí thâp nhất  Lựa chọn phối hợp sản phẩm trong nhà máy nhằm tận dụng tốt nhất giờ máy và giờ lao động sẵn có mà vẫn cực đại lợi nhuận của doanh nghiệp  Phân phối chỗ cho một phối hợp người thuê ở một khu vực có nhiều cửa hàng mới nhằm cực đại tổng thu nhập cho công ty cho thuê Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-8 07458 Management, 7e
  9. Yêu cầu của bài toán quy hoạch tuyến tính 1 Phải tìm cách cực đại hoặc cực tiểu số lượng nào đó (hàm mục tiêu) 2 Có những hạn chế hoặc các ràng buộc – giới hạn khả năng đạt được mục tiêu 3 Phải là những đường lối hành động khác để chọn từ đó 4 Các mục tiêu và các ràng buộc phải có thể diễn đạt được dưới dạng các phương trình hoặc bất phương trình tuyến tính Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-9 07458 Management, 7e
  10. Thiết lập bài toán quy hoạch tuyến tính Giả định:  Bạn muốn sản xuất hai loại sản phẩm (1) Walkman AM/FM/Cassette và (2) Watch-TV  Walkman cần 4 giờ làm việc điện tử và 2 giờ lắp ráp  Watch-TV cần 3 giờ làm việc điện tử và 1 giờ lắp ráp  Hiện có 240 giờ làm việc điện tử và 100 giờ lắp ráp  Lãi trên một Walkman là 7$; lãi trên một Watch-TV 5$ Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-10 07458 Management, 7e
  11. Thiết lập bài toán quy hoạch tuyến tính – tiếp theo Cho:  X1 = số lượng Walkman  X2 = số lượng Watch-TV Thì:  4X1 + 3X2 240 ràng buộc về thời gian điện tử  2X1 + 1X2 100 ràng buộc về thời gian lắp ráp  7X1 + 5X2 = tiền lãi cực đại lợi nhuận Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-11 07458 Management, 7e
  12. Phương pháp giải bằng đồ thị  Vẽ đồ thị với trục tung & trục hoành (chỉ góc phần tư thứ nhất)  Vẽ đồ thị các ràng buộc như đường thẳng, rồi như mặt phẳng  Sử dụng (X1,0), (0,X2) cho đường thẳng  Tìm vùng nghiệm khả dĩ  Tìm nghiệm tối ưu  Phương pháp điểm góc  Phương pháp đường đồng lợi nhuận Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-12 07458 Management, 7e
  13. Công ty Shader Electronic Bài toán Số giờ cần thiết để sản xuất 1 đơn vị Bộ phận X1 X2 Số giờ sẵn có Walkmans Watch-TV trong tuần này Điện tử 4 3 240 Lắp ráp 2 1 100 Lãi/đơn vị 7$ 5$ Ràng buộc: 4x1 + 3x2 240 (số giờ điện tử) 2x1 + 1x2 100 (Số giờ lắp ráp) Mục tiêu: Cực đại: 7x1 + 5x2 Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-13 07458 Management, 7e
  14. Công ty Shader Electronic Các ràng buộc Điện tử 120 (Ràng buộc A) ) 2 Lắp ráp 100 (Ràng buộc B) TV (X TV 80 - 60 40 ợng Watch ợng ư 20 Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-14 07458 Management, 7e
  15. Công ty Shader Electronic Vùng nghiệm khả dĩ Điện tử 120 (Ràng buộc A) ) 2 100 Lắp ráp (Ràng buộc B) 80 TV (X TV - 60 40 Vùng nghiệm khả dĩ ợng Watch ợng ư 20 Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-15 07458 Management, 7e
  16. Công ty Shader Electronic Đường đồng lợi nhuận 120 Điện tử (Ràng buộcA) ) 100 2 Lắp ráp 80 (Ràng buộc B) TV (X TV - 60 Đường đồng 40 lợi nhuận ợng Watch ợng 20 ư Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-16 07458 Management, 7e
  17. Công ty Shader Electronic Giải pháp điểm góc Điện tử Đường đồng lợi nhuận (Ràng buộc A) ) Lắp ráp 2 120 (Ràng buộc B) 100 Nghiệm có thể TV (X TV - 80 tại các điểm góc 60 40 ợng Watch ợng ư 20 Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-17 07458 Management, 7e
  18. Công ty Shader Electronic Nghiệm tối ưu Điện tử (Ràng buộc A) Đường đồng lợi nhuận Lắp ráp ) 2 120 (Ràng buộc B) 100 Nghiệm có thể TV (X TV - 80 tại các điểm góc 60 40 Nghiệm tối ưu ợng Watch ợng ư 20 Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-18 07458 Management, 7e
  19. Công ty Shader Electronic nghiệm tối ưu Điện tử (Ràng buộc A) Đường đồng lợi nhuận Lắp ráp ) 2 120 (Ràng buộc B) 100 Nghiệm có thể TV (X TV - tại các điểm góc 80 X1 = 30 60 X2 = 40 40 Nghiệm tối ưu ợng Watch ợng ư 20 Số l Số 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-19 07458 Management, 7e
  20. Trình bày lời giải  Các biến quyết định  X1 = số tấn hoá chất BW sản xuất được  X2 = số tấn hoá chất Color sản xuất được  Mục tiêu  Cực tiểu Z = 2500X1 + 3000X2  Các ràng buộc  X1 30 (BW); X2 20 (Color)  X1 + X2 60 (Tổng lượng hàng)  X1 0; X2 0 (Không âm) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-20 07458 Management, 7e
  21. Các bước đơn hình cho bài toán cực đại 1. Chọn biến có Cj- Zj dương lớn nhất để đưa vào lời giải 2. Xác định hàng cần thay thế bằng cách chọn hàng mà có tỷ số giữa cột hằng số và các phần tử của cột xoay tương ứng (không âm) nhỏ nhất 3. Tính các giá trị mới cho hàng xoay 4. Tính các giá trị mới cho (các) hàng xoay khác 5. Tính các giá trị Cj và Cj-Zj cho bảng này. Nếu còn bất kỳ con số Cj-Zj nào lớn hơn 0, hãy trở về bước 1. Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-21 07458 Management, 7e
  22. Các bước đơn hình cho bài toán cực tiểu 1. Chọn biến có Cj- Zj âm lớn nhất để đưa vào lời giải 2. Xác định hàng cần thay thế bằng cách chọn hàng mà có tỷ số giữa cột hằng số và các phần tử của cột xoay tương ứng (không âm) nhỏ nhất 3. Tính các giá trị mới cho hàng xoay 4. Tính các giá trị mới cho (các) hàng xoay khác 5. Tính các giá trị Cj và Cj-Zj cho bảng này. Nếu còn bất kỳ con số Cj-Zj nào nhỏ hơn 0, hãy trở về bước 1. Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-22 07458 Management, 7e
  23. Phân tích độ nhạy Dự đoán nghiệm có thể thay đổi bao nhiêu nếu có những thay đổi trong các biến hoặc dữ liệu đầu vào. Giá mờ (đối ngẫu) – giá trị của một đơn vị nguồn lực tăng thêm Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-23 07458 Management, 7e
  24. Ví dụ bài toán cực tiểu Bạn là người phân tích cho một bộ BW: 2.500$ chi phận của Kodak, sản xuất các hoá phí sản xuất mỗi chất BW & color. Mỗi tháng phải tháng sản xuất tối thiểu 30 tấn BW và tối thiểu 20 tấn color. Toàn bộ số lượng hoá chất sản xuất được phải tối thiểu © 1995 Corel Corp. là 60 tấn. Cần sản xuất bao nhiêu tấn mỗi loại hoá chất để cực tiểu chi phí? Color: 3.000$ chi phí sản xuất mỗi tháng Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-24 07458 Management, 7e
  25. Lời giải bằng đồ thị X 80 2 Tìm các giá trị để BW ) X1 + X2 60. 2 X1 30, X2 20. 60 Tổng số Feasible 40 Region X1 20 Color Tấn, hoá chất Color (X Color chất hoá Tấn, 0 X1 0 20 40 60 80 Tấn, hoá chất BW (X1) Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-25 07458 Management, 7e
  26. Nghiệm tối ưu: Phương pháp điểm góc 80 BW Tìm các điểm góc 60 Tổng số Vùng nghiệm 40 khả dĩ B 20 Color Tấn, hoá chất Color chất hoá Tấn, A 0 0 20 40 60 80 Tấn, hoá chất BW Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-26 07458 Management, 7e
  27. RHS ràng buộc lắp ráp tăng 10 X2 100 Ràng buộc lắp ráp Nghiệm ban đầu ban đầu 80 Ràng buộc lắp ráp 60 tăng 10 Nghiệm mới 40 Vùng nghiệm Nghiệm khả dĩ Ràng buộ 20 Nghiệm điện tử 0 X1 0 20 40 60 Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-27 07458 Management, 7e
  28. RHS ràng buộc lắp ráp giảm 10 X2 100 Nghiệm Ràng buộc mới lắp ráp 80 ban đầu Nghiệm 60 Sol’n ban đầu 40 Nghiệm Ràng buộc lắp ráp 20 giảm 10 0 X1 0 20 40 60 Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-28 07458 Management, 7e
  29. Bài toán cực tiểu 60 50 x1 + x2 = 60 Vùng nghiệm 40 khả dĩ 30 b 20 a X = 30 X = 20 10 1 2 0 0 10 20 30 40 50 60 Transparency Masters to accompany Heizer/Render – © 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. Principles of Operations Management, 5e, and Operations B-29 07458 Management, 7e