Tài liệu Thuật toán đơn hình cải biên và ứng dụng giải qui hoạch tuyến tính với ràng buộc suy rộng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN QUANG VUI THUẬT TOÁN ĐƠN HÌNH CẢI BIÊN VÀ ỨNG DỤNG GIẢI QUI HOẠCH TUYẾN TÍNH VỚI RÀNG BUỘC SUY RỘNG Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên -12/2015 Công trình được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên Người hướng dẫn khoa học: GS.TS. Trần Vũ Thiệu Phản biện 1: TS. Nguyễn Thị Thu Thủy Phản biện 2: PGS.TS. Hà Tiến Ngoạn Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn họp tại Trường Đại học Khoa học - Đại học Thái Nguyên vào hồi 11 giờ ngày 26 tháng 12 năm 2015 Có thể tìm hiểu luận văn tại Trung tâm học liệu Đại học Thái Nguyên và Thư viện Trường Đại học Khoa học Công trình được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên Người hướng dẫn khoa học: GS.TS. Trần Vũ Thiệu Phản biện 1: TS. Nguyễn Thị Thu Thủy Phản biện 2: PGS.TS. Hà Tiến Ngoạn Luận văn đã được bảo vệ trước Hội đồng chấm luận văn họp tại Trường Đại học Khoa học - Đại học Thái Nguyên vào hồi 11 giờ 30 ngày 26 tháng 12 năm 2015 Có thể tìm hiểu luận văn tại Trung tâm học liệu Đại học Thái Nguyên và Thư viện Trường Đại học Khoa học 1 MỞ ĐẦU Qui hoạch tuyến tính là bài toán tối ưu được ứng dụng rộng rãi trong lý thuyết và thực tiễn. Phương pháp đơn hình Dantzig (1947) rất hiệu quả để giải lớp bài toán này. Có nhiều biến thể khác nhau cho dạng bài toán hay tình huống cụ thể và có nhiều thuật toán có hiệu quả cao: đơ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, ... Luận văn này đề cập tới thuật toán đơn hình cải biên, một biến thể quan trọng của phương pháp đơn hình Dantzig. Thuật toán đặc biệt hữu ích cho các bài toán có số biến vượt trội so với số ràng buộc hoặc có ma trận ràng buộc thưa (tỉ lệ phần tử 0 khá lớn ) - chẳng hạn ma trận bài toán vận tải và được ứng dụng để giải bài toán qui hoạch tuyến tính với ràng buộc suy rộng, trong đó vectơ hệ số của mỗi biến trong bài toán không cố định trước mà được chọn tùy ý từ một tập lồi đa diện cho trước. Sau khi được học các chuyên đề về giải tích lồi, tối ưu hóa và các kiến thức có liên quan, với mong muốn tìm hiểu sâu hơn về kiến thức đã học, tôi chọn đề tài luận văn: "Thuật toán đơn hình cải biên và ứng dụng giải qui hoạch tuyến tính với ràng buộc suy rộng". Mục đích chính của đề tài là tìm hiểu nội dung các thuật toán đơn hình và đơn hình cải biên giải qui hoạch tuyến tính và trình bày cách áp dụng thuật toán đơn hình cải biên, kết hợp với kỹ thuật sinh cột của nguyên lý phân rã, vào giải bài toán qui hoạch tuyến tính với ràng buộc suy rộng. Nội dung luận văn gồm ba chương Thái Nguyên, ngày 21 tháng 11 năm 2015 Trần Quang Vui Học viên Cao học Lớp 7Y Khóa 01/2014-01/2016 Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên Email: [email protected] 2 Chương 1 KIẾN THỨC VỀ QUI HOẠCH TUYẾN TÍNH Chương này trình bày một số kiến thức cơ sở về tập lồi, tập lồi đa diện, bài toán qui hoạch tuyến tính chính tắc, bài toán đối ngẫu và phương pháp đơn hình giải. 1.1 TẬP LỒI VÀ TẬP LỒI ĐA DIỆN Định nghĩa 1.1. Tập C ⊆ R được gọi là một tập lồi nếu λa + (1 − λ)b ∈ C, ∀a, b ∈ C, ∀λ ∈ [0, 1], tức là nếu C chứa toàn bộ đoạn thẳng nối hai điểm bất kỳ thuộc nó. • Ta để ý tới các tập lồi đặc biệt sau đây: a) Tập afin là tập chứa trọn đường thẳng đi qua hai điểm bất kì thuộc nó. b) Siêu phẳng là tập có dạng H = {x ∈ Rn : aT x = α}, a ∈ Rn , a 6= 0 và α ∈ R. c) Các nửa không gian đóng H + = {x ∈ Rn : aT x > α}, H − = {x ∈ Rn : aT x 6 α}. d) Các nửa không gian mở K + = {x ∈ Rn : aT x > α}, K − = {x ∈ Rn : aT x < α}. 3 e) Hình cầu đóng B(a, r) = {x ∈ Rn : kx − ak 6 r}(a ∈ Rn , r > 0). • Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau đây: a) Giao của một họ bất kì các tập lồi là một tập lồi. C, D lồi ⇒ C lồi. T D b) Nếu C, D ⊂ Rn thì C ± D = {x ± y =: x ∈ C, y ∈ D} là các tập lồi. c) Nếu C ⊂ Rm và D ⊂ Rn thì tích C × D = {(x, y) : x ∈ C, y ∈ D} là một tập lồi trong Rm+n (Có thể mở rộng cho nhiều tập lồi). Định nghĩa 1.2. Cho E là một tập hợp bất kì trong Rn . a) Giao của tất cả các tập afin chứa E gọi là bao afin của E, kí hiệu là aff E. Đó là tập afin nhỏ nhất chứa E. b) Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, kí hiệu là conv E. Đó là tập lồi nhỏ nhất chứa E. Định nghĩa 1.3. a) Thứ nguyên (hay số chiều) của một tập afin M, kí hiệu dim M, là thứ nguyên (số chiều) của không gian con song song với nó. b) Thứ nguyên (hay số chiều) của một tập lồi C, kí hiệu dim C, là thứ nguyên (số chiều) của bao afin aff C của nó. Định nghĩa 1.4. Tập lồi K ⊆ Rn được gọi là một nón lồi nếu nó có thêm điều kiện λx ∈ K, ∀x ∈ K, ∀λ > 0. Định nghĩa 1.5. a) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λi > 0, λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp lồi của a1 , a2 , ..., ak . b) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp afin của a1 , a2 , ..., ak . c) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λi > 0 gọi là một tổ hợp tuyến tính không âm hay tổ hợp nón của a1 , a2 , ..., ak . 4 Định nghĩa 1.6. Một tập lồi mà là giao của một số hữu hạn các nửa không gian đóng gọi là một tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính: ai1 x1 + ai2 x2 + ... + ain xn 6 bi , i = 1, 2, ..., m, nghĩa là tập các x nghiệm đúng Ax 6 b với A = (aij ) ∈ Rm×n , b = (b1 , ..., bm )T . Ví dụ 1.1. a) Tập lồi đa diện vẽ ở Hình (1.1) là giao của 6 nửa không gian đóng: x1 > 0, x2 > 0, x3 > 0, x1 6 2, x2 6 2, x1 + x3 6 3. Tập này không bị chặn và có thứ nguyên (số chiều bằng 3): dimD1 = 3. b) Đa diện lồi D2 vẽ ở Hình 1.2 là tập nghiệm của hệ 4 phương trình và bất phương trình tuyến tính:  x1 + x2 + x3 = 1 x1 + x2 6 0, 8 x2 + x3 6 0, 8 x1 + x3 6 0, 8 Tập này bị chặn và có thứ nguyên (số chiều) bằng 2: dim D2 = 2.(D2 là tam giác với 3 đỉnh (6, 2, 2), (2, 6, 2), (2, 2, 6) nằm trong mặt phẳng x1 + x2 + x3 = 1). Định nghĩa 1.7. Điểm x0 ∈ D được gọi là một đỉnh của D nếu @x1 , x2 ∈ D, x1 6= x0 hoặc x2 6= x0 và @λ ∈ (0, 1) sao cho x0 = λx1 + (1 − λ)x2 , nói một cách khác: x0 không thể là điểm nằm ở trong một đoạn thẳng nào đó nối hai điểm thuộc D. 5 • Trong Hình 1.1, O, A, B, C, D là các đỉnh của tập lồi đa diện D1 . Trong Hình 1.2, ba đỉnh của tam giác (tô gạch chéo) là các đỉnh của tập lồi đa diện D2 . Để hiểu rõ hơn về tập lồi đa diện không bị chặn ta cần các khái niệm sau: Định nghĩa 1.8. Vectơ d ∈ Rn , d 6= 0 được gọi là một hướng lùi xa của D nếu ∃x0 ∈ Dsao cho {x0 + λd : λ > 0} ⊆ D. Tập hợp các hướng lùi xa của D cộng với gốc O tạo thành một nón lồi đóng, gọi là nón lùi xa của D, kí hiệu rec D. Định nghĩa 1.9. Hướng lùi xa d của D được gọi là một hướng cực biên nếu không tồn tại hai hướng lùi xa khác d1 , d2 sao cho d = λ1 d1 +λ2 d2 , λ1 , λ2 > 0. Có thể chứng minh được rằng tập lồi đa diện D không bị chặn khi và chỉ khi recD 6= {0}, nghĩa là khi và chỉ khi D có ít nhất 1 hướng lùi xa. Ta có định lý biểu diễn sau đây, thường hay được dùng trong các chứng minh: Định lí 1.1. Mỗi điểm của tập lồi đa diện D = {x ∈ Rn : Ax = b, x > 0} có thể biểu diễn dưới dạng một tổ hợp lồi của những tập hữu hạn các đỉnh của D cộng với một tổ hợp tuyến tính không âm của một tập hữu hạn các phương cực biên của D. Trong các bài toán quy hoạch tuyến tính, ta gặp tập lồi đa diện có dạng: D = {x ∈ Rn : Ax = b, x > 0}, A ∈ Rm×n , b ∈ Rm . (1.1) tức D là tập nghiệm không âm của một hệ phương trình tuyến tính. Giả thiết m 6 n (nếu m > n, tập D có thể rỗng) và rank A = m. Ở dạng này, tập D không chứa đường thẳng nào (do x > 0) nên D có đỉnh. Kí hiệu Aj (j = 1, ..., n) là vectơ cột thứ j của ma trận A. Theo lý thuyết qui hoạch tuyến tính, vectơ x̄ ∈ D là một đỉnh của D khi và chỉ khi hệ vectơ {Aj : x¯j > 0} là độc lập tuyến tính. Do Aj ∈ Rm nên từ tính chất này suy ra số thành phần dương trong đỉnh của D xác định bởi (1.1) không vượt quá m. Một ứng dụng cụ thể của các kết quả trên đây là tìm các đỉnh của tập lồi đa diện D xác định theo (1.1) khi số biến n không quá lớn. Sau đây là một ví dụ: Ví dụ 1.2. Tìm các đỉnh không suy biến của tập lồi đa diện cho bởi hệ: ( 3x1 − 2x2 + 3x3 = 6 −x1 + 2x2 − x3 = 4 xj > 0, j = 1, 2, 3 6 Ví dụ này có m = 2 phương trình và n = 3 biến. Một đỉnh có nhiều nhất m = 2 thành phần dương, tức là có ít nhất n - m = 1 thành phần bằng 0. Vì thế, lần lượt cho x1 , x2 , x3 bằng 0, ta được: • Với x1 = 0, hệ phương trình trên cho ta x2 = 92 , x3 = 5. • Với x2 = 0, hệ phương trình vô nghiệm (x1 + x3 = −4, x1 > 0, x3 > 0!). • Với x3 = 0, hệ phương trình trên cho ta x2 = 29 , x1 = 5. Như vậy ta nhận được hai nghiệm của hệ: (0, 29 , 5) và (5, 92 , 0). Kiểm tra trực tiếp cho thấy hệ hai vectơ A2 = (−2, 2)T , A3 = (3, −1)T và A1 = (3, −1)T , A2 = (−2, 2)T là độc lập tuyến tính, nên cả hai nghiệm trên đều là các đỉnh không suy biến của tập lồi đa diện đã cho (số thành phần dương m = 2). 1.2 BÀI TOÁN QUI HOẠCH TUYẾN TÍNH CHÍNH TẮC 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 tuyến tính. Khi đề cập tới phương pháp giải, người ta thường xét bài toán qui hoạch tuyến tính ở dạng chính tắc như sau:  Pn fP(x) = j=1 cj xj → min n (1.2) a x = bi , i = 1, 2, ..., m  j=1 ij j xj > 0, j = 1, 2, ..., n. trong đó aij , bi , cj là các hằng số cho trước. Trong bài toán (1.2), f(x) gọi là hàm mục tiêu, mỗi phương trình ai1 x1 + ai2 x2 + ... + ain xn = bi , (i = 1, 2, ..., m) gọi là một ràng buộc đẳng thức, mỗi bất đẳng thức xj > 0 gọi là một ràng buộc về dấu (hay ràng buộc không âm). Điểm (hay vectơ) x ∈ Rn thỏa mãn mọi ràng buộc, gọi là một điểm chấp nhận được, hay một phương án của bài toán. Tập hợp tất cả các phương án của bài toán gọi là tập ràng buộc hay miền chấp nhận được của bài toán và được kí hiệu là D, tức là đặt: 7 D = {x ∈ Rn : Ax = b, x > 0}. Như đã nhắc lại ở Mục 1.2, D là một tập lồi đa diện có đỉnh (nếu tập D 6= ∅). Phương án đạt giá trị nhỏ nhất của hàm mục tiêu, hay gọi là một phương án tối ưu hay một lời giải của bài toán. Một phương án mà đồng thời là một đỉnh của D được gọi là một phương án cực biên của bài toán. Kí hiệu A = (aij ) ∈ Rm×n , b = (b1 , ..., bm )T , c = (c1 , ..., cn )T và x = (x1 , ..., xn )T . Khi đó bài toán (1.2) có thể viết gọn lại thành: min{f (x) = cT x : Ax = b, x > 0}. Định lý sau nêu điều kiện cần và đủ để một qui hoạch tuyến tính có lời giải: Định lí 1.2. Nếu một qui hoạch tuyến tính có ít nhất một phương án và nếu hàm mục tiêu bị chặn dưới trong miền chấp nhận được (đối với bài toán min) thì bài toán chắc chắn có phương án tối ưu (lời giải). Định lý sau nêu lên một tính chất đặc trưng của phương án cực biên (đỉnh) của bài toán qui hoạch tuyến tính chính tắc: Định lí 1.3. Để một phương án x0 = (x01 , x02 , ..., x0n ) của bài toán qui hoạch tuyến tính chính tắc là phương án cực biên thì điều kiện cần và đủ là các vectơ cột Aj của ma trận A tương ứng với các thành phần x0j > 0 là độc lập tuyến tính. Định lí 1.4. Nếu bài toán qui hoạch tuyến tính chính tắc có phương án tối ưu thì cũng có phương án cực biên tối ưu (có đỉnh tối ưu). 1.3 BÀI TOÁN ĐỐI NGẪU Ta định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính chính tắc, kí hiệu bài toán (P): f (x) = c1 x1 + c2 x2 + ... + cn xn → min ai1 x1 + ai2 x2 + ... + ain xn = bi , i = 1, 2, ..., m xj > 0, j = 1, 2, ..., n là bài toán ký hiệu (Q): g(y) = b1 y1 + b2 y2 + ... + bm ym → max a1j y1 + a2j y2 + ... + amj ym 6 cj , j = 1, 2, ..., n. 8 Dùng kí hiệu vectơ và ma trận ta có thể viết gọn lại như sau: Bài toán gốc: f (x) = cT x → min, Ax = b, x > 0. Bài toán đối ngẫu: g(y) = bT y → max, AT y 6 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: min{x1 − 2x2 + 3x3 : x1 + x2 + x3 = 4, x1 − 2x2 = 1, x1 > 0, x2 > 0, x3 > 0}. là bài toán qui hoạch tuyến tính max{4y1 + y2 : y1 + y2 6 1, y1 − 2y2 6 −2, y1 6 3}. Định lí 1.5. (Đối ngẫu yếu) Nếu x là một phương án bất kỳ của bài toán gốc (P) và y là một phương án bất kỳ của bài toán đối ngẫu (Q) thì: f (x) = c1 x1 + c2 x2 + ... + cn xn > g(y) = b1 y1 + b2 y2 + ... + bm ym . Định lí 1.6. (Đối ngẫu mạnh) Nếu một qui hoạch có phương án tối ưu thì qui hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau. Định lí 1.7. (Độ lệch bù yếu) Một cặp phương án x, y của hai qui hoạch đối ngẫu (P) và (Q) là các phương án tối ưu khi và chỉ khi chúng nghiệm đúng hệ thức: xT (c − AT y) = 0 hay xj (cj − m X aij yi ) = 0 với mọi j = 1, ..., n. i=1 Ví dụ 1.4. Áp dụng Định lý (1.7) 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 + x3 = 4, x1 − 2x2 = 1, x1 > 0, x2 > 0, x3 > 0(chấp nhận được gốc) y1 + y2 6 1, y1 − 2y2 6 −2, y1 6 3(chấp nhận được đối ngẫu) x1 (1 − y1 − y2 ) = 0, x2 (−2 − y1 + 2y2 ) = 0, x3 (3 − y1 ) = 0(độ lệch bù yếu). Kiểm tra trực tiếp cho thấy rằng x∗ = (3, 1, 0) và y ∗ = (0, 1) thỏa mãn hệ điều kiện trên. Vì thế, x∗ là phương án tối ưu của bàn 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 ∗ ) = 1. 9 1.4 PHƯƠNG PHÁP ĐƠN HÌNH Xét qui hoạch tuyến tính chính tắc: (P) min{f (x) = cT x : Ax = b, x > 0}, A ∈ Rm×n , b ∈ Rm , c ∈ Rn , x ∈ Rn . Bài toán đối ngẫu của (P) có dạng: (Q) max{g(y) = bT y : AT y 6 c} = max{bT y : AT y + s = c, s > 0}. Định nghĩa 1.10. Ma trận con B cấp m×m của A gọi là cơ sở nếu rankB = m. Với cơ sở B = {Aj1 , Aj2 , ..., Ajm } của A, ta cũng gọi J = {j1 , j2 , ..., jm } là cơ sở của A. Đặt N = {Ak : k ∈ / J}, xB = (xj : j ∈ J)T , xN = (xj : T j ∈ / J) , cB = (cj : j ∈ J), cN = (cj : j ∈ / J). Khi đó, x, c ∈ Rn T T tách thành x = (xB , xN ), c = (cB , cN ) (vectơ hàng). Do rank B = m nên tồn tại B −1 . Mỗi cột Ak của A được biểu diễn: Ak = Bzk với zk = B −1 Ak , (k = 1, ..., n). Hệ Ax = b ⇔ BxB + N xN = b ⇒ xB = B −1 b − B −1 N xN và f (x) = cT x = cB xB + cN xN = cB B − 1b − ∆N xN với ∆N = {Dk = cB zk − ck , k ∈ / J}. Số ∆k gọi là ước lượng của biến xk (k ∈ / J). Định nghĩa 1.11. Cơ sở B gọi là chấp nhận được gốc nếu B −1 b > 0, gọi là chấp nhận được đối ngẫu nếu ∆N 6 0 và gọi là cơ sở tối ưu nếu B −1 b > 0 và ∆N 6 0. Định lí 1.8. Nếu B là cơ sở tối ưu (tức là B −1 b > 0 và ∆N 6 0) thì: a) x = (xB = B −1 b, xN = 0)T là nghiệm tối ưu của bài toán gốc. b) y T = cB B −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 cT x = cB xB = cB B −1 b = y T b. • Thuật toán đơn hình gốc xuất phát từ một cơ sở B chấp nhận được gốc và nghiệm cơ sở của (P): xB = B −1 b, xN = 0. Thay đổi cơ sở B cho đến khi ∆N 6 0. 10 Định lí 1.9. (Dấu hiệu bài toán có giá 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 6 0, ∀j ∈ J thì bài toán gốc (P) đã cho có giá trị tối ưu vô cực (−∞ đối với bài toán min). Lưu ý: Trong quá trình giải bài toán qui hoạch tuyến tính theo thuật toán đơn hình gốc, ở mỗi vòng lặp ta cần lưu giữ và biến đổi các thông tin: • xB = B −1 b: giá trị các biến cơ sở và CB B −1 b: giá trị hàm mục tiêu tương ứng. • B −1 N : ma trận hệ số khai triển của các vectơ ngoài cơ sở theo cơ sở B. • ∆N = cB B −1 N − cN : vectơ ước lượng của các biến ngoài cơ sở. Thông tin này được ghi lại trong một bảng chữ nhật cấp (m + 1) × (n − m + 1), gọi là bảng đơn hình: B −1 b B −1 N cB B −1 b ∆N = cB B −1 N − cN 11 Chương 2 PHƯƠNG PHÁP ĐƠN HÌNH CẢI BIÊN Chương này trình bày phương pháp đơn hình cải biên giải qui hoạch tuyến tính chính tắc: ý nghĩa của sự cải biên, cách tính truy hồi ma trận nghịch đảo, sơ đồ tính toán và ví dụ số minh họa thuật toán. 2.1 Ý NGHĨA CỦA SỰ CẢI BIÊN Xét bài toán qui hoạch tuyến tính dạng chính tắc: min{f (x) = cT x : Ax = b, x > 0} (2.1) Giả sử ta có phương án cực biên x với cơ sở J = {i1 , i2 , ..., im }, (Ai1 , Ai2 , ..., Aim ) là các vectơ cơ sở và xi1 , xi2 , ..., xim là các biến cơ sở). Đặt: B = (Ai1 , Ai2 , ..., Aim ) - ma trận cơ sở (m hàng, m cột). Zk = (z1k , z2k , ..., zmk )T - vectơ cột hệ số khai triển của Ak theo cơ sở B. cB = (ci1 , ci2 , ..., cim )T - vectơ hàng gồm hệ số mục tiêu của các biến cơ sở. xB = (xi1 , xi2 , ..., xim )T - vectơ cột ghi giá trị các biến cơ sở. Theo phương pháp đơn hình ta đã có công thức tính sau: xB = B −1 b, f (x) = (cB )T B −1 b, Zk = B −1 Ak , k = 1, 2, ..., n. ∆k = cB Zk − ck , gọi là các ước lượng của biến xk , k = 1, 2, ..., n. (2.2) 12 Phương pháp đơn hình giải qui hoạch tuyến tính (2.1) cần tính toán trên ma trận cỡ m × n. Phương pháp đơn hình cải biên sử dụng các công thức (2.2) nên ở mỗi vòng lặp chỉ cần lưu giữ và biến đổi ma trận cơ sở nghịch đảo B −1 cỡ m × m, không cần lưu giữ và biến đổi ma trân điều kiện ban đầu (cỡ m × n lớn hơn rất nhiều), nhờ đó tiết kiệm được bộ nhớ và thời gian tính toán giải bài toán. Phương pháp đơn hình cải biên đặc biệt thích hợp và có hiệu quả đối với các bài toán thực tế có kích thước lớn, 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à A là ma trận thưa (tỉ lệ các phần tử khác 0 trong A rất nhỏ, chỉ khoảng từ 5% đến 10%). 2.2 CÔNG THỨC TRUY HỒI TÍNH MA TRẬN NGHỊCH ĐẢO B −1 Khi đưa vectơ phi cơ sở As và cơ sở B và loại khỏi B vectơ Air với zrs 6= 0, ta nhận được cơ sở mới: B 0 = (Ai1 , ..., Air −1 , As , Air +1 , ..., Aim ), nghĩa là B’ chỉ khác B bởi một vectơ As thay cho Air (ở vị trí thứ r trong cơ sở). Kí hiệu: 0 Q = B −1 = (qik )m×n , Q0 = (B 0 )−1 = (qik )m×n . 0 Khi đó công thức liên hệ giữa các phần tử qik và qik như sau:  qik − ( qrk )zis , i 6= r 0 qik = qrk , i =zrs i, k = 1, ..., m. r (2.3) zrs hay ở dạng ma trận ta có (B 0 )−1 = Ur B −1 , trong đó:  1  .. .  0  . Ur =  ..  0  .  .. 0 ... .. . ... ... ... .. . ... 0 .. . 1 .. . 0 .. . 0 − z1,s rs .. . z − r−1,s zrs z 0 .. . 0 ... .. . ... 1 zrs zr+1,s − zrs 0 1 .. . 0 ... ... .. . ... − .. . z m,s zrs  0 ..  .  0   0  0  ..  . 1 (2.4) 13 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 (cột thứ r). 2.3 THUẬT TOÁN ĐƠN HÌNH CẢI BIÊN Dantzig và Orchard - Hays (1954) đã đề ra một thuật toán đơn hình cải biên để giảm bớt khối lượng tính toán và thông tin lưu trữ ở mỗi bước lặp đơn hình. 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 đơn hình cải biên sử dụng hai bảng: Bảng 2.1 và Bảng 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 ước lượng ∆k của biến xk ở mỗi vòng lặp tính theo công thức (2.2). 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 Dòng m+2 ∆1 ∆1 . . . ∆s . . . ∆n Dòng m+3 ∆2 ∆1 . . . ∆s . . . ∆n Bảng 2.1: Bảng 2.2 gọi là bảng đơn hình cải biên. Cột đầu tiên ghi tên các biến cơ sở. Cột cB ghi hệ số mục tiêu của các biến cơ sở. Trong cột thứ ba (Phương án): m phần tử đầu là giá trị các biến cơ sở, phần tử cuối là giá trị hàm mục tiêu tương ứng. Ma trận cơ sở nghịch đảo B −1 được ghi ở m cột tiếp theo. Cột Zs (cột quay): m phần tử đầu ghi các hệ số khai triển của vectơ đưa vào cơ sở As theo các vectơ cơ sở, phần tử cuối ghi ước lượng ∆s . Dòng phía dưới ma 14 trận nghịch đảo ghi phương án của bài toán đối ngẫu, nó được tính theo công thức: (qm+1,1 , qm+1,2 , ..., qm+1,m ) = cB B −1 (2.5) Biến cB Phương cơ sở án Ma trận B −1 Zs xi1 .. . ci .. . q10 .. . q11 . . . . . . q1m .. . . . . . . .. . . z1s .. . xir .. . cir .. . qr0 .. . qr1 . . . . . . qrm .. . . . . . . .. . . zrs .. . xim cim qm0 qm1 . . . . . . qmm zms qm+1,0 qm+1,1 . . . . . . qm+1,m θ ∆s Bảng 2.2: Bảng đơn hình cải biên Thuật toán đơn hình cải biên gồm các bước sau: Bước 0 (Xây dựng bảng đơn hình ban đầu). Giả sử lúc đầu có phương án cực biên x với cơ sở J. Đặt B = {Aj : j ∈ / J}. Tính ma trận nghịch đảo và ghi nó vào Bảng 2.2. Tính m phần tử đầu của cột Phương án theo (2.2) và tính qm+1,0 = (cB )T B −1 b. Các phần tử qm+1,k (k = 1, ..., m) là tích của vectơ cB với vectơ cột thứ k của B −1 theo công thức (2.5). Bước 1 (Kiểm tra tối ưu và tìm cột quay) Tính ước lượng của biến xk theo công thức (2.2): ∆k là tích của dòng m+1 của Bảng 2.2 với cột Ak ở Bảng 2.1, rồi trừ ck . Nếu ∆k 6 0∀k = 1, ..., n thì phương án cực biên hiện có là tối ưu. Trái lại, ta xác định vectơ As đưa vào cơ sở theo công thức (hoặc chọn ngẫu nhiên nếu có nhiều chỉ số đạt max): ∆s = max{∆k : ∆k > 0, k ∈ / J}. Bước 2: (Kiểm tra bài toán không có lời giải hữu hạn và tìm dòng quay). Trước hết tính cột quay (cột Zs ở Bảng 2.2) theo công thức Zs = B −1 As , tức 15 là nhân từng dòng của ma trận nghịch đảo B −1 với cột As ở Bảng 2.1 ta sẽ được từng phần tử của cột quay Zs của Bảng 2.2. Phần tử cuối của cột này là ∆s (đã tính ở trên). Nếu zis 6 0∀i = 1, ..., m thì hàm mục tiêu của bài toán (2.1) không bị chặn dưới: dừng tính toán. Trái lại, xác định vectơ loại khỏi cơ sở theo công thức: θ0 = qr0 zrs = min{ zqi0 : zis > 0} is Cột θ trong Bảng 2.2 dùng để ghi các tỉ số zqi0 đối với zis > 0. is Bước 3:(Biến đổi bảng đơn hình cải biên) Biến cơ sở ở dòng r là xir bị loại khỏi cơ sở, thay vào đó là biến xs . Trong cột cB thay hệ số mục tiêu ở dòng r là cir bởi cs . Biến đổi ma trận (qik )(m+1)×(m+1) (i = 1, 2, ..., m + 1; k = 0, 1, ..., m) theo công thức tương tự (2.3) với cột quay Zs , dòng quay r và phần từ quay zrs > 0. Cụ thể: a) Chia mỗi phần tử ở dòng r cho zrs . Dòng nhận được gọi là dòng chính. b) Lấy mỗi dòng khác trừ tích của dòng chính với phần tử của dòng đó trên cột quay, tức là trừ (dòng chính) ×zis . Quay trở lại thực hiện Bước 1. 2.4 VÍ DỤ MINH HỌA Ví dụ 2.1. Giải bài toán sau theo thuật toán đơn hình cải biên:  f (x) = 26x1 + 35x2 + 34x3 + 37x4 + 25x5 + 31x6 → min 28x1 + 34x2 + 28x3 + 30x4 + 30x5 + 34x6 = 32 x 1 + x 2 + x 3 + x 4 + x 5 + x 6 = 1 x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0, x6 > 0. Số liệu ban đầu của bài toán và các ước lượng ∆k ở mỗi vòng lặp ghi ở Bảng 2.3: Các bước giải bài toán được nêu trong ba bảng đơn hình cải biên Bảng 2.4, Bảng 2.5 và Bảng 2.6: Bảng 2.4: Cơ sở ban đầu gồm hai vectơ 1 và A2 với:  A h i 17 − 16 28 34 −1 3 B = (A1 , A2 ) = 1 1 ⇒B = 1 − 14 6 3 Phương án cực biên ban đầu và biến đối ngẫu tương ứng là: 16 b A1 A2 32 28 34 1 1 1 c 26 35 ∆1 ∆2 ∆3 0 -1 -4 0 0 -4 A3 28 1 34 A4 30 1 37 -8 -8 -14 -12 -12 -12 A5 A6 30 34 1 1 25 31 4 0 0 4 4 0 Bảng 2.3: Biến cơ sở Cơ bản Phương án x1 26 x2 35 1 3 2 3 32 B −1 − 16 1 6 Z5 θ 2 3 1 3 1 2 17 3 − 14 3 1,5 -16 4 Bảng 2.4:  x  − 1 1 = 6 x2 1 6 17 3 − 14 3 2 h i 1 1 2 3 × 32 1 = 2 với f1 = 3 × 26 + 3 × 35 = 32.  3 1 17 −6 3 (y1 , y2 ) = (26, 35) 1 = ( 32 , −16). − 14 6 3  Tính các ước lượng ∆1 = AT y − c = (0 0 −8 − 8 4 4). Đưa vectơ A5 vào cơ sở. Loại vectơ A1 khỏi cơ sở. Bảng 2.4 được biến đổi theo Bước 3 của thuật toán nêu trên, với phần tử quay z15 = 32 (số in đậm). Kết quả ta nhận được Bảng 2.5 Tính các ước lượng ∆2 = AT y−c = (−1 0 −14 −12 0 4). Đưa vectơ A6 vào cơ sở. Loại vectơ A2 khỏi cơ sở. Biến đổi Bảng 2.5 ta thu được Bảng 2.6. Tính các ước lượng ∆3 = AT y−c = (−4 −4 −12 −12 0 0). 17 Biến cơ sở Cơ bản Phương án x5 25 x2 35 1 2 1 2 B −1 − 14 17 2 − 15 2 1 4 30 2,5 Z6 θ 0 − 1 1 2 -50 4 Bảng 2.5: Biến cơ sở Cơ bản Phương án x5 25 x6 31 B −1 1 2 1 2 − 14 28 1, 5 1 4 17 2 15 2 − − − 20 Bảng 2.6: Mọi biến có ước lượng nhỏ hơn hay bằng 0 nên dừng tính toán: Phương án tối ưu của bài toán là x∗ = (0 0 0 0 0, 5 0, 5)T và giá trị tối ưu của hàm mục tiêu fmin = f (x∗ ) = 28. Ví dụ 2.2. Giải bài toán sau bằng phương pháp đơn hình cải biên:  f = 2x + x2 + x3 + x4 → max  4x1 + x12 + 2x 3 + x4 = 8 2x1 + x2 + 2x3 − x4 = 6  2x1 − x2 + 2x3 + x4 = 2 x1 > 0, x2 > 0, x3 > 0, x4 > 0 Ta chuyển sang bài toán tìm min của -f, rồi thêm vào ba biến giả x5 , x6 , x7 > 0 và xét bài toán (M) với M=10: Áp dụng thuật toán, ta được lời giải tối ưu x∗ = (0; 3; 2; 1) với giá trị tối ưu của hàm mục tiêu fmax = 6.