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

Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-1Quản lýVận hànhQuy hoạch tuyến tínhModule BTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-2Những điểm chínhYÊU CẦU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNHTHIẾT LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNHVí dụ Shader ElectronicsGIẢ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 – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-3Những điểm chính – Tiếp theoPHÂN TÍCH ĐỘ NHẠYBáo cáo độ nhạyThay đổi nguồn lực của các giá trị vế phảiThay đổi hệ số trong hàm mục tiêuGIẢI BÀI TOÁN CỰC TIỂUCÁC ỨNG DỤNG QUY HOẠCH TUYẾN TÍNHVí dụ sản xuất hỗn hợpVí dụ bài toán thực đơn ăn kiêngVí dụ điều độ sản xuấtVí dụ điều độ lao độngPHƯƠNG PHÁP ĐƠN HÌNH CỦA LPTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-4Khi 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êuCác ràng buộcVùng nghiệm khả dĩ hay chấp nhận đượcPhươ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)Các mục tiêu học tậpTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-5Khi 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ínhPhương pháp đồ thị trong quy hoạch tuyến tínhCách giải thích phân tích độ nhạyCác mục tiêu học tập – Tiếp theoTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-6Kỹ thuật toán họcChứ 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 1947Quy hoạch tuyến tính là gì?Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-7Đ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 sinhPhâ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 độngCác ví dụ về ứng dụng LP thành côngTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-8Các ví dụ về ứng dụng LP thành công – Tiếp theoChọ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ấtLự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ệpPhâ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 – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-9Yêu cầu của bài toánquy hoạch tuyến tínhPhả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)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êuPhải là những đường lối hành động khác để chọn từ đó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ínhTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-10Thiết lập bài toán quy hoạch tuyến tínhGiả định:Bạn muốn sản xuất hai loại sản phẩm (1) Walkman AM/FM/Cassette và (2) Watch-TVWalkman cần 4 giờ làm việc điện tử và 2 giờ lắp rápWatch-TV cần 3 giờ làm việc điện tử và 1 giờ lắp rápHiện có 240 giờ làm việc điện tử và 100 giờ lắp rápLãi trên một Walkman là 7$; lãi trên một Watch-TV 5$Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-11Thiết lập bài toán quy hoạch tuyến tính – tiếp theoCho:X1 = số lượng WalkmanX2 = số lượng Watch-TVThì:4X1 + 3X2  240 ràng buộc về thời gian điện tử2 X1 + 1X2  100 ràng buộc về thời gian lắp ráp7X1 + 5X2 = tiền lãi cực đại lợi nhuậnTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-12Vẽ đồ 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ẳngSử dụng (X1,0), (0,X2) cho đường thẳngTìm vùng nghiệm khả dĩTìm nghiệm tối ưuPhương pháp điểm gócPhương pháp đường đồng lợi nhuậnPhương pháp giải bằng đồ thịTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-13Công ty Shader Electronic Bài toán Số giờ cần thiết đểsản xuất 1 đơn vịBộ phậnX1WalkmansX2Watch-TVSố giờ sẵn cótrong tuần nàyĐiện tử43240Lắp ráp21100Lã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 + 5x2Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-14Công ty Shader Electronic Các ràng buộc02040608010012001020304050607080Số lượng Walkman (X1)Số lượng Watch-TV (X2)Điện tử(Ràng buộc A)Lắp ráp(Ràng buộc B)Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-15Công ty Shader Electronic Vùng nghiệm khả dĩ02040608010012001020304050607080Số lượng Walkman (X1)Số lượng Watch-TV (X2)Vùng nghiệmkhả dĩĐiện tử(Ràng buộc A)Lắp ráp(Ràng buộc B)Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-16Công ty Shader Electronic Đường đồng lợi nhuận02040608010012001020304050607080Số lượng Walkman (X1)Số lượng Watch-TV (X2)7*X1 + 5*X2 = 2107*X1 + 5*X2 = 420Điện tử(Ràng buộcA)Lắp ráp(Ràng buộc B)Đường đồnglợi nhuậnTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-17Công ty Shader Electronic Giải pháp điểm góc02040608010012001020304050607080Số lượng Walkman (X1)Số lượng Watch-TV (X2)Đường đồng lợi nhuậnĐiện tử(Ràng buộc A)Lắp ráp(Ràng buộc B)Nghiệm có thể tại các điểm gócTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-18Công ty Shader Electronic Nghiệm tối ưu02040608010012001020304050607080Số lượng Walkman (X1)Số lượng Watch-TV (X2)Nghiệm tối ưuĐường đồng lợi nhuậnĐiện tử(Ràng buộc A)Lắp ráp(Ràng buộc B)Nghiệm có thể tại các điểm gócTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-19Công ty Shader Electronic nghiệm tối ưu020406080100120010203040507080Số lượng Walkman (X1)Số lượng Watch-TV (X2)Nghiệm tối ưuĐường đồng lợi nhuậnĐiện tử(Ràng buộc A)Lắp ráp(Ràng buộc B)X1 = 30X2 = 4060Nghiệm có thể tại các điểm gócTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-20Các biến quyết định X1 = số tấn hoá chất BW sản xuất đượcX2 = số tấn hoá chất Color sản xuất đượcMục tiêuCực tiểu Z = 2500X1 + 3000X2Các ràng buộcX1  30 (BW); X2  20 (Color)X1 + X2  60 (Tổng lượng hàng)X1  0; X2  0 (Không âm)Trình bày lời giảiTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-21Các bước đơn hình cho bài toáncực đạiChọn biến có Cj- Zj dương lớn nhất để đưa vào lời giảiXá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ấtTính các giá trị mới cho hàng xoayTính các giá trị mới cho (các) hàng xoay khácTí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 – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-22Các bước đơn hình cho bài toáncực tiểuChọn biến có Cj- Zj âm lớn nhất để đưa vào lời giảiXá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ấtTính các giá trị mới cho hàng xoayTính các giá trị mới cho (các) hàng xoay khácTí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 – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-23Phân tích độ nhạyDự đ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êmTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-24Bạn là người phân tích cho một bộ phận của Kodak, sản xuất các hoá chất BW & color. Mỗi tháng phải 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 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í?BW: 2.500$ chi phí sản xuất mỗi thángColor: 3.000$ chi phí sản xuất mỗi tháng© 1995 Corel Corp.Ví dụ bài toán cực tiểuTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-25Lời giải bằng đồ thịX1Feasible Region0204060800Tấn, hoá chất Color (X2)20406080Tấn, hoá chất BW (X1)BWColorTổng sốTìm các giá trị để X1 + X2  60.X1  30, X2  20.X1X2Transparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-26Nghiệm tối ưu: Phương pháp điểm gócVùng nghiệmkhả dĩ0204060800Tấn, hoá chất Color20406080Tấn, hoá chất BWBWColorTổng sốABTìm các điểm gócTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-27RHS ràng buộc lắp ráp tăng 10X10204060801000204060Ràng buộclắp rápban đầuRàng buộc lắp ráptăng 10NghiệmNghiệmX2Nghiệmban đầuRàng buộđiện tửNghiệmmớiVùng nghiệm khả dĩTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-28RHS ràng buộc lắp ráp giảm 10X10204060801000204060Ràng buộclắp rápban đầuSol’nNghiệmX2Ràng buộclắp rápgiảm 10Nghiệmban đầuNghiệmmớiTransparency Masters to accompany Heizer/Render – Principles of Operations Management, 5e, and Operations Management, 7e© 2004 by Prentice Hall, Inc., Upper Saddle River, N.J. 07458B-29Bài toán cực tiểuVùng nghiệm khả dĩX1 = 30X2 = 20x1 + x2 = 60ab