Bài giảng Khoa học quản lý ứng dụng - Chương 3: Lập trình tuyến tính - Huỳnh Đỗ Bảo Châu

Nội dung text: Bài giảng Khoa học quản lý ứng dụng - Chương 3: Lập trình tuyến tính - Huỳnh Đỗ Bảo Châu

1. 2/12/2017 TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM Mục tiêu bài học KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ  Trình bày đặc điểmcủa bài toán QHTT KHOA HỌC QUẢN LÝ ỨNG DỤNG  Phân biệtcácdạng bài toán QHTT  Ứng dụng cách xây dựng mô hình cho bài toán QHTT  Sử dụng mộtsố công cụ máy tính để giải bài toán QHTT  Giải thích kếtquả sau khi giải bài toán QHTT CHƯƠNG 3 LẬP TRÌNH TUYẾN TÍNH (Linear Programming) GV. ThS. Huỳnh Đỗ Bảo Châu 1 2 GV. Huỳnh Đỗ Bảo Châu Nội dung chính Các giảđịnh cho quy hoạch tuyếntính 1. Mô hình hóa bài toán QHTT  Các giá trị tham số là chắcchắn 2. Phương pháp đồ thị  Không đổitheoquymô 3. Giải pháp máy tính VD:1spthêm4$lợi nhuận, đòi hỏi3giờ 4. Phân tích độ nhạy để sảnxuất, vậy 500 sp thêm $ 4x500, cần 5. Các mô hình ví dụ 3x500 giờ  Không có tương tác giữacácbiếnquyết định 3 GV. Huỳnh Đỗ Bảo Châu 4 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 1
2. 2/12/2017 Giới thiệu về Bài toán QHTT Xác định x1, x2, , xn sao cho: Cực đại (hay Cực tiểu) hàm mục tiêu Z: Z = z(x1, x2, , xn) Đồng thời thỏa mãn các ràng buộc Rj: 1. Mô hình hóa bài toán QHTT Rj = rj(x1, x2, , xn) Trong đó, z và rj là biểu thức tuyến tính đối với x1, x2, , xn. 5 GV. Huỳnh Đỗ Bảo Châu 6 GV. Huỳnh Đỗ Bảo Châu Các bước áp dụng kỹ thuật QHTT Xây dựng mô hình QHTT  B1: Xác định vấn đề cần giải quyết mối quan hệ theo  Xác định: mô hình tuyến tính không.  Số biến cần tìm  B2: Nếu là vấn đề không có cấu trúc, cần phân tích và  Hàm mục tiêu ( MAX, hoặc MIN) xây dựng như 1 mô hình toán học  Các ràng buộc của các biến (các mối quan hệ tuyến tính)  B3: Giải mô hình và tìm ra kết quả bằng cách sử dụng các kỹ thuật toán học  2 kỹ thuật phổ biến là Đồ thị và Đơn hình. 7 GV. Huỳnh Đỗ Bảo Châu 8 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 2
3. 2/12/2017 Các dạng bài toán QHTT  Cực đại chuẩn ∑ Ràng buộc: ∑ ∀1,2, , 0 ∀ 1,2, 0  Cực tiểu chuẩn ∑ 2. Phương pháp đồ thị Ràng buộc: ∑ ∀1,2, , 0 ∀ 1,2, 0  Bài toán cực đại (hay cực tiểu) với ràng buộc có dấu ≥ và cả dấu ≤. 9 GV. Huỳnh Đỗ Bảo Châu 10 GV. Huỳnh Đỗ Bảo Châu Phương pháp đồ thị Giải bài toán QHTT bằng PP đồ thị  Sử dụng khi:  Nghiệmkhả dĩ (Feasible solution): 1 bộ giá trị các  Có nhiều ràng buộc dưới dạng bất phương trình biếnthỏa mãn các ràng buộc.  Số biến cần tìm là 2  Vùng khả dĩ (Feasible region): Tậptấtcả các nghiệmkhả dĩ.  Cung cấp bức tranh toàn cục về giải pháp bài toán.  Thuận lợi để thực hiện phân tích độ nhạy. 11 GV. Huỳnh Đỗ Bảo Châu 12 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 3
4. 2/12/2017 Ví dụ minh họa Các bước thực hiện (áp dụng cho bài toán 2 biến) (MÔ HÌNH BÀI TOÁN CỰC ĐẠI)  B1: Biểu diễn các dữ kiện của bài toán dưới dạng phương  Công ty Gốm Beaver Creek sảnxuấtthủ công quy mô trình hoặc bất phương trình nhỏ,sử dụng các nghệ nhân có tay nghề cao để sản  B2: Giải các phương trình và bất phương trình bằng đồ thị, xuấtchénvàlybằng đất sét theo thiếtkế và màu sắc kết quả sẽ nhận được 1 vùng khả dĩ củaMỹ.Hainguồnlực chính của công ty là đấtsét  B3: Vẽ 1 đường thẳng biểu diễn hàm mục tiêu và tịnh tiến (clay), và lao động có tay nghề cao (labor). đường này tiến về miền nghiệm khả dĩ. Điểm đầu tiên mà  Vớinguồnlựccóhạn, công ty mong muốnbiếtbao đường hàm mục tiêu chạm với miền nghiệm chính là kết quả bài toán. nhiêu cái chén và ly cầnsảnxuấtmỗingàyđể tối đa hóa lợinhuận? 13 GV. Huỳnh Đỗ Bảo Châu 14 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Gọi : số chén (bowl) cầnsảnxuất  Gọi : số ly (mug) cầnsảnxuất  HÀM MỤC TIÊU LỢI NHUẬN: 40 50 →  RÀNG BUỘC: 1 2 40 4 3 120 với , 0, int 15 GV. Huỳnh Đỗ Bảo Châu 16 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 4
5. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt) Đường biểu diễn ràng buộc về người lao động Đường biểu diễn ràng buộc về lượng đất sét nguyên liệu 1 2 40 4 3 120 Vùng ràng buộc Vùng ràng buộc Kết hợp 2 ràng buộc nguyên liệu đất sét nguồn lực lao động có vùng khả dĩ 17 GV. Huỳnh Đỗ Bảo Châu 18 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Vẽ đường hàm mục tiêu với giá trị F bất kỳ  Tìm giá trị của kết quả , 40 50 24, 8 → 1.360 Kết quả tại B (24,8) Đường hàm mục tiêu Tịnh tiến với F = 800 đường hàm mục tiêu 19 GV. Huỳnh Đỗ Bảo Châu 20 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 5
6. 2/12/2017 Ví dụ minh họa (tt) Biến bù (Slack Variables)  BIẾN BÙ được thêm vào bất phương trình ràng buộc để chuyển nó sang một phương trình (=)  BIẾNBÙ đại diện cho nguồn tài nguyên chưa sử dụng Giải pháp tại các góc của vùng Kết quả khi thay đổi giá bán nghiệm khả dĩ Thay đổi hàm F 21 GV. Huỳnh Đỗ Bảo Châu 22 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (Công ty Gốm Beaver Creek) Ví dụ minh họa (tt)  Các ràng buộc  Bài toán trở thành: 1 2 40 Hàm mục tiêu lợi nhuận: 4 3 120 40 50 0 0 → chuyển thành phương trình Với 1 2 40 1 2 40 4 3 120 4 3 120 , , , 0 với ,,, 0  Hàm mục tiêu lợi nhuận: 40 50 0 0 → 23 GV. Huỳnh Đỗ Bảo Châu 24 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 6
7. 2/12/2017 Ví dụ minh họa Ví dụ minh họa (tt) (MÔ HÌNH BÀI TOÁN CỰC TIỂU)  Mộtnôngdânđang chuẩnbịđểtrồng mộtcâytrồng vào mùa xuân và mua phân bón. Có hai thương hiệuphânbónđể lựachọn, Super-Gro và Crop-Quick.  Mỗithương hiệumangmộtlượng cụ thể nitro và phosphate trong 1 túi sảnphẩmnhư sau:  Để hoàn thành vụ mùa đòi hỏiítnhất 16kg nitro và ít nhất 24kg phosphate. Super-Gro giá $6/túi, và Crop-Quick giá $3/túi.  Ngườinôngdânmuốnbiếtcầnbaonhiêutúiphânbónmỗithương hiệu để giảmthiểutổng chi phí bón phân. ? 25 GV. Huỳnh Đỗ Bảo Châu 26 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Gọi :  Gọi :  HÀM MỤC TIÊU CHI PHÍ:  RÀNG BUỘC: 27 GV. Huỳnh Đỗ Bảo Châu 28 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 7
8. 2/12/2017 Ví dụ minh họa(1) Bài giảivídụ minh họa(1)  Mộtxưởng sảnxuấtgỗ có 2 sảnphẩm:bàntrònvà bàn chữ nhật. Mỗi bàn tròn cần2,5hlắpghép,3hđể đánh bóng, 1h để đóng thùng. Mộtbànchữ nhậtcần 1giờđểlắpghép,3hđể đánh bóng, 2h để đóng thùng. Trong 1 tuần, xưởng chỉ có thể bố trí nhân công thựchiệntối đa20hlắp ghép, 30h đánh bóng, và 16h để đóng thùng. Lợinhuậnthuvề khi bán 1 bàn tròn là 30.000, bán 1 bàn chữ nhật là 40.000.  Tìm phương án sảnxuấttối ưu đem về cho xưởng lợi nhuậncaonhất? 29 GV. Huỳnh Đỗ Bảo Châu 30 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (2) Bài giảivídụ minh họa(2)  Mộtngườinôngdânmuốn đàn cừucủa nông trạitiêu thụ các loạisảnphẩmthức ăncócácloạichấtdinh dưỡng A, B, C vớikhẩuphầnhằng ngày ít nhất, nhưng đảmbảovề mặtdinhdưỡng tốithiểuyêucầutheolời khuyên củanhàchuyênmôn.Nhucầudinhdưỡng tối thiểuhằng ngày về chấtdinhdưỡng A, B, C theo thứ tự là 14, 12, 18 đơnvị.Trênthị trường có các loạisản phẩm Y1 và Y2. Sảnphẩm Y1 cung cấp 1A, 1B, 1C. Sảnphẩm Y2 cung cấp1A,1B,3C.Giámua1đơnvị Y1 là 2.000$, 1 đơnvị Y2 là 4.000$.  Tìm phương án mua Y1, Y2 tối ưu để chi phí là ít nhất? 31 GV. Huỳnh Đỗ Bảo Châu 32 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 8
9. 2/12/2017 Các trường hợp bài toán QHTT đặc biệt Vấn đề với nhiều giải pháp tối ưu  Vấn đề với nhiều giải pháp tối ưu  HÀM MỤC TIÊU LỢI NHUẬN: 40 30 →  Vấn đề không tìm được giải pháp tối ưu  RÀNG BUỘC: 1 2 40  Vấn đề với vô hạn giải pháp 4 3 120 với , 0 33 GV. Huỳnh Đỗ Bảo Châu 34 GV. Huỳnh Đỗ Bảo Châu Vấn đề không có giải pháp tối ưu Vấn đề có vô hạn giải pháp  HÀM MỤC TIÊU LỢI NHUẬN:  HÀM MỤC TIÊU LỢI NHUẬN: 5 3 → 4 2 →  RÀNG BUỘC:  RÀNG BUỘC: 4 2 8 4 4 , 6 6 với , 0 với , 0 35 GV. Huỳnh Đỗ Bảo Châu 36 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 9
10. 2/12/2017 Đặc điểm của vấn đề Lập trình tuyến tính Thuộc tính của mô hình lập trình tuyến tính  Vấn đề đòi hỏilựachọncáchướng hành động khác  Proportionality (Cân xứng): có nghĩa là độ dốc của một nhau (là quyết định) ràng buộc hoặc hàm mục tiêu là 1 đường không đổi.  Quyết định được đạidiệnbởicácbiếnquyết định.  Giới hạn của ràng buộc và hàm mục tiêu là các yếu tố  Vấn đề bao hàm mụctiêumàngườiraquyết định bổ sung (additive). muốn đạt được(tối đa, hoặctốithiểu1đạilượng)  Giá trị của các biến quyết định là số nguyên, hoặc có  Có những hạnchế giớihạnviệc đạt đượchàmmục thể là số thực (do kết quả bài toán tính ra) tiên, và có thểđượcmôtả bằng các phương trình toán  Tất cả các thông số của mô hình được giả định là chắc họcbiểuthị mốiquanhệ tuyến tính. chắn và không thay đổi. 37 GV. Huỳnh Đỗ Bảo Châu 38 GV. Huỳnh Đỗ Bảo Châu Giải pháp máy tính  Các công cụ phầnmềmgiải bài toán QHTT theo phương pháp đơnhình  Phầnmềm máy tính:  Dựavàothuậttoán  Khả năng tính nhanh (hàng triệuphépthử/giây) 3. Giải pháp máy tính  EXCEL, ABQM, QSB, LINDO 39 GV. Huỳnh Đỗ Bảo Châu 40 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 10
11. 2/12/2017 Ví dụ minh họa Công cụ Excel Data Solver Số liệu Lúa gạo Lúa mì Tài nguyên tối đa Diện tích (ha/tấn) 2 3 50 Lượng nước (103m3/tấn) 6 4 90 Nhân công (công/tấn) 20 5 250 Lợi nhuận (USD/tấn) 18 21 Biến quyết định: Gọi x1, x2 là số tấn lúa gạo và lúa mì cần sản xuất. Hàm mục tiêu: Tổng lợi nhuận Max Z = 18 x1 + 21 x2 Các ràng buộc: Diện tích 2 x1 + 3 x2 ≤ 50 Lượng nước 6 x1 + 4 x2 ≤ 90 Nhân lực 20 x1 + 5 x2 ≤ 250 Giá trị của biến x1 , x2 ≥ 0 41 GV. Huỳnh Đỗ Bảo Châu 42 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt) 43 GV. Huỳnh Đỗ Bảo Châu 44 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 11
12. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt) 45 GV. Huỳnh Đỗ Bảo Châu 46 GV. Huỳnh Đỗ Bảo Châu Phân tích độ nhạy  Giá mờ biểu thị cho sự thay đổi giá trị tối ưu của hàm mục tiêu khi có sự thay đổi của vế phải các ràng buộc. 4. Phân tích độ nhạy Ràng buộc trói buộc (Binding Constraint) Ràng buộc không trói buộc (Not Binding Constraint) -> Slack 47 GV. Huỳnh Đỗ Bảo Châu 48 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 12
13. 2/12/2017 Phân tích độ nhạy (tt) HẾT CHƯƠNG 3 • Phân tích tài nguyên Diện tích (ha/tấn): Khi thêm (hoặc giảm) 1 ha Diện tích, thì lợi nhuận tăng thêm (hoặc giảm) 5.4 USD (cột Shadow Price)vàđiềunày chỉ đúng trong phạm vị từ 50–10 = 40 (cột Allowable Decrease) đến 50+17.5 = 67.5 (cột Allowable Increase). • Phân tích tài nguyên Nước (10m3/tấn): Trong phạm vi lượng nước từ 66.667 m3 đến 100 m3,cứtăngthêm1m3 thì lợi nhuận tăng thêm 1.2 USD. • Phân tích tài nguyên Nhân công (công/tấn): Giải thích tương tự. 49 GV. Huỳnh Đỗ Bảo Châu 50 GV. Huỳnh Đỗ Bảo Châu GV.ThS. Huỳnh Đỗ Bảo Châu 13