Bài giảng Mô hình toán kinh tế: Chương 3 - ĐH Kinh tế Quốc dân

Chương 3 Mô hình tối ưu tuyến tính (QHTT), cùng tìm hiểu kiến thức trong chương này với các nội dung trình bày sau: Thí dụ mở đầu; Mô hình bài toán QHTT; Các tính chất chung của bài toán QHTT; Phương pháp đơn hình; Bài toán đối ngẫu.
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 - ĐH Kinh tế Quốc dân CHƯƠNG III MÔ HÌNH TỐI ƯU TUYẾN TÍNH (QHTT) I. Thí dụ mở đầu II. Mô hình bài toán QHTT III. Các tính chất chung của bài toán QHTT IV. Phương pháp đơn hình V. Bài toán đối ngẫu I. Thí dụ mở đầu • Thí dụ 1: Bài toán lựa chọn danh mục đầu tư - Nội dung: Một công ty đầu tư dự định dùng khoản quỹ đầu tư 500 tỷ đồng để mua một số cổ phiếu trên thị trường chứng khoán. Để phòng ngừa rủi ro công ty đưa ra các yêu cầu về đa dạng hoá danh mục đầu như sau: + Loại cổ phiếu và giới hạn mua: Loại CK Lợi tức Giới hạn mua A 7%/năm 100 tỷ B 8,5%/năm 300 tỷ C 7,8%/năm 250 tỷ D 8,2%/năm 320 tỷ + Tỷ lệ đầu tư vào cổ phiếu A và C phải chiếm ít nhất 55% và cổ phiếu B phải chiếm ít nhất 15% tổng số vốn đầu tư thực hiện - Bài toán: Với số tiền dự kiến đầu tư, hãy xác định một danh mục đầu tư sao cho đảm bảo về đa dạng hoá danh mục đầu tư và đem lại mức lợi tức lớn nhất. - Mô hình hoá: + Gọi xA, xB, xC, xD là các khoản tiền đầu tư vào các loại chứng khoán A, B, C, D + Các điều kiện về đa dạng hoá danh mục đầu tư: 0  xA  100; 0  xB  300 (1) 0  xC  250, 0  xD  320 (2) xA + xC  0,55(xA + xB+ xC + xD) (3) xB  0,15(xA + xB+ xC + xD) (4) xA + xB+ xC + xD  500 (5) + Mức lợi tức ứng với danh mục đầu tư: Z = 0,07xA + 0,085xB+ 0,078xC + 0,082xD (tỷ đồng) - Xác định x = (xA, xB, xC, xD) sao cho: Z  Max; với các điều kiện (1), (2), (3), (4), (5). - Bài toán này gọi là bài toán QHTT • Thí dụ 2: Bài toán vận tải - Nội dung: Một công ty kinh doanh xăng dầu tại khu vực Z hàng tuần cần cung ứng xăng cho 3 trạm bán lẻ A, B và C. Công ty có thể đưa xăng đến các trạm từ tổng kho I và II. Lượng xăng dự trù cung ứng cho các trạm của kho I là 20 tấn, kho II là 40 tấn. Nhu cầu tiêu thu xăng hàng tuần của các trạm A, B, C lần lượt là 20, 15, 15 (tấn). Chi phí cho việc cung ứng xăng được cho dưới bảng sau: Đơn vị: nghìn đồng/tấn Kho\ Trạm A B C I 500 400 700 II 600 500 500 - Bài toán: Cần lập một kế hoạch cung ứng xăng từ các kho đến các trạm để đảm bảo đáp ứng đủ nhu cầu của các trạm với tổng chi phí vận chuyển là nhỏ nhất. - Mô hình hoá: + Gọi x1A, x1B, x1C, x2A, x2B, x2C (tấn) lần lượt là các lượng xăng vận chuyển từ kho I, kho II đến các trạm A, B, C. + Điều kiện để đáp ứng đầy đủ nhu cầu của các trạm: x1A + x2A = 20 (1) x1B + x2B = 15 (2) x1C + x2C = 15 (3) + Điều kiện về lượng xăng dự trù cung ứng của các kho: x1A + x1B + x1C  20 (4) x2A + x2B + x2C  40 (5) + Tổng chi phí vận chuyển: Y = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C (nghìn đồng) - Xác định x1A, x1B, x1C, x2A, x2B, x2C  0 sao cho: Y  Min; với các điều kiện (1), (2), (3), (4), (5) Bài toán này gọi là bài toán QHTT II. Mô hình bài toán QHTT 1. Bài toán dạng tổng quát 2. Một số khái niệm và định nghĩa 3. Các dạng đặc biệt 1. Bài toán dạng tổng quát - Là bài toán tìm cực trị (cực đại hoặc cực tiểu) của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương và (hoặc) các bất phương trình tuyến tính. - Xác định véc tơ x = (x1, x2, …, xn) sao cho: n f ( x)   c j x j  Min(Max) j 1 n  aij x j  bi (i  I1 )  j 1 n   aij x j  bi (i  I 2 )(*) I1  I 2  I3  , I  I1  I 2  I 3  j 1 n  aij x j  bi (i  I3 )  j 1  2. Một số khái niệm và định nghĩa - Hàm f(x) cần tìm cực trị gọi là hàm mục tiêu của bài toán - Hệ (*) gọi là hệ điều kiện của bài toán - Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc của bài toán và hệ điều kiện còn gọi là hệ ràng buộc - Véc tơ x thoả mãn mọi ràng buộc của bài toán gọi là một phương án (PA) của bài toán - Tập hợp các PA có thể có của bài toán gọi là tập PA của bài toán, ký hiệu: D = {x: t/m (*)} - Xét bài toán QHTT có f(x)  Min và hai PA xA, xB. Khi đó: + Nếu f(xA)  f(xB) thì PA xA gọi là không xấu hơn PA xB + Nếu f(xA) < f(xB) thì PA xA gọi là tốt hơn PA xB - Một PA mà tại đó hàm mục tiêu đạt cực trị gọi là PA tối ưu (PATƯ), ký hiệu: x* và f* = f(x*) gọi là trị tối ưu, f(x*)  f(x) với mọi PA x của bài toán. - Một bài toán có ít nhất một PATƯ gọi là bài toán giải được - Một bài toán không có PA TƯ gọi là bài toán không giải được + Bài toán không có PA  không có PATƯ + Bài toán ...