›
›

Giáo trình Toán kinh tế

pdf 59 trang vanle 3260
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán kinh tế", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

  • pdfgiao_trinh_toan_kinh_te.pdf

Nội dung text: Giáo trình Toán kinh tế

  1. UỶ BAN NHÂN DÂN TỈNH NGHỆ AN TRƢỜNG ĐẠI HỌC KINH TẾ GIÁO TRÌNH TOÁN KINH TẾ (Dùng cho hệ Đại học và Cao đẳng) Lƣu hành nội bộ Vinh, năm 2014
  2. UỶ BAN NHÂN DÂN TỈNH NGHỆ AN TRƢỜNG ĐẠI HỌC KINH TẾ GIÁO TRÌNH TOÁN KINH TẾ (Dùng cho hệ Đại học và Cao đẳng) Lƣu hành nội bộ Th.S Nguyễn Thị Hà (Chủ biên) Th.S Trần Hà Lan Vinh, năm 2014
  3. MỤC LỤC Chƣơng 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - 2 - 1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - 2 - 1.1. Bài toán lập kế hoạch sản xuất - 2 - 1.2. Bài toán phân công lao động - 3 - 1.3. Bài toán vận tải - 4 - 2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (QHTT) - 5 - 2.1. Bài toán quy hoạch tuyến tính dạng tổng quát - 5 - 2.2. Bài toán quy hoạch tuyến tính dạng chính tắc và chuẩn tắc - 7 - 2.3. Chuyển đổi dạng bài toán quy hoạch tuyến tính - 9 - 3. THUẬT TOÁN ĐỒ THỊ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN - 11 - 3.1. Nhận xét - 11 - 3.2. Thuật toán đồ thị giải bài toán quy hoạch tuyến tính - 11 - n 4. MỘT SỐ YẾU TỐ HÌNH HỌC TRONG KHÔNG GIAN ¡ - 14 - 4.1. Tập hợp lồi - 14 - 4.2. Tính chất của tập hợp lồi - 15 - 5. TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH - 15 - 5.1. Các giả thiết ban đầu - 15 - 5.2. Các tính chất cơ bản của bài toán quy hoạch tuyến tính - 16 - 6. PHƢƠNG PHÁP ĐƠN HÌNH - 25 - 6.1. Cơ sở lý luận của phƣơng pháp đơn hình - 25 - 6.2. Công thức đổi tọa độ và bảng đơn hình - 30 - 6.3. Bài toán suy biến - 35 - 7. PHƢƠNG PHÁP TÌM PHƢƠNG ÁN CỰC BIÊN XUẤT PHÁT - 37 - 7.1. Bài toán giả tạo - 37 - 7.2. Mối quan hệ về phƣơng án tối ƣu của bài toán giả tạo và bài toán chính tắc tƣơng ứng - 39 - Chƣơng 2 - 42 - BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU - 42 - 1. KHÁI NIỆM BÀI TOÁN QHTT ĐỐI NGẪU - 42 - 1.1. Bài toán quy hoạch tuyến tính đối ngẫu không đối xứng - 42 - 1.2. Quy tắc thành lập bài toán đối ngẫu - 44 - LƢỢC ĐỒ TỔNG QUÁT - 45 - Dạng 1. - 45 - Dạng 2. - 45 - 1.3. Bài toán quy hoạch tuyến tính đối ngẫu đối xứng - 46 - 2. CÁC ĐỊNH LÝ ĐỐI NGẪU - 48 - 3. PHƢƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU - 52 - 3.1. Nội dung phƣơng pháp - 52 - 3.2. Thuật toán đơn hình đối ngẫu - 53 - Chƣơng 3 - 56 - BÀI TOÁN VẬN TẢI - 56 - 1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI - 56 - 1.1. Nội dung kinh tế và các dạng toán học của bài toán vận tải - 56 - 1.2. Mô hình bảng của bài toán vận tải - 60 - 1.3. Tính chất của bài toán vận tải cân bằng thu phát - 62 - 2. THUẬT TOÁN THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT - 64 - 2.1. Phƣơng pháp tìm phƣơng án cực biên xuất phát - 64 - 2.2. Tiêu chuẩn tối ƣu cho một phƣơng án của bài toán vận tải cân bằng thu phát - 68 - 2.3. Phƣơng pháp cải tiến phƣơng án - 70 -
  4. 4. BÀI TOÁN PHÂN PHỐI - 88 - 4.1. Định nghĩa. - 88 - 4.2. Phƣơng pháp giải - 88 - 5. BÀI TOÁN Ô CẤM - 93 - CHƢƠNG 4. MỘT SỐ BÀI TOÁN ỨNG DỤNG BÀI - 97 - TOÁN QUY HOẠCH TUYẾN TÍNH - 97 - I. BÀI TOÁN SẢN XUẤT ĐỒNG BỘ - 97 - 1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN SẢN XUẤT ĐỒNG BỘ - 97 - 1.1. Nội dung kinh tế và mô hình toán học của bài toán sản xuất đồng bộ - 97 - 1.2. Tính chất của bài toán sản xuất đồng bộ - 101 - 2. PHƢƠNG PHÁP NHÂN TỬ GIẢI BÀI TOÁN SẢN XUẤT ĐỒNG BỘ - 105 - 2.1. Phƣơng pháp tìm phƣơng án cực biên suy rộng ban đầu - 105 - 2.2. Xây dựng hệ thống số kiểm tra và tiêu chuẩn tối ƣu - 108 - 2.3. Điều chỉnh phƣơng án - 109 - 2.4. Thuật toán nhân tử giải bài toán sản xuất đồng bộ - 111 - II. BÀI TOÁN TRÒ CHƠI MA TRẬN - 115 - 1. MỘT SỐ KHÁI NIỆM MỞ ĐẦU - 115 - 1.1. Ví dụ về trò chơi ma trận - 115 - 1.2. Bài toán trò chơi ma trận - 115 - 1.3. Hàm thu hoạch của P - 117 - 2. ĐIỂM YÊN NGỰA VÀ CHIẾN LƢỢC TỐI ƢU - 118 - 2.1. Điểm yên ngựa - 118 - 2.2. Chiến lƣợc tối ƣu - 119 - 2.3. Trò chơi đối xứng - 120 - 3. PHƢƠNG PHÁP TÌM CHIẾN LƢỢC TỐI ƢU CHO BÀI TOÁN TRÒ CHƠI MA TRẬN - 121 - 3.1. Đƣa trò chơi ma trận về bài toán quy hoạch tuyến tính - 121 - 3.2. Phƣơng pháp tìm chiến lƣợc tối ƣu cho bài toán trò chơi ma trận - 123 - TÀI LIỆU THAM KHẢO - 126 -
  5. LỜI NÓI ĐẦU Toán học và kinh tế là hai lĩnh vực có mối quan hệ gắn bó với nhau. Kinh tế là nguồn cảm hứng cho toán học thực hiện khả năng tiềm năng của mình, còn toán học là công cụ giúp cho việc phân tích, giải quyết các vấn đề kinh tế một cách chặt chẽ, hợp lý và hiệu quả. Toán kinh tế là việc nghiên cứu để mô tả các vấn đề kinh tế dƣới dạng mô hình toán học thích hợp và từ góc độ toán học sẽ tìm ra lời giải cho mô hình đó, từ đó giúp các nhà kinh tế tìm ra các giải pháp tối ƣu cho bài toán kinh tế. Để đáp ứng nhu cầu giảng dạy và học tập môn Toán kinh tế cho sinh viên hệ đại học và cao đẳng, chúng tôi đã biên soạn cuốn giáo trình này. Giáo trình không đi sâu vào các vấn đề lý luận và các kỹ thuật toán học phức tạp mà chỉ tập trung trình bày những nội dung cơ bản và các thuật toán chính của lý thuyết tối ƣu tuyến tính. Nhằm giúp sinh viên rèn luyện kỹ năng trong giáo trình có đầy đủ các ví dụ cụ thể mô tả từng tình huống, hƣớng dẫn tỉ mỉ toàn bộ quá trình giải quyết vấn đề. Nội dung giáo trình gồm 4 chƣơng: Chương 1. Bài toán quy hoạch tuyến tính Chương 2. Bài toán quy hoạch tuyến tính đối ngẫu Chương 3. Bài toán vận tải Chương 4. Một số bài toán ứng dụng của bài toán quy hoạch tuyến tính Mặc dù có nhiều cố gắng, nhƣng giáo trình này chắc chắn không tránh khỏi những thiếu sót. Chúng tôi rất mong đƣợc bạn đọc góp ý để cuốn sách ngày càng hoàn thiện. Các tác giả - 1 -
  6. Chƣơng 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1. Bài toán lập kế hoạch sản xuất 1.1.1. Nội dung bài toán Một cơ sở sản xuất có thể sản xuất đƣợc hai loại sản phẩm A và B, từ các nguyên liệu I, II, III. Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản phẩm, cũng nhƣ dự trữ nguyên liệu cho trong Bảng 1.1. Bảng 1.1 Nguyên liệu Lãi I II III (đơn vị tiền) Sản phẩm A 2 0 1 3 B 1 1 0 5 Dự trữ 8 4 3 Hãy lập bài toán thể hiện kế hoạch sản xuất sao cho có tổng số lãi lớn nhất và phù hợp với điều kiện dự trữ nguyên liệu. 1.1.2. Mô hình toán học của bài toán Gọi x1, x2 lần lƣợt là số sản phẩm A và B đƣợc sản xuất. Khi đó: Tổng số lãi là: 3x1 + 5x2 Tổng số nguyên liệu I cần sử dụng là: 2x1 + x2 Tổng số nguyên liệu II cần sử dụng là: x2 Tổng số nguyên liệu III cần sử dụng là: x1 Theo bài ra, ta có mô hình toán học: Tìm X(x1, x2) sao cho f(X) = 3x1 + 5x2 max - 2 -
  7. 2x12 x 8 x2 4 với điều kiện . x1 3 xj 0, j 1,2 1.2. Bài toán phân công lao động 1.2.1. Nội dung bài toán Một phân xƣởng có 4 dây chuyền sản xuất khác nhau có thể sản xuất 3 loại sản phẩm. Lƣợng sản phẩm mỗi loại sản xuất ra đƣợc khi sử dụng một dây chuyền sản xuất mỗi loại trong một giờ và chi phí sản xuất ở dây chuyền đó sau một giờ hoạt động cùng với nhu cầu tối thiểu về các sản phẩm đƣợc cho bởi Bảng 1.2. Bảng 1.2 Dây chuyền sản xuất Nhu cầu Sản phẩm (SP) I II III IV tối thiểu SP 1 2 3 1 1 1600 SP 2 1 2 3 4 2200 SP 3 3 1 4 5 2000 Chi phí (1000đ) 10 5 13 16 Hãy lập bài toán để bố trí thời gian cho các dây chuyền sản xuất sao cho thỏa mãn nhu cầu tối thiểu về các sản phẩm đồng thời tổng chi phí sản xuất thấp nhất. 1.2.2. Mô hình toán học của bài toán Gọi xj là thời gian (giờ) áp dụng dây chuyền sản xuất thứ j (j = 1,4) khi đó: Tổng chi phí sản xuất là: 10x1 + 5x2 + 13x3 + 16x4 (1000đ) Tổng lƣợng sản phẩm 1 sản xuất ra là: 2x1 + 3x2 + x3 + x4 Tổng lƣợng sản phẩm 2 sản xuất ra là: x1 + 2x2 + 3x3 + 4x4 Tổng lƣợng sản phẩm 3 sản xuất ra là: 3x1 + x2 + 4x3 + 5x4 Theo bài ra, ta có mô hình toán học: Tìm X(x1, x2, x3, x4) sao cho f(X) = 10x1 + 5x2 + 13x3 + 16x4 min - 3 -
  8. 2x1 3x 2 x 3 x 4 1600 x1 2x 2 3x 3 4x 4 2200 với điều kiện . 3x1 x 2 4x 3 5x 4 2000 xj 0, j 1,4 1.3. Bài toán vận tải 1.3.1. Nội dung bài toán Một đơn vị vận tải cần vận chuyển xi măng từ 3 kho K1, K2, K3 tới 4 công trƣờng xây dựng T1, T2, T3, T4. Cho biết lƣợng xi măng có ở mỗi kho, lƣợng xi măng cần ở mỗi công trƣờng và giá cƣớc vận chuyển (ngàn đồng) 1 tấn xi măng từ mỗi kho tới mỗi công trƣờng nhƣ Bảng 1.3. Bảng 1.3 Công trƣờng xây dựng Kho xi măng T1: 130 tấn T2: 160 tấn T3: 120 tấn T4: 140 tấn K1: 170 tấn 20 18 22 25 K2: 200 tấn 15 25 30 15 K3: 180 tấn 45 30 40 35 Hãy lập bài toán tìm kế hoạch vận chuyển xi măng từ các kho tới các công trƣờng sao cho tổng chi phí vận chuyển là nhỏ nhất và mọi kho đều phát hết lƣợng xi măng có, mọi công trƣờng nhận đủ lƣợng xi măng cần? 1.3.2. Mô hình toán học của bài toán Gọi xij là lƣợng xi măng cần vận chuyển từ kho i (i = 1, 2, 3) tới công trƣờng j (j = 1, 2, 3, 4). Khi đó: Kho K1 phát hết lƣợng xi măng có: x11 + x12 + x13 + x14 = 170 Kho K2 phát hết lƣợng xi măng có: x21 + x22 + x23 + x24 = 200 Kho K3 phát hết lƣợng xi măng có: x31 + x32 + x33 + x34 = 180 Công trƣờng T1 nhận đủ số xi măng cần: x11 + x21 + x31 = 130 Công trƣờng T2 nhận đủ số xi măng cần: x12 + x22 + x32 = 160 Công trƣờng T3 nhận đủ số xi măng cần: x13 + x23 + x33 = 120 - 4 -
  9. Công trƣờng T4 nhận đủ số xi măng cần: x14 + x24 + x34 = 130 Lƣợng hàng vận chuyển không âm: xij 0, i = 1,3, j = 1,4 Tổng chi phí vận chuyển: f(X) = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 + 30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34. Vậy mô hình toán học của bài toán là: Tìm X = [xij]3x4 sao cho f(X) min với X thỏa mãn các điều kiện trên. Tổng quát: Gọi m là số kho chứa hàng (điểm phát), n là số nơi tiêu thụ hàng (điểm thu). ai là lƣợng hàng có (cung) ở điểm phát thứ i (i = 1,m ) bj là lƣợng hàng cần (cầu) ở điểm thu thứ j (j = 1,n ) cij là chi phí vận chuyển một đơn vị hàng từ điểm phát i tới điểm thu j xij là lƣợng hàng vận chuyển cần tìm từ điểm phát i tới điểm thu j. Mô hình toán học của bài toán vận tải có dạng: mn f (X) cij x ij min i 1 j 1 n x a ,i 1,m ij i j1 m với điều kiện x b , j 1,n ij j i1 x 0,i 1,m; j 1,n ij 2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (QHTT) 2.1. Bài toán quy hoạch tuyến tính dạng tổng quát Định nghĩa 1.1. Từ các bài toán thực tế đã nêu cùng rất nhiều bài toán khác, ta có thể thấy bài toán QHTT dạng tổng quát có dạng sau: Tìm véctơ X(x1, x2, , xn) sao cho hàm số n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (max) (1.1) j1 - 5 -
  10. n aij x j b i ,i 1,p (1.2) j1 n aij x j b i ,i p 1,q (1.3) với điều kiện: j1 n aij x j b i ,i q 1,m (1.4) j1 xjj 0, j 1,k; x 0, j k 1,r; (1.5) trong đó: p, q, m, k, n, r là các số nguyên thỏa mãn: 0 p q m; 0 k r n. xj là biến số, các hệ số cj, aij, bi (j = 1,n ; i = 1,m ). n Khi đó: ▪ Hàm số f(X) = cxjj đƣợc gọi là hàm mục tiêu. j1 ▪ Các bất phƣơng trình (1.2) - (1.5) đƣợc gọi là hệ ràng buộc của bài toán. Các ràng buộc (1.2) - (1.4) đƣợc gọi là các ràng buộc chính (hay ràng buộc cưỡng bức). Các ràng buộc (1.5) gọi là ràng buộc về dấu (hay ràng buộc tự nhiên) của bài toán. Định nghĩa 1.2. Véc tơ X(x1, x2, , xn) thỏa mãn hệ ràng buộc (1.2) - (1.5) đƣợc gọi là phương án của bài toán Ký hiệu tập hợp các phƣơng án của bài toán QHTT là . Ta có 3 khả năng: - Bài toán (1.2) (1.5) có vô số phƣơng án, tức là tập có vô số phần tử. - Bài toán (1.2) (1.5) chỉ có 1 phƣơng án, tức là tập chỉ có 1 phần tử. - Bài toán (1.2) (1.5) không có phƣơng án nào, tức là tập = . * * * * Định nghĩa 1.3. Phƣơng án X ( x1 , x2 , , xn ) của bài toán (1.2) (1.5) đƣợc gọi là phương án tối ưu (PATƢ) của bài toán nếu: f(X*) f(X), X (đối với bài toán f(X) min) f(X*) f(X), X (đối với bài toán f(X) max) Chú ý: Tập PATƢ của bài toán QHTT hoặc một điểm hoặc vô số điểm hoặc không có điểm nào. - 6 -
  11. Định nghĩa 1.4. Nếu bài toán QHTT có phƣơng án tối ƣu thì bài toán đƣợc gọi là giải được (hay bài toán có lời giải) và phƣơng án tối ƣu của bài toán còn gọi là lời giải của bài toán. Nếu bài toán QHTT không có phƣơng án tối ƣu thì bài toán đƣợc gọi là không giải được (hay bài toán không có lời giải). Định nghĩa 1.5. Nếu phƣơng án X(x1, x2, , xn) của một bài toán QHTT làm thỏa n mãn aij x j b i thì phƣơng án X đƣợc gọi là thỏa mãn chặt ràng buộc i tƣơng ứng j1 (1.2), hoặc (1.3) hoặc (1.4). Nếu phƣơng án X(x1, x2, , xn) có xj = 0 thì phƣơng án X đƣợc gọi là thỏa mãn chặt ràng buộc về dấu tƣơng ứng (nếu có ràng buộc loại xj 0 hoặc xj 0). n n Nếu phƣơng án X(x1, x2, , xn) thỏa mãn aij x j b i (hoặc aij x j b i hoặc j1 j1 xj > 0 hoặc xj < 0) thì phƣơng án X đƣợc gọi là thỏa mãn lỏng ràng buộc tƣơng ứng (nếu có). 2.2. Bài toán quy hoạch tuyến tính dạng chính tắc và chuẩn tắc 2.2.1. Bài toán quy hoạch tuyến tính dạng chính tắc Bài toán QHTT chính tắc có dạng: Tìm X(x1, x2, , xn) sao cho n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.6) j1 n aij x j b i ,i 1,m (1.7) với điều kiện j1 xj 0, j 1,n (1.8) a11 a 12 a 1n a a a Nếu ký hiệu A = 21 22 2n là ma trận cấp m n, gọi là ma trận am1 a m2 a mn ràng buộc của bài toán; - 7 -
  12. x1 b1 0 x b 0 X = 2 ; B = 2 ; O = x b n n1 m m1 0 n1 Khi đó bài toán QHTT chính tắc (1.6) – (1.8) viết đƣợc dƣới dạng ma trận sau: f(X) = CX min AX B với điều kiện X0 a1j a Nếu ký hiệu: A = 2j là véctơ cột thứ j (j =1,n ) của ma trận A. Khi đó bài j a mj toán QHTT chính tắc (1.6) – (1.8) viết đƣợc dƣới dạng véctơ sau đây: n f (X) cjj x min j1 n xjj A B với điều kiện j1 xj 0, j 1,n Ma trận A A B đƣợc gọi là ma trận bổ sung (hay còn gọi là ma trận mở rộng) của bài toán QHTT dạng chính tắc (1.6) – (1.8). 2.2.2. Bài toán quy hoạch tuyến tính dạng chuẩn tắc. Bài toán QHTT chuẩn tắc có dạng: Tìm X(x1, x2, , xn) sao cho n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.9) j1 n aij x j b i ,i 1,m (1.10) với điều kiện j1 xj 0, j 1,n (1.11) - 8 -
  13. Bài toán QHTT dạng chuẩn tắc (1.9) – (1.11) viết đƣợc dƣới dạng ma trận nhƣ sau: f(X) = CX min AX B với điều kiện X0 Bài toán QHTT dạng chuẩn tắc (1.9) – (1.11) viết đƣợc dƣới dạng véctơ sau đây: n f (X) cjj x min j1 n xjj A B với điều kiện j1 xj 0, j 1,n 2.3. Chuyển đổi dạng bài toán quy hoạch tuyến tính Bằng cách thực hiện các phép biến đổi nêu dƣới đây, ta có thể chuyển bài toán QHTT bất kỳ về bài toán QHTT chính tắc, chuẩn tắc. n a) Nếu ràng buộc có dạng aij x j b i thì ta thêm biến phụ xn + i 0 để có j1 n aij x j x n i b i . j1 n b) Nếu ràng buộc có dạng aij x j b i thì ta thêm biến phụ xn + i 0 để có j1 n aij x j x n i b i . j1 c) Nếu có ẩn xj nào đó không có ràng buộc về dấu thì ta thay xj bởi hai biến phụ không âm xjj 0 và x 0 sao cho: xj = x j x j . - 9 -
  14. n d) Mỗi ràng buộc đẳng thức aij x j b i có thể thay bằng 2 ràng buộc bất đẳng j1 n n thức aij x j b i và aij x j b i . j1 j1 n n e) Một ràng buộc aij x j b i có thể viết lại thành aij x j b i hoặc ngƣợc lại. j1 j1 f) Bài toán tìm cực đạt f max có thể đƣa về bài toán tìm cực tiểu g = -f min. Nhận xét: i) Khi đƣa biến phụ xn + i vào thì hệ số của nó trong hàm mục tiêu f(X) là Cn + i = 0. ii) Khi đƣa biến phụ x j , x j vào thì hệ số của nó trong hàm mục f(X) tƣơng ứng là Cj = Cj , Cj = - Cj. iii) Mọi bài toán QHTT đều đƣa đƣợc về dạng chính tắc và việc giải bài toán QHTT đã cho tƣơng đƣơng với việc giải bài toán QHTT chính tắc tƣơng ứng với nó, theo nghĩa là nếu bài toán dạng chính tắc có PATƢ thì từ đó suy ra đƣợc PATƢ của bài toán ban đầu, còn nếu bài toán chính tắc không có PATƢ thì bài toán ban đầu cũng không có PATƢ. Nói cách khác: Bài toán ban đầu có PATƢ khi và chỉ khi bài toán dạng chính tắc tƣơng ứng với nó có PATƢ. Nhƣ vậy, ta chỉ cần tìm cách giải bài toán QHTT chính tắc. Ví dụ 1.1: Đƣa bài toán QHTT sau về dạng chính tắc, dạng chuẩn tắc. f(X) = 2x1 – x2 min x1 2x 2 x 3 2 2x 2x x 3 với điều kiện 1 2 3 x1 x 2 x 3 4 x23 0;x 0 Giải: * Dạng chính tắc: Bằng cách thay x1 = x4 – x5 với x4, x5 0 và thêm hai biến phụ x6 , x7 0, ta đi đến bài toán: f(X) = – x2 + 2x4 – 2x5 min - 10 -
  15. 2x2 x 3 x 4 x 5 x 6 2 2x2 x 3 2x 4 2x 5 x 7 3 với điều kiện x2 x 3 x 4 x 5 4 xj 0; j 2,7 * Dạng chuẩn tắc: Bằng cách thay x1 = x4 – x5 với x4, x5 0, đổi dấu hai vế bất đẳng thức đầu và thay bất đẳng thức cuối bằng hai bất đẳng thức , ta đi đến bài toán: f(X) = – x2 + 2x4 – 2x5 min 2x2 x 3 x 4 x 5 2 2x2 x 3 2x 4 2x 5 3 với điều kiện x2 x 3 x 4 x 5 4 x2 x 3 x 4 x 5 4 xj 0, j 2,5 3. THUẬT TOÁN ĐỒ THỊ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN 3.1. Nhận xét Trong mặt phẳng ¡ 2 với hệ trục tọa độ vuông góc xOy ta có: * Phƣơng trình ax + by = c, biểu diễn một đƣờng thẳng vuông góc với véctơ pháp tuyến n (a, b). * Các điểm (x, y) thỏa mãn ax + by c nằm trên nửa mặt phẳng giới hạn bởi đƣờng thẳng ax + by = c. * Phƣơng trình ax + by = f, khi f thay đổi sẽ cho ta họ đƣờng thẳng song song với véctơ chỉ phƣơng v( b,a) . Giá trị f càng lớn khi dịch chuyển các đƣờng của họ theo hƣớng (a, b). Vì vậy hình ảnh hình học của bài toán QHTT trong ¡ 2 đƣợc mô tả theo thuật toán đồ thị nhƣ sau. 3.2. Thuật toán đồ thị giải bài toán quy hoạch tuyến tính Xét bài toán QHTT với hai biến số - 11 -
  16. min(max){f(X) = c1x + c2y: X = (x, y) }, trong đó là tập phƣơng án của bài toán. Bước 1. Biểu diễn các điều kiện buộc của lên mặt phẳng tọa độ vuông góc xOy. Tìm tập phƣơng án . Bước 2. Biểu diễn phƣơng của hàm mục tiêu c1x + c2y = f, bằng cách cho f một giá trị f0 nào đó. Đƣờng thẳng c1x + c2y = f0 đƣợc gọi là đường mức. Bước 3. Tịnh tiến song song đƣờng mức trên tập phƣơng án để tìm phƣơng án tối ƣu. Chú ý: Thay vì xác định véctơ n (c1, c2) để tìm hƣớng tăng, ta có thể kiểm tra giá trị hàm mục tiêu ở gốc tọa độ O(0, 0). Ví dụ 1.2: Giải bài toán QHTT min{f(X) = - 2x + y} x 2y 2 2x 3y 6 với điều kiện 4x 5y 20 x,y 0 Giải: Hình 1.1 Biểu diễn điều kiện buộc của bài toán lên mặt phẳng tọa độ xOy ta đƣợc tập phƣơng án là hình ngũ giác ABCDE (Hình 1.1). Chọn f0 = 1, ta có đƣờng mức -2x + y = 1 (d). Chọn D(2, 0) f(D) = - 4 < f0. Suy ra dịch chuyển đƣờng mức (d) theo chiều mũi tên thì giá trị của hàm là - 12 -
  17. 45 11 giảm. Do đó tịnh tiến (d) theo chiều mũi tên, ta có PATƢ là A( , ) và fmin = 11 8 599 . 88 Ví dụ 1.3: Giải bài toán QHTT min{f(X) = x - y} 2x y 4 với điều kiện x 2y 2 x,y 0 Giải: Hình 1.2 Biểu diễn các điều kiện buộc của bài toán lên mặt phẳng xOy ta đƣợc tập phƣơng án (Hình 1.2). Chọn f0 = 1, ta có đƣờng mức (d): x – y = 1. Chọn C(1, 1) suy ra f(C) = 0 < f0 = 1. Vì vậy dịch chuyển (d) theo chiều mũi tên thì giá trị của hàm mục tiêu f(X) giảm. Ta thấy f(X) không bị chặn trên tập phƣơng án nên bài toán không có phƣơng án tối ƣu. Bạn đọc có thể kiểm tra thêm với ví dụ 2, nhƣng chỉ xét với hàm mục tiêu f(X) = -2x + y và max( -2x + y) thì phƣơng án tối ƣu lúc này là điểm A(4, 0), f(A) = 4. - 13 -
  18. Cũng cách làm nhƣ vậy với ví dụ 2, nhƣng thêm điều kiện x – 2y 5 thì tập phƣơng án rỗng. Bài toán không có phƣơng án tối ƣu. Ở ví dụ 1, nếu thay f(X) = 2x – 3y thì bài toán có vô số phƣơng án tối ƣu. Nhận xét: i)Tập PA của bài toán QHTT là một miền lồi bị chặn hoặc không bị chặn. ii) Bài toán có thể có PATƢ là một đỉnh hoặc có vô số PATƢ. iii) Bài toán có thể không có PATƢ nếu hàm mục tiêu không bị chặn trên tập PA hoặc tập PA rỗng. 4. MỘT SỐ YẾU TỐ HÌNH HỌC TRONG KHÔNG GIAN ¡ n 4.1. Tập hợp lồi 4.1.1. Tổ hợp lồi. Cho hệ hữu hạn điểm X1, X2, , Xk của không gian véctơ . k k Điểm X = iiX trong đó i 0 (i = 1,k ), i 1 đƣợc gọi là tổ hợp lồi i1 i1 của hệ điểm đã cho. 4.1.2. Đoạn thẳng. Cho X1, X2 . Tập hợp các điểm là tổ hợp lồi của hai điểm đã cho gọi là đoạn thẳng nối hai điểm ấy. n Tập hợp XX1 2 X X X(1 1 )X;0 2 1 gọi là đoạn thẳng nối hai điểm X1, X2. 4.1.3. Tập hợp lồi. Tập M đƣợc gọi là tập hợp lồi nếu mọi đoạn thẳng nối hai điểm của tập hợp thì nằm trọn trong tập hợp đó. Nghĩa là: Với mọi X1, X2 M, X X12 (1 )X ;0 1thì X M. 4.1.4. Điểm cực biên (Đỉnh). Điểm X thuộc tập lồi M đƣợc gọi là điểm cực biên nếu X không thể biểu diễn thành tổ hợp lồi thực sự của hai điểm khác nhau thuộc M. Nghĩa là không tồn tại X1, X2 M (X1 X2) sao cho: X X12 (1 )X ;0 1. 4.1.5. Siêu phẳng. Cho t , aΡ , Khi đó tập hợp các điểm X thỏa mãn điều kiện T,X =a gọi là siêu phẳng thuộc không gian . - 14 -
  19. Tập {XΡ n : T,X £ a } gọi là nửa không gian đóng giới hạn bởi siêu phẳng T,X =a. 4.2. Tính chất của tập hợp lồi 4.2.1. Giao của các tập lồi là tập lồi 4.2.2. Cho D1 và D2 là các tập lồi. Khi đó hiệu D = D1 - D2 và tổng D = D1 + D2 là các tập hợp lồi (hiệu và tổng theo nghĩa hiệu và tổng các véc tơ tƣơng ứng thuộc tập hợp). 4.2.3. Tập M lồi khi và chỉ khi tổ hợp lồi của hữu hạn điểm thuộc M cũng thuộc M. ïïìün 4.2.4. Tập M=íýïï X Ρ n : ax £ b,i = 1,2, ,m là tập lồi. ïïå ij j i îþïïj1= Trong trƣờng hợp này, tập M đƣợc gọi là tập lồi đa diện thuộc không gian ¡ n . Nhƣ vậy, tập lồi đa diện là giao của hữu hạn các nửa không gian đóng. 4.2.5. Đa diện lồi M có hữu hạn điểm cực biên X1, X2, , Xr và mọi điểm thuộc đa diện lồi là tổ hợp lồi của các điểm cực biên, nghĩa là mọi XM thì rr Xi X i , i 0, i 1. i 1 i 1 5. TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 5.1. Các giả thiết ban đầu Không mất tính tổng quát, ta giả thiết: Xét bài toán dạng chính tắc n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.6) j1 n aij x j b i ,i 1,m (1.7) với điều kiện j1 xj 0, j 1,n (1.8) * Hệ phƣơng trình (1.7) có đúng m phƣơng trình độc lập tuyến tính. * bi 0, i 1,m . - 15 -
  20. * m < n (vì trong trƣờng hợp m n thì tập phƣơng án có nhiều nhất một điểm, do vậy việc xét phƣơng án tối ƣu là tầm thƣờng). Ký hiệu: là tập các phương án của bài toán (1.6) – (1.8). Với bài toán đã cho, để tiện cho việc chứng minh sau này chúng ta nhớ rằng: Phƣơng án X* là phƣơng án tối ƣu khi và chỉ khi f(X*) f(X), X . 5.2. Các tính chất cơ bản của bài toán quy hoạch tuyến tính Định lý 1.1. Tập phương án của bài toán QHTT là tập lồi đa diện. Định nghĩa 1.6 - Điểm cực biên của tập lồi các phƣơng án gọi là phương án cực biên (PACB). - Tập lồi đa diện M đƣợc gọi là bị chặn nếu với mọi X=Î (xj ) M , tồn tại số thực L sao cho xj L, j 1,n . - Tập lồi đa diện khác rỗng và bị chặn đƣợc gọi là đa diện lồi. Định lý 1.2. Phương án X của bài toán QHTT tổng quát là phương án cực biên khi và chỉ khi X thỏa mãn chặt n ràng buộc độc lập tuyến tính. Phƣơng án cực biên thỏa mãn chặt đúng n ràng buộc gọi là phương án cực biên không suy biến. Phƣơng án cực biên thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến. Chú ý: i) Số n trong định nghĩa là số biến số của bài toán. ii) Nếu phƣơng án X thỏa mãn ít hơn n ràng buộc chặt (hoặc nếu nó thỏa mãn không ít hơn n ràng buộc chặt nhƣng không có hệ n ràng buộc nào độc lập tuyến tính) thì phƣơng án X không phải là phƣơng án cực biên (hay gọi là phƣơng án không cực biên). Định nghĩa 1.7. Nếu một phƣơng án của một bài toán QHTT vừa là PACB, vừa là PATƢ thì phƣơng án đó đƣợc gọi là phương án cực biên tối ưu. Ví dụ 1.4: Cho bài toán QHTT - 16 -
  21. f(X) = 8x1 + 2x2 + 9x3 – x4 min 3x1 2x 3 x 4 14 3x 4x 2x 8 với điều kiện 1 2 4 x1 7x 2 x 3 3x 4 7 x1 0;x 2 0;x 3 0 Xét xem véctơ X0(0, - 1, 6, - 2) và X1(4, 0, 0, -2), véctơ nào là phƣơng án cực biên của bài toán? Giải: ▪ Xét X0(0, -1, 6, -2) + Thay X0 vào hệ ràng buộc của bài toán ta thấy thỏa mãn, do đó X0 là một phƣơng án của bài toán. + Mặt khác X0 thỏa mãn 4 ràng buộc chặt là 3x1 2x 3 x 4 14 3x 4x 2x 8 1 2 4 x1 7x 2 x 3 3x 4 7 x01 Số ràng buộc chặt đúng bằng số biến của bài toán và định thức của ma trận các hệ số ứng với hệ 4 ràng buộc chặt là: 3 0 2 1 0 2 1 1 4 0 2 A = 4 0 2 0 1 7 1 3 7 1 3 1 0 0 0 Suy ra hệ 4 ràng buộc chặt là hệ ràng buộc chặt phụ thuộc tuyến tính, do đó phƣơng án X0 không phải là phƣơng án cực biên. ▪ Xét X1(4, 0, 0, -2) - Thay X1 vào hệ ràng buộc của bài toán ta đƣợc - 17 -
  22. 3x1 2x 3 x 4 14 3x1 4x 2 2x 4 8 x 7x x 3x 10 7 1 2 3 4 x1 4 0 x2 0 x3 0 Nhƣ vậy X1 là phƣơng án của bài toán. Phƣơng án X1 làm thỏa mãn 4 ràng buộc chặt. Số ràng buộc bằng số biến của bài toán và định thức của ma trận các hệ số ứng với hệ 4 ràng buộc chặt trên là: 3 0 2 1 3 0 1 1 4 0 2 3 1 B = 1 4 2 5 0 0 1 0 0 1 2 0 1 0 0 0 1 0 Suy ra hệ 4 ràng buộc chặt là hệ ràng buộc chặt độc lập tuyến tính. Do đó phƣơng án X1 là phƣơng án cực biên. Định lý 1.3. Nếu tập phương án của bài toán QHTT tổng quát khác rỗng và bị chặn thì nó là đa diện lồi. Định lý 1.4. Nếu tập phương án của bài toán QHTT là đa diện lồi thì tồn tại phương án cực biên tối ưu. Chứng minh: Theo giả thiết là đa diện lồi, suy ra tồn tại hữu hạn các phƣơng án cực biên (điểm cực biên) X1, X2, , Xr và với mọi X thuộc ta có: rr Xi X i , i 0, i 1. i 1 i 1 Đặt f(X*) = min{f(X1), f(X2), , f(Xr)}, ta có: r r r r f(X)= f( iiX ) = iif (X ) if (X*) = f (X*)i f (X*) . i1 i1 i1 i1 Suy ra f(X) f(X*), X . Vậy X* là phƣơng án cực biên tối ƣu.■ - 18 -
  23. Định lý 1.5. Nếu bài toán quy hoạch tuyến tính có phương án tối ưu thì có ít nhất một phương án cực biên tối ưu. Nhận xét: Từ định lý 1.4 và 1.5 cho phép chúng ta tìm phƣơng án tối ƣu của bài toán quy hoạch tuyến tính trên tập các phƣơng án cực biên. Sau này, chúng ta thấy thêm rằng số phƣơng án cực biên là hữu hạn. Định lý 1.6. Phương án X x j là cực biên khi và chỉ khi hệ véc tơ cột Aj ứng với các x j > 0 độc lập tuyến tính. Chứng minh: Không mất tính tổng quát, giả sử X có dạng X = (x1, x2, , xk, 0, , 0), trong đó x1, x2, , xk > 0. Điều kiện cần: Giả sử X là phƣơng án cực biên. Ta chứng minh hệ véc tơ A1, A2, , Ak độc lập tuyến tính. Thật vậy, giả sử ngƣợc lại hệ A1, A2, , Ak phụ thuộc tuyến tính, nghĩa là tồn tại s 0 (s [1, k]) mà 1A1+ 2A2 + + kAk = 0. (1.12) Lại do X là phƣơng án nên x1A1 + x2A2 + + xkAk = B. (1.13) Từ (1.12) và (1.13) ta có (x1 1)A1 + (x2 2)A2 + + (xk k)Ak = B. Vì x1, x2, , xk > 0, nên có thể chọn > 0 đủ bé để xs s 0, s =1, 2, , k. Khi đó ta đƣợc: X1 = (x1 + 1, x2 + 2, , xk + k, 0, , 0) và X2 = (x1 1, x2 2, , xk k, 0, , 0) là hai phƣơng án khác nhau (vì tồn tại s 0, > 0). 11 Nhƣng lúc này X = XX, suy ra X là tổ hợp lồi của hai phƣơng án. 2212 Điều này là mâu thuẫn với X là phƣơng án cực biên. Vậy hệ véctơ cột A1, A2, , Ak độc lập tuyến tính. - 19 -
  24. Điều kiện đủ: Cho hệ véctơ cột A1, A2, , Ak của ma trận ràng buộc A trong sự phân tích x1A1 + x2A2 + + xkAk = B, (với x1, x2, , xk > 0) độc lập tuyến tính. Ta chứng minh X = (x1, x2, , xk, 0, , 0) là phƣơng án cực biên. Giả sử X không phải là phƣơng án cực biên, nghĩa là tồn tại hai phƣơng án khác nhau X' (x')j (x',x' 1 2 , ,x' n ) và X" (x")j (x",x", ,x" 1 2 n ) của bài toán sao cho X = X’ + (1 - )X”, (0, 1). Điều này tƣơng đƣơng với xj x' j (1 )x", j j 1,n . Với j k 1,n thì một mặt xj 0, j k 1,n , mặt khác xj x' j (1 )x",j j k 1,n , mà X’, X” là các phƣơng án của bài toán nên x'jj 0, x" 0, j k 1,n . Suy ra x'jj x" 0, j k 1,n . Tức là X’ và X” thỏa mãn x'A x'A x'A B 1 1 2 2 k k x"A1 1 x"A 2 2 x"A k k B Từ đó, ta có (x'1 x")A 1 1 (x' 2 x")A 2 2 (x' k x")A k k 0 . Vì X’ và X” là hai phƣơng án khác nhau nên tồn tại x'll x" 0, từ đẳng thức trên suy ra hệ véctơ A1, A2, , Ak phụ thuộc tuyến tính. Điều này mâu thuẫn với giả thiết. Vậy X là phƣơng án cực biên.■ Ví dụ 1.5: Cho bài toán quy hoạch tuyến tính f(X) x1 2x 2 x 3 x 4 3x 5 min 2x1 x 2 x 3 x 4 3x 5 13 x1 x 2 x 3 5x 4 2x 5 1 với điều kiện 3x1 x 2 x 3 9x 4 3x 5 7 xj 0, j 1,5 Hỏi véctơ X(4, 5, 0, 0, 0) có phải là phƣơng án cực biên của bài toán đã cho hay không? Giải: Thay X vào hệ ràng buộc ta thấy thỏa mãn nên X là phƣơng án của bài toán. - 20 -
  25. Phƣơng án X có hai thành phần dƣơng là x1, x2. Hệ véctơ cột của ma trận ràng buộc A ứng với các thành phần tọa độ dƣơng của X là: 2 1 A1 = 1 ; A2 = 1 3 1 Xét ma trận 2 1 1 1 1 1 1 1 2h12 h hh12 3h1 h 3 4/3h 2 h 3 D = [A1, A2] = 1 1 2 1 0 3 0 3 . 3 1 3 1 0 4 0 0 Suy ra rankD = 2 = số véctơ của hệ, do đó hệ véctơ {A1, A2} độc lập tuyến tính. Theo định lý 1.6, phƣơng án X là phƣơng án cực biên của bài toán. Ví dụ 1.6: Cũng với bài toán nhƣ trên, hỏi véctơ X(2, 8, 0, 1, 0) có phải là phƣơng án cực biên hay không? Giải: Dễ thấy X là một phƣơng án của bài toán. Phƣơng án X có 3 thành phần tọa độ dƣơng là x1, x2, x4. Hệ véctơ cột của ma trận ràng buộc A ứng với thành phần tọa độ dƣơng của phƣơng án X là {A1, A2, A4}, hệ này có số véctơ bằng số chiều và định thức của ma trận tạo bởi chúng là: 2 1 1 D = 1 1 5 0 3 1 9 Suy ra hệ véctơ {A1, A2, A4} phụ thuộc tuyến tính. Vậy X không phải là phƣơng án cực biên. Hệ quả 1. Số tọa độ dương của phương án cực biên có tối đa là m (m là số phương trình của hệ ràng buộc). Hệ quả 2. Số phương án cực biên của là hữu hạn. Chú ý: i) Một phƣơng án của bài toán (1.6) – (1.8) có số thành phần tọa độ dƣơng không vƣợt quá m chƣa hẳn là phƣơng án cực biên. ii) Một phƣơng án cực biên có đủ m tọa độ dƣơng thì phƣơng án cực biên đó là phƣơng án cực biên không suy biến. - 21 -
  26. iii) Một phƣơng án cực biên của bài toán trên có số thành phần tọa độ dƣơng ít hơn m thì phƣơng án cực biên đó là phƣơng án cực suy biến. iv) Hệ m véctơ Aj độc lập tuyến tính tƣơng ứng với phƣơng án cực biên X nhƣ đã nêu trong định lý 1.6 gọi là cơ sở liên kết. v) Bài toán QHTT có tất cả các phƣơng án cực biên không suy biến đƣợc gọi là bài toán QHTT không suy biến. Ví dụ 1.7: Cho bài toán f(X) 2x1 x 2 x 3 min 2x1 x 2 x 3 x 4 4 3x1 x 2 x 5 5 với điều kiện x1 x 2 x 3 2 xj 0, j 1,5 a) Véctơ X(2, 0, 0, 0, 1) có phải là phƣơng án cực biên không? b) Hệ véctơ {A1, A2, A3} có độc lập tuyến tính không? Nếu có hãy tìm một phƣơng án cực biên tƣơng ứng. Giải: a) Vì hệ véctơ {A1, A4, A5} độc lập tuyến tính, nên X(2, 0, 0, 0, 1) là phƣơng án cực biên. b) Dễ kiểm tra hệ véctơ {A1, A2, A3} độc lập tuyến tính. Giả sử X*(x1, x2, x3, 0, 0) (x1, x2, x3 0) là phƣơng án cực biên cần tìm. Khi đó X* thỏa mãn các điều kiện ràng buộc của bài toán. 16 x 1 9 2x1 x 2 x 3 4 1 3x12 x 5 x 2 3 Hệ vô nghiệm. x x x 2 1 2 3 1 x03 xj 0, j 1,3 9 xj 0, j 1,3 Vậy không tồn tại phƣơng án cực biên nào nhận hệ véctơ {A1, A2, A3} là cơ sơ liên kết. - 22 -
  27. Định lý 1.7. Mỗi phương án cực biên của tập phương án đều tồn tại một hàm mục tiêu để nó là phương án tối ưu duy nhất. Chứng minh: Cho X( x1 ,x 2 , ,x j , ,x k ,0 ,0) là phƣơng án cực biên ứng với cơ sở liên kết A1A2 Ak ( k [1, m]). Đặt: J = [1, k] là tập chỉ số cơ sở liên kết của X. 0 nêu j J C = (c ) với c , tức là C = 0,0, ,0,1, ,1 . j j 1 nêu j J  cã k sè 0 n Rõ ràng CX = 0, và với mọi phƣơng án Y y j ta có CY = y j 0. Vậy X j k 1 là phƣơng án tối ƣu. Đồng thời nếu có Y là phƣơng án tối ƣu thì cũng có CY = 0. Lại vì, c j 1với j J, chứng tỏ yj = 0 với j J. Do [A1A2 Ak] không suy biến nên từ hệ phƣơng trình AX = B và AY = B suy ra X =Y, nghĩa là phƣơng án X tối ƣu duy nhất. Định lý 1.8. (Về sự tồn tại PATƢ của bài toán QHTT) Nếu bài toán QHTT có tập phương án khác rỗng và hàm mục tiêu bị chặn dưới đối với bài toán f(X) min ( bị chặn trên đối với bài toán f(X) max) trong tập các phương án thì bài toán có phương án tối ưu. Ví dụ 1.9: Chứng minh bài toán sau có phƣơng án tối ƣu f(X) 3x1 3x 2 x 3 min x1 2x 2 x 3 1 x13 5x 16 với điều kiện 2x23 9x 3 3x1 x 2 3x 3 6 xj 0, j 1,3 Giải: ▪ Nhận thấy X(0, 0, 2) là một phƣơng án của bài toán, do đó tập phƣơng án của bài toán là khác rỗng. - 23 -
  28. ▪ Chứng tỏ hàm mục tiêu f(X) bị chặn dƣới. Từ hệ ràng buộc ta có x1 2x 2 x 3 1 x1 5x 3 16 3x 1 3x 2 x 3 9 3x1 x 2 3x 3 6 Vì xj 0, j 1,3 nên x3 - x3. Do đó f(X) 3x1 3x 2 x 3 3x1 3x 2 x 3 9, X . Tức là hàm mục tiêu f(X) bị chặn dƣới trong tập phƣơng án . Theo định lý 1.8 thì bài toán có phƣơng án tối ƣu. Ví dụ 1.9: Cho bài toán QHTT f(X) 5x1 2x 2 2x 3 5x 4 min 2x1 2x 2 x 3 x 4 5 3x1 x 2 3x 3 4x 4 8 với điều kiện x1 2x 2 x 3 3x 4 7 xj 0, j 1,4 Chứng minh rằng bài toán có phƣơng án nhƣng không có phƣơng án tối ƣu. Giải: Xét họ véctơ phụ thuộc tham số X( ) = (0, 2 , 0, ), mọi tùy ý. Thay X( ) vào hệ ràng buộc của bài toán, ta đƣợc: 202(2) 0 5 5 1 3 0 2 3 0 4 2 8 4 0 . 02(2) 03 7 7 xj 0, j 1,4 0 Vậy, với mọi 0 thì X( ) là phƣơng án của bài toán. Mặt khác, thay họ X( ) vào hàm mục tiêu ta đƣợc f(X( )) = khi + . Vậy hàm mục tiêu của bài toán không bị chặn dƣới trong tập phƣơng án, do đó bài toán không có phƣơng án tối ƣu. - 24 -
  29. Định lý 1.9. Nếu bài toán QHTT có hai phương án tối ưu khác nhau thì có vô số phương án tối ưu. Chứng minh: Giả sử X1 và X2 là hai phƣơng án tối ƣu khác nhau của bài toán (1.6) – (1.8), tức là f(X1) = f(X2) f(X), X . Khi đó, xét Y = X1 + (1 - )X2, (0, 1). Rõ ràng Y là một phƣơng án và f(Y) = f(X1) + (1 - )f(X2) = f(X1) = f(X2) f(X), X . Vậy Y là phƣơng án tối ƣu của bài toán (1.6) – (1.8), có vô số Y nhƣ vậy. ■ 6. PHƢƠNG PHÁP ĐƠN HÌNH Nội dung của phương pháp: Trên cơ sở các tính chất đã nêu ở trên, để tìm phƣơng án tối ƣu của bài toán QHTT dạng chính tắc ta có thể duyệt các phƣơng án cực biên bằng cách: xuất phát từ phƣơng án cực biên X0 nào đó, kiểm tra X0 có tối ƣu không? Nếu X0 tối ƣu thì dừng. Nếu chƣa tối ƣu thì tìm cách chuyển sang một phƣơng án cực biên mới tốt hơn (theo nghĩa giá trị của hàm mục tiêu giảm). Quá trình tiếp tục nhƣ vậy, ta đƣợc dãy các phƣơng án cực biên tốt dần. Vì số phƣơng án cực biên là hữu hạn cho nên sau một số hữu hạn bƣớc ta sẽ tìm đƣợc phƣơng án cực biên tối ƣu nhất hoặc xác định bài toán không có lời giải. 6.1. Cơ sở lý luận của phƣơng pháp đơn hình Xét bài toán QHTT dạng chính tắc n f (X) c1 x 1 c 2 x 2 c n x n c j x j CX min (1.6) j1 n AX B (1.7) aij x j b i ,i 1,m với điều kiện j1 hay xj 0, j 1,n X O (1.8) Nhƣ ở mục 5 chƣơng 1, ta giả thiết: - 25 -
  30. * Hệ phƣơng trình (1.7) có đúng m phƣơng trình độc lập tuyến tính (rank A = m); * bi 0, i 1,m ; * m 0, j = 1, 2, , m. Với cơ sở liên kết là A1A2 Am. Vì Xo là phƣơng án nên nó phải thỏa mãn ràng buộc (1.7), ta có x1oA1 + x2oA2 + + xmoAm = B, (1.14) và giá trị của hàm mục tiêu tại Xo là n . f(Xo) = cxj j0 = c1x1o + c2x2o + + cmxmo (1.15) j1 m Do A1, A2, , Am là cơ sở của không gian ¡ nên các véctơ Aj ( j = 1,n ) biểu thị qua duy nhất qua chúng: m Aj = xAij i = x1jA1 + x2jA2 + + xmjAm ( j = 1,n ). i1 (1.16) Đặt Xj = (x1j, x2j, , xmj) là tọa độ của Aj ( j = 1,n ) đối với cơ sở A1, A2, , Am. Chú ý: Nếu j = 1, 2, , m thì Xj = (0, 0, , 0, 1 , 0, , 0 ) là véctơ đơn vị thứ j. vÞ trÝ j - 26 -
  31. Nếu bằng cách nào đó biết đƣợc Xo là PATƢ thì mục đích của ta đã đạt đƣợc. Nếu Xo không phải là PATƢ thì ta tìm cách xây dựng một phƣơng án cực biên mới mà tại đó giá trị của hàm mục tiêu nhỏ hơn f(X0). Muốn vậy chúng ta cần xác định một cơ sở mới, bằng cách thay thế một véctơ trong cơ sở cũ bởi một véctơ nào đó nằm ngoài cơ sở cũ. Không mất tính tổng quát giả sử đƣa Aj ( j = m 1,n ) vào cơ sở mới (Aj có dạng (1.16)). Từ (1.14) và (1.15), ta có x1oθx 1j1 A x 2o θx 2j2 A x mo θx mjm A θA j B, (1.17) trong đó là một số dƣơng tùy ý. Vì xio > 0, i 1,m , nên có thể tìm đƣợc số đủ bé sao cho xioθx ij > 0, i 1,m . (1.18) Khi đó rõ ràng véctơ X*(x*j) = (x1oθx 1j2o ,x θx 2j , ,x mo θx mj ,0, 0, θ ,0, ,0) , ( j = m 1,n ) v? trí th? j là một phƣơng án của bài toán (1.6) – (1.8), và tại đó giá trị của hàm mục tiêu sẽ là n m f(X*) = cjj x * = ci (x ioθx ij ) c j θ = j1 i1 mm = cxi ioθ c i x ij c j . i 1 i 1 m Đặt j ci x ij c j , (1.19) i1 gọi là ước lượng của véctơ Aj ứng với phƣơng án cực biên Xo. Suy ra f(X*) = f(Xo) j . (1.20) Chú ý: 0, j là chỉ số của hệ véctơ trong cơ sở cũ. Định lý 1.10. (Dấu hiệu tối ƣu) - 27 -
  32. Nếu Xo = (x1o, x2o, , xmo, 0, , 0) là một phương án cực biên sao cho j 0 , j 1,n thì Xo là phương án tối ưu của bài toán (1.6) – (1.8). Chứng minh: Giả sử Y(y1, y2, , yn) là một phƣơng án bất kỳ, ta cần chứng minh f(X0) f(Y). Do Y là một phƣơng án nên thỏa mãn ràng buộc (1.7) y1A1 + y2A2 + + ymAm = B, (1.21) và giá trị của hàm mục tiêu tại Y là n f(Y) = cyjj= c1y1 + c2y2 + + cnyn . (1.22) j1 m Vì j 0, j 1,n ci x ij c j , j 1,n và yj 0, j 1,n nên từ i1 (1.22) ta có n m m n f(Y) cj x ij y j y j x ij c i . (1.23) j 1 i 1 i 1 j 1 Mặt khác, trong (1.21) thay Aj bởi (1.16) ta đƣợc n n m m n B = yj A j y j x ij A i y j x ij A i . (1.24) j 1 j 1 i 1 i 1 j 1 Mà X0 là phƣơng án nên cũng có m B = x1oA1 + x2oA2 + + xmoAm = xAio i . (1.25) i1 So sánh (1.24) và (1.25) ta có n xi0 = yxj ij , i 1,m. (1.26) j1 Từ (1.23) và (1.25) suy ra f(Y) f(Xo).■ Định lý 1.11. (Dấu hiệu bài toán không có lời giải) Nếu tồn tại một véctơ Aj ngoài cơ sở liên kết của phương án cực biên Xo= (x1o, x2o, , xmo, 0, , 0) sao cho j > 0 và Xj = (x1j, x2j, , xmj ) 0 thì bài toán - 28 -
  33. (1.6) – (1.8) không có phương án tối ưu, cụ thể là hàm mục tiêu có thể lấy giá trị nhỏ tùy ý trên tập phương án. Chứng minh: Do Xj = (x1j, x2j, , xmj ) 0 xij 0, i = 1,m nên với là số dƣơng nhỏ tùy ý thì từ (1.18), suy ra X* là phƣơng án có m + 1 thành phần tọa độ dƣơng. Mặt khác, theo (1.20) thì f(X*) = f(Xo) j . Do j > 0, > 0 nên f(X*) 0 và tồn tại xik > 0 thì xây dựng được phương án cực biên X1 tốt hơn X0, nghĩa là f(X1) f(Xo). Chứng minh: Theo giả thiết Xo là phƣơng án nên x1oA1 + x2oA2 + + xmoAm = B. (1.27) Mặt khác, Ak đƣợc biểu diễn qua cơ sở A1, A2, , Am liên kết của Xo là Ak = x1kA1 + x2kA2 + + xmkAm . (1.28) Từ (1.27) và (1.28) ta đƣợc x1oθx 1k1 A x 2o θx 2k2 A x mo θx mkm A θA k B, trong đó là một số dƣơng tùy ý. Khi đó để vectơ X* = (x1oθx 1k ,x 2o θx 2k , ,x mo θx mk ,0, 0, θ ,0, ,0) , vÞ trÝ thø k là phƣơng án thì ta cần và xioθx ik 0, i 1,m . x Với > 0 thì điều đó tƣơng đƣơng với 0 < i0 , i 1,m. xik xio Chọn o = min xik 0,i 1,m (1.29) xik - 29 -
  34. Không mất tính tổng quát, giả sử min đạt đƣợc tại chỉ số i = l (l = 1, 2, , xl0 m), tức là o = > 0. Khi đó phƣơng án mới xlk X1 = (x1oθx,x o1k 2o θx, ,x o 2k (l1)o θx o (l1)k ,x (l1)o θx o (l1)k , , xmoθ o x mk ,0, , 0, θo ,0, ,0), vÞ trÝ thø k là phƣơng án có đủ m thành phần tọa độ dƣơng (đó là vị trí thứ 1, 2, , l -1, l +1, , m và k), hơn thế nữa X1 Xo (vì o > 0). Theo đại số tuyến tính, hệ véctơ A1 ,A 2 , ,A l 1 ,A l 1 , ,A m ,A k là một cơ sở. Do đó X1 là phƣơng án cực biên, đồng thời giá trị hàm mục tiêu tại X1 là f(X1) = f(Xo) o k Vì o > 0, k > 0 nên f(X1) < f(Xo), hay X1 tốt hơn Xo. ■ 6.2. Công thức đổi tọa độ và bảng đơn hình Từ cơ sở lý luận của phƣơng pháp đơn hình đã đƣợc trình bày ta thấy rằng xuất phát từ phƣơng án cực biên ban đầu Xo đƣợc coi nhƣ đã biết, sau khi kiểm tra nếu thấy chƣa thỏa mãn định lý 1.10 (dấu hiệu tối ƣu) và định lý 1.11 (dấu hiệu bài toán không giải đƣợc) thì ta phải tiến hành xây dựng một phƣơng án cực biên mới X1 tốt hơn Xo và kiểm tra nó. Quá trình đó sau một số hữu hạn bƣớc sẽ kết thúc, lúc đó ta tìm đƣợc phƣơng án tối ƣu hoặc kết luận bài toán không giải đƣợc. Ta nói rằng đã thực hiện đƣợc một bước lặp nếu nhƣ mỗi phƣơng án xuất hiện trong quá trình nói trên, sau khi đã kiểm tra xong ta có đƣợc một quyết định tiếp theo. Trong mỗi bƣớc lặp ta cần xác định các tham số xij, j, f (giá trị hàm mục tiêu tại phƣơng án cực biên đang xét), trong đó việc xác định xij là khó khăn nhất vì mỗi j ta phải giải một hệ phƣơng trình tuyến tính. Do cơ sở liên kết của phƣơng án cực biên ở mỗi bƣớc lặp chỉ khác bƣớc lặp trƣớc một véctơ nên ta có thể tìm đƣợc các công thức truy toán cho phép tìm đƣợc giá trị của các tham số ở mỗi bƣớc từ các giá trị ở bƣớc trƣớc. - 30 -
  35. 6.2.1. Công thức đổi tọa độ Tại phƣơng án cực biên Xo, ta đã biết xio là tọa độ thứ i của X0 xij là tọa độ thứ i của véctơ Aj Chú ý: Nếu hệ cơ sở A1A2 Am của Xo là các véctơ đơn vị thì xij = aij của ma trận A. m Từ đó ta tính đƣợc: j ci x ij c j i1 m f(X0) = cxi i0 , i1 để có X1 ta cần tìm xi1, x’ij, ’j, f(X1). Theo chứng minh định lý 1.12, ta có x lo nêu i k xlk xi1 (1.30) xlo xio x ik nêu i k xlk Ta có hệ A1 ,A 2 , ,A l 1 ,A l ,A l 1 , ,A m là cơ sở cũ ứng với phƣơng án cực biên Xo và thay Al bởi Ak ( k = m 1,n ; k ứng với k > 0), ta đƣợc cơ sở mới A1 ,A 2 , ,A l 1 ,A l 1 , ,A m ,A k Theo (1.28) ta có m m Ak = xAik i = xik A i x lk A l , xlk > 0 (1.31) i1 i1 il Với mỗi j = 1,n véctơ Aj biểu diễn qua cơ sở cũ và mới là mm Aj = xij A i x ij A i x lj A l (1.32) i 1 i 1 il mm Aj = x'ij A i x' ij A i x' lj A l (1.33) i 1 i 1 il Từ (1.31) ta có - 31 -
  36. 1 m Al = Ak x ik A i (1.34) xlk i1 il Thay (1.33) vào (1.32) ta đƣợc mm xlj Aj = xij A i A k x ik A i i 1xlk i 1 i l i l m xxlj lj = xij x ik A i A k (1.35) i1 xxlk lk il Do Aj biểu thị tuyến tính duy nhất qua cơ sở mới nên so sánh (1.33) và (1.35) ta đƣợc x xlj x nêu i k ijx ik x' lk (1.36) ij x lj nêu i k xlk Ngoài ra f(X1) = f(Xo) o k . (1.37) Với mọi j 1,n , ta có m m xxlj lj ’j = ci x' ij c k x' kj c j = ci x ij x ik c k c j i1 i1 xxlk lk il il mmmm xlj xlj = ci x ij c j c i x ik c k = ci x ij c j c i x ik c k . i 1xlk i 1 i 1xlk i 1 i l i l xlj Suy ra ’j = j k (1.38) xlk 6.2.2. Bảng đơn hình với cơ sở đơn vị có sẵn Việc biến đổi từ phƣơng án Xo sang phƣơng án X1 theo các công thức (1.30) và (1.36) cho thuận tiện ta mô tả nó trên bảng gồm các dòng và các cột, đƣợc gọi là - 32 -
  37. bảng đơn hình nhƣ Bảng 1.4. Bảng 1.4 Cơ sở Hệ số Tọa độ c1 C2 ck cn Ai ci Xo A1 A2 Ak An Al cl xlo xl1 xl2 xlk Xln f(X) 1 2 k n Để tiện thực hành tính toán, từ các công thức (1.30), (1.36), (1.37) và (1.38) ta nêu thành quy tắc: * j bằng tích các phần tử ở cột (ci) tƣơng ứng với các phần tử ở cột (Aj), rồi cộng lại, đƣợc kết quả bao nhiêu trừ phần tử cj ở trên đầu cột j. * Các phần tử hàng k ở bảng mới bằng các phần tử hàng l ở bảng cũ chia cho phần tử trục xlk. * Các phần tử hàng i bảng mới (x’ij), tƣơng ứng bằng hàng k bảng mới nhân với ( xik) rồi cộng với hàng i ở bảng cũ (i k). Để dễ dàng tính toán ta giả thiết các cột của ma trận D lập thành bởi hệ cơ sở A m liên kết với phƣơng án cực biên X lập thành ma trận đơn vị. Khi đó x = a i i1 0 ij ij và xio = bi. Do vậy các số liệu của bảng đơn hình đầu tiên lúc này có dạng (bảng đơn hình với cơ sở đơn vị có sẵn): Bảng 1.5 Cơ sở Hệ số Tọa độ c1 C2 ck cn Ai ci Xo A1 A2 Ak An Al cl bl al1 al2 alk aln f(X) 1 2 k n - 33 -
  38. Chú ý: Dòng l gọi là dòng xoay, cột k đƣợc gọi là cột xoay. 6.2.3. Thuật toán đơn hình với cơ sở đơn vị có sẵn Bước 1. Chọn cơ sở đơn vị và phƣơng án cực biên xuất phát Xo (xác định xi0, xij, f(X) và j). Bước 2. Kiểm tra j 0, j = 1, 2, , n? Nếu có, chuyển sang bƣớc 7. Nếu không, chuyển sang bƣớc 3. Bước 3. Kiểm tra tồn tại j > 0, xij 0? Nếu có, chuyển sang bƣớc 7. Nếu không, chuyển sang bƣớc 4. Bước 4. Chọn k = max{ j > 0}, đƣa Ak vào cơ sở. xxio lo Bước 5. Tìm o = min , đƣa Al ra khỏi cơ sở. x0 ik xxik lk Bước 6. Xây dựng X1 theo công thức (1.37), (1.43) hoặc quy tắc đã nêu. Gán X1 : = X0, rồi trở lại bƣớc 1. Bước 7. Dừng lại, trả lời có hay không phƣơng án tối ƣu. Ví dụ 1.10: Giải bài toán QHTT sau f(X) x1 x 2 2x 3 2x 4 3x 6 min x1 x 3 x 4 x 6 2 x2 x 4 x 6 12 với điều kiện 4x3 2x 4 x 5 3x 6 9 xj 0, j 1,6 Giải: Chọn cơ sở liên kết {A1, A2, A5} là các véctơ đơn vị tƣơng ứng với phƣơng án cực biên xuất phát X(2, 12, 0, 0, 9, 0). Ta có bảng đơn hình (Bảng 1.6). - 34 -
  39. Bảng 1.6 Bảng Cơ sở Hệ số Tọa độ 1 -1 2 -2 0 -3 số Ai ci xio A1 A2 A3 A4 A5 A6 A1 1 2 1 0 1 1 0 -1 A2 -1 12 0 1 0 1 0 1 I A5 0 9 0 0 4 2 1 3 f(X) = -10 0 0 -1 2 0 1 A4 -2 2 1 0 1 1 0 -1 A2 -1 10 -1 1 -1 0 0 2 A5 0 5 -2 0 2 0 1 5 f(X) = -14 -2 0 -3 0 0 3 3 7 1 A -2 3 0 1 0 4 5 5 5 1 9 2 A -1 8 1 0 0 2 5 5 5 III 2 2 1 A -1 1 0 0 1 6 5 5 5 4 21 3 f(X) = -17 0 0 0 5 5 5 Tại bảng III, ta thấy j 0, j = 1,6 nên ta có phƣơng án tối ƣu là: X = (0, 8, 0, 3, 0, 1) và fmin = - 17. 6.3. Bài toán suy biến Nếu bài toán không suy biến thì thuật toán dừng lại sau hữu hạn bƣớc lặp. Trong trƣờng hợp bài toán suy biến, nghĩa là có thể gặp phƣơng án cực biên X0 mà xio có thành phần thuộc cơ sở bằng 0, khi đó đại lƣợng o = min có thể bằng 0. x0 ik xik Khi đạt giá trị là 0, ta nhận đƣợc phƣơng án cực biên mới giống với phƣơng án cực biên cũ, mặc dù cơ sở mới khác cơ sở cũ. Hai khả năng có thể xảy ra. - 35 -
  40. Một là sau một số hữu hạn bƣớc sẽ thoát khỏi phƣơng án cực biên X0 và chuyển sang phƣơng án cực biên mới tốt hơn. Hai là sau một số hữu hạn bƣớc lại quay trở lại cơ sở mà nó đi qua. Trƣờng hợp này cho ta một vòng khép kín bao gồm một dãy các cơ sở của phƣơng án cực biên X0, ngƣời ta gọi đây là hiện tƣợng xoay vòng của thuật toán. Về mặt lý thuyết cần phải có biện pháp để khắc phục trƣờng hợp này. Sau đây là biện pháp mà ngƣời ta gọi là quy tắc từ vựng để khắc phục hiện tƣợng xoay vòng trên, đảm bảo tính hữu hạn của thuật toán. Nội dung của quy tắc đó là: Giả sử tại phƣơng án cực biên X0 với cơ sở J0 xio có o = min đạt tại nhiều chỉ số, chẳng hạn trên tập R1 J0, lúc này nhiều x0 ik xik véc tơ cơ sở có thể đƣa ra khỏi cơ sở J0, vấn đề ta nên chọn véc tơ nào để tránh hiện tƣợng xoay vòng? Không mất tính tổng quát, giả sử J0 1,m , ta xét các chỉ số: a 1 ( R1k ,a 0), a k nếu giá trị nhỏ nhất của các chỉ số trên không duy nhất mà đạt tại nhiều chỉ số, chẳng hạn trên tập R2 R1 thì ta chuyển sang xét các tỷ số: a 2 ( R2k ,a 0). a k Cứ nhƣ vậy cho đến khi xét đƣợc cực tiểu duy nhất, véc tơ ứng với cực tiểu duy nhất sẽ bị loại ra khỏi cơ sở. Chú ý: Trong nhiều trƣờng hợp giải bài toán quy hoạch tuyến tính, khi gặp trƣờng hợp véc tơ loại khỏi cơ sở không duy nhất, ngƣời ta không cần dùng quy tắc từ vựng mà chỉ loại một cách ngẫu nhiên cũng đủ để không gặp hiện tƣợng quay vòng. - 36 -
  41. 7. PHƢƠNG PHÁP TÌM PHƢƠNG ÁN CỰC BIÊN XUẤT PHÁT 7.1. Bài toán giả tạo Trong thuật toán đã nêu ở mục 6, giả thiết biết trƣớc phƣơng án cực biên xuất phát và khi thực hiện bảng đơn hình chúng ta giả thiết ma trận ràng buộc A chứa ma trận đơn vị cấp m thì khi đó chọn các véc tơ Ai đơn vị tƣơng ứng để tạo nên cơ sở liên kết và phƣơng án cực biên xuất phát ban đầu có xi = bi, với i thuộc vào tập chỉ số của véctơ hệ cơ sở và xij = aij. Trong bài này, chúng ta sẽ nghiên cứu một phƣơng pháp tìm phƣơng án cực biên xuất phát khi chƣa có ma trận đơn vị gọi là phương pháp phạt (hay bài toán M). Cho bài toán QHTT dạng chính tắc n f (X) cjj x min (1.6) j1 n aij x j b i ,i 1,m (1.7) với điều kiện j1 xj 0, j 1,n (1.8) trong đó ma trận A không chứa ma trận đơn vị, bi > 0 với i = 1,m. Khi đó ta có bài toán giả tạo (hay bài toán M) nhƣ sau: nm f(X) cxj j M( x) i min (1.6)’ j 1 i 1 n aij x j x n i b i ,i 1,m (1.7)' với điều kiện j1 xj 0, j 1,n (1.8)' trong đó M là số thực dƣơng lớn tùy ý. Các ẩn xn + i 0 với i = 1,m gọi là ẩn giả tạo. - 37 -
  42. Ta thấy hệ véctơ đơn vị {An+1, An+2, , An+m} là hệ véctơ độc lập tuyến tính nên X 0,0, ,0,b ,b , ,b là phƣơng án cực biên của bài toán M. o 1 2 m n sè 0 Ví dụ 1.11: Xét bài toán f(X) x1 2x 2 x 3 max x1 4x 2 2x 3 6 x1 x 2 2x 3 6 với điều kiện 2x1 x 2 2x 3 4 xj 0, j 1,3 Đƣa bài toán về dạng chính tắc bằng cách đƣa vào các ẩn phụ x4, x5 0. g(X) f(X) x1 2x 2 x 3 min x1 4x 2 2x 3 x 4 6 x1 x 2 2x 3 x 5 6 với điều kiện 2x1 x 2 2x 3 4 xj 0, j 1,5 Ta chỉ mới có A4 là véctơ đơn vị. Cần đƣa thêm hai ẩn giả tạo x6, x7 để đƣợc bài toán giả tạo: g(X) f(X) x1 2x 2 x 3 Mx 6 Mx 7 min x1 4x 2 2x 3 x 4 6 x1 x 2 2x 3 x 5 x 6 6 với điều kiện 2x1 x 2 2x 3 x 7 4 xj 0, j 1,7 Khi đó phƣơng án cực biên của bài toán giả tạo với cơ sở liên kết đơn vị {A4, A6, A7} là X (0,0,0,6,0,6,4) Nhận xét: i) Chúng ta cần phân biệt ẩn giả tạo với ẩn phụ. + Ẩn phụ nhằm mục đích đƣa bài toán về dạng chính tắc + Ẩn giả tạo nhằm mục đích tạo ra ma trận đơn vị cấp m để từ đó tìm ra phƣơng án cực biên xuất phát với cơ sở liên kết đơn vị. Vì vậy ta chỉ cần bổ sung thêm các ẩn giả tạo nếu cần thiết. - 38 -
  43. + Hệ số hàm mục tiêu của ẩn phụ cj = 0 còn hệ số hàm mục tiêu của ẩn giả tạo cn+i = M > 0 lớn tùy ý. ii) Xuất phát từ phƣơng án cực biên X o ta có thể giải bài toán giả tạo bằng phƣơng pháp đơn hình. Vấn đề đặt ra là giữa bài toán (1.6) – (1.8) và (1.6)’ – (1.8)’ có mối quan hệ nhƣ thế nào? Định lý sau sẽ cho ta câu trả lời. 7.2. Mối quan hệ về phƣơng án tối ƣu của bài toán giả tạo và bài toán chính tắc tƣơng ứng Định lý 1.13. Có thể tìm được số M0 > 0 đủ lớn, sao cho với mọi M > M0 thì a) Bài toán (1.6) – (1.8) có phương án tối ưu X khi và chỉ khi bài toán giả tạo có phương án tối ưu X* X,w và w = 0 (trong đó w là thành phần của ẩn giả tạo). b)Nếu bài toán giả tạo có phương án tối ưu , trong đó w 0 (tức là có chứa ít nhất một thành phần 0) thì bài toán (1.6) – (1.8) không có phương án tối ưu. Chú ý: i) Nếu bài toán giả tạo không có phƣơng án tối ƣu thì bài toán (1.6) – (1.8) cũng không có phƣơng án tối ƣu. ii) Trong khi giải bài toán giả tạo ta không cần phải xác định cụ thể số M0 là bao nhiêu, chỉ cần xem M là số lớn hơn bất cứ số nào cần so sánh với nó trong suốt quá trình tính toán. Do hàm mục tiêu của bài toán giả tạo là một hàm tuyến tính đối với M nên các ƣớc lƣợng j sẽ có dạng j = jM + j. Vì số M là rất lớn nên so sánh các j ta có quy tắc sau: j 0 nếu j > 0 (bất kể j) hoặc ( j = 0, j > 0). j > k nếu j > k hoặc ( j = k, j > k ). Khi giải bài toán ta có thể tách hàng j thành hai hàng; dòng trên ghi j, dòng dƣới ghi j. iii) Khi An+i không tham gia trong cơ sở nữa thì ta không cần tính cột n + i. - 39 -
  44. Ví dụ 12: Trở lại bài toán trên, với cơ sở liên kết đơn vị {A4, A6, A7} ta có phƣơng án cực biên xuất phát là X o 0,0,0,6,06,4 . Ta có bảng đơn hình (Bảng 1.7): Bảng 1.7 Cơ Hệ -1 -2 1 0 0 M M Bảng Tọa sở số số độ xio A1 A2 A3 A4 A5 A6 A7 Ai ci A4 0 6 -1 4 -2 1 0 0 0 A6 M 6 1 1 2 0 -1 1 0 I A7 M 4 2 -1 2 0 0 0 1 j 0 1 2 -1 0 0 0 0 j 10 3 0 4 0 -1 0 0 A4 0 10 1 3 0 1 0 0 A6 M 2 -1 2 0 0 -1 1 II A3 1 2 1 1 2 1 0 0 0 j 2 2 3 2 0 0 0 0 j 2 -1 2 0 0 -1 0 A4 0 7 5 2 0 0 1 3 2 A2 -2 1 1 2 1 0 0 1 2 III A3 1 3 4 0 1 0 1 4 1 2 11 4 0 0 0 3 4 A1 -1 14 5 1 0 0 2 5 3 5 A2 -2 12 5 0 1 0 1 5 1 5 IV A3 1 0 0 1 3 10 7 10 36 5 0 0 0 11 10 9 10 - 40 -
  45. Tại bảng IV, có j 0, j = 1,5 nên ta có phƣơng án tối ƣu là: 14 12 2 36 X = ( , , , 0, 0, 0) và fmax = - gmin = . 5 5 5 5 Như vậy: Để giải một bài toán QHTT không suy biến bất kỳ ta thực hiện theo các bƣớc sau: a) Đƣa bài toán về dạng chính tắc nếu nó không ở dạng chính tắc. b) Thêm biến giả tạo và giải bài toán giả tạo nếu chƣa biết phƣơng án cực biên xuất phát. c) Từ lời giải của bài toán chính tắc hay bài toán giả tạo ta suy ra lời giải của bài toán đã cho. - 41 -
  46. Chƣơng 2 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU Chƣơng này đề cập tới vấn đề đối ngẫu trong quy hoạch tuyến tính (QHTT). Đối ngẫu là một phƣơng pháp mà tƣơng ứng với mỗi bài toán quy hoạch tuyến tính đã cho (gọi là bài toán gốc) ta có thể thiết lập một bài toán quy hoạch tuyến tính khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta sẽ thu đƣợc thông tin về lời giải của bài toán kia. Sau đây, chúng tôi trình bày cách xây dựng bài toán đối ngẫu của một bài toán quy hoạch tuyến tính đã cho, nêu các định lý đối ngẫu cơ bản và phƣơng pháp đơn hình đối ngẫu. 1. KHÁI NIỆM BÀI TOÁN QHTT ĐỐI NGẪU 1.1. Bài toán quy hoạch tuyến tính đối ngẫu không đối xứng Cho bài toán QHTT dạng chính tắc (I): n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (2.1) j1 n aij x j b i , i 1,m (2.2) với điều kiện j1 xj 0, j 1,n (2.3) Định nghĩa 2.1. Bài toán QHTT (I) sau m g(X) b1 y 1 b 2 y 2 b m y m b i y i max (2.1)' i1 m aij y i c j , j 1,n (2.2)' với điều kiện i1 yi R , i 1,m đƣợc gọi là bài toán QHTT đối ngẫu của bài toán gốc (I). Cặp bài toán (I) và bài toán đƣợc gọi là cặp bài toán QHTT đối ngẫu không đối xứng. - 42 -
  47. Nhận xét: Phân tích cấu trúc của hai bài toán, ta có thể rút ra những nhận xét, đồng thời là những nguyên tắc thành lập bài toán đối ngẫu: (i) Nếu bài toán gốc tìm Min thì bài toán đối ngẫu tìm Max và hệ ràng buộc của bài toán đối ngẫu có dạng “ ”. (ii) Số ràng buộc (không kể ràng buộc về dấu) trong bài toán này bằng số biến số trong bài toán kia, từ đó ta thấy tƣơng ứng với mỗi ràng buộc của bài toán này là một biến số của bài toán kia. (iii) Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc trong bài toán kia. (iv) Ma trận điều kiện trong hai bài toán là chuyển vị của nhau. (v) Các biến số trong bài toán đối ngẫu không có ràng buộc về dấu. Định nghĩa 2.2. Các cặp bất phƣơng trình sau m xj 0 và a ij y i c j , j 1,n . i1 n aij x j b i và yi R, i 1,m . j1 đƣợc gọi là các cặp điều kiện đối ngẫu. Ví dụ 2.1: Cho bài toán QHTT f(X) = 13x1 – 3x2 – 4x3 + 19x4 min 2x1 x 2 x 3 3x 4 44 x1 2x 2 3x 3 x 4 23 với điều kiện 3x1 x 2 x 3 6x 4 96 xj 0, j 1,4 Viết bài toán đối ngẫu cho bài toán này và chỉ ra các cặp điều kiện đối ngẫu. Giải: Do bài toán gốc tìm Min nên bài toán đối ngẫu tìm Max và bài toán gốc có 3 ràng buộc (không kể ràng buộc về dấu) nên bài toán đối ngẫu có số ẩn là 3. Hệ số hàm mục tiêu của bài toán đối ngẫu tƣơng ứng là vế phải hệ ràng buộc của bài toán gốc. - 43 -
  48. Do đó g(Y) = 44y1 + 23y2 + 96y3 max Các cặp điều kiện đối ngẫu: 2x1 x 2 x 3 3x 4 44 và y 1 R x1 2x 2 3x 3 x 4 23 và y 2 R 3x1 x 2 x 3 6x 4 96 và y 3 R x1 0 và 2y 1 y 2 3y 3 13 x2 0 và y 1 2y 2 3y 3 3 x3 0 và y 1 3y 2 3y 3 4 x4 0 và 3y 1 y 2 6y 3 19 Ta có bài toán đối ngẫu: g(Y) = 44y1 + 23y2 + 96y3 max y1,y2 , y3 R 2y1 y2 3y3 13 với điều kiện y1 2y2 3y3 3 y1 3y2 3y3 4 3y1 y2 6y3 19 Chú ý: Nếu bài toán gốc (I) đƣợc viết dƣới dạng ma trận f(X) = CX min AX B với điều kiện X O thì bài toán đối ngẫu (I) có dạng: g(Y) = YB max với điều kiện YA C, trong đó O là ma trận không cấp n 1, Y = (y1 y2 ym) là ma trận hàng cấp 1 m. 1.2. Quy tắc thành lập bài toán đối ngẫu Đối với bài toán bất kỳ để xác định bài toán đối ngẫu, trƣớc hết ta đƣa về bài toán dạng chính tắc, sau đó xây dựng bài toán đối ngẫu của bài toán này và gọi nó là bài toán đối ngẫu của bài toán đã cho. Việc làm trên khá phức tạp do đó chúng ta - 44 -
  49. có thể sử dụng các quy tắc nêu trong lƣợc đồ dƣới đây để trực tiếp viết bài toán đối ngẫu mà không cần phải thực hiện bƣớc biến đổi về dạng chính tắc. LƢỢC ĐỒ TỔNG QUÁT Dạng 1. n m Bài toán gốc: f (X) cjj x min Bài toán đối ngẫu: g(Y) bii y max j1 i1 m * Nếu xj 0 thì aij y i c j . i1 m * Nếu xj 0 thì aij y i c j . i1 m * Nếu xj không ràng buộc về dấu thì aij y i c j . i1 n * Nếu aij x j b i thì yi không ràng buộc về dấu. j1 n * Nếu aij x j b i thì yi 0. j1 n * Nếu aij x j b i thì yi 0. j1 Dạng 2. n m Bài toán gốc: f (X) cjj x max Bài toán đối ngẫu: g(Y) bii y min j1 i1 m * Nếu xj 0 thì aij y i c j . i1 m * Nếu xj 0 thì aij y i c j . i1 m * Nếu xj không ràng buộc về dấu thì aij y i c j . i1 n * Nếu aij x j b i thì yi không ràng buộc về dấu. j1 n * Nếu aij x j b i thì yi 0. j1 n * Nếu aij x j b i thì yi 0. j1 - 45 -
  50. Chú ý: Do tính đối xứng của cặp bài toán đối ngẫu nên khái niệm bài toán gốc và bài toán đối ngẫu chỉ mang tính tƣơng đối, nghĩa là nếu bài toán này là bài toán gốc thì bài toán kia là bài toán đối ngẫu và ngƣợc lại. Ví dụ 2.2: Viết bài toán đối ngẫu của bài toán sau: f(X) = - 4x1 + x2 + 5x3 + 3x5 min 3x1 6x 2 x 3 2x 4 4x 5 15 2x1 3x 2 4x 3 5x 4 x 5 8 với điều kiện 6x2 3x 3 8x 4 4x 5 9 3x1 2x 2 3x 4 x 5 24 x1 0, x 3 0, x 5 0. Giải: Bài toán đối ngẫu có dạng g(Y) = - 15y1 + 8y2 + 9y3 + 24y4 max 3y1 2y 2 3y 4 4 6y 3y 6y 2y 1 với điều kiện 1 2 3 4 y1 4y 2 3y 3 5 2y1 5y 2 8y 3 3y 4 0 4y1 y 2 4y 3 y 4 3 y 0 1 y2 0 y4 0 1.3. Bài toán quy hoạch tuyến tính đối ngẫu đối xứng Cho bài toán quy hoạch tuyến tính dạng chuẩn tắc (II) n f (X) cjj x min (2.4) j1 n aij x j b i , i 1,m (2.5) với điều kiện j1 xj 0, j 1,n (2.6) Khi đó bài toán đối ngẫu của bài toán (II) là bài toán (II) - 46 -
  51. m g(Y) bii y max (2.4)’ i1 m aij y i c j , j 1,n (2.5)' với điều kiện i1 yj 0, i 1,m (2.6)' Định nghĩa 2.3. Cặp bài toán (II) và bài toán (II) đƣợc gọi là cặp bài toán đối ngẫu đối xứng. Dùng các ký hiệu ma trận ta có thể viết cặp bài toán QHTT đối ngẫu đối xứng trên nhƣ sau: Bài toán gốc Bài toán đối ngẫu min f(X) CX max g(Y) YB AX B YA C Với điều kiện Với điều kiện XOn1 YO1m Chú ý: Cặp bài toán QHTT đối ngẫu đối xứng trên có m + n cặp điều kiện đối ngẫu. Ví dụ 2.3: Tìm bài toán đối ngẫu của bài toán f(X) 2x1 x 2 x 3 min x1 2x 2 x 3 2 với điều kiện 2x1 x 2 2x 3 5 x1 ,x 2 ,x 3 0 Giải: Bài toán đối ngẫu là g(Y) 2y12 5y max y12 2y 2 2y y 1 với điều kiện 12 y12 2y 1 y12 ,y 0 - 47 -
  52. 2. CÁC ĐỊNH LÝ ĐỐI NGẪU Ta có các định lý sau đây phản ánh mối quan hệ giữa bài toán gốc và bài toán đối ngẫu. Các chứng minh đƣợc thực hiện cho cặp bài toán đối ngẫu không đối xứng. Sự đúng đắn của các kết luận đối với cặp bài toán đối ngẫu tùy ý đƣợc suy ra từ nhận xét mọi cặp bài toán đối ngẫu có thể đƣa đƣợc về dạng cặp bài toán đối ngẫu không đối xứng. Xét cặp bài toán QHTT đối ngẫu không đối xứng Bài toán gốc (I) Bài toán đối ngẫu (I) f (X) CX min g(Y) YB max AX B Với điều kiện với điều kiện YA C XOn1 Định lý 2.1. Giả sử X là phương án tùy ý của bài toán gốc (I), Y là phương án tùy ý của bài toán đối ngẫu (I) . Khi đó ta luôn có f(X) g(Y). Chứng minh: Giả sử X là phƣơng án tùy ý của bài toán (I), Y là phƣơng án tùy ý của bài toán (I) . n n m m n m f(X) = CX = cxjj aij y i x j a ij x j y i = byii = YB = g(Y) j1 j 1 i 1 i 1 j 1 i1 Vậy f(X) g(Y). ■ Định lý 2.2. Nếu X* là phương án của bài toán (I), Y* là phương án của bài toán thỏa mãn f(X*) = g(Y*) thì X* là phương án tối ưu của bài toán (I) và Y* là phương án tối ưu của bài toán đối ngẫu . Chứng minh: Giả sử X là phƣơng án bất kỳ của bài toán (I), theo định lý 2.1 chƣơng 2, ta có f(X) g(Y*) = f(X*), X Suy ra min{f(X)} = f(X*). Do đó X* là phƣơng án tối ƣu của bài toán (I). Tƣơng tự, lấy Y là phƣơng án bất kỳ của bài toán , ta có - 48 -
  53. g(Y) f(X*) = g(Y*), Y Suy ra max{g(Y)} = g(Y*). Do đó Y* là phƣơng án tối ƣu của bài toán (I) . ■ Hệ quả 2.1. Cặp bài toán đối ngẫu (I) và có phương án tối ưu khi và chỉ khi chúng có phương án. Chứng minh: Điều kiện cần: Hiển nhiên. Điều kiện đủ: Giả sử X0, Y0 là cặp phƣơng án của bài toán (I), . Để chứng minh bài toán (I) và có phƣơng án tối ƣu, ta chứng minh hàm mục tiêu của chúng bị chặn. Thật vậy, lấy X là phƣơng án bất kỳ của bài toán (I), theo định lý 2.1 chƣơng 2, ta có: f(X) g(Y0), X Suy ra hàm mục tiêu f(X) bị chặn dƣới trong tập phƣơng án của bài toán gốc (I), theo định lý 1.7 chƣơng 1 thì bài toán gốc (I) phải có phƣơng án tối ƣu. Vẫn theo định lý 2.1 chƣơng 2, ta có g(Y) f(X0), Y. Suy ra g(Y) bị chặn trên trong tập phƣơng án của bài toán , theo định lý 1.7 chƣơng 1, thì bài toán phải có phƣơng án tối ƣu.■ Hệ quả 2.2. Nếu một trong hai bài toán (I) hoặc có tập phương án khác nhưng không có phương án tối ưu thì bài toán kia có tập phương án là . Chứng minh: (Sinh viên tự chứng minh xem như bài tập) Định lý 2.3. (Định lý đối ngẫu thứ nhất) Nếu một trong hai bài toán của cặp bài toán đối ngẫu có phương án tối ưu thì bài toán kia cũng có phương án tối ưu, đồng thời min{f(X)} = max{g(Y)} Ta thừa nhận định lý vừa nêu. - 49 -
  54. Định lý 2.4. (Định lý lệch – bù hay định lý đối ngẫu thứ hai) Cặp phương án X*, Y* tương ứng của cặp bài toán đối ngẫu là tối ưu khi và chỉ khi trong từng cặp điều kiện đối ngẫu, nếu điều kiện này thỏa mãn lỏng thì điều kiện kia thỏa mãn chặt. Áp dụng của các định lý đối ngẫu. 1. Khảo sát sự tồn tại phương án, phương án tối ưu Ví dụ 1: Cho bài toán QHTT f(X) = 2x1 – x2 + 3x3 – 2x4 min x12 x 15 với điều kiện x34 x 8 xj 0, j 1,4 Hãy viết bài toán đối ngẫu và chứng tỏ nó có phƣơng án tối ƣu? Giải: Bài toán đối ngẫu g(Y) = 15y1 + 8y2 max y1 2 y 1 với điều kiện 1 y2 3 y2 2 Dễ dàng thấy rằng X(15, 8) và Y(1, 2) là các phƣơng án của cặp bài toán đối ngẫu. Theo hệ quả 1, suy ra bài toán có phƣơng án tối ƣu. Mặt khác, do hạng của hệ ràng buộc của bài toán đối ngẫu bằng 2 do đó nó có phƣơng án cực biên tối ƣu. 2. Kiểm tra một phương án có tối ưu hay không. ▪ Nếu biết cặp phƣơng án X*, Y* thì chỉ cần kiểm tra điều kiện f(X*) = f(Y*) ▪ Nếu chỉ biết phƣơng án X* thì sử dụng định lý lệch bù tìm phƣơng án Y* của bài toán đối ngẫu. Ví dụ 2: Cho bài toán QHTT - 50 -
  55. f X 2x1 4x 2 x 3 max x1 3x 2 x 4 4 2x1 x 2 x 3 3 với điều kiện x24 3x 3 xj 0, j 1,4 a) Hãy chứng tỏ Xo(1, 1, 0, 0) là phƣơng án cực biên đồng thời tại = 0 nó cũng là phƣơng án tối ƣu. b)Tìm phƣơng án tối ƣu của bài toán đối ngẫu. Xác định để bài toán có vô số phƣơng án tối ƣu. Giải: a) Thử lại ta thấy ngay X0 là phƣơng án của bài toán đã cho. Mặt khác X0 thỏa mãn chặt 4 ràng buộc độc lập, vậy nó là phƣơng án cực biên. Xét bài toán đối ngẫu 4y1 3y 2 3y 3 min y12 2y 2 3y1 y 2 y 3 4 với điều kiện y2 y13 3y 0 y3 0 Áp dụng định lý lệch bù, ở đây x1, x2 > 0 và X0 thỏa mãn lỏng điều kiện thứ 3 nên ta có hệ phƣơng trình y12 2y 2 6 2 3y y y 4 Y( , ,0 ) 1 2 3 5 5 y3 0 Thử lại ta thấy Y0 là phƣơng án của bài toán đối ngẫu. Vậy tại = 0, X0 là phƣơng án tối ƣu. - 51 -
  56. b) Rõ ràng tại = 0, Y0 cũng là phƣơng án tối ƣu của bài toán đối ngẫu. Không 2 những thế, với mọi thì Y0 cũng là phƣơng án của bài toán đối ngẫu. Do đó 5 với mọi ta có X0 là phƣơng án tối ƣu. Với 0, do đó phƣơng án tối ƣu X (nếu có) phải thỏa mãn: x1 3x 2 x 4 4 2x1 x 2 x 3 3 x3 0 5 x 5 2x Giải ra ta đƣợc X = 44, ,0,x 55 4 Để X là phƣơng án thì X phải thỏa mãn các điều kiện còn lại x1, x2, x4 0 và x2 – 3x4 3. Từ đó suy ra 12 x 554 Vậy khi < thì tập phƣơng án tối ƣu của bài toán gốc là 5 x 5 2x 12 X = 44, ,0,x , với x . 55 4 554 3. PHƢƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU 3.1. Nội dung phƣơng pháp Về thực chất, đây là phƣơng pháp đơn hình áp dụng vào bài toán đối ngẫu, nhƣng để tìm lời giải của bài toán gốc. Phƣơng pháp này do Lemke G. E. đề xuất năm 1954. Phƣơng pháp đơn hình giải bài toán QHTT bắt đầu từ một phƣơng án cực biên xuất phát (nghiệm đúng AX = B và X 0) mà chƣa thỏa mãn tiêu chuẩn tối - 52 -
  57. ƣu. Sau mỗi bƣớc lặp ta tìm đƣợc một phƣơng án cực biên mới tốt hơn phƣơng án cũ và quá trình này tiếp tục cho đến khi tìm đƣợc một phƣơng án thỏa mãn tiêu chuẩn tối ƣu. Phƣơng pháp đơn hình đối ngẫu, lại xuất phát từ một “giả phương án” (nghiệm đúng phƣơng trình AX = B) mà nó thỏa mãn tiêu chuẩn tối ƣu ( j 0) nhƣng không thỏa mãn X 0, nghĩa là bảng đơn hình ban đầu không có phần tử dƣơng trong dòng ƣớc lƣợng (dòng cuối) nhƣng lại có phần tử âm ở cột phƣơng án (vì thế có tên là cột giả phương án). Các bảng đơn hình đƣợc biến đổi sao cho luôn đảm bảo điều kiện tối ƣu và quá trình này tiếp diễn cho đến khi nhận đƣợc phƣơng án (không còn phần tử âm trong cột Giả phƣơng án). Phƣơng án đó đƣợc gọi là phƣơng án tối ƣu. 3.2. Thuật toán đơn hình đối ngẫu Bước 1. Xuất phát từ hệ m vectơ độc lập tuyến tính có ma trận D = [Aj] với j J, |J| = m, sao cho mọi j 0, j = 1,n. -1 c Tìm giả phƣơng án X0 = (X*, 0), trong đó X* = C*D , với C* = i iJ; xj = 0, j J. Bước 2. Kiểm tra xi 0, i J? + Nếu có, thì X là phƣơng án tối ƣu. + Nếu không, thì sang bƣớc 3. Bước 3. Tại xi < 0, kiểm tra xij 0, j = ? + Nếu có, bài toán không có phƣơng án tối ƣu. + Nếu không, sang bƣớc 4. Bước 4. Tồn tại xi < 0, tồn tại xij < 0. Chọn xl min xi đƣa Al ra khỏi cơ sở. xi 0 Bước 5. Tìm phần tử trục xlk từ cách chọn: j k 0 = min đƣa Ak vào cơ sở mới. x0 lj xxlj lk - 53 -
  58. Bước 6. Xây dựng phƣơng án X1 bằng cách biến đổi bảng đơn hình nhƣ thƣờng lệ. Gán X0 := X1, rồi trở lại bƣớc 2. Chú ý: Trong trƣờng hợp bài toán đối ngẫu suy biến thì có thể o = 0, khi o = 0 ta vẫn áp dụng thuật toán bình thƣờng, điều này làm nảy sinh khả năng xuất hiện hiện tƣợng xoay vòng. tuy nhiên, giống nhƣ phƣơng pháp đơn hình, trong thực tế tính toán ta dễ dàng thoát khỏi hiện tƣợng xoay vòng. Dấu hiệu xuất hiện phƣơng án cực biên suy biến là o đạt tại nhiều chỉ số, khi đó các véc tơ ứng với o đều có thể đƣa vào cơ sở, vì vậy ta chọn véc tơ bất kỳ một cách ngẫu nhiên trong số chúng đƣa vào cơ sở mà không cần sử dụng quy tắc từ vựng. Ví dụ 2.6: Giải bài toán sau đây bằng phƣơng pháp đơn hình đối ngẫu f(X)x1 x 2 x 3 x 4 x 5 min 2x1 x 3 x 4 3x 5 6 x14 x 3 với điều kiện 4x1 x 2 x 4 2x 5 5 xj 0, j 1,5 Giải: Đƣa thêm ẩn phụ x6 0, ta có bài toán dạng chính tắc f(X)x1 x 2 x 3 x 4 x 5 min 2x1 x 3 x 4 3x 5 6 x1 x 4 x 6 3 với điều kiện 4x1 x 2 x 4 2x 5 5 xj 0, j 1,6 Nếu chọn cơ sở A3A6A2, ta đƣợc giả phƣơng án X0 = (0, 5, 6, 0, 0, -3) Ta có bảng đơn hình đối ngẫu: Bảng 2.1 - 54 -
  59. Bảng Cơ sở Hệ số Tọa 1 -1 1 1 1 0 số Ai ci độ xio A1 A2 A3 A4 A5 A6 A3 1 6 2 0 1 -1 3 0 A6 0 -3 -1 0 0 -1 0 1 I A2 -1 5 4 1 0 -1 2 0 f(X) = 1 -3 0 0 -1 0 0 A3 1 9 3 0 1 0 3 -1 A4 1 3 1 0 0 1 0 -1 II A2 -1 8 5 1 0 0 2 -1 f(X) = 4 -2 0 0 0 0 -1 Tại bảng II, có các phần tử trong cột giả phƣơng án đều không âm nên phƣơng án tối ƣu của bài toán là X(0, 8, 9, 3, 0) và fmin = 4. - 55 -