ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC VƯƠNG THỊ HUỆ CHI BÀI TOÁN BÙ TUYẾN TÍNH
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
3.2. Trò chơi song ma trận . . . . . . . . . . . . . . . . . . . 36
3.2.1. Trò chơi song ma trận . . . . . . . . . . . . . . . 36
3.2.2. Nghiệm trò chơi song ma trận . . . . . . . . . . . 39
Kết luận 40
Tài liệu tham khảo 41
2
Lời nói đầu
Bài toán bù tuyến tính (Linear Complementarity Problem, viết tắt là
LCP), do R. W. Cottle và G. B. Dantzig đề xuất năm 1968, là bài toán
tổng quát mô tả thống nhất các bài toán qui hoạch tuyến tính, qui hoạch
toàn phương và trò chơi song ma trận. Các nghiên cứu về bài toán bù
tuyến tính đã đem lại nhiều lợi ích, vượt ra ngoài khuôn khổ bài toán
bù. Chẳng hạn, thuật toán xoay bù (comple-mentarity pivot algorithm)
lúc đầu được đề xuất cho bài toán bù tuyến tính đã được mở rộng trực
tiếp để tạo ra các thuật toán hiệu quả tính điểm bất động Brouwer và
Kakutani, tính các trạng thái cân bằng kinh tế, giải các hệ phương trình
phi tuyến và tìm nghiệm tối ưu cho các bài toán qui hoạch phi tuyến.
Bài toán bù tuyến tính là bài toán tìm véctơ z ∈ R
n
nghiệm đúng hệ
z ≥ 0, q + Mz ≥ 0, z
T
(q + Mz) = 0
hoặc chỉ rõ hệ trên vô nghiệm, với véctơ q ∈ R
n
và ma trận M ∈ R
n×n
cho trước. Ký hiệu bài toán này là LCP (q, M) hay đơn giản là LCP nếu
không cần chỉ rõ q và M (
T

mô hình trò chơi thường gặp trong các ứng dụng của bài toán bù tuyến
tính: trò chơi Stackelberg và trò chơi song ma trận. Trò chơi Stackelberg
liên quan chặt chẽ với bài toán qui hoạch toán học với ràng buộc cân
bằng (MPEC) và là sự mở rộng ý tưởng của trò chơi Nash. Có thể tìm
nghiệm cân bằng Nash của trò chơi song ma trận nhờ lập và giải một
bài toán bù tuyến tính thích hợp.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này
còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn
đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này.
Nhân dịp này tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.
TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm Luận
văn. Tác giả trân trọng cảm ơn các giảng viên Trường Đại học Khoa học
– Đại học Thái Nguyên, Viện Toán học – Viện Hàn lâm Khoa học và
Công nghệ Việt Nam tạo mọi điều kiện thuận lợi trong quá trình tác giả
học tập và nghiên cứu.
Thái Nguyên, tháng 3 năm 2014
Tác giả
Vương Thị Huệ Chi
4
Chương 1
Bài toán bù tuyến tính
Chương này trình bày các khái niệm cơ bản về bài toán bù tuyến
tính, nguồn gốc bài toán và sự tồn tại duy nhất nghiệm của bài toán.
Bài toán bù có nhiều ứng dụng và liên quan chặt chẽ với một số bài toán
dạng tổng quát hơn, hiện đang rất được quan tâm nghiên cứu, đó là bài
toán bất đẳng thức biến phân và bài toán qui hoạch toán học với ràng
buộc cân bằng, vì thế trong chương sẽ giới thiệu về hai bài toán này. Nội
dung của chương được tham khảo từ các tài liệu [3], [4], [6] và [7].
1.1. Bài toán bù tuyến tính (LCP)
1.1.1. Mô tả bài toán

chấp nhận được chặt). Tập tất cả các véctơ chấp nhận được của bài toán
LCP (q, M) gọi là miền chấp nhận được và ký hiệu là FEA (q, M). Đặt
w = q + Mz (1.4)
Véctơ chấp nhận được z của LCP (q, M) thỏa mãn (1.3) khi và chỉ
khi
z
i
w
i
= 0 với mọi i = 1, 2, , n. (1.5)
Điều kiện (1.5) thường được dùng thay cho điều kiện (1.3). z
i
và w
i
gọi là một cặp bù và chúng được gọi là bù nhau. Véctơ z thỏa mãn (1.5)
được gọi là các véctơ bù. Vì thế, LCP là bài toán tìm véctơ chấp nhận
được và bù. Một véctơ như thế gọi là một nghiệm (solution) của LCP.
Bài toán LCP (q, M) gọi là giải được (solvable) nếu nó có nghiệm. Ký
hiệu tập nghiệm của LCP (q, M) là SOL (q, M). Chú ý là nếu q ≥ 0 thì
LCP (q, M) luôn giải được với véctơ 0 là nghiệm tầm thường.
Cách xác định w như trên thường được dùng để diễn đạt theo cách
khác của bài toán LCP (q, M), thuận tiện hơn cho xây dựng các thuật
toán giải. Cụ thể là bài toán tìm các véctơ không âm w và z trong R
n
thỏa mãn (1.4) và (1.5). Để tiện cho trích dẫn về sau, ta viết lại các điều
kiện (1.1) - (1.4) của bài toán LCP dưới dạng
w ≥ 0, z ≥ 0,
w = q + Mz,
z
T

