Bài giảng Mô hình toán kinh tế - Chương 3: Mô hình tối ưu tuyến tính

Bài giảng Mô hình toán kinh tế Chương 3: Mô hình tối ưu tuyến tính trình bày về các khái niệm cơ bản về bài toán quan hệ tuyến tính, thuật toán đơn hình, bài toán đối ngẫu...mời các bạn tham khảo bài giảng để hiểu sâu hon về tối ưu tuyến tính.
Nội dung trích xuất từ tài liệu:
Bài giảng Mô hình toán kinh tế - Chương 3: Mô hình tối ưu tuyến tính CHƯƠNG 3 MÔ HÌNH TỐI ƯU TUYẾN TÍNH §1. Khái niệm cơ bản về bài toán QHTT §2. Thuật toán đơn hình §3. Bài toán đối ngẫu 1 §1. KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Một số ví dụ Ví dụ 1 Một trại chăn nuôi định nuôi 3 loại bò: bò sữa, bò cày, bò thịt. Nguồn cung cấp giống bò sữa chỉ có thể cung cấp tối đa 18 con. Dự trù kinh phí chăn nuôi (tính trên mỗi con bò) được cho trong bảng sau : Loại bò Bò sữa Bò cày Bò thịt Tiền dự tính (đv : 10000 ĐVN) Chi phí Vốn 128 137 165 7020 Chi phí chăn nuôi 59 43 43 860 Tiền lãi 71 45 61 Tìm số bò mỗi loại cần nuôi để đạt lợi nhuận lớn nhất 2 Một nhà đầu tư có 4 tỉ đồng muốn đầu tư vào bốn lĩnh vực Lĩnh vực đầu tư Lãi suất / năm Ví dụ 2 Chứng khoán 20% Công trái 12% Gửi tiết kiệm 15% Bất động sản 18% Ngoài ra, để giảm thiểu rủi ro, nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá 30% tổng số vốn đầu tư; đầu tư vào công trái và gửi tiết kiệm ít nhất 25% tổng vốn đầu tư; gửi tiết kiệm ít nhất 300 triệu đồng. Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng thu nhập hàng năm là lớn nhất. 3 • Các bước lập bài toán QHTT : 1) Xác định ẩn và hàm mục tiêu. 2) Xác định hệ ràng buộc về biến. 3) Xác định hệ ràng buộc về dấu. 4 Công ty A có kết hoạch quảng cáo sản phẩm trong 1 tháng với tổng chi phí là 120 triệu đồng. Các phương tiện quảng cáo: truyền hình, báo giấy, phát thanh. Các dữ liệu như sau : Phương tiện Chi phí cho 1 Số lần QC Dự đoán số lần QC tối đa người tiếp nhận QC trong 1 lần Truyền hình 1,2 triệu đồng 90 10 000 Báo 0,9 triệu đồng 28 15 000 Phát thanh 0,4 triệu đồng 120 5 000 Vì lí do chiến lược tiếp thị, yêu cầu ít nhất phải có 60 lần quảng cáo trên truyền hình trong 1 tháng. Hãy lập mô hình bài toán xác định kế hoạch quảng cáo. 5 2. Bài toán quy hoạch tuyến tính (QHTT) 2.1 Bài toán QHTT tổng quát Tìm x = (x1, x2, . . . , xn) sao cho: n f (x)   c j x j  Min(Max) (1) hàm mục tiêu j1  ràng buộc biến   n  a ij x j    bi ; i  1,..., m (2) (ràng buộc chính) j1         x j    0 ; j  1,..., n (3) ràng buộc dấu  tùy ý    6 2.2 Một số khái niệm • Một phương án của bài toán QHTT là một bộ n số (một véctơ) x  (x1 , x 2 ,..., x n ) thỏa mãn các hệ ràng buộc (2), (3). • Tập hợp các véctơ thỏa mãn (2),(3) gọi là tập phương án. • Phương án tối ưu (PATƯ) là một phương án thỏa (1). 7 2.2 Một số khái niệm Bài toán giải được là bài toán có PATƯ. Bài toán không giải được là bài toán không có PATƯ. Khi đó hoặc là bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn ( f (x)    () đối với bài toán max (min)).  Nếu phương án x thỏa mãn ràng buộc nào đó với dấu “=” thì ta nói x thỏa mãn chặt ràng buộc đó. Ngược lại nếu thỏa dấu “>” hoặc “ 2.2 Một số khái niệm - Ứng với ràng buộc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3). - Ký hiệu:  a1j    là vectơ các hệ số của biến x trong các ràng a 2 j  A j    buộc (không kể ràng buộc dấu). j    a nj    - Hệ vectơ Ai* tương ứng với các ràng buộc chính tạo thành ma trận ràng buộc chính, ký hiệu là A. - Các ràng buộc gọi là độc lập tuyến tính nếu hệ véctơ Ai* tương ứng độc lập tuyến tính. 9 2.2 Một số khái niệm • Phương án cực biên (phương án cơ bản) (PACB): phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính. Lưu ý: PACB có thể thỏa mãn chặt hơn n ràng buộc, nhưng c ...