Toán kinh tế - Chương 3: Bài toán vận tải

71 trang vanle 19980

Download

Bạn đang xem 20 trang mẫu của tài liệu "Toán kinh tế - Chương 3: Bài toán vận tải", để 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:

toan_kinh_te_chuong_3_bai_toan_van_tai.pdf

Nội dung text: Toán kinh tế - Chương 3: Bài toán vận tải

Chƣơng 3 BÀI TOÁN VẬN TẢI 1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI 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 1.1.1. Nội dung kinh tế của bài toán Giả sử cần vận chuyển một loại hàng hóa từ m trạm phát, ký hiệu là A i (i = 1, m ). Lƣợng hàng cần chuyển đi ở mỗi trạm A i tƣơng ứng là ai (đơn vị hàng), tới n trạm cần thu hàng, ký hiệu B j (j = 1, n ), lƣợng hàng cần thu về ở mỗi trạm B j tƣơng ứng bj (đơn vị hàng). Giả sử cƣớc phí vận chuyển từ trạm phát hàng A i tới trạm thu B j là cij (đơn vị tùy theo qui ƣớc). m n Giả thiết ai > 0, bj > 0, cij 0 (i 1,m, j 1,n) và ai b j Q (bài toán i 1 j 1 cân bằng thu phát). Hãy lập kế hoạch vận chuyển hàng hoá sao cho tổng chi phí vận chuyển nhỏ nhất đồng thời thoả mãn nhu cầu thu phát hàng (các trạm phát, phát hết hàng và các trạm thu, thu đủ hàng). 1.1.2. Mô hình toán học của bài toán Xác định kế hoạch vận chuyển hàng nghĩa là xác định lƣợng hàng cần chuyển đi từ các trạm phát tới các trạm thu tƣơng ứng. Gọi xij là lƣợng hàng hoá vận chuyển từ trạm phát A i tới trạm thu B j (xij 0, i = 1,m , j = ). n Mọi trạm phát, phát hết hàng nên ta có: xij ai , i 1,m. j 1 m Mọi trạm thu, thu đủ hàng nên ta có: xij b j, j 1,n. i 1 m n Nhƣ vậy tổng chi phí vận chuyển là: cij xij , và đòi hỏi phải cực tiểu. i 1 j 1 Khi đó mô hình toán học của bài toán sẽ là: - 56 -
mn f (X) cij x ij min (3.1) i 1 j 1 n xij ai ,(i 1,m) (3.2) j 1 m xij b j,(j 1,n) (3.3) i 1 xij 0 (i = 1,m , j = 1, n ). (3.4) Trong đó ma trận X = (xij)m.n đƣợc gọi là ma trận phân phối hàng cần phải tìm. Hàm f(X) đƣợc gọi là hàm mục tiêu và là tổng chi phí vận chuyển. Hiển nhiên (3.1) (3.2) (3.3) (3.4) là mô hình toán học của một bài toán qui hoạch tuyến tính dạng chính tắc. Chú ý: Bài toán vận tải (3.1) (3.2) (3.3) (3.4) đƣợc viết dƣới dạng tƣờng minh nhƣ sau: c11x11 + c12x 12 + + c1nx 1n + c 21x 21 + c22x22 + + c2nx2n + + cm1x m1 + cm2xm2 + +c mnx mn min. x11 + x 12 + + x 1n = a1 x 21 + x22 + + x2n = a2 x m1 + xm2 + +x mn = am x11 + x21 + + xm1 = b1 x12 + x22 + + xm2 = b2 + x1n + x2n + . + xmn = bn Theo đó, ma trận ràng buộc A của bài toán (3.1) (3.2) (3.3) (3.4) là: - 57 -
11 1 00 0 00 0 00 0 11 1 00 0 m 00 0 00 0 11 1 A 10 0 10 0 10 0 01 0 01 0 01 0 n 00 1 00 1 00 1 n n n Nhận thấy ma trận A đƣợc chia làm 2m khối: m khối của m dòng đầu thì ở mỗi khối là một ma trận cấp m.n có một dòng có các phần tử là 1, còn các dòng khác các phần tử đều là 0; khối thứ k có dòng thứ k là 1 với k = 1, m . Còn m khối của n dòng sau thì mỗi khối là một ma trận đơn vị cấp n. Gọi Aij là cột hệ số của ẩn xij , ta có Aij là véc tơ cột thứ j trong nhóm cột thứ i của ma trận A, khi đó ta luôn có Aij = Ei + E m + j, i = 1,m, j 1,n , trong đó Ek là ma trận cấp (m.n, 1) có phần tử ở hàng thứ k là 1, các phần tử khác là 0. Định nghĩa 3.1. Mọi bài toán qui hoạch tuyến tính có dạng toán học (3.1) (3.2) m n (3.3) (3.4) với giả thiết ai > 0, bj > 0, cij 0 (i 1,m, j 1,n); ai b j Q đƣợc i 1 j 1 gọi là bài toán vận tải cân bằng thu phát. Ngoài bài toán vận tải cân bằng thu phát hay bài toán dạng đóng ta có hai bài toán vận tải không cân bằng thu phát hay bài toán dạng mở nhƣ sau: mn +) abij: i 1 j 1 mn f (X) cij x ij min i 1 j 1 n xij a i ,(i 1,m) j1 - 58 -
m xij b j,(j 1,n) i 1 xij 0 (i = 1,m , j = 1, n ). mn +) abij: i 1 j 1 mn f (X) cij x ij min i 1 j 1 n xij ai ,(i 1,m) j 1 m xij b j ,(j 1,n) i1 xij 0 (i = , j = ). Định nghĩa 3.2. Ma trận X = (xij)m.n thoả mãn hệ các điều kiện (3.2) (3.3) (3.4) của bài toán vận tải cân bằng thu phát đƣợc gọi là một phương án của bài toán hay một phương án phân phối hàng. K hiệu tập hợp các phƣơng án của bài toán là D. Định nghĩa 3.3. Phƣơng án X thoả mãn yêu cầu (3.1) của hàm mục tiêu f(X) đƣợc gọi là một phương án tối ưu. Đặt: X là ma trận cột gồm m.n thành phần: c = (x11 x12 x1n x21 x22 x2n xm1 xm 2 xm n) , C là ma trận dòng gồm m.n thành phần: C = (c11 c12 c1n c21 c22 c2n cm1 cm 2 cm n), B là ma trận cột gồm m + n thành phần: B = (a1 a2 am b1 b2 bn) A = (aij)(m + n)(m.n) ma trận hệ số các ẩn của (3.2) (3.3). Khi đó dạng (3.1) (3.2) (3.3) (3.4) có dạng ma trận sau: f(X) CX min AX B X 0 - 59 -
1.2. Mô hình bảng của bài toán vận tải 1.2.1. Bảng vận tải Ngoài cách mô tả bài toán dƣới dạng tổng quát, do đặc thù của lớp bài toán vận tải, ta có thể mô tả bài toán dƣới dạng bảng để thuận lợi cho việc tìm lời giải của bài toán. Bảng 3.1 T B1: b1 B2: b2 Bn: bn P c11 c12 c1n A1: a1 c21 c22 c2n A2: a2 cm1 cm2 cmn Am: am Bảng 3.1 trên đƣợc gọi là bảng vận tải. Không tính dòng đầu (ghi lƣợng hàng của các trạm thu), cột đầu (ghi lƣợng hàng của các trạm phát) thì bảng có m dòng, n cột và m.n ô. Mỗi cột tƣơng ứng cho một trạm phát, mỗi dòng tƣơng ứng cho một trạm thu. Ô nằm trên dòng i, cột j k hiệu là ô (i, j). Góc trên bên trái ô (i, j) ta ghi giá cƣớc cij, góc dƣới bên phải ghi giá trị xij là lƣợng hàng vận chuyển từ trạm Ai đến trạm Bj, chú rằng ta chỉ ghi giá trị của xij vào ô (i, j) nếu xij > 0 và gọi ô đó là một ô chọn; nếu xij = 0 thì ta bỏ trống vị trí đó (trừ trƣờng hợp đặc biệt) và gọi ô đó là ô loại. K hiệu C(X) = {(i, j): xij > 0}. 1.2.2. Vòng và các tính chất Định nghĩa 4. Một tập hợp gồm k ô (k 4) trên bảng vận tải đƣợc đánh số thứ tự 1, 2, , k (xem ô đầu tiên là ô tiếp theo của ô cuối cùng) đƣợc gọi là một vòng nếu - 60 -
chúng thỏa mãn điều kiện: hai ô liên tiếp phải cùng nằm trên một dòng hay một cột và không có ba ô liên tiếp cùng nằm trên một dòng hay một cột. Vòng thƣờng đƣợc k hiệu là V và đƣợc biểu diễn: V = {(i1, j1), (i1, j2), ( i2, j2), , ( ip, jp)( ip, j1)} hoặc V = {(i1, j1), (i2, j1), ( i2, j2), , ( ip, jp)( i 1, jp)}, với ik ik + 1, j k j k + 1, k = 1, 2, , p. Ví dụ 1: Ta có một vòng nhƣ Bảng 3.2 sau: V = {(1,2), (3, 2), (3, 3), (5, 3), (5, 5), (1, 5)} Bảng 3.2 (1) (6) (2) (3) (4) (5) Nhận xét: Từ định nghĩa ta nhận thấy số ô của mỗi hàng hoặc mỗi cột mà vòng đi qua là hai ô, do đó tổng số các ô có mặt trên vòng luôn là một số chẵn và ít nhất phải có bốn ô. Định nghĩa 3.5. Một tập hợp các ô mà từ đó có thể lấy ra đƣợc một số ô để tạo thành vòng thì tập hợp các ô đó đƣợc gọi là có chứa vòng. Định l 3.1. Cho K là một tập hợp các ô trên bảng vận tải (Aij): (i, j) K (3.5) Tập hợp K có chứa vòng khi và chỉ khi họ (3.5) là một họ véc tơ phụ thuộc tuyến tính. Chứng minh: Cần: Giả sử K chứa vòng V có dạng: V = (i1, j1), (i1, j2), ( i2, j2), , ( ip, jp)( ip, j 1). Vì Aij = Ei + Em + j nên rõ ràng ta có: - 61 -
A A A A A 0, i1 j1 i1 j2 i 2 j2 i p jp i p j1 đẳng thức này chứng tỏ họ (3.5) là họ véc tơ phụ thuộc tuyến tính. Đủ: Giả sử họ (3.5) phụ thuộc tuyến tính, khi đó ta có: ij Aij 0, (3.6) (i, j) K với ít nhất một hệ số ij 0. Từ (3.6) ta có: ij(E i E m j ) 0 (3.7) (i,j) K Giả sử 0. Khi đó số hạng A (E E ) có hai thành phần i1 j1 i1 j1 i1 j1 i1 j1 i1 m j1 thứ i1 và m + j 1 là 0. Để làm triệt tiêu thành phần thứ i1 của số hạng này thì i1 j1 vế trái của (3.6) phải chứa ít nhất một số hạng có thành phần thứ i1 khác không. Giả sử đó là số hạng thứ i1j2: A 0. Lại xuất hiện thành phần thứ m + j2 i1 j2 i1 j2 khác 0. Để làm triệt tiêu thành phần này thì vế trái của (3.6) phải chứa ít nhất một số hạng có thành phần thứ m + j2 khác 0. Giả sử đó là số hạng : A 0. Lại i 2 j2 i 2 j2 xuất hiện thành phần thứ i2 0 v.v Vì vế trái của (3.6) là một tổng hữu hạn nên cuối cùng để làm triệt tiêu thành phần thứ m + i1 (xuất hiện lúc đầu) thì vế trái của (3.6) phải chứa ít nhất một số hạng có thành phần thứ m + i1 khác 0. Giả sử đó là số hạng A 0. Đồng thời với việc chọn các số hạng khác không thì ta đã i p j1 i p j1 chọn ra đƣợc tập hợp các ô tƣơng ứng là: (i1, j 1); (i1, j 2); (i2, j 2); ; (ip, j p); (ip, j 1) tập hợp các ô này chính là một vòng và nó là một tập con của (3.5). Vậy (3.5) chứa vòng. 1.3. Tính chất của bài toán vận tải cân bằng thu phát Định l 3.2. Bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4) luôn có phương án tối ưu. Chứng minh: Áp dụng định lý 1.8, ta cần chỉ ra rằng bài toán có phƣơng án và hàm mục tiêu f(X) bị chặn dƣới trên tập các phƣơng án. Thật vậy: - 62 -
m n Giả sử X = (xij) D, do cij 0, xij 0 i, j nên f (x) cij xij 0. Nhƣ i 1 j 1 vậy với mọi X D, hàm f(x) bị chặn dƣới trên D. m n 0 aib j 0 Đặt xij ,i 1,m; j 1,n ( ai b j Q). Đặt X0 = (x ij)m.n. Khi đó ta có: Q i 1 j 1 n m 0 0 0 xij a i ,i 1,m; xij b j , j 1,n; x ij 0, i = 1,m , j = 1, n . j1 i1 Vậy X0 là một phƣơng án của bài toán. Ta có điều phải chứng minh. Định l 3. Trong bài toán vận tải với dạng ma trận hạng của ma trận ràng buộc A là rankA = m + n - 1. Chứng minh: Ta có tổng của m dòng đầu của ma trận A bằng tổng của n dòng sau của ma trận A và bằng (1, 1, , 1). Suy ra m + n dòng của A phụ thuộc tuyến tính, do vậy rankA m + n -1. Ta sẽ chứng minh rằng m + n -1 dòng của A kể từ dòng thứ hai là độc lập tuyến tính. Thật vậy: Gọi Di là dòng thứ i của ma trận A, xét đẳng thức sau: m n iDi 0. (3.8) i 2 Vế trái của (3.8) là một véc tơ gồm m.n thành phần, ta xét n cột đầu. Khi đó m n từ (3.8) ta có idij 0, j 1,n ; mà dij = 1 nếu i = m + j; dij = 0 nếu i m + j. i m 1 Do vậy i 0, i m j, j 1,n . Hay m + j = 0, j = . Khi đó ta có m (3.8)ii D 0. i2 ( 2, 2, , 2, 3, 3, , 3, , m, m, , m) = 0. k = 0, k 2,m . k = 0, k 2,m n . Vậy m + n – 1 dòng sau của A độc lập tuyến tính, hay rankA = m + n – 1. - 63 -
Từ kết quả này, ta thấy rằng khi giải bài toán vận tải bằng phƣơng pháp đơn hình thì có thể bỏ đi một dòng bất kỳ của hệ ràng buộc. Định l 3.4. Giả sử X = (xij) m.n là một phương án của bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4). Khi đó điều kiện cần và đủ để X là một phương án cực biên là C(X) không chứa vòng. Chứng minh: Theo định lý 1.6 phƣơng án X của bài toán chính tắc là phƣơng án cực biên khi và chỉ khi {Aij : xij > 0}độc lập tuyến tính, mà {Aij : xij > 0} = {Aij : (i, j) C(X)}, theo định lý 2.1 họ này độc lập tuyến tính khi và chỉ khi C(X) không chứa vòng. Từ các định lý trên ta có các hệ quả sau: Hệ quả 3.1. Mọi tập hợp gồm nhiều hơn m + n – 1 ô trên bảng vận tải m.n đều có chứa vòng. Hệ quả 3.2. Điều kiện cần để phương án X là phương án cực biên là số thành phần dương thực sự của nó không vượt quá m + n – 1. Định nghĩa 3.6. Phƣơng án cực biên X của bài toán vận tải (3.1) (3.2) (3.3) (3.4) đƣợc gọi là phương án không suy biến nếu nó có đủ m + n – 1 thành phần dƣơng thực sự, nếu không thì phƣơng án cơ bản đó gọi là suy biến. Định nghĩa 3.7. Giả sử X là một phƣơng án cực biên và J là một tập hợp gồm m + n – 1 ô không chứa vòng đồng thời J chứa các ô ứng với các thành phần dƣơng thực sự của X. Khi đó J đƣợc gọi là hệ ô chọn cơ sở của phƣơng án cực biên X. Từ định nghĩa ta có, nếu phƣơng án cực biên X không suy biến thì C(X) J là hệ ô cơ sở duy nhất của X. Nếu X suy biến thì C(X) J và X có thể có nhiều hệ cơ sở khác nhau. 2. THUẬT TOÁN THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT 2.1. Phƣơng pháp tìm phƣơng án cực biên xuất phát 2.1.1. Phương pháp cước phí bé nhất - 64 -
Phƣơng pháp này luôn ƣu tiên phân phối cho ô có cƣớc phí nhỏ nhất trên bảng. Nội dung phƣơng pháp nhƣ sau: Trên bảng vận tải, ta tìm ô có cƣớc phí nhỏ nhất, phân vào ô đó một lƣợng hàng lớn nhất có thể đƣợc. Khi đó sẽ có ít nhất một dòng hay một cột thỏa mãn nhu cầu (nghĩa là trạm phát đã tiêu thụ hết hàng hoặc trạm thu đã nhận đủ số hàng so với nhu cầu), xóa bỏ dòng hay cột đó đi và lặp lại công việc này đối với các ô còn lại, sau một số hữu hạn bƣớc lặp ta thu đƣợc ma trận X = (xij)m.n. Tập hợp các giá trị {x ij}, i = 1,m , j = 1, n thu đƣợc từ cách tìm nhƣ trên là một phƣơng án của bài toán, vì chúng thoả mãn mọi ràng buộc. Hơn nữa nó còn là một phƣơng án cực biên. Thật vậy, theo cách phân phối, các ô chọn đều có xij > 0. Giả sử tập các ô chọn có một số ô tạo thành vòng có dạng: V = {(i1, j1), (i1, j2), ( i2, j2), , ( ip, jp)( ip, j1)}. Khi đó có các trƣờng hợp sau xảy ra: - Hoặc yêu cầu của trạm phát A thoả mãn, hàng i1 bị loại khỏi bảng, ô i1 (i1, j2) không thể đƣợc phân phối. - Hoặc yêu cầu của trạm thu B thoả mãn, hàng j1 bị loại khỏi bảng, ô (ik, j1) j1 không thể đƣợc phân phối. - Hoặc yêu cầu của cả trạm phát và trạm thu B thoả mãn, khi đó hàng j1 i1 và cột j1 bị loại khỏi bảng, ô (i1, j2) và ô (ik, j1) không thể đƣợc phân phối. Vậy X là phƣơng án cực biên của bài toán vận tải cân bằng thu phát. Ví dụ 3.1: Tìm phƣơng án cực biên của bài toán vận tải sau (Bảng 3.1) bằng phƣơng pháp cƣớc phí nhỏ nhất. - 65 -
Bảng 3.3 T 30 20 25 35 40 P 30 13 7 6 2 12 20 5 1 10 5 11 40 10 5 3 7 14 60 6 3 2 11 10 Giải: Trên bảng vận tải 3.3, ta thấy ô (2, 2) có cƣớc phí nhỏ nhất c22 = 5. Phân vào ô đó lƣợng hàng lớn nhất có thể đƣợc là x22 = 20. Khi đó trạm phát A2 hết hàng và trạm thu B2 nhận đủ hàng, trạm phát A1 còn 80 đơn vị hàng. Xóa bỏ hàng 2, cột 2, lặp lại công việc trên sau một số hữu hạn bƣớc, ta thu đƣợc phƣơng án cực biên của bài toán nhƣ bảng (3.4). Bảng 3.4 T P 30 20 25 35 40 13 7 6 2 12 30 30 5 1 10 5 11 20 20 10 5 3 7 14 40 5 35 6 3 2 11 10 60 30 25 5 0 0 0 30 0 0 20 0 0 0 Nhƣ vậy, phƣơng án cực biên thu đƣợc là: X . 0 0 0 0 5 35 30 0 25 0 5 - 66 -
Phƣơng án X0 có 7 ô chọn, thiếu một ô so với hạng của bài toán cân bằng thu phát. Ta lấy thêm một ô loại bổ sung thêm vào tập hợp 7 ô chọn để đủ 8 ô không chứa vòng. Chẳng hạn ô (1, 2), ta đƣợc tập ô cơ sở J0 = {(1, 2), (1, 4), (2,2), (3, 4), (3, 5), (4, 1), (4, 3), (4, 5)}. 2.1.2. Phương pháp Fogels Nội dung phƣơng pháp: Trên bảng vận tải, ta tính chênh lệch cƣớc phí giữa hai ô có cƣớc phí nhỏ nhất của mỗi dòng và mỗi cột. Xét dòng hay cột có chênh lệch lớn nhất và phân vào ô có cƣớc phí nhỏ nhất của dòng hay cột đó một lƣợng hàng lớn nhất có thể đƣợc, bỏ đi các ô nằm trên các trạm đã đƣợc thỏa mãn. Sau đó tính lại chênh lệch cƣớc phí của các cột hay dòng còn lại, lặp lại công việc trên sau một số hữu hạn lần, ta thu đƣợc ma trận X = (xij)m.n là một phƣơng án cực biên của bài toán vận tải cân bằng thu phát. Ví dụ 3.2: Tìm phƣơng án cực biên theo phƣơng pháp Fogels của bài toán vận tải ở ví dụ 3.1. Giải: Bằng phƣơng pháp Fogels ta tìm đƣợc phƣơng án cực biên nhƣ bảng 3.5. Bảng 3.5 T P 30 20 25 35 40 13 7 6 2 12 30 4,4x 30 5 1 10 5 11 20 4x 20 10 5 3 7 14 40 2,4,3,7 5 35 6 3 2 11 10 60 1,4,4,1 30 25 5 1,4,4x 2x 1,1,1x 3,5,4,7x 1,2,4,4 Phƣơng án cực biên tìm đƣợc theo phƣơng pháp Fogels: - 67 -
0 0 0 30 0 0 20 0 0 0 X 0 0 0 25 5 10 30 0 0 0 30 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 2.2.1. Bài toán đối ngẫu của bài toán vận tải Xét bài toán vận tải : mn f (X) cij x ij min (3.1) i 1 j 1 n xij ai ,(i 1,m) (3.2) j 1 m xij b j,(j 1,n) (3.3) i 1 xij 0 (i = 1,m , j = 1, n ). (3.4) K hiệu ui là các biến đối ngẫu ứng với hệ ràng buộc (3.2), vj là các biến đối ngẫu ứng với hệ ràng buộc (3.3). Khi đó bài toán đối ngẫu của bài toán vận tải có dạng: m n aiui b jv j max (3.9) i 1 j 1 ui + vj cij (i 1,m, j 1,n). (3.10) Các cặp điều kiện đối ngẫu: xij 0 ui + vj cij (i 1,m, j 1,n) (3.11) 2.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 Định lý 3.5. Giả sử X = (xij)m.n là phương án của bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4). Khi đó điều kiện cần và đủ để phương án X là phương án tối ưu là tồn tại một hệ thống gồm m + n thế vị (u1, u2, , um, v1, v2, , vn) = (U, V) sao cho: - 68 -
ui + vj cij (i 1,m,j 1,n), (3.12) ui + vj = cij nếu xij > 0. (3.13) Chứng minh. Cần: Giả sử X = (xij)m.n là phƣơng án tối ƣu của bài toán vận tải cân bằng thu phát (3.1) (3.2) (3.3) (3.4). Theo định lý đối ngẫu thứ nhất, bài toán đối ngẫu (3.9) (3.10) cũng có phƣơng án tối ƣu. Giả sử phƣơng án tối ƣu đó là (U, V) = (ui, vj), i 1,m, j 1,n . Khi đó điều kiện (3.12) đƣợc thỏa mãn. Mặt khác theo định l đối ngẫu thứ hai giữa (U, V) và X thì điều kiện (3.13) đƣợc thỏa mãn. Vậy phƣơng án tối ƣu của bài toán đối ngẫu (U, V) chính là hệ thống thế vị phải tìm. Đủ: Giả sử tìm đƣợc hệ thống thế vị (U, V) = {(ui, vj): } thỏa mãn (3.12) (3.13). Vì thỏa mãn (3.12) nên (U, V) là phƣơng án của bài toán đối ngẫu. Vì thỏa mãn (3.13) nên cặp phƣơng án X, (U, V) thỏa mãn giả thiết của định l đối ngẫu thứ hai. Vậy X là phƣơng án tối ƣu của bài toán vận tải và hệ thống thế vị (U, V) là phƣơng án tối ƣu của bài toán đối ngẫu. 2.2.3. Phương pháp xây hệ thống toán thế vị 0 Giả sử X0 (x ij ) m.n là một phƣơng án cực biên và J0 là một hệ thống ô chọn cơ sở của X0. Ta sẽ xây dựng hệ thống thế vị (U, V) = (ui, vj), . Lấy (3.13) làm điều kiện xuất phát để tìm hệ thống thế vị sau đó sẽ kiểm tra điều kiện (3.12). Xét hệ phƣơng trình tuyến tính: ui + vj = cij (i, j) J0. (3.14) Vì J0 gồm m + n – 1 ô không chứa vòng nên hệ (3.14) gồm m + n – 1 phƣơng trình độc lập tuyến tính, xác định m + n ẩn. Do vậy hệ (3.14) có vô số nghiệm phụ thuộc một tham số. Lấy bất kỳ một ẩn làm tham số, và cho tham số nhận một giá trị cụ thể, chẳng hạn là số 0, ta đƣợc một nghiệm riêng của hệ phƣơng trình. Đó chính là hệ thống thế vị đối với tập ô cơ sở J0. Định lý 2. Giả sử (U, V) và (U’, V’) là hai nghiệm riêng của hệ (3.14) khi đó ta có: ui + vj = ui’ + vj’ , i 1,m, j 1,n . - 69 -
Từ kết quả của định l ta nhận thấy việc phƣơng án X0 có tối ƣu hay không nghĩa là hệ thống thế vị (U, V) tìm đƣợc có thỏa mãn điều kiện (3.12) hay không, nó hoàn toàn không phụ thuộc vào việc ta chọn ẩn tự do và cho nó giá trị là bao nhiêu khi đi tìm nghiệm riêng của hệ phƣơng trình (3.14). Tóm lại, để tìm hệ thống thế vị ứng với một phương án cực biên X0 cho trước và kiểm tra X0 đã tối ưu chưa ta thực hiện các bước sau: - Xác định hệ ô chọn cơ sở của X0. Nếu X0 không suy biến thì J0 = C(X0). Nếu X0 suy biến thì ta cần bổ sung thêm một số ô loại (làm ô chọn giả) để cùng với tập C(X0) tạo thành m + n – 1 ô không chứa vòng. Lƣợng hàng tại các ô chọn giả là 0. - Tìm một hệ thống thế vị, hay là tìm một nghiệm riêng của hệ (3.14). Đặt ij = ui + vj – cij, ij đƣợc gọi là số kiểm tra hay ƣớc lƣợng của ô (i, j). Rõ ràng ij = 0 (i, j) J và - nếu ij 0 (i, j) thì X0 là phƣơng án tối ƣu, - nếu tồn tại ij > 0 thì X0 chƣa phải là phƣơng án tối ƣu. 2.3. Phƣơng pháp cải tiến phƣơng án Bổ đề 3.1. Xét phƣơng án cực biên X0 với hệ ô chọn cơ sở J0. Giả sử (i0, j0) là một ô bất kỳ không thuộc J0, khi đó tập hợp {J0 + (i0, j0)} sẽ chứa một vòng duy nhất. Chứng minh: Do {J + (i0, j0)} gồm m + n ô nên nó chứa một vòng V nào đó và hiển nhiên V đi qua (i0, j0), Giả sử vòng V có dạng: V = {(i0, j0), (i0, j1), (i1, j1), , (ik, jk), (ik, j0)}. Giả sử tồn tại vòng V’ V, dĩ nhiên V’ cũng đi qua (i0, j0) và giả sử V’ có dạng: V’ = {(i0, j0), (i0, q1), (p1, q1), , (pk, qk), (pk, j0)}. Từ V và V’ ta lập vòng mới: V’’ = {(i0, j1), (i1, j1), , (ik, jk), (ik, j0), (pk, jo), (pk, qk), , (i0, q1)}. Vòng này không đi qua (i0, j0), trái với giả thiết J0 không chứa vòng. Vậy ta có điều phải chứng minh. - 70 -
Bổ đề 3.2. Gọi V là vòng duy nhất tạo bởi (i0, j0) và một số ô của J0. Đánh số thứ tự 1, 2, 3, các ô trên V bắt đầu từ (i0, j0). K hiệu: Vc = {(i, j) V có số thứ tự chẵn}, Vl = {(i, j) V có số thứ tự lẻ}. Ta có công thức c c . ij ij i 0 j0 (i, j) Vc (i, j) Vl Chứng minh: Giả sử V = {(i0, j0), (i0, j1), (i1, j1), , (ik, jk), (ik, j0)}. Khi đó: c c c c c c c ij ij i 0 j0 i 0 j1 i1 j1 i k jk i k j0 (i, j) Vc (i, j) Vl c u v u v u v u v i 0 j0 i 0 i1 i1 j1 i k jk i k j0 c u v . i 0 j0 i 0 j0 i 0 j0 Ta có điều phải chứng minh. Dựa vào hai kết quả trên ta đưa ra thuật toán cải tiến phương án như sau: Giả sử phƣơng án cực biên X0 với hệ ô chọn cơ sở J0 chƣa thỏa mãn tiêu chuẩn tối ƣu, nghĩa là còn tồn tại số kiểm tra ij > 0. - Chọn ô điều chỉnh (thƣờng chọn ô có số kiểm tra dƣơng lớn nhất). Giả sử max{ 0}, khi đó ô (i0, j0) là ô điều chỉnh. i 0 j0 ij - Lập vòng điều chỉnh V tạo bởi (i0, j0) và một số ô chọn khác của J0. Sau đó đánh số thứ tự và chia V thành Vc , Vl. - Xác định phƣơng án mới X1 theo công thức: 0 xij (ij) V 1 0 xij xij q (ij) Vc (3.15) 0 xij q (ij) Vl với q là lƣợng điều chỉnh đƣợc xác định theo công thức: q min x0 : (ij) V x0 . (3.16) ij c i r jr Định l 3.7. Giả sử X0 là phương án cực biên không suy biến, ma trận X1 được xác định theo công thức (3.15) (3.16) là một phương án cực biên với hệ ô chọn cơ sở J0 = J {i0, j0}\{ir, jr}, và tốt hơn hẳn X0. - 71 -
Chứng minh: Vì số ô của vòng V nằm trên một dòng hay một cột bằng 0 hoặc là một số chẵn nên từ công thức (3.15) ta có: n n m m 1 0 1 0 xij xij ai , i 1,m , xij xij b j, j 1,m. j 1 j 1 i 1 i 1 0 Vì X0 là phƣơng án cực biên không suy biến nên x ij > 0 với mọi (i, j) J0. 1 Do vậy q > 0, mặt khác theo (3.15) và (3.16) thì x ij 0, (i, j). Nhƣ vậy chứng tỏ X1 là phƣơng án của bài toán. Tập hợp J1 vẫn đảm bảo m + n - 1 ô chọn và không chứa vòng. Vậy phƣơng án X1 thu đƣợc là phƣơng án cực biên với cơ sở J1, đồng thời f(X0) – f(X1) = q > 0, chứng tỏ phƣơng án X1 tốt hơn phƣơng án X0. i 0 j0 Thuật toán thế vị giải bài toán vận tải cân bằng thu phát (bài toán không suy biến)gồm các bước sau: Bƣớc 1: Tìm phƣơng án cực biên xuất phát X0 và hệ ô chọn cơ sở J0. Bƣớc 2: Xây dựng hệ thống thế vị, kiểm tra tiêu chuẩn tối ƣu. + Nếu thỏa mãn tiêu chuẩn tối ƣu, kết luận bài toán; + Nếu chƣa thỏa mãn tiêu chuẩn tối ƣu, chuyển sang bƣớc 3. Bƣớc 3: Cải tiến phƣơng án: - Chọn ô điều chỉnh, lập vòng điều chỉnh, xác định lƣợng điều chỉnh q. - Xác định phƣơng án cực biên mới X1: Giữ nguyên lƣợng hàng tại các ô không nằm trên vòng điều chỉnh V. Trên vòng điều chỉnh V ta thêm lƣợng hàng q ở các ô lẻ, bớt đi lƣợng hàng q ở các ô chẵn đồng thời xác định hệ ô chọn cơ sở mới J1. Gán X1: = X0, quay về bƣớc 2. Chú rằng, do số phƣơng án cực biên là hữu hạn nên thuật toán thế vị cũng sẽ kết thúc sau một số hữu hạn bƣớc. Ví dụ 3.3: Tìm phƣơng án tối ƣu của bài toán vận tải cân bằng thu phát cho ở bảng 3.6. - 72 -
Bảng 3.6 T 30 25 40 25 P 20 4 2 10 6 45 1 3 8 12 55 5 3 9 7 Giải: - Bằng phƣơng pháp cƣớc phí bé nhất, ta tìm đƣợc phƣơng án cực biên xuất phát X0 nhƣ bảng 3.7. Bảng 3.7 T 30 25 40 25 P 4 2 10 6 20 20 1 3 8 12 45 30 5 10 5 3 9 7 55 30 25 0 20 0 0 X0 30 5 10 0 0 0 30 25 Phƣơng án cực biên X0 có cơ sở J0 là tập các ô chọn. - 73 -
Bảng 3.8 4 2 10 6 u1 = 0 - 20 - - 1 3 8 12 u2 = 1 30 5 10 - 5 3 9 7 u3 = 2 - (1) 30 25 v1 = 0 V2 = 2 v3 = 7 v4 = 5 - Xây dựng hệ thống thế vị: từ công thức ui + vj = cij (i, j) J0, cho u1 = 0, ta đƣợc hệ thống thế vị nhƣ ở bảng 3.8. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij đối với các ô loại, thấy ô (3.2) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: lấy ô (3.2) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 2), (2, 2), (2, 3), (3, 3)}. q = min{5, 30} = 5. Điều chỉnh 5 đơn vị hàng từ ô thuộc Vc sang ô thuộc Vl, ta đƣợc phƣơng án cực biên X1 nhƣ bảng 3.9: khi đó ô (2, 2) hết hàng trở thành ô loại, ô (3, 2) có hàng trở thành ô chọn. Ta có cơ sở mới J1 là tập các ô chọn nhƣ bảng 3.9. Bảng 3.9 4 2 10 6 u1 = - 1 - 20 - (0) 1 3 8 12 u2 = - 1 30 - 15 - 5 3 9 7 u3 = 0 - 5 25 25 v1 = 2 v2 = 3 V3 = 9 v4 = 7 - 74 -
- Xây dựng hệ thống thế vị: từ công thức ui + vj = cij (i, j) J1, cho u3 = 0, ta đƣợc hệ thống thế vị nhƣ ở bảng 3.9. Tính ij, ta thấy ij 0, (i, j). Vậy phƣơng án cực biên X1 là phƣơng án tối ƣu của bài toán. 0 20 0 0 X1 30 0 15 0 , 0 5 25 25 tổng cƣớc phí vận chuyển nhỏ nhất là: f(x) = 2.20 + 1.30 + 8.15 + 3.5 + 9.25 + 7.25 = 605. Chú : Nếu gặp trƣờng hợp phƣơng án cực biên suy biến thì q có thể bằng 0. Khi q = 0, ta vẫn tiến hành thuật toán bình thƣờng. Thực chất của quá trình này là thay đổi một ô cơ sở thành một ô không thuộc cơ sở, còn ô điều chỉnh sẽ trở thành ô cơ sở. Kết quả của quá trình là chuyển từ tập ô cơ sở này sang tập ô cơ sở khác mà không làm thay đổi phƣơng án cực biên. Nếu q = min xij đạt tại nhiều ô khác nhau, đó là dấu hiệu của phƣong án (i, j) Vc cực biên suy biến. Ta loại một ô bất kỳ một cách ngẫu nhiên trong các ô đó, các ô khác giữ nguyên trong tập cơ sở mới (chúng có vai trò nhƣ ô bổ sung). Ví dụ 3.4: Cho bài toán vận tải nhƣ bảng 3.10. Bảng 3.10 T 51 54 60 45 80 P 50 10 11 10 9 8 90 12 12 5 13 11 70 19 18 6 14 15 80 18 17 7 15 12 - 75 -
Tìm phƣơng án vận chuyển tối ƣu. Giải: - Tìm phƣơng án cực biên xuất phát: Dùng phƣơng pháp Fogels, ta thu đƣợc phƣơng án cực biên X0 nhƣ bảng 3.11. Bảng 3.11 T 51 54 60 45 80 P 10 11 10 9 8 50 1,1,2,1x 5 45 12 12 5 13 11 90 6,1,1,0 46 44 19 18 6 14 15 70 10 60 0 8,1,3,1 18 17 7 15 12 80 5,3,5x 80 2,2,7x 1,1,6 1x 4x 3x - Xác định tập ô cơ sở: phƣơng án cực biên xuất phát có 7 ô chọn, thiếu một ô so với hạng của bài toán. Ta bổ sung thêm ô (3.5) để đủ 8 ô không chứa vòng. Khi đó ta có tập ô cơ sở J0 = {(1, 1), (1, 4), (2,1), (2,2), (3,2), (3,3), (3,5), (4, 5)}. Bảng 3.12 10 11 10 9 8 u1 =-8 5 - - 45 - 12 12 5 13 11 u2 = -6 46 44 - - - 19 18 6 14 15 u3 = 0 - 10 60 (3) 0 18 17 7 15 12 u4 = -3 - - - - 80 v1 = 18 V2 = 18 v3 = 6 v4 =17 v5 =15 - 76 -
- Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.12. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij , ta thấy ô (3, 4) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (3.4) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 4), (1, 4), (1, 1), (2, 1), (2, 2), (2, 3)}. q = min{45, 46, 10} = 10. Điều chỉnh 10 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1: Khi đó ô (3, 2) hết hàng trở thành ô loại, ô (3, 4) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J1. Bảng 3.13 10 11 10 9 8 u1 =-5 15 - - 35 (2) 12 12 5 13 11 u2 = -3 36 54 - - (1) 19 18 6 14 15 u3 = 0 - - 60 10 0 18 17 7 15 12 u4 = -3 - - - - 80 v1 = 15 V2 = 15 v3 = 6 v4 =14 v5 =15 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J1, ta đƣợc hệ thống thế vị nhƣ bảng 3.13. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (1, 5) và ô (2, 5) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (1, 5) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(1,5), (3, 5), (3, 4), (1, 4)}. q = min{35, 0} = 0. - 77 -
Điều chỉnh 0 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X2: khi đó ô (3, 5) trở thành ô loại, ô (1, 5) trở thành ô chọn, ta có hệ ô chọn cơ sở J2. Bảng 3.14 10 11 10 9 8 u1 =-5 15 - - 35 0 12 12 5 13 11 u2 = -3 36 54 - - - 19 18 6 14 15 u3 = 0 - - 60 10 - 18 17 7 15 12 u4 = -1 - - - - 80 v1 = 15 v2 = 15 v3 = 6 v4 =14 v5 =13 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J2, ta đƣợc hệ thống thế vị nhƣ bảng 3.14. - Kiểm tra tiêu chuẩn tối ƣu: ij 0, (i, j) . Vậy phƣơng án cực biên X2 là phƣơng án tối ƣu: 15 0 0 35 0 36 54 0 0 0 X 2 0 0 60 10 0 0 0 0 0 80 Khi đó tổng cƣớc phi vận chuyển nhỏ nhất là: f(X2) = 10.15 + 9.35 + 12.36 + 12.54 + 6.60 + 14.10 + 12.80 = 3005. 3. BÀI TOÁN VẬN TẢI KHÔNG CÂN BẰNG THU PHÁT m n 3.1. Phát lớn hơn thu: ( ai b j ) i 1 j 1 - 78 -
Khi vận chuyển xong cho các trạm thu thì các trạm phát còn tồn kho một m n lƣợng hàng tổng cộng là ai b j . Bài toán đặt ra nên để trạm phát nào phải i 1 j 1 chịu tồn kho và tồn bao nhiêu thì tổng chi phí vận chuyển sẽ thấp nhất. Để giải quyết bài toán này, ta lập thêm trạm thu thứ n + 1 (gọi là trạm thu m n giả) với nhu cầu nhận về là bn 1 ai b j , cƣớc phí từ các trạm phát đến các i 1 j 1 trạm thu giả là ci n+1 = 0, i = 1, m . Khi đó ta đƣợc bài toán vận tải cân bằng thu phát, tìm phƣơng án tối ƣu cho bài toán cân bằng này, từ đó suy ra phƣơng án tối ƣu của bài toán gốc: trạm phát nào phân hàng cho trạm thu giả thì trạm phát đó phải chịu tồn hàng. Chú ý rằng, khi giải bài toán trên nếu dùng phƣơng pháp cƣớc phí bé nhất để tìm phƣơng án cực biên xuất phát ta ƣu tiên phân phối hàng tối đa vào các ô có cƣớc phí dƣơng bé nhất trƣớc, rồi cuối cùng mới đến các ô có cƣớc phí bằng 0. Ví dụ 3.5: Tìm phƣơng án vận chuyển tối ƣu của bài toán vận tải (Bảng 3.15). Bảng 3.15 T 25 35 42 53 P 45 4 8 7 6 38 10 12 3 9 57 7 5 4 12 20 11 1 5 8 m n Giải: - Kiểm tra điều kiện cân bằng thu phát: ai 160, b j 155, nhƣ vậy i 1 j 1 phát lớn hơn thu. Ta lập thêm trạm thu giả B4 với nhu cầu nhận về tƣợng trƣng là: - 79 -
4 4 b5 ai bj = 160 – 155 = 5 đơn vị hàng, cƣớc phí ci5 = 0, i = 1,4. Khi đó i 1 j 1 ta đƣợc bài toán vận tải cân bằng thu phát nhƣ bảng 3.16. Bảng 3.16 T 25 35 42 53 5 P 45 4 8 7 6 0 38 10 12 3 9 0 57 7 5 4 12 0 20 11 1 5 8 0 - Tìm phƣơng án cực biên xuất phát: Dùng phƣơng pháp cƣớc phí bé nhất, ta thu đƣợc phƣơng án cực biên X0 nhƣ bảng 3.17. Bảng 3.17 T 25 35 42 53 5 P 4 8 7 6 0 45 25 20 10 12 3 9 0 38 38 7 5 4 12 0 57 15 4 33 5 11 1 5 8 0 20 20 Tập ô cơ sở J0 là tập các ô chọn nhƣ bảng trên. - 80 -
Bảng 3.18 4 8 7 6 0 u1 = -6 25 - - 20 - 10 12 3 9 0 u2 = -1 - - 38 (2) - 7 5 4 12 0 u3 = 0 (3) 15 4 33 5 11 1 5 8 0 u4 = -4 - 20 - (0) - v1=10 v2 = 5 V3 = 4 V4=12 v5 = 0 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.18. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (3, 1) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (3.1) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(3, 1), (1, 1), (1, 4), (3, 4)}. q = min{25, 33} = 25. Điều chỉnh 25 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1: Khi đó ô (1, 1) hết hàng trở thành ô loại, ô (3, 1) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J1. Bảng 3.19 4 8 7 6 0 u1 = -6 - - - 45 - 10 12 3 9 0 u2 = -1 - - 38 (2) - 7 5 4 12 0 u3 = 0 25 15 4 8 5 11 1 5 8 0 u4 = -4 - 20 - (0) - V1=7 v2 = 5 V3 = 4 V4=12 v5 = 0 - 81 -
- Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J1, ta đƣợc hệ thống thế vị nhƣ bảng 3.19. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij, ta thấy ô (2, 4) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (2, 4) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(2, 4), (3, 4), (3, 3), (2, 3)}. q = min{8, 38} = 8. Điều chỉnh 8 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X2: Khi đó ô (3, 4) hết hàng trở thành ô loại, ô (2, 4) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J2. Bảng 3.20 4 8 7 6 0 u1 = -4 4 - - - 45 - 10 12 3 9 0 u2 = -1 - - 30 8 - 7 5 4 12 0 u3 = 0 25 15 12 - 5 11 1 5 8 0 u4 = -4 - 20 - - - V1=7 v2 = 5 V3 = 4 v4=10 v5 = 0 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J2, ta đƣợc hệ thống thế vị nhƣ bảng 3.20. - Kiểm tra tiêu chuẩn tối ƣu: ij 0, (i, j). Vậy phƣơng án cực biên X2 là phƣơng án tối ƣu: 0 0 0 45 0 0 0 30 8 0 X . 2 25 15 12 0 5 0 20 0 0 0 Phƣơng án tối ƣu của bài toán gốc là: - 82 -
0 0 0 45 0 0 30 8 X , 25 15 12 0 0 20 0 0 theo phƣơng án này trạm phát A3 phải chịu tồn kho 5 đơn vị hàng. khi đó chi phí vận chuyển nhỏ nhất là:f(X) = 6.45 + 3.30 + 9.8 + 7.25 + 5.15 + 4.12 + 1.20 = 750. m n 3.2. Phát ít hơn thu: ( ai b j ) i 1 j 1 Khi vận chuyển hết hàng từ các trạm phát đến các trạm thu theo nhu cầu của các trạm thu, thì các trạm thu còn thiếu so với nhu cầu một lƣợng hàng tổng cộng n m là b j ai . Bài toán đặt ra nên để trạm thu nào phải chịu thiếu hàng và thiếu j 1 i 1 bao nhiêu thì tổng chi phí vận chuyển sẽ thấp nhất. Để giải quyết bài toán này, ta lập thêm trạm phát Am + 1 thứ m + 1 (gọi là n m trạm phát giả) với lƣợng hàng cần chuyển đi là am 1 b j ai , cƣớc phí từ j 1 i 1 các trạm phát giả đến các trạm thu là cm+1 j = 0, j = 1, n . Khi đó ta đƣợc bài toán vận tải cân bằng thu phát, tìm phƣơng án tối ƣu cho bài toán cân bằng này, từ đó suy ra phƣơng án tối ƣu của bài toán gốc: trạm thu nào nhận hàng của trạm phát giả thì trạm thu đó phải chịu thiếu hàng. Ví dụ 3.6: Cho bài toán vận tải Bảng 3.21 110 90 110 15 17 14 80 60 12 10 11 100 20 16 21 - 83 -
a. Viết dạng toán học của bài toán. b. Tìm phƣơng án vận chuyển tối ƣu. m n Giải: a. Kiểm tra điều kiện cân bằng thu phát: ai 240, b j 310, nhƣ vậy i 1 j 1 phát ít hơn thu, do đó các trạm phát tiêu thụ hết hàng, các trạm thu phải chịu thiếu hàng. Gọi xij là lƣợng hàng từ trạm phát Ai, đến trạm thu Bj (i 1,3, j 1,3). Khi đó ta có mô hình toán học nhƣ sau: Tìm ma trận X = (xij)3x3 sao cho: f(X) = 15x11 + 17x12 + 14x13 + 12x21 + 10x22 + 11x23 + 20x31 + 16x32 + 21x11 min. x11 + x12 + x13 = 80 x21 + x22 + x24 = 60 x31 + x32 + x33 = 100 x11 + x21 + x31 110 x21 + x22 + x32 90 x13 + x23 + x33 110 xij 0, i 1,3, j 1,3 b. Ta lập thêm trạm phát giả A4 với luợng hàng tƣợng trƣng cần chuyển đi là: 3 3 a4 b j ai = 310 - 270 = 70 đơn vị hàng, cƣớc phí c4j = 0, j = 1,3 . Khi đó j 1 i 1 ta đƣợc bài toán vận tải cân bằng thu phát trong bảng 3.22. - 84 -
Bảng 3.22 T 110 90 110 P 15 17 14 80 12 10 11 60 20 16 21 100 70 0 0 0 - Bằng phƣơng pháp cƣớc phí bé nhất, ta tìm đƣợc phƣơng án cực biên xuất phát X0 nhƣ bảng sau, phƣơng án cực biên X0 có cơ sở J0 là tập các ô chọn. Bảng 3.23 T 110 90 110 P 15 17 14 80 80 12 10 11 60 60 20 16 21 100 70 30 0 0 0 70 40 30 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij (i, j) J0, ta thu đƣợc hệ thống thế vị nhƣ ở bảng 3.24. - 85 -
Bảng 3.24 15 17 14 u1 = 14 - - 80 12 10 11 u2 = 14 (2) 60 (3) 20 16 21 u3 = 20 70 30 - 0 0 0 u4 = 0 40 - 30 v1 = 0 v2 = -4 v3 = 0 - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij đối với các ô loại, thấy ô (2, 1) và (2, 3) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: lấy ô (2, 3) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(2, 3), (2, 2), (3, 2), (3, 1), (4, 1), (4, 3)}. q = min{60, 70, 30} = 30. Điều chỉnh 30 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1 : khi đó ô (3, 4) hết hàng trở thành ô loại, ô (2, 3) có hàng trở thành ô chọn, đồng thời ta có cơ sở mới J1. Bảng 3.25 15 17 14 u1 = 17 (2) - 80 12 10 11 u2 = 14 (2) 30 30 20 16 21 u3 = 20 40 60 - 0 0 0 u4 = 0 70 - - v1 = 0 v2 = -4 v3 = -3 Xây dựng hệ thống thế vị, nhƣ bảng trên và kiểm tra tiêu chuẩn tối ƣu, ta nhận thấy ô (1, 1) và ô (2, 1) vi phạm. - 86 -
Lấy ô (2, 1) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh: V = {(2, 1), (3, 1), (3, 2), (2, 2)}. Lƣợng hàng điều chỉnh là q = min{30, 40} = 30. Điều chỉnh 30 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên thứ X2 nhƣ bảng 3.26. Bảng 3.26 15 17 14 u1 = 15 (0) - 80 12 10 11 u2 = 12 30 - 30 20 16 21 u3 = 20 10 90 - 0 0 0 u4 = 0 70 - - v1 = 0 v2 = -4 v3 = -1 Xây dựng hệ thống thế vị, kiểm tra thấy ij 0, (i, j). Vậy phƣơng án cực biên thứ X2 là phƣơng án tối ƣu của bài toán cân bằng thu phát. 0 0 80 30 0 30 X 2 10 90 0 70 0 0 Vậy phƣơng án tối ƣu của bài toán gốc là: 0 0 80 X 30 0 30 . 10 90 0 Theo phƣơng án này thì trạm thu B1 phải chịu thiếu 70 đơn vị hàng và tổng chi phí vận chuyển nhỏ nhất là: f(X) = 14.80 + 12.30 + 11.30 + 20.10 + 16.90 = 3450. - 87 -
4. BÀI TOÁN PHÂN PHỐI 4.1. Định nghĩa. Bài toán phân phối là bài toán quy hoạch tuyến tính có hệ ràng buộc giống nhƣ hệ ràng buộc của bài toán vận tải nhƣng với yêu cầu làm cực đại hàm mục tiêu. Dạng toán học mn f (X) cij x ij max i 1 j 1 n xij ( ) ai ,(i 1,m) j 1 m xij ( ) b j,(j 1,n) i 1 xij 0 (i = 1,m , j = 1, n ). cij 0; ai > 0; bj > 0, i, j. Trong bài toán phân phối, ta sử dụng thuật ngữ “ năng suất” thay cho thuật ngữ “cƣớc phí”, thuật ngữ “ tổng thu nhập” thay cho thuật ngữ “tổng chi phí”. 4.2. Phƣơng pháp giải Để tìm phƣơng án tối ƣu cho bài toán phân phối ta vẫn sử dụng phƣơng pháp thế vị. Tuy nhiên vẫn có những điểm khác so với bài toán min. + Kiểm tra điều kiện cân bằng. + Tìm phƣơng án cực biên xuất phát: - Phƣơng pháp “năng suất cao nhất”: Trên bảng năng suất, tìm ô có năng suất cao nhất và phân vào ô đó lƣợng hàng lớn nhất có thể đƣợc. Khi đó có ít nhất một dòng hay một cột chứa ô đó thoả mãn nhu cầu. Xoá bỏ dòng hay cột đó và lặp lại thuật toán cho các ô còn lại, sau một số hữu hạn bƣớc ta tìm đƣợc phƣơng án cực biên của bài toán. - Phƣơng pháp Fogels: Tính chênh lệch năng suất giữa hai ô có năng suất cao nhất của mỗi dòng và mỗi cột. Ƣu tiên phân hàng cho dòng hay cột có chênh lệch cao nhất vào ô có năng suất cao nhất một lƣợng hàng lớn nhất có thể đƣợc, - 88 -
khi đó có ít nhất một dòng hay cột thoả mãn nhu cầu. Xoá bỏ dòng hay cột đó, lặp lại thuật toán trên sau một số hữu hạn bƣớc ta thu đƣợc phƣơng án cực biên của bài toán. + Kiểm tra tiêu chuẩn tối ƣu: tiêu chuẩn tối ƣu của bài toán phân phối là: ij 0, i 1,m, j 1,n. + Tìm hệ thống thế vị và kiểm tra tính tối ƣu cho phƣơng án giống nhƣ bài toán min. + Điều chỉnh phƣơng án: Nếu phải cải tiến phƣơng án thì ô điều chỉnh là: ij = min{ ij < 0}. Ví dụ 3.7: Tìm phƣơng án vận chuyển tối ƣu của bài toán phân phối. Bảng 3.27 T 100 200 150 140 P 150 17 19 14 12 200 23 15 16 10 200 18 20 19 19 150 24 19 13 18 m n Giải: - Kiểm tra điều kiện cân bằng thu phát: ai 700, b j 590, nhƣ vậy i 1 j 1 phát lớn hơn thu. Ta lập thêm trạm thu giả B5 với nhu cầu nhận về tƣợng trƣng là: 4 4 b5 ai bj = 700 – 590 = 110 đơn vị hàng, cƣớc phí ci5 = 0, i = 1,4. Khi i 1 j 1 đó ta đƣợc bài toán vận tải cân bằng thu phát sau: - 89 -
Bảng 3.28 T 100 200 150 140 110 P 150 17 19 14 12 0 200 23 15 16 10 0 200 18 20 19 19 0 150 24 19 13 18 0 - Tìm phƣơng án cực biên xuất phát: Dùng phƣơng pháp Fogels, ta thu đƣợc phƣơng án cực biên nhƣ bảng 3.29. Bảng 3.29 T 100 200 150 140 110 P 17 19 14 12 0 150 2,5x 150 23 15 16 10 0 200 7,1,5 100 50 50 18 20 19 19 0 200 1,1,1 150 50 24 19 13 18 0 150 5,1,1 90 60 1x 1,1x 3,3x 1,1 Phƣơng án cực biên X0 có hệ ô chọn cơ sở J0. - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.30. - 90 -
Bảng 3.30 17 19 14 12 0 u1 = 4 + 150 + + + 23 15 16 10 0 u1 = 0 100 50 + + 50 18 20 19 19 0 u1 = 1 + (-4) 150 50 + 24 19 13 18 0 u1 = 0 (-1) (-4) + 90 60 v1=23 v2=15 v3=18 v4=18 v5 = 0 - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij , ta thấy ô (3,2), (4, 1) và (4, 2) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (4, 2) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(4, 2), (2, 2), (2, 5), (4, 5)}. q = min{50, 60} = 50. Điều chỉnh 50 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X1: Khi đó ô (2, 2) hết hàng trở thành ô loại, ô (4, 2) có hàng trở thành ô chọn, ta có hệ ô chọn cơ sở J1. Bảng 3.31 17 19 14 12 0 u1 = 0 + 150 + + + 23 15 16 10 0 u2 = 0 100 + + + 100 18 20 19 19 0 u3 = 1 + + 150 50 + 24 19 13 18 0 u4 = 0 (-1) 50 + 90 10 V1=23 v2=19 v3=18 v4=18 v5 = 0 - 91 -
- Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J1, ta đƣợc hệ thống thế vị nhƣ bảng 3.32. - Kiểm tra tiêu chuẩn tối ƣu: tính ij = ui + vj – cij , ta thấy ô (4,1) vi phạm tiêu chuẩn tối ƣu. - Điều chỉnh phƣơng án: Lấy ô (4, 1) làm ô điều chỉnh, ta đƣợc vòng điều chỉnh V = {(4, 1), (2, 1), (2, 5), (4, 5)}. q = min{100, 10} = 10. Điều chỉnh 10 đơn vị hàng từ các ô chẵn sang các ô lẻ, ta đƣợc phƣơng án cực biên X2, và hệ ô chọn cơ sở J2. Bảng 3.32 17 19 14 12 0 u1 = 1 + 150 + + + 23 15 16 10 0 u1 = 0 90 + + + 11 18 20 19 19 0 0 u1 = 2 + + 150 50 + 24 19 13 18 0 u1 = 1 10 50 + 90 + v1=23 v2=18 V3=17 v4=17 v5 = 0 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J2, ta đƣợc hệ thống thế vị nhƣ bảng 3.32. - Kiểm tra tiêu chuẩn tối ƣu: ij ≥ 0, (i, j). Vậy phƣơng án cực biên X2 là phƣơng án tối ƣu: 0 150 0 0 0 90 0 0 0 110 X . 0 0 150 50 0 10 50 0 90 0 Phƣơng án tối ƣu của bài toán gốc là: - 92 -
0 150 0 0 90 0 0 0 X , 0 0 0 150 50 10 50 0 90 theo phƣơng án này trạm phát A2 phải chịu tồn kho 110 đơn vị hàng. Khi đó tổng thu nhập cao nhất là: f(X) = 19.150 + 23.90 + 19.150 + 19.50 + 24.10 + 19.50 + 18.19 = 11530. 5. BÀI TOÁN Ô CẤM Trong thực tế ta thƣờng gặp tình huống trạm thu Bj không thể nhận hàng của trạm phát Ai, khi đó ô (i, j) đƣợc gọi là ô cấm. Bài toán vận tải hay bài toán phân phối có thêm yêu cầu trên đƣợc gọi là bài toán ô cấm. Muốn tìm phƣơng án tối ƣu của bài toán vận tải trong điều kiện nhƣ trên, ta làm cho cƣớc phí vận chuyển trở nên rất lớn. Khi đó trong phƣơng án vận chuyển tối ƣu sẽ không có hàng từ Ai đến Bj. Trên bảng vận tải, ta cho cƣớc phí cij = M > 0 đủ lớn. Còn đối với bài toán phân phối có ô cấm (i, j) thì ta cho năng suất cij = - M, với M là số dƣơng đủ lớn. Ví dụ 3.8: Cho bài toán vận tải nhƣ bảng 3.33, biết rằng trạm phát A1 phải tiêu thụ hết hàng. Tìm phƣơng án vận chuyển tối ƣu. Bảng 3.33 T 100 120 90 P 120 10 9,5 14 120 8,5 8 10 130 12 9 12 m n Giải: Kiểm tra điều kiện cân bằng thu phát: ai 370, b j 310, nhƣ vậy phát i 1 j 1 lớn hơn thu, do đó các trạm thu đƣợc nhận đủ hàng, các trạm phát phải chịu tồn hàng, nhƣng riêng trạm phát A1 phải đƣợc ƣu tiên tiêu thụ hết hàng. - 93 -
Ta lập thêm trạm thu giả B4 với luợng hàng tƣợng trƣng cần nhận về là: 3 3 b4 ai b j = 370 - 310 = 60 đơn vị hàng, cƣớc phí ci4 = 0, i = 1,3 . Khi đó j 1 i 1 ta đƣợc bài toán vận tải cân bằng thu phát trong bảng 3.34. Bảng 3.34 T 100 120 90 60 P 120 10 9,5 14 M 120 8,5 8 10 0 130 12 9 12 0 - Bằng phƣơng pháp Fogels, ta tìm đƣợc phƣơng án cực biên xuất phát nhƣ bảng 3.35. Bảng 3.35 T 100 120 90 60 P 10 9,5 14 M 0,5;4 120 100 20 8,5 8 10 0 0,5;1,5 120 90 30 12 9 12 0 3;0 130 120 10 1,5x 1x 2x - Tập ô cơ sở nhƣ bảng trên, k hiệu tập ô cơ sở là J. - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij (i, j) J, ta thu đƣợc hệ thống thế vị nhƣ ở bảng 3.36. - 94 -
Bảng 3.36 10 9,5 14 M u1 = 0 100 20 8,5 8 10 0 u2 = -M 90 30 12 9 12 0 u3 = -M 120 10 v1=10 v2=9+M v3=10+M v4 = M 9+M Bảng 3.37 10 9,5 14 M u1 = 0,5 100 20 8,5 8 10 0 u2 = 0 (1) (1) 90 30 12 9 12 0 u3 = 0 100 30 v1=9,5 v2 = 9 v3=10 v4 = 0 Bảng 3.38 10 9,5 14 M u1 = 9,5 100 20 8,5 8 10 0 u2 = 8 30 90 12 9 12 0 u3 = 9 70 60 v1=0,5 v2 = 0 V3=2 v4 = 9 - Xây dựng hệ thống thế vị: dùng công thức ui + vj = cij, (i, j) J0, ta đƣợc hệ thống thế vị nhƣ bảng 3.38. Kiểm tra thấy ij 0, (i, j). Vậy phƣơng án cực biên xuất phát là phƣơng án tối ƣu của bài toán cân bằng: - 95 -
100 20 0 0 X 0 30 90 0 0 70 0 60 100 20 0 Vậy phƣơng án tối ƣu của bài toán gốc là: X0 0 30 90 . 0 70 0 Theo phƣơng án này thì trạm phát A3 phải chịu tồn kho 60 đơn vị hàng và tổng chi phí vận chuyển nhỏ nhất là: f(X) = 10.100 + 9,5.20 + 8.30 + 10.90 + 9.70 = 2960. - 96 -
CHƢƠNG 4. MỘT SỐ BÀI TOÁN ỨNG DỤNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH I. BÀI TOÁN SẢN XUẤT ĐỒNG BỘ 1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN SẢN XUẤT ĐỒNG BỘ 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ộ 1.1.1. Nội dung kinh tế của bài toán sản xuất đồng bộ Giả sử có m máy công cụ khác nhau tham gia sản xuất một loại sản phẩm gồm n chi tiết khác nhau. Số máy mỗi loại tham gia quá trình sản xuất đƣợc giả thiết là một chiếc, số chi tiết mỗi loại cấu thành nên sản phẩm đƣợc giả thiết là tỷ lệ với nhau theo tỷ số 1 : 1 : : 1, do vậy có thể coi số chi tiết mỗi loại cấu thành nên sản phẩm đều là 1. Năng suất máy thứ i sản xuất chi tiết thứ j là aij (số đơn vị chi tiết/ 1 đơn vị thời gian) với i 1,m, j 1,n . Hãy bố trí thời gian để các máy sản xuất các chi tiết sao cho số sản phẩm đủ bộ (đồng bộ) sản xuất đƣợc là nhiều nhất. 1.1.2. Mô hình toán học của bài toán sản xuất đồng bộ Ta cần tìm tỷ lệ thời gian phân bố cho máy thứ i sản xuất chi tiết thứ j trong một đơn vị thời gian. Gọi xij là phần thời gian trong một đơn vị thời gian mà máy thứ i sản xuất n chi tiết thứ j, khi đó ta có: x 0, i 1,m, j 1,n và x 1, i 1,m . ij j1ij Số chi tiết j sản xuất đƣợc bởi máy i là ax , i 1,m, do đó tổng số chi tiết j ij sản xuất đƣợc bởi tất cả các máy là: m Zj a ij x ij , j 1,n . i1 Số sản phẩm đủ bộ là: - 97 -
m Z min{Zj , j=1,n}=min{Z j a ij x ij , j 1,n}. i1 mm Z ax,j1,nij ij ax ij ij Z0,j1,n . i 1 i 1 Khi đó dạng toán học của bài toán sẽ là: Tìm ma trận X = (xij)mxn và Z sao cho Z max (4.1) n xij 1, i 1,m (4.2) j1 m aij x ij Z 0, j 1,n (4.3) i1 xij 0, i 1,m, j 1,n;Z 0 (4.4) Bài toán (4.1) - (4.4) là bài toán QHTT. Định nghĩa 4.1. Bài toán qui hoạch tuyến tính có dạng toán học (4.1) (4.2) (4.3) (4.4) với giả thiết aij 0, i 1,m, j 1,n đƣợc gọi là bài toán sản xuất đồng bộ. Xuất phát từ thực tế, ta co hẹp phạm vi nghiên cứu của bài toán sản xuất đồng bộ nhƣ sau: với mỗi i, mỗi j đều tồn tại aij > 0, nghĩa là mỗi chi tiết j phải đƣợc sản xuất bởi ít nhất là một máy và mỗi máy i phải sản xuất đƣợc ít nhất một loại chi tiết. Trong trƣờng hợp tổng quát: Nếu máy loại i có ti chiếc tham gia vào quá trình sản xuất thì ta coi nhƣ chỉ có một chiếc máy loại này, nhƣng năng suất đƣợc ' quy ƣớc lại là aij t i a ij , j 1,n . Nếu chi tiết j có kj (đơn vị chi tiết j) cấu thành nên sản phẩm thì ta coi nhƣ chi tiết j chỉ có một đơn vị, nhƣng năng suất đƣợc quy ƣớc lại là: ' aij aij , i 1,m . k j - 98 -
Vì những lý do trên, về mặt lý thuyết ta chỉ cần nghiên cứu phƣơng pháp giải bài toán sản xuất đồng bộ nhƣ đã cho là đủ. 1.1.3. Bài toán đối ngẫu của bài toán sản xuất đồng bộ Để thuận tiện cho việc xây dựng phƣơng pháp giải bài toán sản xuất đồng bộ, ta giả thiết rằng aij > 0, i 1,m, j 1,n . Bài toán (4.1.1) (4.1.2) (4.1.3) (4.1.4) đƣợc viết dƣới dạng tƣờng minh nhƣ sau: Z → max x11 + x 12 + + x 1n ≤ 1 x 21 + x22 + + x2n ≤ 1 x m1 + xm2 + +x mn ≤ 1 -a11x11 -a21x21 - –am1xm1 + Z ≤ 0 -a12x12 -a22x22 - –am2xm2 + Z ≤ 0 -a1nx1n -a2nx2n - -amnxmn + Z ≤ 0 x 0, i 1,m, j 1,n;Z 0 ij Ma trận hệ số các ràng buộc chính của bài toán sản xuất đồng bộ là: 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 A a11 0 0 a 21 0 0 a m1 0 0 1 0 a12 0 0 a 22 0 0 a m2 0 1 0 0 a1n 0 0 a 2n 0 0 a mn 1 Bài toán đối ngẫu của bài toán sản xuất đồng bộ: Tìm các số u1, u2, , um, v1, v2, , vn sao cho - 99 -
m ui min (4.5) i1 ui a ij v j 0, i 1,m, j 1,n (4.6) n vj 1 (4.7) j1 uij 0,v 0, i 1,m, j 1,n (4.8) Các cặp điều kiện đối ngẫu: xij 0 vàu i av ij j 0,i1,m,j1,n n Z 0 và vj 1 j1 n xij 1 vàu i 0,i1,m j1 m axij ij Z 0vàv j 0, j 1,n i1 1.1.4. Dạng bảng của bài toán sản xuất đồng bộ Bảng 4.1 A11 a12 a1j a1n u1 x11 x12 x1j x1n ai1 ai2 aij ain ui xi1 xi2 xij xin am1 am2 amj amn um xm1 xm2 xmj xmn V1 v2 vj vn - 100 -
Bài toán sản xuất đồng bộ đƣợc biểu diễn dƣới dạng một bảng gồm m dòng, n cột và m.n ô. Ứng với mỗi máy loại i và mỗi chi tiết j ta có một ô nằm ở dòng thứ i và cột j, k hiệu là ô (i, j), trong ô này năng suất aij đặt ở góc trên bên trái, còn thời gian xij đặt ở góc dƣới bên phải của ô. 1.2. Tính chất của bài toán sản xuất đồng bộ 1.2.1. Phương án của bài toán sản xuất đồng bộ Định nghĩa 4.2. Ma trận X = (xij)mxn và Z thỏa mãn các ràng buộc (4.2), (4.3), (4.4) đƣợc gọi là phương án của bài toán sản xuất đồng bộ. Phƣơng án làm cho Z đạt cực đại đƣợc gọi là phương án tối ưu của bài toán. Với bất kỳ ma trận X = (xij)mxn thỏa mãn các ràng buộc (4.2), (4.4) cũng cho tƣơng ứng một họ phƣơng án với Z đƣợc xác định nhƣ sau: 0 Z min{Zj , j=1,n}, trong đó rõ ràng phƣơng án có Z min{Zj , j=1,n} là tốt hơn cả. Do đó ta sẽ xem ma trận X = (xij)mxn thỏa mãn các ràng buộc (4.2), (4.4) là một phƣơng án của bài toán sản xuất đồng bộ với Z đƣợc hiểu là: Z min{Zj , j=1,n}. 1.2.2. Tính chất cơ bản của bài toán sản xuất đồng bộ Định lý 4.1. Bài toán sản xuất đồng bộ luôn có phương án tối ưu. Chứng minh: Nhận thấy X = (xij) với xij = 1/n, i 1,m, j 1,n thỏa mãn điều kiện (4.2), (4.4). Vì vậy bài toán sản xuất đồng bộ luôn có phƣơng án. n Mặt khác, vì xij 1, i 1, m và xij 0 i, j nên 0 ≤ xij ≤ 1. Từ đó suy ra j 1 hàm mục tiêu: m m Zmin{ aij xij , j 1 , n } ≤ min{aij , j 1 , n }=C i 1 i 1 bị chặn trên bởi C trên tập phƣơng án nên bài toán có phƣơng án tối ƣu. - 101 -
Định lý 4.2. Trong phương án tối ưu của bài toán sản xuất đồng bộ thì Z luôn dương. Chứng minh: Theo giả thiết aij > 0, i 1,,, m j 1 n, đồng thời mỗi sản phẩm thứ i phải đƣợc sản xuất trên ít nhất một máy j, nên mỗi i đều tồn tại j để xij > 0. Do vậy từ: m Zmin{ Zj ,j=1, n }=min{ Z j aij x ij , j 1 , n } i 1 cho ta thấy Z > 0. Định l 4.3. Trong toán sản xuất đồng bộ hạng của ma trận hệ số các ràng buộc chính là m + n. Chứng minh: Ký hiệu Di véc tơ dòng thứ i của ma trận A với i 1, m n , ta chứng minh hệ m + n véc tơ dòng này độc lập tuyến tính. Xét đẳng thức sau: 1D1 + 2D2 + + m+nDm+n = 0 trong đó 0 là véc tơ không m.n + 1 chiều. Giả sử 1 0, ta có thể giả sử 1 = 1 (vì nếu không, ta chỉ việc chia cả hai vế của đẳng thức trên cho 1 0). Từ thành phần thứ nhất của đẳng thức trên ta có 1 - m+1 a11 = 0, suy ra m+1 > 0, tƣơng tự ta có m+j > 0, jn2, . Từ thành phần cuối n cùng của thứ m.n +1 của đẳng thức trên ta có mj 0 . Suy ra tổng các số j 1 dƣơng bằng 0, vô lý. Vì vậy 1 = 0. Lý luận tƣơng tự, ta có i = 0, i = 2, 3, , m. Từ n thành phần đầu tiên của đẳng thức trên ta suy m+j = 0, jn1, . Nhƣ vậy i 0,i 1, m n hay hệ {D1, D2, , Dn} độc lập tuyến tính. Ta có điều phải chứng minh. Định l 4.4. Nếu hệ thống số {(ui, vj ): i 1,,, m j 1 n} là phương án của bài toán đối ngẫu thì ui > 0, i 1,. m - 102 -
Chứng minh: Từ (4.7) và (4.8) suy ra vj > 0, kết hợp với (4.1.6) và aij > 0, i 1,,, m j 1 n, ta suy ra ui > 0, im1, . Nhận xét. Nếu Xx()ij mxn và {(uvij, ) : i 1,,, m j 1 n} là phƣơng án tối ƣu của bài toán gốc và bài toán đối ngẫu thì nn xij 1, i 1, m v à v j 1. jj11 Theo Định lý 4.2, Định lý 4.4 và Định lý lệch – bù ta có điều phải chứng minh. Định l 4.5. Nếu hệ thống số {( ) : } là phương án tối ưu của * bài toán đối ngẫu thì v j > 0, j 1,n. Chứng minh: Giả sử ngƣợc lại tồn tại v* 0 , vì u* 0, i 1,, m nên j0 i u a v0, i 1, m. Theo Định lý lệch bù thì phƣơng án tối ƣu của bài toán ijij00 * gốc phải thỏa mãn x 0, do đó chi tiết j0 không có, tức là Z = 0, mâu ij0 thuẫn với định lý 4.2. Vậy > 0, jm1, . Hệ quả. Nếu Xx()ij mxn và {( ) : } là phương án tối ưu của bài toán gốc và bài toán đối ngẫu thì m aij x ij Z0, j 1, n. i 1 Điều này có nghĩa là nếu X* là phƣơng án tối ƣu thì số các chi tiết sản xuất ra phải bằng nhau (Z1 = Z2 = = Zn). Hệ quả trên đƣợc suy ra từ định lý 4.5 và định lý lệch – bù. Định l 4.6. Nếu hệ thống số {(uvij, ) : } là phương án cực biên của n bài toán đối ngẫu thì v j 1. 1 - 103 -
Chứng minh: Giả sử {(uvij, ) : i 1,,, m j 1 n} là phƣơng án cực biên của bài toán n đối ngẫu mà không thỏa mãn v j 1. Khi đó nó phải thỏa mãn m + n ràng buộc 1 chặt độc lập tuyến tính dạng: ui – aijvj = 0, với iI1,jJ 1 vk = 0, với kJ2 , trong đó I1, J1, J2 là tập chỉ số nào đó thỏa mãn IJJ1{1, 2, ,m};J 1 , 2 {1, 2, ,n} và J 1 2 Hệ trên có duy nhất một nghiệm tầm thƣờng: ui = 0 iI1 ; vj =0, j JJ12. Điều này mâu thuẫn với định lý 4.4 nói rằng ui 0 , i 1, m . Vậy . Chú ý. Định lý 4.6 vẫn đúng trong trƣờng hợp tồn tại aij = 0, chỉ cần: max{aij, } > 0, j 1, n và max{aij, } > 0, . Nhận xét. Giả sử {(ui, vj ): } là phƣơng án tùy ý của bài toán đối ngẫu mà , ta sẽ trực tiếp suy ra phƣơng án {(ui’,vj’), } thỏa n ' mãn v j 1 nhờ phép biến đổi tỷ lệ sau: 1 u' u, i 1, m ii , ' vjj v, j 1, n 1 trong đó n 1. Khi đó giá trị hàm mục tiêu mới là: v j j 1 m m m m ui '' i 1 w wui u i u i nn w, i1 i 1 i 1 vvjj ii11 - 104 -
tức là phƣơng án {(ui’,vj’), i 1,,, m j 1 n} tốt hơn phƣơng án cũ. Tuy nhiên, ta sẽ coi hai phƣơng án này là tƣơng đƣơng nhau theo nghĩa từ phƣơng án này trực tiếp suy ra đƣợc phƣơng án kia nhờ một phép biến đổi tỷ lệ, vì vậy ta có coi chúng nhƣ chỉ là một phƣơng án. Tổng quát hơn, các phƣơng án {(uvij, ) : } chỉ khác nhau một thừa số nhân đƣợc coi nhƣ là một. Từ định lý 4.5 và định lý 4.6 suy ra để tìm phƣơng án tối ƣu của bài toán đối ngẫu ta chỉ cần tìm nó trong số các phƣơng án của bài toán đối ngẫu làm thỏa mãn chặt m + n – 1 ràng buộc chặt độc lập tuyến tính dạng ui - aij vj = 0 (mỗi dòng và mỗi cột đều phải có ít nhất một ô (i, j) mà ui - aij vj = 0) Định lý 4.7. Tập hợp m + n -1 ô ứng với m + n - 1 đẳng thức độc lập tuyến tính dạng ui - aij vj = 0 khi và chỉ khi nó không chứa vòng. Do vậy, phƣơng án thỏa mãn chặt m + n – 1 ràng buộc chặt độc lập tuyến tính ui - aij vj = 0 đƣợc gọi là phƣơng án cực biên suy rộng của bài toán đối ngẫu (4.1.5) – (4.1.8), với giá trị hàm mục tiêu tƣơng ứng là: m ui i 1 w n v j j 1 Mỗi phƣơng án cực biên suy rộng của bài toán đối ngẫu đƣợc gọi là hệ thống nhân tử của bài toán sản xuất đồng bộ, các số ui đƣợc gọi là nhân tử của dòng i, các số vj đƣợc gọi là nhân tử của cột j. 2. PHƢƠNG PHÁP NHÂN TỬ GIẢI BÀI TOÁN SẢN XUẤT ĐỒNG BỘ 2.1. Phƣơng pháp tìm phƣơng án cực biên suy rộng ban đầu Trên bảng năng suất, tìm ô có năng suất lớn nhất. Giả sử ô đó là ô (i0, j0), ta cho cột j0 nhân tử cột v = 1, nhân tử của các dòng và các cột khác đƣợc tính theo j0 nguyên tắc sau: - 105 -
- Nếu cột k đã có nhân tử, dò theo cột ấy, tìm ô có năng suất cao nhất trên những dòng chƣa có nhân tử, viết nhân tử cho dòng chứa ô ấy theo công thức: ui = max{aijvj với mọi cột j đã có nhân tử}. (4.1) Ô tƣơng ứng với tích lớn nhất này đƣợc lấy làm ô chọn. - Nếu dòng l đã có nhân tử, dò theo dòng ấy, tìm ô có năng suất cao nhất trên những cột chƣa có nhân tử, viết nhân tử cho cột chứa ô ấy theo công thức: ui vj = min{ : với mọi dòng i đã có nhân tử}. (4.2) aij Ô tƣơng ứng với thƣơng nhỏ nhất này đƣợc lấy làm ô chọn. Áp dụng nguyên tắc trên sau một số hữu hạn bƣớc lặp ta tìm đƣợc hệ thống m + n số (uij ,v ) : i 1,m, j 1,n. Chú ý. Nếu cực đại (4.1) hoặc cực tiểu (4.2) đạt tại nhiều ô thì có thể lấy một trong các ô đó làm ô chọn. Định lý 4.8. Hệ thống m + n số (ui, vj) : i 1,m, j 1,n tìm được theo phương pháp trên là một phương án cực biên của bài toán đối ngẫu. Chứng minh: Từ các bƣớc xác định ui, vj ta có ui –aij vj ≥ 0, ui > 0, vj > 0, i 1,m, j 1,n , còn tại các ô chọn thì ui –aijvj = 0. Ngoài ra cũng theo phƣơng pháp trên, các ô chọn không tạo thành vòng. Trừ ô đầu tiên (i0 ,j0) là ứng với hai nhân tử u ,v , còn sau đó có thêm một nhân tử ij00 dòng hoặc cột thì ta có thêm một ô chọn. Vì vậy số ô chọn bao giờ cũng là m + n – 1. Do đó hệ thống m + n số ( uij ,v ) : i 1,m, j 1,n làm thỏa mãn m + n -1 đẳng thức độc lập tuyến tính, vì vậy hệ thống số tìm đƣợc theo phƣơng pháp trên lập thành một phƣơng án cực biên của bài toán đối ngẫu. Ký hiệu tập các ô chọn là H, khi đó ta có ui – aijvj ≥ 0 (i, j) H (4.3) ui – aijvj = 0 (i, j) H (4.4) - 106 -
ui > 0, vj > 0, i 1,m, j 1,n . (4.5) Ví dụ 4.1: Tìm hệ thống nhân tử của bài toán sản xuất đồng bộ cho nhƣ bảng 4.2. Bảng 4.2 50 100 96 40 60 99 70 41 45 70 72 25 57 80 65 38 - Ô (1, 2) có năng suất là 100, cho v2 = 1. - Trên cột 1 ô (1, 2) có năng suất cao nhất trên các dòng chƣa có nhân tử nên: u1 = max{100.1} = 100, đạt tại ô (1, 2) nên lấy ô (1, 2) làm ô chọn và đánh dấu nhƣ bảng 4.3. Bảng 4.3 50 100 * 96 * 40 u1 = 100 60 * 99 70 41 * u2 = 100 45 * 70 72 * 25 u3 = 75 57 * 80 65 38 u4 = 95 v1 = 5/3 V2 = 1 V3 = v4 = 100/41 25/24 - Trên dòng 1 ô (1, 3) có năng suất cao nhất trên các cột chƣa có nhân tử nên: 100 25 v3 = min , 96 24 đạt tại ô (1, 3) nên lấy ô (1, 3) làm ô chọn và đánh dấu nhƣ bảng. - Trên cột 3 ô (3, 3) có năng suất cao nhất trên các dòng chƣa có nhân tử nên: 25 u3 = max{70.1; 72. } = 75, 24 - 107 -
đạt tại ô (3, 3) nên lấy ô (3, 3) làm ô chọn và đánh dấu nhƣ bảng. - Trên dòng 3 ô (3, 1) có năng suất cao nhất trên các cột chƣa có nhân tử nên: 100 75 5 v1 = min , , 50 45 3 đạt tại ô (3, 1) nên lấy ô (3, 1) làm ô chọn và đánh dấu nhƣ bảng. - Trên cột 1 ô (2, 1) có năng suất cao nhất trên các dòng chƣa có nhân tử nên: 5 25 u2 = max 60. ,99.1,70. 100, 3 24 đạt tại ô (2, 1) nên lấy ô (2, 1) làm ô chọn và đánh dấu nhƣ bảng. - Trên dòng 2 ô (2, 4) có năng suất cao nhất trên các cột chƣa có nhân tử nên: 100 100 75 100 v4 = min , , , 40 41 25 41 đạt tại ô (2, 4) nên lấy ô (2, 4) làm ô chọn và đánh dấu nhƣ bảng. - Trên cột 4 ô (4, 4) có năng suất cao nhất trên các dòng chƣa có nhân tử nên: 5 25 100 u4 = max 57. ,80.1,65. ,38. 95, 3 24 41 đạt tại ô (4, 1) nên lấy ô (4, 1) làm ô chọn và đánh dấu nhƣ bảng. 2.2. Xây dựng hệ thống số kiểm tra và tiêu chuẩn tối ƣu Ta tính xij và Z nhờ phƣơng án cực biên (ui, vj) của bài toán đối ngẫu theo các phƣơng trình sau: xij = 0, (,)i j H (4.6) n xij 1, i 1, m (4.7) j 1 - 108 -
m aij x ij Z0, j 1, n. (4.8) i 1 m ui Từ (4.8) ta có Z aij x ij , j 1, n , từ (4) ta có aij ở các ô chọn, xij = 0 i 1 v j mm ui 1 ở các ô loại nên Z xij ui x ij, j 1, n ii11vvjj n n m vji Z() u xij j1 j 1 i 1 nm Z vji u (Do (4.7)) ji11 m ui i 1 Z n W v j j 1 Khi có Z ta tính tiếp xij theo các phƣơng trình (4.6), (4.7), (4.8). - Nếu xij ≥ 0, (i, j) thì hệ thống nhân tử tƣơng ứng là phƣơng án tối ƣu của bài toán đối ngẫu, do đó ma trận X = (xij) là phƣơng án tối ƣu của bài toán sản xuất đồng bộ đã cho. - Nếu tồn tại ô chọn (i, j) mà xij < 0 thì hệ thống nhân tử tƣơng ứng chƣa phải là phƣơng án tối ƣu của bài toán đối ngẫu. Trong trƣờng hợp này ma trận X = (xij) đƣợc gọi là giả phƣơng án của bài toán sản xuất đồng bộ đã cho. X = (xij) đƣợc gọi là hệ thống số kiểm tra của phƣơng án cực biên của bài toán đối ngẫu. 2.3. Điều chỉnh phƣơng án Giả sử trong giả phƣơng án X = (xij) tồn tại ô chọn (i1, j1) mà x < 0, khi đó ij11 '' ta xây dựng phƣơng án cực biên – bộ số nhân tử mới (,)uvij không xấu hơn - 109 -
phƣơng án cực biên cũ (ui, vj). Muốn vậy ta tìm cách loại bỏ ô (i1, j1) khỏi tập các ô chọn, bổ sung ô chọn mới thay thế. Trƣớc hết ta sửa lại hệ thống nhân tử sao cho từ đẳng thức u a v 0 trở i1 i 1 j 1 j 1 thành u'' a v 0. Muốn vậy ta thực hiện phép biến đổi sau: i1 i 1 j 1 j 1 ' ' - Tại ô (i1, j1) ta giữ nguyên vv, còn uu( 1) , nghĩa là giữ jj11 ii11 nguyên nhân tử cột và sửa nhân tử dòng. - Các ô chọn khác, sau phép điều chỉnh vẫn là ô chọn, vì vậy đẳng thức '' ui a ij v j 0 vẫn phải thực hiện. Muốn vậy ta xét ô chọn (i, j) nào có nhân tử dòng ' ' ' uuiithì vvjj, ô chọn (i, j) nào có nhân tử cột vvij thì . Ta chia tập hợp các ô của bảng thành 4 nhóm sau: - Nhóm 1: Gồm các ô mà cả nhân tử dòng và cột đều tăng lên λ lần, vì vậy '' bất đẳng thức ui a ij v j 0 vẫn đúng với mọi λ. - Nhóm 2: Gồm các ô mà nhân tử dòng tăng lên λ lần, nhân tử cột giữ nguyên, vì vậy bất đẳng thức vẫn đúng với mọi λ ≥ 1. - Nhóm 4: Gồm các ô mà cả nhân tử dòng và nhân tử cột giữ nguyên, bất đẳng thức đúng. - Nhóm 3: Gồm các ô loại mà nhân tử dòng giữ nguyên, nhân tử cột tăng lên λ lần. '' Để sau khi sửa hệ thống thế vị {(uij ,v ): i=1,m;j=1,n} vẫn là phƣơng án ta '' phải chọn λ sao cho ui a ij v j u i aij v j 0, với mọi ô (i, j) thuộc nhóm 3, ký u hiệu nhóm này là A. Suy ra i ,(,)i j A. avij j ui Do ui – aijvj ≥ 0 nên λ ≥ 1. Vậy 1 , (i, j) A . avij j Muốn phƣơng án là phƣơng án cực biên thì phải có thêm ô chọn mới lấy thêm ở các ô loại cũ và chỉ chọn thêm đƣợc ở tập hợp A, ta - 110 -
ui chọn min , (i, j) A . Giả sử cực tiểu đạt tại ô (i2, j2). Khi đó ô (i2, j2) avij j đƣợc lấy làm ô chọn mới thay thế ô (i1, j1) bị loại. Dễ thấy rằng m + n – 1 ô chọn mới không chứa vòng. Ngƣời ta đã chứng minh đƣợc rằng phƣơng án cực biên suy rộng mới tốt hơn phuƣơng án cực biên suy rộng cũ (với giả thiết bài toán đối ngẫu không suy biến thì λ > 1). 2.4. Thuật toán nhân tử giải bài toán sản xuất đồng bộ Bƣớc 1. Xây dựng phƣơng án cực biên suy rộng ban đầu của bài toán đối ngẫu là w1 = (ui, vj) với tập ô chọn H. Bƣớc 2. Kiểm tra tiêu chuẩn tối ƣu. Từ phƣơng án cực biên suy rộng w1 = (ui, vj) ta thực hiện các thao tác sau: m ui i 1 - Tính Z n v j j 1 - Tính giả phƣơng án X1 = (xij) từ hệ xij = 0, (,)i j H n xij 1, i 1, m j 1 m aij x ij Z, j 1, n . i 1 + Nếu xij 0, ( i , j ) thì giả phƣơng án X1 là phƣơng án cực biên tối ƣu của bài toán sản xuất đồng bộ. + Nếu xij 0 thì chuyển sang bƣớc 3. Bƣớc 3. Điều chỉnh chỉnh nhân tử (giả sử loại ô (i1, j1) vì có x0): ij11 - Tìm tập A. uu - Tìm miniir2 :(i , j ) A a vrk a v ir j k j k i 2 j 2 j 2 - 111 -
Đƣa ô (i2, j2) vào tập các ô chọn thay cho ô (i1, j1) '' - Xây dựng hệ thống nhân tử mới w2 = (,)uvij bằng cách: '' + Hoặc ui u i, v j v j tại hàng i hay cột j có chữ λ. + Hoặc tính lại từ đầu bằng cách đặt một nhân tử vj = 1 ở cột j nào đó, sau đó tính ui, vj theo công thức ui – aijvj = 0 với (,)i j H . Ta có phƣơng án cực biên w2 tốt hơn w1. Gán w2 = w1 quay trở lại bƣớc 2. Sau hữu hạn bƣớc lặp ta tìm đƣợc phƣơng án tối ƣu. Chú ý: + Trƣờng hợp bài toán đối ngẫu suy biến, có thể gặp λ =1, khi đó ta vẫn áp dụng thuật toán bình thƣờng nhƣng kết quả không cho phƣơng án cực biên suy rộng mới mà chỉ chuyển sang cơ sở khác của phƣơng án ấy. Điều này có thể làm xuất hiện hiện tƣợng xoay vòng. Tuy nhiên trong thực tế tính toán chúng ta dễ dàng thoát khỏi hiện tƣợng xoay vòng. + Khi λ đạt tại nhiều ô khác nhau đây là dấu hiệu bài toán suy biến, khi đó ta chọn ngẫu nhiên một trong các ô đó vào làm ô chọn. Ví dụ 4.2: Tìm phƣơng án tối ƣu của bài toán sản xuất đồng bộ với phƣơng án cực biên suy rộng đã xây dựng đƣợc nhƣ ở ví dụ 1. Bảng 4.4 50 100 * 96 * 40 u1 = 100 60 * 99 70 41 * u2 = 100 λ (-) 45 * 70 72 * 25 u3 = 75 57 * 80 65 38 u4 = 95 (+) v1 = 5/3 V2 = 1 v3 = 25/24 v4 = 100/41 λ - 112 -
4 u i 100 100 75 95 Z i 1 60,19 4 5 / 3 1 25 / 24 100 / 41 v j j 1 Nhận thấy trên cột 4 chỉ có một ô chọn (2, 4) nên x24 = Z/a24 > 1. Trên hàng 2 có các ô chọn (2, 1) và (2, 4) nên x21 + x24 = 1. Suy ra x21 = 1 - x24 < 0, ghi dấu (-) vào ô (2, 1) nhƣ bảng trên. Ta chuyển sang điều chỉnh phƣơng án. x21 < 0 nên u2 phải sửa, dóng theo dòng 2 gặp ô chọn (2, 4) vì vậy nhân tử cột v4 phải sửa. Dóng theo cột 4 không gặp ô chọn nào nữa, vì vậy các nhân tử khác giữ nguyên (những nhân tử phải sửa ta viết thêm chữ λ vào cạnh bên để đánh dấu nhƣ ở bảng trên). 100 75 95 41 A = {(1, 4), (3, 4), (4, 4)}, λ = min ,, . 100 100 100 40. 25. 38. 40 41 41 41 Cực tiểu đạt tại ô (1, 4) và (4, 4). Lấy một trong 2 ô này làm ô chọn mới thay thế ô (2, 1) bị loại, chẳng hạn ô (4, 4), ghi dấu (+) vào ô (4, 4) nhƣ bảng trên. Xây dựng bảng mới với hệ thống ô chọn mới, hệ thống nhân tử mới theo '' một trong hai cách: Hoặc ui u i, v j v j tại hàng i hay cột j có chữ λ, hoặc tính lại từ đầu bằng cách đặt một nhân tử cột vj = 1 nào đó. Bảng 4.5 50 100 * 96 * 40 u1 = 100 60 99 70 41 * u2 = 102,5 45 * 70 72 * 25 u3 = 75 57 * 80 65 38 * u4 = 95 v1 = 5/3 V2 = 1 v3 = 25/24 v4 = 5/2 - 113 -
4 u i 100 102,5 75 95 Ta có Z i 1 60 . 4 5/3 1 25/24 5/2 v j j 1 x12 + x13 = 1 x24 = 1 x31 + x33 = 1 x41 + x44 = 1 45x31 + 57x41 = 60 100x12 = 60 96x13 + 72x33 = 60 41x24 + 38x44 = 60 Giải hệ trên ta tìm đƣợc: x24 = 1; x44 = 0,5; x41 = 0,5; x31 = 0,7; x33 = 0,3; x13 = 0,4; x12 = 0,6. Do mọi xij ≥ 0 nên phƣơng án tối ƣu cần tìm của bài toán đã cho là 0 0,6 0,4 0 0 0 0 1 X* 0,7 0 0,3 0 0,5 0 0 0,5 với số sản phẩm đủ bộ sản xuất ra đƣợc nhiều nhất là fmax= 60. - 114 -
II. BÀI TOÁN TRÕ CHƠI MA TRẬN 1. MỘT SỐ KHÁI NIỆM MỞ ĐẦU 1.1. Ví dụ về trò chơi ma trận + Quy tắc chơi: Hai đối thủ P và Q cùng chơi, mỗi ngƣời đều có một viên bi trắng (T) và một viên bi xanh (X). Cùng một lúc (bằng hiệu lệnh nào đó) mỗi ngƣời lấy ra một viên bi và đặt nó lên bàn. + Cách trả tiền: Q trả cho P 1 đồng nếu hai viên bi chọn ra cùng màu, hoặc – 1 đồng (nghĩa là P trả cho Q 1 đồng) nếu hai viên bi chọn ra khác màu. Trong trƣờng hợp đầu ta nói P thắng, Q thua; trƣờng hợp sau ta nói Q thắng, P thua. Trò chơi cứ tiếp tục nhƣ thế. Số tiền trả 1 hay – 1 biểu thị số thu nhập hay số tổn thất của P. P mong muốn làm cực đại số thu nhập của mình nên P đƣợc gọi là người chơi max, còn Q mong muốn làm cực tiểu số thu nhập của đối thủ P (hay là cực tiểu số tổn thất của mình) nên Q đƣợc gọi là người chơi min. + Ma trận trò chơi: đƣợc thể hiện nhƣ bảng 4.6. Bảng 4.6 Q S N P S 1 -1 N -1 1 11 Ma trận A = đƣợc gọi là ma trận thu hoạch hay ma trận thắng 11 hay ma trận trả tiền của P. Ví dụ trên là một dạng của trò chơi ma trận hay còn gọi là trò chơi đối kháng hai đối thủ với tổng 0 (số thu hoạch của ngƣời này bằng số tổn thất của ngƣời kia). 1.2. Bài toán trò chơi ma trận Định nghĩa 4.3. Trò chơi ma trận là trò chơi đƣợc xác định bởi ma trận m hàng, n cột A = (aij)mxn với aij là số thực tùy ý cho trƣớc . Ma trận A đƣợc gọi là ma trận - 115 -
thắng (hay ma trận thu hoạch, hay ma trận trả tiền). Phần tử aij biểu thị mức độ thắng (chẳng hạn số tiền mà Q phải trả cho P, thắng thì aij > 0, thua thì aij < 0,hòa thì aij = 0) của P nếu P chọn cách chơi thứ i, còn Q chọn cách chơi thứ j. Đối với ngƣời chơi P thì A là ma trận thắng (hay ma trận thu hoạch, hay ma trận trả tiền), ngƣợc lại đối với ngƣời chơi Q thì - A là ma trận thắng (hay ma trận thu hoạch, hay ma trận trả tiền). Định nghĩa 4.4. Với mỗi i = 1, 2, , m, véc tơ đơn vị thứ i X = (0, 0, , 1, , 0) m với số 1 ở tọa độ thứ i, đƣợc gọi là chiến lược đơn thứ i của P. Véc tơ chiến lƣợc thứ i biểu thị việc ngƣời chơi P chọn hàng i của ma trận A. Để đơn giản, thay vì nói chiến lƣợc đơn thứ i ta nói chiến lƣợc i. Tƣơng tự, Với mỗi j = 1, 2, , n, véc tơ đơn vị thứ j X = (0, 0, , 1, , 0) n với số 1 ở tọa độ thứ j, đƣợc gọi là chiến lược đơn thứ j của Q. Véc tơ chiến lƣợc thứ j biểu thị việc ngƣời chơi Q chọn hàng j của ma trận A. Để đơn giản, thay vì nói chiến lƣợc đơn thứ j ta nói chiến lƣợc j. Chú ý rằng trong các trò chơi ma trận, thông tin về cách chơi của mỗi đối thủ cần đƣợc giữ kín. Ở mỗi lần chơi, các đối thủ không chọn cố định một chiến lƣợc đơn ( hàng, cột) cụ thể nào mà sẽ lựa chọn phối hợp các hàng (cột) theo tỷ lệ (xác suất) nào đó. Vì thế, ta đi đến khái niệm chiến lƣợc hỗn hợp. Định nghĩa 4.5. Véc tơ X = (x1, x2, , xm) với xi 0,i 1,m và x1 + x2 + + xm = 1, trong đó xi biểu thị xác suất để P chọn cách chơi thứ i, đƣợc gọi là chiến lược hỗn hợp của P. Tƣơng tự, Véc tơ Y = (y1, y2, , yn) với yj 0, j 1,n và y1 + y2 + + yn = 1, trong đó yj biểu thị xác suất để Q chọn cách chơi thứ j, đƣợc gọi là chiến lược hỗn hợp của Q. - 116 -
1.3. Hàm thu hoạch của P Khi P chọn chiến lƣợc hỗn hợp X = (x1, x2, , xm) và Q chọn chiến lƣợc hỗn hợp Y = (y1, y2, , yn) thì phần thắng của P (cũng là phần thua của Q) đƣợc tính nhƣ sau: Nếu Q chọn chiến lƣợc đơn thứ nhất (cột 1 của A) thì kỳ vọng thắng cuộc m của P là: a11x1 + a21x2 + + am1xm = axi1 i . i1 Nếu Q chọn chiến lƣợc đơn thứ hai (cột 2 của A) thì kỳ vọng thắng cuộc của m P là: a12x1 + a22x2 + + am2xm = axi2 i . i1 Nếu Q chọn chiến lƣợc đơn thứ n (cột n của A) thì kỳ vọng thắng cuộc của P m là: a1nx1 + a2nx2 + + amnxm = axin i . i1 Do Q chọn chiến lƣợc hỗn hợp Y = (y1, y2, , yn) nên kỳ vọng thắng cuộc của P là: m m m nm E(X, Y) = y1 axi1 i + y2 axi2 i + + yn axin i = aij x i y j . i1 i1 i1 j 1 i 1 Định nghĩa 4.6. Hàm thu hoạch hay số thu hoạch của P là số thực E(X, Y) = , trong đó X = (x1, x2, , xm) và Y = (y1, y2, , yn) tƣơng ứng là chiến lƣợc hỗn hợp bất kỳ của P và Q. Ví dụ 4.3: Xét trò chơi cho bởi ma trận chữ nhật (m = 3, n = 4): 1 3 3 2 5 4 0 1 3 1 2 4 - 117 -
111 1 1 1 1 Xét cặp chiến lƣợc X = và Y = . Tính số thu 244 1 4 4 4 hoạch của P? Q chọn cột 1: kỳ vọng thắng của P là: 1 1/2 5 1/4 3 1/4 2,5. Q chọn cột 2: kỳ vọng thắng của P là: 3 1/2 4 1/4 1 1/4 2,25. Q chọn cột 3: kỳ vọng thắng của P là: 31/2 0 1/4 2 1/4 2 . Q chọn cột 1: kỳ vọng thắng của P là: 2 1/2 1 1/4 4 1/4 2,25. Vậy số thu hoạch của P là: E(X, Y) = 2,5 1/4 2,25 1/4 2 1/4 2,25 1/4 2,25. 2. ĐIỂM YÊN NGỰA VÀ CHIẾN LƢỢC TỐI ƢU 2.1. Điểm yên ngựa Xét trò chơi cho bởi ma trận trả tiền A = (aij). Nếu P chọn chiến lƣợc đơn thứ i thì P tin chắc sẽ nhận đƣợc số thu hoạch ít nhất là minaij . j Do P có thể chọn chiến lƣợc đơn bất kỳ nên P sẽ chọn chiến lƣợc đơn làm cực đại số thắng cuộc, nghĩa là P sẽ chọn i sao cho là lớn nhất. Bằng cách chọn chiến lƣợc đơn này, P bảo đảm thắng ít nhất là maxminaij . i j Tƣơng tự, nếu Q chọn chiến lƣợc đơn j, Q tin chắc số tiền phải trả (tổn thất) nhiều nhất là maxaij . Nhƣ vậy Q sẽ cách chọn chiến lƣợc đơn làm cực tiểu số tổn i thất của mình. Bằng cách chọn chiến lƣợc đơn này Q có thể giữ cho P thắng nhiều nhất (Q thua ít nhất) là minmaxaij . j i Định nghĩa 4.7. Nếu ma trận trả tiền A thỏa mãn điều kiện: = = ahk = v, thì ta nói rằng trò chơi ma trận có điểm yên ngựa và giá của điểm yên ngựa là phần tử ahk = v. - 118 -
Khi trò chơi có điểm yên ngựa ahk, P sẽ thắng ít nhất v, nếu P chọn chiến lƣợc đơn h và Q sẽ thua nhiều nhất là v, nếu Q chọn chiến lƣợc đơn k. Khi đó h là chiến lƣợc tối ƣu cho P và k là chiến lƣợc tối ƣu cho Q. Ví dụ 4.4: Cho trò chơi với ma trận trả tiền 1 3 1 2 5 4 0 1 . 3 3 2 3 Ta có: mina1j = a11 = a13 = 1, mina2j = a23 = 0, mina3j = a33 = 2 và j j j maxminaij = 2 = a33. i j maxai1 = a21 = 5, maxai2 = a22 = 4, maxai3 = a33 = 2, maxai4 = a34 = 3 và i i i i minmaxaij = 2 = a33. j i Vậy giá của điểm yên ngựa là a33 = 2 = v, ứng với cặp chiến lƣợc đơn X = (0, 0, 1) và Y = (0, 0, 1, 0). Ta nhận xét rằng a33 là vừa là phần tử nhỏ nhất trên hàng 3, vừa là phần tử lớn nhất trên cột 3. Bất cứ điểm yên ngựa nào cũng có tính chất này. Tổng quát, ta có nếu ahk = v là giá của điểm yên ngựa thì h là chiến lƣợc đơn tối ƣu của P và k là chiến lƣợc đơn tối ƣu của Q. Tuy nhiên không phải trò chơi ma trận nào cũng có điểm yên ngựa, nghĩa là có chiến lƣợc đơn tối ƣu. Vì thế ta đi đến khái niệm chiến lƣợc hỗn hợp tối ƣu. 2.2. Chiến lƣợc tối ƣu Định nghĩa 4.8. Nghiệm của trò chơi ma trận là cặp chiến lƣợc hỗn hợp X (x,x1 2 , ,x m ),Y (y,y 1 2 , ,y n ) và số thực v, ký hiệu E( X , Y , v) sao cho: a. E( , ) = v, b. E( , j) v với mọi chiến lƣợc đơn j = 1, 2, , n, c. E(i, ) = v với mọi chiến lƣợc đơn i = 1, 2, , m. - 119 -
X , Y tƣơng ứng gọi là chiến lược tối ưu của P và Q, v gọi là giá của trò chơi. Định nghĩa trên cho thấy nếu P chọn cách chơi theo tỷ lệ cho bởi chiến lƣợc tối ƣu thì dù Q chơi thế nào, P cũng luôn thắng ít nhất là v. Cũng vậy, nếu Q chọn cách chơi theo tỷ lệ cho bởi chiến lƣợc tối ƣu thì dù P chơi thế nào, Q chỉ thua nhiều nhất là v. Giá v có thể dƣơng, âm hoặc bằng 0. Định lý 4.9. ( Định lý minimax) Mọi trò chơi ma trận với các phần tử dương, hàm thu hoạch E(X, Y) bao giờ cũng tồn tại giá tối ưu, hay ta có maxmin E( X ,Y ) minmax E( X ,Y )= v. XY YX Nhận xét: 1) Mọi trò chơi ma trận, với aij > 0, đều có nghiệm ( , , v) thỏa mãn E(X, ) ≤ E( , ) = v ≤ E( ,Y), với mọi cặp chiến lƣợc hỗn hợp X, Y. 2) Nếu ma trận trả tiền A có phần tử âm thì ta có thể thay thế nó bằng ma trận Ap = (aij + p), với aij + p > 0, bằng cách chọn p = 1 – min{aij: aij 0. 2.3. Trò chơi đối xứng 2.3.1. Định nghĩa. Trò chơi đối xứng là trò chơi có ma trận trả tiền A thỏa mãn các điều kiện sau: a) A là ma trận vuông cấp n; b) aii = 0,với mọi i; c) aij = -aji, với mọi i, j. Ma trận A với các tính chất a, b, c nhƣ trên gọi là ma trận đối xứng lệch. Ví dụ 4.5: Trò chơi dân gian: “One – Two -Three” (đọc chệch là Oẳn tù tì) là một trò chơi ma trận với tập chiến lƣợc đơn giống nhau cho cả hai đấu thủ: ở mỗi lần chơi, mỗi ngƣời chơi giơ tay ra hiệu chọn “Giấy” hoặc “Búa” hoặc “Kéo” với quy ƣớc: Giấy thắng Búa, Búa thắng Kéo, Kéo thắng Giấy. Ma trận trả tiền có dạng: - 120 -
Bảng 4.7 Q Giấy Búa Kéo P Giấy 0 1 -1 Búa -1 0 1 Kéo 1 -1 0 2.3.2. Tính chất của trò chơi đối xứng +) Nếu X = Y thì E(X, Y) = 0, nghĩa là hai ngƣời chơi sử dụng cùng một chiến lƣợc nhƣ nhau thì kỳ vọng thắng cuộc của họ bằng 0. +) Giả sử chiến lƣợc tối ƣu của hai ngƣời lần lƣợt là X và Y .Khi đó = và v = E( , ) = 0, nghĩa là giá của trò chơi đối xứng bằng 0. Chiến lƣợc tối ƣu cho trò chơi “Giấy – Búa – Kéo” là = = (1/3, 1/3, 1/3) với giá v = 0. 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 3.1. Đƣa trò chơi ma trận về bài toán quy hoạch tuyến tính Xét trò chơi ma trận A = (aij)mxn. Theo định nghĩa 4 và định nghĩa 6 thì bài toán của P là tìm véc tơ X = (x1, x2, , xm) và số v sao cho a11x1 + a21x2 + + am1xm ≥ v (cộng theo cột 1), a12x1 + a22x2 + + am2xm ≥ v (cộng theo cột 2), a1nx1 + a2nx2 + + amnxm ≥ v (cộng theo cột n), x1 + x2 + + xm = 1, xi ≥ 0, i = 1, 2, , m. Bài toán của Q là tìm véc tơ Y = (y1, y2, , yn) và số v sao cho a11y1 + a12y2 + + a1nyn ≤ v (cộng theo hàng 1), a21y1 + a22y2 + + a2nyn ≤ v (cộng theo hàng 2), am1y1 + am2y2 + + amnyn ≤ v (cộng theo hàng m), - 121 -
y1 + y2 + + yn = 1, yj ≥ 0, i = 1, 2, , n. Không mất tính tổng quát, ta có thể giả thiết aij > 0 và vì thế v > 0. Đặt x y x' i ,i 1,m và y' j , j 1,n . Ta có i v j v 1 1 x''' x x và y''' y y . 1 2 m v 1 2 n v Ta thấy v là số tiền mà P nhận đƣợc và v cũng là số tiền mà Q phải trả nên P tìm cách làm cực đại v hay cực tiểu 1/v; còn Q tìm cách làm cực tiểu v hay cực đại 1/v. Vì thế ta có cặp bài toán quy hoạch tuyến tính đối ngẫu: Bài toán của P: ''' f1 x 1 x 2 x m min ''' a11 x 1 a 21 x 2 a m1 x m 1 ''' a12 x 1 a 22 x 2 a m2 x m 1 ''' a1n x 1 a 2n x 2 a mn x m 1 ' xi 0,i 1,m Bài toán của Q: ''' f2 y 1 y 2 y n max ''' a11 y 1 a 12 y 2 a 1n y n 1 ''' a21 y 1 a 22 y 2 a 2n y n 1 ''' am1 y 1 a m2 y 2 a mn y n 1 ' yj 0, j 1,n Nhận xét. + Hai bài toán trên lập thành cặp bài toán quy hoạch tuyến tính đối ngẫu. Hơn nữa, rõ ràng cả hai bài toán đều có phƣơng án nên cả hai bài toán đều có mn ''1 phƣơng án tối ƣu và min xij max y . X' Y' i 1 j 1 v (Số tiền thắng nhỏ nhất của P bằng số tiền thua lớn nhất của Q). - 122 -
+ Chiến lƣợc tối ƣu của P1 và P2 tƣơng ứng là: ' ' xii v x ,i 1,n và yjj v y , j 1,n . 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 + Xét ma trận A đã thỏa mãn mọi aij > 0, nếu chƣa ta đƣa ma trận A về ma trận Ap sao cho mọi aij > 0, bằng cách chọn p = 1 – min{aij: aij 0. Cặp bài toán đối ngẫu của P và Q là: ''' (P) f1 x 1 x 2 x 3 min ''' 6x1 2x 2 5x 3 1 3x''' 4x 6x 1 1 2 3 ''' 4x1 2x 2 x 3 1 ''' x1 0,x 2 0,x 3 0 - 123 -
''' (Q) f2 y 1 y 2 y 3 max ''' 6y1 3y 2 4y 3 1 2y''' 4y 2y 1 1 2 3 ''' 5y1 6y 2 y 3 1 ''' y1 0,y 2 0,y 3 0 Ta giải bài toán (Q). Đƣa bài toán (Q) về dạng chính tắc nhƣ sau: ''' f2 y 1 y 2 y 3 min '''' 6y1 3y 2 4y 3 y 4 1 '''' 2y1 4y 2 5y 3 y 5 1 '''' 5y1 6y 2 y 3 y 6 1 ' yj 0, j 1,6 Chọn cơ sở {A4, A5, A6} với phƣơng án cực biên xuất phát ta có bảng đơn hình nhƣ sau Bảng 4.8 Tọa -1 -1 -1 0 0 0 Bảng Cơ sở Hệ số độ Số Ai ci A1 A2 A3 A4 A5 A6 xio A4 0 1 6 3 4 1 0 0 A5 0 1 2 4 2 0 1 0 I A6 0 1 5 6 1 0 0 1 f(X) = -10 1 1 1 0 0 0 A4 0 1/2 7/2 0 7/2 1 0 -1/2 A5 0 1/3 -4/3 0 4/3 0 1 -2/3 II A2 -1 1/6 5/6 1 1/6 0 0 1/6 F(X) = -1/6 1/6 0 5/6 0 0 -1/6 A3 -1 1/7 1 0 1 2/7 0 -1/7 A5 0 1/7 -8/3 0 0 -8/21 1 -6/7 III A2 -1 1/7 2/3 1 0 -1/21 0 4/21 F(X) = -2/7 -2/3 0 0 -5/21 0 -1/21 - 124 -
Tại bảng III ta thấy j 0, j = 1,6 nên phƣơng án tối ƣu của bài toán (Q) là: Y’ = (0, 1/7, 1/7, 0, 1/7, 0). Suy ra phƣơng án tối ƣu của bài toán (Q) là Y’ = (0, 1/7, 1/7) và f1 = f1 = 2/7 = 1/vp. Ta có Y’ = (0, 1/7, 1/7) thỏa mãn lỏng các ràng buộc sau ' y02 ' y03 , ''' 2y1 4y 2 2y 3 1 nên theo định lý lệch bù ta có ''' ' 3x1 4x 2 6x 3 1 x1 5 / 21 ''' ' 4x1 2x 2 x 3 1 x02 . ' ' x02 x3 1/ 21 Phƣơng án tối ƣu của bài toán (P) là X’ = (5/21, 0, 1/21). Nghiệm của trò chơi là: + Chiến lƣợc tối ƣu của P là: X* = v.X’ = 7/2.(5/21, 0, 1/21) = (5/6, 0, 7/42). + Chiến lƣợc tối ƣu của Q là: Y* = v.Y’ = 7/2.(0, 1/7, 1/7) = (0, 1/2, 1/2). + Giá của trò chơi: v* = vp – p = 7/2 – 4 = -1/2. - 125 -
TÀI LIỆU THAM KHẢO [1]. Nguyễn Quang Đông, Ngô Văn Thứ, Hoàng Đình Tuấn, Giáo trình mô hình toán kinh tế, Nhà xuất bản Giáo dục, 2002. [2]. Trần Xuân Sinh, Toán kinh tế, Nhà xuất bản Đại học Quốc gia Hà Nội, 2007. [3]. Phạm Đình Phùng, Nguyễn Văn Quý, Giáo trình mô hình toán kinh tế, Nhà xuất bản tài chính Hà Nội, 2002. [4]. Trần Túc, Quy hoạch tuyến tính, Đại học Kinh tế Quốc dân, 2001. [5]. Trần Vũ Thiệu, giáo trình tối ưu tuyến tính, Nhà xuất bản Đại học Quốc gia Hà Nội, 2004. - 126 -