Giáo trình Toán kinh tế (Phần 2)

- 56 - 
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 = m,1 ). 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 = n,1 ), 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). 
Giả thiết ai > 0, bj > 0, cij 0 ( n,1j,m,1i ) và Qba
n
1j
j
m
1i
i (bài toán 
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 = m,1 , j = n,1 ). 
Mọi trạm phát, phát hết hàng nên ta có: m,1i,ax i
n
1j
ij . 
 Mọi trạm thu, thu đủ hàng nên ta có: .n,1j,bx j
m
1i
ij 
 Nhƣ vậy tổng chi phí vận chuyển là: 
m
1i
n
1j
ijijxc , và đòi hỏi phải cực tiểu. 
 Khi đó mô hình toán học của bài toán sẽ là: 
- 57 - 
m n
ij ij
i 1 j 1
f (X) c x min (3.1) 
 )m,1i(,ax i
n
1j
ij (3.2) 
 )n,1j(,bx j
m
1i
ij (3.3) 
 xij 0 (i = m,1 , j = n,1 ). (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à: 
- 58 - 
1...00
...
0...01
0...10
...
...
...
...
1...00
...
0...01
0...10
1...00
...
0...01
0...10
1...11...0...000...00
............
0...00
0...00
...
...
1...11
0...00
0...00
1...11
A
n
m
 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 = m,1 . 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 = n,1j,m,1 , 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) 
(3.3) (3.4) với giả thiết ai > 0, bj > 0, cij 0 ( n,1j,m,1i ); Qba
n
1j
j
m
1i
i đƣợc 
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: 
 +) 
m n
i j
i 1 j 1
a b : 
m n
ij ij
i 1 j 1
f (X) c x min 
n
ij i
j 1
x a ,(i 1,m) 
- 59 - 
 )n,1j(,bx j
m
1i
ij 
 xij 0 (i = m,1 , j = n,1 ). 
+) 
m n
i j
i 1 j 1
a b : 
m n
ij ij
i 1 j 1
f (X) c x min 
 )m,1i(,ax i
n
1j
ij 
m
ij j
i 1
x b ,( j 1,n) 
 xij 0 (i = m,1 , j = n,1 ). 
Đị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: 
 X = (x11 x12  x1n x21 x22  x2n  xm1 xm 2 xm n) 
c
, 
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: 
 minXC)X(f 
 BXA 
 0X 
- 60 - 
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 
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 
T 
P 
B1: b1 B2: b2  Bn: bn 
A1: a1 
c11 c12  
c1n 
A2: a2 
c21 c22  
c2n 
Am: am 
cm1 cm2  
cmn 
- 61 - 
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ó: 
- 62 - 
 0AA...AAA
1ppp222111
jijijijiji , 
đẳ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ó: 
 0A
K)j,i(
ijij , (3.6) 
với ít nhất một hệ số ij 0. Từ (3.6) ta có: 
 ij i m j
(i, j) K
(E E ) 0 (3.7) 
Giả sử 0
11
ji . Khi đó số hạng )EE(A
11111111
jmijijiji có hai thành phần 
thứ i1 và m + j 1 là 0
11
ji . Để làm triệt tiêu thành phần thứ i1 của số hạng 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ứ i1 khác không. 
Giả sử đó là số hạng thứ i1j2: 
2121
jiji A 0. Lại xuất hiện thành phần thứ m + 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 : 
2222
jiji A 0. Lại 
xuất hiện thành phần thứ i2 0 v.vVì 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 
1p1p
jiji A 0. Đồng thời với việc chọn các số hạng khác không thì ta đã 
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: 
- 63 - 
 Giả sử X = (xij) D, do cij 0, xij 0 i, j nên 0xc)x(f
m
1i
n
1j
ijij . Nhƣ 
vậy với mọi X D, hàm f(x) bị chặn dƣới trên D. 
Đặt n,1j;m,1i,
Q
ba
x
ji0
ij )Qba(
n
1j
j
m
1i
i . Đặt X0 = (x
0
ij)m.n. Khi đó ta có: 
n
0
ij i
j 1
x a ,i 1,m ; 
m
0
ij j
i 1
x b , j 1,n ; x
0
ij 0, i = m,1 , j = n,1 . 
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: 
 0D
nm
2i
ii . (3.8) 
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 đó 
từ (3.8) ta có 
nm
1mi
iji 0d , j 1,n ; mà dij = 1 nếu i = m + j; dij = 0 nếu i m + j. 
Do vậy n,1j,jmi,0i . Hay m + j = 0, j = n,1 . Khi đó ta có 
m
i i
i 2
(3.8) D 0 . 
 ( 2, 2, , 2, 3, 3, , 3, , m, m, , m) = 0. 
 k = 0, m,2k . 
 k = 0, nm,2k . 
Vậy m + n – 1 dòng sau của A độc lập tuyến tính, hay rankA = m + n – 1. 
- 64 - 
 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 
- 65 - 
 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 = m,1 , j = n,1 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 
1
iA thoả mãn, hàng i1 bị loại khỏi bảng, ô 
(i1, j2) không thể đƣợc phân phối. 
- Hoặc yêu cầu của trạm thu 
1
jB thoả mãn, hàng j1 bị loại khỏi bảng, ô (ik, j1) 
không thể đƣợc phân phối. 
 - Hoặc yêu cầu của cả trạm phát 
1
iA và trạm thu 
1
jB thoả mãn, khi đó hàng 
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. 
- 66 - 
Bảng 3.3 
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 
Nhƣ vậy, phƣơng án cực biên thu đƣợc là: 
5025030
355000
000200
030000
X0 . 
T 
P 
30 20 25 35 40 
30 13 7 6 2 12 
20 5 1 10 5 11 
40 10 5 3 7 14 
60 6 3 2 11 10 
T 
P 
30 
20 
25 
35 
40 
30 
13 7 6 2 12 
 30 
20 
5 1 10 5 11 
 20 
40 
10 5 3 7 14 
 5 35 
60 
6 3 2 11 10 
 30 25 5 
- 67 - 
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 
Phƣơng án cực biên tìm đƣợc theo phƣơng pháp Fogels: 
T 
P 
30 
20 
25 
35 
40 
30 
13 7 6 2 12 
4,4x 
 30 
20 
5 1 10 5 11 
4x 
 20 
40 
10 5 3 7 14 
2,4,3,7 
 5 35 
60 
6 3 2 11 10 
1,4,4,1 
 30 25 5 
1,4,4x 2x 1,1,1x 3,5,4,7x 1,2,4,4 
- 68 - 
0
0 0 0 30 0
0 20 0 0 0
X
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 : 
m n
ij ij
 ... 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 
- 114 - 
Ta có 
4
1
4
1
100 102,5 75 95
60
5 / 3 1 25 / 24 5 / 2
i
i
j
j
u
Z
v
. 
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. 
- 115 - 
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 
P 
S N 
S 1 -1 
N -1 1 
 Ma trận A = 
1 1
1 1
 đƣợc gọi là ma trận thu hoạch hay ma trận thắng 
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 
- 116 - 
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. 
- 117 - 
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 
của P là: a11x1 + a21x2 +  + am1xm = 
m
i1 i
i 1
a x . 
 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 
P là: a12x1 + a22x2 +  + am2xm = 
m
i2 i
i 1
a x . 
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 
là: a1nx1 + a2nx2 +  + amnxm = 
m
in i
i 1
a x . 
 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à: 
E(X, Y) = y1
m
i1 i
i 1
a x + y2
m
i2 i
i 1
a x +  + yn
m
in i
i 1
a x = 
n m
ij i j
j 1 i 1
a x y . 
Đị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) = 
n m
ij i j
j 1 i 1
a 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
- 118 - 
Xét cặp chiến lƣợc X = 
1 1 1
2 4 4
 và Y =
