›
›

Tài liệu môn học Toán kinh tế

pdf 61 trang vanle 3470
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tài liệu môn học 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:

  • pdftai_lieu_mon_hoc_toan_kinh_te.pdf

Nội dung text: Tài liệu môn học Toán kinh tế

  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: 0,04x1 0,06 x 2 0,05 x 3 500; (2) 0,07x1 0,02 x 3 300 (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 x 12 x 13 20; x21 x 22 x 23 40; (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; 6x11 5 x 12 4 x 13 4 x 21 3 x 22 2 x 23 0 x11 x 21 10; Với điều kiện 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 )  cj x j m in( m ax ) j 1 7
  8. n  aij xj b i ,(); i I 1 j 1 n ( 2 )  aij xj b i , ( i I 2 ); j 1 n  aij xj b i ,(); 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 )  cj x j m in ( m a x ) j 1 n ( 2 ) aij xj b i ( i 1, m ) j 1 (3)xj 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 x 2 x 3 6 x 4 min 8
  9. x1 4 x 2 x 4 12; (2) 12x1 3 x 2 x 3 x 4 3; x1 x 2 x 3 x 4 6. (3 )xj 0 ( j 1, n ) 1.2.3. Dạng chuẩn của bài toán QHTT n (1)f ( x )  cj x j m in ( m a x ) j 1 n ( 2 ) aij xj b i ( i 1, m ) j 1 (3)xj 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 . ; e 0 ; ; e . 2 m . . 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 x 2 x 3 6 x 4 x 5 4 x 6 min x1 x 4 x 5 12; (2) 12x1 x 3 x 6 3; x1 x 2 x 3 x 4 6. ( 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  aij xi b j i 1 ta đưa vào ẩn phụ xn+i 0 để biến về phương trình. n  aij xj x n i b i i 1 2. Khi gặp ràng buộc dạng. n  aij xi b i i 1 ta đưa vào ẩn phụ xn+i 0 để biến về phương trình. n  aij xj x n i b i i 1 ' ' 3. Khi gặp ẩn xj ≤ 0, ta đổi biến xj 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 4x1 6 x 2 5 x 3 50 7x1 x 3 30 2x1 3 x 2 5 x 3 25 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 x 2 với. x2 0 ' '' ' '' - Đổi biến x3 x 3 x 3 với x3 0; x 3 0. Ta đưa bài toán về dạng chính tắc: (1)()f x f (,,)3 x1 x 2 x 3 x 1 2 x 2 2,5 x 3 max ''" 4x1 6 x 2 5( x 3 x 3 ) x 4 50; '" (2) 7x1 ( x 3 x 3 ) x 5 30; ''" 2x1 3 x 2 5( x 3 x 3 ) 25. ' ' '' (3)x1 0; x 2 0; x 3 0; x 3 0; x 4 0; x 5 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 x 2 x 3 5 (2) x1 2 x 2 x 3 3 x1 x 2 x 3 0 (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  akj x j x n k b k j 1 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 (,,)3 x1 x 2 x 3 x 1 2 x 2 2 x 3 x 4 min 4x1 6 x 2 5 x 3 50; (2) 7x1 x 3 x 4 0; 2x1 3 x 2 5 x 3 25 (3)xj 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 4x1 6 x 2 5 x 3 50; ' (2 ) 7x1 x 3 x 4 0; 2x1 3 x 2 5 x 3 25 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 x 2 2 x 3 x 4 Mx 5 Mx 6 min. 4x1 6 x 2 5 x 3 x 5 50; (2) 7x1 x 3 x 4 0; 2x1 3 x 2 5 x 3 x 6 25. 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 x 2 2 x 3 x 4 Mx 5 - Mx6 max 4x1 6 x 2 5 x 3 x 5 50; 7x1 x 3 x 4 0; 2x1 3 x 2 5 x 3 x 6 25. 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 9x2 15 x 3 50; (2) 6x3 2 x 4 120; x1 3 x 2 5 x 3 45. (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 9x2 15 x 3 x 5 50; (2) 6x3 2 x 4 120; x1 3 x 2 5 x 3 x 6 45. (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: 9x2 15 x 3 x 5 50; (2) 6x3 2 x 4 120; x1 3 x 2 5 x 3 x 6 45. 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. 9x2 15 x 3 x 5 50; 6x3 2 x 4 x 7 120; x1 3 x 2 5 x 3 x 6 45. 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 2x1 3 x 2 x 3 5 4x1 x 2 2 x 3 11 Với điều kiện 3x1 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 x 3 2 2x1 x 2 x 3 2 Với điều kiện x1 x 2 x 3 4 x1, x 2 0 Bài 3: f(x) = 2x1 + 4x2 - x3 + x4 max 17
  18. x1 3 x 2 x 4 4 2x1 x 2 3 Với điều kiện x2 4 x 3 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 x2 x 3 5 2x x 2 1 2 x1, x 3 0 Bài 5: f(x) = -5x1 –2x2 – 10x3/3 min 2x1 4 x 2 3 x 3 4 6 4x1 2 x 3 3 x 5 3 8 Với điều kiện 3x1 x 3 2 1 x1, x 3 0 Bài 6: f(x) = -x1 – 5x2 + 4x3 – 2x4 min. x1 4 x 2 x 3 6 x 4 13 Với điều kiện x1 2 x 2 3 x 4 9 3x1 x 2 x 3 2 x 4 8 xj ≥ 0 (j = 1,4 ) Bài 7: f(x) = 7x1 + 6x2 – 12x3 + x4 max. 2x1 2 x 2 3 x 3 2 x 4 8 Với điều kiện 3x2 2 x 3 2 x 4 1 2x1 3 x 3 x 4 10 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 )  cj x j min j 1 a11 x 1 a 12 x 2 a 1n x n b 1 ; a21 x 1 a 22 x 2 a 2n x n b 2 ; (2) am1 x 1 a m 2 x 2 a mn x n b m . (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à x; x ; ; x và lập bảng đơn hình đầu tiên: i1 i 2 im Ẩn cơ Phương c1 cv cn Hệ số i bản án x1 xv xn c x b1 a11 a1v a1n i1 i1 b a a c x r r1 rn ir ir arv  * ik bm am1 amv amn c x im im f(x) f * 0 1 v n Trong đó: f = c b c b c b 0 i11 i 2 2 im m = (cột hệ số) (cột Phương án) c a c a c a c (j = 1, n ) j i11 j i 2 2 j im mj j = (cột Hệ số) (cột xj) - cj 19
  20. Bước 2: Nhận định tính tối ưu. 0 0 1. Nếu j 0 với mọi j = 1, ,n thì phương án cơ bản ban đầu x (x có thành phần 0 thứ ik là x = 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 ik 0 min đang xét với f(x ) = 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 v ), hàng r (hàng chứa r ) [Ta đóng 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. hi:, h i a i v 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: h c v h r nghĩa là (hàng cuối mới) = (hàng cuối cũ) - v (hàng r mới). 20
  21. Bước 7: Quay về bước 2. Chú ý: a. Trong bước 3, nếu có chiều v 0 lớn nhất thì ta chỉ chọn một trong số đó để đánh dấu * và xác định ẩn đưa vào tương ứng. b. Trong bước 4, nếu có nhiều r thoả mãn bk  r min :a kv 0  akv  thì ta chỉ chọn một trong số đó để đánh dấu * và xác định ẩn đưa ra tương ứng. c. Trong Bước 6, các phép biến đổi từ 2) đến 4) có thể được thực hiện bằng phương pháp “đường chéo hình chữ nhật” như sau: d.Trong Bước 6, hàng cuối có thể được tính nhờ vào các hàng trên của bảng mới như khi lập bảng đơn hình đầu tiên ở Bước 1. Ví dụ: Giải bài toán QHTT sau: (1) f(x) = f(x1, x2, x3) = 2x1 + 5x2 + 4x3 + x4 – 5x5 min x1 6 x 2 2 x 4 9 x 5 3 2 ; 1 3 ( 2 ) 2x2 x 3 x 4 x 5 3 0 ; 2 2 3x2 x 5 x 6 3 6 . (3) xj 0 (j = 1, , 6) 21
  22. Giải. Bài toán trên có dạng chính tắc với các vế phải của các phương trình ràng buộc trong (2) đều không âm. Ma trận hệ số ràng buộc là: 1 6 0 2 9 0 A 0 2 1 1/ 2 3/ 2 0 0 3 0 0 1 1 Vì A chứa đủ 3 véctơ cột đơn vị e1 (cột 1), e2 (cột 3), e3 (cột 6) nên bài toán có dạng chuẩn, trong đó. - Ẩn cơ bản thứ 1 là x1; - Ẩn cơ bản thứ 2 là x3; - Ẩn cơ bản thứ 3 là x6; Ta giải bài toán bằng phương pháp đơn hình. Lập bảng đơn hình: Ẩn cơ Phương 2 5 4 1 -5 0 Hệ số i bản án x1 x2 x3 x4 x5 x6 2 x1 32 1 -6 0 -2 -9 0 4 x2 30 0 2 1 1/2 3/2 0 0 x3 36 0 3 0 0 1 1 f(x) 184 0 -9 0 -3 -7 0 f0 = 2.32 + 4.30 + 0.36 = 184; 1 3 6 0; 2 2.( 6) 4.2 0.3 5 9; 4 2.( 2) 4.(1/ 2) 0.0 1 3; 5 2.( 9) 4.(3 / 2) 0.1 ( 5) 7 Trong bảng trên ta tấy j 0 với mọi j = 1,2, ,6, nên bài toán min đang xét có một phương án tối ưu là phương án cơ bản ban đầu x0 định bởi: x 1 3 2 ; x 3 3 0 ; x 6 3 6 ; x2 x 4 x 5 0 với f(x0) = 184. Kết luận: Bài toán có phương án tối ưu là x0 = (32, 0, 30, 0, 0, 36) với f(x0) = 184. 22
  23. Ví dụ 2: Giải bài toán QHTT sau: (1) f(x) = f(x1, x2, x3) = 6x1 + x2 + x3 + x5 – x6 min x1 x 2 x 4 x 6 15; (2) 2x1 x 3 2 x 6 9; 4x1 2 x 4 x 5 3 x 6 2. (3) xj 0 (j = 1, , 6) Giải Bài toán trên có dạng chính tắc với về phải của phương trình ràng buộc thứ 2 trong (2) là -9 < 0. Đổi dấu hai vế của phương trình này, ta đưa về bài toán sau: (1) f(x) = f(x1, x2, x3) = 6x1 + x2 + x3 + 3x4 + x5 – x6 min x1 x 2 x 4 x 6 15; ' (2 ) 2x1 x 3 2 x 6 9; 4x1 2 x 4 x 5 3 x 6 2. (3) xj ≥ 0 (j = 1, , 6). Ma trận hệ số ràng buộc là: 1 1 0 1 0 1 A 2 0 1 0 0 2 4 0 0 2 1 3 Vì A chứa đủ 3 véctơ cột đơn vị e1 (cột 2), e2 (cột 3), e3 (cột 5) nên bài toán có dạng chuẩn, trong đó. - Ẩn cơ bản thứ 1 là x2; - Ẩn cơ bản thứ 2 là x3; - Ẩn cơ bản thứ 3 là x5; Ta giải bài toán bằng phương pháp đơn hình. Lập bảng đơn hình: Hệ Ẩn cơ Phương 6 1 1 3 1 -7 i số bản án x x x x x x 1 2 3 4 5 6 Bảng I 1 x2 15 -1 1 0 -1 0 1 h2:= h2 + 2h1: 1 x3 9 -2 0 1 0 0 -2 1 x5 2 4 0 0 2 1 -3 h3:= h3 + 3h1: f(x) 26 -5 0 0 -2 0 3* hc:= hc – 3h1: -7 x6 15 -1 1 0 -1 0 1 Bảng II 1 x3 39 -4 2 1 -2 0 0 1 x5 47 1 3 0 -1 1 0 f(x) -19 -2 -3 0 1 0 0 23
  24. Bảng I: Ta tìm được: f0 = 1.15 + 1.9 + 1.2 = 26; 2 3 5 0; 1.( 1) 1.( 2) 1.4 6 5; 1 4 1.( 1) 1.0 1.2 3 2 6 1.1 1.( 2) 1( 3) ( 7) 3. Trong bảng I ta thấy tồn tại 6 3 0 và trên cột tương ứng có a13=1>0 (a23 =-2, a33 = -3) nên ta chọn ẩn đưa vào là x6, ẩn đưa ra là x2, phần tử chốt là a13 = 1. Bảng II: Trong bảng II, ta thấy tồn tại 4 1 0 mà ai4 ≤ 0 với mọi j= 1,2,3 (a14 = -1, a24 = -2, a34 = -1) nên bài toán min đang xét vô nghiệm. Ví dụ 3: Giải bài toán QHTT sau: (1) f(x) = 2x1 – x2 + 3x3 + 2x4 + x5 + 4x6 min 2x2 x 3 2 x 4 3 x 5 6 (2) x2 x 4 x 5 x 6 3 x1 4 x 4 2 x 5 5 (3) xj ≥ 0 (j = 1,6 ) Giải Ma trận hệ số ràng buộc 0 2 1 2 3 0 A 0 1 0 1 1 1 1 0 0 4 2 0 Véctơ A có chứa đủ 3 véctơ cột đơn vị e1, e3, e6. - Ẩn cơ bản: x3; x6; x1. Bảng đơn hình Hệ Ẩn cơ Phương 2 -1 3 2 1 4 Bảng II: số bản án x x x x x x 1 2 3 4 5 6 1 3 x 6 0 2 1 2 0 h1:= h1 3 3 3 4 x 3 0 1 0 -1 1 1 6 h2:= h2 – h1: 2 x1 5 1 0 0 -4 2 0 h3:= h3 – 2h1: f(x) 40 0 11 0 -8 16* 0 hc:= hc – 16h1: Bảng III: 1 x5 2 0 1/3 2/3 1 0 2/3 3 4 x6 1 0 1/3 -1/3 -5/3 0 1 h1:= h : 2 1 2 x 1 1 -4/3 -2/3 -16/3 0 0 1 1 f(x) 8 0 1/3* -16/3 -56/3 0 0 h2:= h2 - h1: 3 -1 x2 3 0 1 1/2 1 3/2 0 4 h3:= h3 + h : 4 x 0 0 -2 -1/2 1 1 6 0 -1/2 3 2 x 1 0 0 -4 2 0 1 5 1 f(x) 7 0 0 -11/2 -19 -1/2 0 hc:= hc - h : 3 c 24
  25. Phương án tối ưu của bài toán (5; 3; 0; 0; 0; 0) f(x) = 7 2.1.2. Thuật toán giải bài toán max Đối với bài toán QHTT f(x) max ta có thể chuyển về bài toán min như sau: Đặt g(x) = -f(x). Ta có g(x) min và f(x) đạt max tại x0 g(x) đạt min tại x0. Hơn nữa, khi đó f(x0) = -g(x0). Ngoài ra ta cũng có thuật toán giải trực tiếp bài toán max tương tự như thuật toán giải bài toán min, nhưng những điều kiện về các j ở hàng cuối sẽ hoàn toàn ngược lại, cụ thể có sự thay đổi như sau: a. Bước 2 (Kiểm tra tính tối ưu): 0 1. Nếu j 0với mọi j = 1, ,n, thì phương án cơ bản ban đầu x (là phương án có 0 thành phần thứ i là x = b còn các thành phần khác bằng 0) là một phương án tối ưu k ik k, 0 của bài toán max đang xét với f(x ) = 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 max đ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. 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 bé nhất [Ta đánh dấu * cho v âm bé nhất trong bảng]. Khi đó, xv là ẩn mà ta sẽ đưa vào hệ ẩn cơ bản. Ví dụ 1: Giải bài toán QHTT sau: (1) f(x) = f(x1, x2, x3) = 3x1 + 8x2 + 5x3 max x1 3 x 2 4; (2) x1 2 x 3 7; x1 3 x 2 2 x 3 12. (3) xj 0 (j = 1, 2, 3) Giải. Chuyển về bài toán min bằng cách đặt g(x) = -f(x) = -3x1 – 8x2 – 5x3 Ta có bài toán: (1’) g(x) = -3x1 – 8x2 – 5x3 min 25
  26. x1 3 x 2 4; (2) x1 2 x 3 7; x1 3 x 2 2 x 3 12. (3) xj ≥ 0 (j = 1, 2, 3). Biến đổi bài toán trên về dạng chính tắc bằng cách đưa vào các ẩn phụ xj ≥0 (j = 4, 5, 6): (1’) g(x) = - 3x1 – 8x2 – 5x3 min x1 3 x 2 x 4 4; (2') x1 2 x 3 x 5 7; x1 3 x 2 2 x 3 x 6 12 (3’) xj 0 (j = 1, 2, , 6) Bài toán dạng chính tắc trên có các vế phải của các phương trình ràng buộc trong (2’) đều không âm. Ma trận hệ số ràng buộc là: 1 3 0 1 0 0 A 1 0 2 0 1 0 1 3 2 0 0 1 Vì A chứa đủ 3 véctơ cột đơn vị e1 (cột 4), e2 (cột 5), e3 (cột 6) nên bài toán có dạng chuẩn, trong đó - Ẩn cơ bản thứ 1 là x4; - Ẩn cơ bản thứ 2 là x5; - Ẩn cơ bản thứ 3 là x6; Ta giải bài toán bằng phương pháp đơn hình. Lập bảng đơn hình: -3 -8 -5 0 0 0 Ẩn cơ Phương Hệ  bản án x x x x x x i số 1 2 3 4 5 6 0 x4 4 1 3 0 1 0 0 1=4/3* 0 x5 7 1 0 2 0 1 0 Bảng I 0 x6 12 1 3 2 0 0 1  =12/3 3 h :=(1/3)h g(x) 0 3 8* 5 0 0 0 1 1 h3:= h3 – 3h1: -8 x2 4/3 1/3 1 0 1/3 0 0 hc; hc – 8h1: 2 0 x5 7 1 0 0 1 0 2 =7/2* Bảng II 0 x6 8 0 0 2 -1 0 1  =8/2 3 h2:= (1/2)h2 g(x) -32/3 1/3 0 5* -8/3 0 0 h3:= h3 – 2h2: -8 x2 4/3 1/3 1 0 1/3 0 0 hc = hc – 5h2: -5 x3 7/2 1/2 0 1 0 1/2 0 Bảng III 0 x6 1 -1 0 0 -1 -1 1 g(x) -169/6 -13/6 0 0 -8/3 -5/2 0 26
  27. Bảng I: Ta tìm được: g0 = 0.4 + 0.7 + 0.12 = 0; 4 5 6 0; 0.1 0.1 0.1 ( 3) 3; 1 2 0.3 0.0 0.3 ( 8) 8; 3 0.0 0.2 0.2 ( 5) 5; Trong bảng I ta thấy tồn tại các j 0 là: 1 3, 2 8, 3 5 và trên mỗi cột tương ứng có hệ số dương. Ta chọn 2 8 dương lớn nhất và ẩn đưa vào là x2, khi đó trên cột tương ứng có các hệ số dương là a12 = 3, a32 = 3 nên ta lập các tỉ số 1 =3/4, 2 =12/3. Ta chọn tỉ số 1 = 4/3 nhỏ nhất và ẩn đưa ra là x4, phần tử chốt là a12 = 3. Sau đó, biến đổi Bảng I bằng các phép biến đổi ghi cạnh bảng. Bảng II: Lý luận tương tự như trên, ta thấy phương án cơ bản ban đầu trong bảng này chưa tối ưu và cũng không có dấu hiệu cho thấy bài toán vô nghiệm. Biến đổi bảng II bằng các phép biến đổi ghi cạnh bảng. Bảng III: Trong bảng III ta thấy j 0 với mọi j = 1, 2, , 6, nên bài toán min đang xét có một phương án tối ưu là phương án cơ bản ban đầu x1 định bởi: x2 4 / 3; x3 7 / 2; x6 1; x1 x 4 x 5 0. Với g (x1) = -169/6. Bỏ đi các ẩn phụ, ta được phương án tối ưu của bài toán min là 0 0 x = (x1, x2, x3) = (0, 4/3, 7/2) với g (x ) = -169/6. Kết luận: Bài toán max đã cho có phương án tối ưu là x0 = (0, 4/3, 7/2) với f(x0) = 169/6. Ví dụ 2: Giải bài toán QHTT sau: (1) f(x) = f(x1, x2, x3) = -2x1 + 6x2 + 4x3 – 2x4 + 3x5 max x1 2 x 2 4 x 3 52; (2) 4x2 2 x 3 x 4 60; 3x2 x 5 36. (3) xj ≥ 0 (1 ≤ j ≤ 5). Giải: Bài toán trên có dạng chính tắc với các vế phải của các phương trình ràng buộc trong (2) đều không âm. Ma trận hệ số ràng buộc là: 27
  28. 1 2 4 0 0 A 0 4 2 1 0 0 3 0 0 1 Vì A chứa đủ 3 véctơ cột đơn vị e1 (cột 1), e2 (cột 4), e3 (cột 5) nên bài toán có dạng chuẩn, trong đó. - Ẩn cơ bản thứ 1 là x1; - Ẩn cơ bản thứ 2 là x4; - Ẩn cơ bản thứ 3 là x5; Ta giải bài toán bằng phương pháp đơn hình. Lập bảng đơn hình: Hệ Ẩn cơ Phương -2 6 4 -2 3 i số bản án x1 x2 x3 x4 x5 -2 x1 52 1 2 0 0  52 / 4* 4 1 Bảng I -2 x4 60 0 4 2 1 0 2 60 / 2 h1:= (1/4)h1 3 x5 36 0 3 0 0 1 h := h – 2h f(x) -116 0 -9 -16* 0 0 2 2 1 hc:= hc + 16h1 4 x3 13 1/4 1/2 1 0 0 1 13.2  34 / 3* Bảng II -2 x4 34 -1/2 3 0 1 0 2  36 / 3 h2:= (1/3)h2 3 x5 36 0 3 0 0 1 3 h := h – (1/2)h f(x) 92 4 -1* 0 0 0 1 1 1 h3:= h3 – 3h2 4 x3 22/3 1/3 0 1 -1/6 0 hc:= hc + h2 6 x2 34/3 -1/6 1 0 1/3 0 Bảng III 3 x5 2 1/2 0 0 -1 1 f(x) 310/3 23/6 0 0 1/3 0 Bảng I: Ta tìm được: f0 = -2.52 – 2.60 + 3.36 = -116; 1 4 5 0; 2 2.2 2.4 .3. 6 9; 3 2.4 2.2 3.0 4 16. Trong bảng I, ta thấy tồn tại các j 0 là: 2 9, 3 16 và trên mỗi cột tương ứng có hệ số dương. Ta chọn 3 16 âm nhỏ nhất và ẩn đưa vào là x3, khi đó trên cột tương ứng có các hệ số dương là a13 = 4, a23 = 2 nên ta lập các tỉ số 1 52 / 4,  2 60 / 2 . Ta chọn tỉ số 1 52 / 4 nhỏ nhất và ẩn đưa ra là x1, phần tử chốt là a13 = 4. Sau đó, biến đổi Bảng I bằng các phép biến đổi ghi cạnh bảng. 28
  29. Bảng II: Lý luận tương tự như trên, ta thấy phương án cơ bản ban đầu trong bảng này chưa tối ưu và cũng không có dấu hiệu cho thấy bài toán vô nghiệm. Biến đổi Bảng II bằng các phép biến đổi ghi cạnh bảng. Bảng III: Trong Bảng III ta thấy j 0 với mọi j = 1, 2, , 5, nên bài toán max 0 đang xét có một phương án tối ưu là phương án cơ bản ban đầu x định bởi: x3 22 / 3; x2 34 / 3; x5 2; x1 x 4 0. với f(x0) = 310/3. Kết luận: Bài toán max đã cho có phương án tối ưu là x0 = (0, 34/3, 22/3, 0, 2) với f(x0) = 310/3. 2.2. PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG GIẢI BÀI TOÁN QHTT DẠNG CHÍNH TẮC 2.2.1. Phương pháp giải bài toán QHTT dạng chính tắc - Do hàm mục tiêu mở rộng là f()()( X f x M  ẩn giả) đối với bài toán min, và là f()()( X f x M  ẩn giả) đối với bài toán max. Khi giải trong các bảng đơn hình, ở cột Hệ số có thể có các hệ số phụ thuộc M. Khi đó, ở hàng cuối gồm f( x ); f0 và các j , các hệ số sẽ có dạng j  j M , do đó người ta thường chia hàng cuối thành 2 hàng nhỏ: Hàng nhỏ trên ghi các số j ; Hàng nhỏ trên ghi các số  j M . Các hàng này cũng tuân thủ các phép biến đổi của bảng giống như các hàng khác. - Do hàm mục tiêu mở rộng là f()()( X f x M  ẩn giả) đối với bài toán max. - Khi giải trong các bản đơn hình, ở cột Hệ số có thể có các hệ số phụ thuộc M. Khi đó, ở hàng cuối gồm f() X f0 và j , các hệ số sẽ có dạng j + jM, do đó người ta thường chia hàng cuối thành 2 hàng nhỏ: Hàng nhỏ trên ghi các số j; hàng nhỏ trên ghi các số jM. Các hàng này cũng tuân thủ các phép biến đổi của bảng giống như các hàng khác. 2.2.2. So sánh các đại lượng trong bài toán QHTT dạng chính tắc. - Vì M là một đại lượng dương rất lớn, nên khi so sánh các số dạng + M và ’ + ’M, ta có qui tắc sau: '; MM ''    '.  0;  M 0 Tuỳ ý  0; 0. 29
  30.   '; ,' Tuỳ ý MM ''    '; '. Do đó khi xét dấu j, hệ số j ở hàng nhỏ dưới được xem xét trước; và chỉ khi nào j =0, ta mới xét đến hệ số j ở hàng nhỏ trên. Tương tự, khi so sánh các j, các hệ số j ở hàng nhỏ dưới được so sánh trước; và chỉ khi nào các j bằng nhau, ta mới so sánh các hệ số j ở hàng nhỏ trên. - Trong bảng đơn hình đầu tiên, tất cả các ẩn giả đều có trong cột Ẩn cơ bản (vì chúng đều là các ẩn cơ bản). Mỗi khi một ẩn giả bị đưa ra khỏi hệ ẩn cơ bản thì không bao giờ ta đưa ẩn giả đó trở lại nữa, vì vậy trong bảng đơn hình ta có thể bỏ đi các cột ứng với các ẩn giả. Ví dụ 1: Giải bài toán QHTT sau: (1) f(X) = x1 + 2x2 + x4 – 5x5 min 3x 9 x 0; 3 4 (2) x2 7 x 3 5 x 4 2 x 5 5; 1 2 4 1 2 x x x x x . 13 2 3 3 3 4 3 5 3 (3) xj > 0 (1 0 (j = 6,7) và lần lượt cộng x6, x7 vào vế trái của các phương trình ràng buộc thứ 1, thứ 2 để xây dựng bài toán mở rộng dạng chuẩn: (1) f( x ) x1 2 x 2 x 4 5 x 5 Mx 6 Mx 7 min 3x 9 x x 0; 3 4 6 (2) x2 7 x 3 5 x 4 2 x 5 x 7 5; 1 2 4 1 2 x x x x x . 13 2 3 3 3 4 3 5 3 (3) xj > 0 (1 < j < 7) 30
  31. Khi đó bài toán có - Ẩn cơ bản thứ 1 là x6; - Ẩn cơ bản thứ 2 là x7; - Ẩn cơ bản thứ 3 là x1; Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: Ẩn cơ Phương 1 2 0 1 -5 Hệ số i bản án x1 x2 x3 x4 x5 M x6 0 0 0 -3 -9 0 Bảng I M x7 5 0 1 -7 -5 -2 h3: =h3+(1/3)h2 1 x1 2/3 1 -1/3 2/3 4/3 1/3 h2:= h2: h = h f() x 2/3 0 -7/3 2/3 1/3 16/13 1: 1: 5M 0 M* -10M -14M -2M hc1: =hc1+ (7/3)h2: hc2: =hc2 – M.h2: M x6 0 0 0 -3 -9 0 Bảng II 2 x2 5 0 1 -7 -5 -2 1 x1 7/3 1 0 -5/3 -1/3 -1/3 f() x 37/3 0 0 -47/3 -34/3 2/3 0 0 0 -3M -9M 0 Bảng I: Ta tìm được: f0 M.0 M .5 1.(2/3) 2/3 5 M ; 1 0  MMM.0 .11.(1/3) 2 7/3 ; 2 3 MMM.( 3) .(7) 1.(2/3) 0 2/3 10 ; 4 MMM.( 9) .( 5) 1.(4/3) 1 1/3 14 ; 5 MMM.0 .( 2) 1.(1/3) 5 16/3 2 . Trong bảng I ta thấy tồn tại duy nhất một j >0 là: 2= 7/3 + M >0 và trên cột tương ứng chỉ có một hệ số dương là a22 = 1 > 0 nên ta chọn ẩn đưa vào là x2, ẩn đưa ra là x7, phần tử chốt là a22 1. Sau đó, biến đổi bảng I bằng các phép biến đổi ghi cạnh bảng. Bảng II: Trong bảng II, ta thấy tồn tại 5 = 2/5 >0 mà ai5 < 0 với mọi j = 1, 2, 3 (a15 = 0, a25 = -2, a35 = -1/3) nên bài toán min mở rộng vô nghiệm. Suy ra bài toán min xuất phát cũng vô nghiệm. Kết luận: Bài toán đã cho không có phương án tối ưu. Ví dụ 2: Giải bài toán QHTTsau: (1) f(x) = -2x1 -4x2 + 2x3 – 5x5 max 31
  32. x1 2 x 2 x 3 27; (2) 2x1 x 2 2 x 3 50; x1 x 2 x 3 18. (3) xj > 0 (j 1,3) Giải: Biến đổi bài toán trên về dạng chính tắc bằng cách đưa và ẩn phụ x4 > 0: (1’) f(x) = -2x1 -4x2 + 2x3 max x1 2 x 2 x 3 27; (2’) 2x1 x 2 2 x 3 50; x1 x 2 x 3 x 4 18. (3’) xj > 0 (j 1, 4 ) Các vế phải của phương trình ràng buộc trong (2’) đều không âm. Ma trận hệ số ràng buộc là: 1 2 1 0 A 2 1 2 0 1 1 1 1 A chứa vectơ cột đơn vị e3 (cột 4), không chứa các vectơ cột đơn vị e1, e2 nên bài toán chưa có dạng chuẩn. Ta đưa vào các ẩn giả xj > 0 (j = 5, 6) và lần lượt cộng x5, x6 vào vế trái của các phương trình ràng buộc thứ 1, thứ 2 để xây dựng bài toán mở rộng dạng chuẩn: (1”) f( x ) 2 x1 4 x 2 2 x 3 Mx 5 Mx 6 max x1 2 x 2 x 3 x 5 27; (2”) 2x1 x 2 2 x 3 x 6 50; x1 x 2 x 3 x 4 18. (3”) xj > 0 (j 1,6) Khi đó bài toán có: - Ẩn cơ bản thứ 1 là x5; - Ẩn cơ bản thứ 2 là x6; - Ẩn cơ bản thứ 3 là x4; Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: 32
  33. Ẩn cơ Phương -2 -4 2 0 Hệ số i bản án x1 x2 x3 x4 -M x5 27 1 -2 1 0  = 27/1 1 Bảng I -M x 50 2 1 2 0 6 2 = 50/2 h2: = (1/2)h2: h1: = h1+h2: 0 x4 18 1 -1 -1 1 h3:=h3 +h2: f() x 0 2 4 -2 0 -77M -3M M -3M* 0 hc1: =hc1 + 2h2: -M x5 2 0 -5/2 0 0 hc2:=hc2+ 3M.h2: 2 x3 25 1 ½ 1 0 Bảng II 0 x4 43 2 -1/2 0 1 f() x 50 4 5 0 0 -2M 0 5M/2 0 0 Bảng I: Ta tìm được: f0 M.27 M .50 0.8 77 M ; 4 0 1 MMM.1 .2 0.1 (2) 2 3 ;  2 MMM.(2) .1 0.(1) (4) 4 ; 3 MMM.1 .2 0.(1) 2 2 3 . Trong bảng I ta thấy tồn tại các j 0, a23 =2>0. Ta lậpc ác tỷ số 1 = 27/1, 2 =50/2; chọn tỷ số 2 = 25 nhỏ nhất và ẩn đưa ra là x6, phần tử chốt là a23 = 2. Sau đó, biến đổi Bảng I bằng các phép biến đổi ghi cạnh bảng: Bảng II: Trong Bảng II ta thấy j > 0 với mọi j = 1, 2, 3, 4, nên bài toán mở rộng 0 max có một phương án tối ưu là phương án cơ bản ban đầu x định bởi. x5 2; x3 25; x 4 43; x1 x 2 x 6 0. 0 Với f( x ) 50 2 M . 0 Vì bài toán mở rộng max có phương án tối ưu là x (0,0,25,43,0) , trong đó ẩn giả x5 = 2>0 nên bài toán max xuất phát không có phương án nào. Kết luận: Bài toán đã cho không có phương án nào và do đó không có phương án tối ưu. 33
  34. Ví dụ 3: Giải bài toán QHTT sau: (1) f(x) = -16x1 + 7x2 + 9x3 min 2 1 1 x1 x 2 x 3 ; (2) 3 3 3 5x1 5 x 2 7. (3) xj 0 ( j 1,3) Giải: Bài toán trên có dạng chính tắc với vế phải của phương trình ràng buộc trong (2) đều không âm. Ma trận hệ số ràng buộc là: 2 1 1 A= 3 3 5 5 0 A chứa vectơ cột đơn vị e1 (cột 3), không chứa vectơ cột đơn vị e2, nên bài toán chưa có dạng chuẩn. Ta đưa vào ẩn giả x4 > 0 và x4 vào vế trái của phương trình ràng buộc thứ 2 để xây dựng bài toán mở rộng dạng chuẩn: (1) f( x ) 16 x1 7 x 2 9 x 3 Mx 4 min 2 1 1 x x x ; (2) 31 3 2 3 3 5x1 5 x 2 x 4 7. (3) xj 0 ( j 1,4) Khi đó bài toán có - Ẩn cơ bản thứ 1 là x3; - Ẩn cơ bản thứ 2 là x4; Ta giải bài toán bằng phương pháp đơn hình mở rộng. Lập bảng đơn hình: Ẩn cơ Phương -16 7 9 Hệ số i bản án x1 x2 x3 9 x3 1/3 -2/3 -1/3 1 Bảng I M x4 7 -5 5 0 h2: =(1/5)h2: f() x 3 10 -10 0 h1: =h1+(1/3)h2: 7M -5M 5M* 0 hc1: =hc1+10h2: hc2: =hc2-5M.h2: 0 x3 4/5 -1 0 1 Bảng II 7 x4 7/5 -1 1 0 f() x 17 0 0 0 34
  35. Bảng I: Ta tìm được: f0 9.(1/3) M .7 3 7 M ;  0 3 1 9.(2/3) MM .(5) (16) 10 5 ; 2 9.(1/3) MM .5 7 10 5 . Trong bảng I ta thấy tồn tại duy nhất một j > 0 là: 2 = -10+5M >0 và trên cột tương ứng chỉ có một hệ số dương là a22 =5. Sau đó, biến đổi Bảng I bằng các phép biến đổi ghi cạnh bảng: Bảng II: Trong Bảng II ta thấy j < 0 với mọi j = 1, 2, 3 nên bài toán mở rộng min 0 có một phương án tối ưu là phương án cơ bản ban đầu X định bởi: X 3 4 / 5; X 2 7 / 5; x1 X 4 0. 0 Với f( x ) 17. 0 Bài toán mở rộng f( X ) min có phương án tối ưu là x (0,7 / 5,4 / 5,0), trong đó 0 ẩn giả duy nhất x4 = 0 nên bài toán f(x) → min xuất phát có phương án tối ưu là x = (0,7/5, 4/5) với f(x0) = 17. Kết luận: Bài toán đã cho có phương án tối ưu là x0 =(0,7/5,4/5) với f(x0)=17 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. 35
  36. BÀI TẬP CHƯƠNG 2 Giải bài toán bằng phương pháp đơn hình: Bài 1: f(x) = x1 – x2 + x3 + x4 + x5 – x6 →min x1 x 4 6 x 6 9 3x1 x 2 4 x 3 2 x 6 2 x 2 x x 2 x 6 1 3 5 6 x j 0 j 1, 6 Bài 2: f(x) = x1 – x2 + x3 + x4 + x5 → min 2x1 x 3 x 4 6 2x1 5 x 4 x 5 3 4x x x 5 1 2 4 x j 0 j 1, 5 Bài 3: f(x) = x1 + 3x2 - x3 + x4 + 4x5 →min x1 2 x 3 x 4 7 x 5 8 x3 5 x 4 x 5 7 x 4 x x 2 x 3 2 3 4 5 x 0 1, 5 j j Bài 4: f(x) = x1 – x2 + x3 + x4 + x5 →min 2x1 x 3 x 4 3 x 5 6 x1 x 4 x 6 3 4x1 x 2 x 4 2 x 5 5 x1 0, x 2 0, x 3 0, x 4 0, x 5 0, x 6 0 xj > 0 (j = 1,2 6) Bài 5: f(x) = 4x1 – 3x2 + 2x3 + 3x4 →min x1 x 3 x 4 2 x1 2 x 2 x 4 11 2x x 3 x 8 1 2 4 xj 0( j 1, 4) 36
  37. Bài 6: f(x) = 2x1 –x2 + 3x3 + 2x4 +x5 + 4x6 →min x3 2 x 4 3 x 5 x 6 6 x2 x 4 x 5 3 x1 4 x 3 4 x 4 2 x 5 5 x1 0, x 2 0, x 3 0, x 4 0, x 5 0, x 6 0 xj > 0 (j = 1,2 6) Bài 7: f(x) = x1 –4x2 - 3x3 →min 2x1 x 2 2 x 3 16; 4x1 2 x 3 18; x1 2 x 2 x 3 12 xj > 0 (j = 1,3) Bài 8: f(x) = 2x1 + 3x2 - 5x3 →min 4x1 x 2 2 x 3 1 2; 1 2x1 x 2 x 3 8; 2 3 2x x x 2 0 . 12 2 3 xj > 0 (j = 1,3) Bài 9: f(x) = -x1 - 2x2 - 3x3 + x4 →min x1 2 x 2 3 x 3 22; 2x1 x 2 5 x 3 25; x1 2 x 2 x 3 x 4 20. xj > 0 (j = 1,4) Bài 10: f(x) = -3x1 +x2 + 3x3 - x4 →min x1 2 x 2 x 3 x 4 2; 2x1 6 x 2 3 x 3 3 x 4 9; x1 x 2 x 3 x 4 6 . xj > 0 (j = 1,4) . Bài 11: 37
  38. f(x) = x1 – x2 + 3x3 + 2x4 + x5 + 2x6 → min x1 x 3 2 x 4 3 x 5 x 6 6 2x1 x 2 2 x 3 x 4 x 5 4 x1 3 x 2 3 x 4 2 x 5 7. xj ≥ 0 (j = 1,6 ) Bài 12: f(x) = 4x1 – x2 + 2x3 + 2x4 + 3x6 → min 2x1 x 2 x 3 3 x 5 8 x1 3 x 3 x 5 x 6 9 x1 2 x 3 x 4 2 x 5 3 xj ≥ 0 (j = 1,6 ) Bài 13: f(x) = x1 – x2 + x3 + x4 + 3x5 + 2x6 → min 2x1 2 x 3 x 5 4 x 6 7 x1 x 2 3 x 3 x 6 9 x1 2 x 3 x 4 2 x 6 5 xj ≥ 0 (j = 1,6 ). Bài 14: f(x) = x1 – x2 + x3 + x4 → min x1 x 2 x 3 2 x 4 5 5x1 2 x 2 x 3 x 4 3 x1 2 x 2 x 3 x 4 1 xj ≥ 0 (j = 1,4 ) Bài 15: f(x) = 2x1 – x2 + 3x3 + 2x4 → min 2x1 x 2 3 x 3 2 x 4 6 5x1 x 3 x 4 5 x1 2 x 2 x 3 x 4 4 xj ≥ 0 (j = 1,4 ) Bài 16: 38
  39. f(x) = x1 – x2 – x3 + x5 + 3x6 → min 2x1 x 2 x 5 3 x 6 3 2x1 3 x 2 x 4 x 6 8 x1 x 3 3 x 6 6 x1 0, x 2 0, x 3 0, x 4 0, x 5 0, x 6 0 xj ≥ 0 (j = 1,2 6) Bài 17: f(x) = 2x1 – x2 + 3x3 + 2x4 → min 2x1 x 2 x 3 2 x 4 x 5 5 2x1 2 x 3 x 4 x 5 x 6 3 x1 x 3 3 x 4 2 x 5 2 x 6 8 x1 0, x 2 0, x 3 0, x 4 0, x 5 0, x 6 0 xj ≥ 0 (j = 1,2 6) Bài 18. Một công ty sản xuất hai loại sơn: sơn nội thất và sơn ngoài trời. Nguyên liệu để sản xuất gồm hai loại A, B với trữ lượng tương ứng là 16 tấn và 18 tấn. Để sản xuất 1 tấn sơn nội thất cần 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Để sản xuất 1 tấn sơn ngoài trời cần 2 tấn nguyên liệu A và 3 tấn nguyên liệu B. Qua điều tra thị trường công ty biết rằng nhu cầu sơn nội thất không hơn sơn ngoài trời quá 1 tấn. Giá bán một tấn sơn nội thất là 4000 USD, giá bán một tấn sơn ngoài trời là 3000 USD. Khi sản xuất 1 tấn sơn nội thất phải bỏ ra một chi phí là 1300 USD, khi sản xuất 1tấn sơn ngoài trời phải bỏ ra một chi phí là 1000 USD. Hỏi cần sản xuất mỗi loại sơn bao nhiêu tấn để có lợi nhuận lớn nhất? Bài 19. Một công ty sản xuất hai loại sơn nội thất và sơn ngoài trời. Nguyên liệu để sản xuất gồm hai loại A, B với trữ lượng là 6 tấn và 8 tấn tương ứng. Để sản xuất một tấn sơn nội thất cần 2 tấn nguyên liệu A và 1tấn nguyên liệu B. Để sản xuất một tấn sơn ngoài trời cần 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Qua điều tra thị trường công ty biết rằng nhu cầu sơn nội thất không hơn sơn ngoài trời quá 1 tấn, nhu cầu cực đại của sơn nội thất là 2 tấn. Giá bán một tấn sơn nội thất là 2000 USD, giá bán một tấn sơn ngoài trời là 3000 USD. Hỏi cần sản xuất mỗi loại sơn bao nhiêu tấn để có doanh thu lớn nhất? Bài 20. Một công ty sản xuất hai loại thực phẩm A, B. Nguyên liệu để sản xuất gồm ba loại bột, đường và dầu thực vật. Với trữ lượng dự trự tương ứng là 30 tấn, 12 tấn, 6 tấn. Để sản xuất: 1 tấn thực phẩm loại A cần 0,5 tấn bột, 0,5 tấn đường, 0,2 tấn dầu thực vật. 39
  40. 1 tấn thực phẩm loại B cần 0,8 tấn bột, 0,4 tấn đường, 0,4 tấn dầu thực vật. Giá bán một tấn thực phẩm A là 4000 USD, giá bán một tấn thực phẩm B là 4500 USD. Hỏi cần sản xuất mỗi loại thực phẩm bao nhiêu tấn để có doanh thu lớn nhất? Bài 21. Một xí nghiệp dự định sản xuất ba loại sản phẩm A, B và C. Các sản phẩm này được chế tạo từ ba loại nguyên liệu I, II và III . Số lượng các nguyên liệu I, II và III mà xí nghiệp có lần lượt là 30, 50, 40. Số lượng các nguyên liệu cần để sản xuất một đơn vị sản phẩm A, B, C được cho ở bảng sau đây: NL I II III SP A 1 1 3 B 1 2 2 C 2 3 1 Xí nghiệp muốn lập kế hoạch sản xuất để thu được tổng số lãi nhiều nhất (với giả thiết các sản phẩm làm ra đều bán hết), nếu biết rằng lãi 5 triệu đồng cho một đơn vị sản phẩm loại A, lãi 3,5 triệu đồng cho một đơn vị sản phẩm loại B, lãi 2 triệu đồng cho một đơn vị sản phẩm loại C. a. Lập mô hình bài toán Quy hoạch tuyến tính. b. Bằng phương pháp đơn hình, hãy giải bài toán trên. Bài 22. Một Xí nghiệp chăn nuôi cần mua một loại thức ăn tổng hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh dưỡng như sau: 1 kg T1 chứa 4 đơn vị dinh dưỡng D1, 2 đơn vị dinh dưỡng D2, và 1 đơn vị dinh dưỡng D3. 1 kg T2 chứa 1 đơn vị dinh dưỡng D1, 7 đơn vị dinh dưỡng D2, và 3 đơn vị dinh dưỡng D3 1kg T3 chứa 3 đơn vị dinh dưỡng D1, 1 đơn vị dinh dưỡng D2, và 4 đơn vị dinh dưỡng D3. Mỗi bữa ăn, gia súc cần tối thiểu 20 đơn vị D1, 25 đơn vị D2 và 30 đơn vị D3. Hỏi: Xí nghiệp phải mua bao nhiêu kg T1, T2, T3 mỗi loại cho một bữa ăn để bảo đảm tốt về chất dinh dưỡng và tổng số tiền mua là nhỏ nhất? Biết rằng 1 kg T1 có giá là 10 ngàn đồng, 1 kg T2 có giá là 12 ngàn đồng, 1 kg T3 có giá là 14 ngàn đồng. Bài 23. Một Xí nghiệp xử lí giấy, có ba phân xưởng I, II, III cùng xử lí hai loại giấy A, B. Do hai phân xưởng có nhiều sự khác nhau, nên nếu cùng đầu tư 10 triệu đồng vào mỗi phân xưởng thì cuối kỳ phân xưởng I xử lí được 6 tạ giấy loại A, 5 tạ giấy loại B. Trong khi đó phân xưởng II xử lí được 4 tạ giấy loại A, 6 tạ giấy loại B. Phân xưởng III xử lí 40
  41. được 5 tạ giấy loại A, 4 tạ giấy loại B. Theo yêu cầu lao động thì cuối ky Xí nghiệp phải xử lí ít nhất 6 tấn giấy loại A, 8 tấn giấy loại B. Hỏi cần đầu tư vào mỗi phân xưởng bao nhiêu tiền để xí nghiệp hoàn thành công việc với giá tiền đầu tư là nhỏ nhất. Bài 24. Một gia đình cần ít nhất 1800 đơn vị prôtêin và 1500 đơn vị lipit trong thức an mỗi ngày. Một kilôgam thịt bò chứa 600 đơn vị prôtêin và 600 đơn vị lipit, một kilôgam thịt heo chứa 600 đơn vị prôtêin và 300 đơn vị lipit, một kilôgam thịt gà chứa 600 đơn vị prôtêin và 600 đơn vị lipit. Giá một kilôgam thịt bò là 84 ngàn đồng, giá một kilôgam thịt heo là 71 ngàn đồng, giá một kilôgam thịt gà là 90 ngàn đồng. Hỏi một gia đình nên mua bao nhiêu kilôgam thịt mỗi loại để bảo đảm tốt khẩu phần ăn trong một ngày và tổng số tiền phải mua là nhỏ nhất? 41
  42. Chương 3 BÀI TOÁN ĐỐI NGẪU Mục tiêu: Sau khi đọc xong chương này học sinh sẽ: - Hiểu được cách xây dựng bài toán đối ngẫu - Dựa vào nghiệm bài toán gốc để giải bài toán đối ngẫu và dựa vào nghiệm bài toán đối ngẫu để tìm ra nghiệm của bài toán gốc. - Vận dụng để giải các bài toán đối ngẫu. 3.1. ĐỊNH NGHĨA VÀ CÁCH XÂY DỰNG BÀI TOÁN ĐỐI NGẪU 3.1.1. Định nghĩa bài toán đối ngẫu Cặp bài toán QHTT đối ngẫu là cặp bài toán có dạng sau: Trong đó mỗi cặp ràng buộc đối ngẫu là một cặp gồm: ràng buộc thứ i ở bài toán này và ràng buộc về dấu của ẩn thứ i của bài toán kia. Quy ước: * Đối với bài toán min một ràng buộc được gọi là bất phương trình chuẩn nếu có dạng >, là bất phương trình không chuẩn nếu có dạng Bất phương trình chuẩn Bất phương trình không chuẩn Bài toán min > 3.1.2. Cách xây dựng một bài toán đối ngẫu 1. Số ẩn của bài toán này bằng số ràng buộc của bài toán kia. 2. Bài toán này tìm min (max) thì bài toán kia tìm max (min). Hệ số của các ẩn số trong hàm mục tiêu ở bài toán này chính là các hệ số ở vế phải của các ràng buộc ở bài toán kia. 42
  43. 3. Ma trận hệ số ràng buộc của bài toán này bằng chuyển vị của ma trận hệ số ràng buộc của bài toán kia. 3.2. QUAN HỆ GIỮA BÀI TOÁN GỐC VÀ BÀI TOÁN ĐỐI NGẪU 3.2.1. Cặp ràng buộc bài toán đối ngẫu Ràng buộc Ẩn Bất phương trình chuẩn > 0 Bất phương trình không chuẩn thì ràng buộc thứ j của bài toán (II) là bất phương trình chuẩn. * Nếu ẩn xj 0 * Nếu ràng buộc thứ i của bài toán (I) là bất phương trình không chuẩn thì ẩn yi 0 ; x2 < 0 Giải: Ta thấy bài toán min 4 ẩn, 3 ràng buộc có * Véctơ hệ số các ẩn trong hàm mục tiêu là C= (3,2 – 5,1) * Ma trận hệ số ràng buộc vế trái là: 4 6 5 5 A = 7 0 1 1 1 3 5 0 43
  44. * Véctơ các hệ số tự do vế phải là 50 B = 30 25 * Ràng buộc 1 là bất phương trình không chuẩn. Ràng buộc 2 là phương trình. Ràng buộc 3 là bất phương trình chuẩn. * x1 > 0; x2 0 Ví dụ 2: Tìm bài toán đối ngẫu của bài toán sau: (1) f(x) = f(x1, x2, x3, x4) = 3x1 + 2x2 - 5x3 + x4 → max 4x1 6 x 2 5 x 3 5 x 4 50; (2) 7x1 x 3 x 4 30; 2x1 3 x 2 5 x 3 25 (3) x1 > 0 ; x2 < 0 Giải: Ta thấy bài toán xax 4 ẩn, ràng buộc có * Véctơ hệ số các ẩn trong hàm mục tiêu là C= (3, 2, – 5,1) * Ma trận hệ số ràng buộc vế trái là: 4 6 5 5 A = 7 0 1 1 1 3 5 0 * Véctơ các hệ số tự do vế phải là 50 B = 30 25 44
  45. * Ràng buộc 1 là bất phương trình chuẩn. Ràng buộc 2 là phương trình. Ràng buộc 3 là bất phương trình không chuẩn. * x1 > 0; x2 0 ; y2 tuỳ ý; y3 0 Giải: 45
  46. Bài toán đối ngẫu của bài toán trên là: (1) g(y) = -2y1+ 4y2 + 2y3 → max y1 2 y 2 y 3 27; (2) 2y1 y 2 2 y 3 50; y1 y 2 y 3 18. (3) yj > 0 (j 1,3) Ta giải bài toán đối ngẫu trên và kết quả cho thấy bài toán này không có PATU. Do đó bài toán đã cho cũng không có PATU. 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 Ví dụ 1: Biết rằng X* = (0,5,0,3) là phương án tối ưu của bài toán: f(x) = 10x1+ 5x2 + 13x3+ 16x4 → max 2x1 3 x 2 x 3 x 4 16 x1 2 x 2 3 x 3 4 x 4 22 3x x 4 x 5 x 20 1 2 3 4 xj 0( j 1,4) Dựa vào phương án tối ưu của bài toán tốc để tìm ra phương án tối ưu của bài toán đối ngẫu. Ví dụ 2: Cho bài toán f(x) = -2x1- 6x2 + 5x3- x4 + 4x5 → max y1 4 x 2 2 x 3 5 x 4 9 x 5 3 x2 3 x 3 4 x 4 5 x 5 6 x2 x 3 x 4 x 5 1 xj 0( j 1, 5) Áp dụng lý thuyết đối ngẫu tìm ra phương án tối ưu của bài toán đối ngẫu. 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 Ví dụ 1: Giải bài toán QHTT sau: (1) f(x) = 12x1+ x2 + 3x3 → min 3x1 x 2 x 3 2; (2) x1 2 x 2 x 3 3; x2 x 3 3. (3) x1 > 0; x2 < 0 Giải: 46
  47. Bài toán đối ngẫu của bài toán trên là: (1) g(y) = -2y1+ 3y2 - 3y3 → max 3y1 y 2 12; (2) y1 2 y 2 y 3 1; y1 y 2 y 3 3. (3) yj > 0 (j 1, 3) Giải bài toán đối ngẫu trên và kết quả cho thấy bài toán này có PATU là 0 0 0 0 0 y = (y1 , y 2 , y 3 ) (9 / 2,3 / 2,0) với g(y ) = -9/2. 0 0 0 0 Bây giờ ta tìm PATU x = (,,)x1 x 2 x 3 của bài toán gốc. a. Thay y0 = (9/2, 3/2, 0) vào các ràng buộc trong (2’), ta thấy ở ràng buộc thứ 2: 0 y1 + 2y2 – y3 > 1 không xảy ra dấu = (VT = 15/2). Do đó x2 0 0 y1 9 / 2 0; b. Do nên ta có: 0 y2 3 / 2 0. 0 0 0 0 0 3x1 x 2 x 3 2 3 x 1 x 3 2 0 0 0 0 0 x1 2 x 2 x 3 3 x 1 x 3 3 0 x1 1 / 2; 0 x 2 7 / 2. Vậy PATU của bài toán gốc đã cho là x0 = (1/2,0,-7/2) với f(x0)=g(y0) = -9/2. Ví dụ 2: Cho bài toán QHTT sau: (1) f(x) = -16x1+ 7x2 +9y3 → min 2 1 1 x1 x 2 x 3 ; (2) 3 3 3 5x1 5 x 2 7. (3) xj > 0 (j = 1,3) Hãy lập bài toán và tìm PATU của bài toán đối ngẫu. 1 Giải: (1’) g(y) = y 7 y max 3 1 2 2 y 5 y 16 3 1 2 (2’ 1 y1 5 y 2 7 3 y1 9 (3’) y1, y2 tuỳ ý. Ta đã giải bài toán đã cho và kết quả cho thấy bài toán nàycó PATU là x0 = (0,7/5, 4/5) với f(x0) = 17. 0 0 0 Bây giờ ta tìm PATU y = (,)y1 y 2 của bài toán đối ngẫu. 47
  48. 0 x2 7 / 5 0; Do 0 nên ta có: x3 4 / 5 0. 1 0 0 0 y1 5 y 2 7; y1 9; 3 0 0 y2 2. y1 9 Vậy PATU của bài toán đối ngẫu là y0 = (9,2) với g(y0)= f(x0) = 17. 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 3 48
  49. Giải bài toán theo phương pháp đơn hình và lập bài toán đối ngẫu của các bài toán QHTT. Dựa vào kết quả của bài toán gốc để tìm phương án tối ưu của các bài toán đối ngẫu. Bài 1: f(x) = 2x1 – 2x2 + 3x3 → min 2x1 2 x 2 x 3 1; x1 x 2 3 x 3 1. xj > 0 (j = 1,3) Bài 2: f(x) = x1 + 2x2 - 3x3 → max x1 4 x 2 2 x 3 6; x1 x 2 2 x 3 6. 2x1 x 2 2 x 3 4 xj > 0 (j = 1,3) Bài 3: f(x) = x1 + 2x2 - 3x3 → max 4x1 4 x 2 2 x 3 6; x1 x 2 2 x 3 6 . 2x1 x 2 2 x 3 4 xj > 0 (j = 1,3) Bài 4: f(x) = 5x1 + 10x2 +7x3 → max x1 2 x 2 2 x 3 30; x1 2 x 2 x 3 25; 2x1 x 2 x 3 40. xj > 0 (j = 1,3) Bài 5: f(x) = -3x1 + x2 + 3x3 –x4 → min x1 2 x 2 x 3 x 4 2; 2x1 6 x 2 3 x 3 3 x 4 9. x1 x 2 x 3 x 4 6 xj > 0 (j = 1,4) Bài 6: 49
  50. f(x) = 3x1 - x2 + 2x3 +x4 → max 2x1 x 2 4 x 3 x 4 10; 3x1 2 x 2 x 3 2 x 4 8; 4x1 x 2 2 x 3 4 xj > 0 (j = 1,4) Bài 7: Cho bài toán gốc: (1) f(x) = 27x1 +50x2 + 18x3 → max x1 2 x 2 x 3 2; (2) 2x1 x 2 x 3 4; x1 2 x 2 x 3 2 (3) x1; x2 tuỳ ý; x3 0 ; j = 1,4 a. Lập bài toán đối ngẫu. b. Dựa vào nghiệm x0 = (5; 8; 0; 10) tìm nghiệm của bài toán đối ngẫu. Bài 9: Cho bài toán gốc: (1) f(x) = 2x1 +3x2 –x5 → min 2x2 2 x 3 x 4 x 5 24; (2) 3x1 3 x 2 4 x 3 2 x 5 72; x1 3 x 2 2 x 5 28 (3) x3 0 a. Viết bài toán đối ngẫu. b. Cho x0 = (28; 0; 0; 24; 0). Xác định phương án tối ưu của bài toán đối ngẫu. Bài 10: f(x) = 7x1 + 6x2 – 12x3 + x4 → max 2x1 2 x 2 3 x 3 2 x 4 8 3x2 2 x 3 2 x 4 1 2x1 3 x 3 x 4 10 a. Lập bài toán đối ngẫu. 50
  51. b. Giải bài toán đối ngẫu và suy ra kết quả của bài toán gốc. c. Dựa vào nghiệm. x6 = (0; 6; 0; 10) tìm nghiệm của bài toán đối ngẫu. Bài 11: Cho bài toán gốc. f(x) = 5x1 – 9x2 + 15x3 + 7x4 + 6x5 → min x1 3 x 2 x 3 x 4 x 5 1 4x1 x 3 2 x 4 x 5 4 x1 x 2 x 3 2 x 5 1 xj ≥ 0 (j = 2,5) a. Viết bài toán đối ngẫu. b. Cho x0 = (0; 1; 0; 2; 0). Xác định phương án tối ưu của bài toán đối ngẫu. Bài 12: Cho bài toán gốc: f(x) = -2x1 – 6x2 + 15x3 – x4 – 4x5 → max x1 4 x 2 2 x 3 5 x 4 9 x 5 3 x2 3 x 3 4 x 4 5 x 5 6 x2 x 3 x 4 x 5 1 xj ≥ 0 a. Viết bài toán đối ngẫu. b. Cho x0 = (0; 0; 16; 31; 14). Xác định phương án tối ưu của bài toán đối ngẫu. Bài 13: Giải bằng phương pháp đơn hình đối ngẫu các bài toán quy hoạch tuyến tính sau: 1. f(x) = x1 + 3x2 + 4x3 + x4 → min x1 2 x 2 2 x 4 8 3x2 x 3 4 x 4 18 3x x 2 x x 20 1 2 3 4 xj 0( j 1,4) 2. f(x) = 3x1 + 5x2 – 7x3 + x4 → min 2x2 x 3 3 x 4 10 x x 4 x x 3 1 2 3 4 3x 2 x 4 x 7 2 3 4 xj 0( j 1,4) 3. f(x) = -2x1 + 4x2 – 3x3 – x4 + 5x5 → min x1 x 2 3 x 3 x 4 x 5 6 2x x 4 x 15 2 3 5 5x 2 x x x 18 2 3 4 5 xj 0( j 1,5) 4. f(x) = 4x1 + 5x2 + 3x3 + 2x4 → min 51
  52. 2x1 x 2 3 x 3 21 x 2 x 3 x x 27 1 2 3 4 x 4 x 2 x 2 x 8 1 2 3 4 xj 0( j 1,4) 5. f(x) = 5x1 + x2 – 3x3 + x4 + 5x5 + 2x6 → min 5x1 4 x 2 2 x 5 3 x 6 18 9x x x 2 x 11 1 2 5 6 6x 5 x x 3 x 4 x 24 1 3 4 5 6 xj 0( j 1,6) Bài 14: Cho bài toán gốc. f(x) = -2x1 – 6x2 + 5x3 – x4 – 4x5 → max x1 4 x 2 2 x 3 5 x 4 9 x 5 3 x2 3 x 3 4 x 4 5 x 5 6 x2 x 3 x 4 x 5 1 xj ≥ 0 (j = 1,5) a. Viết bài toán đối ngẫu. b. Cho x = (0; 0; 16; 31; 14). Dựa vào nghiệm của bài toán gốc tìm nghiệm của bài toán đối ngẫu. Bài 15. Một Xí nghiệp xử lí giấy, có ba phân xưởng I, II, III cùng xửlí hai loại giấy A, B. Do hai phân xưởng có nhiều sự khác nhau, nên nếucùng đầu tư 10 triệu đồng vào mỗi phân xưởng thì cuối kỳ phân xưởng I xửlí được 6 tạ giấy loại A, 5 tạ giấy loại B. Trong khi có phân xưởng II xử líđược 4 tạ giấy loại A, 6 tạ giấy loại B. Phân xưởng III xử lí đư ợc 5 tạ giấyloại A, 4 tạ giấy loại B. Theo yêu cầu lao động thì cuối kỳ Xí nghiệp phải xửlí ít nhất 6 tấn giấy loại A, 8 tấn giấy loại B. Hỏi cần đầu tư vào mỗi phânxưởng bao nhiêu tiền để xí nghiệp hoàn thành công việc với giá tiền đầu tư là nhỏ nhất. Bài 16. Một gia đình cần ít nhất 1800 đơn vị prôtêin và 1500 đơn vịlipit trong thức ăn mỗi ngày. Một kilôgam thịt bò chứa 600 đơn vị prôtêin và600 đơn vị lipit, một kilôgam thịt heo chứa 600 đơn vị prôtêin và 300 đơn vịlipit, một kilôgam thịt gà chứa 600 đơn vị prôtêin và 600 đơn vị lipit. Giá mộtkilôgam thịt bò là 84 ngàn đồng, giá một kilôgam thịt heo là 71 ngàn đồng, giá một kilôgam thịt gà là 90 ngàn đồng. Hỏi một gia đình nên mua bao nhiêu kilôgam thịt mỗi loại để bảo đảm tốt khẩu phần ăn trong một ngày và tổng số tiền phải mua là nhỏ nhất 52
  53. Chương 4 BÀI TOÁN VẬN TẢI Mục tiêu: Sau khi đọc xong học sinh sẽ: - Hiểu được nội dung và đặc điểm của bài toán vận tải. - Hiểu được phương pháp thế vị để giải bài toán vận tải. - Vận dụng để giải các bài toán vận tải. 4.1. Nội dung và đặc điểm của bài toán. 4.1.1. Nội dung bài toán. a. Bài toán Có m địa điểm A1, A2, Am cùng sản xuất một loại hàng hoá với các lượng hàng tương ứng là a1, a2, , am. Có n nơi tiêu thụ loại hàng đó B1, B2, , Bn với các yêu cầu tương ứng là b1, b2, ,bn. Để đơn giản ta sẽ gọi. Ai: điểm phát i, i = 1, m Bj: điểm thu j, j = 1, n. Hàng có thể chở từ một điểm phát bất kỳ (i) tới một điểm thu bất kỳ (j). Ký hiệu: cij – chi phí vận chuyển chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j) xij - lượng hàng chuyên chở từ i tới j. Bài toán đặt ra là: xác định những đại lượng xij cho mọi con đường (i; j) sao cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết: m n ai  b j i 1 j 1 Tức là lượng hàng phát ra bằng đúng lượng hàng yêu cầu ở các điểm thu. b. Mô hình toán học. Dạng toán học của bài toán vận tải. m n  cij x ij min i 1 j 1 n  xij ai , i 1, m j 1 m x b, j 1, n  ij j i 1 x 0, i 1, m ; j 1, n ij m n ai, b j 0; a i  b j i 1 j 1 Bài toán trên được gọi là bài toán cân bằng thu phát. m n - Trường hợp ai  b j . Ta đưa về bài toán cân bằng thu phát bằng cách thêm i 1 j 1 m n vào một trạm thu giả Bn+1 với yêu cầu bn+1 = ai  b j , đồng thời cin+1 = 0 ( i ). Lượng i 1 j 1 53
  54. hàng lấy từ trạm phát Ai cung cấp cho trạm thu giả Bn+1, nghĩa là lượng hàng được giữ lại ở trạm phát Ai. m n - Trường hợp ai  b j .Ta đưa về bài toán cân bằng thu phát bằng cách thêm i 1 j 1 n m vào một trạm phát giả Am+1 với yêu cầu am+1 = bi  a j , đồng thời cm+1j = (j ). j 1 i 1 Lượng hàng lấy từ trạm phát giả Am+1 cung cấp cho trạm thu Bj, nghĩa là lượng hàng yêu cầu của trạm thu Bj không được thoả mãn. c. Bài toán vận tải dạng bảng. Ta đưa bài toán vận tải vào bảng gọi là bảng vận tải. Bj b1 b2 bj bn Ai c11 c12 c1j c1n a1 x11 x12 x1j x1n c21 c22 c2j c2n a2 x21 x22 x2j x2n ci1 ci2 cij cin ai xi1 xi2 xij xin cml cm2 cmi cmn am xm1 xm2 xmj xmn Các khái niệm về bài toán dạng bảng: + Ô chọn: Là ô có lượng hang xij > 0, còn gọi là ô sử dụng. + Ô loại: Là ô không có hàng, tức là xij = 0. + Dây chuyền: Là một đoạn thẳng hay một hãy liên tiếp các đoạn thẳng gấp khúc mà hai đầu mút là hai ô chỉ nằm trên cùng một hàng hoặc một cột với một ô chọn khác thuộc dây chuyền của bảng vận tải. + Chu trình: Là một dây chuyền khép kín. Như vậy một hàng hoặc một cột mà chu trình đi qua thì chỉ đi qua hai ô và do đó, số ô ít nhất của một chu trình là 4. + Ma trận X = (xij)mxn thoả mãn hệ điều kiện ràng buộc được gọi là một phương án của bài toán. + Phương án X = (xij)mxn được gọi là phương án cực biên của bài toán vận tải nếu tập hợp các ô tương ứng với các thành phần dương của nó không tạo thành chu trình. + Phương án X = (xij)mxn được gọi là phương án cực biên không suy biến nếu nó có đúng m + n – 1 ô chọn. + Phương án X = (xij)mxn được gọi là phương án cực biên suy biến nếu nó có ít hơn m + n – 1 ô chọn. 54
  55. + Phương án X = (xij)mxn được gọi là phương án tối ưu (hay là nghiệm) của bài toán nếu nó thoả mãn điều kiện (5.1), ký hiệu là X. 4.1.2. Đặc điểm của bài toán. - Một phương án cực biên có tối đa m + n – 1 thành phần dương. - Các véc tơ Aj tương ứng với biến xij có thành phần i và thành phần m + j bằng 1 còn các thành phần còn lại đều bằng 0. - Bài toán luôn có lời giải. 4.2. Phương pháp thế vị để giải bài toán. 4.2.1. Phương pháp tìm phương án cực biên xuất phát. Để xây dựng một phương án cực biên xuất phát người ta dùng một trong 3 phương pháp sau: *Phương pháp góc Tây - Bắc: Bước 1: Chọn ô ở dòng 1, cột 1 của bảng vận tải. Bước 2: Phân lượng hàng h a1, b 1 vào ô (1; 1) Bước 3: Đánh dấu hàng (cột), theo đó lượng hàng ở trạm phát (trạm thu) đã hết (đã đủ). Bước 4: Quay trở về bước 1 thực hiện công việc ở những ô còn lại. *Phương pháp chi phí nhỏ nhất: Bước 1: Chọn ô có cước phí thấp nhất, giả sử là ô (i; j). Bước 2: Phân lượng hàng h = ai, b j  vào ô (i; j). Bước 3: Đánh dấu các ô thuộc hàng i nếu trạm phát Ai đã hết hàng hoặc cột j nếu trạm thu Bj đã nhận đủ hàng. Bước 4: Quay trở lại bước 1 thực hiện công việc ở những ô còn lại. *Phương pháp xấp xỉ Fogels: - Định nghĩa độ lệch của hàng (cột) là hiệu số giữa ô có cước phí thấp thứ nhì trừ đi ô có cước phí thấp thứ nhất ở hàng (cột) đó. Bước 1: Chọn hàng hoặc cột có độ lệch lớn nhất. Bước 2: Chọn ô có cước phí thấp nhất thuộc hàng hoặc cột đó, giả sử là ô (i; j). Bước 3: Phân lượng hàng h = ai, b j  vào ô (i; j). Bước 4: Đánh dấu các ô thuộc hàng i nếu trạm phát Ai đã hết hàng hoặc cột j nếu trạm thu Bj đã nhận đủ hàng. Quay trở về bước 1 tiếp tục thực hiện thuật toán. 4.2.2. Phương pháp thế vị giải bài toán vận tải. a. Tiêu chuẩn tối ưu. Phương án cực biên không suy biến X = (xij)mxn được gọi là phương án tối ưu khi và chỉ khi tồn tại các số ui (i = 1, , m) cho các hàng và các số vj (j = 1, , n) cho các cột của ui v j cij( i ; j ) : x ij 0(*) bảng vận tải sao cho ui v j cij( i ; j ) : x ij 0( ) Phương trình (*) ứng với ô (i; j) là ô chọn. Phương trình ( ) ứng với ô (i; j) là ô loại. 55
  56. Các số ui và vj được gọi là hệ thống thế vị, trong đó ui được gọi là thế vị hàng, vj được gọi là thế vị cột. b. Thuật toán thế vị. 0 Bước 1: Tìm phương án cực biên xuất phát X = (xij)mxn. Sử dụng một trong 3 phương pháp ở trên. Nếu phương án tìm được là phương án suy biến thì ta bổ sung ô chọn không để được phương án cực biên không suy biến, ô chọn này có vai trò như các ô chọn khác. Bước 2: Kiểm tra tính tối ưu của phương án. + Xây dựng hệ thống thế vị. Cho ui một giá trị tuỳ ý nào đó thì mọi giá trị khác đều xác định được một cách duy nhất do (*) có (n+m) ẩn và (m+n-1) phương trình độc lập tuyến tính. + Tính các số kiểm tra ij . Đặt ij ui v j c ij ( i 1, m , j 1, n ) . Tính các ij ứng với các ô loại. + Nếu ij 0(i 1, m , j 1, n )thì phương án đang xét là phương án tối ưu.  + Nếu  ij 0(i 1, m , j 1, n ) thì phương án đang xét chưa tối ưu, chuyển sang bước 3. Bước 3: Xây dựng phương án mới. + Chọn ô điều chỉnh: Ô (r,s) gọi là ô điều chỉnh nếu: rs max ij 0( i 1, m , j 1, n ) + Tìm chu trình điều chỉnh: Là chu trình với ô xuất phát là ô điều chỉnh, các ô còn lại là ô chọn. Gọi V là tập hợp các ô thuộc chu trình điều chỉnh. + Đánh dấu các ô của chu trình, bắt đầu từ ô điều chỉnh đánh dấu (+) rồi xen kẽ nhau đánh dấu (-), (+) cho đến hết chu trình. Gọi V + là tập hợp các ô có dấu (+), V- là tập các ô có dấu (-). Khi đó, VVV  . + Xác định lượng hàng điều chỉnh: q min xij : ( i , j ) V , q 0. 1 + Điều chỉnh sang phương án mới: X = (xij) mxn với: xij ,(,) i j V xij q,(,) i j V xij q,(,) i j V Gọi X1 đóng vai trò như X0 rồi quay lại bước 2 và lặp cho tới khi tìm được phương án tối ưu. *Chú ý: - Nếu ô điều chỉnh không duy nhất thì ta xét theo hàng từ trên xuống dưới trong bảng vận tải gặp ô nào trước thì ta chọn ô đó làm ô điều chỉnh. - Nếu có thể thì chọn ô (i0, j0) thoả mãn: q. i0 j 0 m ax q . ij 0 thì giá trị hàm mục tiêu giảm nhanh hơn. c. Ví dụ. Ví dụ 1: Giải bài toán vận tải với số tiền cho trong bảng sau: 56
  57. Thu 46 45 76 20 52 Phát 79 10 1 5 13 8 50 5 6 10 8 13 60 3 2 8 9 6 50 13 5 7 10 13 Giải: Bước 1: Tìm phương án cực biên xuất phát: Sử dụng phương pháp chi phí nhỏ nhất xây dựng phương án cực biên ta được phương án cực biên không suy biến cho trong bảng sau: Thu 46 45 76 20 52 Phát 10 1 5 13 8 79 x 45 34 x x 5 6 10 8 13 50 x x x 20 30 3 2 8 9 6 60 46 x x x 14 13 5 7 10 13 50 x x 42 x 30 Bước 2: Kiểm tra tính tối ưu của phương án: + Xây dựng hệ thống thế vị: Cho u4 = 0, các ô (4,3), (4,5) là các ô cơ sở nên tính được v3 = 7 và v5 = 13. Xét cột 3 chẳng hạn ta thấy (1,3) là ô cơ sở nên tính được u1 = 7-5=2, Tiếp tục tính tương tự sẽ xác định được toàn bộ các thế vị hàng và cột như trong bảng dưới: + Tính các số kiểm tra: Tính các ij (i 1,4, j 1,5) ta thấy các 15 3 0, 21 5 0nên phương án đang xét chưa tối ưu, ta chuyển sang bước 3. Thu 46 45 76 20 52 ui Phát 10 1 5 13 8 -2 79 -2 45 34 -7 3 5 6 10 8 13 50 0 5 -3 -3 20 30 3 2 8 9 6 60 -7 46 -6 -8 -8 14 13 5 7 10 13 50 0 3 -2 42 -2 8 Vj 10 3 7 8 13 57
  58. Bước 3: Xây dựng phương án mới: + Chọn ô điều chỉnh: 21 max 5;3 5nên chọn ô (2, 1) làm ô điều chỉnh đánh dấu (+) vào ô điều chỉnh. + Chọn chu trình điều chỉnh: Chu trình điều chỉnh như trong bảng sau: Thu 46 45 76 20 52 ui Phát 10 1 5 13 8 -2 79 -2 45 34 -7 3 5 6 10 8 13 50 0 (+) 5 -3 -3 20 (-) 30 3 2 8 9 6 60 -7 (-) 46 -6 -8 -8 (+) 14 13 5 7 10 13 50 0 - 3 -2 42 -2 8 Vj 10 3 7 8 13 + Xác định lượng hàng điều chỉnh: q min 46;30 30 + Điều chỉnh sang phương án mới: 1 1 X = ( xij ) theo công thức cho trong bước 3 của thuật toán ta được bảng sau: Thu 46 45 76 20 52 ui Phát 10 1 5 13 8 79 -2 -2 45 34 -2 3 5 6 10 8 13 50 -5 (+) 30 -8 -8 (-) 20 -5 3 2 8 9 6 60 -7 (-) 46 -6 -8 -3 (+) 44 13 5 7 10 13 50 0 - 3 -2 42 (+) 3 (-) 8 Vj 10 3 7 13 13 + Lặp lại quá trình ta được chu trình như bảng trên. Ta được: q min 16;20;8 8 + Điều chỉnh sang phương án mới X2 cho trong bảng dưới: 58
  59. Thu 46 45 76 20 52 ui Phát 10 1 5 13 8 79 -2 -2 45 34 -5 0 5 6 10 8 13 50 -2 38 -5 -5 12 -5 3 2 8 9 6 60 -4 8 -3 -5 -3 52 13 5 7 10 13 50 8 0 -6 -2 42 -3 Vj 7 3 7 10 10 Ta thấy mọi ij 0(i 1,4, j 1,5) nên phương án tương ứng ở bảng trên là tối ưu với giá trị hàm mục tiêu là f* = 45 * 1 + 34 * 5 + 12 * 8 + 8*3 + 52*6 + 42*7 + 8*10 = 1211. 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. 59
  60. BÀI TẬP CHƯƠNG 4 Giải các bài toán vận tải sau, sử dụng cả 3 phương pháp tìm phương án cực biên xuất phát: Bài 1: Thu 60 70 40 30 Phát 60 10 0 30 100 2 1 4 3 X 0 60 20 0 ; f ( X ) 460 Đáp số: 80 5 3 2 6 0 0 20 0 20 6 2 1 5 Bài 2: Thu 10 10 10 20 20 Phát 0 5 0 0 0 5 5 1 4 6 7 10 0 0 0 5 15 3 4 2 7 8 Đáp số: X ; f ( X ) 435 0 5 10 5 0 20 4 3 1 7 9 0 0 0 15 15 30 6 5 4 9 11 Bài 3: Thu 20 100 145 30 150 Phát Đáp số: 120 6 3 1 4 5 0 0 120 0 0 150 1 2 5 4 3 0 0 0 0 150 X ; f ( X ) 940 150 2 4 3 1 6 20 75 25 30 0 25 3 1 4 2 7 0 25 0 0 0 60