intTypePromotion=1

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

Chia sẻ: Tằng Túy | Ngày: | Loại File: PPT | Số trang:29

0
51
lượt xem
5
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Module B gồm có những nội dung chính sau: 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, giải bài toán quy hoạch tuyến tính bằng đồ thị, phân tích độ nhạy, giải bài toán cực tiểu, các ứng dụng quy hoạch tuyến tính, phương pháp đơn hình của LP. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-1 River, N.J. 07458 Management, 5e, and Operations 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) © 2004 by Prentice Hall, Inc., Upper Saddle Transparency Masters to accompany Heizer/Render – Principles of Operations B-2 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-3 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-4 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-5 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-6 River, N.J. 07458 Management, 5e, and Operations 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 B-7 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-8 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-9 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-10 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-11 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-12 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-13 River, N.J. 07458 Management, 5e, and Operations Management, 7e
  14. Công ty Shader Electronic Các  ràng buộc Điện tử 120 (Ràng buộc A) Số lượng Watch­TV (X2) 100 Lắp ráp (Ràng buộc B) 80 60 40 20 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-14 River, N.J. 07458 Management, 5e, and Operations Management, 7e
  15. Công ty Shader Electronic  Vùng nghiệm khả dĩ Điện tử 120 (Ràng buộc A) Lắp ráp Số lượng Watch­TV (X2) 100 (Ràng buộc B) 80 60 40 Vùng nghiệm khả dĩ 20 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-15 River, N.J. 07458 Management, 5e, and Operations Management, 7e
  16. Công ty Shader Electronic  Đường đồng lợi nhuận 120 Điện tử (Ràng buộcA) 100 7*X1 + 5*X2 = 420 Số lượng Watch­TV (X2) Lắp ráp 80 (Ràng buộc B) 60 Đường đồng 40 7*X lợi nhuận 1  + 5 *X 20 2  = 2 10 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-16 River, N.J. 07458 Management, 5e, and Operations Management, 7e
  17. Công ty Shader Electronic  Giải pháp điểm góc Điện tử Đường đồng lợi  (Ràng buộc A) nhuận Lắp ráp Số lượng Watch­TV (X2) 120 (Ràng buộc B) 100 Nghiệm có thể  80 tại các điểm góc 60 40 20 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-17 River, N.J. 07458 Management, 5e, and Operations 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 Số lượng Watch­TV (X2) 120 (Ràng buộc B) 100 Nghiệm có thể  80 tại các điểm góc 60 40 Nghiệm tối ưu 20 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-18 River, N.J. 07458 Management, 5e, and Operations 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 Số lượng Watch­TV (X2) 120 (Ràng buộc B) 100 Nghiệm có thể  tại các điểm góc 80 X1 = 30 60 X2 = 40 40 Nghiệm tối ưu 20 0 0 10 20 30 40 50 60 70 80 Số lượng Walkman (X1) Transparency Masters to accompany © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-19 River, N.J. 07458 Management, 5e, and Operations 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 © 2004 by Prentice Hall, Inc., Upper Saddle Heizer/Render – Principles of Operations B-20 River, N.J. 07458 Management, 5e, and Operations Management, 7e
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2