1 1 1 1
1 4 4 4
. Tính số thu 
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à: 3 1/ 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à 
ij
j
mina . 
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 
ij
j
mina 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à ij
ji
maxmina . 
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à ij
i
maxa . Nhƣ vậy Q sẽ cách chọn chiến lƣợc đơn làm cực tiểu số tổn 
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à ij
j i
minmaxa . 
Định nghĩa 4.7. Nếu ma trận trả tiền A thỏa mãn điều kiện: 
ij
ji
maxmina = ij
j i
minmaxa = 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. 
- 119 - 
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ó: 
1j
j
mina = a11 = a13 = 1, 2j
j
mina = a23 = 0, 3j
j
mina = a33 = 2 và 
ij
ji
maxmina = 2 = a33. 
i1
i
maxa = a21 = 5, i2
i
maxa = a22 = 4, i3
i
maxa = a33 = 2, i4
i
maxa = a34 = 3 và 
ij
j i
minmaxa = 2 = a33. 
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 
1 2 m 1 2 nX (x ,x ,...,x ),Y (y ,y ,..., y ) và số thực v, ký hiệu E( X , Y , v) sao cho: 
a. E( X , Y ) = v, 
b. E( X , j) v với mọi chiến lƣợc đơn j = 1, 2, , n, 
c. E(i, Y ) = v với mọi chiến lƣợc đơn i = 1, 2, , m. 
- 120 - 
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 X 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 Y 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ó 
X Y
maxmin E( X ,Y ) 
Y X
minmax E( X ,Y )= v. 
 Nhận xét: 1) Mọi trò chơi ma trận, với aij > 0, đều có nghiệm ( X , Y , v) thỏa mãn 
 E(X, Y ) ≤ E( X , Y ) = v ≤ E( X ,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}. 
 Ngƣời ta đã chứng minh đƣợc rằng các chiến lƣợc tối ƣu của cả hai trò chơi 
