intTypePromotion=3
Array
(
    [0] => Array
        (
            [banner_id] => 140
            [banner_name] => KM1 - nhân đôi thời gian
            [banner_picture] => 964_1568020473.jpg
            [banner_picture2] => 839_1568020473.jpg
            [banner_picture3] => 620_1568020473.jpg
            [banner_picture4] => 994_1568779877.jpg
            [banner_picture5] => 
            [banner_type] => 8
            [banner_link] => https://tailieu.vn/nang-cap-tai-khoan-vip.html
            [banner_status] => 1
            [banner_priority] => 0
            [banner_lastmodify] => 2019-09-18 11:11:47
            [banner_startdate] => 2019-09-11 00:00:00
            [banner_enddate] => 2019-09-11 23:59:59
            [banner_isauto_active] => 0
            [banner_timeautoactive] => 
            [user_username] => sonpham
        )

)

Bài giảng Toán kinh tế - Đỗ Thị Vân Dung

Chia sẻ: Hồ Ky | Ngày: | Loại File: PDF | Số trang:61

0
334
lượt xem
78
download

Bài giảng Toán kinh tế - Đỗ Thị Vân Dung

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

Tập bài giảng này sẽ trang một số kỹ năng cơ bản về mô hình hóa toán kinh tế và ứng dụng vào giải các bài toán kinh tế. Tập bài giảng gồm 4 chương: chương 1 bài toán quy hoạch tuyến tính, chương 2 phương pháp đơn hình, chương 3 bài toán đối ngẫu, chương 4 bài toán vận tải. Mời các bạn cùng tham khảo và vận dụng kiến thức trong tập bài giảng này thật tốt trong việc học môn Toán kinh tế.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Toán kinh tế - Đỗ Thị Vân Dung

  1. LỜI NÓI ĐẦU Sự tồn tại và vận động của các đối tượng trong quá trình phát triển kinh tế - xã hội là hết sức phức tạp và đa dạng. Người ta có thể sử dụng nhiều phương pháp tiếp cận khác nhau để nghiên cứu, phân tích lý giải sự tồn tại và vận động này, từ đó tìm cách tác động đến các đối tượng và quá trình kinh tế nhằm mang lại lợ ích ngày càng lớn cho chính bản thân xã hội loài người. Mỗi cách tiếp cận trong những điều kiện cụ thể có những ưu, nhược điểm riêng. Phương pháp mô hình toán kinh tế là một trong những phương pháp được xem là hiệu quả nhất trong nghiên cứu kinh tế - xã hội hiện nay. Đây là phương pháp khai thác công cụ mạnh của toán học, kỹ thuật tinh toán, nhờ đó mà phương pháp mô hình toán kinh tế cho phép giải quyết các bài toán với kích cỡ không hạn chế với độ phức tạp mong muốn. Trong khuôn khổ môn học “ Toán kinh tế” dành cho chuyên ngành quản trị kinh doanh bậc cao đẳng với thời lượng 2 tín chỉ, tập bài giảng này sẽ trang một số kỹ năng cơ bản về mô hình hóa toán kinh tế và ứng dụng vào giải các bài toán kinh tế. Do hạn chế về thời lượng giảng dạy, tập bài giảng này không thể đề cập sâu và chi tiết, cũng như không đề cập đến nhiều nội dung khác thuộc lĩnh vực mô hình Toán kinh tế. Các nội dung này người đọc có thể tìm đọc ở các tài liệu tham khảo đã liệt kê. Tập bài giảng gồm 4 chương: Chương I: Bài toán quy hoạch tuyến tính Chương II: Phương pháp đơn hình Chương III: Bài toán đối ngẫu Chương IV: Bài toán vận tải. Mặc dù tập bài giảng đã kế thừa nhiều tài liệu tôi cho rằng tập bài giảng vẫn không thể tránh được những hạn chế nhất định. Tôi mong nhận được sự quan tâm của các đồng nghiệp cũng như của tất cả bạn đọc nhằm tạo điều kiện cho tập bài giảng ngày càng hoàn thiện hơn. Chủ biên: CN Đỗ Thị Vân Dung 1
  2. MỤC LỤC 2
  3. Nội dung Trang LỜI NÓI ĐẦU…………………………………………………………………....... 1 MỤC LỤC…………………………………………………………………………. 2 Chương 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH………………………………. 4 1.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTT……………………………………………. 4 1.1.1. Lập kế hoạch sản xuất……………………………………………………… 4 1.1.2. Bài toán vận tải. ……………………………………………………………. 5 1.1.3. Bài toán phân công lao động……………………………………………….. 6 1.2. PHÂN LOẠI DẠNG BÀI TOÁN QHTT. ……………………………………… 7 1.2.1. Dạng tổng quát của bài toán QHTT. ……………………………………... 7 1.2.2. Dạng chính tắc của bài toán QHTT……………………………………….. 7 1.2.3 Dạng chuẩn của bài toán QHTT…………………………………………… 8 1.3. BIẾN ĐỔI DẠNG BÀI QHTT………………………………………………...... 9 1.3.1. Chuyển bài toán dạng tổng quát sang bài toán dạng chính tắc………… 9 1.3.2. Chuyển bài toán dạng chính tắc sang bài toán dạng chuẩn……………... 10 1.3.3. Quan hệ giữa bài toán xuất phát và bài toán mở rộng…………………………. 13 BÀI TẬP CHƯƠNG 1…………………………………………………………………….. 14 1. Lập bài toán QHTT…………………………………………………………….. 14 2. Chuyển bài toán về dạng chính tắc……………………………………………. 16 Chương 2: PHƯƠNG PHÁP ĐƠN HÌNH 18 2.1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QHTT DẠNG CHUẨN……….. 18 2.1.1. Thuật toán giải bài toán min………………………………………………. 18 2.1.2. Thuật toán giải bài toán max………………………………………………. 24 2.2. PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG GIẢI BÀI TOÁN QHTT DẠNG 28 CHÍNH TẮC…………………………………………………………………………….. 2.2.1. Phương pháp giải bài toán QHTT dạng chính tắc……………………….. 28 2.2.2. So sánh các đại lượng trong bài toán QHTT dạng chính tắc……………. 28 BÀI TẬP CHƯƠNG 2…………………………………………………………………….. 35 Chương 3: BÀI TOÁN ĐỐI NGẪU…………………………………………………….. 41 3.1. ĐỊNH NGHĨA BÀI TOÁN ĐỐI NGẪU…………………………………………….. 41 3.1.1. Định nghĩa bài toán đối ngẫu….……………………………………………….. 41 3.1.2. Cách xây dựng một bài toán đối ngẫu. ………………………………………. 41 3.2. QUAN HỆ GIỮA BÀI TOÁN GỐC VÀ BÀI TOÁN ĐỐI NGẪU………………... 42 3.2.1. Cặp ràng buộc bài toán đối ngẫu.…………………………………………….. 42 3
  4. 3.2.2. Mối liên hệ giữa PATU của bài toán gốc và bài toán đối ngẫu…………… 44 3.3. GIẢI BÀI TOÁN GỐC VÀ BÀI TOÁN ĐỐI NGẪU. ……………………………. 44 3.3.1. Giải bài toán đối ngẫu theo phương pháp đơn hình. ……………………… 44 3.3.2. Giải bài toán đối ngẫu dựa vào quan hệ với bài toán gốc. ……………… 45 3.3.3. Giải bài toán gốc dựa vào quan hệ với bài toán đối ngẫu. ……………… 45 BÀI TẬP CHƯƠNG 3…………………………………………………………………….. 48 Chương 4: BÀI TOÁN VẬN TẢI………………………………………………………… 53 4.1. Nội dung và đặc điểm của bài toán.………………………………………… 53 4.1.1. Nội dung bài toán.……………………………………………………………... 53 4.1.2. Tính chất chung của bài toán.……………………………………………… 54 4.2. Phương pháp thế vị để giải bài toán. ………………………………………. 54 4.2.1. Phương pháp tìm phương án cực biên xuất phát. ……………………. 54 4.2.2. Phương pháp thế vị giải bài toán vận tải. ………………………………. 55 BÀI TẬP CHƯƠNG 4…………………………………………………………………….. 59 Chương 1 4
  5. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH Mục tiêu: Sau khi đọc xong chương này học sinh sẽ: - Hiểu được các dạng của bài toán quy hoạch tuyến tính. - Hiểu được cách biến đổi các dạng của bài toán quy hoạch tuyến tính. - Hiểu được mối quan hệ giữa bài toán xuất phát và bài toán mở rộng. - Vận dụng để xây dựng bài toán QHTT và biến đổi các dạng bài toán quy hoạch tuyến tính về dạng chính tắc. 1.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTT 1.1.1. Lập kế hoạch sản xuất Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, đậu cho một bánh mỗi loại; lượng dự trữ nguyên liệu; tiền lãi cho một bánh mỗi loại được cho trong bảng sau: Nguyên Bánh đậu Bánh thập Lượng dự Bánh dẻo liệu xanh cẩm trữ Đường 0,04 kg 0,06 kg 0,05 kg 500 kg Đậu 0,07 kg 0 kg 0,02 kg 300 kg Lãi 3 ngàn 2 ngàn 2,5 ngàn Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần sản xuất sao cho không bị động về nguyên liệu mà lãi đạt được cao nhất. Giải. Gọi x1, x2, x3 lần lượt là số bánh đậu xanh, bánh thập cẩm và bánh dẻo cần sản xuất. Điều kiện: xj ≥ (j = 1,2,3). Khi đó 1. Tiền lãi thu được là: f(x) = f(x1, x2, x3) = 3x1 + 2x2 + 2,5x3 (ngàn). 2. Lượng đường được sử dụng là: 0,04x1 + 0,06x2 + 0,05x3 (kg). Ta phải có 0,04x1 + 0,06x2 + 0,05x3 ≤ 500. 3. Lượng đậu được sử dụng là: 0,07x1 + 0,02x3 ≤ 300. Vậy ta có mô hình bài toán: (1) f(x) = f(x1, x2, x3) = 3x1 + 2x2 + 2,5x3 max. Với điều kiện: (2)  0 , 0 4 x1  0 , 0 6 x 2  0 , 0 5 x 3  5 0 0 ; 0 , 0 7 x1  0 , 0 2 x 3  3 0 0 (3) xj ≥ 0 (j = 1, 2, 3) Ta nói đây là một bài toán qui hoạch tuyến tính 3 ẩn tìm max của hàm mục tiêu f(x) = 3x1 + 2x2 + 2,5x3. 1.1.2. Bài toán vận tải 5
  6. Ta cần vận chuyển vật liệu xây dựng từ hai kho K1 và K2 đến ba công trường xây dựng C1, C2, C3. Tổng số vật liệu có ở mỗi kho, tổng số vật liệu yêu cầu ở mỗi công trường, cũng như khoảng cách từ mỗi kho đến mỗi công trường được cho trong bảng sau: Cự ly CT C1 15T C2 25T C3 20T kho K1: 20T 5km 2km 3km x11 x12 x13 K2: 40T 4km 3km 1km x21 x22 x23 Hãy lập kế hoạch vận chuyển sao cho: - Các kho giải phóng hết hàng; - Các công trường nhận đủ vật liệu cần thiết; - Tổng số T(tấn) x km phải thực hiện là nhỏ nhất. Giải. Gọi xij là số tấn vật liệu sẽ vận chuyển từ kho Kj đến công trường Cj. Điều kiện: xij ≥ 0 (i = 1,2; j = 1, 2, 3). Khi đó: 1. Tổng số T x km phải thực hiện là: f(x) = 5x11 + 2x12 + 3x13 + 4x21 + 3x22 + x23. 2. Tổng số tấn vật liệu được vận chuyển từ kho K1 đến các công trường là x11 + x12 + x13. Để giải phóng hết vật liệu, ta phải có x11 + x12 + x13 = 20. 3. Tổng số tấn vật liệu được vận chuyển từ kho K2 đến các công trường là x21 + x22 + x23. Để giải phóng hết vật liệu, ta phải có x21 + x22 + x23 = 40. 4. Tổng số tấn vật liệu được vận chuyển về công trường C1 là x12 + x21. Để C2 nhận đủ vật liệu, ta phải có x11 + x21 = 15. 5. Tổng số tấn vật liệu được vận chuyển về công trường C2 là x12 + x22. Để C2 nhận đủ vật liệu, ta phải có x12 + x22 = 25. 6. Tổng số tấn vật liệu được vận chuyển về công trường C3 là x13 + x23. Để C3 nhận đủ vật liệu, ta phải có x13 + x23 = 20. Vậy ta có mô hình bài toán: (1) f(x) = 5x11 + 2x12 + 3x13 + 4x21 + 3x22 + x23 min Với điều kiện: 6
  7.  x11  x12  x13  20;  x  x  x  40;  21  22 23 (2)  x11  x 21  15;  x  x  25;  12 22  x13  x 23  20.  (3) xij  0 (i = 1, 2; j = 1, 2, 3). Ta nói đây là một bài toán qui hoạch tuyến tính 6 ẩn tìm min của hàm mục tiêu f(x) = 5x11 + 2x12 + 3x13 + 4x21 + 3x22 + x23. 1.1.3. 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. 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 A(10) B(20) C(12) 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 i (j = 1,2; xij 0, nguyên ). Khi đó, năng suất lao động của công việc đào đất sẽ là: 6x11 + 5x12 + 4x13; Còn chuyển đất sẽ là: 4x21 + 3x22 + 2x23; 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: 6x11 + 5x12 + 4x13  max;  6 x11  5 x12  4 x13  4 x 21  3 x 22  2 x 23  0   x  x 21  10; Với điều kiện  11  x12  x 22  20;  x13  x 23  12;  1.2. PHÂN LOẠI DẠNG BÀI TOÁN QHTT 1.2.1. Dạng tổng quát của bài toán QHTT n (1) f ( x )  c j 1 j x j  m in ( m a x ) 7
  8.  n   a ij x j  bi , (i  I1 );  j 1  n  ( 2 )   a ij x j  bi , (i  I 2 );  j 1  n   a ij x j  bi , (i  I 3 );  j 1  (3) xj  0 (j  J1); xj ≤ 0 (j  J2); xj tuỳ ý (j  J3); Trong đó - f(x) là hàm mục tiêu; - I1, I2, I3 rời nhau và I1  I2  I3 = 1, 2,..., m  - J1, J2, J3 rời nhau và J1  J2  J3 = 1, 2, ..., n - A = (aij)mxn: Ma trận hệ số ràng buộc; - B = (b1, b2, ..., bm): Véctơ các hệ số tự do; - C = (c1, c2, ..., cm): Véctơ hệ số các ẩn trong hàm mục tiêu; - x = (x1, x2, ...., xn): Véctơ các ẩn số. Khi đó * Mỗi véctơ x = (x1, x2, ..., xn) thoả (2) và (3) được gọi là một phương án (PA) của bài toán. * Mỗi phương án x = (x1, x2, ..., xn) thoả (1), nghĩa là tại đó hàm mục tiêu đạt giá trị nhỏ nhất (lớn nhất) trên tập các phương án, được gọi là một phương án tối ưu (PATU) của bài toán. * Giải một bài toán QHTT là đi tìm một PATU của nó hoặc chỉ ra rằng bài toán vô nghiệm, nghĩa là không có PATU. 1.2.2. Dạng chính tắc của bài toán QHTT n (1) f ( x )   j 1 c j x j  m in ( m a x ) n ( 2 )  a ij x j  b i ( i  1, m ) j 1 (3) x j  0 ( j  1, n ) Nhận xét: Bài toán QHTT dạng chính tắc là bài toán dạng tổng quát, trong đó. - Các ràng buộc đều là phương trình; - Các ẩn đều không âm Ví dụ 1: Bài toán sau có dạng chính tắc: (1) f ( x)  2 x1  4 x2  x3  6 x4  min 8
  9.  x1  4 x 2  x 4  12;  (2) 12 x1  3 x 2  x3  x 4  3;  x  x  x  x   6.  1 2 3 4 (3 ) x j  0 ( j  1, n ) 1.2.3. Dạng chuẩn của bài toán QHTT n (1) f ( x )   j 1 c j x j  m in ( m a x ) n ( 2 )  a ij x j  b i ( i  1, m ) j 1 (3) x j  0 ( j  1, n ) Trong đó: - Các hệ số tự do b1, b2, ..., bm đều không âm. - Trong ma trận hệ số ràng buộc A = (aij) mxn có đầy đủ m véctơ cột đơn vị e1, e2, ..., em: 1  0 0       0 1  0 e   .  ; e2   0  ;...; em   .        .  .  0 0 0 1        Khi đó. *Các ẩn ứng với các véctơ cột đơn vị được gọi là các ẩn cơ bản. Cụ thể ẩn ứng với véctơ cột đơn vị ek là ẩn cơ bản thứ k. *Một phương án mà các ẩn không cơ bản đều bằng 0 được gọi là một phương án cơ bản. *Một phương án cơ bản có đủ m thành phần dương (nghĩa là mọi ẩn cơ bản đều dương) đượi gọi là không suy biến. Ngược lại, một phương án cơ bản có ít hơn m thành phần dương (nghĩa là có ít nhất một ẩn cơ bản bằng 0) được gọi là suy biến. Ví dụ 2: Xét bài toán QHTT sau: (1) f ( x)  2 x1  4 x2  x3  6 x4  x5  4 x6  min  x1  x4  x5  12;  (2) 12 x1  x3  x6  3;  x  x  x  x  6.  1 2 3 4 ( 3 ) x  0 ( j  1, 6 ) . Ta thấy bài toán trên đã có dạng chính tắc, hơn nữa. - Các hệ số tự do b1 = 12, b2 = 3, b3 = 6 đều không âm. - Ma trận hệ số ràng buộc A là:  1 0 0 1 1 0 A   12 0 1 0 0 1     1 1 1 1 0 0    Có chứa đầy đủ 3 véctơ cột đơn vị e1 (cột 5), e2 (cột 6), e3 (cột 2). Do đó bài toán có dạng chuẩn, trong đó 9
  10. *Ẩn cơ bản thứ 1 là x5. *Ẩn cơ bản thứ 2 là x6. *Ẩn cơ bản thứ 3 là x2. Nhận xét: Trong bài toán trên, khi cho ẩn cơ bản thứ k = hệ số tự do thứ k, còn các ẩn không cơ bản = 0, nghĩa là. x5 = 12; x6 = 3; x2 = 6; x1 = 0; x3 = 0; x4 = 0; Ta được một phương án cơ bản của bài toán: x = (0, 6, 0, 0, 12, 3). Phương án này không suy biến vì có đủ 3 thành phần dương. Ta gọi đây là phương án cơ bản ban đầu của bài toán. Chú ý: Tổng quát, trong bài toán QHTT dạng chuẩn bất kỳ, khi cho ẩn cơ bản thứ k = hệ số tự do thứ k (k = 1, 2, ..., m), còn các ẩn không cơ bản = 0, ta được một phương án cơ bản của bài toán. Ta gọi đây là phương án cơ bản ban đầu của bài toán. 1.3. BIẾN ĐỔI DẠNG BÀI TOÁN QHTT 1.3.1. Chuyển bài toán dạng tổng quát sang bài toán dạng chính tắc Ta có thể biến đổi bài toán QHTT dạng tổng quát về dạng chính tắc như sau: 1. Khi gặp ràng buộc dạng. n  i 1 a ij x i  b j ta đưa vào ẩn phụ xn+i  0 để biến về phương trình. n  i1 a ij x j  x n i  bi 2. Khi gặp ràng buộc dạng. n i 1 a ij x i  b i ta đưa vào ẩn phụ xn+i 0 để biến về phương trình. n a i 1 ij x j  x n  i  bi 3. Khi gặp ẩn xj ≤ 0, ta đổi biến x j   x 'j với x 'j 0. ' 4. Khi gặp ẩn xj tuỳ ý, ta đổi biến xj = x j - x ''j với x 'j  0; x ''j  0. Chú ý: Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ, thì sẽ được PATU của bài toán dạng tổng quát đã cho. Ví dụ 1: Biến đổi bài toán QHTT sau về dạng chính tắc: 10
  11. f(x) = 3x1 + 2x2 + 2,5x3 max  4 x1  6 x2  5 x3  50  7 x1  x3  30  2 x  3 x  5 x  25  1 2 3 x1 ≥ 0; x2 ≤ 0 Giải: - Đưa vào ẩn phụ x4 ≥0 để biến bất phương trình 4x1 – 6x2 + 5x3 ≤ 50 về phương trình 4x1 – 6x2 + 5x3 + x4 = 50. - Đưa vào ẩn phụ x5 ≥ 0 để biến bất phương trình 7x1 + x3 ≥ 30 về phương trình 7x1 + x3 – x5 = 30. ' ' - Đổi biến x2   x2 với. x2  0 ' '' ' '' - Đổi biến x3  x3  x3 với x3  0; x3  0. Ta đưa bài toán về dạng chính tắc: (1) f ( x)  f ( x1 , x2 , x3 )  3x1  2 x2  2,5 x3 max ' ' " 4 x1  6 x2  5( x3  x3 )  x4  50;  ' " (2) 7 x1  ( x3  x3 )  x5  30;  ' ' " 2 x1  3x2  5( x3  x3 )  25. ' ' '' (3) x1  0; x2  0; x3  0; x3  0; x4  0; x5  0. Ví dụ 2: Đưa bài toán sau về dạng chính tắc. (1) f(x) = x1 – x2 – x3 min  x1  x2  x3  5  (2)  x1  2 x2  x3  3 x  x  x  0  1 2 3 (3) x1, x3 ≥ 0. 1.3.2.Chuyển bài toán dạng chính tắc sang bài toán dạng chuẩn Từ bài toán QHTT dạng chính tắc ta có thể xây dựng bài toán QHTT mở rộng có dạng chuẩn như sau: 1. Khi gặp hệ số tự do bi < 0 ta đổi dấu hai vế của ràng buộc thứ i. 2. Khi ma trận hệ số ràng buộc A không chứa véctơ cột đơn vị thứ k là ek, ta đưa vào ẩn giả xn+k  0 và cộng thêm ẩn giả xn+k vào vế trái của phương trình ràng buộc thứ k để được phương trình ràng buộc mới: 11
  12. n a j 1 kj x j  xn  k  bk 3. Hàm mục tiêu mở rộng f ( x) được xây dựng từ hàm mục tiêu f(x) ban đầu như sau: - Đối với bài toán min: f ( x)  f ( x )  M ( ẩn giả) - Đối với bài toán max: f ( x)  f ( x )  M ( ẩn giả) trong đó M là đại lượng dương rất lớn (lớn hơn bất kỳ số nào cho trước). Ví dụ 1: Biến đổi bài toán QHTT sau về dạng chuẩn: (1) f ( x)  f ( x1, x2 , x3 )  3x1  2x2  2x3  x4 min  4 x1  6 x 2  5 x3  50;  (2)  7 x1  x3  x 4  0;  2 x  3 x  5 x   25  1 2 3 (3) x j  0( j  1, ..., 4).. Giải: Bài toán trên đã có dạng chính tắc, trong đó vế phải của phương trình ràng buộc thứ ba là -25 < 0. Đổi dấu hai vế của phương trình này ta được: -2x1 – 3x2 + 5x3 =25. và (2) trở thành  4 x1  6 x2  5 x3  50; '  (2 ) 7 x1  x3  x4  0;  2 x  3 x  5 x  25  1 2 3 Ma trận hệ số ràng buộc là:  4 6 5 0 1 0   A 7 0 1 10 0  2 3 5 0 0 1   Vì A còn thiếu 2 véctơ cột đơn vị là e1 và e3 nên bài toán có dạng chuẩn. - Lập các ẩn giả x5  0, x6  0 và xây dựng bài toán mở rộng dạng chuẩn như sau: (1). f ( x )  3 x1  2 x2  2 x3  x4  Mx5  Mx6 min. 4 x1  6 x2  5 x3  x5  50;  (2) 7 x1  x3  x4  0; 2 x  3x  5 x  x  25.  1 2 3 6 12
  13. (3) xj  0 (j = 1,....,6). Nếu hàm mục tiêu chuyển sang max ta xây dựng bài toán mở rộng dạng chuẩn như sau: f ( x )  3 x1  2 x2  2 x3  x4  Mx5 - Mx6 max  4 x1  6 x2  5 x3  x5  50;   7 x1  x3  x4  0;   2 x  3 x  5 x  x  25.  1 2 3 6 xj  0 (j = 1, ..., 6). Ví dụ 2: Biến đổi bài toán QHTT sau về dạng chuẩn: (1) f(x) = f(x1, x2, x3) = 3x1 + 2x2 + 2x3 + x4 min 9 x2  15 x3  50;  (2) 6 x3  2 x4  120;  x  3 x  5 x  45.  1 2 3 (3) xj  0 (j = 1,....,4). Giải. Trước hết ta đưa bài toán về dạng chính tắc bằng cách đưa vào 2 ẩn phụ x5  0; x6  0: (1) f(x) = f(x1, x2, x3) = 3x1 + 2x2 + 2x3 + x4 min   9 x 2  15 x 3  x 5  50;  (2)   6 x 3  2 x 4   120;  x  3 x  5 x  x   45.  1 2 3 6 (3) xj  0 (j = 1,....,6). Bài toán trên chưa có dạng chuẩn. Ta thấy các vế phải của các phương trình ràng buộc thứ 2 và 3 đều âm nên bằng cách đổi dấu hai vế của các phương trình này ta được:   9 x 2  15 x 3  x 5  50;  (2)  6 x 3  2 x 4  120;   x  3 x  5 x  x  45.  1 2 3 6 Ma trận hệ số ràng buộc là:  0  9 15 0 1 0  0   A 0 0 6  2 0 0 1  1  3 5 0 0 1  0   Vì A còn thiếu 1 véctơ cột đơn vị là e2 nên bài toán chưa có dạng chuẩn. - Lập ẩn giả x7  0 và xây dựng bài toán mở rộng dạng chuẩn như sau: f ( x ) = 3x1 + 2x2 + 2x3 + x4 + Mx7 min 13
  14. 9 x2  15 x3  x5  50;  6 x3  2 x4  x7  120;  x  3 x  5 x  x  45.  1 2 3 6 xj  0 (j = 1,....,7). 1.3.3. Quan hệ giữa bài toán xuất phát và bài toán mở rộng. a. Quan hệ giữa bài toán QHTT dạng tổng quát và bài toán dạng chính tắc. - Sử dụng ẩn phụ. Ẩn phụ biến 1 bất phương trình thành 1 phương trình theo đúng logic toán học. - Các hệ số của ẩn phụ đều bằng 0 trong hàm mục tiêu. b. Quan hệ giữa bài toán QHTT dạng chính tắc và bài toán dạng chuẩn. - Sử dụng ẩn giả. Ẩn giả đưa vào một cách “giả tạo” cốt để ma trận có hệ số ràng buộc có chứa đủ véctơ cột đơn vị, nó chỉ được cộng hình thức vào vế trái của phương trình ràng buộc và tạo nên 1 phương trình ràng buộc mới. - Ẩn giả sẽ tạo ra hàm mục tiêu mở rộng, hệ số của các ẩn giả đều = M (đối với bài toán min), hoặc đều = -M (đối với bài toán max). c. Mối quan hệ giữa bài toán xuất phát (A) và bài toán mở rộng B như sau: (B) Vô nghiệm  (A) vô nghiệm Mọi ẩn giả = 0  Bỏ các ẩn giả, được PATU của (A). (B) Có nghiệm Có ít nhất một ẩn giả > 0  (A) không có phương án nào nên vô nghiệm TÀI LIỆU THAM KHẢO 1, TS. Phan Quốc Khánh, Th.s Trần Huệ Nương.Quy hoạch tuyến tính. NXB Giáo dục. 2000 2, Th.s Nguyễn Đình Tùng. Quy hoạch tuyến tính. NXB Giáo dục. 2000 3, TS. Lê Khánh Luận. Quy hoạch tuyến tính. NXB Lao Động.2006 4, Th.s Bùi Phúc Trung. Quy hoạch tuyến tính. NXB Lao Động - Xã hội. 2010 5, Giáo trình quy hoạch tuyến tính - Trường Đại học Quốc Gia Hà Nội. 6, Giáo trình quy hoạch tuyến tính - Trường Đại học Kinh tế Quốc Dân. 7, Giáo trình mô hình toán kinh tế - Trường Đại học kinh tế Quốc Dân. 8, Th.s Nguyễn Đức Phương - Bài giảng quy hoạch tuyến tính - Trường Đại học Công Nghiệp BÀI TẬP CHƯƠNG 1 1. Lập bài toán QHTT Bài 1: 14
  15. Xí nghiệp sản xuất giấy có 3 phân xưởng. Do trang bị kỹ thuật khác nhau nên mức hao phí tre gỗ, axít để sản xuất một tấn giấy thành phẩm cũng khác nhau. Mức hao phí được cho trong bảng dưới đây: Mức hao phí nguyên liệu cho một tấn giấy Nguyên liệu P. xưởng I P. xưởng II P. xưởng III Tre gỗ 1,4 tấn 1,3 1,2 Axít 0,1 0,12 0,15 Số lượng tre gỗ có trong năm là 1.500.000 tấn, Axit là 100.000 tấn. Hãy lập kế hoạch sản xuất sao cho tổng số giấy sản xuất trong năm của xí nghiệp là nhiều nhất? Bài 2: Một xí nghiệp có thể sản xuất bốn loại mặt hàng xuất khẩu H1, H2, H3, H4. Để sản xuất 4 loại mặt hàng này, xí nghiệp sử dụng hai loại nguyên liệu N1, N2. Số nguyên liệu tối đa mà xí nghiệp huy động được tương ứng là 600kg và 800kg. Mức tiêu hao mỗi loại nguyên liệu để sản xuất một mặt hàng và lợi nhuận thu được cho trong bảng sau: Định mức tiêu hao nguyên liệu và lợi nhuận H1 H2 H3 H4 N1 0,5 0,2 0,3 0,4 N2 0,1 0,4 0,2 0,5 Lợi nhuận 0,8 0,3 0,5 0,4 Lập mô hình sao cho xí nghiệp sản xuất đạt lợi nhuận cao nhất? Bài 3: Một cơ sở dự định sản xuất tối đã trong một ngày 500 ổ bánh mì dài và 500 ổ bánh mì tròn, muốn đạt lợi nhuận nhiều nhất, với những điều kiện như sau: - Giá bán một ổ bánh mì dài làm từ 400g bột là 325 đồng, một ổ bánh mì tròn làm từ 250g bột là 220 đồng. - Số lượng bột được cung cấp tối đa trong ngày là 225kg với giá mỗi kg là 300 đồng. - Lò nướng bánh cho phép nướng 75 ổ bánh mì dài hay 100 ổ bánh mì tròn trong một giờ nhưng không thể nướng hai loại cùng một lúc. Lò nướng hoạt động tối đa 8 giờ trong một ngày. Hãy lập mô hình cho bài toán nêu trên? Bài 4: Ba xí nghiệp A, B, C cùng có thể sản xuất áo vét và quần. Khả năng sản xuất của mỗi xí nghiệp như sau: Khi đầu tư 1000 USD vào xí nghiệp A thì thu được 35 áo vét và 45 15
  16. quần; vào xí nghiệp B thì thu được 40 áo vét và 42 quần; vào xí nghiệp C thì thu được 43 áo vét và 30 quần. Lượng vải và giờ công sản xuất được cho trong bảng sau: A B C Xí nghiệp Vải/ giờ Vải/ giờ Vải/ giờ 1 áo vét 3,5m 20 giờ 4m 16 giờ 3,8m 18 giờ 1 quần 2,8m 10 giờ 2,6m 12 giờ 2,5m 15 giờ Tổng số vải huy động được là 1.000m. Tổng số giờ công huy động được là 52.000 giờ. Theo hợp đồng thì tối thiểu phải có 1.500 bộ quần áo, nếulẻ bộ thì quần là dễ bán. Hãy lập kế hoạch đầu tư vào mỗi xí nghiệp bao nhiêu vốn để: - Hoàn thành hợp đồng. - Không khó khăn về tiêu thụ. - Không bị động về vải và giờ công. - Tổng số vốn đầu tư là nhỏ nhất. Bài 5: Một nhà máy cán thép có thể sản xuất hai loại sản phẩm: thép tấm và thép cuộn. Nếu chỉ sản xuất một loại sản phẩm thì nhà máy chỉ có thể sản xuất 200 tấn thép tấm hoặc 140 tấn thép cuộn trong một giờ. Lợi nhuận thu được khi bán một tấn thép tấm là 25USD, một tấn thép cuộn là 30USD. Nhà máy làm việc 40 giờ trong một tuần và thị trường tiêu thụ tối đa là 6.000 tấn thép tấm và 4.000 tấn thép cuộn. Nhà máy cần sản xuất mỗi loại sản phẩm là bao nhiêu trong một tuần để lợi nhuận thu được là cao nhất? Bài 6. Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với:  Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván.  Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván. Máy cưa làm việc tối đa 8 giờ trong ngày, và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng), và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất? Bài 7 Chuyên gia dinh dưỡng định thành lập một thực đơn gồm 2 loại thực phẩm chính A và B. Cứ một (trăm gram): 16
  17.  Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein.  Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein. Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm gram) thực phẩm B giá 25 (ngàn đồng). Hỏi nhà dinh dưỡng muốn thức ăn phải cung cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24 đơn vị protein thì cần bao nhiêu (trăm gram) thực phẩm mỗi loại để có giá nhỏ nhất những vẫn cung cấp đủ dinh dưỡng? Bài 8 Một nhà sản xuất có 2 nhà máy: Một nhà máy ở Vĩnh Phúc và một nhà máy ở Bình Dương. Có 3 kho hàng phân phối sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy ở Vinh phúc; Bình Dương, có khả nang cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầu của các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấn trở lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản xuất đến các kho hàng ở Hà Nội, TP. HCM và ở Cần Thơ để chi phí nhỏ nhất nhưng vẫn đáp ứng đủ nhu cầu? Trạm phát Hà Nội TP. HCM Cần Thơ Trạm thu W1: 100 W2: 60 W3: 80 Vĩnh Phúc Q1: 100 5 7 9 Bình Dương Q2:140 8 7 10 2. Chuyển bài toán về dạng chính tắc: Bài 1: f(x) = -5x1 – 4x2 – 3x3  min  2 x1  3 x 2  x 3  5   4 x1  x 2  2 x 3  1 1 Với điều kiện   3 x1  4 x 2  2 x 3  8  x1 , x 2 , x 3  0  Bài 2: f(x) = 2x1 –x2  max   x1  2 x 2  x3  2   2 x1  x2  x3  2 Với điều kiện   x1  x2  x3  4  x1 , x2  0  Bài 3: f(x) = 2x1 + 4x2 - x3 + x4  max 17
  18.  x1  3 x 2  x 4  4   2 x1  x 2  3 Với điều kiện   x 2  4 x3  x 4  3  x1 , x 2 , x 4  0  Bài 4: f(x) = x1 –2x2 – x3  min  x1  x 2  2 x 3  2 x  x  x  1  1  2 3 Với điều kiện  x 2  x3  5 2 x  x  2  1 2  x1 , x 3  0  Bài 5: f(x) = -5x1 –2x2 – 10x3/3 min  2 x1  4 x 2  3 x 3  4 6  Với điều kiện  4 x1 2 x 3  3 x 5  3 8   3 x1  x 3  2 1  x1 , x 3  0  Bài 6: f(x) = -x1 – 5x2 + 4x3 – 2x4  min.  x1  4 x2  x3  6 x4  13  Với điều kiện  x1  2 x2  3 x4  9  3 x  x  x  2 x  8  1 2 3 4 xj ≥ 0 (j = 1, 4 ) Bài 7: f(x) = 7x1 + 6x2 – 12x3 + x4  max. 2 x1  2 x2  3x3  2 x4  8  Với điều kiện 3 x2  2 x3  2 x4  1 2 x  3 x  x  10  1 3 4 xj ≥ 0 (j = 1, 4 ). 18
  19. Chương2 PHƯƠNG PHÁP ĐƠN HÌNH Mục tiêu: Sau khi đọc xong chương này học sinh sẽ: - Hiểu được phương pháp đơn hình giải bài toán QHTT dạng chuẩn. - Hiểu được phương pháp đơn hình mở rộng giải bài toán QHTT dạng chính tắc. - Vận dụng giải các bài toán quy hoạch tuyến tính. 2.1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QHTT DẠNG CHUẨN 2.1.1. Thuật toán giải bài toán min n (1) f ( x)   c j x j  min j 1 a11 x1  a12 x2  ...  a1n xn  b1; a x  a x  ...  a x  b ;  (2)  21 1 22 2 2n n 2 ............................................ am1x1  am 2 x2  ...  amn xn  bm .  (3) xj ≥ 0 (j = 1, n ). Qua một số hữu hạn các bước sau đây ta sẽ giải được bài toán QHTT trên, nghĩa là chứng tỏ được rằng bài toán vô nghiệm hoặc chỉ ra được một phương án tối ưu của bài toán. Bước 1: Lập bảng đơn hình đầu tiên: Xác định các ẩn cơ bản 1,2 ..., m lần lượt là xi1 ; xi2 ;...; xim và lập bảng đơn hình đầu tiên: Ẩn cơ Phương c1 ...... cv ...... cn Hệ số i bản án x1 ....... xv ....... xn ci1 xi1 b1 a11 ..... a1v ..... a1n ...... ...... ..... ..... ..... ..... ..... .... br ar1 ..... .... arn cir xir ..... ...... ..... arv ...... ..... ..... ik * ...... .... bm am1 ..... amv ..... amn cim xim f(x) f0 1 .... * v .... n Trong đó: f0 = ci1 b1  ci2 b2  ....  cim bm = (cột hệ số) (cột Phương án)  j  ci1 a1 j  ci2 a2 j  ...  cim amj  c j (j = 1, n ) = (cột Hệ số) (cột xj) - cj 19
  20. Bước 2: Nhận định tính tối ưu. 1. Nếu  j  0 với mọi j = 1,...,n thì phương án cơ bản ban đầu x0 (x0 có thành phần thứ ik là x i0k = bk, còn các thành phần khác bằng 0) là một phương án tối ưu của bài toán min đang xét với f(x0) = f0. 2. Nếu tồn tại v  0 sao cho aiv  0 với mọi i = 1,....,m, thì bài toán min đang xét vô nghiệm, nghĩa là không có phương án tối ưu nào. 3. Nếu hai trường hợp trên đều không xảy ra, nghĩa là tồn tại v  0 , và với mọi j mà  j  0 đều tồn tại i sao cho aij  0 , thì sang bước 3. Bước 3: Tìm ẩn đưa vào hệ ẩn cơ bản. Trong tất cả các  j  0 , ta chọn v  0 lớn nhất [Ta đánh dấu * cho  v dương lớn nhất trong bảng]. Khi đó, xv là ẩn mà ta sẽ đưa vào hệ ẩn cơ bản. Bước 4: Tìm ẩn đưa ra khỏi hệ ẩn cơ bản. bk Lập các tỉ số j = với mọi k mà akv > 0 và ghi vào cột i của bảng. Xác định akv  bk    min  : akv  0   akv  Ta đánh dấu * cho r nhỏ nhất trong bảng]. Khi đó xr là ẩn ta sẽ đưa ra khỏi hệ ẩn cơ bản. Bước 5: Tìm phần tử chốt. Phần tử chốt là hệ số arv ở cột v (cột chứa * ), hàng r (hàng chứa r* ) [Ta đóng v khung phần tử chốt arv]. Bước 6: Biến đổi bảng. 1. Trong cột ẩn cơ bản ta thay xr bằng xv. Trong cột hệ số ta thay cr bằng cv. hr 2. Dùng phép biến đổi hr: = , nghĩa là hàng r mới = hàng r cũ (của ma trận bổ arv sung các phương trình ràng buộc) chia cho phần tử chốt arv. 3. Với các hàng i (i  r) (của ma trận bổ sung các phương trình ràng buộc) ta dùng phép biến đổi. h i : h i  a iv h r , nghĩa là (hàng i mới) = (hàng i cũ) – aiv (hàng r mới). 4. Với hàng cuối cùng của bảng (gồm f(x), f0 và các  j ), ta dùng phép biến đổi hc : hc  v hr nghĩa là (hàng cuối mới) = (hàng cuối cũ) -  v (hàng r mới). 20

CÓ THỂ BẠN MUỐN DOWNLOAD

AMBIENT
Đồng bộ tài khoản