Tài liệu Nghịch lý tăng khối lượng để giảm chi phí trong bài toán vận tải

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC Nguyễn Quốc Khánh NGHỊCH LÝ “ TĂNG KHỐI LƯỢNG ĐỂ GIẢM CHI PHÍ” TRONG BÀI TOÁN VẬN TẢI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên – 2013 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC Nguyễn Quốc Khánh NGHỊCH LÝ “ TĂNG KHỐI LƯỢNG ĐỂ GIẢM CHI PHÍ” TRONG BÀI TOÁN VẬN TẢI Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.16.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 - 2013 LỜI NÓI ĐẦU Bài toán vận tải của qui hoạch tuyến tính có nhiều ứng dụng trong thực tiễn. Trong bài toán này có tồn tại nghịch lý "Tăng khối lượng hàng vận chuyển để giảm chi phí vận chuyển", gọi tắt là ngịch lý "Tăng để giảm", nghĩa là khi tăng lượng cung của một trạm phát nào đó thêm một lượng hàng  > 0 và đồng thới tăng lượng cầu của một trạm thu nào đó cũng thêm một lượng hàng  đó thì chi phí vận chuyển tổng cộng lại giảm đi so với chi phí vận chuyển lúc trước khi tăng. Cần tìm hiểu lý do xảy ra và giải thích về mặt lý thuyết tại sao có nghịch lý này. Mục tíêu của luận văn này là tìm hiểu tại sao tăng lượng hàng vận chuyển lại có thể giảm được chi phí vận chuyển trong bài toán vận tải. Tìm điều kiện để nghịch lý "tăng để giảm" xảy ra và điều kiện đảm bảo nghịch lý này không thể xảy ra. Luận văn gồm lời nói đầu, ba chương, kết luận và danh mục tài liệu tham khảo. Chương 1 BÀI TOÁN QUI HOẠCH THAM SỐ Chương này nhắc lại một số kết quả về bài toán qui hoạch tuyến tính và bài toán vận tải phụ thuộc tham số ở vế phải ràng buộc. Nêu tính chất của hàm giá trị tối ưu của bài toán có vế phải phụ thuộc tuyến tính vào một tham số và nêu ví dụ về bài toán vận tải với lượng cung và cầu phụ thuộc tham số. 1.1. BÀI TOÁN QUI HOẠCH TUYẾN TÍNH THAM SÔ Bài toán qui hoạch tuyến tính với vế phải ràng buộc phụ thuộc tham số có dạng: n (Q(t)) z(t) =  c jx j → min, (1.1) j 1 n  a ijx j j 1 = bi + tdi, i = 1, 2, ... , m, x1 ≥ 0, x2 ≥ 0, ... , xn ≥ 0, (1.2) (1.3) trong đó aij, cj, bi, di là các hệ số cho trước và t là tham số. z(t) xác định theo (1.1) gọi là hàm mục tiêu, mỗi đẳng thức (1.2) gọi là một ràng buộc chính của bài toán. Giả thiêt tmin ≤ t ≤ tmax với tmin, tmax là hai số thực cho trước (có thể tmin = - ∞, tmax = + ∞). 1 Đặt A là ma trận hệ số aij (i = 1, ... , m, j = 1, ... , n), x = (x1, x2, ... , xn)T là véctơ cột các biến; c = (c1, c2, ... , cn)T, b = (b1, ... , bm)T và d = (d1, ... , dm)T. Bài toán qui hoạch tham số Q(t) có thể viết gọn lại như sau: min {cTx : Ax = b + t.d, x ≥ 0}. (1.4) Với t cố định, véctơ x(t) thỏa mãn các ràng buộc (1.2) - (1.3) gọi là một phương án của bài toán Q(t). Phương án đạt giá trị nhỏ nhất của hàm mục tiêu (1.1), gọi là một phương án tối ưu hay lời giải của bài toán. Tập các phương án của Q(t) gọi là tập ràng buộc hay miền chấp nhận được và ký hiệu là D(t). Ta giả thiêt D(tmin) ≠ ∅. Phương án của Q(t) mà đồng thời là một đỉnh của D(t) gọi là một phương án cực biên. Một cơ sở của phương án cực biên tối ưu của Q(t) ứng với một giá trị t cho trước gọi là cơ sở tối ưu. Tập hợp tất cả các giá trị t sao cho cơ sở đã cho là tối ưu gọi là khoảng tối ưu của cơ sở đó. Theo lý thuyết qui hoạch tuyến tính tham số, giá trị tối ưu z*(t) là một hàm lồi, tuyến tính từng khúc theo t và tồn tại một số hữu hạn giá trị - ∞ = t- p < ... < t- 1 < 0 ≤ t1 < ... < tq < tq+1 = + ∞ sao cho z*(t) là tuyến tính đối với mọi t ∈ [tk, tk+1] (- p ≤ k ≤ q). Đồng thời, với mỗi k ∈ {- p, q} tồn tại cơ sở Bk là cơ sở tối ưu của bài toán Q(t) với mọi t ∈ [tk, tk+1]. Ví dụ 1.1. Giải qui hoạch tuyến tính với vế phải phụ thuộc tham số t ≥ 0. 2x1 + 3x2 + 9x3 → min, x1 + 3x3 - x4 = 3 + 2t, x2 + 2x3 - x5 = 5 - t, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0. Dùng qui hoạch tham số giải bài toán trên ta nhận được kết quả như sau: Tham số t Phương án tối ưu Giá trị tối ưu z(t) 0 ≤ t ≤ 9/7 (0 937 t 332 t 0 0) 18 - t 9/7 ≤ t ≤ 5 ( 92 7 t 0 52 t 0 0) (27 + 5t)/2 5≤t (3 + 2t 0 0 0 - 5 + t) 6 + 4t 1.2. BÀI TOÁN VẬN TẢI THAM SÔ Bài toán vận tải phụ thuộc tham số có dạng: m n V(t) f(t) =  cijx ij → min, i 1 j 1 2 (1.6) n  x ij = ai + t. a i , i = 1, ... , m, (1.7) j 1 m  x ij = bj + t. bj , j = 1, ... ,n, (1.8) xij ≥ 0, với mọi i = 1, ... , m, j = 1, ... , n, (1.9) i 1 trong đó cij ≥ 0; ai > 0, a i > 0, bj > 0, bj > 0 là những hằng số thỏa mãn điều kiện: m n i 1 j 1  a i =  b j và m  a i = i 1 n  bj . (1.10) j 1 Bài toán V(t) với điều kiện (1.10) là bài toán vận tải cân bằng thu phát với vế phải ràng buộc phụ thuộc tham số, gọi tắt là bài toán vận tải tham số. Tham số t ở vế phải ràng buộc biến thiên trong đoạn [tmin, tmax], trong đó tmin, tmax là hai số thực cho trước với 0 ≤ tmin ≤ tmax. Ta đưa vào các ký hiệu: A = (aij)(m + n)×(m.n) - ma trận hệ số các biến ở vế trái các ràng buộc (1.7) - (1.8). d = (a1, ... , am, b1, ... , bn)T - véctơ vế phải ràng buộc (độc lập với tham số t). d' = ( a 1 , ... , a m , b1 , ... , bn )T - véctơ vế phải ràng buộc (hệ số của tham số t). c = (c11, c12, ... , c1n, c21, c22, ... , c2n, . . . , cm1, cm2, ... , cmn)T - véctơ hệ số mục tiêu. x = (x11, x12, ... , x1n, x21, x22, ... , x2n, . . . , xm1, xm2, ... , xmn)T - véctơ biến cần tìm. Khi đó, bài toán V(t) trở thành qui hoạch tuyến tính tham số (xem (1.4)): min {cTx : Ax = d + td', x ≥ 0}. Theo lý thuyết qui hoạch tuyến tính tham số, giá trị tối ưu f(t) của bài toán V(t) là một hàm lồi, tuyến tính từng khúc theo t và tồn tại một số hữu hạn giá trị tham số t 0 = t0 ≤ t1 < ... < tq < tq+1 = + ∞ sao cho f(t) là tuyến tính đối với mọi t ∈ [tk, tk+1] (0 ≤ k ≤ q). Đồng thời, với mỗi k ∈ {0, q} tồn tại một tập ô Gk là cơ sở tối ưu của bài toán V(t) với mọi t ∈ [tk, tk+1]. Thuật toán giải V(t) dựa trên phương pháp thế vị quen thuộc đối với bài toán vận tải dạng bảng. Cụ thể như sau. Bước 0. (Khởi sự). Xuất phát từ giá trị tham số t0 = tmin. Do có điều kiện (1.10) 0 nên Q(t0) có phương án cực biên tối ưu. Chẳng hạn, đó là x0 = ( x11 , 0 12 , ... , x 0mn )T, tương ứng với tập ô chọn G0 = {(i, j) : x ij0 là biến cơ sở}. Giả sử x0 không suy biến, nghĩa là G0 gồm đúng (m + n - 1) ô và G0 không chứa chu trình. 3 Bước 1 (Tìm khoảng tham số tối ưu của G0). Với lượng cung của các trạm phát là ai + t0 a i và lượng cầu của các trạm thu là bj + t0 bj , áp dụng qui tắc tam giác vào tập ô chọn G0, ta nhận được giá trị của biến cơ sở xij là một hàm tuyến tính của t0 (các biến phi cơ sở x ij0 = 0 ∀(i, j) ∉ G0) và x ij0 = pij + t0qij ≥ 0 với mọi i, j (pij = qij = 0 ∀(i, j) ∉ G0). Do x ij0 ≥ 0 (với mọi i, j) nên hệ bất đẳng thức tuyến tính (phụ thuộc tham số t) xij (t) = pij + tqij = x ij0 + (t - t0)qij ≥ 0 (1.11) là tương thích (có nghiệm t = t0). Nếu mọi qij ≥ 0 thì x(t) = (x11(t), x12(t), . . . , xmn(t))T là phương án tối ưu của Q(t) với mọi tham số t ≥ t0. Nếu trái lại, (có qij < 0) thì x(t) là phương án tối ưu với mọi tham số t thỏa mãn t0 ≤ t ≤ t1. Tìm t1 theo công thức t1 - t0 = min q ij  0  x ij0 q ij Rõ ràng phương án (1.11) là tối ưu với mọi t thuộc khoảng t0 ≤ t ≤ t1. Giả sử t1 ≠ + ∞. Khi tăng t (t ≥ t1) véctơ x(t) với các thành phần pij + tqij vẫn thỏa mãn điều kiện tối ưu, nghĩa là mọi ước lượng ij ≤ 0. Song véctơ này có thể sẽ không còn là phương án của bài toán đang xét, bởi vì khi tăng t tới một giá trị nào đó, một trong các thành phần xij (t) = pij + t.qij sẽ trở thành âm. Nếu xrs là thành phần đầu tiên bị đổi dấu (từ dương sang âm) thì t1 = - prs/qrs = x ij0 + (t - t0)qij trong đó qrs < 0. Biến xrs sẽ bị loại khỏi cơ sở cũ. Để tìm biến đưa vào cơ sở mới ta cần thực hiện một số thao tác phụ sau: a) Với mỗi (i, j) ∉ G0, xác định hệ số ij theo qui tắc: lập chu trình C tạo nên bởi ô (i, j) với các ô thuộc G0 (chẳng hạn bằng cách loại dần các ô treo trên hàng và cột). Lần lượt phân các ô thuộc C thành các ô lẻ C1 và ô chẵn C2 với qui ước (i, j) ∈ C1. Đặt ij = 0 nếu (r, s) ∉ C, ij = - 1 nếu (r, s) ∈ C1 và ij = 1 nếu (r, s) ∈ C2. (ij là hệ số khai triển véctơ điều kiện Aij theo các véctơ cơ sở Aij với (i, j) ∈ G0). b) Tìm biến đưa vào cơ sở theo qui tắc: 4 pq = min {- ij : (i, j) ∉ G0, ij = - 1}. Làm như vậy ta sẽ nhận được phương án tối ưu mới của bài toán Q(t1). Bước 3. Lặp lại Bước 1 với t1 thay cho t0. 1.3. VÍ DỤ MINH HỌA Ví dụ 1.2. Xét bài toán vận tải V(t) với các lượng cung và cầu phụ thuộc tham số t ≥ 0. Dữ liệu bài toán được cho trong bảng sau đây. b 40 75 90 125 ui a 30 0 0 0 b' a' 4 15 18 17 100 0 u1 x11 x12 x13 x14 5 10 13 12 110 30 u2 x21 x22 x23 x24 2 14 16 10 120 0 u3 x31 x32 x33 x34 vj v1 v2 v3 v4 f= Bảng 1.2. Dữ liệu bài toán vận tải tham số Dùng qui hoạch tham số giải bài toán vận tải trên, ta nhận được kết quả như sau: b 40 30 75 90 125 a 0 0 0 b' a' 4• 15 • 18 17 100 0 40 + 30t 60 - 30t 5 10 • 13 • 12 • 110 30 15 + 30t 90 5 2 14 16 10 • 120 0 120 vj 4 15 18 17 ui 0 -5 -7 f = 3640 - 30t Bảng 1.3. Cơ sở tối ưu với 0 ≤ t ≤ 2 b a a' 100 0 110 30 120 0 vj 40 30 b' 4• 75 0 90 0 15 18 10 • 13 • 125 0 17 100 12 • 75 90 -55+30t 2• 14 16 10 • -60+30t -30t 5 4 10 13 12 Bảng 1.4. Cơ sở tối ưu với 2 ≤ t ≤ 6 5 ui 0 0 -2 f = 3340 + 120t b a a' 40 30 b' 75 0 4• 100 0 110 30 120 0 15 90 0 18 125 0 17 100 vj 5• 10 • 13 • 12 • -180+30t 75 90 125 2• 14 16 10 120 4 9 12 11 ui 0 1 -2 f = 3160 + 150t Bảng 1.5. Cơ sở tối ưu với 6 ≤ t < + ∞ Tham số t 0≤t≤2 2≤t≤6 6 ≤ t < +∞ Phương án tối ưu xem Bảng 1.3 xem Bảng 1.4 xem Bảng 1.5 Giá trị tối ưu f(t) 3640 - 30.t 3340 + 120.t 3160 + 150.t Dáng điệu của hàm giá trị tối ưu f(t) vẽ ở Hình 1.2. f(t) 466 f(0) = 3640, f(2) = 3580, f(6) = 4060, f(10) = 4660 436 406 364 358 0 2 4 6 8 10 t Hình 1.2. Hàm giá trị tối ưu f(t) lồi, tuyến tính từng khúc, t ≥ 0 6 Chương 2 BÀI TOÁN VẬN TẢI TUYẾN TÍNH Chương này đề cập tới bài toán vận tải tuyến tính. Phần đầu chương trình bày nội dung và các tính chất cơ bản của bài toán vận tải. Tiếp đó, đề cập tới phương pháp tìm phương án cực biên ban đầu của bài toán. Sau đó, trình bày cơ sở lý luận và nội dung thuật toán thế vị giải bài toán vận tải. Cuối chương, nêu ví dụ minh hoạ cho thuật toán thế vị. 2.1. NỘI DUNG BÀI TOÁN VÀ TÍNH CHẤT Giả sử cần vận chuyển một loại hàng từ m điểm cung cấp (gọi là các trạm phát), ký hiệu i = 1, ... , m, đến n điểm tiêu thụ (gọi là các trạm thu), ky hiệu j = 1, ... , n. Cho biết khả năng cung cấp hàng của trạm phát i là ai > 0 (gọi là lượng phát), nhu cầu tiêu thụ hàng của trạm thu j là bj > 0 (gọi là lượng thu) và chi phí vận chuyển một đơn vị hàng từ trạm phát i tới trạm thu j là cij ≥ 0. Hãy xác định các biến xij ≥ 0 (i = 1, ... , m; j = 1, ... , n), biểu thị lượng hàng cần vận chuyển từ trạm phát i tới trạm thu j sao cho mọi trạm thu nhận đủ hàng và tổng chi phí vận chuyển là nhỏ nhất? Mô hình toán học của bài toán vận tải như sau. m n (P) f(x) =  cijx ij  min (cực tiểu tổng chi phí vận chuyển) (2.1) i 1 j1 n x j1 ij = ai, ∀i = 1, ... ,m (trạm phát i giao hết hàng) (2.2) ij = bj, ∀j = 1, ... ,n (trạm thu j nhận đủ hàng) (2.3) m x i 1 xij ≥ 0, ∀i = 1, 2, ... , m; j =1, 2, ... , n. (2.4) Điều kiện cần và đủ để bài toán (2.1) - (2.4) giải được ta phải có điều kiện cân bằng thu phát hay điều kiện cân bằng cung cầu, nghĩa là tổng cung bằng tổng cầu: a1 + a2 + ... + am = b1 + b2 + ... + bn. (2.5) Ký hiệu Aij là véctơ hệ số của biến xij trong (2.2) - (2.3) Véctơ này có hai thành phần bằng +1 tại hàng thứ i và hàng thứ m + j, mọi thành phần khác bằng 0. Véctơ x thỏa mãn (2.2) - (2.4) gọi là một phương án của bài toán vận tải. Một phương án đạt cực tiểu (2.1) gọi là phương án tối ưu hay lời giải. Phương án x là 7 phương án cực biên khi và chỉ khi tập véctơ cột Aij của ma trận A ứng với các xij > 0 độc lập tuyến tính hay tương đương, tập các ô (i, j) với xij > 0 không chứa chu trình. Bổ đề 2.1. Hạng của hệ ràng buộc (2.2) - (2.3) bằng m + n - 1. Hơn nữa, mỗi ràng buộc là tổ hợp tuyến tính của m + n - 1 ràng buộc còn lại, vì thế một ràng buộc bất kỳ có thể xem là thừa và có thể loại bỏ nếu cần. Mỗi phương án cực biên của bài toán vận tải có vừa đúng (m + n - 1) biến cơ sở. Tập hợp các véctơ hệ số Aij của các biến cơ sở xij gọi là một cơ sở của bài toán. Một phương án cực biên x = {xij}m×n gọi là không suy biến nếu số phần tử của tập hợp G = {(i, j) : xij > 0} bằng m + n - 1 và gọi là suy biến nếu |G| < m + n - 1. Định nghĩa 2.1. 1. Một ma trận vuông được gọi là ma trận tam giác nếu nó có hai tính chất sau: a) ma trận chứa ít nhất một hàng có đúng một phần tử khác 0; b) Nếu hàng chứa phần tử khác 0 duy nhất và cột của nó bị xóa thì ma trận nhận được sẽ vẫn có tính chất trên. 2. Ta có thể định nghĩa ma trận vuông là ma trận tam giác nếu có thể hoán vị các hàng và cột của nó để được ma trận tam giác trên hoặc ma trận tam giác dưới. Sau đây là các định lý cơ bản về bài toán vận tải dạng bảng (xem [5], tr. 211). Định lý 2.1. Mọi cơ sở của bài toán vận tải là ma trận tam giác. Định lý 2.2. Mọi biến cơ sở có giá trị nguyên nếu mọi ai và bj là các số nguyên. Định lý 2.3. Nếu mọi cước phí vận chuyển cij nguyên và nếu cho một nhân tử bất kỳ (ui hoặc vj) một giá trị nguyên tùy ý thì mọi nhân tử đơn hình ui và vj sẽ nguyên. 2.2. PHƯƠNG ÁN CỰC BIÊN BAN ĐẦU Cách đơn giản để xây dựng phương án cực biên ban đầu cho bài toán vận tải (dạng bảng) là áp dụng qui tắc (hay thuật toán) tam giác sau đây. Qui tắc tam giác (Triangularity Rule). Chọn tuỳ ý một biến xpq làm ứng viên cho biến cơ sở đầu tiên. Gán cho xpq giá trị lớn nhất có thể, miễn là không vi phạm ràng buộc về lượng cung của trạm phát p (hàng p) và lượng cầu của trạm thu q (cột q), tức là phân vào ô (p, q) một lượng hàng bằng xpq = min {ap, bq}. 8 Biến cơ sở tiếp theo được xác định bằng chính thủ tục này, sau khi thu hẹp bảng vận tải theo một trong ba trường hợp sau đây: a) Nếu ap < bq thì mọi biến còn lại ở hàng p được gán giá trị 0 và là các biến phi cơ sở. Tiếp đó, xoá hàng p và giảm lượng cầu bq của cột q còn (bq - ap). b) Nếu ap > bq thì mọi biến còn lại ở cột q được gán giá trị 0 và là các biến phi cơ sở. Tiếp đó, xoá cột q và giảm lượng cung ap của hàng p còn (ap - bq). c) Nếu ap = bq thì chọn hàng p hoặc cột q để xóa, nhưng không xóa cả hai. Tuy nhiên, nếu trong bảng chỉ còn lại duy nhất hàng p thì xoá cột q và ngược lại, nếu trong bảng chỉ còn duy nhất cột q thì xoá hàng p. Nếu hàng p bị xóa, giá trị bq của cột q giảm còn 0. Nếu cột q bị xóa, giá trị ap của hàng p giảm còn 0. Ở đây, ta hiểu "xóa" có nghĩa là hàng (hay cột) bị xoá đã phát hêt (hay nhận đủ) hàng và vì thế sẽ không cần xét tiếp hàng (hay cột) đó nữa. Bảng còn lại sau khi xóa hàng hay cột, vẫn thỏa mãn điều kiện cân bằng thu phát (2.5) (do giả thiêt bảng vận tải ban đầu đã thỏa mãn điều kiện này) và được gọi là bảng thu hep. Ở bước cuối cùng, còn lại vừa đúng một hàng và một cột thì xóa cả hàng lẫn cột, sau khi đã gán giá trị cho biến cuối cùng này bằng lượng cung của hàng (cầu của cột). Định lý 2.4. Phương án tìm được theo qui tắc tam giác là phương án cực biên của bài toán vận tải. Trường hợp riêng của quy tắc tam giác là qui tắc cước phí còn lại nhỏ nhất (The least remaining cost rule), qui tắc góc tây bắc (Northwest corner rule) và phương pháp xấp xỉ Vôghel (Vogel’s approximation method). Xét minh họa hai qui tắc đầu. Ví dụ 2.1. Tìm phương án cực biên của bài toán vận tải cho ở Bảng 2.2 theo qui tắc cước phí còn lại nhỏ nhất. Cước phí ghi ở góc trên bên trái mỗi ô. Bảng 2.2. Phương án cực biên ban đầu (Ví dụ 2.1) Thu b1 = 120 Phát 22 • a1 = 170 10 40 • a2 = 180 110 30 a3 = 200 b2 = 130 b3 = 140 b4 = 160 20 18 • 25 160 35 • 45 30 70 15 • 15 • 130 9 25 70 Cước phí nhỏ nhất trong bảng là 15, đạt tại hai ô (3.2) và (3.3). Ta chọn ô thứ nhất và phân vào ô này lượng hàng x32 = min {200, 130} = 130. Cột 2 đã nhận đủ hàng nên bị loại (không phân hàng vào đó nữa). Hàng 3 chỉ còn lại lượng phát a 3 = 200 - 130 = 70. Trong bảng thu hẹp (không kể cột 2), ta chọn ô (3.3) có cước phí nhỏ nhất (bằng 15) và phân vào ô này lượng hàng x33 = min {70, 140} = 70. Lúc này hàng 3 đã phát hết hàng nên bị loại. Cột 3 chỉ còn thiếu lượng hàng b3 = 140 - 70 = 70. Trong bảng còn lại (trừ cột 2 và hàng 3), ta chọn ô (1.4) có cước phí nhỏ nhất (bằng 18) và phân vào ô này lượng hàng x14 = min {170, 160} = 160. Cột 4 đã nhận đủ hàng nên bị loại. Hàng 1 chỉ còn lại lượng phát a 1 = 170 - 160 = 10. Tiếp đó, ta phân vào ô (1.1) lượng hàng x11 = min {10, 120} = 10. Đến đây hàng 1 cũng hết hàng, chỉ có hàng 2 là còn hàng. Cuối cùng, ta phân vào hai ô còn lại của bảng lượng hàng x21 = 120 - 10 = 110 và x23 = 180 - 110 = 140 - 70 = 70. Lúc này mọi hàng (cột) đã phát hết (nhận đủ) hàng, ta đặt xij = 0 cho mọi ô (i, j) còn lại. Kết quả ta nhận được phương án cực biên ghi ở Bảng 2.2: Ô có phân phối hàng (ô chọn) đánh dấu "•" với số lượng in đậm (góc dươi bên phải). Giá trị hàm mục tiêu tương ứng bằng 12.950. Trong mục sau ta sẽ thấy giá trị cực tiểu fmin = 12.140. Ví dụ 2.2. Tìm phương án cực biên của bài toán vận tải cho ở Bảng 2.2 theo qui tắc góc tây bắc. Bảng 2.3. Phương án cực biên ban đầu (Ví dụ 2.2) Thu b1 = 120 b2 = 130 b3 = 140 Phát 22 • 20 • 25 a1 = 170 120 50 40 45 • 35 • a2 = 180 80 100 30 15 15 • a3 = 200 40 b4 = 160 18 30 25 • 160 Theo phương pháp này ta chọn ô nằm ở góc tây bắc để phân phối trước. Trong ví dụ này, thứ tự các ô chọn như sau: (1. 1), (1. 2), (2. 2), (2. 3). (3. 3) và (3. 4). Kết quả ta nhận được phương án cực biên ghi ở Bảng 2.3. Giá trị hàm mục tiêu tương ứng bằng 15.340 (> 12950). Qui tắc này thường cho phương án cực biên có giá trị hàm 10 mục tiêu cao hơn so với qui tắc cước phí còn lại nhỏ nhất. Tuy nhiên qui tắc này lại tiện dùng để lập trình trên máy tính. 2.3. TIÊU CHUẨN TỐI ƯU Cho phương án cực biên không suy biến x0 = { x ij0 }m×n. Ký hiệu tập các ô chọn tương ứng với x0 là G(x0) = {(i, j) : x ij0 > 0}. Tính các số ui (i = 1, 2, ... , m), gọi là thế vị hàng và vj (j = 1, 2, ... , n), gọi là thế vị cột, thỏa mãn: ui + vj = cij với mọi (i, j) ∈ G(x0). Các thế vị hàng và cột xác định sai khác một hàng số khác 0 và là các số nguyên nếu mọi cij nguyên (Định lý 2.3). Do mọi cơ sở của bài toán vận tải là ma trận tam giác (Định lý 2.1) nên các thế vị ui và vj có thể tính theo qui tắc đơn giản như sau: a) Đầu tiên đặt u1 = 0; b) Khi đã có ui, nếu (i, j) ∈ G(x0) và nếu cột j chưa có thế vị thì đặt vj = cij - ui; c) Khi đã cõ vj, nếu (i, j) ∈ G(x0) và nếu hàng i chưa có thế vị thì đặt ui = cij - vj; d) Lặp lại các thao tác b) và c) cho đến khi mọi hàng và cột đều đã có thế vị. Định lý sau đây nêu điều kiện cần và đủ để x0 là phương án tối ưu. Định lý 2.5 ([3], tr. 147). Phương án x0 = { x ij0 } của bài toán vận tải (2.1) - (2.4) là tối ưu khi và chỉ khi tìm được các số ui (i = 1, ... , m) và vj (j = 1, ... , n) thỏa mãn: ui + vj ≤ cij ∀i = 1, ... , m, j = 1, ... , n, (2.7) ui + vj = cij ∀(i, j) ∈ G(x0). (2.8) Như vậy mỗi phương án cực biên không suy biến x0 tương ứng với một bộ số ui, i = 1, ... , m và vj, j = 1, ... , n (sai khác một hàng số khác 0) thỏa mãn (2.7) - (2.8). Số ij = (ui + vj) - cij được gọi là ước lượng của biến xij. Định lý 2.5 cho thấy phương án x0 là tối ưu khi và chỉ khi mọi ij ≤ 0. Nếu ij > 0 với i, j nào đó thì phương án x0 chưa tối ưu và ta co thể tìm một phương án cực biên khác tốt hơn nhờ định lý sau. Định lý 2.6 ([3], tr. 149). Giả sử x0 là phương án cực biên không suy biến của bài toán vận tải và ui, vj là các thế vị tương ứng với x0. Nếu tồn tại ô (r, s) sao cho rs = ur + vs - crs > 0 thì x0 không phải là phương án tối ưu và ta có thể xây dựng phương án cực biên x1 tốt hơn x0, theo nghĩa f(x1) < f(x0). 11 2.4. THUẬT TOÁN THẾ VỊ Bước 0 (Khởi tạo). Áp dụng qui tắc tam giác (hoặc biến thể của nó) tìm phương án cực biên không suy biến x0 = { x ij0 }. Tập ô chọn tương ứng với x0 là G(x0) = {(i, j) : x ij0 > 0} gồm (m + n - 1) phần tử và không chứa chu trình. Bước 1. Theo qui tắc đã nêu, tính các thế vị ui (i = 1, ... , m) và vj (j = 1, ... , n) tương ứng với x0 thỏa mãn hệ phương trình ui + vj = cij, với mọi (i, j) ∈ G(x0). Bước 2. Tính các ước lượng ij = ui + vj - cij với mọi (i, j) ∉ G(x0). Ta luôn có ij = ui + vj - cij = 0 với mọi (i, j) ∈ G(x0). Bước 3 (Kiểm tra điều kiện tối ưu). Nếu ij ≤ 0 với mọi i, j thì dừng thuật toán. Theo Định lý 2.5, x0 là phương án tối ưu. Nếu trái lại, chuyển sang Bước 4. Bước 4 (Điều chỉnh phương án). Gồm các thao tác: a) Xác định ô điều chỉnh (r, s) với rs = max {ij : (i, j) ∉ G(x0)}. Nếu có nhiều ô đạt max thì ưu tiên chọn ô ở hàng nhỏ hơn và cột nhỏ hơn. b) Tìm chu trình duy nhất C trong tập ô G(x0) ∪ {(r, s)}. c) Lần lượt chia các ô thuộc C thành các ô chẵn C1 và các ô lẻ C2 với (r, s) ∈ C1. d) Xây dựng phương án mới x1 = { x 1ij } với  x ij0  h neu (i, j)  C1 ,  x 1ij = x ij0  h neu (i, j)  C 2 ,  x 0 neu (i, j)  C . ij 1  trong đó h = min { x ij0 : (i, j) ∈ C2} = x 0pq . Nếu có nhiều ô (i, j) ∈ C2 với x ij0 = h thì ta chọn ngẫu nhiên một biến xpq trong số đó dể loại khỏi cơ sở. Ta có G(x1) = (G(x0) \ (p, q)) ∪ (r, s) và G(x1) không chứa chu trình, tức x1 là phương án cực biên mới. Bước 5. Đặt x0 ← x1 và G(x0) ← G(x1). Quay lại Bước 1. Nếu mọi phương án cực biên của bài toán vận tải đều không suy biến thì sau một số hữu hạn bước lặp thuật toán thế vị sẽ dừng và cho ta phương án cực biên tối ưu (lời giải) của bài toán. 12 2.5. VÍ DỤ MINH HỌA Ví dụ 2.3. Dùng thuật toán thế vị giải bài toán vận tải với m = 3 trạm phát, n = 4 trạm thu. Véctơ cung a = (170 180 200), véctơ cầu b = (120 130 140 160). Ma trận cước phí và phương án cực biên ban đầu cho ở Bảng 2.2 (xem Ví dụ 2.1). Giải. Ví dụ này thỏa mãn điều kiện cân bằng cung cầu (2.5). Phương án x0 có tập ô chọn G(x0) = {(1, 1), (1, 4), (2, 1), (2, 3), (3, 2), (3, 3)}, gồm m + n - 1 = 6 ô không chứa chu trình và giá trị hàm mục tiêu f(x0) = 12950. Vòng lặp 1. Bước 1. Các thế vị tương ứng với x0: u0 = (0 18 - 2), v0 = (22 17 17 18). Bước 2. Các số ij = ui + vj - cij ghi trong ma trận 0 dưới đây: 3 8 0   0    10 0 6 . 0 =  0   10 0 0  9   Bước 3. Phương án x0 (ghi ở Bảng 2.2) chưa tối ưu vì còn 24 = 6 > 0. Bước 4. a) 24 = max {ij > 0 : (i, j) ∉ G(x0)} = 6. Ô điều chỉnh (r, s) = (2, 4). b) Chu trình điều chỉnh gồm 4 ô: C = {(2, 4), (1, 4), (1, 1), (2, 1)}. c) Các ô lẻ C1 = {(2, 4), (1, 1) }. Các ô chẵn C2 = {(1, 4), (2, 1)}. 0 d) Lượng h = min { x14 = 160, x 021 = 110} = x 021 = 110. Ô loại (p, q) = (2, 1). e) Phương án cực biên mới 0 50  120 0   0 70 110  . x1 =  0  0 130 70 0    G(x1) = {(1, 1), (1, 4), (2, 3), (2, 4), (3, 2), (3, 3)} và f(x1) = 12290 < f(x0) = 12950. Áp dụng thuật toán thế vị, sau 3 vòng lặp ta nhận được phương án tối ưu 0  120 50 0   0 20 160  . x2 =  0  0 80 120 0    với chi phí nhỏ nhất fmin = f(x2) = 12140. 13 Chương 3 BÀI TOÁN TĂNG LƯỢNG HÀNG ĐỂ GIẢM CHI PHÍ Chương này trình bày nội dung nghịch lý "tăng lượng hàng vận chuyển để giảm chi phí vận chuyển", gọi tắt là nghịch lý "tăng để giảm" và nêu ví dụ xảy ra nghịch lý trong một bài toán cụ thể. Tiếp đó, nêu điều kiện cần và điều kiện đủ để có nghịch lý "tăng để giảm" và giải thích nghịch lý theo lý thuyết qui hoạch tham số. Cuối chương xét nghịch lý "tăng để giảm" trong bài toán qui hoạch tuyến tính dạng chính tắc. 3.1. NỘI DUNG NGHỊCH LÝ "TĂNG ĐỂ GIẢM" Trong bài toán vận tải của qui hoạch tuyến tính có tồn tại nghịch lý "tăng khối lượng hàng vận chuyển để giảm chi phí vận chuyển", gọi tắt là ngịch lý "tăng để giảm" (the more-for-less paradox). Có thể hiểu nghịch lý này như sau: khi tăng lượng cung của một số trạm phát nào đó thêm một lượng tổng cộng bằng T > 0, đồng thới tăng lượng cầu của một số trạm thu nào đó cũng thêm một lượng tổng cộng bằng T đó thì chi phí vận chuyển tổng cộng lại giảm đi so với chi phí vận chuyển lúc trước khi tăng lượng hàng vận chuyển. Chính xác hơn, có thể mô tả nghịch lý này dựa trên mô hình bài toán vận tải. Xét bài toán vận tải cân bằng thu phát: Tìm ma trận x = {xij}m×n sao cho m n (Pa,b) fa,b(x) =  cijx ij  min, i 1 j1 n x j1 ij = ai, ∀i = 1, ... ,m, ij = bj, ∀j = 1, ... ,n, m x i 1 xij ≥ 0, ∀i = 1, 2, ... , m; j =1, 2, ... , n, trong đó ai > 0 ∀i, bj > 0 ∀j, cij ≥ 0 ∀i, j và a1 + a2 + ... + am = b1 + b2 + ... + bn. Giả sử x* = ( x ij )m×n là phương án tối ưu của bài toán (Pa,b) với f* = fa,b(x*). Khi tăng lượng cung ai thành a i = ai + i và tăng lượng cầu bj thành bj = bj + j, trong đó i ≥ 0 ∀i, j ≥ 0 ∀j và T = 1 + 2 + ... + m = 1 + 2 + ... + n > 0, ta sẽ nhận được bài toán vận tải mới với tổng lượng hàng vận chuyển nhiều hơn trước. Giả sử x = ( x ij )m×n là phương án tối ưu của bài toán (Pa',b') với f = fa',b'( x ). 14 Nếu có f < f*, nghĩa là vận chuyển hàng nhiều hơn mà chi phí vận chuyển lại nhỏ hơn, thì ta nói đã xảy ra nghịch lý "tăng để giảm" trong bài toán vận tải (Pa,b). Trường hợp riêng khi tăng lượng cung của trạm phát k từ ak thành a k = ak + , đồng thời tăng lượng cầu của trạm thu ℓ từ b  thành b = b  +  với  > 0 nào đó cũng có thể xảy ra nghịch lý "tăng để giảm", nghĩa là chi phí vận chuyển sau thấp hơn trước. Trong trường hợp này ta nói rằng cặp phát - thu (k, ℓ) là một cặp nghịch lý. 3.2. VÍ DỤ XẢY RA NGHỊCH LÝ Trong mục này ta sẽ mô tả nghịch lý "tăng để giảm" qua việc xét một ví dụ đơn giản về bài toán vận tải có cặp nghịch lý. Ví dụ 3.1. Từ một bài toán vận tải đã cho, ta sẽ xây dựng một bài toán vận tải mới cùng kích thước và cùng ma trận cước phí sao cho tổng lượng hàng vận chuyển từ các trạm phát tới các trạm thu tăng lên, nhưng tổng chi phí vận chuyển lại giảm đi, tức là xảy ra nghịch lý "tăng để giảm" trong bài toán ban đầu. Bảng 3.1. Ví dụ nghịch lý "tăng để giảm" Thu Phát a1 = 100 a2 = 135 a3 = 95 vj b1 = 40 b2 = 75 b3 = 90 b4 = 125 4• 15 • 40 17 13 • 12 • 15 2 0 60 10 • 5 18 14 90 30 10 • 16 95 4 15 18 ui 17 -5 -7 fmin = 3690 Bài toán vận tải ban đầu với dữ liệu ghi ở Bảng 3.1: số trạm phát m = 3, số trạm thu n = 4, véctơ cung a = (100 135 95), véctơ cầu b = (40 75 90 125) với tổng lượng hàng vận chuyển từ các trạm phát tới các trạm thu là 100 + 135 + 95 = 40 + 75 + 90 + 125 = 330. Cước phí cij ghi ở góc trên bên trái mỗi ô. Phương án tối ưu x0 của bài toán này là ma trận  40 60 0 0    x0 =  0 15 90 30   0 0 0 95    cũng được ghi ở Bảng 3.1. Ô có chuyển hàng (ô chọn) đánh dấu " •". Các thế vị tương 15 ứng là u0 = (0 - 5 - 7) và v0 = (4 15 18 17). Giá trị hàm mục tiêu fmin = f(x0) = 3690. Nếu tăng lượng cung của trạm phát 3 từ a3 = 95 lên thành a 3 = a3 +  = 95 + 30 = 125 và tăng lượng cầu của tram thu 1 từ b1 = 40 lên thành b1 = b1 +  = 40 + 30 = 70 ( = 30), ta nhận được bài toán vận tải mới với dữ liệu ghi ở Bảng 3.2. Bảng 3.2. Bài toán điều chỉnh Thu Phát a1 = 100 a2 = 135 a3 = 125 vj b1 = 70 b2 = 75 b3 = 90 b4 = 125 4• 15 • 70 17 13 • 12 45 2 -5 90 16 • 14 10 • 0 4 0 30 10 • 5 18 15 18 ui 125 12 -2 fmin = 3600 Phương án tối ưu x1 của bài toán này là ma trận 0   70 30 0   x =  0 45 90 0   0 0 0 125    1 cũng được ghi ở Bảng 3.2. Ô có chuyển hàng (ô chọn) đánh dấu "•". Các thế vị tương ứng là u1 = (0 - 5 - 2) và v1 = (4 15 18 12). Giá trị hàm mục tiêu nhỏ nhất fmin = f(x1) = 3600 < f(x0) = 3690, giảm so với trước khi tăng lượng hàng vận chuyển. Như vậy ô (3. 1) là "ô nghịch lý" với  = 30 và bài toán ở Bảng 3.1 đã được cải tiến thành bài toán ở Bảng 3.2 có hiệu qủa kinh tế hơn (tổng chi phí vận chuyển nhỏ hơn). 3.3. ĐIỀU KIỆN TỒN TẠI NGHỊCH LÝ Định lý sau đây nêu điều kiện đủ để từ một bài toán vận tải đã cho có thể xây dựng được bài toán vận tải mới, vận chuyển nhiều hàng hơn nhưng tốn ít chi phí hơn. Định lý 3.1. Giả sử bài toán vận tải đã cho có phương án cực biên tối ưu không suy biến x* = ( x ij )m×n với tập ô chọn G(x*) = {(i, j) : x ij > 0}. Giả sử các thế vị tương ứng với G(x*) là u i (i = 1, ... , m) và v j (j = 1, ... , n). Nếu có u k + v  < 0 với (k,  ) ∉ G(x*) thì có thể xây dựng được bài toán vận tải mới bằng cách tăng ak thành a k = ak + , và tăng b  thành b = b  + , với  > 0 sao cho bài toán mới có phương án tối ưu x' với tổng chi phí vận chuyển nhỏ hơn trước, tức f(x') < f(x*). 16 Nhận xét 3.1. Giả thiết không suy biến (đảm bảo cho  xác định theo (3.1) là số dương) có thể giảm nhẹ thành giả thiêt min { x ij : (i, j) ∈ C1 \ (k,  )} > 0. (3.2) Định lý sau nêu dấu hiệu cho biết bài toán không xảy ra nghịch lý "tăng để giảm". Định lý 3.2. Giả sử bài toán vận tải cân bằng thu phát (Pa,b) có phương án cực biên tối ưu x* = { x ij }m×n với tập ô chọn tối ưu G(x*). Giả sử u i (i = 1, ... , m) và v j (j = 1, ... , n) là các thế vi tương ứng với G(x*). Nếu u i + v j ≥ 0 với mọi (i, j) ∉ G(x*) thì từ (Pa,b) không thể xây dựng bài toán vận tải khác bằng cách tăng bất kỳ lượng cung ui, lượng cầu bj thêm một lượng  > 0 nào để sao cho bài toán mới có phương án tối ưu với tổng chi phí vận chuyển nhỏ hơn. Từ Định lý 3.2 trực tiếp suy ra hệ qủa sau đây về điều kiện cần để tồn tại nghịch lý "tăng để giảm" trong bài toán vận tải. Hệ quả 3.1. Muốn cho từ một bài toán vận tải đã cho có thể xây dựng được bài toán mới sao cho vận chuyển được nhiều hàng hơn nhưng lại tốn ít chi phí hơn thì điều kiện cần là tồn tại một tập ô chọn tối ưu của bài toán và các thế vị tương ứng thỏa mãn ui + vj < 0 với một ô (i, j) nào đó không thuộc tập ô chọn tối ưu đó. Xét lại Ví dụ 3.1 ta thấy bài toán vận tải ở Bảng 3.1 có phương án cực biên tối ưu không suy biến x0 với tập ô chọn G(x0) = {(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3,4)} và các thế vị tương ứng u0 = (0 - 5 - 7), v0 = (4 15 18 17). Bài toán này có (k,  ) = (3, 1) với u 30 + v10 = - 7 + 4 = - 3 < 0. Chu trình tạo nên bởi ô (k,  ) = (3, 1) với các ô thuộc G(x0) gồm 6 ô: C = {(3, 1), (1, 1), (1, 2), (2, 2), (2, 4), 3, 4)}. Tập ô lẻ C1 = {(3, 1), (1, 2), (2, 4)} và tập ô chẵn C2 = {(1, 1), (2, 2), (3, 4)}. Theo 0 công thức (3.1) thì  = min { x12 = 60, x 024 = 30} = 30 > 0. Vì thế theo Định lý 3.1, từ bài toán ở Bảng 3.1 có thể xây dựng bài toán mới ở Bảng 3.2 với phương án tối ưu x1 có f(x1) = 3600 < f(x0) = 3690. Tiếp theo, bài toán vận tải ở Bảng 3.2 có phương án cực biên tối ưu x1 với tập ô chọn là G(x1) = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3,4)} và các thế vị tương ứng là u1 = (0 - 5 - 2), v1 = (4 15 18 12). Bài toán này có (k,  ) = (2, 1) với u 12 + v11 = - 5 + 4 = - 1 < 0. 17 Chu trình tạo nên bởi ô (k,  ) = (2, 1) với các ô thuộc G(x1) gồm 4 ô: C = {(2, 1), (1, 1), (1, 2), (2, 2)}. Tập các ô lẻ C1 = {(2, 1), (1, 2)} và tập các ô chẵn C2 = {(1, 1), (2, 2)}. Theo công thức (3.1) thì  = min { x112 = 30} = 30 > 0. Vì thế theo Định lý 3.1, từ bài toán ở Bảng 3.2 có thể xây dựng bài toán mới ở Bảng 3.3 với phương án tối ưu x2 có f(x2) = 3570 < f(x1) = 3600. Cuối cùng, bài toán vận tải ở Bảng 3.3 có phương án cực biên tối ưu x2 với tập ô chọn là G(x2) = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3,4)} và các thế vị tương ứng là u2 = (0 - 5 - 2), v2 = (4 15 18 12). Bài toán này tuy có (k,  ) = (2, 1) với u 22 + v12 = - 5 + 4 = - 1 < 0, những theo công thức (3.1) thì  = min { x112 = 0} = 0 nên không thể vận dụng Định lý 3.1 được. Tuy nhiên do phương án tối ưu x2 suy biến nên x2 có tập ô chọn khác là G'(x2) = {(1, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3,4)} và các thế vị tương ứng là u2 = (0 0 - 2), v2 = (4 10 13 12) (xem Bảng 3.4). Với các thế vị mới này ta có ui + vj > 0 với mọi (i, j) ∉ G'(x2). Vì thế, theo Định lý 3.2, từ bài toán vận tải ở Bảng 3.4 (cũng là bài toán ở Bảng 3.3) không thể xây dựng được bài toán mới, có phương án tối ưu với tổng chi phí vận chuyển nhỏ hơn. Bảng 3.4. Tập ô chọn và các thế vị tương ứng khác Thu b1 = 100 b2 = 75 Phát 4• 15 a1 = 100 100 5 10 • a2 = 165 75 2• 14 a3 = 125 0 vj 4 b3 = 90 b4 = 125 18 17 13 • 12 • 0 90 0 10 • 16 125 10 13 18 ui 12 0 -2 fmin = 3570