(tức là x ∈
K ⇒ λx ∈ K với mọi số λ ≥ 0) và hàm F : K → R
n
. Bài toán bù, ký
hiệu là CP (K, F ), là bài toán tìm một véctơ z ∈ R
n
thỏa mãn các điều
kiện:
K  z⊥F (z) ∈ K
∗
7
trong đó ⊥ là ký hiệu "vuông góc" và K
∗
là nón đối ngẫu (dual cone)
của K được xác định bởi
K
∗
=

d ∈ R
n
: z
T
d ≥ 0 với mọi z ∈ K

,
tức là K
∗
gồm tất cả các véctơ không tạo thành góc tù với bất kỳ véctơ
nào trong K.

quả, có tính chất kiến thiết, để tính toán nghiệm cân bằng. Bài toán bù
tuyến tính có nhiều ứng dụng phong phú và đa dạng. Trong mục này ta
sẽ mô tả một số ứng dụng cổ điển này và trong mỗi ứng dụng sẽ chỉ ra
một số tính chất đặc biệt của ma trận M trong bài toán LCP tương ứng.
8
• Qui hoạch toàn phương
Xét bài toán qui hoạch toàn phương (Quadratic Program, viết tắt là
QP)
f(x) = c
T
x +
1
2
x
T
Qx → min
với các điều kiện
Ax ≥ b, x ≥ 0,
trong đó Q ∈ R
n×n
đối xứng, c ∈ R
n
, A ∈ R
m×n
và b ∈ R
m
. Trường
hợp Q = 0 ta nhận được bài toán qui hoạch tuyến tính (Linear Program,
viết tắt là LP). Nếu x là một nghiệm tối ưu địa phương của bài toán
QP thì tồn tại véctơ y ∈ R

nếu sau khi hoán vị một tập như nhau các hàng và cột, có thể đưa ma
trận về dạng
N =

G −A
T
A H

với G và H đối xứng. Nếu Q nửa xác định dương như trong qui hoạch
toàn phương lồi thì M là một ma trận song đối xứng. (Nhớ rằng ma trận
vuông Q là nửa xác định dương nếu z
T
Qz ≥ 0 với mọi véctơ z).
Một trường hợp riêng quan trọng của bài toán toàn phương QP là
khi nó chỉ có các ràng buộc về dấu đối với các biến x. Khi đó, bài toán
9
QP có dạng đơn giản
f(x) = c
T
x + x
T
Qx → min
với điều kiện
x ≥ 0.
Nếu Q nửa xác định dương thì bài toán dạng đơn giản này hoàn toàn
tương đương với bài toán LCP (c, Q). Có nhiều ứng dụng trong công
nghiệp và vật lý dẫn tới mô hình qui hoạch toàn phương lồi dạng đặc
biệt trên mà ta vừa chỉ ra là tương đương với bài toán bù tuyến tính
LCP (c, Q). Các ứng dụng đó bao gồm bài toán tiếp xúc, bài toán chất
lỏng nhớt, bài toán vật cản, bài toán xoắn chất dẻo đàn hồi cũng như

x
i
biểu thị xác suất chọn chiến lược đơn i, tức là x ≥ 0 và

m
i=1
x
i
= 1.
Chiến lược hỗn hợp của người chơi II được định nghĩa tương tự. Do đó,
nếu x và y là cặp chiến lược hỗn hợp tương ứng của người chơi I và II
10
thì chi phí kỳ vọng (trung bình) của họ lần lượt được tính bởi x
T
Ay
và x
T
By. Cặp chiến lược (x
∗
, y
∗
) với x
∗
∈ R
m
, y
∗
∈ R
n
được gọi là một


