›
›

Lý thuyết tài chính - Chương 1: Giới thiệu mô hình toán kinh tế

ppt 147 trang vanle 3010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Lý thuyết tài chính - Chương 1: Giới thiệu mô hình toán kinh tế", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptly_thuyet_tai_chinh_chuong_1_gioi_thieu_mo_hinh_toan_kinh_te.ppt

Nội dung text: Lý thuyết tài chính - Chương 1: Giới thiệu mô hình toán kinh tế

  1. Phần 2: Mô Hình Toán Kinh Tế Chương 1: Giới Thiệu Mô Hình Toán Kinh Tế
  2. I. Khái niệm mô hình kinh tế và mô hình toán kinh tế 1. Mô hình kinh tế: - Mô hình của một đối tượng là sự phản ánh hiện thực khách quan của một đối tượng; sự hình dung, tưởng tượng đối tượng đó bằng ý nghĩ của người nghiên cứu và việc trình bày, thể hiện, diễn đạt ý nghĩ đó bằng lời văn, chữ viết, sơ đồ, hình vẽ, hoặc một ngôn ngữ chuyên ngành. - Mô hình bao gồm nội dung của mô hình và hình thức thể hiện nội dung.
  3. 2. Mô hình toán kinh tế: Là mô hình kinh tế được trình bày bằng ngôn ngữ toán học. Ví dụ: Giả sử chúng ta muốn nghiên cứu, phân tích quá trình hình thành giá cả một loại hàng hoá A trên thị trường với giả định các yếu tố khác như điều kiện sản xuất hàng hoá A, thu nhập, sở thích người tiêu dùng đã cho trước và không thay đổi.
  4. Mô hình bằng lời: Tại thị trường hàng hoá A, nơi người bán, người mua gặp nhau và xuất hiện mức giá ban đầu. Với mức giá đó lượng hàng hoá người bán muốn bán gọi là mức cung, lượng hàng hoá người mua muốn mua gọi là mức cầu. Nếu cung lớn cầu thì người bán phải giảm giá do đó hình thành mức giá mới thấp hơn. Nếu cầu lớn hơn cung thì người mua sẵn sàng trả giá cao hơn để mua được hàng do đó mức giá mới cao hơn được hình thành. Với mức giá mới xuất hiện mức cung, mức cầu mới. Quá trình tiếp diễn cho đến khi cung bằng cầu.
  5. Mô hình toán kinh tế: - Gọi S, D là đường cung, đường cầu tương ứng. - Ứng với mức giá p ta có: S = S(p); D = D(p) Ta có mô hình cân bằng thị trường ký hiệu MHIA dưới đây: S = S(p) D = D(p) S = D
  6. Khi muốn đề cập đến tác động của thu nhập (M) và thuế (T) tới quá trình hình thành giá ta có mô hình MHIB dưới đây: S = S(p, T) D = D(p, M, T) S = D
  7. II. Cấu trúc mô hình toán kinh tế: - Mô hình toán kinh tế là một tập hợp gồm các biến số và các hệ thức toán học liên hệ giữa chúng nhằm diễn tả đối tượng liên quan đến sự kiện, hiện tượng kinh tế. Mô hình toán kinh tế gồm: các biến, các phương trình, các bất phương trình.
  8. 1. Các biến số của mô hình: - Biến nội sinh (biến được giải thích): + Là các biến mà về bản chất chúng phản ánh, thể hiện trực tiếp sự kiện, hiện tượng kinh tế và giá trị của chúng phụ thuộc vào giá trị của các biến khác trong mô hình. + Nếu biết giá trị của các biến khác trong mô hình ta có thể xác định giá trị cụ thể của biến nội sinh bằng cách giải các hệ thức. Ví dụ: Trong mô hình MHIA các biến S, D, p là các biến nội sinh. - Biến ngoại sinh (biến giải thích) Là các biến độc lập với các biến khác trong mô hình, giá trị của chúng tồn tại bên ngoài mô hình. Ví dụ: Trong mô hình MHIB các biến M, T là các biến ngoại sinh.
  9. - Tham số(thông số): là các biến số mà trong phạm vi nghiên cứu chúng thể hiện các đặc trưng tương đối ổn định, ít biến động. Các tham số của mô hình phản ánh xu hướng, mức độ ảnh hưởng của các biến tới các biến nội sinh. Ví dụ: Nếu trong mô hình MHIB có S = p.T thì , ,  là các tham số của mô hình Lưu ý: Cùng một biến số, trong các mô hình khác nhau có thể đóng vai trò khác nhau
  10. 2. Mối liên hệ giữa các biến số- Các phương trình của mô hình: a. Phương trình định nghĩa: phương trình thể hiện quan hệ định nghĩa giữa các biến số hoặc hai biểu thức ở hai vế của phương trình. Ví dụ: + Lợi nhuận (LN) được định nghĩa là hiệu số của tổng doanh thu (TR) và tổng chi phí (TC): LN = TR – TC + trong mô hình MHIA, các phương trình là các phương trình định nghĩa.
  11. b. Phương trình hành vi: là phương trình mô tả quan hệ giữa các biến do tác động của các quy luật hoặc do giả định. - Từ phương trình hành vi ta có thể biết sự biến động của biến nội sinh- “hành vi” của biến này khi các biến số khác thay đổi. Ví dụ: Trong mô hình MHIA có S = S(p), D = D(p) chúng phản ánh phản ứng của người sản xuất và người tiêu dùng trước sự thay đổi của giá cả.
  12. c. Phương trình điều kiện: Là phương trình mô tả quan hệ giữa các biến số trong các tình huống có điều kiện mà mô hình đề cập. Ví dụ: Trong mô hình MHIA, phương trình S = D là phương trình điều kiện vì nó thể hiện điều kiện cân bằng thị trường.
  13. III. Phân loại mô hình toán kinh tế: 1. Phân loại mô hình theo đặc điểm cấu trúc và công cụ toán học sử dụng: - Mô hình tối ưu: là mô hình phản ánh sự lựa chọn cách thức hoạt động nhằm tối ưu hoá một hoặc một số chỉ tiêu định trước. - Mô hình cân bằng: là lớp mô hình xác định sự tồn tại của trạng thái bằng nếu có và phân tích sự biến động của trạng thái này khi các biến ngoại sinh hay các tham số thay đổi. - Mô hình tất định, mô hình ngẫu nhiên: Mô hình với các biến là tất định (phi ngẫu nhiên) gọi là mô hình tất định, nếu có chưa biến ngẫu nhiên gọi là mô hình ngẫu nhiên.
  14. - Mô hình tĩnh, mô hình động: Mô hình có các biến mô tả hiện tượng kinh tế tồn tại ở một thời điểm hay một khoảng thời gian đã xác định gọi là mô hình tĩnh. Mô hình mô tả hiện tượng kinh tế trong đó các biến số phụ thuộc vào thời gian gọi là mô hình động.
  15. 2. Phân loại mô hình theo quy mô, phạm vi, thời gian: - Mô hình vĩ mô: Mô hình mô tả các hiện tượng kinh tế liên quan đến một nền kinh tế, một khu vực kinh tế gồm một số nước. - Mô hình vi mô: Mô hình mô tả một thực thể kinh tế nhỏ hoặc những hiện tượng kinh tế với các yếu tố ảnh hưởng trong phạm vi hẹp và ở mức độ chi tiết. - Theo thời hạn mà mô hình đề cập ta có: Mô hình ngắn hạn, mô hình dài hạn.
  16. Chương 2: Mô Hình Tối Ưu Tuyến Tính
  17. I. Một số ví dụ thực tế dẫn đến Bài toán quy hoạch tuyến tính (QHTT): VD 1: Đầu tư tài chính: Một công ty đầu tư định dùng khoản quỹ đầu tư 500 triệu đồng để mua một số cổ phiếu trên thị trường chứng khoán. Công ty đưa ra các giới hạn trên của số tiền mua từng loại chứng khoán. Bảng dưới đây cho các số liệu về các giới hạn này cũng như lãi suất của các chứng khoán .
  18. Loại chứng Lãi suất (trung Giới hạn mua khoán bình) A 7% 100 triệu B 8,5% 300 triệu C 7,8% 250 triệu D 8,2% 320 triệu Để ngăn ngừa rủi ro trong đầu tư, công ty còn quy định khoản đầu tư vào loại cổ phiếu A và C phải chiếm ít nhất là 55%, loại cổ phiếu B phải chiếm ít nhất 15% trong tổng số danh mục đầu tư thực hiện. Hãy xác định số tiền công ty mua từng loại cổ phiếu sao không vượt quá khoản dự kiến ban đầu, đảm bảo đòi hỏi về đa dạng hoá đồng thời đạt mức lãi (trung bình) cao nhất.
  19. Mô hình hoá: Gọi x1, x2, x3, x4 là số tiền mua các loại cổ phiếu A, B, C, D. - Tổng số tiền mua các loại cổ phiếu A, B, C, D: x1 + x2 + x3 + x4 - Tổng tiền lãi: 0,07x1 + 0,085x2 + 0,078x3 + 0,082x4 Ta có bài toán: Tìm vectơ x = ( x1, x2, x3, x4) sao cho f(x) = 0,07x1 + 0,085x2 + 0,078x3 + 0,082x4 max và thoả mãn các điều kiện: x1 + x2 + x3 + x4 ≤ 500 x1 ≤ 100; x2 ≤ 300; x3 ≤ 250; x4 ≤ 320 x1 + x3 0,55(x1 + x2 + x3 + x4) x2 0,15(x1 + x2 + x3 + x4) x1, x2, x3, x4 0
  20. VD 2: Bài toán vận tải Một công ty kinh doanh xăng dầu hàng tuần cung ứng xăng dầu cho 3 trạm bán lẻ A, B, C. Công ty có thể đưa xăng từ kho I và II. Dự trù cung ứng xăng của kho I là 20 tấn, kho II là 40 tấn. Chi phí cho việc cung ứng xăng từ kho đến các trạm được cho trong bảng dưới đây: Đơn vị: Nghìn đồng/tấn
  21. Trạm kho A B C I 500 400 700 II 600 500 500 Nhu cầu tiêu thụ xăng hàng tuần của 3 trạm lần lượt là 20, 15, 15 (tấn). Công ty cần lập kế hoạch cung ứng xăng từ dự trù của các kho đến các trạm để đảm bảo đủ nhu cầu của các trạm với tổng chi phí là nhỏ nhất.
  22. Mô hình hoá: - Gọi lượng xăng chuyển từ kho I, kho II đến các trạm lần lượt là x1A, x1B, x1C và x2A, x2B, x2C (tấn). - Tổng lượng xăng chuyển từ kho I đến các trạm: x1A+x1B+x1C - Tổng lượng xăng chuyển từ kho II đến các trạm:x2A+x2B+x2C - Tổng lượng xăng trạm A nhận được từ 2 kho: x1A + x2A - Tổng lượng xăng trạm B nhận được từ 2 kho: x1B + x2B - Tổng lượng xăng trạm C nhận được từ 2 kho: x1C + x2C - Tổng chi phí tương ứng là: 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C
  23. Ta có bài toán sau: Xác định vectơ x = ( x1A, x1B, x1C, x2A, x2B, x2C ) sao cho: f(x) = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C min Với điều kiện: x1A + x2A = 20 x1B + x2B = 15 x1C + x2C = 15 x1A + x1B + x1C ≤ 20 x2A + x2B + x2C ≤ 40 x1A 0, x1B 0, x1C 0, x2A 0, x2B 0, x2C 0
  24. II. Bài toán QHTT tổng quát và các dạng đặc biệt: 1. Dạng tổng quát: Tìm x = (x1, x2, , xn) sao cho 1) 2) Nếu ký hiệu D là tập tất cả các vectơ x thoả mãn hệ điều kiện 2) thì đây chính là bài toán tìm min (max) của hàm f(x) trên D.
  25. VD 1: Cho bài toán QHTT Tìm x = (x1, x2, x3, x4) sao cho 1) x1 + x2 – x3 = 2 (1) 2x1 + x2 3 (2) 2) x2 + x3 + x4 4 (3) x2 0 (4) x3 0 (5) x4 0 (6)
  26. 2. Một số khái niệm và định nghĩa:  f(x): gọi là hàm mục tiêu  Mỗi phương trình hoặc bất phương trình trong hệ điều kiện 2) gọi là một ràng buộc. Những ràng buộc dạng đặc biệt: xj 0 hay xj ≤ 0, gọi là các ràng buộc dấu đối với biến xj  Ứng với ràng buộc thứ i ta ký hiệu A*i là vectơ dòng có các thành phần là các hệ số của biến xj  Một nhóm ràng buộc có hệ vectơ A*i tương ứng độc lập tuyến tính được gọi là các ràng buộc độc lập tuyến tính.  Xét các ràng buộc không phải ràng buộc dấu, hệ vectơ A*i tương ứng với các ràng buộc này tạo thành một ma trận, kí hiệu A. Ma trận A có n cột, vectơ cột thứ j – kí hiệu là Aj.
  27. Ví dụ 2: Xác định x = (x1, x2, x3, x4, x5) sao cho f(x) = 3x1 +x2 -5x3 + 2x4 + x5 min x1 +x2 +x3 + x4 + x5 = 21 2x1 +6x2 -3x3 + 2x4 - 2x5 2 -3x1 +x2 +2x3 -3x4 + 3x5 = 28 xj 0 (j = 1, 2, , 5) A*1 = (1, 1, 1, 1, 1); A*2 = (2, 6, -3, 2, -2); A*3 = (-3, 1, 2, -3, 3)
  28.  Phương án: Một vectơ x thỏa mãn mọi ràng buộc của bài toán gọi là một phương án (PA). + Nếu đối với PA x mà ràng buộc i thoả mãn với dấu đẳng thức thì ta nói PA x 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 đối với PA x mà ràng buộc i thỏa mãn với dấu bất đẳng thức thực sự thì ta nói PA x thoả mãn lỏng ràng buộc i hay ràng buộc là lỏng đối với PA x.
  29.  Phương án cực biên (PACB): Một phương án thoả mãn chặt n ràng buộc độc lập tuyến tính gọi là phương án cực biên (PACB). PACB thoả mãn chặt đúng n ràng buộc gọi là PACB không suy biến, thoả mãn chặt hơn n ràng buộc gọi là PACB suy biến.  Phương án tối ưu (PATƯ): Một phương án mà tại đó trị số hàm mục tiêu đạt cực tiểu (hoặc cực đại) gọi là PATƯ. Một bài toán có ít nhất một PATƯ gọi là bài toán giải được, bài toán không có PATƯ gọi là bài toán không giải được.
  30. VD 3: Xét bài toán f(x) = x1 + 6x2 max x1 + 5x2 ≤ 20 x1 5 x2 ≤ 4 x2 0 Bài toán có các PACB: xA = (5, 3), xB = (5, 0), xC=(20, 0)
  31. Dùng đồ thị để biểu diễn tập phương án: x2 4 A 3 B C 0 5 20 x1
  32. 3. Các dạng đặc biệt: a. Bài toán dạng chính tắc: Tìm vtơ x = (x1, x2, , xn) sao cho Mệnh đề: Mọi bài toán quy hoạch tuyến tính đều có thể đưa về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ PA, PATƯ của bài toán này suy ra PA, PATƯ của bài toán kia.
  33. Cách đưa một bài toán về dạng chính tắc:  Nếu xj ≤ 0 thì đặt tj = -xj tj 0. Nếu biến số xj không có ràng buộc dấu thì ta đặt xj = với  Nếu một ràng buộc có dạng: thì thay bằng với và h ệ s ố c ủ a trong f(x) bằng 0.  Tương tự nếu ràng buộc có dạng thì thay bằng với
  34. b. Bài toán dạng chuẩn: là bài toán có dạng x1 + a1,m+1xm+1 + + a1nxn = b1 x2 + a2,m+1xm+1 + + a2nxn = b2 xm+ am,m+1xm+1 + + amnxn = bm 0 Btoán có một PACB là x = (b1, b2, , bm, 0, , 0)
  35. III. Các tính chất chung của bài toán QHTT: Tính chất 1: Sự tồn tại PACB Nếu bài toán có PA và hạng của ma trận hệ ràng buộc bằng n thì bài toán có PACB. Tính chất 2: Sự tồn tại PATƯ Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn dưới (trên) trên tập phương án thì bài toán có PATƯ (giải được). Nếu btoán có PACB và giải được thì btoán có PACB tối ưu. Tính chất 3: Tính hữu hạn của số PACB Số PACB của mọi bài toán quy hoạch tuyến tính đều hữu hạn.
  36. IV. Phương pháp đơn hình giải bài toán QHTT: 1. Nội dung của phương pháp: Xuất phát từ một PACB tìm cách đánh giá PACB ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một PACB mới tốt hơn, quá trình được lặp lại, vì số PACB là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được hoặc sẽ tìm được PACB tối ưu. Ta sẽ xét bài toán dạng chính tắc trong quá trình giới thiệu phương pháp đơn hình.
  37. 2. Đặc điểm của PACB của bài toán dạng chính tắc: Định lý: PA x = (x1, x2, , xn) của bài toán dạng chính tắc là cực biên khi và chỉ khi hệ các vectơ Aj / xj>0 là đ.lập tuyến tính. Nhận xét: Không làm mất tính tổng quát ta luôn có thể giả thiết hệ phương trình ràng buộc của bài toán dạng chính tắc gồm m phương trình độc lập tuyến tính với m < n, tức r(A) = m. Khi đó một PACB sẽ có không quá m thành phần dương. PACB không suy biến có đúng m thành phần dương, PACB suy biến có ít hơn m thành phần dương.
  38. 3. Cơ sở của PACB của bài toán dạng chính tắc: ĐN:Ta gọi một hệ m vectơ Aj độc lập tuyến tính bao hàm hệ các vectơ Aj/ xj > 0 là cơ sở của PACB x. Ký hiệu một cách quy ước là J, trong đó J = {j: Aj nằm trong cơ sở} Chú ý: PACB x có cơ sở là J, cần phải hiểu: - Số phần tử của J là m - {Aj, j J} độc lập tuyến tính - {Aj, j J}  {Aj, xj>0} Đối với PACB x =(x1, x2, , xn) cơ sở J ta gọi các thành phần xj (j J) là thành phần cơ sở, xk (k J) là thành phần phi cơ sở. Dễ thấy xk = 0 (k J).
  39. PACB x, cơ sở J ta có: - Các vectơ Ak (k J) cũng biểu diễn được qua cơ sở J. Gọi các hệ số phân tích của Ak là xjk tức là: Ak = - Ta xác định đại lượng k (k J) bằng công thức sau - k được gọi là ước lượng của biến xk theo cơ sở J. - Nói riêng thì
  40. 4. Quan hệ giữa PACB và PA của bài toán dạng ctắc: 0 Đối với PACB x cơ sở J0, với mỗi chỉ số k J0 xác định một vectơ zk – gọi là phương zk có các thành phần như sau: Xét sự di chuyển theo phương zk, tức là xét các vectơ có dạng x() = x0 + .zk với  0. Thay vtơ x() = x0 + .zk vào các phương trình ràng buộc luôn thoả mãn. Để x() là PA thì chỉ cần x() 0.
  41. Ta có: 0 Vậy tóm lại để x() là phương án thì chỉ cần x j - .xjk 0 (j J0). Có 2 trường hợp xảy ra: TH 1: Nếu xjk ≤ 0 (j J0) thì x() là PA   0. Khi đó ta gọi zk là phương vô hạn. 0 TH 2: Nếu  xjk > 0, từ x j - .xjk 0 ứng với xjk > 0, suy ra 0  ≤ x j /xjk . Gọi Như vậy x() là PA khi 0 ≤  ≤ 0. k Trường hợp này z gọi là phương hữu hạn và x(0) là PACB mới.
  42. Trong cả 2 trường hợp ta luôn có: 0 f(x()) = f(x ) - . k Với  > 0 ta có 0 k  Nếu k > 0 thì f(x()) < f(x ), khi đó z gọi là phương giảm. k  Nếu k < 0 thì z gọi là phương tăng. k  Nếu k = 0 thì z là phương không đổi.
  43. 5. Các định lý cơ bản: Dưới đây ta xét bài toán dạng chính tắc với hàm mục tiêu f(x) min. Định lý 1: (Dấu hiệu tối ưu của PACB) 0 Nếu đối với PACB x , cơ sở J0 của bài toán dạng chính 0 tắc mà k 0 (k J0) thì x là PATƯ. Chú ý: 0 +) Nếu k < 0, k J0 thì x là PATƯ duy nhất. +) Nếu x0 là PACB không suy biến thì x0 là PATƯ khi và chỉ khi k 0 (k J0).
  44. Định lý 2: (Dấu hiệu bài toán không giải được) 0 Nếu đối với PACB x cơ sở J0 của bài toán dạng chính tắc tồn tại một k > 0 mà xjk 0 (j J0) thì bài toán không giải được. Định lý 3: (Dấu hiệu điều chỉnh PACB) 0 Nếu đối với PACB x cơ sở J0 của bài toán dạng chính tắc mà mỗi k > 0 đều tồn tại xjk > 0 thì có thể chuyển sang một PACB mới tốt hơn trong trường hợp bài toán không suy biến (nghĩa là bài toán mà mọi PACB đều không suy biến ).
  45. 6. Thuật toán của phương pháp đơn hình: Giả thiết bài toán dạng chính tắc có hàm mục tiêu f(x) 0 min, đã biết một PACB x cơ sở J0, không làm mất tính tổng quát có thể giả thiết J0 = 1, 2, , m tức là cơ sở gồm các vectơ {A1, A2, , Am}. Thuật toán gồm các bước sau: Bước 1: Lập bảng đơn hình ứng với PACB x0
  46. Hệ Cơ Phương c1 c2 cr cm cm+1 cs cn số sở án x1 x2 xr xm xm+1 xs xn 0 c1 x1 x 1 1 0 0 0 x1,m+1 x1s x1n 0 c2 x2 x 2 0 1 0 0 x2,m+1 x2s x2n 0 cr xr x r 0 0 1 0 xr,m+1 [xrs] xrn 0 cm xm x m 0 0 0 1 xm,m+1 xms xmn 0 f(x) f(x ) 0 0 0 0 m+1 s n
  47. Bước 2: Kiểm tra dấu hiệu tối ưu: 0 Nếu k ≤ 0, k J0 thì x là PATƯ, nếu tồn tại một k > 0 thì chuyển sang bước 3. Bước 3: Kiểm tra tính không giải được của bài toán: Nếu tồn tại một k > 0 mà xjk ≤ 0,  j J0 thì bài toán không giải được. Nếu với mỗi k > 0 đều có xjk > 0 thì chuyển sang bước 4.
  48. Bước 4: Chọn vectơ đưa vào cơ sở và xác định vectơ loại khỏi cơ sở. + Chọn vectơ đưa vào: Giả sử max k = s ( k>0). Vectơ As được đưa vào cơ sở. + Chọn vectơ loại ra: Tính , giả sử, vectơ Ar bị loại khỏi cơ sở, phần tử trục của phép biến đổi là xrs, trong bảng đóng khung phần tử này. Thành lập một mẫu bảng đơn hình mới, ở vị trí xr ghi xs và ghi cs thay cho cr. Chuyển sang bước 5
  49. Bước 5: Biến đổi bảng: Tính các dòng của bảng mới (bắt đầu từ cột thứ 3 trở đi) theo quy tắc sau - Để tính dòng vectơ đưa vào (xs) trong bảng mới ta lấy dòng vectơ loại ra (xr) trong bảng cũ chia cho phần tử trục. Dòng này được gọi là dòng chuẩn. - Để tính dòng (xj) trong bảng mới, ta lấy dòng (xj) trong bảng cũ trừ đi tích dòng chuẩn với xjs - Để tính dòng cuối trong bảng mới ta lấy dòng cuối của bảng cũ trừ đi tích dòng chuẩn với s
  50. VD 1: Giải bằng phương pháp đơn hình bài toán f(x) = -4x1 + 3x3 - x4 -5x5 min 4x1 + x2 +4x4 + 2x5 = 6 (1) 2x1 + x3 + 3x4 -3x5 = 8 (2) 3x1 + 5x4 + 5x5 ≤ 10 (3) xj 0 (j = 1, 2, 3, 4, 5) Giải: Đưa bài toán về dạng chính tắc. f(x) = -4x1 + 3x3 - x4 -5x5 + 0x6 min 4x1 + x2 +4x4 + 2x5 = 6 (1’) 2x1 + x3 + 3x4 -3x5 = 8 (2’) 3x1 + 5x4 + 5x5 +x6 = 10 (3’) xj 0 (j = 1, 2, , 6) Bài toán trên ở dạng chuẩn, có PACB x0=(0, 6, 8, 0, 0, 10) cơ sở J0 = {2, 3, 6} là cơ sở đơn vị. Lập bảng đơn hình:
  51. HS CS PA - 4 0 3 -1 -5 0 x1 x2 x3 x4 x5 x6 0 x2 6 [4] 1 0 4 2 0 3 x3 8 2 0 1 3 -3 0 0 x6 10 3 0 0 5 5 1 f(x) 24 10 0 0 10 -4 0 -4 x1 3/2 1 1/4 0 1 1/2 0 dc 3 x3 5 0 -1/2 1 1 -4 0 0 x6 11/2 0 -3/4 0 2 7/2 1 f(x) 9 0 -5/2 0 0 -9 0 Đến bảng đơn hình thứ 2 ta có k 0 (k J) nên bài toán có PATƯ x* = (3/2, 0, 5, 0, 0) với fmin = f(x*) = 9.
  52. Các chú ý khi áp dụng thuật toán 1) Đối với bài toán có hàm f(x) max thì có thể chuyển về giải bài toán với hàm g(x) = - f(x) min, với fmax = - gmin hoặc cũng có thể giải trực tiếp với dấu hiệu tối ưu là k 0 (k J0). 2) Trường hợp bài toán suy biến thì 0 có thể bằng 0, khi 0 = 0 vẫn thực hiện thuật toán một cách bình thường, nghĩa là vectơ ứng với 0 vẫn bị loại khỏi cơ sở. 3) Nếu khi chọn vectơ đưa vào cơ sở hoặc đưa ra khỏi cơ sở có nhiều vectơ thuộc diện lựa chọn thì ta tuỳ chọn một trong số đó.
  53. 4) Khi áp dụng thuật toán sẽ có 2 trường hợp xảy ra: TH 1: Bài toán ở dạng chuẩn, nó cho ngay một PACB x0, cơ sở J0 là cơ sở đơn vị, ta đưa toàn bộ các hệ số ở vế trái của các phương trình ràng buộc vào bảng đơn hình và lập được ngay bảng đơn hình đối với PACB này. 0 TH 2: Khi PACB x , cơ sở J0 chưa phải là cơ sở đơn vị, ta phải biến đổi ma trận hệ số mở rộngA bằng các phép biến đổi sơ cấp trên dòng của ma trận, đưa các vectơ cơ sở thành các vectơ đơn vị khác nhau. Sau đó đưa toàn bộ các phần tử trong ma trận mở rộng cuối cùng vào trong bảng đơn hình và thực hiện tiếp thuật toán.
  54. VD 2: Cho bài toán f(x) = -2x1 - 6x2 + 8x3 – 5x4 min x1 + 2x2 – 3x3 + x4 = 8 (1) -2x1 + x2 + x3 – 5x4 ≤ 2 (2) 4x1 + 7x2 -8x3 +2x4 20 (3) xj 0 (j =14 ) và vectơ x0 = (8, 0, 0, 0). a. Chứng tỏ x0 là phương án cực biên, lợi dụng x0 giải bài toán bằng phương pháp đơn hình. b. Tìm một phương án x có trị số f(x) = - 50. Giải:
  55. a. Vectơ x0 thoả mãn mọi ràng buộc của bài toán, thoả mãn chặt ràng buộc (1) và 3 ràng buộc dấu, các ràng buộc này đltt nên x0 là PACB của bài toán. Đưa bài toán về dạng chính tắc: f(x) = -2x1 - 6x2 + 8x3 – 5x4 min x1 + 2x2 – 3x3 + x4 = 8 -2x1 + x2 + x3 – 5x4 + x5 = 2 4x1 + 7x2 - 8x3 + 2x4 - x6 = 20 xj 0 (j = 1 6) 0 PACB tương ứng x = (8, 0, 0, 0, 18, 12) cơ sở {A1, A5, A6}. Đây không phải là cơ sở đơn vị. Để lập bảng đơn hình ta phải biến đổi ma trận mở rộng
  56. Bảng đơn hình:
  57. HS CS PA -2 -6 8 -5 0 0 x1 x2 x3 x4 x5 x6 -2 x1 8 1 2 -3 1 0 0 0 x5 18 0 5 -5 -3 1 0 0 x6 12 0 1 -4 [ 2 ] 0 1 f(x) -16 0 2 -2 3 0 0 -2 x1 2 1 3/2 -1 0 0 -1/2 0 x5 36 0 13/2 -11 0 1 3/2 -5 x4 6 0 1/2 -2 1 0 1/2 dc f(x) -34 0 1/2 4 0 0 -3/2 Đến bảng đơn hình thứ 2 ta có 3 = 4 > 0 mà xj3 < 0 (j J) nên bài toán không giải được.
  58. b. Tìm một phương án có trị số f(x) = - 50. Gọi PA tương ứng ở bảng đơn hình thứ 2 là x*, từ x* di chuyển theo phương z3 là phương giảm vô hạn ta được các PA có dạng: x() = x* + .z3,  0 Do đó: f(x()) = f(x*) - . 3 Như vậy -50 = -34 – 4.  = 4 Ta có: x* = (2,0,0,6,36,0) z3 = (1,0,1,2,11,0) Vậy PA cần tìm là: x = (6,0,4,14,80,0)
  59. V. Tìm phương án cực biên: Khi bài toán ở dạng chính tắc nhưng không phải dạng chuẩn đồng thời không biết PACB, như vậy muốn áp dụng thuật toán cần tìm một PACB của bài toán. Xét bài toán dạng chính tắc: bi 0 (i = 1m)
  60. Từ bài toán đã cho xây dựng một bài toán phụ, ký hiệu là P bằng cách cộng vào vế trái phương trình ràng buộc i g một biến giả x i (i = 1  m) với hàm mục tiêu là tổng các biến giả đã thêm vào và hàm mục tiêu này phải đạt cực tiểu. g g g g Ký hiệu x = (x 1, x 2, , x m) là vectơ các biến giả và hàm mục tiêu của bài toán phụ là P(x, xg). Khi đó bài toán phụ có dạng:
  61. Nhận xét:  Vto x là PA của bài toán xuất phát khi và chỉ khi (x,xg= 0) là PA của bài toán phụ P. Do đó x là PACB của bài toán xuất phát khi và chỉ khi (x, xg= 0) là PACB của bài toán P.  Việc tìm PACB của bài toán xuất phát (nếu có) sẽ dẫn tới tìm PACB của bài toán P có dạng (x, xg= 0).  Bài toán P có dạng chuẩn và P(x, xg) 0,  PA (x, xg) nên bài toán P luôn giải được. Do P(x, xg = 0) = 0 nên (x, xg = 0) là PATƯ của bài toán P.
  62. Như vậy: Việc tìm PACB của bài toán xuất phát dẫn tới việc giải bài toán P. Dùng thuật toán đơn hình giải bài toán P tìm được PATƯ và Có 2 trường hợp xảy ra: TH1: Pmin > 0 Khi đó bài toán xuất phát không có phương án.
  63. TH 2: Pmin = 0 Khi đó = 0 (i = 1m) hay = 0, PATƯ của P có dạng do đó x là PACB của bài toán xuất phát. Hai khả năng có thể xảy ra: a. Trong cơ sở của PACB tối ưu không có các g vectơ tương ứng với các biến giả. Ta loại các cột x i , tính lại hàng ước lượng k theo hàm f và tiếp tục thuật toán. b. Trong cơ sở của PACB TƯ có ít nhất một vectơ g biến giả.Ta loại các cột ứng với k(P) < 0 và các cột x i phi cơ sở, sau đó tính lại các ước lượng k theo theo hàm f và tiếp tục thuật toán.
  64. VD 1: Giải bài toán sau bằng phương pháp đơn hình: f(x) = 3x1 + 4x2 + 2x3 + 2x4 min 2x1 + 2x2 + x4 = 28 x1 + 5x2 + 3x3 – 2x4 ≤ 31 2x1 – 2x2 + 2x3 + x4 = 16 xj 0 (j = 1 4) Giải: Đưa bài toán về dạng chính tắc: f(x) = 3x1 + 4x2 + 2x3 + 2x4 min 2x1 + 2x2 + x4 = 28 x1 + 5x2 + 3x3 – 2x4 + x5 = 31 2x1 – 2x2 + 2x3 + x4 = 16 xj 0 (j = 15)
  65. Ta thấy bài toán không phải dạng chuẩn nên thành lập bài toán phụ: g g g P(x, x ) = x 1 + x 3 min g 2x1 + 2x2 + x4 + x 1 = 28 x1 + 5x2 + 3x3 – 2x4 + x5 = 31 g 2x1 – 2x2 + 2x3 + x4 + x 3 = 16 g xj 0 (j = 15), x 0
  66. HS CS PA 3 4 2 2 0 1 1 g g x1 x2 x3 x4 x5 x 1 x 3 g 1 x 1 28 2 2 0 1 0 1 0 0 x5 31 1 5 3 -2 1 0 0 g 1 x 3 16 [2 ] - 2 2 1 0 0 1 P 44 4 0 2 2 g 0 0 0 1 x 1 12 0 [ 4 ] -2 0 0 1 0 x5 23 0 6 2 -5/2 1 0 0 x1 8 1 -1 1 1/2 0 0 dc P 12 0 4 -2 0 0 0 4 x2 3 0 1 -1/2 0 0 dc 0 x5 5 0 0 5 -5/2 1 3 x1 11 1 0 1/2 1/2 0 f(x) 45 0 0 -5/2 -1/2 0 Bài toán có PATƯ duy nhất x* = (11,3,0,0) và fmin = 45
  67. Khi giải bài toán P cần chú ý một số đặc điểm sau: • Khi xây dựng bài toán phụ chỉ cộng thêm biến giả vào những phương trình cần thiết. • Một biến giả đã bị loại khỏi cơ sở thì cột tương ứng không cần tính ở các bước tiếp theo. • Chỉ được áp dụng công thức đổi cơ sở cho hàng ước lượng khi hai bảng kế tiếp có cùng tên hàm mục tiêu. • Khi tất cả các biến giả bị loại khỏi cơ sở thì kết thúc việc giải bài toán P, tính lại dòng ước lương k theo hàm f và tiếp tục thuật toán.
  68. VD 2: Giải bài toán sau bằng phương pháp đơn hình: f(x) = - 4x1 - 2x2 + 4x3 - x4 min x1 + x2 + 2x3 + x4 = 15 2x2 + x3 – 2x4 = 6 2x1 + 5x2 – x4 = 45 xj 0 (j = 1 4) Giải: Lập bài toán phụ: g g g g P(x, x ) = x 1 + x 2+ x 3 min g x1 + x2 + 2x3 + x4 +x 1 = 15 g 2x2 + x3 – 2x4 + x 2 = 6 g 2x1 + 5x2 – x4 +x 3 = 45 g xj 0 (j = 1 5), x 0
  69. HS CS PA 1 1 1 g g g x1 x2 x3 x4 x 1 x 2 x 3 g 1 x 1 15 1 1 2 1 1 0 0 g 1 x 2 6 0 [2 ] 1 -2 0 1 0 g 1 x 3 45 2 5 0 -1 0 0 1 P 66 3 8 3 -2 g 0 0 0 1 x 1 12 1 0 3/2 [ 2 ] 1 0 0 x2 3 0 1 1/2 -1 0 0 dc g 1 x 3 30 2 0 -5/2 4 0 1 P 42 3 0 -1 6 0 0 0 x4 6 1/2 0 3/4 1 0 dc 0 x2 9 1/2 1 5/4 0 0 g 1 x 3 6 0 0 -11/2 0 1 P 6 0 0 -11/2 0 0 0 0 Do Pmin = 6 >0 nên bài toán k có PA. Vậy bài toán k giải được
  70. VD 3: Giải bài toán sau bằng phương pháp đơn hình: f(x) = 6x1 + 2 x2 + x3 min 2x1 + 5x2 + 3x3 10 4x1 - 3x2 + 2x3 = 16 2x1 + 4x2 + x3 = 8 xj (j = 1, 2, 3) Giải: Đưa bài toán về dạng chính tắc và lập bài toán P. g g g P(x, x ) = x 2 + x 3 min 2x1 + 5x2 + 3x3 + x4 = 10 g 4x1 - 3x2 + 2x3 + x 2 =16 g 2x1 + 4x2 + x3 + x 3 =8 g g xj 0(j = 1 4); x 2, x 3 0
  71. HS CS PA 6 2 1 0 1 1 g g x1 x2 x3 x4 x 2 x 3 0 x4 10 2 5 3 1 0 0 g 1 x 2 16 4 -3 2 0 1 0 g 1 x 3 8 [2 ] 4 1 0 0 1 P 24 6 1 3 0 0 x4 2 0 0 0 1 0 [2 ] 1 0 g 0 1 x 2 0 0 -11 0 0 1 6 0 x1 4 1 2 1/2 0 0 dc P 0 0 -11 0 0 0 f(x) 24 0 2 0 0 1 x3 1 0 1 1/2 0 dc g 0 x 2 0 0 0 0 1 6 x 7/2 1 0 -1/4 0 1 f(x ) 22 0 -1 0 0
  72. XÐt bµi to¸n QHTT: f(x) = x1 + 3x2 + 3x3 min 5x1 + 3x2 + 6x3 8 (1) -x1 - 2x2 -2 (2) x3 1/4 (3) 3x1 + x2 + x3 4 (4) -x1 - x3 -1 (5) xj 0 (j = 1, 2, 3) Bµi to¸n nµy nÕu gi¶i trùc tiÕp b»ng ph­¬ng ph¸p ®¬n h×nh sÏ rÊt dµi, v× khi ®ã bµi to¸n phô cã 5 Èn gi¶. ChÝnh v× vËy mçi BT QHTT ta ®Òu thµnh lËp mét bto¸n QHTT kh¸c theo mét quy t¾c nhÊt ®Þnh gäi lµ Bµi to¸n §èi ngÉu cña Bto¸n ®· cho vµ ta sÏ ®i nghiªn cøu mèi q.hÖ gi÷a cÆp bµi to¸n ®èi ngÉu.
  73. VI. Bµi to¸n ®èi ngÉu 1- C¸ch thµnh lËp: a. CÆp bµi to¸n ®èi ngÉu kh«ng ®èi xøng: XÐt bµi to¸n d¹ng chÝnh t¾c (I): Bµi to¸n ®èi ngÉu cña bµi to¸n (I), k/h cã d¹ng sau:
  74. Nhận xét:  NÕu f(x) min th× max vµ hÖ rµng buéc cña bµi to¸n ®èi ngÉu cã d¹ng “ ≤ ”.  NÕu f(x) max th× min vµ hÖ rµng buéc cña bµi to¸n ®èi ngÉu cã d¹ng “ ≥ “.  Số ràng buộc (không kể ràng buộc dấu của bài toán này) bằng số biến số của bài toán kia.  HÖ sè trong hµm môc tiªu cña bµi to¸n nµy lµ vÕ ph¶i cña hÖ rµng buéc trong bµi to¸n kia.  Ma trËn ®iÒu kiÖn trong hai bµi to¸n lµ chuyÓn vÞ cña nhau.
  75. CÆp rµng buéc ®èi ngÉu: Ta gäi 2 rµng buéc bÊt ®¼ng thøc (kÓ c¶ rµng buéc dÊu) trong hai bµi to¸n cïng t­¬ng øng víi mét chØ sè lµ mét cÆp rµng buéc ®èi ngÉu. Trong bµi to¸n (I) vµ cã n cÆp rµng buéc ®èi ngÉu:
  76. VÝ dô 1: ViÕt bµi to¸n ®èi ngÉu cña bµi to¸n sau vµ chØ râ c¸c cÆp rµng buéc ®èi ngÉu: f(x)= -4x1 + 3x2 - 5x4 + x5 min 2x2 - x3 + 4x4 - 2x5 + 7x6 = -12 -2x1+ 2x2 +5x3 + 3x5 = 3 3x1 - 3x2+ 5x3- x4 + x5 + 2x6 = 7 xj 0 (j = 1 6) Bµi to¸n ®èi ngÉu: -2y2 + 3y3 ≤ -4 (1) 2y1 + 2y2 - 3y3 ≤ 3 (2) -y1 + 5y2 + 5y3 ≤ 0 (3) 4y1 -y3 ≤ -5 (4) -2y1 + 3y2 + y3 ≤ 1 (5) 7y1 + 2y3 ≤ 0 (6)
  77. VÝ dô 2: ViÕt bµi to¸n ®èi ngÉu cña bµi to¸n sau: f(x)= 5x2 + 4x3 - 2x4 + x5 max - 2x1 - 3x2 - x3 + 6x4 - 2x5 = -14 - x1 + 2x2 + 5x3 + 3x5 = 8 6x1 - 3x2 + 2x3 - x4 + x5 = 12 xj 0 (j = 1  5) Bµi to¸n ®èi ngÉu: - 2y1 - y2 + 6y3 0 (1) - 3y1 + 2 y2 - 3y3 5 (2) - y1 + 5 y2 + 2y3 4 (3) 6y1 - y3 -2 (4) - 2y1 + 3 y2 + y3 1 (5)
  78. Chó ý: §èi víi bµi to¸n bÊt kú th× ®­avÒ bµi to¸n d¹ng chÝnh t¾c, x©y dùng bµi to¸n ®èi ngÉu cña bµi to¸n nµy vµ gäi nã lµ bµi to¸n ®èi ngÉu cña bµi to¸n ®· cho.
  79. b. CÆp bµi to¸n ®èi ngÉu ®èi xøng- XÐt bµi to¸n sau gäi lµ bµi to¸n (II) §­abµi to¸n (II) vÒ d¹ng chÝnh t¾c, ký hiÖu lµ (II’) Bµi to¸n ®èi ngÉu cña (II’) vµ còng lµ ®èi ngÉu cña (II) ký hiÖu cã d¹ng:
  80. Hai bµi to¸n (II) vµ cã n+m cÆp rµng buéc ®èi ngÉu sau:
  81. VÝ dô 3: ViÕt bµi to¸n ®èi ngÉu cña bµi to¸n sau: f(x)= -5x2 + 4x3 min - x1 - 3x2 - x3 -14 - 2x1 + 5x2 + 5x3 8 6x1 - 3x2 + 2x3 12 xj 0 (j = 1  3)
  82. c. Cặp bài toán đối ngẫu tổng quát: Ta cã thÓ sö dông c¸c q.t¾c nªu trong l­îc ®å tæng qu¸t d­íi ®©y ®Ó viÕt trùc tiÕp bµi to¸n ®èi ngÉu mµ kh«ng cÇn ®­abµi to¸n vÒ d¹ng chÝnh t¾c.
  83. Lược Đồ Tổng Quát Bài toán gốc Bài toán đối ngẫu yi kh«ng cã rµng buéc dÊu i I1 xj kh«ng cã rµng buéc dÊu j J1
  84. NhËn xÐt: + NÕu mét biÕn sè kh«ng cã rµng buéc dÊu trong bµi to¸n nµy th× rµng buéc t­¬ng øng trong bµi to¸n kia cã dÊu b»ng vµ ng­îc l¹i. + NÕu mét biÕn sè cã rµng buéc dÊu trong bµi to¸n nµy th× rµng buéc t­¬ng øng trong bµi to¸n kia cã dÊu bÊt ®¼ng thøc vµ ng­îc l¹i. + ChiÒu cña c¸c dÊu bÊt ®¼ng thøc cña bµi to¸n ®èi ngÉu ®­îc quyÕt ®Þnh bëi hµm môc tiªu ph¶i ®¹t cùc ®¹i hay cùc tiÓu. + Nếu max và biến số yi có ràng buộc dấu thì yi và ràng buộc tương ứng cùng chiều “bất đẳng thức”.
  85. VÝ dô 4 : ViÕt bµi to¸n ®èi ngÉu cña bµi to¸n sau vµ chØ râ c¸c cÆp rµng buéc ®èi ngÉu: f(x) = -4x1 + x2 +5x3 +3x5 min 3x1 -6 x2 - x3 +2x4 +4x5 ≥ -15 (1) -2x1 +3 x2 +4x3 -5x4 +x5 ≤ 8 (2) -6 x2 +3x3 +8x4 -4x5 = 9 (3) 3x1 +2 x2 -3x4 +x5 ≥ 24 (4) x1 0 , x3 ≤ 0 , x5 0
  86. VÝ dô 5 : ViÕt bµi to¸n ®èi ngÉu cña bµi to¸n sau vµ chØ râ c¸c cÆp rµng buéc ®èi ngÉu: f(x) = -2x1 + x2 +8x4 max 3x1 -6 x2 - x3 +2x4 = -5 (1) x1 +5 x2 -5x4 3 (2) -3 x2 +3x3 +8x4 = 2 (3) 3x1 +2 x2 -3x4 ≥ 24 (4) x2 ≤ 0 , x3 ≤ 0 , x4 0
  87. 2- C¸c tÝnh chÊt vµ ®Þnh lý ®èi ngÉu XÐt cÆp bµi to¸n ®èi ngÉu tæng qu¸t víi hµm môc tiªu f(x) min (max) vµ max(min). TÝnh chÊt 1: Víi mäi cÆp ph­¬ng ¸n x vµ y cña hai bµi to¸n ®èi ngÉu ta lu«n cã: f(x) ≥ ( ) TÝnh chÊt 2: NÕu ®èi víi hai ph­¬ng ¸n x* vµ y* cña 1 cÆp bµi to¸n ®èi ngÉu mµ: th× x* vµ y* t­¬ng øng lµ 2 PAT¦.
  88. §Þnh lý 1(§èi ngÉu): NÕu mét trong hai bµi to¸n ®èi ngÉu gi¶i ®­îc th× bµi to¸n kia còng gi¶i ®­îc vµ khi ®ã mäi cÆp PAT¦ x* vµ y* ta lu«n cã: HÖ qu¶ 1: §iÒu kiÖn cÇn vµ ®ñ ®Ó hai bµi to¸n ®èi ngÉu gi¶i ®­îc lµ mçi bµi to¸n ph¶i cã Ýt nhÊt mét PA. HÖ qu¶ 2: §iÒu kiÖn cÇn vµ ®ñ ®Ó mét bµi to¸n cã PA cßn mét bµi to¸n kh«ng cã ph­¬ng ¸n lµ trÞ sè hµm môc tiªu cña bµi to¸n cã ph­¬ng ¸n kh«ng bÞ chÆn trªn tËp ph­¬ng ¸n cña nã.
  89. VD: Cho bµi to¸n: f(x) = x1 + 8x2 + 10x3 min x1 + x2 + 4x3 = 2 (1) x1 - x2 + 2x3 = 0 (2) (xj 0, j = 1 3) Kh«ng gi¶i h·y chøng minh bµi to¸n cã pacb t­.
  90. Chó ý: Từ t/c2 và đlý 1 ta suy ra điÒu kiÖn cÇn vµ ®ñ ®Ó hai PA x vµ y cña mét cÆp BT§N tèi ­u lµ §Þnh lý 2 (®èi ngÉu): §iÒu kiÖn cÇn vµ ®ñ ®Ó hai PA x vµ y cña mét cÆp BT§N tèi ­u lµtrong c¸c cÆp rµng buéc ®èi ngÉu nÕu mét rµng buéc tho¶ m·n láng th× rµng buéc kia ph¶i tho¶ m·n chÆt. HÖ qu¶: NÕu mét rµng buéc lµ láng ®èi víi mét PAT¦ cña bµi to¸n nµy th× rµng buéc ®èi ngÉu cña nã ph¶i lµ chÆt ®èi víi mäi PAT¦ cña bµi to¸n kia.
  91. 3- øng dông: a) Ph©n tÝch tÝnh chÊt tèi ­ucña mét PA: XÐt xem 1 PA xo cña bto¸n gèc cã ph¶i PAT¦ hay kh«ng: Gi¶ sö xo lµ PAT¦, theo ®Þnh lý 2 ®èi ngÉu, mäi PAT¦ y cña BT§N ph¶i tho¶ m·n chÆt c¸c rµng buéc ®èi ngÉu víi c¸c rµng buéc mµ xo tho¶ m·n láng. TËp hîp c¸c rµng buéc nµy t¹o thµnh hÖ p.tr×nh ®èi víi y. Gi¶i hpt nµy  NÕu hÖ VN th× xo kh«ng ph¶i lµ PAT¦.  NÕu hÖ cã nghiÖm th× ph¶i thö nghiÖm ®ã vµo c¸c rµng buéc cßn l¹i cña BT§N. - NÕu mäi nghiÖm ®Òu kh«ng tho¶ m·n th× xo kh«ng ph¶i PAT¦. - NÕu cã 1 nghiÖm yo tho¶ m·n th× xo lµ PAT¦, ®ång thêi yo còng lµ PAT¦ cña BT§N.
  92. b) X¸c ®Þnh tËp PAT¦: - NÕu xo lµ PAT¦ cña bµi to¸n gèc, theo c¸ch ph©n tÝch trªn ta x¸c ®Þnh ®­îc tËp PAT¦ cña BT§N. - Tõ 1 PAT¦ nµo ®ã cña BT§N ta x¸c ®Þnh ®­îc tËp PAT¦ cña bµi to¸n gèc.
  93. VD: Cho bµi to¸n: f(x) = 3x1 + 9x2 - 2x3 + x4 - 4x5 min -x1 + 5x2 - 3x3 + x4 - 2x5 = - 6 (1) 3x1 - 4x2 +2x3 - x4 + x5 = 4 (2) 4x1 - x3 +2x4 - 3x5 2 (3) (xj 0, j = 1 5) vµ vÐc t¬ xo = (2, 0, 0, 8, 6) a) ViÕt bµi to¸n ®èi ngÉu. b) Ph©n tÝch c¸c tÝnh chÊt cña xo ®èi víi bµi to¸n ®· cho. c) X¸c ®Þnh tËp ph­¬ng ¸n tèi ­uv à c¸c PACB tèi ­ucña hai bµi to¸n. Giải:
  94. a) Bµi to¸n ®èi ngÉu: - y1 + 3y2 + 4y3 3 (1’) 5y1 - 4y2 9 (2’) - 3y1 + 2 y2 - y3 -2 (3’) y1 - y2 + 2y3 1 (4’) - 2y1 + y2 - 3y3 - 4 (5’) y3 0
  95. b) - Vtơ xo = (2, 0, 0, 8, 6) thoả mãn mọi ràng buộc của bài toán nên nó là PA. PA xo thoả mãn chặt rb (1), (2) và 2 rb dấu nên xo không là PACB. - Giả sử xo là PATƯ, theo định lý 2 (đối ngẫu), mọi PATƯ y của bài toán đối ngẫu phải t/m: - Hệ pt trên có nghiệm duy nhất yo = (3, 2, 0). Thử yo vào các rb còn lại của BTĐN đều t/m. - Vậy yo là PATƯ của BTĐN. Do đó xo, yo là 2 PATƯ.
  96. Chương II: Phương Pháp Bảng Cân Đối Liên Ngành I. Mô hình bảng cân đối liên ngành: 1. Dạng hiện vật: Khi nghiên cứu quá trình tái sản xuất xã hội, phương pháp bảng cân đối liên ngành xem toàn bộ nền KTQD là một thể thống nhất bao gồm n ngành sản xuất vật chất “ thuần tuý” khác nhau. Giữa các ngành có mối quan hệ qua lại mật thiết thông qua một mô hình toán học phản ánh các mặt của quá trình tái sản xuất.
  97. Gọi Qi là tổng sản lượng của ngành i trong năm (i = 1n). - Một phần phân phối cho các ngành khác dưới dạng nguyên, nhiên vật liệu, tư liệu sản xuất trong năm, ký hiệu qij (i, j=1n) Qi qij 0 - Phần còn lại là “ sản phẩm cuối cùng” của ngành i, ký hiệu qi (i = 1n) dùng để tích luỹ, tiêu dùng cho năm sau (qi 0). Ta có các phương trình phân phối sản phẩm dạng hiện vật:
  98. Gọi: Qo là tổng đơn vị lao động sống của toàn bộ nền kinh tế quốc dân sử dụng trong năm. qoj là tổng số đơn vị lao động sử dụng ở ngành j qo là tổng số đơn vị lao động sử dụng trong các ngành phi sản xuất. Ta có: Qo > 0, qoj > 0, qo > 0 Phương trình phân phối lao động dạng hiện vật là:
  99. Ghép (1) và (2) được bảng cân đối liên ngành dạng hiện vật. Ngành Tổng Đơn vị Phân phối sử dụng ở SP sx SL tính các ngành cuối 1 2 . . . n cùng q q . . . q q 1 Q1 KW/h 11 12 1n 1 T q q . . . q q 2 Q2 1000 21 22 2n 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 q q . . . q q n Qn 1000m n1 n2 nn n Lao Ngày Q q01 q02 . . . q0n q0 động 0 (người)
  100. 2. Dạng giá trị: Gọi: pi: giá trị một đơn vị sản phẩm ngành i (tính theo đơn vị quy ước). p0: giá trị một đơn vị lao động xã hội. Ta có:
  101. - Tổng giá trị sản lượng trong năm của ngành i là: Xi = piQi (i = 1 n) - Giá trị phần sản phẩm của ngành i cung cấp cho ngành j là Xij = pi.qij (i, j = 1 n) - Giá trị sản phẩm cuối cùng của ngành i là: xi = pi.qi (i = 1 n) - Tổng giá trị lao động sống của toàn xã hội là: X0 = p0.Q0 - Giá trị khối lượng lao động sử dụng trong ngành sản xuất thứ j là: X0j = q0j.p0 - Giá trị của lao động xã hội của các ngành phi sản xuất vật chất là: x0 = p0.q0
  102. Ta có các phương trình: (3) là các phương trình phân phối sản phẩm dạng giá trị. (4) là phương trình phân phối lao động dạng giá trị. Sau mỗi năm, mỗi ngành sản xuất vật chất đều sáng tạo thêm một phần giá trị mới cho xã hội (gọi là giá trị đóng góp cho xã hội, kí hiệu mj). Ta có bảng cân đối liên ngành dạng giá trị:
  103. Sản Ngành Gtrị Tổng Phân phối sử dụng các ngành phẩm SX sản lượng 1 2 . . . n Cuối cùng 1 X1 X11 X12 . . . X1n x1 2 X2 X21 X22 . . . X2n x2 . . . . . . . . . n Xn Xn1 Xn2 . . . Xnn xn Lao X X X . . . X x0 động 0 01 02 0n Giá trị đóng góp Năm m1 m2 . . . mn cho xã hội
  104. II. Các hệ số chi phí trực tiếp và toàn bộ: Ta có: Đặt: aij: gọi là hệ số chi phí trực tiếp dạng giá trị Khi đó ta có: hay
  105. Gäi: E: ma trận đơn vị cấp n A=[aij]nxn là ma trận hệ số chi phí trực tiếp X và x là các ma trận cột có các thành phần là Xi và xi (*) x = X – AX = (E-A)X X = (E-A)-1.x Đặt: (E-A)-1 = B X = Bx B = [bij]nxn được gọi là ma trận hệ số chi phí toàn bộ.
  106. III. Ứng dụng lập kế hoạch năm sau (dạng A): Một tình huống có thể xảy ra trong công tác kế hoạch là người ta dự kiến trước những sản phẩm cuối cùng của năm kế hoạch (chính là năm sau, t+1). Từ mức xi(t) (t: năm trước), phát triển, mở rộng đến mức xi(t+1) năm dự kiến kế hoạch (xi(t+1)>xi(t)) Việc xây dựng dự án kế hoạch trong tình huống này gọi là lập kế hoạch cân đối dạng A.
  107. Để lập dự án kế hoạch dạng A cho năm t +1 ta làm như sau: B1: Tìm A(t+1) Từ ước thực hiện kế hoạch năm t ta tính aij(t) = Xij(t)/Xj(t) suy ra aij(t+1) và A(t+1). B2: Tìm B(t+1) Tính E – A(t+1) tính [E – A(t+1)] -1 = B(t+1) B3: Tìm X(t+1) = B(t+1).x(t+1) sẽ tính được các Xj(t+1) B4: Tìm Xij(t+1) Xij(t+1) = aij(t+1).Xj(t+1) B5: Tìm Xoj(t+1) + Tính a0j(t) = X0j(t)/Xj(t) rồi suy ra a0j(t+1) + Tính Xoj(t+1) = aoj(t+1).Xj(t+1) + Tính
  108. VD1: Cho a) Ước thực hiện kế hoạch năm t là: Ngành Xi Xij xi 1 80 16 32 32 2 100 15 40 45 X0 10 20 Năm t mj 39 8 b) aij(t+1) aij(t); a0j(t+1) a0j(t); c) x1(t+1) = 40; x2(t+1) = 60 Hãy tìm dự án kế hoạch năm t+1 cân đối dạng A
  109. Giải: B1: Tìm A(t+1): Tìm aij(t) = Xij(t)/Xj(t) a11 (t) = X11/X1 = 16/80 = 0,2 a12 (t) = X12/X2 = 32/100 = 0,32 a21 (t) = X21/X1 = 15/80 = 0,1875 a22 (t) = X22/X2 = 40/100 = 0,4 A(t+1) A(t) =
  110. B2: Tìm B(t+1) [E – A(t+1)] = C= [C]-1 = B(t+1) = B3: Tìm X(t+1) = B(t+1).x(t+1)
  111. B4: Tìm Xij(t+1) = aij(t+1).Xj(t+1) X11(t+1) = a11(t+1).X1(t+1) = 0,2 x 102,858 = 20,5716 X12(t+1) = a12(t+1).X2(t+1) = 0,32 x 132,144 = 42,2861 X21(t+1) = a21(t+1).X1(t+1) = 0,1875 x 102,858 = 19,2859 X22(t+1) = a22(t+1).X2(t+1) = 0,4 x 132,144 = 52,8576
  112. B5: Tìm X0j(t+1) a01(t) = X01/X1 = 10/80 = 0,125 a02(t) = X02/X2 = 20/100 = 0,2 a01(t+1) a01(t) ; a02(t+1) a02(t) X0j(t+1) = a0j(t+1). Xj(t+1) X01(t+1) = a01(t+1). X1(t+1) = 0,125 x 102,858 = 12,8573 X02(t+1) = a02(t+1). X2(t+1) = 0,2 x 132,144 = 26,4288
  113. Bảng cân đối liên ngành dạng giá trị năm t+1 Ngành Xi Xij xi 1 102.858 20,5716 42,2861 40 2 132,144 19,2859 52,8576 60 X0 12,8573 26,4288 Năm t+1 mj 50,1432 10,5715 m1 = X1 – (X11+X21) – X01 = 102,858 – 20,5716 - 19,2859- 12,8573 = 50,1432 m2 = X2 – (X12+X22) – X02 = 132,144 – 42,2861 - 52,8576 - 26,4288 = 10,5715
  114. VD 2: Cho biết a) Ước thực hiện kế hoạch năm t thể hiện ở bảng cân đối liên ngành dạng giá trị sau: (Đơn vị tính: 1000 triệu đồng) Ngành Xi Xij xi 1 397,8 159,7 40,1 87,8 110,2 2 197,9 16,5 118,9 3 300,5 80,1 38,7 151,3 X0 73,7 39,6 Năm t mj 58,6 130,2 b) aij(t+1) aij(t); a0j(t+1) a0j(t); (i,j = 1, 2, 3) c) x(t+1) = (500, 300, 400) Hãy hoàn thiện bảng và lập dự án kế hoạch năm t+1 cân đối dạng A
  115. Hãy hoàn thiện bảng và lập dự án kế hoạch năm t+1 cân đối dạng A Giải: Hoàn thiện bảng
  116. Ngành Xi Xij xi 1 397,8 159,7 40,1 87,8 110,2 2 197,9 16,5 118,9 3 300,5 80,1 38,7 151,3 X0 73,7 39,6 Năm t mj 58,6 130,2
  117. B1: Tìm A(t+1): aij(t) = Xij(t)/Xj(t) a11 = X11/X1 = 159,7/397,8 a12 = X12/X2 = 40,1/197,9 a13 = X13/X3 = 87,8/300,5 a21 = X21/X1 = 41,6/397,8 a22 = X22/X2 = 20,9/197,9 a23 = X23/X3 = 16,5/300,5 a31 = X31/X1 = 80,1/397,8 a32 = X32/X2 = 38,7/197,9 a33 = X33/X3 = 30,4/300,5
  118. A(t+1) A(t)= B2: Tìm B(t+1) [E – A(t+1)] = C = C = 0,5985.0,8944.0,8988+(-0,2026).(-0,0549).(-0,2014)+ +(-0,1046)(-0,1956)(-0,2922)-(-0,2014).0,8944.(-0,2922) -(-0,1046).(-0,2026).0,8988-(-0,1956).(-0,0549).0,5985 = 0,3948
  119. = 0,7931 = 0,1051 = 0,2006 = 0,2393 = 0,4791
  120. = 0,1579 = 0,2725 = 0,0634 = 0,5141
  121. C11 = 0,7931; C21 = 0,2393 ; C31 = 0,2725 C12 = 0,1051; C22 = 0,4791 ; C32 = 0,0634 C13 = 0,2006; C23 = 0,1579 ; C33 = 0,5141 C -1 =B(t+1) =
  122. B3: X(t+1) = B(t+1). x(t+1)
  123. B4: Tìm Xij(t+1) 587,1375 X11(t+1) = 0,4015 x 1462,36 = X12(t+1) = 0,2026 x 561,39 = 113,7376 X13(t+1) = 0,2922 x 894,9 = 261,4898 X21(t+1) = 0,1046 x 1462,36 = 152,9629 X22(t+1) = 0,1056 x 561,39 = 59,2828 X23(t+1) = 0,0549 x 894,9 = 49,13 X31(t+1) = 0,2014 x 1462,36 = 294,5193 X32(t+1) = 0,1956 x 561,39 = 109,8079 X33(t+1) = 0,1012 x 894,9 = 90,5639
  124. B5: Tìm X0j(t+1) a01(t+1) a01(t) =X01/X1= 73,7/397,8 = 0,1853 a02(t+1) a02(t) =X02/X2= 39,6/197,9 = 0,2001 a03(t+1) a03(t) =X03/X3= 35,6/300,5 = 0,1185 X01(t+1) = a01(t+1). X1(t+1) = 0,1853 x 1462,36 = 270,9753 X02(t+1) = a02(t+1). X2(t+1) = 0,2001 x 561,39 = 112,3341 X03(t+1) = a03(t+1). X3(t+1) = 0,1185 x 894,9 = 106,0457
  125. Ngành Xi Xij xi 1 1462,36 587,1375 113,7376 261,4898 500 2 561,39 152,9629 59,2828 49,13 300 3 894,9 294,5193 109,8079 90,5639 400 X0 270,9753 112,3341 106,0457 Năm t+1 mj 156,765 166,2276 387,6706 m1 = X1 – (X11+X21+X31) – X01 = 1462,36 - 587,1375 - 152,9629 - 294,5193 - 270,9753 = 156,765 m2 = 166,2276 m3 = 387,6706
  126. Bài 1: Cho biết a) Ước thực hiện kế hoạch năm t thể hiện ở bảng cân đối liên ngành dạng giá trị sau: (Đơn vị tính: 1000 triệu đồng) Ngành Xi Xij xi 1 350,18 268,47 300,89 100,81 2 750,15 210,5 148,34 130,96 3 890,2 215,51 210,1 74,14 X0 50,37 75,63 Năm t mj 18,85 26,25 43,23 b) aij(t+1) aij(t); a0j(t+1) a0j(t); (i,j = 1, 2, 3) c) x(t+1) = (120, 150, 100) Hãy lập dự án kế hoạch năm t+1 cân đối dạng A
  127. Ngành Xi Xij xi 1 1020,35 350,18 268,47 300,89 100,81 2 750,15 210,5 148,34 260,35 130,96 3 890,2 390,45 215,51 210,1 74,14 X0 50,37 91,58 75,63 Năm t mj 18,85 26,25 43,23
  128. B1: Tìm A(t+1): a11 = 350,18 / 1020,35 a12 = 268,47 / 750,15 a13 = 300,89 / 890,2 a21 = 210,5 / 1020,35 a22 = 148,34 / 750,15 a23 = 260,35 / 890,2 a31 = 390,45 / 1020,35 a32 = 215,51 / 750,15 a33 = 210,1 / 890,2
  129. A(t+1) A(t)= B2: Tìm B(t+1) [E – A(t+1)] = C = C = 0,6568.0,8023.0,764 + (-0,3579).(-0,2925).(-0,3827) + + (-0,2063)(-0,2873)(-0,338) - (-0,3827).0,8023.(-0,338) - (-0,2063).(-0,3579).0,764 - (-0,2873).(-0,2925).0,6568 = 0,1271
  130. = 0,5289 = 0,2696 = 0,3663 = 0,3705 = 0,3724
  131. = 0,3257 = 0,3759 = 0,2618 = 0,4531
  132. B(t+1) = C-1 =
  133. B3: X(t+1) = B(t+1). x(t+1)
  134. B4: Tìm Xij(t+1) = aij(t+1).Xj(t+1) 422,9446 X11(t+1) = 0,3432 x 1232,356 = X12(t+1) = 0,3579 x 900,024 = 322,1186 X13(t+1) = 0,338 x 1086,705 = 367,3063 X21(t+1) = 0,2063 x 1232,356 = 254,235 X22(t+1) = 0,1977 x 900,024 = 177,9347 X23(t+1) = 0,2925 x 1086,705 = 317,8612 X31(t+1) = 0,3827 x 1232,356 = 471,6226 X32(t+1) = 0,2873 x 900,024 = 258,5769 X33(t+1) = 0,236 x 1086,705 = 256,4624
  135. B5: Tìm X0j(t+1) a01(t+1) a01(t) = 50,37/1020,35 = 0,0494 a02(t+1) a02(t) = 91,58/750,15 = 0,1221 a03(t+1) a03(t) = 75,63/890,2 = 0,085 X01(t+1) = 0,0494 x 1232,356 = 60,8784 X02(t+1) = 0,1221 x 900,024 = 109,8929 X03(t+1) = 0,085 x 1086,705 = 92,3699 Bảng CĐLN năm t+1
  136. Ngành Xi Xij xi 1 1232,356 422,9446 322,1186 367,3063 120 2 900,024 254,235 177,9347 317,8612 150 3 1086,705 471,6226 258,5769 256,4624 100 X0 60,8784 109,8929 92,3699 Năm t+1 mj 22,6754 31,5009 52,7052 m1 = 22,6754 m2 = 31,5009 m3 = 52,7052
  137. Bài 2: Cho biết a) Ước thực hiện kế hoạch năm t thể hiện ở bảng cân đối liên ngành dạng giá trị sau: (Đơn vị tính: 1000 triệu đồng) Ngành Xi Xij xi 1 648,36 150,24 246,54 203,12 48,46 2 820,57 230,17 193,82 293,18 103,4 3 973,15 206,03 346,19 297,84 123,09 X0 40,26 21,07 113,21 Năm t mj 21,66 12,95 65,8 b) aij(t+1) aij(t); a0j(t+1) a0j(t); (i,j = 1, 2, 3) c) x(t+1) = (96,14; 165,37; 195,85) Hãy lập dự án kế hoạch năm t+1 cân đối dạng A
  138. B1: Tìm A(t+1): a11 = 150,24/648,36 a12 = 246,54/820,57 a13 = 203,12/973,15 a21 = 230,17 /648,36 a22 = 193,82 /820,57 a23 = 293,18 /973,15 a31 = 206,03 /648,36 a32 = 346,19 /820,57 a33 = 297,84 /973,15
  139. A(t+1) A(t)= B2: Tìm B(t+1) [E – A(t+1)] = C = C = 0,1249
  140. = 0,4029 = 0,3421 = 0,3925 = 0,2965 = 0,4668
  141. = 0,4196 = 0,2499 = 0,3056 = 0,4802
  142. B(t+1) = C-1 =
  143. B3: X(t+1) = B(t+1). x(t+1)
  144. B4: Tìm Xij(t+1) = aij(t+1).Xj(t+1) 253,6088 X11(t+1) = 0,2317 x 1094,5569 = X12(t+1) = 0,3004 x 1360,5871 = 408,7204 X13(t+1) = 0,2087 x 1610,665 = 336,1458 X21(t+1) = 0,355 x 1094,5569 = 388,5677 X22(t+1) = 0,2362 x 1360,5871 = 321,3707 X23(t+1) = 0,3013 x 1610,665 = 485,2934 X31(t+1) = 0,3178 x 1094,5569 = 347,8502 X32(t+1) = 0,4219 x 1360,5871 = 574,0317 X33(t+1) = 0,3061 x 1610,665 = 493,0246
  145. B5: Tìm X0j(t+1) a01(t+1) a01(t) = 40,26/648,36 = 0,0621 a02(t+1) a02(t) = 21,07/820,57 = 0,0257 a03(t+1) a03(t) = 113,21/973,15 = 0,1163 X01(t+1) = 0,0621 x 1094,5569 = 67,972 X02(t+1) = 0,0257 x 1360,5871 = 34,9671 X03(t+1) = 0,1163 x 1610,665 = 187,3203 Bảng CĐLN năm t+1
  146. Ng Xi Xij xi 1 1094,5569 253,6088 408,7204 336,1458 96,14 2 1360,5871 388,5677 321,3707 485,2934 165,37 3 1610,665 347,8502 574,0317 493,0246 195,85 X0 67,972 34,9671 187,3203 Năm 36,5582 21,4972 108,8809 t+1 mj m1 = 36,5582 m2 = 21,4972 m3 = 108,8809
  147. c c c c c c c Hệ Cơ Phương 1 2 r m m+1 s n số sở án x1 x2 xr xm xm+1 xs xn x1 0 c1 x 1 1 0 0 0 x1,m+1 x1s x1n c2 x2 x01 0 1 0 0 x2,m+1 x2s x2n cr xr x0r 0 0 1 0 xr,m+1 [xrs] xrn c x x0m 0 0 0 1 xm,m+1 xms xmn m m 0 f(x) f(x ) 0 0 0 0 m+1 s n