Bài giảng Mô hình toán kinh tế - Lại Đức Hùng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:142

Thêm vào BST

Báo xấu

12
lượt xem 8
download

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

(NB) Bài giảng Mô hình toán kinh tế được biên soạn theo chương trình môn học Mô hình toán kinh tế dành cho sinh viên khối ngành quản lý và kinh doanh, với nội dung gồm có 3 chương, trình bày như sau: Quy hoạch tuyến tính; bảng vào ra; mô hình toán kinh tế. Mời các bạn cùng tham khảo!

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ế - Lại Đức Hùng

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI LẠI ĐỨC HÙNG BÀI GIẢNG MÔ HÌNH TOÁN KINH TẾ mathematical economics model (LƯU HÀNH NỘI BỘ) HÀ NỘI, NĂM 2017 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 1
TÀI LIỆU THAM KHẢO [1] Nguyễn Quang Dong – Ngô Văn Thứ - Hoàng Đình Tuấn, Mô hình toán kinh tế, Đại học Kinh tế quốc dân, Nhà xuất bản Thống kê, 2006. [2] Nguyễn Quang Dong, Kinh tế lượng, Đại học Kinh tế quốc dân, Nhà xuất bản Giao thông Vận tải, 2008. [3] Lê Quốc Phương, Đặng Huyền Linh, Tình hình xây dựng và ứng dụng mô hình kinh tế tại một số cơ quan, tổ chức ở Việt nam, Ban Phân tích và Dự báo Vĩ mô (Trung tâm Thông tin Dự báo Kinh tế - Xã hội quốc gia) [4] Nguyễn Quảng, Nguyễn Thượng Thái, Toán kinh tế, Học viện Công nghệ bưu chính viễn thông, 2007. [5] Nguyễn Hải Thanh, Các phương phápToán kinh tế, Đại học Nông nghiệp Hà Nội, 2008. [6] Lê Đình Thúy(Chủ biên), Toán cao cấp cho các nhà kinh tế, Nhà xuất bản Đại học Kinh tế quốc dân, 2012. [7] Bùi Trinh, Bảng vào ra, Nhà xuất bản Thống kê, 2006. [8] Tổng cục Thống kê, Bảng cân đối liên ngành của Việt Nam năm 1989, 2007, 2012 Nhà xuất bản thống kê, 2010. [9] Alpha C.Chiang – Kevin Wainwright, Fundamental methods of mathematical economics, Springer, 2006. Trần Nam Bình – Viện Đại học New South Wales, Úc Thế giới là một thị trường lớn, con người nếu không phải là kẻ mua thì là người bán. 2 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
MỤC LỤC Trang TÀI LIỆU THAM KHẢO .................................................................... ....2 LỜI NÓI ĐẦU ....................................................................................... ....4 Chương 1. QUY HOẠCH TUYẾN TÍNH §1. Bài toán lập kế hoạch sản xuất ...................................................... ....6 Bài tập ......................................................................................... ..10 §2. Bài toán quy hoạch tuyến tính ....................................................... ..11 Bài tập ......................................................................................... ..20 §3. Giải bài toán quy hoạch tuyến tính bằng hương pháp đơn hình ... ..21 Bài tập ......................................................................................... ..31 §4. Phương pháp tìm phương án cực biên xuất phát........................... ..32 Bài tập ......................................................................................... ..37 Chương 2. BẢNG VÀO RA ( Input – Output table ) §1. Các khái niệm của bảng vào ra ...................................................... ..41 Bài tập .......................................................................................... ..51 §2. Cấu trúc cơ bản của bảng vào ra ................................................... ..52 Bài tập ......................................................................................... ..58 §3. Một số ứng dụng của bảng vào ra ................................................. ..61 Bài tập ......................................................................................... ..73 Chương 3. MÔ HÌNH TOÁN KINH TẾ §1. Các khái niệm cơ bản về mô hình toán kinh tế ............................. .79 Bài tập .......................................................................................... 105 §2. Một số mô hình tối ưu cơ bản ........................................................ 107 Bài tập .......................................................................................... 120 §3. Một số mô hình toán kinh tế ........................................................ 122 Bài tập ......................................................................................... 141 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 3
LỜI NÓI ĐẦU Trong một thế giới toàn cầu hóa các đối tượng vận động trong kinh tế xã hội rất đa dạng và phức tạp. Việt Nam trong thời gian qua và sắp đến hội nhập vào các khối và các tổ chức kinh tế khu vực cũng như toàn cầu: WTO, ASEM, APEC, FTA, Cộng đồng kinh tế ASEAN 2015, TPP…Tuy nhiên để việc hội nhập như thế nào để có hiệu quả về kinh tế xã hội là một câu hỏi rất khó có câu trả lời? Kinh tế học là môn khoa học xã hội, khoa học về con người. Đối tượng nghiên cứu rất phức tạp: “Con người là tổng hòa các mối quan hệ xã hội”. Toán học là môn khoa học cơ bản, một công cụ hết sức hiệu quả giúp cho việc xây dựng, phân tích và giải quyết các vấn đề kinh tế một cách chặt chẽ và hợp lí, mang lại các lợi ích thiết thực. Toán kinh tế là môn khoa học nhằm vận dụng toán học trong xây dựng , phân tích các mô hình kinh tế để từ đó hiểu rõ hơn các nguyên tắc và các quy luật kinh tế của nền kinh tế thị trường. Toán kinh tế cung cấp cho các Nhà Quản lý các kiến thức để họ có thể vận dụng vào việc ra các quyết định sản xuất. Giải Nobel kinh tế năm 2012 được trao cho Lloyd S. Shapley là nhà toán học và Alvin E. Roth nhà kinh tế học vì các nghiên cứu của hai ông trong lĩnh vực lý thuyết “ghép đôi” và các phát minh về thiết kế thị trường có khả năng ứng dụng rộng rãi trên khắp thế giới. Trên tinh thần đó, cuốn “Bài giảng mô hình toán kinh tế” được biên soạn theo chương trình môn học Mô hình toán kinh tế dành cho sinh viên khối ngành quản lý và kinh doanh với thời lượng 45 tiết của trường Đại học Công nghiệp Hà Nội. Trong cuốn sách này, dùng kiến thức cơ bản của Toán học để người đọc hiểu được các cấu trúc và biết cách phân tích các Mô hình kinh tế đã được áp dụng với kinh tế học vĩ mô hiện đại, mong muốn làm cho các đối tượng vận động trong kinh tế đơn giản hơn. Cuốn sách gồm có ba chương : Chương 1 Trình bày những nội dung cơ bản về mô hình tối ưu tuyến tính trong sản xuất và kinh doanh. Cụ thể là các khái niệm, tích chất cơ bản và phương pháp đơn hình để giải bài toán quy hoạch tuyến tính. 4 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
Chương 2 Trình bày cấu trúc, các khái niệm của mô hình vào ra. Thông qua mô hình vào ra người đọc có thể hiểu về bức tranh kinh tế của một quốc gia và xây dựng được các bảng vào ra đơn giản cho một số ngành kinh tế. Chương 3 Trình bày về mô hình toán kinh tế. Cấu trúc, các khái niệm, cách phân tích một mô hình toán kinh tế.Trong đó có đưa ra một số mô hình toán kinh tế : mô hình tối ưu, mô hình cân đối liên ngành, mô hình kinh tế cân bằng, mô hình kinh tế tĩnh,… Để học tốt môn Mô hình toán kinh tế, người học cần các có kiến thức cơ bản về toán cao cấp, kinh tế học, như là: Đại số tuyến tính ( Ma trận, định thức, giải hệ phương trình tuyến tính, không gian véc tơ), giải tích ( Đạo hàm, vi phân của hàm số một biến và nhiều biến, phương trình vi phân, phương trình sai phân), kinh tế vi mô, kinh tế vĩ mô. Ngoài ra để tính toán nhanh các mô hình toán kinh tế thì người đọc cần phải có kỹ năng sử dụng máy tính. Trong lần xuất bản này, tác giả hy vọng cuốn sách sẽ có ý nghĩa thiết thực đối với sinh viên khối ngành quản lý và kinh doanh. Tác giả đã nhận được nhiều ý kiến đóng góp quý báu của các bạn đồng nghiệp ở các khoa : Kiểm toán – kế toán, Quản lý và kinh doanh, Khoa học cơ bản của Trường Đại học Công nghiệp Hà Nội. Tác giả xin gửi lời cảm ơn chân thành tới các bạn bởi sự đóng góp đó. Tuy nhiên vẫn còn rất nhiều vấn đề trong cuốn sách này cần phải tiếp tục thảo luận. Tác giả rất mong tiếp tục nhận được những ý kiến đóng góp từ phía các bạn đồng nghiệp và đông đảo bạn đọc để cuốn sách được hoàn thiện hơn. Mọi ý kiến đóng góp xin gửi về hòm thư : hungminh0102@gmail.com Xin chân thành cảm ơn! Hà nội, tháng 04 năm 2017 TÁC GIẢ HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 5
CHƯƠNG I. QUY HOẠCH TUYẾN TÍNH MỤC TIÊU CHƯƠNG I .Giải bài toán quy hoạch tuyến tính sau: Tìm vectơ x  ( x1, x2 ,..., xn )  n sao cho hàm số: n z  f ( x)  c1 x1  c2 x2  ...  c j x j  ...cn xn   c j x j  min(max) (1.1) j 1  n  aij x j ( , , ) bi ; i  1, m (1.2) thỏa mãn các điều kiện:  j 1  x (, , ) 0 ; j  1, n (1.3)  j §1. BÀI TOÁN LẬP KẾ HOẠCH SẢN XUẤT Trong những ngày tháng 8 năm 2015 đã có nhiều biến động về thị trường tài chính. Từ khi Ngân hàng Trung Quốc phá giá đồng Nhân dân tệ 4,6%, dẫn tới đồng tiền của các nước trong khu vực và trên thế giới cũng phải làm theo. Tại sao lại có phản ứng dây truyền như vậy? Với tình hình kinh tế biến động như thế, thì chính sách tiền tệ, tài khóa và các doanh nghiệp phải hành động như thế nào? Để kinh tế không vào vòng suy thoái. Song hành cùng chính sách điều hành vĩ mô của các chính phủ thì mọi doanh nghiệp muốn sản xuất-kinh doanh n sản phẩm tốt nhất để cung ứng ra thị trường với các điều kiện ràng buộc: lượng nguyên liệu b, nhân công x, nhà xưởng y, công nghệ z, thuế k…hiện có. Hãy lập kế hoạch (mô hình) sản xuất-kinh doanh mỗi loại trong n sản phẩm là bao nhiêu sao cho tổng danh thu từ việc bán các sản phẩm lớn nhất- max (hoặc tổng chi phí: b,x,y,z,k,… nhỏ nhất-min). Đó là bài toán tối ưu trong sản xuất-kinh doanh mà mọi doanh nghiệp cần phải thiết lập trước khi tham gia vào thị trường. Ví dụ 1.1. Một nông dân có b1 sào đất để trồng hoa và lúa. Ông ta dự định mua hai loại giống trên là b2 VNĐ, số tiền phân bón là b3 VNĐ. Hãy lập kế hoạch sản xuất sao cho tổng tiền thu được lớn nhất từ việc bán các sản phẩm (hoặc sản xuất sao cho tổng tiền chi phí là nhỏ nhất). 6 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
Mô hình: Gọi x1 là số sào trồng hoa thu hoạch quy ra tiền là c1 , x2 là số sào trồng lúa thu hoạch quy ra tiền là c2 . Tìm x1 , x2 để z  c1 x1  c2 x2 đạt max  x1  x2  b1  ex  fx  b  Thỏa mãn các điều kiện ràng buộc:  1 2 2 .  gx1  hx2  b3  x1 , x2  0 Ví dụ 1.2. Một doanh nghiệp hiện có 3 loại nguyên liệu b1  8, b2  8, b3  4 (tạ) muốn sản xuất 2 sản phẩm xi với c1  4, c2  3 ( triệu đồng) là giá bán một đơn vị sản phẩm loại j, j  1, 2 . Mỗi sản phẩm phải dùng số lượng nguyên liệu được cho như trong bảng sau: Sản phẩm x1 x2 Nguyên liệu Nguyên liệu hiện có bi 1 2 0 8 2 0 1 8 3 1 0 4 Tiền bán được từ SP xi 4 3 Với các điều kiện khác (thuế, nhà xưởng, công nghệ, nhân công) ổn định. Hãy lập kế hoạch (mô hình) sản xuất mỗi loại sản phẩm là bao nhiêu sao cho tổng danh thu từ việc bán các sản phẩm lớn nhất trong điều kiện nguyên liệu hiện có. Mô hình: Gọi số lượng loại sản phẩm thứ nhất thứ hai theo thứ tự là x1 , x2 Doanh thu từ việc bán các sản phẩm là: z  4 x1  3x2 Tìm x1 , x2 để z  4 x1  3x2 đạt giá trị lớn nhất với các điều kiện: Lượng nguyên liệu thứ nhất dùng để sản xuất sản phẩm thứ nhất x1 là 2x1 Lượng nguyên liệu thứ hai dùng để sản xuất sản phẩm thứ hai x2 là 1.x2 . Tìm x1 , x2  để f ( x1 , x2 )  4 x1  3x2  max HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 7
 2 x1  x2  8   0 x1  x2  8 Thỏa mãn các điều kiện ràng buộc:  .  x1  0 x2  4  x1 , x2  0 Ví dụ 1.3. Một doanh nghiệp hiện có m nguyên liệu bi (i  1, m) người ta muốn sản xuất n sản phẩm, c j ( j  1, n) là số tiền thu được từ việc bán một đơn vị sản phẩm loại j . Mỗi sản phẩm phải dùng hết aij đơn vị nguyên liệu, được cho như trong bảng sau: Sản phẩm x1 x2 … xj … xn Ng.liệu Nguyên liệu hiện có 1 a11 a12 … a1 j … a1n b1 2 a21 a22 … a2 j … a2n b2 … ….. … m am1 am 2 … amj … amn bm Tiền lãi c1 c2 … c j cn Hãy lập kế hoạch (mô hình) sản xuất mỗi loại sản phẩm là bao nhiêu sao cho tổng số tiền thu được từ việc bán các sản phẩm lớn nhất (hoặc chi phí là nhỏ nhất) trong điều kiện nguyên liệu hiện có . Mô hình: Gọi x j  0 , ( j  1, n ) là số lượng sản phẩm thứ j sẽ sản xuất, c j ; j  1, n là số tiền thu được từ việc bán một đơn vị sản phẩm loại j .Tổng số tiền thu được từ việc bán các sản phẩm là: n z  f ( x)  c1 x1  c2 x2  ...  c j x j  ...cn xn   c j x j . j 1 Vì yêu cầu tiền thu được từ việc bán các sản phẩm lớn nhất nên ta có: n z  f ( x)   c j x j  max . j 1 8 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
