Quy hoạch tuyến tính - Linear Programming

© 2008 Prentice Hall, Inc. B – 1 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 Prentice Hall, Inc. B – 2 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 – 3 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 – 4 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 – 5 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 Prentice Hall, Inc. B – 6 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 Prentice Hall, Inc. B – 7 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 – 8 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 Prentice Hall, Inc. B – 9 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 Prentice Hall, Inc. B – 10 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 Prentice Hall, Inc. B – 11 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 Prentice Hall, Inc. B – 12 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 Prentice Hall, Inc. B – 13 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 Prentice Hall, Inc. B – 14 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 Prentice Hall, Inc. B – 15 Xây dựng bài toán LP Walkman Watch TV Số giờ Bộ phận (X1) (X2) có trong tuần Số giờ cần thiết để sx 1 đv sp Kĩ thuật điện tử 4 3 240 Lắp ráp 2 1 100 Lợi nhuận của 1 đv sp $7 $5 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 Prentice Hall, Inc. B – 16 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 Prentice Hall, Inc. B – 17 Xây dựng bài toán LP Ràng buộc 2: 2X1 + 1X2 ≤ 100 (số giờ lắp ráp) Thời gian lắp ráp có sẵn Thời gian lắp ráp dùng đến ≤ Ràng buộc 1: 4X1 + 3X2 ≤ 240 (số giờ của sx điện tử) Thời gian sx điện tử có sẵn Thời gian sx kĩ thuật điện tử dùng đến ≤ © 2008 Prentice Hall, Inc. B – 18 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 Prentice Hall, Inc. B – 19 Cách giải bằng đồ thị 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 S ố l ư ợ n g W a tc h -T V Số lượng Walkman X1 X2 Lắp ráp (Ràng buộc B) Điện tử (Ràng buộc A) Miền khả thi © 2008 Prentice Hall, Inc. B – 20 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 X1 = 30 © 2008 Prentice Hall, Inc. B – 21 Cách giải bằng đồ thị 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 S ố l ư ợ n g W a tc h -T V Số lượng Walkman X1 X2 (0, 42) (30, 0) $210 = $7X1 + $5X2 © 2008 Prentice Hall, Inc. B – 22 Cách giải bằng đồ thị 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 S ố l ư ợ n g W a tc h -T V Số lượng Walkman X1 X2 $210 = $7X1 + $5X2 $350 = $7X1 + $5X2 $420 = $7X1 + $5X2 $280 = $7X1 + $5X2 © 2008 Prentice Hall, Inc. B – 23 Cách giải bằng đồ thị 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 S ố l ư ợ n g W a tc h -T V Số lượng Walkman X1 X2 $410 = $7X1 + $5X2 Đường lợi nhuận tối đa Điểm tối ưu (X1 = 30, X2 = 40) © 2008 Prentice Hall, Inc. B – 24 Phương pháp Góc – Điểm (Corner- Point) Figure B.7 1 2 3 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 S ố l ư ợ n g W a tc h -T V Số lượng Walkman X1 X2 4 © 2008 Prentice Hall, Inc. B – 25 Phương pháp Góc-Điểm  Giá trị tối ưu luôn nằm ở điểm góc  Tìm ra giá trị hàm mục tiêu tại mỗi điểm góc và chọn điểm nào có lợi nhuận cao nhất Điểm 1 : (X1 = 0, X2 = 0) Lợi nhuận $7(0) + $5(0) = $0 Điểm 2 : (X1 = 0, X2 = 80) Lợi nhuận $7(0) + $5(80) = $400 Điểm 4 : (X1 = 50, X2 = 0) Lợi nhuận $7(50) + $5(0) = $350 © 2008 Prentice Hall, Inc. B – 26 Phương Pháp Góc-Điểm Tìm ra giao của hai giới hạn 2X1 + 1X2 ≤ 100 (thời gian lắp ráp) 4X1 + 3X2 ≤ 240 (thời gian sx điện tử) 4X1 + 3X2 = 240 - 4X1 - 2X2 = -200 + 1X2 = 40 4X1 + 3(40) = 240 4X1 + 120 = 240 X1 = 30 © 2008 Prentice Hall, Inc. B – 27 Phương pháp Góc - Điểm  Giá trị tối ưu luôn nằm ở điểm góc  Tìm ra giá trị hàm mục tiêu tại mỗi điểm góc và chọn điểm nào có lợi nhuận cao nhất Điểm 1 : (X1 = 0, X2 = 0) Lợi nhuận $7(0) + $5(0) = $0 Điểm 2 : (X1 = 0, X2 = 80) Lợi nhuận $7(0) + $5(80) = $400 Điểm 4 : (X1 = 50, X2 = 0) Lợi nhuận $7(50) + $5(0) = $350 Điểm 3 : (X1 = 30, X2 = 40) Lợi nhuận $7(30) + $5(40) = $410 © 2008 Prentice Hall, Inc. B – 28 Phân tích mức độ nhạy cảm  Mức độ nhạy cảm của các kết quả đối với thay đổi của các tham số là như thế nào?  Thay đổi giá trị các hệ số  Thay đổi giá trị bên phải của các ràng buộc  Phương pháp Trial-and-error (thử nghiệm cho đến khi tìm được phương pháp phù hợp)  Phương pháp phân tích tối ưu © 2008 Prentice Hall, Inc. B – 29 Báo cáo mức độ nhạy cảm © 2008 Prentice Hall, Inc. B – 30 Các thay đổi nguồn lực Giá trị phía bên phải của phương trình ràng buộc có thể thay đổi khi nguồn lực thay đổi Mức giá ảo của ràng buộc là sự thay đổi về giá trị của hàm mục tiêu bắt nguồn từ thay đổi trên một đơn vị của gí trị phía phải của ràng buộc © 2008 Prentice Hall, Inc. B – 31 Các thay đổi nguồn lực  Các mức giá ảo thường là câu trả lời cho câu hỏi “Bạn sẽ trả bao nhiêu cho mỗi đơn vị nguồn lực tăng thêm?”  Các mức giá ảo chỉ có giá trị vượt quá một mức độ thay đổi nhất định của các giá trị phía bên phải.  Báo cáo về tính nhạy cảm cung cấp các giới hạn trên và giới hạn dưới ủa mức độ thay đổi này. © 2008 Prentice Hall, Inc. B – 32 Phân tích tính nhạy cảm – 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 X1 X2 Ràng buộc của lắp ráp thay đổi từ 2X1 + 1X2 = 100 đến 2X1 + 1X2 = 110 Ràng buộc điện tử không đổi Điểm góc 3 vẫn là tối ưu, nhưng lúc này giá trị tại điểm 3 là X1 = 45, X2 = 20, lợi nhuận = $415 1 2 3 4 © 2008 Prentice Hall, Inc. B – 33 Phân tích tính nhạy cảm – 100 – – 80 – – 60 – – 40 – – 20 – – –| | | | | | | | | | | 0 20 40 60 80 100 X1 X2 Ràng buộc Lắp ráp thay đổi tư 2X1 + 1X2 = 100 đến 2X1 + 1X2 = 90 Ràng buộc Điện tử không đổi Điểm góc 3 vẫn là tối ưu, nhưng giá trị tại điểm 3 lúc này là X1 = 15, X2 = 60, lợi nhuận = $405 1 2 3 4 © 2008 Prentice Hall, Inc. B – 34 Các thay đổi trong Hàm mục tiêu  Thay đổi hệ số trong hàm mục tiêu có thể hình thành một điểm góc khác để tạo ra một phương án tối ưu khác  Báo cáo về mức độ nhạy cảm thể hiện việc các hệ số của hàm mục tiêu có thể thay đổi bao nhiêu mà không tạo ra sự thay đổi của phương án tối ưu © 2008 Prentice Hall, Inc. B – 35 Giải bài toán Tối thiểu hóa (Minimizing)  Xây dựng và giải bài toán tương tự như đối với bài toán Tối đa hóa.  Trong cách giải bằng đồ thị, sử dụng đường Chi phí cân bằng  Mục tiêu là chuyển đường chi phí cân bằng vào trong cho đến khi đạt đến điểm góc Chi phí tối thiểu © 2008 Prentice Hall, Inc. B – 36 Ví dụ về Tối thiểu hóa X1 = số tấn hóa chất vẽ tranh đen trắng cần sản xuất X2 = số tấn hóa chất để vẽ tranh màu cần sản xuất Tổng chi phí tối thiểu =2,500X1+ 3,000X2 Giả thuyết: X1 ≥ 30 tấn hóa chất đen trắng X2 ≥ 20 tấn hóa chất màu X1 + X2 ≥ 60 tổng số tấn X1, X2 ≥ $0 yêu cầu không âm © 2008 Prentice Hall, Inc. B – 37 Ví dụ Tối thiểu hóa 60 – 50 – 40 – 30 – 20 – 10 – –| | | | | | | 0 10 20 30 40 50 60 X1 X2 Miền khả thi X1 = 30 X2 = 20 X1 + X2 = 60 b a © 2008 Prentice Hall, Inc. B – 38 Ví dụ Tối thiểu hóa Tổng chi phí a = 2,500X1 + 3,000X2 = 2,500 (40) + 3,000(20) = $160,000 Tổng chi phí b = 2,500X1 + 3,000X2 = 2,500 (30) + 3,000(30) = $165,000 Tổng chi phí thấp nhất là tại điểm a © 2008 Prentice Hall, Inc. B – 39 Các ứng dụng LP Ví dụ Kết hợp sản phẩm Bộ phận Sản phẩm Gắn kết Khoan Lắp ráp Kiểm tra Lợi nhuận đv XJ201 .5 3 2 .5 $ 9 XM897 1.5 1 4 1.0 $12 TR29 1.5 2 1 .5 $15 BR788 1.0 3 2 .5 $11 Công suất Mức độ Bộ phận (theo giờ) Sản phẩm SX thấp nhất Gắn kết 1,500 XJ201 150 Khoan 2,350 XM897 100 Lắp ráp 2,600 TR29 300 Kiểm tra 1,200 BR788 400 © 2008 Prentice Hall, Inc. B – 40 Các ứng dụng LP X1 = số đơn vị sp XJ201 cần sx X2 = số đơn vị sp XM897 cần sx X3 = số đơn vị sp TR29 cần sx X4 = số đơn vị BR788 cần sx Lợi nhuận tối đa = 9X1 + 12X2 + 15X3 + 11X4 Giả thuyết .5X1 + 1.5X2 + 1.5X3 + 1X4 ≤ 1,500 giờ gắn kết 3X1 + 1X2 + 2X3 + 3X4 ≤ 2,350 giờ khoan 2X1 + 4X2 + 1X3 + 2X4 ≤ 2,600 giờ lắp ráp .5X1 + 1X2 + .5X3 + .5X4 ≤ 1,200 giờ kiểm tra X1 ≥ 150 đơn vị sp XJ201 X2 ≥ 100 đơn vị sp XM897 X3 ≥ 300 đơn vị spTR29 X4 ≥ 400 đơn vị sp BR788 © 2008 Prentice Hall, Inc. B – 41 Các ứng dụng LP Vd bài toán Chế độ ăn uống A 3 oz 2 oz 4 oz B 2 oz 3 oz 1 oz C 1 oz 0 oz 2 oz D 6 oz 8 oz 4 oz Cung cấp Sản phẩm Kho X Kho Y Kho Z © 2008 Prentice Hall, Inc. B – 42 Các ứng dụng LP X1 = Số cân thức ăn của kho X đặt mua cho mỗi con bò hàng tháng X2 = Số cân thức ăn của kho Y đặt mua cho mỗi con bò hàng tháng X3 = Số cân thức ăn của kho Z đặt mua cho mỗi con bò hàng tháng Chi phí tối thiểu = .02X1 + .04X2 + .025X3 Yêu cầu đối với thành phần A: 3X1 + 2X2 + 4X3 ≥ 64 Yêu cầu đối với thành phần B: 2X1 + 3X2 + 1X3 ≥ 80 Yêu cầu đối với thành phần C: 1X1 + 0X2 + 2X3 ≥ 16 Yêu cầu đối với thành phần D: 6X1 + 8X2 + 4X3 ≥ 128 Giới hạn kho Z: X3 ≤ 80 X1, X2, X3 ≥ 0 Phương pháp rẻ nhất là mua 40 cân ngũ cốc X với giá $0.80 cho mỗi con bò © 2008 Prentice Hall, Inc. B – 43 Các ứng dụng LP Ví dụ về lịch làm việc nhân công Thời gian Số Giao dịch viên Thời gian Số GDV làm việc cần thiết làm việc cần thiết 9 AM - 10 AM 10 1 PM - 2 PM 18 10 AM - 11 AM 12 2 PM - 3 PM 17 11 AM - Noon 14 3 PM - 4 PM 15 Noon - 1 PM 16 4 PM - 5 PM 10 F = GDV toàn thời gian P1 = GDV bán thời gian bắt đầu lúc 9 AM (ra về lúc 1 PM) P2 = GDV bán thời gian bắt đầu lúc 10 AM (ra về lúc 2 PM) P3 = GDV bán thời gian bắt đầu lúc 11 AM (ra về lúc 3 PM) P4 = GDV bán thời gian bắt đầu lúc giữa trưa (ra về lúc 4 PM) P5 = GDV bán thời gian bắt đầu lúc 1 PM (ra về lúc 5 PM) © 2008 Prentice Hall, Inc. B – 44 Các ứng dụng LP = $75F + $24(P1 + P2 + P3 + P4 + P5) Tối thiểu hóa tổng chi phí nhân sự hàng ngày F + P1 ≥ 10 (9 AM - 10 AM) F + P1 + P2 ≥ 12 (10 AM – 11 AM) 1/2 F + P1 + P2 + P3 ≥ 14 (11 AM - 11 AM) 1/2 F + P1 + P2 + P3 + P4 ≥ 16 (noon - 1 PM) F + P2 + P3 + P4 + P5 ≥ 18 (1 PM - 2 PM) F + P3 + P4 + P5 ≥ 17 (2 PM - 3 PM) F + P4 + P5 ≥ 15 (3 PM - 7 PM) F + P5 ≥ 10 (4 PM - 5 PM) F ≤ 12 4(P1 + P2 + P3 + P4 + P5) ≤ .50(10 + 12 + 14 + 16 + 18 + 17 + 15 + 10) © 2008 Prentice Hall, Inc. B – 45 Các ứng dụng LP = $75F + $24(P1 + P2 + P3 + P4 + P5) Tối thiểu hóa tổng chi phí nhân sự hàng ngày F + P1 ≥ 10 (nhu cầu lúc 9 AM - 10 AM) F + P1 + P2 ≥ 12 (nhu cầu lúc 10 AM - 11 AM ) 1/2 F + P1 + P2 + P3 ≥ 14 (nhu cầu lúc 11 AM - 11 AM) 1/2 F + P1 + P2 + P3 + P4 ≥ 16 (nhu cầu lúc giữa trưa - 1 PM) F + P2 + P3 + P4 + P5 ≥ 18 (nhu cầu lúc 1 PM - 2 PM) F + P3 + P4 + P5 ≥ 17 (nhu cầu lúc 2 PM - 3 PM) F + P4 + P5 ≥ 15 (nhu cầu lúc 3 PM - 7 PM) F + P5 ≥ 10 (nhu cầu lúc 4 PM - 5 PM) F ≤ 12 4(P1 + P2 + P3 + P4 + P5) ≤ .50(112) F, P1, P2, P3, P4, P5 ≥ 0 © 2008 Prentice Hall, Inc. B – 46 Các ứng dụng LP = $75F + $24(P1 + P2 + P3 + P4 + P5) Minimize total daily manpower cost F + P1 ≥ 10 (9 AM - 10 AM needs) F + P1 + P2 ≥ 12 (10 AM - 11 AM needs) 1/2 F + P1 + P2 + P3 ≥ 14 (11 AM - 11 AM needs) 1/2 F + P1 + P2 + P3 + P4 ≥ 16 (noon - 1 PM needs) F + P2 + P3 + P4 + P5 ≥ 18 (1 PM - 2 PM needs) F + P3 + P4 + P5 ≥ 17 (2 PM - 3 PM needs) F + P4 + P5 ≥ 15 (3 PM - 7 PM needs) F + P5 ≥ 10 (4 PM - 5 PM needs) F ≤ 12 4(P1 + P2 + P3 + P4 + P5) ≤ .50(112) F, P1, P2, P3, P4, P5 ≥ 0 Có hai phương án tối ưu để giải quyết bài toán này nhưng cả hai đều dẫn đến kết quả chi phí là $1086 / ngày F = 10 F = 10 P1 = 0 P1 = 6 P2 = 7 P2 = 1 P3 = 2 P3 = 2 P4 = 2 P4 = 2 5 = 3 P5 = 3 Cách 1 Cách 2 © 2008 Prentice Hall, Inc. B – 47 Phương pháp đơn hình  Các bài toán thực tế rất phức tạp nên không thể giải được bằng đồ thị  Phương pháp đơn hình là thuật toán dùng để giải những bài toán phức tạp hơn  Được phát triển bởi George Dantzig vào cuối những năm 40  Hầu hết các chương trình LP trên máy tính đều sử dụng phương pháp đơn hình. © 2008 Prentice Hall, Inc. B – 48