TẠP CHÍ KHOA HỌC, Đại học Huế, Số 53, 2009
HỆ PHÂN HOẠCH HOÀN TOÀN KHÔNG GIAN RN
Huỳnh Thế Phùng
Trường Đại học Khoa học, Đại học Huế
TÓM TẮT
Một phân hoạch hoàn toàn của Rnlà một hệ gồm 2nvec-tơ
U=u1,0, u1,1, u2,0, u2,1,· · · , un,0, un,1⊆Rn
sao cho, với mọi x∈Rntồn tại duy nhất vec-tơ λthoả mãn
λ= (λ1,0, λ1,1,· · · , λn,0, λn,1)T∈R2n,
λi,s ≥0,(i, s)∈I×S,
λi,0.λi,1= 0, i ∈I,
x=X
(i,s)∈I×S
λi,sui,s
ở đây I:= {1,2,· · · , n}, và S:= {0,1}.
Những hệ vec-tơ như vậy thường gặp trong bài toán bù tuyến tính và việc nghiên cứu chúng
có thể mang lại một công cụ nghiên cứu hiệu quả bài toán bù. Trong bài này chúng tôi sẽ thiết
lập một đặc trưng cơ bản của hệ phân hoạch không gian Rnvà một vài ứng dụng trực tiếp của
nó trong việc khảo sát số nghiệm của bài toán bù.
1 Mở đầu
Cho Ulà một hệ gồm 2nvec-tơ trong không gian Rn:
U=u1,0, u1,1, u2,0, u2,1,· · · , un,0, un,1.(1.1)
Để thuận tiện ta cũng xem Unhư một ma trận thực cấp n×2n.Uđược gọi là một phân
hoạch hoàn toàn cuả không gian nếu với mọi x∈Rntồn tại duy nhất một vec-tơ λthoả mãn
λ= (λ1,0, λ1,1,· · · , λn,0, λn,1)T∈R2n,
λi,s ≥0,(i, s)∈I×S,
λi,0.λi,1= 0, i ∈I,
x=Uλ =P(i,s)∈I×Sλi,sui,s,
(1.2)
ở đây I:= {1,2,· · · , n}, và S:= {0,1}. Lúc đó ta nói xđược biểu diễn dưới dạng một tổ hợp
bù của U. Vậy Ulà một phân hoạch hoàn toàn của không gian nếu mọi vec-tơ x∈Rnđều
được biểu diễn một cách duy nhất dưới dạng tổ hợp bù của U.
65
Với mỗi tập con αcủa Ita thiết lập ma trận U(α)∈Rn×n, gọi là ma trận bù của Utương
ứng với α, mà vec-tơ cột thứ icủa nó được xác định bởi
U(α)i=(ui,0, i ∈α,
ui,1, i ∈I\α. (1.3)
Ký hiệu M(U) = {U(α)|α⊆I}. Rõ ràng, |M(U)|= 2n. Hai tập con αvà βcủa Iđược
gọi là kề nhau tại r∈Inếu (α∪β)\(α∩β) = {r}. Trong trường hợp đó ta cũng nói U(α)và
U(β)là kề nhau tại cột thứ r. Hiển nhiên lúc đó,
U(α)i=U(β)i, i ∈I\ {r},
{U(α)r, U(β)r}=ur,0, ur,1.
Kết quả chính của bài này là định lý sau
Định lý 1.1. Ba phát biểu sau là tương đương
a. Ulà một phân hoạch hoàn toàn của Rn,
b. Với mọi cặp ma trận bù U(α),U(β), ta có
det(U(α)).det(U(β)) <0.(1.4)
c. Với mọi λ= (λ1,0, λ1,1, λ2,0, λ2,1,· · · , λn,0, λn,1)T∈R2nthoả mãn
λi,0.λi,1≥0, λi,0+λi,16= 0, i ∈I, (1.5)
hệ
λi,0.ui,0−λi,1.ui,1|i∈I(1.6)
độc lập tuyến tính.
Chứng minh Định lý 1.1 sẽ được trình bày trong mục tiếp theo còn mục cuối cùng dành
cho việc nghiên cứu số nghiệm của bài toán bù tuyến tính bằng cách sử dụng đặc trưng của hệ
phân hoạch.
2 Chứng minh Định lý 1.1
Nhận xét 2.1.Nếu một trong các phát biểu của Định lý 1.1 thoả mãn thì U(α)không suy biến
với mọi α⊆I.
Chứng minh Định lý 1.1.
(a⇒b) Không mất tính tổng quát ta có thể giả sử rằng α={1,2,· · · , r −1}và β=
α∪ {r}. Như vậy
U(α)=[u1,0, u2,0,· · · , u(r−1),0, ur,1, u(r+1),1· · · , un,1];
66
U(β) = [u1,0, u2,0,· · · , u(r−1),0, ur,0, u(r+1),1,· · · , un,1].
Đặt t:= U(β)−1ur,1ta có
ur,1=U(β)t=
r
X
i=1
tiui,0+
n
X
j=r+1
tjuj,1.
Thay vế phải của đẳng thức trên vào cột thứ rcủa U(α)và tính định thức của ma trận
này ta nhận được
det(U(α)) = trdet(U(β)).
Vì U(α)không suy biến tr6= 0 và như vậy (1.4) tương đương với khẳng định tr<0. Giả
sử ngược lại rằng tr>0. Lúc đó ta đặt
x=
r−1
X
i=1
ui,0+εur,1+
n
X
j=r+1
uj,1(2.1)
=
r−1
X
i=1
(1 + εti)ui,0+εtrur,0+
n
X
j=r+1
(1 + εtj)uj,1.(2.2)
Với ε > 0đủ bé ta có 1 + εti>0với mọi i6=r. Nhưng lúc đó (2.1) và (2.2) cho ta hai
biểu diễn khác nhau của xdưới dạng tổ hợp bù của U, mâu thuẫn với giả thiết rằng Ulà một
phân hoạch hoàn toàn.
(b⇒c) Bằng quy nạp trên |α|ta có thể chứng minh được rằng
(−1)|α|.det(U(α)).det(U(∅)) >0, α ⊆I.
Suy ra,
(−1)|I\α|.det(U(α)).(−1)|I\β|.det(U(β)) >0, α, β ⊆I. (2.3)
Từ những tính chất đã biết của định thức ma trận ta dễ dàng kiểm chứng được rằng
det λ1,0u1,0−λ1,1u1,1, λ2,0u2,0−λ2,1u2,1,· · · , λn,0un,0−λn,1un,1
=X
α⊆IY
i∈α
λi,0 Y
j∈I\α
λj,1(−1)|I\α|det(U(α)).
Kết hợp (1.5) và (2.3) ta có thể khẳng định rằng tất cả các số hạng của tổng trên là cùng
dấu và hơn nữa, có ít nhất một số hạng là khác không. Vì vậy định thức của ma trận khác
không và do đó hệ (1.6) độc lập tuyến tính.
Trong suốt phần còn lại của mục này ta giả thiết phát biểu (c) là đúng. Việc chứng minh
(a) được thực hiện bởi một số bổ đề.
Bổ đề 2.1. Với mọi λ= (λi,s : (i, s)∈I×S)∈R2n, thoả mãn
n
X
i=1
(λi,0ui,0−λi,1ui,1) = 0 và λi,0.λi,1≥0, i ∈I, (2.4)
ta có λ= 0.
67
Chứng minh. Do λi,0.λi,1≥0với mọi i∈I, ta chỉ cần chỉ ra rằng tập hợp γ:= {i|λi,0+λi,16= 0}
là rỗng. Thật vậy, nếu γ6=∅thì từ (2.4) ta có
X
i∈γ
(λi,0ui,0−λi,1ui,1)=0.
Điều này là không thể vì {λi,0.ui,0−λi,1.ui,1|i∈γ}là một hệ con khác rỗng của (1.6).
Bổ đề 2.2. Với mọi λ= (λi,s : (i, s)∈I×S),µ= (µi,s : (i, s)∈I×S)∈R2nthoả mãn
λi,0.λi,1=µi,0.µi,1= 0, λi,s ≥0, µi,s ≥0; i∈I, s ∈S
và
X
(i,s)∈I×S
λi,sui,s =X
(i,s)∈I×S
µi,sui,s,
ta có λ=µ.
Chứng minh. Từ định nghĩa ta nhận được
n
X
i=1
[(λi,0−µi,0)ui,0−(µi,1−λi,1)ui,1] = 0,
và hơn nữa,
(λi,0−µi,0).(µi,1−λi,1) = λi,0.µi,1+λi,1.µi,0≥0; i∈I.
Từ Bổ đề 2.1 suy ra rằng λi,0−µi,0=λi,1−µi,1= 0 với mọi i∈I, tức là λ=µ.
Bây giờ lấy tuỳ ý x∈Rn. Do (c) thoả mãn, U(α)không suy biến với mọi α⊆I. Tương
ứng với một tập con như thế ta đặt yα:= U(α)−1x, tức là,
x=U(α)yα=X
i∈α
yα
iui,0+X
i∈I\α
yα
iui,1.
Ta định nghĩa tα= sgn(yα),vec-tơ dấu của yα, được xác định như sau
tα
i:= (1,nếu (yα
i>0) hoặc (yα
i= 0 và i∈α),
−1,nếu (yα
i<0) hoặc (yα
i= 0 và i∈I\α).
Bổ đề 2.3. Φ : P(I)→ {−1,1}nxác định bởi Φ(α) = tαlà ánh xạ song ánh, ở đây P(I)ký
hiệu tập tất cả các tập con của I.
Chứng minh. Vì |P(I)|=| {−1,1}n|= 2nta chỉ cần chứng minh Φlà đơn ánh.
Giả sử ngược lại rằng tồn tại các tập con khác nhau α, β ⊆Isao cho tα=tβ. Từ định
nghĩa của yαvà yβta có
X
i∈α
yα
iui,0+X
i∈I\α
yα
iui,1=x=X
i∈β
yβ
iui,0+X
i∈I\β
yβ
iui,1.
68
Từ đó suy ra
X
i∈α∩β
(yα
i−yβ
i)ui,0+X
i∈α\β
(yα
iui,0−yβ
iui,1) + X
i∈β\α
(−yβ
iui,0+yα
iui,1)
+X
i∈I\(α∪β)
(yα
i−yβ
i)ui,1= 0.
Mặt khác, từ tα=tβta có yα
iyβ
i≥0với mọi i∈I. Vậy theo Bổ đề 2.1, ta có yα
i−yβ
i= 0
với mọi i∈(α∩β)∪(I\(α∪β)) và yα
i=yβ
i= 0 với mọi i∈(α\β)∪(β\α).Vì α6=βtồn
tại, chẳng hạn, r∈α\β. Theo định nghĩa của vec-tơ dấu ta có tα
r= 1 và tβ
r=−1, điều này là
mâu thuẫn.
Bây giờ ta chứng minh khẳng định (a). Với mọi x∈Rn, ta chứng minh rằng có duy nhất
một vec-tơ λthoả mãn
x=X
(i,s)
λi,sui,s với λi,s ≥0, λi,0.λi,1= 0,(i, s)∈I×S. (2.5)
Thật vậy, theo Bổ đề 2.3 tồn tại α⊆Isao cho tα= sgn(yα) = (1,1,· · · ,1).Như vậy
yα
i≥0với mọi i∈Ivà vec-tơ λxác định bởi
λi,0=(yα
i,nếu i∈α,
0,nếu i∈I\α, λi,1=(0,nếu i∈α,
yα
i,nếu i∈I\α,
thoả mãn (2.5). Cuối cùng, tính duy nhất của λđược suy ra từ Bổ đề 2.2 và định lý đã được
chứng minh hoàn toàn.
Nhận xét 2.2.Cho α⊆I, ta ký hiệu U−αlà ma trận nhận được từ Ubằng cách thay các vec-tơ
ui,0,ui,1lần lượt bởi −ui,0,−ui,1với mọi i∈α. Rõ ràng là nếu Uthoả mãn phát biểu (c) trong
Định lý 1.1 thì U−αcũng vậy. Do ba phát biểu là tương đương ta suy ra rằng U−αlà một phân
hoạch hoàn toàn khi và chỉ khi Ucũng có tính chất đó.
3 Số nghiệm bài toán bù tuyến tính
Trong mục này bằng cách sử dụng đặc trưng của hệ phân hoạch không gian được thiết lập
trong Định lý 1.1 ta sẽ thiết lập một vài kết quả mới về số nghiệm của bài toán bù tuyến tính.
Nhắc lại rằng với ma trận M∈Rn×nvà vec-tơ q∈RnBài toán bù tuyến tính LCP(M, q)là
tìm (x, z)∈Rn×Rnthoả mãn
x≥0, z ≥0,
xT.z = 0,
q=−Mx +z.
(3.1)
Tính thời sự cũng như vai trò quan trọng của bài toán này trong lý thuyết tối ưu được
chứng minh thông qua một khối lượng lớn các kết quả được công bố, và được kết tập trong
69