j=1
y
j
= 1.
Nói cách khác, cặp chiến lược (x
∗
, y
∗
) là nghiệm cân bằng Nash nếu
không người chơi nào được lợi hơn (theo nghĩa chi phí trung bình thấp
hơn) khi đơn phương thay đổi chiến lược của mình. Kết quả cơ bản trong
lý thuyết trò chơi khẳng định rằng một nghiệm cân bằng Nash như thế
luôn tồn tại.
Để đưa mô hình trò chơi G(A, B) về bài toán bù tuyến tính ta giả
thiết A và B là hai ma trận dương (theo mọi phần tử). Giả thiết này
hoàn toàn hợp lý, bởi vì bằng cách thêm vào mỗi phần tử a
ij
và b
ij
cùng
một số dương đủ lớn sẽ làm chúng trở thành số dương và biến đổi này
không hề ảnh hưởng gì đến nghiệm cân bằng. Sau đó, ta xét bài toán bù
LCP
u = −e
m
+ Ay ≥ 0, x ≥ 0, x
T
u = 0, (1.8)
v = −e

(x
∗
)
T
By
∗
và y

=
y
∗
(x
∗
)
T
Ay
∗
(1.10)
Ngược lại, rõ ràng là nếu (x

, y

) là một nghiệm của (1.8) - (1.9) thì
x

và y

phải khác không. Vậy (x
∗
, y

ma trận M xác định bài toán LCP với các điều kiện (1.8) - (1.9) được
cho bởi
q =

−e
m
−e
n

và M =

0 A
B
T
0

Trong bài toán LCP (q, M) này ma trận M không âm, có cấu trúc và
véctơ q khá đặc biệt.
• Cân bằng thị trường
Cân bằng thị trường (Market Equilibrium) là trạng thái của nền kinh
tế trong đó nhu cầu của người tiêu dùng và khả năng cung cấp của người
sản xuất cân bằng nhau theo mức giá hiện hành. Ta hãy xét một bài
toán cân bằng thị trường cụ thể mà ở đó véctơ cung được mô tả bởi
một mô hình qui hoạch tuyến tính để thu hút các đặc điểm kỹ thuật hay
công nghệ trong hoạt động sản xuất. Hàm nhu cầu thị trường được sinh
ra bởi mô hình kinh tế lượng với giá cả hàng hóa xem như các biến độc
lập chính. Về mặt toán học, mô hình cân bằng thị trường là tìm véctơ
giá p
∗
và véctơ nhu cầu tiêu dùng r

(iii) điều kiện cân bằng:
p
∗
= π
∗
, (1.14)
12
với π
∗
là véctơ đối ngẫu (hay véctơ giá bóng - shadow prices, tức là giá
cung trên thị trường) tương ứng với ràng buộc (1.12).
Để đưa mô hình trên về bài toán bù tuyến tính, ta chú ý rằng véctơ
x
∗
là một nghiệm tối ưu của bài toán qui hoạch tuyến tính về cung khi
và chỉ khi tồn tại véctơ v
∗
sao cho
y
∗
= c − A
T
v
∗
− B
T
π
∗
≥ 0, x
∗

)
T
π
∗
= 0,
(1.15)
Thay thế hàm nhu cầu (1.13) của r
∗
và dùng điều kiện cân bằng
(1.14), ta kết luận rằng các điều kiện (1.15) tạo nên bài toán bù tuyến
tính LCP (q, M) với
q =


c
−b
−d


và M =


0 −A
T
−B
T
A 0 0
B 0 −D



gồm lớp bài toán rộng hơn bài toán bù tuyến tính LCP. Cách phát biểu
13
toán học của bài toán bất đẳng thức biến phân như sau.
Định nghĩa 1.3 ([4], tr. 2). Tìm véctơ z ∈ K ⊂ R
n
sao cho
(y −z)
T
F (z) ≥ 0 với mọi y ∈ K, (1.18)
trong đó K là một tập lồi đóng và F là một hàm liên tục từ K vào R
n
cho trước.
Ta dùng ký hiệu VI (K, F ) để chỉ bài toán bất đẳng thức biến phân
nêu trên. Có thể giải thích ý nghĩa hình học của bài toán bất đẳng thức
biến phân, hay chính xác hơn của các bất đẳng thức (1.18) như sau.
Điểm z ∈ K là một nghiệm của bài toán VI (K, F ) khi và chỉ khi F (z)
không tạo nên một góc tù với mọi véc tơ có dạng y − z với y ∈ K. Ta
hình thức hóa nhận xét này nhờ dùng khái niệm nón pháp tuyến (normal
cone). Cụ thể, với mỗi tập lồi đóng K và bất kỳ véctơ z
0
∈ K, ta định
nghĩa nón pháp tuyến (ngoài) của K tại z
0
là tập
N
K
(z
0
) =


