Bài giảng Khoa học quản lý ứng dụng: Chương 3 - ThS. Huỳnh Đỗ Bảo Châu

Bài giảng Khoa học quản lý ứng dụng: Chương 3 Lập trình tuyến tính có mục tiêu như 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 trích xuất từ tài liệu:
Bài giảng Khoa học quản lý ứng dụng: Chương 3 - ThS. Huỳnh Đỗ Bảo Châu 2/12/2017 Mục tiêu bài học 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     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 CHƯƠNG 3 LẬP TRÌNH TUYẾN TÍNH (Linear Programming) GV. ThS. Huỳnh Đỗ Bảo Châu 1 2 Nội dung chính 1. 2. 3. 4. 5. Các giả định cho quy hoạch tuyến tính Mô hình hóa bài toán QHTT Phương pháp đồ thị Giải pháp máy tính Phân tích độ nhạy Các mô hình ví dụ 3 GV.ThS. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu 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  4 GV. Huỳnh Đỗ Bảo Châu 1 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 Các bước áp dụng kỹ thuật QHTT 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     6 GV. Huỳnh Đỗ Bảo Châu Xây dựng mô hình QHTT 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 kỹ thuật phổ biến là Đồ thị và Đơn hình. 7 GV.ThS. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu 8 GV. Huỳnh Đỗ Bảo Châu 2 2/12/2017 Các dạng bài toán QHTT  Cực đại chuẩn ∑ Ràng buộc: ∑ ∀ 0 ∀ 1,2, … , 1,2, … 0  Cực tiểu chuẩn Ràng buộc: 2. Phương pháp đồ thị ∑ ∑ ∀ 0 ∀ 1,2, … , 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 Phương pháp đồ thị      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. 11 GV.ThS. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu Giải bài toán QHTT bằng PP đồ thị Sử dụng khi:  10 GV. Huỳnh Đỗ Bảo Châu  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ĩ. 12 GV. Huỳnh Đỗ Bảo Châu 3 2/12/2017 Các bước thực hiện (áp dụng cho bài toán 2 biến)    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. 13 Ví dụ minh họa (MÔ HÌNH BÀI TOÁN CỰC ĐẠI)   GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) 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 ? 14 Ví dụ minh họa (tt)     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: 2 40 1 3 120 4 với 15 GV.ThS. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu 16 , 0, int GV. Huỳnh Đỗ Bảo Châu 4 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 1 2 40 Đường biểu diễn ràng buộc về lượng đất sét nguyên liệu 4 3 120 Vùng ràng buộc nguyên liệu đất sét Vùng ràng buộc nguồn lực lao động 17 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt)  18  Tìm giá trị của kết quả 24, Đường hàm mục tiêu với F = 800 GV.ThS. Huỳnh Đỗ Bảo Châu GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Vẽ đường hàm mục tiêu với giá trị F bất kỳ 50 40 19 Kết hợp 2 ràng buộc có vùng khả dĩ , 8 → 1.360 Kết quả tại B (24,8) Tịnh tiến đường hàm mục tiêu GV. Huỳnh Đỗ Bảo Châu 20 GV. Huỳnh Đỗ Bảo Châu 5