ứng với ma trận trả tiền A và Ap là nhƣ nhau, đồng thời vp = v + p > 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: 
- 121 - 
 Bảng 4.7 
Q 
P 
Giấy Búa Kéo 
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 đó X = Y 
và v = E(X , Y ) = 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à X = Y = (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), 
- 122 - 
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 
' i
i
x
x ,i 1,m
v
 và 
j'
j
y
y , j 1,n
v
. Ta có 
' ' '
1 2 m
1
x x ... x
v
 và ' ' '1 2 n
1
y y ... y
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: 
 ' ' '
1 1 2 mf x x ... x min 
' ' '
11 1 21 2 m1 m
' ' '
12 1 22 2 m2 m
' ' '
1n 1 2n 2 mn m
'
i
a x a x ... a x 1
a x a x ... a x 1
...
a x a x ... a x 1
x 0,i 1,m
Bài toán của Q: 
 ' ' '
2 1 2 nf y y ... y max 
' ' '
11 1 12 2 1n n
' ' '
21 1 22 2 2n n
' ' '
m1 1 m2 2 mn n
'
j
a y a y ... a y 1
a y a y ... a y 1
...
a y a y ... a y 1
y 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ó 
phƣơng án tối ƣu và 
m n
' '
i j
X ' Y '
i 1 j 1
1
min x max y
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). 
- 123 - 
 + Chiến lƣợc tối ƣu của P1 và P2 tƣơng ứng là: 
'
i ix v x ,i 1,n và 
'
j jy 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};Ap = (aij + p)mxn. 
 + Viết cặp bài toán quy hoạch tuyến tính đối ngẫu tƣơng ứng của P và Q. 
 + Giải một trong hai bài toán bằng phƣơng pháp đơn hình hoặc đơn hình đối 
ngẫu. Từ đó tìm phƣơng án tối ƣu cho bài toán còn lại. 
 + Từ các phƣơng án tối ƣu X’ = ( '
ix ) và Y’ = (
'
jy ) của cặp bài toán đối ngẫu 
ta tìm đƣợc chiến lƣợc tối ƣu X* = (xi) và Y* = (yj) của P và Q với 
'
i p ix v x ,i 1,n và 
'
j p jy v y , j 1,n , với vp = 1/f1; v* = vp - p 
Ví dụ 4.6: Tìm chiến lƣợc tối ƣu của trò chơi ma trận 
2 1 0
A 2 0 2
1 2 3
Ta thấy – min{ aij: aij < 0} = 3, vì thế chọn p = 4. Xét ma trận Ap nhƣ sau: 
 p
6 3 4
A 2 4 2
5 6 1
Mọi phần tử của Ap đều dƣơng nên vp > 0. Cặp bài toán đối ngẫu của P và Q 
là: 
(P) ' ' '
1 1 2 3f x x x min 
' ' '
1 2 3
' ' '
1 2 3
' ' '
1 2 3
' ' '
1 2 3
6x 2x 5x 1
3x 4x 6x 1
4x 2x x 1
x 0,x 0,x 0
- 124 - 
(Q) ' ' '
2 1 2 3f y y y max 
' ' '
1 2 3
' ' '
1 2 3
' ' '
1 2 3
' ' '
1 2 3
6y 3y 4y 1
2y 4y 2y 1
5y 6y y 1
y 0,y 0,y 0
Ta giải bài toán (Q). Đƣa bài toán (Q) về dạng chính tắc nhƣ sau: 
 ' ' '
2 1 2 3f y y y min 
' ' ' '
1 2 3 4
' ' ' '
1 2 3 5
' ' ' '
1 2 3 6
'
j
6y 3y 4y y 1
2y 4y 5y y 1
5y 6y y y 1
y 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 
Bảng 
Số 
Cơ sở 
Ai 
Hệ số 
ci 
Tọa 
độ 
xio 
-1 -1 -1 0 0 0 
A1 A2 A3 A4 A5 A6 
I 
 A4 0 1 6 3 4 1 0 0 
A5 0 1 2 4 2 0 1 0 
A6 0 1 5 6 1 0 0 1 
 f(X) = -10 1 1 1 0 0 0 
II 
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 
 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 
III 
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 
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 
- 125 - 
Tại bảng III ta thấy j 0, j = 6,1 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 
'
2
'
3
' ' '
1 2 3
y 0
y 0
2y 4y 2y 1
, 
nên theo định lý lệch bù ta có 
' ' '
1 2 3
' ' '
1 2 3
'
2
3x 4x 6x 1
4x 2x x 1
x 0
'
1
'
2
'
3
x 5 / 21
x 0
x 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. 
- 126 - 
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.