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

2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 1 CHƯƠNG 3 LẬP TRÌNH TUYẾN TÍNH (Linear Programming) 1 TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOA HỌC QUẢN LÝ ỨNG DỤNG GV. ThS. Huỳnh Đỗ Bảo Châu Mục tiêu bài học GV. Huỳnh Đỗ Bảo Châu2  Trình bày đặc điểm của bài toán QHTT  Phân biệt các dạ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ột số công cụ máy tính để giải bài toán QHTT  Giải thích kết quả sau khi giải bài toán QHTT Nội dung chính GV. Huỳnh Đỗ Bảo Châu3 1. Mô hình hóa bài toán QHTT 2. Phương pháp đồ thị 3. Giải pháp máy tính 4. Phân tích độ nhạy 5. Các mô hình ví dụ Các giả định cho quy hoạch tuyến tính GV. Huỳnh Đỗ Bảo Châu4  Các giá trị tham số là chắc chắn  Không đổi theo quy mô VD: 1 sp thêm 4 $ lợi nhuận, đòi hỏi 3 giờ để sản xuất, vậy 500 sp thêm $ 4x500, cần 3x500 giờ  Không có tương tác giữa các biến quyết định 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 2 1. Mô hình hóa bài toán QHTT GV. Huỳnh Đỗ Bảo Châu5 Giới thiệu về Bài toán QHTT GV. Huỳnh Đỗ Bảo Châu6 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: Rj = rj(x1, x2, , xn) Trong đó, z và rj là biểu thức tuyến tính đối với x1, x2, , xn. Các bước áp dụng kỹ thuật QHTT GV. Huỳnh Đỗ Bảo Châu7  B1: Xác định vấn đề cần giải quyết mối quan hệ theo mô hình tuyến tính không.  B2: Nếu là vấn đề không có cấu trúc, cần phân tích và xây dựng như 1 mô hình toán học  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. Xây dựng mô hình QHTT GV. Huỳnh Đỗ Bảo Châu8  Xác định:  Số biến cần tìm  Hàm mục tiêu ( MAX, hoặc  MIN)  Các ràng buộc của các biến (các mối quan hệ tuyến tính) 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 3 Các dạng bài toán QHTT GV. Huỳnh Đỗ Bảo Châu9  Cực đại chuẩn ܯܽݔ ܼ ൌ ∑ ௝ܿݔ௝௡௝ୀଵ Ràng buộc: ∑ ܽ௜௝ݔ௝௡௝ୀଵ ൑ ܾ௜ ∀݅ ൌ 1,2, ,݉ ݔ௝ ൒ 0 ∀݆ ൌ 1,2, ݊ ܾ௜ ൒ 0  Cực tiểu chuẩn ܯ݅݊ ܼ ൌ ∑ ௝ܿݔ௝௡௝ୀଵ 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 ≤. 2. Phương pháp đồ thị GV. Huỳnh Đỗ Bảo Châu10 Phương pháp đồ thị GV. Huỳnh Đỗ Bảo Châu11  Sử dụng khi:  Có nhiều ràng buộc dưới dạng bất phương trình  Số biến cần tìm là 2  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. Giải bài toán QHTT bằng PP đồ thị GV. Huỳnh Đỗ Bảo Châu12  Nghiệm khả dĩ (Feasible solution): 1 bộ giá trị các biến thỏa mãn các ràng buộc.  Vùng khả dĩ (Feasible region): Tập tất cả các nghiệm khả dĩ. 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 4 Các bước thực hiện (áp dụng cho bài toán 2 biến) GV. Huỳnh Đỗ Bảo Châu13  B1: Biểu diễn các dữ kiện của bài toán dưới dạng phương trình hoặc bất phương trình  B2: Giải các phương trình và bất phương trình bằng đồ thị, kết quả sẽ nhận được 1 vùng khả dĩ  B3: Vẽ 1 đường thẳng biểu diễn hàm mục tiêu và tịnh tiến đường này tiến về miền nghiệm khả dĩ. Điểm đầu tiên mà đườ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. Ví dụ minh họa (MÔ HÌNH BÀI TOÁN CỰC ĐẠI) GV. Huỳnh Đỗ Bảo Châu14  Công ty Gốm Beaver Creek sản xuất thủ công quy mô nhỏ, sử dụng các nghệ nhân có tay nghề cao để sản xuất chén và ly bằng đất sét theo thiết kế và màu sắc của Mỹ. Hai nguồn lực chính của công ty là đất sét (clay), và lao động có tay nghề cao (labor).  Với nguồn lực có hạn, công ty mong muốn biết bao nhiêu cái chén và ly cần sản xuất mỗi ngày để tối đa hóa lợi nhuận ? Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu15 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu16  Gọi ݔଵ: số chén (bowl) cần sản xuất  Gọi ݔଶ: số ly (mug) cần sản xuấ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 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 5 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu17 Đường biểu diễn ràng buộc về người lao động 1ݔଵ ൅ 2ݔଶ ൑ 40 Vùng ràng buộc nguồn lực lao động Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu18 Đường biểu diễn ràng buộc về lượng đất sét nguyên liệu 4ݔଵ ൅ 3ݔଶ ൑ 120 Kết hợp 2 ràng buộc có vùng khả dĩ Vùng ràng buộc nguyên liệu đất sét Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu19  Vẽ đường hàm mục tiêu với giá trị F bất kỳ ܨ ൌ 40ݔଵ ൅ 50ݔଶ Đường hàm mục tiêu với F = 800 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu20  Tìm giá trị của kết quả ݔଵ, ݔଶ ݔଵ ൌ 24, ݔଶ ൌ 8 → ܨ ൌ 1.360 Tịnh tiến đường hàm mục tiêu Kết quả tại B (24,8) 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 6 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu21 Giải pháp tại các góc của vùng nghiệm khả dĩ Kết quả khi thay đổi giá bán Thay đổi hàm F Biến bù (Slack Variables) GV. Huỳnh Đỗ Bảo Châu22  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ẾN BÙ đại diện cho nguồn tài nguyên chưa sử dụng Ví dụ minh họa (Công ty Gốm Beaver Creek) GV. Huỳnh Đỗ Bảo Châu23  Các ràng buộc ቊ 1ݔଵ ൅ 2ݔଶ ൑ 40 4ݔଵ ൅ 3ݔଶ ൑ 120 chuyển thành phương trình ቊ 1ݔଵ ൅ 2ݔଶ ൅ ࢙૚ ൌ 40 4ݔଵ ൅ 3ݔଶ ൅ ࢙૛ ൌ 120 với ݔଵ, ݔଶ, ݏଵ, ݏଶ ൒ 0  Hàm mục tiêu lợi nhuận: ܨ ൌ 40ݔଵ ൅ 50ݔଶ ൅ 0ݏଵ ൅ 0ݏଶ → ܯܣܺ Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu24  Bài toán trở thành: Hàm mục tiêu lợi nhuận: ܨ ൌ 40ݔଵ ൅ 50ݔଶ ൅ 0ݏଵ ൅ 0ݏଶ → ܯܣܺ Với ቊ 1ݔଵ ൅ 2ݔଶ ൅ ࢙૚ ൌ 40 4ݔଵ ൅ 3ݔଶ ൅ ࢙૛ ൌ 120 ݔଵ, ݔଶ, ݏଵ, ݏଶ ൒ 0 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 7 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu25 Ví dụ minh họa (MÔ HÌNH BÀI TOÁN CỰC TIỂU) GV. Huỳnh Đỗ Bảo Châu26  Một nông dân đang chuẩn bị để trồng một cây trồng vào mùa xuân và mua phân bón. Có hai thương hiệu phân bón để lựa chọn, Super-Gro và Crop-Quick.  Mỗi thương hiệu mang một lượng cụ thể nitro và phosphate trong 1 túi sản phẩm như sau:  Để hoàn thành vụ mùa đòi hỏi ít nhất 16kg nitro và ít nhất 24kg phosphate. Super-Gro giá $6/túi, và Crop-Quick giá $3/túi.  Người nông dân muốn biết cần bao nhiêu túi phân bón mỗi thương hiệu để giảm thiểu tổng chi phí bón phân. ? Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu27  Gọi ݔଵ:  Gọi ݔଶ:  HÀM MỤC TIÊU CHI PHÍ:  RÀNG BUỘC: Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu28 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 8 Ví dụ minh họa (1) GV. Huỳnh Đỗ Bảo Châu29  Một xưởng sản xuất gỗ có 2 sản phẩm: bàn tròn và bàn chữ nhật. Mỗi bàn tròn cần 2,5h lắp ghép, 3h để đánh bóng, 1h để đóng thùng. Một bàn chữ nhật cần 1 giờ để lắp ghé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ực hiện tối đa 20h lắp ghép, 30h đánh bóng, và 16h để đóng thùng. Lợi nhuận thu về 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ản xuất tối ưu đem về cho xưởng lợi nhuận cao nhất ? Bài giải ví dụ minh họa (1) GV. Huỳnh Đỗ Bảo Châu30 Ví dụ minh họa (2) GV. Huỳnh Đỗ Bảo Châu31  Một người nông dân muốn đàn cừu của nông trại tiêu thụ các loại sản phẩm thức ăn có các loại chất dinh dưỡng A, B, C với khẩu phần hằng ngày ít nhất, nhưng đảm bảo về mặt dinh dưỡng tối thiểu yêu cầu theo lời khuyên của nhà chuyên môn. Nhu cầu dinh dưỡng tối thiểu hằng ngày về chất dinh dưỡng A, B, C theo thứ tự là 14, 12, 18 đơn vị. Trên thị trường có các loại sản phẩm Y1 và Y2. Sản phẩm Y1 cung cấp 1A, 1B, 1C. Sản phẩm Y2 cung cấp 1A, 1B, 3C. Giá mua 1 đơn vị Y1 là 2.000$, 1 đơn vị Y2 là 4.000$.  Tìm phương án mua Y1, Y2 tối ưu để chi phí là ít nhất ? Bài giải ví dụ minh họa (2) GV. Huỳnh Đỗ Bảo Châu32 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 9 Các trường hợp bài toán QHTT đặc biệt GV. Huỳnh Đỗ Bảo Châu33  Vấn đề với nhiều giải pháp tối ưu  Vấn đề không tìm được giải pháp tối ưu  Vấn đề với vô hạn giải pháp Vấn đề với nhiều giải pháp tối ưu GV. Huỳnh Đỗ Bảo Châu34  HÀM MỤC TIÊU LỢI NHUẬN: ܨ ൌ 40ݔଵ ൅ 30ݔଶ → ܯܣܺ  RÀNG BUỘC: ቊ 1ݔଵ ൅ 2ݔଶ ൑ 40 4ݔଵ ൅ 3ݔଶ ൑ 120 với ݔଵ, ݔଶ ൒ 0 Vấn đề không có giải pháp tối ưu GV. Huỳnh Đỗ Bảo Châu35  HÀM MỤC TIÊU LỢI NHUẬN: ܨ ൌ 5ݔଵ ൅ 3ݔଶ → ܯܣܺ  RÀNG BUỘC: ቊ 4ݔଵ ൅ 2ݔଶ ൑ 8 ݔଵ ൒ 4 , ݔଶ ൒ 6 với ݔଵ, ݔଶ ൒ 0 Vấn đề có vô hạn giải pháp GV. Huỳnh Đỗ Bảo Châu36  HÀM MỤC TIÊU LỢI NHUẬN: ܨ ൌ 4ݔଵ ൅ 2ݔଶ → ܯܣܺ  RÀNG BUỘC: ቊ ݔଵ ൒ 4 ݔଶ ൑ 6 với ݔଵ, ݔଶ ൒ 0 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 10 Đặc điểm của vấn đề Lập trình tuyến tính GV. Huỳnh Đỗ Bảo Châu37  Vấn đề đòi hỏi lựa chọn các hướng hành động khác nhau (là quyết định)  Quyết định được đại diện bởi các biến quyết định.  Vấn đề bao hàm mục tiêu mà người ra quyết định muốn đạt được (tối đa, hoặc tối thiểu 1 đại lượng)  Có những hạn chế giới hạn việc đạt được hàm mục tiên, và có thể được mô tả bằng các phương trình toán học biểu thị mối quan hệ tuyến tính. Thuộc tính của mô hình lập trình tuyến tính GV. Huỳnh Đỗ Bảo Châu38  Proportionality (Cân xứng): có nghĩa là độ dốc của một ràng buộc hoặc hàm mục tiêu là 1 đường không đổi.  Giới hạn của ràng buộc và hàm mục tiêu là các yếu tố bổ sung (additive).  Giá trị của các biến quyết định là số nguyên, hoặc có thể là số thực (do kết quả bài toán tính ra)  Tất cả các thông số của mô hình được giả định là chắc chắn và không thay đổi. 3. Giải pháp máy tính GV. Huỳnh Đỗ Bảo Châu39 Giải pháp máy tính GV. Huỳnh Đỗ Bảo Châu40  Các công cụ phần mềm giải bài toán QHTT theo phương pháp đơn hình  Phần mềm máy tính:  Dựa vào thuật toán  Khả năng tính nhanh (hàng triệu phép thử/giây)  EXCEL, ABQM, QSB, LINDO 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 11 Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu41 Số liệu Lúa gạo Lúa mì Tài nguyên tối đa Diện tích (ha/tấn) Lượng nước (103m3/tấn) Nhân công (công/tấn) Lợi nhuận (USD/tấn) 2 6 20 18 3 4 5 21 50 90 250 Diện tích Lượng nước Nhân lực Giá trị của biến 2 x1 6 x1 20 x1 x1 + + + , 3 x2 4 x2 5 x2 x2 ≤ ≤ ≤ ≥ 50 90 250 0 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: Công cụ Excel  Data  Solver GV. Huỳnh Đỗ Bảo Châu42 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu43 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu44 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 12 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu45 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu46 4. Phân tích độ nhạy GV. Huỳnh Đỗ Bảo Châu47 Phân tích độ nhạy GV. Huỳnh Đỗ Bảo Châu48  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. Ràng buộc trói buộc (Binding Constraint) Ràng buộc không trói buộc (Not Binding Constraint) -> Slack 2/12/2017 GV.ThS. Huỳnh Đỗ Bảo Châu 13 Phân tích độ nhạy (tt) GV. Huỳnh Đỗ Bảo Châu49 • 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ều nà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ăng thêm 1 m3 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ự. HẾT CHƯƠNG 3 GV. Huỳnh Đỗ Bảo Châu50