Lượng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ nhất x1 là ai1 x1. Lượng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ hai x2 là ai 2 x2 . ………….. Lượng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ n xn là ain xn . Vậy lượng nguyên liệu thứ i; i  1, m dùng để sản xuất các sản phẩm là: ai1 x1  ai 2 x2  ...  ain xn . Vì lượng nguyên liệu thứ i; i  1, m dùng để sản xuất các sản phẩm x j  0 không vượt quá lượng nguyên liệu hiện có bi ; i  1, m nên: ai1 x1  ai 2 x2  ...  ain xn  bi . Tóm tắt mô hình như sau: Tìm x  ( x1, x2 ,..., xn )  n . n Để z  f ( x)  c1 x1  c2 x2  ...  c j x j  ...cn xn   c j x j  max j 1 Thỏa mãn các điều kiện ràng buộc:  a11 x1  a12 x2  ...a1n xn  b1  a x  a x  ...a x  b  21 1 22 2 2n n 2   .... . a x  a x  ...a x  b  m1 1 m 2 2 mn n m  x j  0, j  1...n Bài tập thảo luận 1.1: Theo Tổng cục thống kê (GSO), năm 2014 Việt Nam xuất khẩu gạo đạt gần 6,38 triệu tấn (trị giá 2,96 tỷ USD), nhập khẩu 9 triệu tấn ngô-đậu tương (trị giá hơn 4 tỷ USD). Mặc dù là nước nông nghiệp nhưng nghịch lý này tồn tại đã nhiều năm. Anh chị có nhận xét gì về các con số thống kê trên? Nếu anh chị là chủ doanh nghiệp sản xuất-kinh doanh một trong các sản phẩm: gạo; ngô; đậu tương thì anh chị có dự án sản xuất- kinh doanh gì mới? HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 9
BÀI TẬP 1.1. Một doanh nghiệp dệt có kế hoạch sản suất 3 loại vải A, B, C. Nguyên liệu để sản xuất là các loại sợi cotton, kater, polyester. Doanh nghiệp đã chuẩn bị 3 loại nguyên liệu trên với khối lượng tương ứng là 3 tấn; 2,5 tấn; 4,2 tấn. Mức tiêu hao mỗi loại sợi để sản xuất 1m vải và giá bán (ngàn đồng/m) vải thành phẩm mỗi loại được cho trong bảng sau: Sản phẩm Nguyên A B C Nguyên liệu(g) liệu(kg) Cotton 200 150 100 3000 Katé 300 50 200 2500 Polyester 100 300 350 4200 Giá bán 35 48 25 Hãy lập mô hình toán học của bài toán để lập kế hoạch sản xuất tối ưu, nghĩa là sản xuất mỗi loại vải bao nhiêu mét để tổng doanh thu của doanh nghiệp đạt được cao nhất, biết rằng với giá bán đã định thì doanh nghiệp có thể tiêu thụ được hết số sản phẩm sẽ sản xuất. 1.2. Một công ty cần vận chuyển hàng hóa từ các kho I, II với khối lượng lần lượt là 150 tấn, 120 tấn đến các đại lí A, B, C với nhu cầu cần nhập hàng lần lượt là 70 tấn, 110 tấn, 80 tấn. Cho biết chi phí vận chuyển hàng hóa (ngàn đồng/tấn) từ các kho đến các đại lí được cho trong bảng sau: Đại lý A B C Kho hàng I 100 70 30 II 50 90 60 Hãy lập mô hình toán học (lập kế hoạch) vận chuyển hàng hóa từ các kho đến các đại lí sao cho tổng chi phí vận chuyển nhỏ nhất. 10 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
§2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. Bài toán quy hoạch tuyến tính dạng tổng quát & các khái niệm Bài toán quy hoạch tuyến tính tổng quát có dạng: Tìm vectơ x  ( x1, x2 ,..., xn )  n Sao cho hàm số n z  f ( x)  c1 x1  c2 x2  ...  c j x j  ...cn xn   c j x j  min(max) (1.1) j 1  n  aij x j ( , , ) bi ; i  1, m (1.2) Thỏa mãn các điều kiện:  j 1  x (, , ) 0 ; j  1, n (1.3)  j Ở đó z, x1; x2 ;...x j ;...xn gọi là các biến số, c   c1 , c2 , ..., cn  gọi là hệ số của các biến , aij , bi là các hằng số (có thể là tham số). Hàm mục tiêu: z = f ( x) (1.1) gọi là hàm mục tiêu. Ta gọi bài toán f ( x)  min là bài toán min, bài toán f ( x)  m ax gọi là bài toán max. Ràng buộc: Các điều kiện xác định ở (1.3) là các ràng buộc dấu (nếu không nói gì về điều kiện dấu của biến x j thì quy ước x j nhận dấu tuỳ ý).Các điều kiện xác định ở (1.2) gọi là ràng buộc hàm ( hàm mục tiêu là hàm tuyến tính và các ràng buộc là các phương trình, bất phương trình tuyến tính). Ứng với ràng buộc thứ i ta có Ai  (ai1 , ai 2 ,...ain ) là véctơ dòng thứ i , hệ véctơ Ai này tạo thành một ma trận ràng buộc hay ma trận hệ số:  a11 a12 ... a1n  a a22 ... a2 n  A   21  a  ;  ... ... aij ...   ij  mxn    am1 am 2 ... amn   a1 j   x1   c1   b1  a  x  c  b  A  j  2j ; x  2 ;c  t  2 ; b 2  ...   ...   ...   ...           amj   xn  cn  bm  theo thứ tự là các ma trận véctơ cột thứ j của ma trận A; biến số, hệ số của biến số trong hàm mục tiêu, bi hệ số của ràng buộc. HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 11
Ví dụ 1.4. Cho bài toán quy hoạch tuyến tính f ( x)  3x1  x2  3x3  x4  min  3x1  4 x2  3x3  x4  12 x x  x3 5  1 2 5 x  x  5 x 6  1 2 3  x j  0 , j  1, 4  Ta có A1  (3, 4, 3, 4); A2  (1, 1, 1,0); A3  (5,1, 5,0) 3  4   3  1  3 4 3 1  1   2   3  A  1  ; A   1 ; A   1 ; A  0  ; A  1 1 1 0   1   5 1   5 0  5 1 5 0  Phương án: Mỗi véctơ x  ( x1, x2 ,..., xn ) thoả mãn mọi ràng buộc của bài toán gọi là một phương án (viết tắt PA). Phương án tối ưu: Phương án x  ( x1, x2 ,..., xn ) mà tại đó hàm mục tiêu đạt cực tiểu (hoặc cực đại) gọi là phương án tối ưu(viết tắt PATU). Phương án x1 được gọi là “tốt hơn” phương án x 2 nếu f ( x1 )  f ( x 2 ) đối với bài toán min; hoặc f ( x1 )  f ( x 2 ) đối với bài toán max. Ràng buộc chặt: Phương án x nếu thoả mãn ràng buộc thứ i với dấu n “bằng”, nghĩa là:  aij x j  bi (ràng buộc dấu xi  0 ) thì ta nói phương án x j 1 thoả mãn ràng buộc chặt thứ i . Ràng buộc lỏng: Phương án x nếu thoả mãn ràng buộc thứ i với dấu n “không bằng”, nghĩa là: ràng buộc dấu xi (, )0 ,  aij x j (, )bi thì ta nói j 1 phương án x thoả mãn ràng buộc lỏng thứ i . Ví dụ 1.5. Cho bài toán quy hoạch tuyến tính f ( x)  2 x1  6 x2  8 x3  5 x4   min  x1  2 x2  3x3  x4  8 (1) 2 x  x  x  5 x  2 (2)  1 2 3 4 4 x  7 x  8 x  2 x  20 (3)  1 2 3 4  x  0 , j  1, 4 (4)  j 12 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
và véctơ x 0  (8,0,0,0) . Ta thấy véc tơ x 0 thỏa mãn mọi ràng buộc của bài toán nên nó là phương án của bài toán. Hơn nữa nó thỏa mãn chặt ràng buộc (1) và 3 ràng buộc dấu x 2  x 3  x 4  0 , thỏa mãn lỏng ràng buộc (2), (3) và ràng buộc dấu x1 . Ví dụ 1.6. Cho bài toán quy hoạch tuyến tính f ( x)  2 x1  3x2  x3  x4  min  1  x1  x2  x3  2 x4  10  ( P1 )  x2  4 x3  8 x4  8  2 x2  2 x3  3x4  28   x j  0 ; j  1, 4 và các vecto x1  (10, 0, 0, 0); x  (0, 0,10, 0) . Các vecto x1 , x 2 có phải là các 2 phương án của bài toán không? Phương án nào tốt hơn? Kiểm tra các ràng buộc của bài toán. Bài toán quy hoạch tuyến tính (viết tắt BTQHTT) có ít nhất một phương án tối ưu gọi là BTQHTT giải được. Bài toán không có phương án tối ưu gọi là bài toán không giải được. Có hai khả năng của bài toán không giải được: (i) Bài toán không có phương án. (ii) Bài toán có phương án nhưng hàm mục tiêu không bị chặn dưới đối với bài toán min tức là f ( x)   , hoặc không bị chặn trên đối với bài toán max tức là f ( x)   trên tập phương án. Giải bài toán quy hoạch tuyến tính là đi tìm phương án tối ưu của bài toán hoặc kết luận bài toán không giải được. Phương án cực biên: Một phương án thoả mãn n ràng buộc chặt độc lập tuyến tính gọi là phương án cực biên (n là số biến của bài toán). Phương án cực biên thoả mãn đúng n ràng buộc chặt gọi là phương án cực biên không suy biến, thoả mãn chặt nhiều hơn n ràng buộc gọi là phương án cực biên suy biến. Chú ý: Ta có thể chuyển bài toán QHTT max về bài toán QHTT min giữ nguyên các điều kiện ràng buộc (1.2) và (1.3) theo quy tắc sau: n n f ( x)   c j x j  max  g ( x)   f ( x)   (c j ) x j  min j 1 j 1 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 13
Ví dụ 1.7. Trong Ví dụ 1. 5, phương án x 0  4 thoả mãn 4 ràng buộc chặt. Hãy kiểm tra xem 4 ràng buộc này có độc lập tuyến tính không? Thật vậy, xét hệ véctơ A  (1, 2, 3,1), (0,1, 0, 0), (0, 0,1, 0), (0, 0, 0,1) , ta có: 1 2 3 1 0 1 0 0 det A  1 0 0 0 1 0 0 0 0 1 Do đó hệ 4 véctơ trên độc lập tuyến tính nên 4 ràng buộc chặt này độc lập tuyến tính. Vậy x 0 là phương án cực biên và là phương án cực biên không suy biến. Ví dụ 1.8. Chứng tỏ x 0  (0, 2,3,1, 0, 0) không là phương án cực biên của bài toán sau f ( x)  x1  x2  6 x3  5 x4  3x5  2 x6  min  x1  x2  x4  3x5  3 (1)  x2  2 x3  x4  2 x5  2 x6  5 (2)   x  2 x  x  3x  x  3x  10 (3)  1 2 3 4 5 6  x  0 , j  2, 6 (4)  j Thật vậy, ta thấy véctơ x 0 thỏa mãn mọi ràng buộc của bài toán nên nó là phương án. Mặt khác x0  6 lại chỉ thỏa mãn chặt 5 ràng buộc (gồm 3 chặt ràng buộc hàm và 2 chặt ràng buộc dấu x5  0, x6  0 ) nên x 0 không là phương án cực biên. 2. Bài toán quy hoạch tuyến tính dạng chính tắc Bài toán quy hoạch tuyến tính dạng chính tắc có dạng như sau: Tìm vectơ x  ( x1, x2 ,..., xn )  n Để hàm số f ( x)  c1 x1  c2 x2   cn xn  min(max) (1.1)  a11 x1  a12 x2  ...a1n xn  b1  a x  a x  ...a x  b  21 1 22 2 2n n 2 Thỏa mãn  .... (1.2)  a x  a x  ...a x  b  m1 1 m2 2 mn n m  x j  0, j  1...n  (1.3) Hoặc dạng ma trận như sau: 14 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
n f ( x)   c j x j  min(max) j 1  n  aij x j  bi , i  1,..., m  j 1  x  0 , j  1,..., n  j Bài toán quy hoạch tuyến tính dạng chính tắc là bài toán mà mọi ràng buộc hàm đều là phương trình và mọi ràng buộc dấu đều không âm. Ví dụ 1.9. Cho bài toán quy hoạch tuyến tính dạng chính tắc f ( x)  2 x1  3x2  x3  x4  min  1  x1  x2  x3  2 x4  10   ( P1 )  x2  4 x3  8 x4  x5 8  2 x2  2 x3  3 x4  x6  28   x j  0 ; j  1, 6  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 giá trị tối ưu của hàm mục tiêu của hai bài toán là bằng nhau, và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia. Ta có quy tắc chuyển đổi giữa các bài toán được phát biểu dưới đây. 2.1. Quy tắc chuyển bài toán quy hoạch tuyến tính về dạng chính tắc Nếu ràng buộc dấu x j  0 . Đặt x j   xj .  x  x  x Nếu ràng buộc dấu x j mang dấu tuỳ ý, ta đặt:  j j j x  j   0 , x  j  0 Nếu ràng buộc hàm có dấu "  " hoặc "  " , ta thêm các biến phụ xn i (hệ số cn i của các biến phụ trong hàm mục tiêu bằng 0) theo quy tắc:  n n  aij x j  xn i  bi  aij x j  bi   j 1 j 1 x  0  n i  n n  aij x j  xn i  bi  aij x j  bi   j 1 j 1 x  0  n i Ví dụ 1.10. Đưa bài toán sau về dạng chính tắc HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 15
f ( x)  2 x1  3x2  x3  x4  min  1  x1  x2  x3  2 x4  10   ( P1 )  x2  4 x3  8 x4  8  2 x2  2 x3  3 x4  28   x j  0 ; j  1, 4  Lời giải: Mọi ràng buộc dấu đều không âm, có 2 ràng buộc hàm chưa phải là phương trình. Do đó, thêm hai biến phụ x5 , x6 ta được bài toán dạng chính tắc f ( x)  2 x1  3x2  x3  x4  min  1  x1  x2  x3  2 x4  10  ( P1 )  x2  4 x3  8 x4  x5 8  2 x2  2 x3  3x4  x6  28   x j  0 ; j  1, 6 Ví dụ 1.11. Đưa bài toán sau về bài toán min, dạng chính tắc f ( x)  x1  x2  x3  x4  max  x1  2 x2  5 x3  3 x4  7  ( P)  x1  x2  2 x3  1  x  0 , j  1, 2,3.  j Lời giải: Do x4 chưa có ràng buộc về dấu nên ta đặt x4  t4  t5 , lại do 2 ràng buộc hàm chưa là phương trình nên thêm hai biến phụ t6 , t7 ; đồng thời đặt x1  t1 , x2  t2 , x3  t3 và đổi dấu hàm mục tiêu. Ta có bài toán min, dạng chính tắc như sau F (t )  t1  t2  t3  t4  t5  min  t1  2t2  5t3  3t4  3t5  t6  7  ( P1 ) t1  t2  2t3  t 7  1  t  0 , j  1  7.  j 2.2. Phương án cực biên của bài toán QHTT dạng chính tắc Định lí 1.1. Phương án x 0  ( x1 , x2 ,..., x j ,..., xn ) của bài toán quy hoạch tuyến tính dạng chính tắc là phương án cực biên khi và chỉ khi hệ các véctơ cột ứng với các thành phần dương của x 0 độc lập tuyến tính. 16 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
Từ định lí trên, để phương án x 0  ( x1 , x2 ,..., x j ,..., xn ) là phương án cực biên của bài toán QHTT là hệ véctơ cột H ( x 0 )   A j | x j  0 độc lập tuyến tính. Ví dụ 1.12. Cho bài toán quy hoạch tuyến tính có hệ ràng buộc  3 x1  x2  2 x3 5  2 x  x  3x 5  1 2 3  2 x1  x3  2 x4  9  x j  0, j  1, 2,3, 4. Phương án x 0  (1, 0,1,3) có là phương án cực biên của bài toán? Lời giải: Phương án x 0 có các thành phần x1 , x3 , x4 dương. Ứng với các thành phần dương của x 0 , xét hệ véctơ:  A , A , A   (3, 2, 2) , (2,3,1) , (0, 0, 2)  , hệ véctơ này độc lập tuyến tính. 1 3 4 t t t Vậy x 0 là phương án cực biên. 2.3. Cơ sở của phương án cực biên của bài toán dạng chính tắc Giả sử x  ( x1 , x2 ,..., xn ) là phương án cực biên của bài toán dạng chính tắc. Ta gọi hệ m  r ( A) véctơ J  A j | x j  0 độc lập tuyến tính là cơ sở của phương án cực biên x ( m là hạng của ma trận A). Nếu x là phương án cực biên không suy biến thì nó có đúng m thành phần x j dương, J   A j | x j  0 là cơ sở duy nhất . Nếu x là phương án cực biên suy biến thì hệ véctơ  A j | x j  0 giả sử có k thành phần dương (k  m) , ta bổ sung thêm (m  k ) véctơ cột khác của A để được một hệ gồm m véctơ độc lập tuyến tính và gọi hệ m véctơ này là cơ sở của phương án cực biên x . Kí hiệu cơ sở của phương án cực biên x là: J   A j : A j nằm trong cơ sở  . Với phương án cực biên x , ta gọi các thành phần x j , j  J là thành phần cơ sở; còn xk  0 với k  J là thành phần phi cơ sở. HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 17
Ví dụ 1.13. Tìm phương án cực biên ứng với cơ sở  A2 , A3 , A4  của bài toán có hệ ràng buộc:  3 x1  x2  x3  33 x x  x4  5  1 2 5 x  8 x  x5  9  1 2  x j  0, j  1,5.  Lời giải: Gọi x  ( x1 , x2 , x3 , x4 , x5 ) là phương án cực biên ứng với cơ sở 0  A , A , A  , thế thì 2 3 4 x1 , x5 sẽ là thành phần phi cơ sở nên x1  x5  0 . Thay vào hệ ràng buộc trên ta tính được x2  9 / 8, x3  255 / 8, x4  31/ 8 . Vậy phương án cực biên ứng với cơ sở A , A , A  2 3 4 là x 0  (0, 9 / 8, 255 / 8, 31/ 8, 0) . Nhận xét: Nếu phương án cực biên x không suy biến thì có một cơ sở duy nhất, đó chính là hệ m véctơ độc lập tuyến tính  A j | x j  0 . Nếu phương án cực biên x là suy biến thì có thể tìm được nhiều cơ sở khác nhau, tuỳ thuộc vào cách bổ xung (m  k ) véctơ cột của A để được một hệ gồm m véctơ độc lập tuyến tính. 3. Bài toán quy hoạch tuyến tính dạng chuẩn Bài toán quy hoạch tuyến tính dạng chuẩn có dạng: Tìm vectơ x  ( x1, x2 ,..., xn )  n f ( x)  c1 x1  c2 x2   cn xn  min(max)  x1 + +a1 m +1x m+1 + +a1n x n = b1   x2 + +a 2 m +1x m+1 + +a 2n x n = b 2    x m +a m m 1x m+1 + +a mn x n = b m   x  0 , j  1, n  j Và bi  0 , i  1,..., m . 18 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng
1 0 0 a1m1 a1n    0 1 0 Ở đó ma trận hệ số: A   a2 m1 a2 n      0 0 1 am m1 amn  Bài toán quy hoạch tuyến tính dạng chuẩn là bài toán thoả mãn ba điều kiện: Là bài toán dạng chính tắc; vế phải hệ ràng buộc hàm không âm; ma trận hệ số A chứa một ma trận đơn vị cấp m . Bài toán QHTT dạng chuẩn luôn có một phương án cực biên : x 0  (b1 , b2 ,..., bm , 0,..., 0) với cơ sở J   A1 , A2 ,..., Am  . Ví dụ 1.14. Cho bài toán quy hoạch tuyến tính dạng chuẩn f ( x)  3 x1  x2  3x3  x4  min  3 x1  4 x2  3 x3  x4  x5  12 x  x  x3  x6 5  1 2 5 x  x  5 x  x7  6  1 2 3  x j  0 , j  1, 7  Có phương án cực biên x 0  (0, 0, 0,12, 0,5, 6) với cơ sở J=  A4 , A6 , A7  . 4. Tính chất cơ bản của bài toán quy hoạch tuyến tính Tính chất 1. Nếu bài toán quy hoạch tuyến tính có phương án và hạng của ma trận hệ ràng buộc bằng n biến số thì bài toán có phương án cực biên. Tính chất 2. Nếu bài toán quy hoạch tuyến tính có tập phương án khác rỗng và hàm mục tiêu bị chặn (bị chặn dưới đối với bài toán min, bị chặn trên đối với bài toán max) trên tập phương án thì bài toán có phương án tối ưu. Tính chất 3. Số phương án cực biên của bài toán quy hoạch tuyến tính là hữu hạn. Ví dụ 1.14a. Cho BTQHTT f ( x)  3 x1  x2  3x3  x4  min  3 x1  4 x2  3x3  x4  12 x x  x3 5  1 2 5 x  x  5 x 6  1 2 3  x j  0 , j  1, 4  Ta thấy mọi ràng buộc dấu đều không âm, có ba ràng buộc hàm chưa là phương trình, thêm các biến phụ x5 , x6 , x7 vào các ràng buộc này ta được bài toán: HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng 19
f ( x)  3 x1  x2  3 x3  x4  min  3 x1  4 x2  3 x3  x4  x5  12 x  x  x3  x6 5  1 2 5 x  x  5 x  x7  6  1 2 3  x j  0 , j  1, 7  Đó là bài toán dạng chuẩn, có phương án cực biên x 0  (0, 0, 0,12, 0,5, 6) với cơ sở  A4 , A6 , A7  . Tuy nhiên, bài toán có hàm mục tiêu giảm vô hạn trên tập phương án. Do đó bài toán không giải được. Chúng ta sẽ giải quyết ở bài học sau. Ví dụ 1.14b. Bài toán QHTT f ( x)  5 x1  4 x2  5 x3  2 x4  x5  3x6  min  2 x1  4 x2  3x3  x4  152  4 x  2 x  3x  x5  60  1 2 3  3x  x3  x6  36  1  x j  0 , j  1,6  Có tập phương án tối ưu của bài toán là: 1 2 x*  x1   z 6  (12  t , 6  t , 0,104  2t , 0, t ), 0  t  36 . 3 3 BÀI TẬP 1.3. Chuyển bài toán quy hoạch tuyến tính sau về dạng chính tắc. f ( x)  3x1  2 x2  3x3  15 x4  min f ( x)  x1  x2  x3  x4  min  x1  x3  3x4  7  x1  x2  x4  1 a.  x2  2 x3  2 x4  1 b.   x1  x2   x4  1  x3  x4  16    x2  x3 1  x j  0 , j  1, 4  x1  0, x2  0  f ( x)  x1  x2  x3  min f ( x)  7 x1  x2  4 x3  min  2 x1  x2  x3  2 6 x1  4 x2  5 x3  20 c.  4 x1  x2  2 x3  1 d.  x1  2 x2  x3  8  x  2x  4x  4  3x  2 x  x  8  1 2 3  1 2 3  x j  0 , j  1,3  x j  0 , j  1,3   20 HAUI – Khoa Khoa học cơ bản – Bài giảng Mô hình toán kinh tế – Lại Đức Hùng