bài giảng toán kinh tế
Slide bai giảng môn thanh toán quốc tế – Hối đoái – ThS Vũ Thị Lê Giang – ĐH Kinh Tế (2.81 MB) Slide bài giảng môn Tài chính quốc tế (11.55 MB) Slide bài giảng môn quản trị doanh nghiệp GV Trần Ngọc Tiến Học Viện Ngân Hàng (106.13 KB)
Toán kinh tế đối với nhà quản lý vô cùng quan trọng, thông qua những phần tích của toán kinh tế về thị trường mà họ sẽ có những quyết định về sản xuất cho doanh nghiệp. Toán kinh tế còn là một chuyên ngành của kinh tế học, chuyên nghiên cứu và áp dụng toán vào
Bài giảng Toán cao cấp cho các nhà kinh tế 2 - Bài 4: Hàm số nhiều biến - Bùi Quốc Hoàn 1.3. MỘT SỐ HÀM TRONG PHÂN TÍCH KINH TẾ a) Hàm sản xuất • Hàm sản xuất là hàm số biểu diễn sự phụ thuộc của mức sản lượng tiềm năng (Q) của một doanh nghiệp vào mức sử dụng
Freie Presse Partnersuche Er Sucht Sie. Dưới đây là tổng hợp các file tài liệu môn toán kinh tế MI3131 mà mình sưu tầm được dành cho chương trình chuẩn, các bạn chương trình vip cũng có thể tham khảo nhé. Các bạn nhấn vào nút để tải file về nhé, File trên Scribd chỉ là để xem trước Giáo trình toán kinh tế2. Slides bài giảng3. Tổng hợp một số đề thi toán kinh tế4. File bài tập toán kinh tế có đáp án5. Record môn học6. Kênh youtube hay nên xem1. Tổng hợp bài giảng của thầy Hà Chí Công2. Tổng hợp bài giảng về Quy hoạch tuyến tính, BTVT, BTĐN của cô GiangHiện nay trường chưa có giáo trình chính thức nên dưới đây là một số giáo trình để chúng ta tham các phương pháp tối ưu Lý thuyết và thuật toán này được giáo viên khuyến khích tìm hiểu và học bộ môn này Slides bài giảngCác bạn xem toàn bộ bài giảng trong thư mục Tổng hợp một số đề thi toán kinh tế 4. File bài tập toán kinh tế có đáp ánCác bạn xem toàn bộ file trong thư mục nhé5. Record môn học6. Kênh youtube hay nên xem1. Tổng hợp bài giảng của thầy Hà Chí Công2. Tổng hợp bài giảng về Quy hoạch tuyến tính, BTVT, BTĐN của cô GiangTài liệu môn Pháp luật đại cương
Nội dung Text Bài giảng Toán kinh tế - Nguyễn Hải Đăng Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH. PHƯƠNG PHÁP ĐƠN HÌNH Bài toán quy hoạch tuyến tính Một số mô hình thực tế A. Bài toán lập kế hoạch sản xuất Một cơ sở có thể sản xuất hai loại sản phẩm A và B, từ các nguyên liệu I, II, III. Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản phẩm, cũng như dự trữ nguyên liệu cho trong bảng sau đây Nguyên liệu I II III Lãi Sản phẩm A 2 0 1 3 B 1 1 0 5 Dự trữ 8 4 3 Hãy lập bài toán thể hiện kế hoạch sản xuất sao cho có tổng số lãi lớn nhất, trên cơ sở dự trữ nguyên liệu đã có. Lập bài toán Gọi x, y lần lượt là số sản phẩm A và B được sản xuất x, y ≥ 0 , đơn vị sản phẩm. Khi đó ta cần tìm x, y ≥ 0 sao cho đạt lãi lớn nhất. f X = 3 x + 5 y → max với điều kiện nguyên liệu 2 x + y ≤ 8; 1. y ≤ 4; ≤ 3; Tức là cần giải bài toán f X = 3 x + 5 y → max ⎧2 x + y = 8; ⎪ y ≤ 4; ⎪ với điều kiện ⎨ ⎪ x ≤ 3; ⎪⎩ x, y ≥ 0; -1- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định B. Bài toán phân công lao động Một lớp học cần tổ chức lao động với hai loại công việc xúc đất và chuyển đất. Lao động của lớp được chia làm 3 loại A, B, C, với số lượng lần lượt là 10, 20, 12. Năng suất của từng loại lao động trên từng công việc cho trong bảng dưới đây Lao động A10 B20 C12 Công việc Xúc đất 6 5 4 Chuyển đất 4 3 2 Hãy tổ chức lao động sao cho có tổng năng suất lớn nhất. Lập bài toán Gọi xij là số lao động loại j làm công việc ij=1,2;xij ≥ 0 , nguyên. Khi đó, năng suất lao động của công việc đào đất sẽ là 6 x11 + 5 x12 + 4 x13 ; còn chuyển đất sẽ là 4 x 21 + 3 x 22 + 2 x 23 ; Ta thấy rằng để có năng suất lớn nhất thì không thể có lao động dư thừa, tức là phải cân bằng giữa hai công việc. Vì vậy ta có bài toán sau 6 x11 + 5 x12 + 4 x13 → max; ⎧6 x11 + 5 x12 + 4 x13 − 4 x21 + 3 x22 + 2 x23 = 0; ⎪ x + x = 10; ⎪ 11 21 với điều kiện ⎨ ⎪ x12 + x22 = 20; ⎪⎩ x13 + x23 = 12; C. Bài toán khẩu phần thức ăn Một khẩu phần thức ăn có khối lượng P, có thể cấu tạo từ n loại thức ăn. Gía mua một đơn vị thức ăn loại j là cj. Để đảm bảo cơ thể phát triển bình thường thì khẩu phần cần m loại chất dinh dưỡng. Chất dinh dưỡng thứ i cần tối thiểu cho khẩu phần là bi và có trong một đơn vị thức ăn loại j là aij. Hỏi nên cấu tạo một khẩu phần thức ăn như thế nào để ăn đủ no, đủ chất dinh dưỡng mà có giá thành rẻ nhất. Lập bài toán Gọi xj xj ≥ 0 là số đơn vị thức ăn loại j được cấu tạo trong khẩu phần. Khi đó, giá thành của khẩu phần là -2- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định n f X = ∑cjxj; j =1 Vì phải đảm bảo thoả mãn điều kiện đủ no và đủ chất, tức là n n ∑x j =1 j =P, ∑ aij x j ≥ b j , i = 1, m. j =1 n Ta có bài toán sau f X = ∑ c j x j → min j =1 ⎧ n x = P; ⎪∑ j =1 j ⎪ n ⎪ với điều kiện ⎨ ∑ a ij x j ≥ b i , i = 1, m ; ⎪ j =1 ⎪ x j ≥ 0 , j = 1, n ; ⎪⎩ Ta thấy rằng ba bài toán trên đều thuộc bài toán tổng quát. Bài toán quy hoạch tuyến tính tổng quát Bài toán tổng quát của QHTT có dạng n f X = ∑ c j x j → min max j =1 ⎧ n a x = b , i = 1, k ⎪∑ j =1 ij j i ⎪ n ⎪ với điều kiện ⎨ ∑ a ij x j ≥ bi , i = k + 1, m ⎪ j =1 ⎪ x j ≥ 0, j = 1, r , r ≤ n ⎪⎩ Để phân biệt tính chất của các ràng buộc đối với một phương án, ta làm quen với hai khái niệm ràng buộc chặt và ràng buộc lỏng. Định nghĩa 1 Nếu đối với phương án x mà ràng buộc i thỏa mãn với dấu đẳng n thức, nghĩa là ∑a x j =1 ij j = bi thì ta nói phương án x thỏa mãn chặt ràng buộc i Nếu đối với phương án x mà ràng buộc i thỏa mãn với dấu bất đẳng thức thực sự, n nghĩa là ∑a x j =1 ij j > bi thì ta nói phương án x thỏa mãn lỏng ràng buộc i Định nghĩa 2 Ta gọi một phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính là phương án cực biên. Một phương án cực biên thỏa mãn chặt đúng n ràng buộc -3- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định gọi là phương án cực biên không suy biến, thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến. Định nghĩa 3 Một phương án mà tại đó hàm mục tiêu đạt cực tiểu cực đại gọi là phương án tối ưu. Bài toán có ít nhất một phương án tối ưu gọi là bài toán giải được, 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 dưới trên trên tập phương án gọi là không giải được. Để nhất quán trong lập luận, ta xét bài toán tìm cực tiểu, sau đó ta xét cách đưa bài toán tìm cực đại về bài toán tìm cực tiểu. * Chuyển bài toán tìm cực đại về bài toán tìm cực tiểu Nếu gặp bài toán tìm max, tức là n f X = ∑ c j x j → max j =1 X ∈M thì giữ nguyên ràng buộc, ta đưa nó về dạng bài toán tìm min n g X = − f X = − ∑ c j x j → min j =1 X ∈M Chứng minh Nếu bài toán tìm min có phương án tối ưu là X* thì bài toán tìm max cũng có phương án tối ưu là X* và gX= - fX. Thật vậy, X* là phương án tối ưu của bài toán tìm min, tức là n n f X = ∑ c j x ≤ ∑ c j x j , ∀X ∈ M * * j j =1 j =1 n n ⇒ − ∑ c j x ≥ ∑ c j x j , ∀X ∈ M * j j =1 j =1 hay − f X * = g X * ≥ g X , ∀X ∈ M Vậy X* là phương án tối ưu của bài toán max và n f max = −∑ c j x*j = −g min j =1 Dạng chính tắc của bài toán quy hoạch tuyến tính -4- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định Người ta thường xét bài toán QHTT dưới dạng sau n f X = ∑ c j x j → min j =1 ⎧ n a x = b , i = 1, m ∑ với điều kiện ⎪⎨ j = 1 ij j i ⎪ x j ≥ 0 , j = 1, n ⎩ Bài toán được gọi là Bài toán Quy hoạch tuyến tính dạng chính tắc. Kí hiệu ma trận hàng c = c1 , c2 ,..., cn 1×n và các ma trận ⎛ x1 ⎞ ⎛ b1 ⎞ ⎛ a1j ⎞ ⎜x ⎟ ⎜b ⎟ ⎜a ⎟ x = ⎜ ⎟ , b = ⎜ ⎟ , A = aij m×n , Aj = ⎜ ⎟ j = 1, n 2 2 2j ⎜ ... ⎟ ⎜ ... ⎟ ⎜ ... ⎟ ⎜ ⎟ ⎜ ⎟ ⎜⎜ ⎟⎟ x ⎝ n⎠ b ⎝ m⎠ ⎝ amj ⎠ Ta có bài toán ở dạng ma trận như sau fx = cx → min ⎧ Ax = b Với điều kiện ⎨ ⎩x ≥ 0 và bài toán ở dạng véc tơ như sau fx = cx → min ⎧ A1 x1 + A2 x2 + .... + An xn = b Với điều kiện ⎨ ⎩ x1 , x2 ,..., xn ≥ 0 Đối với bài toán dạng chính tắc ta có một số tính chất và khái niệm quan trọng của phương án cực biên như sau Tính chất 1 Nhận dạng phương án cực biên Phương án x của bài toán dạng chính tắc là cực biên khi và chỉ khi hệ thống các véc tơ { Aj x j > 0} độc lập tuyến tính. Với giả thiết hạng[A] = m thì một phương án cực biên không suy biến có đúng m thành phần dương, suy biến có ít hơn m thành phần dương. Chứng minh Lấy một phương án x bất kì, giả sử p thành phần đầu của x là dương, tức là x j > 0 j = 1, p , suy ra xk = 0 k = p + 1, n . Thành lập ma trận tương ứng với các ràng -5- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định buộc chặt của phương án x bao gồm m ràng buộc đẳng thức và n - p ràng buộc chặt về dấu , kí hiệu là C, ta có ⎡ a11 a12 ... a1 p a1 p +1 a1 p + 2 ... a1n ⎤ ⎢a a22 ... a2 p a2 p +1 a2 p + 2 ... a2 n ⎥ ⎢ 21 ⎥ m ⎢ ... ... P ... ... ... ... ... ⎥ ⎢ ⎥ ⎢ am1 am 2 ... amp amp +1 amp + 2 ... amn ⎥ C=⎢ 0 0 ... 0 1 0 ... 0 ⎥ ⎢ ⎥ ⎢ 0 0 ... 0 0 1 ... 0 ⎥ ⎢ 0 0 ... 0 0 0 ... 0 ⎥ n-p ⎢ ⎥ ⎢ ... ... ... ... ... ... ... ... ⎥ ⎢ 0 0 ... 0 0 0 ... 1 ⎥⎦ ⎣ Theo cách tính hạng của ma trận thì hạng[C] = n – p + hạng[P] Từ định nghĩa suy ra, x là phương án cực biên khi và chỉ khi hạng[C] = n, nghĩa là khi { } và chỉ khi hạng[P] = p, nói cách khác thì Aj j = 1, p hay { Aj x j > 0} độc lập tuyến tính. Từ đây đối với bài toán dạng chính tắc, không mất tính tổng quát , ta giả thiết • Hệ có đúng m phương trình độc lập tuyến tính. • ∀bi ≥ 0, i = 1, m • m 0} Tính chất 2 Tính hữu hạn của số phương án cực biên Số phương án cực biên của mọi bài toán quy hoạch tuyến tính đều hữu hạn Thật vậy Vì mỗi phương án cực biên đều tương ứng với một hệ n ràng buộc chặt độc lập tuyến tính, số hệ gồm n phương trình độc lập tuyến tính là hữu hạn, do đó số phương án cực biên cũng là hữu hạn. Tính chất 3 Sự tồn tại phương án tối ưu Nếu bài toán dạng chính tắc có phương án và hàm mục tiêu bị chặn dưới trên tập phương án thì bài toán có phương án cực biên tối ưu. Thật vậy, giả sử bài toán có các phương án cực biên là x1 , x 2 ,..., x k . { Đặt f xl = Min f x i i = 1, k . } Do tập nghiệm hay tập phương án của bài toán quy hoạch tuyến tính của hệ ràng buộc là một đa diện lồi, cho nên mọi nghiệm phương án x đều có thể phân tích thành k k x = ∑ λi x , ∑ λi = 1 i i =1 i =1 k k k Suy ra f x = f ∑ λi x = ∑ λi f x ≥ ∑ λi f xl = f xl ∀x ∈ M i i i =1 i =1 i =1 Vậy xl chính là phương án cực biên tối ưu. Một lớp quan trọng của các bài toán quy hoạch tuyến tính dạng chính tắc là bài toán dưới đây gọi là bài toán dạng chuẩn -7- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định n f x = ∑ c j x j → min j =1 ⎧ x1 + a 1m +1 x m +1 + a 1m +2 x m +2 + ... + a 1 n x n = b1 ⎪ x2 + a 2m +1 x m +1 + a 2m +2 x m +2 + ... + a 2 n x n = b 2 ⎪ ⎪ ... ................. ................. ..................... ⎨ ⎪ xm + a mm +1x m+1 + a m m+2 x m+2 + ... + a m n x n = b m ⎪ ⎪⎩ x j ≥ 0 , j = 1, n trong đó bi ≥ 0i = 1, m , nghĩa là bài toán dạng chính tắc có vế phải không âm và mỗi phương trình đều có một biến số với hệ số bằng 1 đồng thời không có trong các phương trình khác gọi là biến cô lập với hệ số bằng 1. Từ hệ phương trình ràng buộc của bài toán dễ dàng suy ra một phương án x 0 = b1 , b2 ,..., bm ,0,0,...,0 Đây chính là một phương án cực biên có hệ cơ sở tương ứng là ⎛1⎞ ⎛0⎞ ⎛0⎞ ⎜0⎟ ⎜1⎟ ⎜0⎟ A1 = ⎜ ⎟ , A2 = ⎜ ⎟ ,..., Am = ⎜ ⎟ ⎜ ... ⎟ ⎜ ... ⎟ ⎜ ... ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝0⎠ ⎝0⎠ ⎝1⎠ Đưa bài toán quy hoạch tuyến tính về dạng chính tắc Phương pháp Ta có thể đưa bài toán tuyến tính tổng quát về bài toán tuyến tính dạng chính tắc tương đương nhờ các quy tắc sau • Nếu có max fX thì đổ thành {min − f X }. n n • Nếu có bất đẳng thức ∑a x j =1 ij j ≥ bi hoặc ∑a x j =1 ij j ≤ bi thì ta đưa thêm ẩn phụ xn+i ≥ 0 ,với hệ số hàm mục tiêu cn+i = 0 để có n n ∑a x j =1 ij j − xn +i = bi hoặc ∑a xj =1 ij j + xn+i = bi ; • Nếu có ẩn xk chưa ràng buộc về dấu, thì ta có thể thay nó bởi hai biến mới xk và xk không âm, theo công thức ' " xk = xk - xk . ' " Ví dụ Đưa bài toán sau về dạng chính tắc min { x1 − x2 − x3 } ; -8- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định ⎧ 6 x11 + 5 x12 + 4 x13 − 4 x 21 + 3 x 22 + 2 x 23 = 0; ⎪ x + x + x = 5; ⎪⎪ 1 2 3 với điều kiện ⎨ x1 − 2 x 2 + x3 ≤ 3; ⎪ x + x − x ≥ 4; ⎪ 1 2 3 ⎪⎩ x1 , x3 ≥ 0; Giải Ta thấy có bất đẳng thức x1 − 2 x2 + x3 ≤ 3 nên ta đưa thêm ẩn phụ x4 , x5 ≥ 0 Mặt khác, có ẩn x2 chưa ràng buộc về dấu, do đó ta thay x2 bởi x2' − x2" . Khi đó, bài toán ban đầu được chuyển về dạng sau x1 − x2' + x2" − x3 → min ⎧ x1 + x 2' − x 2" + x 3 = 5 ⎪ ⎪ x1 − 2 x 2 + 2 x 2 + x 3 + x 4 = 3 ' " với điều kiện ⎨ ⎪ x1 + x 2 − x 2 − x 3 − x 5 = 4 ' " ⎪ x , x ' , x" , x , x , x ≥ 0 ⎩ 1 2 2 3 4 5 Ví dụ Đưa bài toán QHTT sau về dạng chính tắc 2 x1 − x2 + 2 x3 + x4 − 2 x5 → min ⎧ x1 − 2 x2 + x3 + 2 x4 + x5 ≤ 71 ⎪ x + 2 x + x ≥ −12 ⎪ 2 3 4 ⎪⎪2 x3 + x4 + 3 x5 ≥ 103 với điều kiện ⎨ ⎪ x1 + x2 − 2 x3 + x4 = 20 ⎪ x1 , x5 ≥ 0 ⎪ ⎪⎩ x4 ≤ 0 Giải Vì x2, x3 chưa ràng buộc về dấu nên ta thay x2 bởi x2' − x2" x2' , x2" ≥ 0 , x3 bởi x3' − x3" x3' , x3" ≥ 0 , x4 ≤ 0 nên thay x4 bởi − x4' x4' ≥ 0 . Vì có các bất đẳng thức 1, 2, 3 nên ta thêm các ẩn phụ x6, x7, x8. Từ đó, ta được bài toán sau 2 x1 − x2' − x2" + 2 x3' − x3" − x4' − 2 x5 → min -9- Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định ⎧ x1 − 2 x2' − x2" + x3' − x3" − 2 x4' + x5 + x6 = 7 ⎪ ' ⎪ x2 − x2 + 2 x3 − x3 − x4 − x7 = −1 " ' " ' ⎪ Với điều kiện ⎨2 x2' − x2" − x4' + 3 x5 − x8 = 10 ⎪ x + x ' − x" − 2 x ' − x" − x ' = 20 ⎪ 1 2 2 3 3 4 ⎪⎩ x1 , x5 , x6 , x7 , x8 , x2 , x2 , x3 , x3 , x4 ≥ 0 ' " ' " ' Phương pháp đơn hình Tư tưởng của phương pháp đơn hình Xét bài toán quy hoạch tuyến tính dạng chính tắc n f x = ∑ c j x j → min j =1 ⎧ n ⎪∑ aij x j = bi , i = 1, m ⎨ j =1 ⎪x ≥ 0 ⎩ j Dạng véctơ của bài toán f x = cx → min ⎧ n Với điều kiện ⎪∑ Aj x j = b ⎨ j =1 ⎪ x ≥ 0, j = 1, n ⎩ j Ta đã biết rằng - Nếu bài toán có phương án thì có phương án cực biên - Nếu bài toán có phương án tối ưu thì cũng có phương án cực biên tối ưu. Số phương án cực biên là hữu hạn. Do đó, ta có thể tìm một phương án tối ưuhay một lời giải của bài toán trong tập hợp các phương án cực biên. Tập hợp này là hữu hạn. Vì vậy Dantzig đề xuất thuật toán đơn hình như sau Xuất phát từ một phương án cực biên x0. Kiểm tra xem x0 có là phương án tối ưu hay chưa. Nếu x0 chưa phải là phương án tối ưu thì tìm cách cải tiến nó để được phương pháp khác là x1 tốt hơn x0, tức là fx1 0. Ta có j 0 n AX 0 = b hay b = ∑ x 0j Aj = ∑x 0 j Aj 1 j =1 j∈J 0 vì x 0j = 0∀j ∉ J 0 . Với mỗi k ∉ J 0 , ta biểu diễn véc tơ Ak qua các véc tơ cơ sở {A , j ∈ J } j 0 Ak = ∑z j∉J 0 jk A j ∀k ∉ J 0 Gỉa sử x ∈ M là một phương án bất kỳ. Ta có n b = ∑ x j Aj = ∑ x j Aj + ∑ xk Ak = ∑x A +∑x ∑z j j k jk Aj = ∑ x + ∑ z j jk xk Aj 2 j =1 j∈J k∉J j∈J 0 k∉J 0 j∈J 0 j∈J 0 k∉J 0 Vì { Aj , j ∈ J 0 } độc lập tuyến tính nên từ 1 và 2 suy ra x 0j = x j + ∑ z jk xk ∀j ∈ J 0 k∉J Hay x j = x j − ∑ z jk xk ∀j ∈ J 0 0 3 k∉J Khi đó, ta có n f x = ∑ c j x j = ∑c x + ∑c x j j k k 4 j =1 j∈J 0 k∉J 0 Thay 3 vào ta được n n f x = ∑ x − ∑ z jk xk c j + ∑ ck xk = ∑ c j x 0j − ∑ ∑ z jk c j − ck xk 0 j j =1 k∉J 0 k∉J 0 j =1 k∉J 0 j∈J 0 Ký hiệu Δk = ∑z j∈J 0 jk c j − ck k ∉ J 0 gọi là ước lượng của véc tơ cột Ak theo cơ sở J và f x = f x 0 − ∑ Δ k xk k∉J 0 - 11 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định Nhận xét Do x ≥ 0 nên nếu ∀k ∉ J 0 , Δ k ≤ 0 thì f x ≥ f x 0 , ∀x ∈ M do đó ta có dấu hiệu tối ưu sau đây Phương án cực biên x0 với cơ sở J0 là phương án tối ưu khi và chỉ khi Δk ≤ 0, ∀k ∉ J 0 . Công thức biến đổi. Bảng đơn hình Giả sử x0 với cơ sở J là một phương án cực biên nhưng chưa phải là phương án tối ưu, khi đó ∃k ∉ J 0 sao cho Δk > 0 . Giả sử s là một chỉ số trong các chỉ số nói trên s ∉ J0 , Δs > 0 . Theo thuật toán trên ta cần cải tiến x0 để nhận được một phương án cực biên mới tốt hơn. Ta sẽ tìm một phương án cực biên mới x1 ứng với cơ sở J1 chỉ khác J một véc tơ J 1 = J 0 \ r ∪ s , tức là ta đưa véc tơ As vào cơ sở thay cho véc tơ Ar bị loại ra khỏi cơ sở J. Vì mọi thành phần ngoài cơ sở của một phương án cực biên đều bằng 0 nên phương án cực biên mới x1 có cơ sở J 1 = J \ r ∪ s là ⎧0 víi k ∉ J 0 , k ≠ støc lμ k ∉ J1 x =⎨ 1 k 5 ⎩θ víi k = s Trong đó θ là một số dương sẽ được xác định sau sao cho x1 là một phương án cực biên. * Tìm điều kiện của θ để x1 là một phương án Thay 5 vào 3 ta được x1j = x 0j − ∑ z jk .x1k = x 0j − θ z js ∀j ∈ J 0 k ∉J 0 ⎧0 víi j ∉ J 0 , j ≠ støc lμ j ∉ J1 ⎪ = ⎨θ víi j = s 1 Hay x j 6 ⎪x 0 − θ z víi j ∈ J ⎩ j js 0 Để x1 là một phương án thì nó phải thỏa mãn các điều kiện buộc Ax=b và x ≥ 0. + Ta thấy rằng với mọi θ , ta có Ax1 = ∑ x1j Aj + ∑ x1j Aj = ∑ x 0j − θ z js A j + θ As = ∑x 0 j A j − θ ∑ z js A j + θ As = b − θ As + θ As = b j∈J j∉J j∈J j∈J 0 j∈J 0 Vậy với mọi θ thì ràng buộc thứ nhất thỏa mãn. Ta chỉ cần tìm θ sao cho x1 ≥ 0. Có hai trường hợp xảy ra - 12 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định + Trường hợp 1 Nếu zjs ≤ 0 với mọi j ∈J thì x1 ≥ 0 với mọi θ > 0 và x1 là phương án của bài toán. Nhưng do Δ s > 0 f x1 = f x 0 − ∑ k∉J0 Δ k x 1k = f x 0 − Δ sθ → − ∞ k h i θ → + ∞ Như vậy hàm mục tiêu không bị chặn dưới trên miền ràng buộc. Khi đó bài toán không có lời giải hữu hạn. + Trường hợp 2 Nếu ∃j ∈ J 0 để zjs > 0, khi đó theo 6 số θ không thể lớn tùy ý, nó phải thỏa mãn x j − θ z js ≥ 0, ∀j ∈ J 0 mà z js > 0 . Giá trị θ lớn nhất chỉ có thể bằng 0 ⎧⎪ x 0j ⎫⎪ min ⎨ j ∈ J 0 mà z js > 0 ⎬ ⎩⎪ z js ⎪⎭ Nếu vượt qua miền đó sẽ có một trong các x 0j − θ z js 0. z rs Rõ ràng, phương án x1 được xác định theo công thức 7 là phương án cực biên với cơ sở J 1 = J 0 \ r ∪ s . Thật vậy, theo 7 suy ra x1r = 0 nên J + X 1 ⊆ J 1 với J+X = { j x j > 0} . Ta cần chứng minh hệ véc tơ { Aj , j ∈ J 1} độc lập tuyến tính. - 13 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định + Thật vậy, giả sử ∑α x 1 j j = 0 ta cần chứng minh α j = 0∀j ∈ J 1 . Ta có j∈J 0= ∑α j xj = ∑ j∈J , j ≠ r α j x j + α s xs = ∑ j∈J 0 , j ≠ r α j x j + α s ∑ z js Aj = j∈J 0 ∑ j∈J 0 , j ≠ r α j −α s z js Aj + α s zrs Ar j∈J 1 Vì hệ véc tơ { Aj , j ∈ J 0 } độc lập tuyến tính, nên ⎧⎪α j − α s z js = 0∀j ∈ J 0 , j ≠ r ⎨ ⎪⎩α s zrs = 0 Vì zrs > 0 nên suy ra α s = 0 , do đó α j = 0 j ∈ J , j ≠ r . Vậy α j = 0∀j ∈ J 1 = J 0 \ r ∪ s . Vì J + X 1 ⊆ J 1 nên hệ véc tơ {A , j ∈ J j + X 1 } độc lập tuyến tính. Do đó x là 1 phương án cực biên và J1 là cơ sở của phương án cực biên x1. Như vậy x1 là một phương án cực biên của bài toán. ở trên ta đã tìm các thành phần của phương án cực biên mới x1 cùng với giá trị hàm mục tiêu fx1 thông qua các hệ số khai triển zjk và các ước lượng Δ k trong cơ sở J. Như vậy chúng ta cần xác định các đại lượng z1jk và Δ1k trong cơ sở J1. Theo định nghĩa zjk và z1jk là các hệ số khai triển của véc tơ Ak tương ứng với cơ sở J, J1. Ak = ∑z j∈J 0 jk Aj = ∑z 1 1 jk Aj * j∈J ∑z j∈J 0 jk Aj = ∑ j∈J 0 , j ≠ r z jk Aj + zrk Ar ** Từ 1 ⎛ ⎞ As = ∑z js Aj = ∑ A j z js + z rs Ar vì z rs > 0tacó A r = z rs ⎜ As − ∑ z js A j ⎟ . j∈ J 0 j∈ J 0 , j ≠ r ⎝ j∈ J 0 , j ≠ r ⎠ Thay vào ** ta được zrk ∑z j∈J 0 jk Aj = ∑ j∈J 0 , j ≠ r z jk Aj + zrs As − ∑ z js Aj j∈J 0 , j ≠ r zrk z *** = ∑ j∈J 0 , j ≠ r z jk − zrs .z js Aj + rk . As zrs Vì { Aj , j ∈ J 1} độc lập tuyến tính nên từ * và ** suy ra - 14 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định ⎧ z rk ⎪z víi j = s ⎪ x1jk = ⎨ rs ⎪ z − z rk z víi j ∈ J 0 , j ≠ r ⎪⎩ jk z rs js ⎛ zrk ⎞ z Δ1k = ∑z 1 jk c j − ck = ∑ ⎜ z jk − j∈J 0 , j ≠ r ⎝ zrs z js ⎟c j + rk cs − ck zrs j∈J 1 ⎠ ⎛ zrk ⎞ z ⎛ z ⎞ = ∑⎜z jk − zrs z js ⎟c j + rk cs − ck zrs vì j=r thì ⎜ z jk − rk z js ⎟ = 0 zrs j∈J 0 ⎝ ⎠ ⎝ ⎠ zrk zrk = ∑ z jk c j − ck − ∑z js c j − cs = Δ k − Δs . j∈J 0 zrs j∈J 0 zrs zrk Vậy Δ1k = Δ k − Δs . zrs Để thuận tiện cho việc tính toán, người ta sắp xếp các số liệu thành một bảng gọi là bảng đơn hình như dưới đây Hệ Cơ Phương c1 c2 .... ck cs cn số sở án A1 A2 ... Ak As An c j1 Aj1 x j1 z j11 z j1 2 ... z j1k ... z j1s ... z j1n ... c j2 Aj2 x j2 z j2 1 z j2 2 z j2 k ... z j2 s ... z j2 n ... ... ... ... ... ... ... ... ... ... c jr Ajr x jr z jr 1 z jr 2 ... z jr k ... z jr s ... z jr s ... ... ... ... ... ... ... ... ... c jm z jm 1 z jm 2 z jmk ... z jm s ... z jm s Ajm x jm fx Δ1 Δ 2 ... ... Δk Δ s ... Δn Các cột ứng với j∈J sẽ là các véc tơ đơn vị với số 1 trên dòng với chỉ số j. Chú ý Đối với bài toán dạng chuẩn, ta có ngay một phương án cực biên x 0 = b1 , b2 ,..., bm ,0,0,...,0 với hệ véc tơ cơ sở tương ứng là A1 , A2 ,..., Am . Đây là các véc tơ đơn vị nên trong bảng đơn hình xuất phát ta có z jk = a jk - 15 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định Thuật toán đơn hình Bước xuất phát Tìm một phương án cực biên x0 và cơ sở J0 tương ứng . Tìm các hệ số khai triển zjk và các ước lượng Δ k . Bước 1 Kiểm tra dấu hiệu tối ưu - Nếu Δ k ≤ 0∀k ∉ J 0 thì x0 là phương án tối ưu. Thuật toán kết thúc. - Nếu ∃Δ k > 0 thì chuyển sang bước 2. Bước 2 Kiểm tra dấu hiệu hàm mục tiêu giảm vô hạn Với mỗi k ∉ J 0 mà Δ k > 0 thì kiểm tra các hệ số khai triênjk của cột Ak tương ứng a Nếu có một Δ k > 0 mà tất cả zjk ≤ 0 ∀j ∈ J 0 thì kết luận hàm mục tiêu giảm vô hạn trên miền ràng buộc. Bài toán không có lời giải hữu hạn. Thuật toán kết thúc. b ∀k ∉ J 0 mà Δ k > 0 đều tồn tại ít nhất một hệ số zjk>0 thì chuyển sang bước 3 Bước 3 Xác định cột xoay, dòng xoay, phần tử trục - Chọn chỉ số s ∉ J 0 Δ s = max {Δ k > 0, k ∉ J 0 } , đánh dấu cột s là cột xoay xr0 ⎧⎪ x 0j ⎫⎪ - Tìm chỉ số r đạt min θ = = min ⎨ , z js > 0 ⎬ , đánh dấu hàng r là hàng xoay. zrs z ⎪⎩ js ⎪⎭ Bước 4 Tính các x j , f x , Δ k , z jk trong cơ sở mới J 1 = J 0 \ r ∪ s theo các công thức 1 1 1 1 trên. Ghi nhận các kết quả trong một bảng mới. Quay trở lại bước 1. - Để nhận được bảng đơn hình mới từ bảng đơn hình cũ ta làm như sau + Thay Ar bằng As, cr bằng cs. + Chia các phần tử trên hàng xoay hàng r cho phần tử trục zrs ta được hàng r mới gọi là hàng chuẩn. + Mỗi phần tử khác ngoài hàng xoay trừ đi tích của phần tử cùng hàng với nó trên cột xoay với phần tử cùng cột với nó trên hàng chuẩn được phần tử cùng vị trí trong bảng đơn hình mới. a b bd a' = a − c d c Dòng xoay Cột xoay - 16 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định Tính hữu hạn của thuật toán đơn hình Nếu bài toán quy hoạch tuyến tính có phương án và không suy biến thì sau hữu hạn bước lặp theo thủ tục đơn hình ta sẽ tìm thấy phương án tối ưu hoặc phát hiện ra bài toán có hàm mục tiêu giảm vô hạn hay bài toán không có lời giải hữu hạn. xr0 1 0 Thật vậy, vì bài toán không suy biến nên x 0j > 0∀j ∈ J nên θ = > 0 suy ra x ≠ x , zrs fx1>0, bài toán “M” có dạng - 17 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định n m f x = ∑ c j x j + M ∑ xn+i → min j =1 i =1 ⎧n ⎪∑ aij x j + x n +i = bi i = 1, m Với điều kiện ⎨ j =1 ⎪ x ≥ 0 j = 1, n ⎩ j Bài tóan “M” có ngay phương án cực biên xuất phát 0 x = 0;0;....;0; b1; b2 ;.....bm với cơ sở J0 là Em =An+1; An+2;....;An+m; J0 = {n+1; n+2; ....;n+m} Do vậy áp dụng được thuật toán đơn hình để giải bài toán “M”. Từ cách xây dựng bài toán “M” như trên ta thấy 0 Nếu x = x1; x2 ;.....xn ;0;0;....;0 là phương án của bài toán “M” thì x = x1; x2 ;.....xn là phương án của bài toán ban đầu và ngược lại, đồng thời fx = f x . Mối quan hệ giữa bài toán “M” và bài toán ban đầu • Nếu bài toán “M” có x = x1* , x2* ,...., xn* ,0,0,....,0 là phương án tối ưu thì bài * toán ban đầu có x* = x1* , x2* ,...., xn* là phương án tối ưu và f x = f x* . * • Nếu bài toán “M” có x = x1* , x2* ,...., xn*+ m trong đó tồn tại ít nhất một * xn+i* > 0 i = 1, m thì bài toán ban đầu không có phương án tối ưu bài toán không giải được. • Nếu bài toán “M” vô nghiệm thì bài toán ban đầu cũng vô nghiệm. Chú ý • Nếu bài toán ban đầu có nghiệm x* thì nghiệm này chỉ có thể nhận được sau ít nhất m + 1 bảng đơn hình. • Nếu ma trận hệ số aij đã chứa m1 véc tơ đơn vị m1 MIN 2x2 + x3 + 2x4 + 3x5 = 6 x2 - x4 + x5 + x6 = 3 x1 -4x4 + 2x5 = 5 x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0 Ñaây laø baøi toaùn quy hoaïch tuyeán tính daïng chuaån, ta coù ngay phöông aùn cöïc bieân x 0 = 5,0,6,0,0,3 vôùi cô sôû A3, A6, A1. Töø ñoù ta coù baûng ñôn hình xuaát phaùt nhö sau 2 -1 3 2 1 4 Heä soá Cô sôû θ A1 A2 A3 A4 A5 A6 3 A3 6 0 2 1 2 3 0 2 4 A6 3 0 1 0 -1 1 1 3 2 A1 5 1 0 0 -4 2 0 5/2 Fx 40 0 11 0 -8 16 0 Do coøn toàn taïi giaù trò Delta lôùn hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo Coät coù giaù trò lôùn nhaát öùng vôùi bieán ñöa vaøo laø A5 Haøng coù giaù trò θ nhoû nhaát öùng vôùi coät ñoù laø haøng 1 2 -1 3 2 1 4 Heä soá Cô sôû θ A1 A2 A3 A4 A5 A6 1 A5 2 0 2/3 1/3 2/3 1 0 3 4 A6 1 0 1/3 -1/3 -5/3 0 1 3 2 A1 1 1 -4/3 -2/3 -16/3 0 0 - Fx 8 0 1/3 -16/3 -56/3 0 0 Do coøn toàn taïi giaù trò Delta lôùn hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo Coät coù giaù trò lôùn nhaát öùng vôùi bieán ñöa vaøo laø A2 Haøng coù giaù trò θ nhoû nhaát öùng vôùi coät ñoù laø haøng 1 2 -1 3 2 1 4 Heä soá Cô sôû θ A1 A2 A3 A4 A5 A6 -1 A2 3 0 1 1/2 1 3/2 0 - - 19 - Nguyễn Hải Đăng - Khoa KHCB&KTCS Toán Kinh tế - Trường Cao Đẳng Công Nghiệp Nam Định 4 A6 0 0 0 -1/2 -2 -1/2 1 - 2 A1 5 1 0 0 -4 2 0 - Fx 7 0 0 -11/2 -19 -1/2 0 Phöông aùn toái öu cuûa baøi toaùn laø 5,3,0,0,0,0 Giaù trò haøm muïc tieâu ñaït ñöôïc laø Fx = 7 Bài 2 Fx = 2x1 - x2 + 3x3 + 2x4 + x5 + 4x6 => MIN 2x1 + x3 + 2x4 + 3x5 + x6 = 6 x2 - x4 + x5 = 3 - x1 + 3x4 + 2x5 ≤5 x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0 Chuyeån veà daïng chính taéc Fx = 2x1 - x2 + 3x3 + 2x4 + x5 + 4x6 => MIN 2x1 + x3 + 2x4 + 3x5 + x6 = 6 x2 - x4 + x5 = 3 - x1 + 3x4 + 2x5 + x7 = 5 x7 laø bieán phuï x1 >=0, x2 >=0, x3 >=0, x4 >=0, x5 >=0, x6 >=0, x7 >=0 Ñaây laø baøi toaùn quy hoaïch tuyeán tính daïng chuaån, ta coù ngay phöông aùn cöïc bieân x 0 = 0,3,0,0,0,6,5 vôùi cô sôû A6, A2, A7. Töø ñoù ta coù baûng ñôn hình xuaát phaùt nhö sau Heä Cô 2 -1 3 2 1 4 0 θ soá sôû A1 A2 A3 A4 A5 A6 A7 4 A6 6 2 0 1 2 3 1 0 2 -1 A2 3 0 1 0 -1 1 0 0 3 0 A7 5 -1 0 0 3 2 0 1 5/2 Fx 21 6 0 1 7 10 0 0 Do coøn toàn taïi giaù trò Delta lôùn hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo Coät coù giaù trò lôùn nhaát öùng vôùi bieán ñöa vaøo laø A5 Haøng coù giaù trò θ nhoû nhaát öùng vôùi coät ñoù laø haøng 1 Heä Cô 2 -1 3 2 1 4 0 θ soá sôû A1 A2 A3 A4 A5 A6 A7 1 A5 2 2/3 0 1/3 2/3 1 1/3 0 3 -1 A2 1 -2/3 1 -1/3 -5/3 0 -1/3 0 - 0 A7 1 -7/3 0 -2/3 5/3 0 -2/3 1 3/5 Fx 1 -2/3 0 -7/3 1/3 0 -10/3 0 Do coøn toàn taïi giaù trò Delta lôùn hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo Coät coù giaù trò lôùn nhaát öùng vôùi bieán ñöa vaøo laø A4 Haøng coù giaù trò θ nhoû nhaát öùng vôùi coät ñoù laø haøng 3 Heä Cô 2 -1 3 2 1 4 0 θ - 20 - Nguyễn Hải Đăng - Khoa KHCB&KTCS
Tài Liệu Tươi Tải tài liệu, báo cáo, lời giải hay, giáo trình, bài kiểm tra, đồ án, luận án, văn bản, ebook, văn bản pháp luật, giáo án, đề thi, đáp án, bài giảng... © 2023 Tài Liệu Tươi. Đã đăng ký bản quyền.
4/25/2018 1 TOÁN KINH TẾ 1 Một số phương pháp toán cơ bản thường sử dụng trong kinh tế - Phần 1 Ngọc Lam Điện thoại cá nhân 0918 625526 Hạn chế điện thoại ngoài giờ hành chính và không nhắn tin Email nnlam 4/25/2018 2 Vị trí của học phần Toán kinh tế Kinh tế học Kinh tế lượng Mô hình Toán Kinh tế 4/25/2018 3 Tài liệu tham khảo 1. Bài giảng Toán Kinh tế. Nguyễn Ngọc Lam. Lưu hành nội bộ. 2011. 2. Giáo trình Toán Kin 6 trang Chia sẻ huongnhu95 Ngày 28/08/2021 Lượt xem 424 Lượt tải 0 Tóm tắt tài liệu Bài giảng Toán Kinh tế 1 - Nguyễn Ngọc Lam, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trênh tế 1. Nguyễn Tuấn Kiệt NXB 3. Toán cao cấp C1, 2. Nguyễn Quốc Hưng. NXB Đại học quốc gia 2009 4. Toán cao cấp C1, 2. Nguyễn Quốc Hưng. NXB Đại học quốc gia 2009 5. Toán học cao cấp, tập 1,2,3. Nguyễn Đình Trí. NXB Giáo dục. 2004. 6. Fundamental Methods of Mathematical Economics, 2nd Ed. Alpha McGraw-Hill Kogakusha, Ltd. 1975. 4/25/2018 4 Nội dung học phần Đại số tuyến tính Giải tích Đạo hàm, vi phân Hàm nhiều biến5 1 Ma trận - Định thức Hệ phương trình tuyến tính2 Hàm số và giới hạn hàm 1 biến3 Đạo hàm và vi phân hàm 1 biến4 Tích phân6 Phương trình vi phân7 4/25/2018 5 Tài liệu tham khảo Đánh giá • Kiểm tra hệ số 0,3 • Điểm thi hệ số 0,7 Kiểm tra, thi được sử dụng tài liệu • Lịch thi và kiểm tra sẽ được công bố trên lớp và web. • Các khiếu nại chỉ giải quyết trong buổi trả bài. • Khi đi kiểm tra, thi phải đem theo giấy tờ có ảnh. 4/25/2018 6 Tài liệu tham khảo Điểm 10 Điểm A,B,C,D Điểm 4 0 – 3,9 F 0 4,0 – 4,9 D 1,0 5,0 – 5,4 D+ 1,5 5,5 – 6,4 C 2,0 6,5 – 6,9 C+ 2,5 7,0 – 7,9 B 3,0 8,0 – 8,9 B+ 3,5 9,0 – 10 A 4,0 Các file đính kèm theo tài liệu nàybai_gian
1BÀI TẬP TOÁN KINH TẾChương 2. Toán tài chính căn Lãi đơnLãiGiá trị tương lai1S P I P P r t P r t Bài tập1. $10 000 is invested for 6 years at an annual simple interest rate lãi suất năm of 6%.a How much interest will be earned?b What is the future value of the investment at the end of the 6 years?2. If you borrow $800 for 6 months at 6% annual simple interest, how much must you repay at theend of the 6 months?3. If you lend $3500 to a friend for 15 months at 8% annual simple interest, find the future value ofthe A couple bought some stock chứng khoán for $30 per share cổ phiếu that pays ancổ tức hằng năm of $ per share. After 1 year the price of the stock was $33. Findthe simple interest rate on the growth of their Janie Christopher lent $6000 to a friend for 90 days at 12%. After 30 days, she sold the note to athird party for $6000. What annual simple interest rate did the third party receive? Use 360 daysin a A student has a savings account earning 9% simple interest. She must pay $1500 for first-semestertuition by September 1 and $1500 for second-semester tuition by January 1. How much must sheearn in the summer by September 1 in order to pay the first-semester bill on time and still havethe remainder of her summer earnings grow to $1500 between September 1 and January 1?7. What is the present value of an investment at 6% annual simple interest if it is worth $832 in 8months?8. If $5000 is invested at 8% annual simple interest, how long does it take to be worth $9000?9. Nếu bạn gửi ngân hàng 100 triệu đồng với lãi suất năm 5%, theo phương thức lãi đơn thì tổng sốtiền bạn thu được sau 6 năm là bao nhiêu?10. Nếu bạn gửi ngân hàng 50 triệu đồng với lãi suất năm 4%, theo phương thức lãi đơn thì tổngsố tiền bạn thu được sau 5 năm là bao nhiêu?11. Nếu bạn gửi ngân hàng 60 triệu đồng với lãi suất năm 4%, theo phương thức lãi đơn thì saubao lâu, tổng số tiền bạn thu được là 72 triệu đồng?12. Anh A gửi ngân hàng 90 triệu đồng, trong 2 năm. Tổng số tiền anh A thu được là 99 triệuđồng. Tìm mức lãi đơn của khoản đầu tư này.
bài giảng toán kinh tế