T
F (z) ≤ 0 có thể diễn đạt nhờ toán tử bù như sau:
0 ≤ z⊥F (z) ≥ 0.
Đó là ràng buộc bù của bài toán LCP. Định lý sau cho thấy rằng bài
toán LCP (q, M) và bài toán VI (R
+
, q + Mz) có nghiệm như nhau.
Định lý 1.1 ([7], tr. 7). Cho F = q + Mz với q ∈ R
n
, M ∈ R
n×n
và
z ∈ R
n
+
. Khi đó, bài toán bất đẳng thức biến phân VI (R
n
+
, q + Mz) và
bài toán bù tuyến tính LCP (q, M) có tập nghiệm trùng nhau hoặc cùng
vô nghiệm.
Chứng minh. Giả sử z là một nghiệm của bài toán VI (R
n
+
, F ), tức
là z ∈ R
n
+
và (y − z)
T

k
= 0 với mọi k = i và y
i
→ +∞ sẽ dẫn
tới mâu thuẫn), nghĩa là z là một nghiệm của bài toán LCP (q, M).
Ngược lại, giả sử z là một nghiệm của bài toán LCP (q, M), tức là
z ≥ 0, F (z) = Mz + q ≥ 0 và z
T
F (z) = 0. Từ đó suy ra (y −z)
T
F (z) =
y
T
F (z) ≥ 0 với mọi y ∈ R
n
+
(do y ≥ 0 và F(z) ≥ 0), tức z cũng là một
nghiệm của bài toán VI (R
n
+
, F ). 
Có thể mở rộng định lý trên cho bài toán bù CP ở dạng tổng quát
(xem Định nghĩa 1.2). Mối liên hệ giữa bài toán bất đẳng thức biến phân
VI (K, F) và bài toán bù CP (K, F) với K là một nón được nêu trong
kết quả cơ bản sau.
Định lý 1.2 ([4], tr. 4). Cho K là một nón trong R
n
. Véctơ z là một
nghiệm của bài toán VI (K, F ) khi và chỉ khi z là một nghiệm của bài
toán CP (K, F ).

là z ∈ K, F (z) ∈ K
∗
và z
T
F (z) = 0. Từ đó suy ra (y − z)
T
F (z) =
y
T
F (z) ≥ 0 với mọi y ∈ K (do y ∈ K và F (z) ∈ K
∗
), tức z cũng là một
nghiệm của bài toán VI (K, F). 
1.2.2. Bài toán qui hoạch toán học với ràng buộc cân bằng
Qui hoạch toán học với ràng buộc cân bằng (Mathematical Programs
with Equilibrium Constrains, viết tắt là MPEC) là một hướng nghiên
cứu hoàn toàn mới và là hướng mở rộng của tối ưu hai cấp (Bilevel
Programming, viết tắt là BP). Các ràng buộc cân bằng thường được
biểu thị dưới dạng một hệ bù hay một bất đẳng thức biến phân, trong
đó dạng đầu là trường hợp riêng của dạng sau. MPEC có phạm vi ứng
dụng rộng rãi, chẳng hạn trong kinh tế và trong nghiên cứu thị trường
điện năng. Các khái niệm của MPEC bắt nguồn từ các khái niệm kinh
tế trong trò chơi Stackelberg. Trò chơi Stackelberg và trò chơi song ma
trận sẽ được đề cập chi tiết hơn ở Chương cuối của luận văn.
MPEC là bài toán tối ưu được phân thành hai cấp. Bài toán này
đôi khi còn gọi là bài toán qui hoạch toán học với các ràng buộc bù
(Mathematical Programs with Complementarity Constraints, viết tắt là
MPCC), do các ràng buộc cân bằng được mô tả bởi một hệ bù. Các ràng
buộc bù lại có thể phân chia thành các bài toán bù hỗn hợp (viết tắt là
MCP) và bài toán bù tuyến tính tổng quát (viết tắt là GLCP). Bài toán

