Tài liệu Thuật toán đơn hình đối ngẫu và ứng dụng trong tái tối ưu hóa với ràng buộc phụ

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỖ HOÀNG TÙNG THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU VÀ ỨNG DỤNG TRONG TÁI TỐI ƯU HÓA VỚI RÀNG BUỘC PHỤ (The dual simplex method and its applications to reoptimization with supplementary constraints) Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. TRẦN VŨ THIỆU Thái Nguyên - 2015 MỤC LỤC Trang MỞ ĐẦU 3 Chương 1. Kiến thức về qui hoạch tuyến tính 5 1.1. Bài toán qui hoạch tuyến tính và bài toán đối ngẫu 5 1.2. Các định lý đối ngẫu 8 1.3. Phương pháp đơn hình gốc và đơn hình đối ngẫu Chương 2. Thuật toán đơn hình đối ngẫu 10 14 2.1. Thuật toán đơn hình đối ngẫu dạng đầy đủ 14 2.2. Thuật toán đơn hình đối ngẫu dạng cải biên 19 2.3. Áp dụng giải trò chơi ma trận 24 Chương 3. Kỹ thuật tái tối ưu hóa với ràng buộc phụ 28 3.1. Vấn đề tái tối ưu hóa 28 3.2. Thuật toán đơn hình đối ngẫu trong tái tối ưu hóa 29 3.3. Ví dụ minh họa 30 KẾT LUẬN 34 TÀI LIỆU THAM KHẢO 35 2 MỞ ĐẦU Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Qui hoạch tuyến tính có nhiều ứng dụng rộng rãi trong lý thuyết và thực tiễn. Với mỗi bài toán qui hoạch tuyến tính đã cho (gọi là bài toán gốc) được gắn với một bài toán qui hoạch tuyến tính khác (gọi là bài toán đối ngẫu). Hai bài toán này có quan hệ chặt chẽ với nhau và là cặp bài toán đối ngẫu của nhau. Nghiên cứu bài toán đối ngẫu sẽ giúp hiểu rõ hơn về bài toán gốc và ngược lại. Phương pháp đơn hình (do G. B. Dantzig đề xuất năm 1947) là phương pháp quen thuộc, có hiệu qủa để giải bài toán qui hoạch tuyến tính. Phương pháp đơn hình có nhiều biến thể khác nhau, phù hợp với các dạng cụ thể của bài toán qui hoạch tuyến tính như: đơn hình gốc, đơn hình cải biên, đơn hình đối ngẫu, đơn hình gốc - đối ngẫu ... Trong một số tình huống thực tế, sau khi giải xong bài toán ta thấy cần bổ sung thêm một số ràng buộc vào bài toán. Nếu giải lại bài toán từ đầu thì sẽ tốn nhiều thời gian và công sức. Việc tận dụng lời giải đã có để giải tiếp bài toán mới gọi là kỹ thuật tái tối ưu hóa bài toán. Để làm việc này, phương pháp đơn hình đối ngẫu rất hữu ích. Vì thế cần đi sâu tìm hiểu về phương pháp này, cùng các dạng thể hiện cụ thể và các ứng dụng của nó trong kỹ thuật tái tối ưu hóa. Với ý nghĩa đó, chúng tôi chọn đề tài luận văn: "Thuật toán đơn hình đối ngẫu và ứng dụng trong tái tối ưu hóa với ràng buộc phụ " Mục đích chính của đề tài là tìm hiểu và trình bày kết quả lý thuyết về bài toán qui hoạch tuyến tính và qui hoạch tuyến tính đối ngẫu, các thuật toán khác nhau của phương pháp đơn hình đối ngẫu và ứng dụng thuật toán đơn hình đối ngẫu trong tái tối ưu hóa khi thêm ràng buộc phụ vào bài toán. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [4]. 3 Các kết quả cần đạt được: hiểu và trình bày được một số nội dung chính sau: a) Bài toán qui hoạch tuyến tính và bài toán đối ngẫu. Lý thuyết đối ngẫu. b) Phương pháp đơn hình đối ngẫu và các thuật toán đơn hình đối ngẫu. c) Phương pháp tái tối ưu hóa khi thêm ràng buộc phụ vào bài toán đã giải. Cấu trúc luận văn gồm 3 chương. • Chương 1 “Kiến thức chuẩn bị” nhắc lại tổng quan vắn tắt một số kiến thức cơ bản cần thiết về qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu, các định lý đối ngẫu trong qui hoạch tuyến tính, với nhiều ví dụ số và hình vẽ minh họa cho các sự kiện, các định lý đã trình bày. Cuối chương giới thiệu ý tưởng cơ bản của phương pháp đơn hình gốc, đơn hình đối ngẫu giải qui hoạch tuyến tính. • Chương 2 "Thuật toán đơn hình đối ngẫu " trình bày chi tiết các bước tính toán của thuật toán đơn hình đối ngẫu dạng đầy đủ và thuật toán đơn hình đối ngẫu dạng cải biên. Cuối chương trình bày ví dụ áp dụng thuật toán đơn hình đối ngẫu dạng đầy đủ vào giải bài toán trò chơi ma trận. • Chương 3 “Kỹ thuật tái tối ưu hóa với ràng buộc phụ” trình bày vấn đề tái tối ưu hóa khi thêm ràng buộc vào bài toán sau khi đã giải xong và vai trò của việc áp dụng thuật toán đơn hình đối ngẫu trong tái tối ưu hóa. Cuối chương nêu ví dụ minh họa. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Trần Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả chân thành cảm ơn các thầy giáo, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên, Viện Toán hoc - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. 4 Chương 1 KIẾN THỨC VỀ QUI HOẠCH TUYẾN TÍNH Chương này trình bày tóm tắt một số kiến thức cơ bản cần thiết về qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu, các định lý đối ngẫu trong qui hoạch tuyến tính và phương pháp đơn hình gốc, đơn hình đối ngẫu giải qui hoạch tuyến tính. Nội dung của chương được tham khảo từ các tài liệu [1], [3] và [4]. 1.1. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH VÀ BÀI TOÁN ĐỐI NGẪU 1.1.1. Phát biểu bài toán Bằng các phép biến đổi đơn giản, một bài toán qui hoạch tuyến tính bất kỳ có thể đưa được về một trong hai dạng chính sau đây. • Dạng chuẩn tắc: min {f(x) = cTx : Ax ≥ b, x ≥ 0}, trong đó A ∈ ℝm×n, b ∈ ℝm, c  ℝn, x ≥ 0 có nghĩa x ∈ ℝ n . Trong bài toán này tập ràng buộc D = {x ∈ ℝn : Ax ≥ b, x ≥ 0} là một tập lồi đa diện. • Dạng chính tắc: min {f(x) = cTx : Ax = b, x ≥ 0}, trong đó A, b, c và x được xác định như ở trên. Trong bài toán này tập ràng buộc D = {x ∈ ℝn : Ax = b, x ≥ 0} cũng là một tập lồi đa diện. Có thể dễ dàng chuyển từ dạng chuẩn tắc sang dạng chính tắc và ngược lại. Trong các bài toán trên f(x) được gọi là hàm mục tiêu. Mỗi bất phương trình (Ax)i ≥ bi hay phương trình (Ax)i = bi gọi là một ràng buộc chính, xj ≥ 0, j = 1,..., n gọi là các ràng buộc không âm hay ràng buộc về dấu. Véctơ (điểm) x ∈ D gọi là một nghiệm chấp nhận được hay một phương án. Một phương án đạt cực tiểu của hàm mục tiêu f(x) gọi là một phương án tối ưu hay một nghiệm tối ưu của bài toán. 1.1.2. Các tính chất cơ bản Định lý sau nêu điều kiện để một qui hoạch tuyến tính có nghiệm tối ưu. 5 Định lý 1.1. Nếu một qui hoạch tuyến tính có nghiệm chấp nhận được và nếu hàm mục tiêu bị chặn dưới trên tập ràng buộc (đối với bài toán min) thì qui hoạch đó chắc chắn có nghiệm tối ưu. Định lý 1.2. Nếu x0 là một phương án tối ưu của bài toán qui hoạch tuyến tính dạng bất kỳ và nếu x1, x2 (x1 ≠ x2) là hai phương án thỏa mãn x0 = x1 + (1  )x2, 0 <  < 1, thì x1, x2 cũng là các phương án tối ưu của bài toán. Định nghĩa 1.1. Một nghiệm chấp nhận được x ∈ D mà đồng thời là một đỉnh của D được gọi là một nghiệm cơ sở hay một phương án cực biên, nghĩa là x không thể biểu diễn được dưới dạng một tổ hợp lồi của bất kỳ hai nghiệm chấp nhận được (phương án) nào khác của bài toán. Định lý sau nêu một tính chất đặc trưng cho phương án cực biên (nghiệm cơ sở) của bài toán qui hoạch tuyến tính chính tắc với giả thiết m ≤ n và rank (A) = m. Định lý 1.3. Để một nghiệm chấp nhận được x = { x1 , x 2 , ... , x n } của qui hoạch tuyến tính chính tắc là nghiệm cơ sở thì cần và đủ là các véctơ cột Aj của ma trận A ứng với các thành phần x j > 0 là độc lập tuyến tính. Người ta phân ra hai loại nghiệm cơ sở: không suy biến nếu nghiệm đó có số thành phần dương bằng m và suy biến nếu nó có số thành phần dương nhỏ hơn m. Định lý sau cho thấy qui hoạch tuyến tính chính tắc có phương án cực biên. Định lý 1.4. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có ít nhất một phương án thì nó cũng có phương án cực biên, nghĩa là tập ràng buộc D có đỉnh. Định lý sau cho phép tìm phương án tối ưu của bài toán qui hoạch tuyến tính chính tắc trong số các phương án cực biên của bài toán (số này hữu hạn). Định lý 1.5. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó cũng có phương án cực biên tối ưu. Ví dụ 1.1. Xét bài toán qui hoạch tuyến tính f(x) =  x1 + x2  min, với các điều kiện: x1  3x2  2, 3x1  x2  14, x1  0, x1 + 4x2  22,  x1 + x2  3, x2  0. 6 Tập ràng buộc của bài toán là đa giác lồi 6 đỉnh vẽ ở Hình 1.1. Tọa độ các đỉnh: O = (0, 0), A = (2, 0), B = (5, 1), C = (6, 4), D = (2, 5), E = (0, 3). Theo Định lý 1.5, nghiệm tối ưu của bài toán đạt được tại một trong các đỉnh của đa giác. Tính giá trị hàm mục tiêu tại các đỉnh này, ta nhận được: f(O) = 0, f(A) =  2, f(B) =  4, f(C) =  2, f(D) = 3 và f(E) = 3. Từ đó cho thấy cực tiểu của hàm f đạt tại đỉnh B (5, 1) với giá trị cực tiểu fmin =  4. x2 D C E min B O x1 A Hình 1.1. Tập ràng buộc của bài toán ở Ví dụ 1.1. 1.1.3. Cặp bài toán đối ngẫu Đối ngẫu là phương pháp mà ứng với mỗi bài toán qui 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 qui hoạch khác (gọi là bài toán đối ngẫu) sao cho từ nghiệm của bài toán này ta sẽ thu được thông tin về nghiệm của bài toán kia. Sau đây là hai dạng cặp bài toán đối ngẫu thường gặp. • Đối ngẫu của qui hoạch tuyến tính dạng chuẩn tắc (qui hoạch gốc) (P) min {f(x) = cTx : Ax ≥ b, x ≥ 0} là bài toán qui hoạch tuyến tính (qui hoạch đối ngẫu): (Q) max {g(y) = bTy : ATy ≤ c, y ≥ 0} (AT là ma trận chuyển vị của ma trận A). Ví dụ 1.2. Đối ngẫu của bài toán qui hoạch tuyến tính chuẩn tắc f(x) = 20x1 + 15x2  min, 3x1 + x2  60, 7 x1 + x2  40, x1 + 2x2  60, x1  0, x2  0, là bài toán qui hoạch tuyến tính: g(y) = 60y1 + 40y2 + 60y3  max, 3y1 + y2 + y3  20, y1 + y2 + 2y3  15, y1  0, y2  0, y3  0. • Đối ngẫu của qui hoạch tuyến tính dạng chính tắc (qui hoạch gốc): (P) min {f(x) = cTx : Ax = b, x ≥ 0} là bài toán qui hoạch tuyến tính (qui hoạch đối ngẫu): (Q) max {g(y) = bTy : ATy ≤ c}. Ví dụ 1.3. Đối ngẫu của bài toán qui hoạch tuyến tính chính tắc + 0,8x4 + 0,6x5  min, f(x) = 0,2x1 2x1 + x3 + 2x2 + x5 = 400, + x5 = 400, x2 + 2x3 + 3x4 = 1300, xj  0, j = 1, 2, 3, 4, 5. là bài toán qui hoạch tuyến tính: g(y) = 400y1 + 400y2 + 1300y3  max,  0,2 2y1 2y2 + y1 + y3  0, 2y3  0, 3y3  0,8 y1  0,6. + y2 Dễ kiểm tra lại rằng lấy đối ngẫu của bài toán đối ngẫu ta được lại bài toán gốc. Vì thế ta gọi (P) và (Q) là cặp bài toán qui hoạch tuyến tính đối ngẫu nhau. 8 1.2. CÁC ĐỊNH LÝ ĐỐI NGẪU Các kết quả nêu dưới đây đúng cho cặp bài toán đối ngẫu (P), (Q) dạng bất kỳ. Định lý 1.6 (Đối ngẫu yếu). Nếu x là một lời giải chấp nhận được của bài toán gốc (P) và y là một lời giải chấp nhận được của bài toán đối ngẫu (Q) thì f(x) = c1x1 + c2x2 + ... + cnxn ≥ g(y) = b1y1 + b2y2 + ... + bmym, nghĩa là giá trị mục tiêu của một phương án gốc bất kỳ (bài toán min) không nhỏ hơn giá trị mục tiêu của một phương án đối ngẫu bất kỳ (bài toán max). Định lý 1.7 (Đối ngẫu mạnh). Nếu một qui hoạch có nghiệm tối ưu thì qui hoạch đối ngẫu của nó cũng có nghiệm tối ưu và hai giá trị tối ưu bằng nhau. Các định lý trên cho thấy các quan hệ sau giữa hai qui hoạch gốc và đối ngẫu. Định lý 1.8 (Định lý đối ngẫu cơ bản). Đối với một cặp bài toán qui hoạch tuyến tính đối ngẫu nhau chỉ có một trong ba khả năng loại trừ nhau sau đây: a) Cả hai bài toán đều không có nghiệm chấp nhận được. b) Cả hai bài toán đều có nghiệm chấp nhận được. Khi đó, cả hai đều có nghiệm tối ưu và giá trị tối ưu của hai hàm mục tiêu bằng nhau. c) Một bài toán có nghiệm chấp nhận được và bài toán kia không có nghiệm chấp nhận được. Khi đó, bài toán có nghiệm chấp nhận được sẽ có giá trị tối ưu vô cực (+∞ hay - ∞ tùy theo bài toán max hay min). Các ví dụ sau đây minh hoạ cho các tình huống a) - c) nêu trên. a) Bài toán gốc và bài toán đối ngẫu không có phương án. f(x) = x1  min, g(y) = y1 + y2  max, x1 + x2  1 y1  y2 = 1 x1  x2  1 y1  y2 = 0 x1, x2 tuỳ ý y1  0, y2  0 b) Bài toán gốc và bài toán đối ngẫu có phương án. f(x) = 5x1 + 10x2  min, g(y) = 14y1 + 12y2  max, 9 2x1 + 3x2  14 2y1 + x1 + 4x2  12 y2  5 3y1 + 4y2  10 x1  0, x2  0 y1  0, y2  0 Phương án tối ưu của hai bài toán là x* = (4; 2) và y* = (2; 1) với f(x*) = g(y*) = 40. c) Bài toán gốc và bài toán đối ngẫu đều không có phương án tối ưu. f(x) = x1  min, g(y) = y1 + y2  max, x1 + x2  1 y1  y2  1 x1  x2  1 y1  y2  0 x1  0, x2  0 y1  0, y2  0 Quan hệ giữa cặp bài toán đối ngẫu nhau còn thể hiện ở định lý sau đây. Định lý 1.9 (Định lý độ lệch bù). Một cặp nghiệm chấp nhận được x, y của hai qui hoạch tuyến tính đối ngẫu nhau (P) và (Q) là cặp nghiệm tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: n yi(  a ijx j  bi) = 0 i = 1, 2, ... , m ⇔ yT(Ax  b) = 0, j 1 xj(cj  m  a ij yi ) = 0 j = 1, 2, ... , n ⇔ xT(c  ATy) = 0. i 1 Ví dụ 1.4. Xét cặp bài toán đối ngẫu chuẩn tắc: min {4x1 : x1 + x2  2, x1  x2  2, xj  0, x2  0} và max {2y1 + 2y2 : y1 + y2  4, y1  y2  0, y1  0, y2  0}. y2 x2 4 2 y* 2 0 4 2 x1 y1 0 x* Bài toán đối ngẫu Bài toán gốc Hình 1.1. Tập ràng buộc cặp bài toán đối ngẫu ở Ví dụ 1.3 10 4 Áp dụng Định lý 1.9 vào cặp bài toán đối ngẫu cho ở Ví dụ 1.3, ta thấy x và y là nghiệm tối ưu của các bài toán gốc và đối ngẫu tương ứng khi và chỉ khi x, y thỏa mãn hệ điều kiện sau: x1 + x2  2, x1  x2  2, x1  0, x2  0 (chấp nhận được gốc) y1 + y2  4, y1  y2  0, y1  0, y2  0 (chấp nhận được đối ngẫu) y1(x1 + x2  2) = 0, y2(x1  x2  2) = 0, (độ lệch bù yếu) x1(4  y1  y2) = 0, x2( y1 + y2) = 0 (độ lệch bù yếu) Kiểm tra trực tiếp cho thấy ràng x* = (2, 0) và y* = (0, 4) thỏa mãn hệ điều kiện trên. Vì thế, x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán đối ngẫu tương ứng và ta có hệ thức f(x*) = g(y*) = 8. 1.3. PHƯƠNG PHÁP ĐƠN HÌNH GỐC VÀ ĐƠN HÌNH ĐỐI NGẪU  Cơ sở lý thuyết. Xét qui hoạch tuyến tính chính tắc (m ràng buộc đẳng thức, n biến): (P) min{f(x) = cTx : Ax = b, x  0} với A là ma trận mn, b  ℝm, c và x  ℝn. Ta giả thiết: m  n và rank (A) = m. Bài toán đối ngẫu của (P) có dạng (với y  ℝm, s  ℝn): (Q) max {g(y) = bTy : ATy  c} = max {bTy : ATy + s = c, s  0}. Định nghĩa 1.2. Giả sử B là ma trận con cấp mm của A. Nếu B có hạng m thì ta nói B là một cơ sở của A. Giả sử cơ sở B gồm m véctơ cột A j , A j , … , A j của A. 1 2 m Ký hiệu J = {j1, j2, ... , jm}. Để cho tiện, đôi khi ta cũng gọi J là cơ sở. Các véctơ Aj và các biến xj với j  J lần lượt được gọi là các véctơ cơ sở và biến cơ sở. Còn các véctơ Aj và các biến xj với j  J gọi là các véctơ và biến ngoài cơ sở. Đặt N = {Ak : k  J}, xB = (xj : j  J)T, xN = (xj : j  J)T, cB = (cj : j  J), cN = x  (cj : j  J). Khi đó, x, c  ℝ n tách thành x =  B  , cT = (cB, cN) (véctơ hàng). Do xN  rank (B) = m nên tồn tại ma trận nghịch đảo B1. Mỗi véctơ cột Ak (k = 1, 2, ... , n) của ma trận A được biểu diễn qua các véctơ cơ sở Aj, j  J như sau: 11 Ak =  z jk A j = z1kA j + z2kA j + ... + zmkA j với k = 1, ... , n. jJ 1 2 m (1.1) Nếu ký hiệu zk = (z1k, ... , zmk)T (véctơ cột) thì hệ thức (1.1) viết lại thành Ak = Bzk. Từ đó zk = B1Ak (k = 1, … , n). (Để ý là với j  J, zj là véctơ đơn vị). Mặt khác, hệ phương trình Ax = b có thể viết thành BxB + NxN = b. Từ đó xB = B-1(b – NxN) = B-1b  B-1NxN. (Công thức biểu diễn các biến cơ sở xj, j  J, qua các biến ngoài cơ sở xj, j  J). Tiếp đó, giá trị hàm mục tiêu bằng cTx = cBxB + cNxN = cBB-1b - cBB-1NxN + cNxN = cBB-1b - (cBB-1N - cN)xN = cBB-1b – NxN. (1.2) trong đó N = cBB-1N - cN. Do B-1N = {B-1Ak : k  J} = {zk, k  J} nên véctơ N = {k = cBzk  ck, k  J}. Số k (k  J) được gọi là ước lượng của biến ngoài cơ sở xk. Từ đó, công thức (1.2) trở thành cTx = cBB-1b -   k x k . kJ Dễ kiểm tra lại rằng nếu B-1b  0 thì x = (xB = B-1b, xN = 0) là nghiệm chấp nhận được của bài toán gốc (LP); còn nếu N  0 thì yT = cBB-1, s = (sB = 0, sN =  N)T  0 là nghiệm chấp nhận được của bài toán đối ngẫu (Q). Vì thế, ta có Định nghĩa 1.11. Cơ sở B gọi là chấp nhận được gốc nếu B-1b  0, gọi là chấp nhận được đối ngẫu nếu N  0 và là cơ sở tối ưu nếu B-1b  0 và N  0. Định lý 1.10. Nếu B là cơ sở tối ưu (tức là B-1b  0 và N  0) thì a) x = (xB = B-1b, xN = 0)T là nghiệm tối ưu của bài toán gốc, b) yT = cBB-1, s = (sB = 0, sN =  N)T là nghiệm tối ưu của bài toán đối ngẫu. Chứng minh suy từ hệ thức đối ngẫu cTx = cBxB = cBB-1b = yTb.  Phương pháp đơn hình gốc xuất phát từ một cơ sơ B chấp nhận được gốc (tức là B-1b  0) và nghiệm cơ sở của (P): xB = B-1b, xN = 0. Nếu với cơ sở đó N  0 thì B là cơ sở tối ưu: dừng thuật toán. Còn nếu N có thành phần dương, chẳng hạn s > 0 với s  J, thì có thể giảm giá trị hàm mục tiêu cTx bằng cách đưa biến xs 12 vào cơ sở và tìm đưa ra khỏi cơ sở biến xr (r  J) thích hợp. Làm như thế ta sẽ thu được một nghiệm cơ sở mới tốt hơn nghiệm cơ sở cũ (hay ít ra không kém), tương ứng với cơ sở mới B’ (thay cho cơ sở cũ B). Thuật toán lặp lại với cơ sở B’, cho tới khi đạt tới phương án tối ưu hoặc khi phát hiện bài toán có trị tối ưu vô cực. Định lý 1.11. (Dấu hiệu bài toán có trị tối ưu vô cực). Nếu với cơ sở B chấp nhận được gốc tồn tại chỉ số k  J sao cho ước lượng k > 0 và zjk  0, j  J thì bài toán gốc (P) đã cho có trị tối ưu vô cực (- ∞ đối với bài toán min).  Phương pháp đơn hình đối ngẫu xuất phát từ một cơ sơ B chấp nhận được đối ngẫu (tức là N  0) và "giả" nghiệm cơ sở của (P): xB = B-1b, xN = 0 (gọi là “giả” vì xB có thể có thành phần âm). Nếu B-1b  0 thì B là cơ sở tối ưu: dừng thuật toán. Còn nếu B-1b có thành phần âm, chẳng hạn (B-1b)r < 0 với r  J, thì có thể cải tiến (trường hợp này là tăng) trị mục tiêu cTx bằng cách đưa biến xr ra khỏi cơ sở và tìm đưa vào cơ sở một biến ngoài cơ sở xs (s  J) thích hợp và ta sẽ thu được một cơ sở mới B’ (thay cho cơ sở cũ B). Thuật toán lặp lại với cơ sở mới B’, cho tới khi đạt tới phương án tối ưu hoặc khi phát hiện bài toán gốc không có phương án. Nếu (B-1b)r < 0 với r  J và zrk  0 k  J thì đó là dấu hiệu cho biết (P) không có nghiệm chấp nhận được (D = ). Tóm lại, chương này đã nhắc lại một số kiến thức cơ bản về bài toán qui hoạch tuyến tính, bài toán qui hoạch tuyến tính đối ngẫu, các định lý đối ngẫu trong qui hoạch tuyến tính và trình bày ý tưởng cơ bản của phương pháp đơn hình gốc và đơn hình đối ngẫu giải qui hoạch tuyến tính chính tắc. 13 Chương 2 THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU Dựa trên ý tưởng của phương pháp đơn hình đối ngẫu trình bày ở Chương 1, chương này trình bày chi tiết thuật toán đơn hình đối ngẫu dạng đầy đủ và dạng cải biên và xét một số ví dụ giải bài toán qui hoạch tuyến tính chuẩn tắc. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [5]. 2.1. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU DẠNG ĐẦY ĐỦ 2.1.1. Nội dung phương pháp Dựa trên các lý thuyết đối ngẫu đã trình bày ở chương trước, có thể để ra một phương pháp để giải các bài toán qui hoạch là: thay cho việc giải bài toán gốc, người ta giải bài toán đối ngẫu, rồi từ đó suy ra lời giải của bài toán gốc. Nếu giải bài toán đối ngẫu bằng phương pháp đơn hình, và diễn tả các bước tiến hành theo ngôn ngữ bài toán gốc thì thuật toán tương ứng gọi là thuật toán đơn hình đối ngẫu. Phương pháp này do Lemke G. E. đề xuất năm 1954. Phương pháp đơn hình gốc giải qui hoạch tuyến tính bắt đầu từ một phương án (nghiệm đúng Ax = b và x  0) mà nó chưa thoả mãn tiêu chuẩn tối ưu (N  0). Sau mỗi bước lặp ta sẽ tìm được một phương án mới tốt hơn phương án cũ và quá trình lặp này tiếp tục cho đến khi nhận được phương án thoả 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 Ax = b) mà nó thoả mãn tiêu chuẩn tối ưu nhưng không thoả mãn điều kiện x  0, nghĩa là bảng đơn hình ban đầu không có phần tử dương trong dòng mục tiêu (dòng cuối), nhưng lại có phần tử âm ở cột Phương án (vì thế có tên gọi 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 đó sẽ là phương án tối ưu. Phương pháp đơn hình đối ngẫu thường được sử dụng khi ta chưa biết một phương án cực biên nào của bài toán gốc, nhưng lại có sẵn một phương án cực biên 14 của bài toán đối ngẫu. Chẳng hạn, khi bài toán cần giải có dạng chuẩn và véctơ hệ số mục tiêu c  0: min {f(x) = cTx : Ax  b, x  0} (vế phải b tuỳ ý) Bài toán đối ngẫu có dạng max{g(y) = bTy : ATy  c, y  0}. Rõ ràng y0 = 0 là một phương án cực biên của bài toán đối ngẫu, bởi vì ATy0 = 0  c. 2.1.2. Thuật toán đơn hình đối ngẫu Các bước tiến hành thuật toán đơn hình đối ngẫu như sau: Bước 1. Lập bảng đơn hình đối ngẫu ban đầu (xem các ví dụ minh hoạ 2.1, 2.2 dưới đây). Bước 2. Kiểm tra tối ưu: Nếu mọi phần tử trong cột giả phương án đều không âm thì dừng quá trình giải và ta nhận được phương án tối ưu của bài toán đã cho. Trái lại, chuyển sang Bước 3. Bước 3. Chọn dòng quay: Đó là dòng đầu tiên từ trên xuống mà nó chứa phần tử âm nhỏ nhất trong cột giả phương án. Bước 4. Chọn cột quay: Chia các phần tử trên dòng ước lượng (cuối mỗi bảng) cho các phân tử tương ứng trên dòng quay, nhưng chỉ chia cho những phần tử âm trên dòng quay. Cột quay là cột đầu tiên từ trái sang phải ứng với số nhỏ nhất trong các tỉ số đó. Bước 5. Biến đổi bảng đơn hình hoàn toàn như trong phương pháp đơn hình thường (thay đổi biến cơ sở, đổi hệ số mục tiêu tương ứng, xác lập các véctơ đơn vị, biến đổi dòng quay và cuối cùng là biến đổi các dòng khác theo qui tắc hình chữ nhật). Trở lại thực hiện Bước 2 mô tả ở trên. Chú ý. Khi tìm cột quay, nếu mọi phần tử trên dòng quay đều không âm thì đó là dấu hiệu cho thấy bài toán gốc ban đầu không có phương án. Ví dụ 2.1. Giải bài toán qui hoạch tuyến tính dạng chuẩn sau đây. 15 f(x) = 15x1 + 12x2 + 10x3  min, 3x1 + 4x2 + 2x3  160, x1 + 2x2 + 3x3  140, x1  0, x2  0, x3  0. Đưa bài toán về dạng chính tắc và đổi dấu hai vế các ràng buộc đẳng thức, ta nhận được bài toán:  min, f(x) = 15x1 + 12x2 + 10x3 3x1  4x2  2x3 + x4 x1  2x2  3x3 = 160, + x5 = 140, x1  0, x2  0, x3  0, x4  0, x5  0. Bài toán có n = 5 biến và m = 2 ràng buộc chính, nên mỗi bảng đơn hình gồm n + 3 = 8 cột và m + 1 = 3 dòng. Cũng như trong phương pháp đơn hình thường, bảng đầu tiên ghi lại các hệ số trong bài toán, chỉ khác là cột “Phương án” bây giờ được thay bằng cột “Giả phương án”, vì trong thành phần của “phương án” xuất phát có các phần tử âm. Bảng này tương ứng với giả phương án ban đầu x0 = (0, 0, 0, 160, 140), f0 = f(x0) = 0. Biến cơ sở CB Giả phương x1 x2 x3 x4 x5 án 15 12 10 0 0 x4 0 160 3 4 2 1 0 x5 0 140 1 2 3 0 1 0 15 12 10 0 0 Bảng 1 x2 12 40 3/4 1 1/2 1/4 0 x5 0 60 1/2 0 2 1/2 1 Bảng 2 480 6 0 4 3 0 x2 12 25 7/8 1 0 3/8 1/4 x3 10 30 1/4 0 1 1/4 1/2 600 7 0 0 2 2 Bảng 3 16 Trong Bảng 1, cột giả phương án có phần tử âm, nên ta chưa nhận được phương án tối ưu. Ta chọn dòng x4 (tương ứng với số âm nhỏ nhất 160) làm dòng 15 12 quay. Cột quay là cột x2 (tương ứng với số nhỏ nhất trong ba tỉ số: 3 = 5, 4 = 10 3, 2 = 5). Phần tử quay bằng 4 (trong ô được tô bóng mờ). Biến đổi bảng này theo qui tắc đơn hình ta nhận được Bảng 2. Trong Bảng 2, cột giả phương án vẫn còn phần tử âm. Ta chọn dòng x5 làm dòng quay và chọn cột x3 làm cột quay. Phần tử quay bằng 2. Biến đổi Bảng 2 ta nhận được Bảng 3. Trong bảng này, mọi phần tử trong cột giả phương án đều dương nên ta nhận được phương án tối ưu: x* = (0, 25, 30) với fmin = 600. Từ các kết quả tính toán nêu trên, ta cũng có thể tìm được lời giải của bài toán đối ngẫu nhờ vận dụng qui tắc sau đây: Qui tắc B. Nếu cơ sở ban đầu là ma trận đơn vị thì để tìm phương án tối ưu của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình đối ngẫu cuối cùng các  j của các cột biến xj mà chúng là các biến cơ sở ở bước lặp đầu tiên (Bảng 1), rồi cộng thêm với hệ số cj tương ứng. Sau đó, đổi dấu tổng tìm được nếu biến cơ sở tương ứng ban đầu nhận giá trị âm. Với ví dụ đang xét ta thấy các biến cơ sở ở bước lặp đầu tiên (Bảng 1) là x4, x5 (A4, A5 là các véctơ đơn vị). Lúc đầu các biến này nhận giá trị âm, nên phương án tối ưu của bài toán đối ngẫu y* = ( y1* , y*2 ) được xác định như sau: y1* =   4  c4 = 2  0 = 2 y*2 =  5  c5 = 2  0 = 2 Vậy, y* = (2; 2) và gmax = 1602 + 1402 = 600 = fmin. Ví dụ sau đây cho thấy bài toán gốc không có phương án. Ví dụ 2.2. Dùng phương pháp đơn hình đối ngẫu giải bài toán sau. f(x) = 2x1  4x2 + x3  x4 + 2x5 x1  2x2  min,  2x5 = 2, 4x2 + x3 + x4  x5 = 4, 17  x5 + x6 2x3 x 2 + x3 + 4x5 = 2, + x7 = 6, xj  0, j = 1, 2, 3, 4, 5, 6, 7. Sử dụng giả phương án x0 = (2, 0, 0, 4, 0, 2, 6), quá trình giải như sau: Biến cơ sở CB Giả x1 x2 x3 x4 x5 x6 x7 phương án 2 4 1 1 2 0 0 x1 2 2 1 2 0 0 2 0 0 x4 -1 4 0 4 1 1 1 0 0 x6 0 2 0 0 2 0 1 1 0 x7 0 6 0 1 1 0 4 0 1 Bảng 1 0 0 4 2 0 5 0 0 x1 2 6 1 10 2 2 0 0 0 x5 2 4 0 4 1 1 1 0 0 x6 0 6 0 4 1 1 0 1 0 x7 0 10 0 17 5 4 0 0 1 Bảng 2 20 0 24 7 5 0 0 0 Ở Bảng 2, mọi phần tử trên dòng quay x7 (dòng được tô bóng mờ) không âm, nên bài toán gốc không có phương án. Trong các ví dụ trên ta đã may mắn có được các giả phương án thoả mãn tiêu chuẩn tối ưu. Nói chung, khó có thể tìm những điểm xuất phát như thế cho phương pháp đơn hình đối ngẫu. Đối với phương pháp đơn hình ta đã biết khá kỹ về các kỹ thuật tìm một phương án cực biên ban đầu của bài toán qui hoạch tuyến tính dạng bất kỳ. Song với phương pháp đơn hình đối ngẫu ta sẽ không đi sâu tìm hiểu các thủ tục tìm giả phương án ban đầu thoả mãn tiêu chuẩn tối ưu. Sở dĩ như vậy là vì ở đây ta chủ yếu dùng phương pháp đơn hình đối ngẫu để tìm phương án khi đã có bảng đơn hình thoả mãn tiêu chuẩn tối ưu, nhưng chưa thoả mãn điều kiện x  0. Các bảng như thế có sẵn trong một số ví dụ đã xét ở trên hoặc dễ xây dựng trong ứng dụng xét ở chương sau. 18 2.2. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU DẠNG CẢI BIÊN 2.2.1. Ký hiệu và công thức tính toán  Xét bài toán qui hoạch tuyến tính chính tắc: min {f(x) = cTx : Ax = b, x ≥ 0}. (2.1) Nếu đã biết một phương án đối ngẫu chấp nhận được của bài toán (2.1) thì ta có thể giải nó theo thuật toán đơn hình đối ngẫu dạng cải biên. Thuật toán dạng này chỉ cần lưu trữ và biến đổi ma trận nghịch đảo cấp mm, thay cho ma trận điều kiện ban đầu A (cỡ mn lớn hơn nhiều), nhờ đó tiết kiệm được bộ nhớ và thời gian tính toán giải bài toán. Thuật toán càng hiệu quả đối với những bài toán qui hoạch tuyến tính có số ràng buộc m nhỏ hơn nhiều so với số biến n của bài toán và có ma trận A thưa (tỉ lệ các phần tử khác 0 trong A rất nhỏ, chỉ khoảng từ 5% đến 10%). Ta nhắc lại một số ký hiệu và công thức tính dùng trong thuật toán đơn hình. Giả sử có phương án cực biên x với cơ sở J = {i1, i2, . . , im} ( Ai1 , Ai2 , ... , Aim ) là các véctơ cơ sở và x i1 , x i2 , ... , x im là các biến cơ sở). Đặt B = ( Ai1 , Ai2 , ... , Aim ) - ma trận cơ sở. Zk = (z1k, z2k, ... , zmk)T - véctơ cột hệ số khai triển của Ak theo cơ sở B. cB = ( ci1 , ci2 , ... , cim ) - véctơ hàng gồm hệ số mục tiêu của các biến cơ sở. xB = ( x i1 , x i2 , ... , x im )T - véctơ cột ghi giá trị các biến cơ sở. Theo phương pháp đơn hình, ta đã có các công thức tính sau: xB = B-1b, f(x) = cBB-1b, Zk = B-1Ak, k = 1, 2, ... , n, k = cBZk  ck, gọi là ước lượng của biến xk, k = 1, 2, ... , n. (2.2) Phương án x là đối ngẫu chấp nhận được nếu N  0 (k  0, k = 1, . . . , n).  Khi đưa véctơ phi cơ sở As vào cơ sở B và loại khỏi B véctơ A i r với zrs ≠ 0, ta nhận được cơ sở mới: B' = ( Ai1 , ... , Air 1 , As, Air 1 , ... , Aim ), nghĩa là B' chỉ khác B bởi một véctơ: As thay cho A i r (ở vị trí thứ r trong cơ sở). Ký hiệu 19 Q = B1 = (qik)m×n, Q' = (B')1 = (q'ik)m×n. Khi đó, công thức liên hệ giữa các phần tử q'ik và qik như sau:  q ik  (q rk / z rs )z is , i  r q'ik =  i, k = 1, ... , m. q / z , i  r , rk, rs  (2.3) hay ở dạng ma trận ta có (B')1 = UrB1, trong đó 1   0  Ur =   0    0        0  z1s / z rs   1  z r 1,s / z rs  1/ z rs 0  z r 1,s / z rs   0  z ms / z rs 0  0 0 1  0        0   0  0 0    1 là một ma trận sơ cấp, nghĩa là nó chỉ khác ma trận đơn vị ở một cột duy nhất. 2.2.2. Thuật toán đơn hình đối ngẫu cải biên Xét bài toán qui hoạch tuyến tính chính tắc ở dạng (2.1). Quá trình giải bài toán theo đơn hình đối ngẫu dạng cải biên sử dụng hai bảng: Bảng 2.1 và 2.2. Trong Bảng 2.1, m + 1 dòng đầu lưu giữ các hệ số aij, bi, cij của bài toán cần giải (2.1). Từ dòng m + 2 trở đi ghi các phần tử của véctơ Pr = (zr1, ... , zrn) và các ước lượng k của biến xk ở mỗi vòng lặp tính theo công thức (2.2). Bảng 2.1. Dòng 0 b A1  As  An Dòng 1 b1 a11  a1s  a1n       Dòng m bm am1  ams  amn Dòng m + 1 c c1  cs  cn Ước lượng 1 1  s  n Dòng quay Pr zr1  zrs  zrn Tỉ số min  1 ……… s ……… n  20