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

Thêm vào BST

Báo xấu

83
lượt xem 6
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

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
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 (IsoProfit Line Solution Method) Phương pháp giải bằng điểm góc (CornerPoint 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
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
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 (Cornerpoint 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
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
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
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
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
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
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) WatchTV Walkman cần 4 giờ làm việc điện tử và 2 giờ lắp ráp WatchTV 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 WatchTV 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
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 WatchTV 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
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
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 WatchTV 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
Công ty Shader Electronic Các ràng buộc Điện tử 120 (Ràng buộc A) Số lượng WatchTV (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
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 WatchTV (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
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 WatchTV (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
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 WatchTV (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
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 WatchTV (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
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 WatchTV (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
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