, C(x)
là một tập con lồi đóng (có thể rỗng) trong R
m
.Tập các véctơ x ∈ R
n
với C(x) = Ø gọi là miền hữu dụng (domain) của C và được ký hiệu là
dom (C). Giả sử X là hình chiếu của Z trên R
n
, tức là
X = {x ∈ R
n
: ∃y ∈ R
m
sao cho (x, y) ∈ Z}.
Hàm f là hàm mục tiêu toàn thể cần tìm cực tiểu, F là hàm cân bằng
của bài toán bên trong (ở mức dưới), Z là miền chấp nhận được đối với
các cặp (x, y) của bài toán ở mức trên. Tập C(x) xác định các giá trị y
chấp nhận được đối với mỗi x ∈ X cho trước. Ta giả thiết X ⊆ dom(C).
Với các định nghĩa trên, dạng tổng quát của bài toán qui hoạch toán học
với ràng buộc cân bằng MPEC như sau:
min
x,y
f(x, y)
với các điều kiện
(x, y) ∈ Z,
y ∈ S(x),
trong đó với mỗi x ∈ X, S(x) là tập nghiệm của bất đẳng thức biến
phân (VI) được xác định bởi cặp (F (x, •), C(x)), tức là y ∈ S(x) khi và
chỉ khi y ∈ C(x) và y thỏa mãn hệ bất đẳng thức
(z − y)

2
i
= 0 và ngược lại. Các bài toán MPEC này lại có thể
biến đổi thành bài toán qui hoạch phi tuyến (Nonlinear Programming,
viết tắt là NLP) bằng cách thay ràng buộc bù 0 ≤ x
1
⊥x
2
≥ 0 bởi ràng
buộc X
1
x
2
≤ 0, trong đó X
1
= diag(x
1
). Cách làm này cho phép diễn
đạt bài toán MPEC như một bài toán qui hoạch phi tuyến
min
x
f(x)
với điều kiện
c(x) ≥ 0, (1.19)
x
1
, x
2
≥ 0,
X

P-ma trận.
Định nghĩa 1.5 (P-ma trận). Ma trận vuông thực M gọi là một
P-ma trận nếu
z
i
(Mz)
i
> 0, i = 1, , n
với mọi 0 = z ∈ R
n
.
Có thể chứng minh được rằng LCP (q, M) có ít nhất một nghiệm với
mọi véctơ thực q nếu M là một P-ma trận và mọi tử thức con chính của
M là số dương.
Định lý 1.3 ([7], tr. 8). Cho M ∈ R
m×m
là một P-ma trận với mọi
tử thức con chính là số dương. Khi đó, bài toán LCP (q, M) có nghiệm
với mọi véctơ q ∈ R
m
Như đã nói ở trên, một số kết quả chính về sự tồn tại và duy nhất
nghiệm liên quan chặt chẽ với tính đơn điệu của bài toán. Có nhiều kiểu
đơn điệu khác nhau và chúng có vai trò quan trọng đối với sự tồn tại
nghiệm của bài toán LCP và bài toán VI. Trong luận văn này tính đơn
điệu được định nghĩa như sau.
Định nghĩa 1.6 (Tính đơn điệu). Một ánh xạ F : K ⊆ R
m
→ R
m
gọi là

tử.
Sự tồn tại nghiệm được đảm bảo khi q không âm. Sự kiện này sẽ được
sử dụng trong phương pháp Lemke trình bày ở chương sau.
Định lý 1.5. ([7], tr. 9). Nếu q không âm thì bài toán LCP (q, M)
luôn giải được với z = 0 là nghiệm tầm thường.
Chứng minh. Chỉ cần đặt z = 0 và kiểm tra lại rằng các ràng buộc
trong Định nghĩa 1.1 về bài toán bù tuyến tính LCP được thoả mãn với
mọi q ≥ 0. 
Tóm lại, chương này đã đề cập tới ba bài toán tối ưu trong không gian
hữu hạn chiều, liên quan chặt chẽ với nhau: bài toán bù tuyến tính LCP
(q, M) (bù phi tuyến CP (K, F)), bài toán bất đẳng thức biến phân VI
(K, F) và bài toán qui hoạch toán học với ràng buộc cân bằng MPEC.
Bài toán bù tuyến tính (bù phi tuyến) là trường hợp riêng của bài toán
bất đẳng thức biến phân khi nón K = R
n
+
và F (z) = q + Mz(K ⊆ R
n
+
)).
20
Các ràng buộc cân bằng trong bài toán MPEC thường được biểu thị
dưới dạng một hệ bù hay một bất đẳng thức biến phân. Bài toán MPEC
có thể xem như mở rộng của bài toán tối ưu hai cấp BP. Bài toán bù
tuyến tính LCP (q, M) có nhiều ứng dụng trong lý thuyết và thực tiễn,
như trong qui hoạch toàn phương, trò chơi song ma trận, cân bằng thị
trường và trong nhiều bài toán kinh tế, công nghiệp và vật lý khác.
21
Chương 2
Phương pháp giải bài toán bù tuyến

