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

Chia sẻ: Cảnh Đặng Xuân | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

203
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 có PA nhưng hàm mục tiêu không bị chặn trên tập PA - Xét với PA x: + Nếu ràng buộc i (iI) thoả mãn với dấu “=“ thì PA x gọi là thoả mãn “chặt” ràng buộc i hay ràng buộc i là chặt đối với PA x + Nếu ràng buộc i (iI) thoả mãn với dấu “>” hoặc “
- Với ràng buộc i ta ký kiệu véc tơ A*i = (ai1, ai2,…, ain) và tập hợp các véc tơ A*i (iI) tạo thành một ma trận, ký hiệu: A* và gọi là ma trận hệ ràng buộc của bài toán - Gọi một nhóm các ràng buộc có hệ véc tơ A*i tương ứng độc lập tuyến tính gọi là các ràng buộc độc lập tuyến tính - Một PA thoả mãn chặt n ràng buộc độc lập tuyến tính gọi là PA cực biên (PACB) + PACB thoả mãn đúng n ràng buộc gọi là PACB không suy biến + PACB thoả mãn hơn n ràng buộc gọi là PACB suy biến - Một bài toán có tất cả các PACB đều không suy biến gọi là bài toán không suy biến - Một bài toán có ít nhất một PACB suy biến gọi là bài toán suy biến
Ví dụ 1 f ( x )   2 x1  x 2  M in  x1  2 x 2  6 (1) x  x  3 (2 )  1 2   x1 0 (3)   x2  0 (4 )
3. Các dạng đặc biệt 3.1. Bài toán dạng chính tắc - 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  1  m) (1)  j 1  x  0( j  1  n) (2)  j - Bài toán dạng chính tắc có một hệ phương trình ràng buộc và các biến số đều không âm + (1) là nhóm các ràng buộc dạng phương trình gọi là các phương trình ràng buộc + (2) là nhóm các ràng buộc dạng bất phương trình gọi là các ràng buộc về dấu đối với các biến
- Ký hiệu: A = ((aij))mn gọi là ma trận điều kiện của bài toán Aj là véc tơ cột j của ma trận A- gọi là véc tơ điều kiện j c là véc tơ hệ số của các biến trong hàm mục tiêu b là véc tơ vế phải của hệ phương trình ràng buộc - Khi đó bài toán dạng chính tắc có thể viết dưới dạng n f (x)  cj xj Min(Max) f (x)  (c, x) Min(Max) j1 n Ax b  hoặc  xj Aj  b x  0  j1 x  0( j 1 n)  j
Mệnh đề - Mọi bài toán QHTT đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hai bài toán là như nhau và từ PATƯ của bài toán này có thể suy ra PATƯ của bài toán kia. - Các phép biến đổi tương đương như sau: + Nếu xj  0 thì đặt: xj’ = - xj  0  x j  x 'j  x ''j  + Nếu xj không có ràng buộc về dấu thì đặt:  ' '' x j , x j  0   n aij x j  xip  bi Nếu ràng buộc i có dạng aij x j  bi thì biến đổi:  n +  j 1 j 1 x p  0  i  n + n  aij x j  xip  bi Nếu ràng buộc i có dạng aij x j  bi thì biến đổi:  j 1  j 1 x p  0  i
Ví dụ 2 - Cho bài toán QHTT: f ( x )  2 x1  x 2  3 x 3  M in  x1  2 x 2  x 3  6 (1)  x  4 x  x  10 (2)  1  2 3  x2  x3  4 (3) x 0 (4) 1    x2 0 (5) - Đưa bài toán về dạng chính tắc tương đương
Định lý 1 - PA x của bài toán dạng chính tắc là PACB khi và chỉ khi hệ thống các véc tơ {Aj: xj > 0} là độc lập tuyến tính - Ví dụ 3: Cho bài toán QHTT f ( x )  2 x1  4 x 2  6 x 3  M in  3 x1  4 x 2  4 x 3  1 0 (1)    x1  x 2  4 x 3   1 (2)  x  0 ( j  1  3)  j Chứng tỏ véc tơ x0 = (2, 1, 0) là PACB bằng hai cách
Nhận xét - Với bài toán dạng chính tắc, không làm mất tính chất tổng quát ta giả thiết hệ phương trình ràng buộc gồm m phương trình độc lập và m < n, tức là r(A) = m < n - Bởi vì: + Nếu m = n thì hệ phương trình ràng trở thành hệ Cramer, hệ này có tối đa một nghiệm nên việc tìm PATƯ trở thành không cần thiết + Nếu m > n thì bằng phép biến đổi tương đương ta có thể đưa về hệ chỉ có n phương trình và hệ này cũng là hệ Cramer - Từ định lý 1 ta thấy: + Một PACB có tối đa m thành phần dương (?) + Một PACB không suy biến có đúng m thành phần dương (?) + Một PACB suy biến có ít hơn m thành phần dương (?)
Định nghĩa cơ sở của PACB - Xét bài toán dạng chính tắc và PACB x - Gọi m véc tơ {Aj} độc lập tuyến tính bao hàm hệ thống các véc tơ {Aj: xj > 0} là cơ sở của PACB x, ký hiệu một cách quy ước là J - Cơ sở J của PACB x bao hàm 3 nội dung: + Số phần tử của J là m + Hệ véc tơ {Aj: j  J} độc lập tuyến tính + {Aj: j  J}  {Aj: xj > 0} - Nếu PACB x không suy biến thì có một cơ sở duy nhất: {Aj: j  J}  {Aj: xj > 0} - Nếu PACB x suy biến thì có thể có nhiều cơ sở khác nhau mà phần chung của chúng là các véc tơ {Aj: xj > 0} - Với PACB x ta gọi: xj (j  J) gọi là thành phần cơ sở của PACB x: xj > 0  j  J xk(k  J) gọi là thành phần phi cơ sở của PACB x: k  J  xk = 0
3.2. Bài toán dạng chuẩn - Là bài toán dạng chính tắc có bi  0 (i) và mỗi phương trình ràng buộc đều có một biến với hệ số bằng 1 và không có mặt ở các phương trình khác. - Xác định véc tơ x = (x1, x2, …, xn) sao cho: n f (x)  c j 1 j x j  M in ( M a x )  x1  a 1 m  1 x m  1  ...  a 1 n x n  b1   x2  a 2 m  1 x m  1  ...  a 2 n x n  b 2   ....................................................................  x m  a m m  1 x m  1  ...  a m n x n  b m   x j  0( j  1  n)  - Bài toán dạng chuẩn cho ta PACB x0 = (b1, b2, …, bm, 0, …, 0) với cơ sở {Aj: j  J}  {ej: j = 1m} gọi là cơ sở đơn vị + Nếu bi > 0 (i) thì PACB x0 là PACB không suy biến + Nếu có ít nhất một bi = 0 thì PACB x0 PACB suy biến
Ví dụ 4 - Cho bài toán QHTT: f ( x )   2 x1  5 x 2  x 3  M a x  3 x1  2 x3  3 x 4  1 2 (1) 2 x  x  x  2 x  4 (2)  1 2 3 4   3 x1  4 x3  x 4   8 (3)  x j  0( j  1  4)  - Đưa bài toán về dạng chính tắc và dạng chuẩn - Xác định một PACB của bài toán và cho biết tính chất của PACB