lại (tức là có q
i
< 0 với i nào đó), ta thêm vào một biến giả z
0
và xét bài
toán bù suy rộng:
w −Mz −ez
0
= q, (2.3)
z
0
≥ 0, z
j
≥ 0, w
j
≥ 0, j = 1, , n, (2.4)
z
j
w
j
= 0 với mọi j = 1, , n. (2.5)
trong đó e ∈ R
n
là véctơ với mọi thành phần bằng 1. Ta gọi (2.4) là điều
kiện không âm và (2.5) là điều kiện bù.
22
Ý tưởng phương pháp Lemke: Bằng cách đặt z
0
=
max {−q

sẽ được đưa vào cơ sở và trở thành biến cơ sở mới để thay thế cho một
biến cơ sở bị đưa ra khỏi cơ sở và sẽ trở thành biến phi cơ sở mới. Khi
một biến cơ sở và một biến phi cơ sở đổi chỗ cho nhau thì hệ phương
trình sẽ được biến đổi theo sao cho tập biến cơ sở mới được biểu diễn
qua tập biến phi cơ sở mới.
Định nghĩa 2.1. Ta nói (z
0
, z, w) ∈ R
1+2n
là một nghiệm chấp nhận
được cơ sở gần bù (almost complementary basic feasible solution) của
hệ (2.3) - (2.5) nếu
(a) (z
0
, z, w) là một nghiệm chấp nhận được cơ sở của hệ (2.3) - (2.4),
(b) có chỉ số s ∈ {1, , n} sao cho cả hai biến z
s
và w
s
đều là biến
phi cơ sở,
(c) z
0
là biến cơ sở và có đúng một biên trong mỗi cặp bù nhau (z
j
, w
j
)
23
là biến cơ sở với mọi j = 1, , n và j = s.

chấp nhận được cơ sở gần bù kề nhau cho đến khi đạt tới nghiệm chấp
nhận được cơ sở bù hoặc đến khi gặp một tia (vô hạn) của miền xác
định bởi (2.3) - (2.5). Với những giả thiết nhất định về ma trận M, thuật
toán Lemke sẽ hội tụ sau hữu hạn bước tới một nghiệm chấp nhận được
cơ sở bù của bài toán LCP (q, M).
Thuật toán Lemke giải bài toán LCP (q, M) gồm các thủ tục sau.
Khởi sự. Nếu q ≥ 0 thì dừng thuật toán: (z, w) = (0, q) là nghiệm
chấp nhận được cơ sở bù của LCP (q, M). Trái lại, ghi các hệ số của
hệ phương trình xác định theo (2.3) vào một bảng chữ nhật (như bảng
đơn hình). Giả sử −q
s
= max {−q
i
: i = 1, , n} > 0. Áp dụng "qui tắc
hình chữ nhật" và biến đổi bảng theo dòng s và cột z
0
. Phần tử nằm ở
dòng s và cột z
0
gọi là phần tử trụ và phép biến đổi bảng như vậy gọi
là phép xoay theo trụ (w
s
, z
0
). Như vậy, các biến cơ sở z
0
và w
j
với mọi
j = 1, , n, j = s đều không âm. Đặt y


Nếu biến cơ sở ở hàng r là z
0
thì chuyển sang Bước 3. Trái lại, chuyển
24
sang Bước 2.
Bước 2. Giả sử biến cơ sở ở hàng r là z
h
hoặc w
h
với chỉ số h nào đó
khác s. Đưa biến y
s
vào cơ sở và biến đổi bảng theo phần tử trụ ở hàng
r và cột y
s
. Nếu biến w
h
bị loại khỏi cơ sở thì đặt y
s
= z
h
, còn nếu biến
z
h
bị loại khỏi cơ sở thì đặt y
s
= w
h
. Quay lại thực hiện Bước 1.

- 663).
Ví dụ 2.1 (Dừng ở nghiệm chấp nhận được cơ sở bù). Tìm nghiệm
của bài toán bù tuyến tính LCP (q, M) với
q =




2
2
−2
−6




, M =




0 0 −1 −1
0 0 1 −2
1 −1 2 −2
1 2 −2 4




Khởi sự. Đưa vào biến giả z