TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
*************

BÙI THỊ THÙY DƯƠNG

TẬP LỒI ĐA DIỆN
VÀ ỨNG DỤNG TRONG BẤT ĐẲNG
THỨC BIẾN PHÂN AFFINE

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học

HÀ NỘI – 2018


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
*************

BÙI THỊ THÙY DƯƠNG

TẬP LỒI ĐA DIỆN
VÀ ỨNG DỤNG TRONG BẤT ĐẲNG
THỨC BIẾN PHÂN AFFINE
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học

Người hướng dẫn khoa học
TS. TRẦN VĂN NGHỊ

HÀ NỘI – 2018


LỜI CẢM ƠN
Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng
cảm ơn tới các thầy cô khoa Toán, trường Đại Học Sư Phạm Hà Nội 2,
các thầy cô trong tổ bộ môn Hình học cũng như các thầy cô tham gia
giảng dạy đã tận tình truyền đạt những tri thức quý báu và tạo điều
kiện thuận lợi để em hoàn thành tốt nhiệm vụ khóa học và khóa luận.
Đặc biệt, em xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới TS.
Trần Văn Nghị, người đã tận tình hướng dẫn, chỉ bảo tận tình giúp đỡ
để em có thể hoàn thành khóa luận này.
Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia
đình, bạn bè đã luôn bên em, cổ vũ, động viên, giúp đỡ em trong suốt
quá trình học tập và thực hiện khóa luận tốt nghiệp.
Em xin chân thành cảm ơn.
Hà Nội, ngày...tháng...năm 2018
Sinh viên

Bùi Thị Thùy Dương


LỜI CAM ĐOAN
Khóa luận này được hoàn thành sau quá trình tự tìm hiểu, nghiên
cứu của bản thân và sự hướng dẫn của TS.Trần Văn Nghị.
Trong khóa luận này em có tham khảo các kết quả nghiên cứu của
các nhà khoa học trong và ngoài nước. Em xin cam đoan kết quả của
khóa luận này là không sao chép từ bất cứ khóa luận nào. Em xin chịu
hoàn toàn trách nhiệm về lời cam đoan của mình.
Hà Nội, ngày...tháng...năm 2018

Sinh viên

Bùi Thị Thùy Dương


Mục lục

Lời mở đầu

1

1 Tập lồi đa diện

3

1.1

Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Một số tính chất của tập lồi . . . . . . . . . . . . . . . .

6

1.3

Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . .


12

1.3.1

Khái niệm . . . . . . . . . . . . . . . . . . . . . .

12

1.3.2

Điểm cực biên . . . . . . . . . . . . . . . . . . . .

14

1.3.3

Phương vô tận . . . . . . . . . . . . . . . . . . .

17

1.3.4

Phương cực biên . . . . . . . . . . . . . . . . . .

18

1.3.5

Tập lồi đa diện không chứa đường thẳng . . . . .


19

2 Ứng dụng trong bất đẳng thức biến phân affine
2.1

2.2

22

Bài toán bất đẳng thức biến phân affine . . . . . . . . .

22

2.1.1

Bài toán bất đẳng thức biến phân . . . . . . . . .

22

2.1.2

Bài toán bất đẳng thức biến phân affine . . . . .

28

Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . .

35


2.2.1

Sự tồn tại nghiệm dưới điều kiện đơn điệu . . . .

35

2.2.2

Sự tồn tại nghiệm dưới điều kiện đồng dương . .

42

i


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Kết luận

47

Tài liệu tham khảo

48

ii



Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Tập lồi đa diện là một đối tượng quan trọng trong toán học. Các
nhà khoa học trên thế giới đã và đang nghiên cứu các tính chất của
tập lồi đa diện và các ứng dụng của nó trong toán học và thực tiễn.
Bài toán về bất đẳng thức biến phân affine là một lớp những bài
toán bất đẳng thức biến phân đặc biệt với miền ràng buộc là tập lồi
đa diện. Với mong muốn tìm hiếu sâu hơn về tập lồi đa diện cũng
như ứng dụng của tập lồi đa diện trong bài toán bất đẳng thức biến
phân affine em chọn đề tài "Tập lồi đa diện và ứng dụng trong bất
đẳng thức biến phân affine" làm đề tài khóa luận tốt nghiệp.
2. Mục đích nghiên cứu
- Bước đầu làm quen với việc nghiên cứu khoa học tìm hiểu sâu hơn
về tập lồi đa diện.
- Đưa ra được ứng dụng của tính lồi trong bài toán bất đẳng thức
biến phân affine.
3. Đối tượng và phạm vi nghiên cứu
- Đối tượng: Tập lồi đa diện.
- Phạm vi nghiên cứu: Ứng dụng của tập lồi đa diện trong bất đẳng
thức biến phân affine.
4. Nhiệm vụ nghiên cứu

1


Khóa luận tốt nghiệp Đại học


BÙI THỊ THÙY DƯƠNG

Trình bày cơ sở lý thuyết về tập lồi, tập lồi đa diện và đưa ra ứng
dụng trong sự tồn tại nghiệm của bất đẳng thức biến phân affine.
5. Phương pháp nghiên cứu
Phân tích và tổng hợp kiến thức.
6. Cấu trúc khóa luận
Khóa luận gồm 2 chương:
Chương 1: Tập lồi đa diện.
Chương 2: Ứng dụng trong bất đẳng thức biến phân affine.

2


Chương 1
Tập lồi đa diện
Nội dung chính của chương này đề cập đến tập lồi và tập lồi đa diện.
Tập lồi và các tính chất của tập lồi được trình bày trong các Mục 1.1 và
1.2. Khái niệm và các tính chất của tập lồi đa diện được trình bày trong
Mục 1.3.

1.1

Tập lồi

Định nghĩa 1.1.1. Tập A ⊂ Rn được gọi là tập lồi nếu
∀x1 , x2 ∈ A, ∀λ ∈ R, 0 ≤ λ ≤ 1 ⇒ λx1 + (1 − λ)x2 ∈ A.
Nhận xét 1.1.1. Tập ∅ là tập lồi.
Định nghĩa 1.1.2. Đoạn thẳng nối x1 , x2 là tập hợp có dạng như sau

[x1 , x2 ] := {x ∈ A : x = λx1 + (1 − λ)x2 , 0 ≤ λ ≤ 1 }.
Nhận xét 1.1.2. Tập A là lồi nếu ∀x1 , x2 ∈ A, ta có [x1 , x2 ] ⊂ A.

3


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Định nghĩa 1.1.3. Tập C ⊂ Rn được gọi là tập affine nếu
(1 − λ)x1 + λx2 ∈ C ∀x1 , x2 ∈ C, ∀λ ∈ R,
nghĩa là, nếu x1 , x2 ∈ C thì đường thẳng đi qua x1 , x2 cũng nằm trong
C.
Định nghĩa 1.1.4. Giao của tất cả các tập affine chứa C được gọi là
bao affine của C. Kí hiệu bao affine của C là af f C.
Ví dụ 1.1.1. Trong mặt phẳng, đoạn thẳng, hình tam giác, hình tròn
là các tập lồi. Trong không gian affin thực, m - phẳng là tập lồi. Hình
cầu đơn vị trong không gian Banach là tập lồi. Các nửa không gian là
các tập lồi.
Ví dụ 1.1.2. Mặt phẳng trong không gian là tập affine.
Định lí 1.1.1. Giao của bất kỳ họ các tập lồi là tập lồi.
Chứng minh. Giả sử Aα ⊂ Rn (α ∈ I) là các tập lồi, I là tập chỉ số bất
kỳ. Ta cần chứng minh A =

Aα cũng là tập lồi.
α∈I

Lấy x1 , x2 ∈ A. Khi đó x1 , x2 ∈ Aα (∀α ∈ I) . Với ∀α ∈ I do Aα lồi, nên
λx1 + (1 − λ)x2 ∈ Aα (∀λ ∈ [0, 1]).

⇒ λx1 + (1 − λ)x2 ∈ A.
Vậy A là tập lồi.
Định lí 1.1.2. Giả sử A ⊂ Rn lồi và x1 , x2 , . . . , xm ∈ A. Khi đó, A chứa
tất cả các tổ hợp lồi của x1 , x2 , . . . , xm .
4


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. Ta chứng minh bằng quy nạp.
m = 2 : Với mọi λ1 , λ2 > 0, λ1 + λ2 = 1, x1 , x2 ∈ A, theo Định nghĩa
1.1.1, λ1 x1 + λ2 x2 ∈ A. Giả sử kết luận đúng với m ≤ k, ta sẽ chứng
minh rằng:
k+1

∀x1 , x2 , . . . , xk+1 ∈ A, ∀λi ≥ 0, (i = 1, . . . , k + 1) ,

λi = 1,
i=1

x = λ1 x1 + λ2 x2 + . . . + λk xk + λk+1 xk+1 ∈ A.
Có thể xem như λk+1 < 1, bởi vì nếu λk+1 = 1 thì λ1 = λ2 = . . . = λk = 0
và ta có ngay x ∈ A. Khi đó,
1 − λk+1 = λ1 + . . . + λk > 0,
λi
≥ 0 (i = 1, . . . , k).
1 − λk+1
k


Vì

λi
= 1, nên theo giả thuyết quy nạp ta có
i=1 1 − λk+1
k

y=
i=1

λi xi
∈A
1 − λk+1

mà, 1 − λk+1 > 0, (1 − λk+1 ) + λk+1 = 1.
Do đó,
x = (1 − λk+1 )y + λk+1 xk+1 ∈ A.

Định nghĩa 1.1.5. Giả sử X ⊂ Rn . Giao của tất cả các tập lồi chứa X
được gọi là bao lồi của tập X. Kí hiệu bao lồi của X là convX.
Định lí 1.1.3. Cho X ⊂ Rn . Khi đó convX là tập lồi nhỏ nhất chứa X.
5


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. Do convX là giao của tất cả các tập lồi chứa X nên theo

Định lý 1.1.1, convX là tập lồi chứa X. Mặt khác, cho C là một tập lồi
bất kỳ chứa X, thì convX chứa trong C. Vậy convX trùng với tập lồi
nhỏ nhất chứa X.
Hệ quả 1.1.1. Bao lồi hữu hạn của các tập con {b0 , . . . , bm } ⊂ Rn
gồm tất cả các vectơ có dạng λ0 b0 + . . . + λm bm với λ0 ≥ 0, . . . , λm ≥
0, λ0 + . . . + λm = 1.
Định nghĩa 1.1.6. Một tập C đươc gọi là nón nếu
∀x ∈ C, ∀λ ≥ 0 ⇒ λx ∈ C.
Ví dụ 1.1.3.
C = {x ∈ R, x = 0}
là một nón.
Một nón được gọi là nón nhọn nếu nó không chứa đường thẳng, khi
đó ta nói 0 là đỉnh của nón. Một nón được gọi là nón lồi nếu nó đồng
thời là một tập lồi.
Ví dụ 1.1.4. a) Rn+ = {x ∈ Rn : x ≥ 0} là nón lồi.
b) Nón Loentz Ln = x ∈ Rn : xn ≥

1.2

x21 + ..... + x2n−1

là nón lồi.

Một số tính chất của tập lồi

Định lí 1.2.1. Nếu A và B là các tập lồi trong Rn thì tổng của chúng
A + B cũng là tập lồi, trong đó
A + B = {x1 + x2 : x1 ∈ A, x2 ∈ B}.
6



Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. Cho x và y là điểm trong A + B, khi đó tồn tại các vectơ
x1 và y1 trong A và x2 và y2 trong B sao cho

x = x1 + x2 , y = y1 + y2 .
Với 0 ≤ λ ≤ 1, ta có
(1 − λ)x + λy = [(1 − λ)x1 + λy1 ] + [ (1 − λ) x2 + λy2 ],
Mặt khác, A và B là lồi nên
(1 − λ)x1 + λy1 ∈ A, (1 − λ)x2 + λy2 ∈ B.
Do đó, (1 − λ)x + λy ∈ A + B.
Nhận xét 1.2.1. Nếu A, B là các tập lồi trong Rn và C là tập lồi trong
Rm thì các tập sau là lồi:
αA + βB := {x : x = αa + βb; a ∈ A, b ∈ B; α, β ∈ R};
A × C := {x ∈ Rm+n : x = (a, c); a ∈ A, c ∈ C}.
Nhận xét 1.2.2. Nếu A, B, C là các tập lồi trong Rn thì:
A + B = B + A;
(A + B) + C = A + (B + C);
λ1 (λ2 A) = (λ1 λ2 )A;
λ(A + B) = λA + λB;
(λ1 + λ2 )A = λ1 A + λ2 A.

7


Khóa luận tốt nghiệp Đại học


BÙI THỊ THÙY DƯƠNG

Định lí 1.2.2. Cho {Ci |i ∈ I} là tập gồm các tập lồi tùy ý khác rỗng
trong Rn và C là bao lồi. Khi đó

C=∪

λi Ci

,

i∈I

là hợp hữu hạn của các tổ hợp lồi.
Định lí 1.2.3. Cho T : Rn → Rm là một ánh xạ tuyến tính. Khi đó:
(i) A là lồi thì T (A) là lồi trong Rm ;
(ii) B là lồi thì T −1 (B) là lồi trong Rn .
Hệ quả 1.2.1. Phép chiếu vuông góc của một tập lồi A lên một không
gian con L cũng là một tập lồi.
Định lí 1.2.4. Cho các tập A ⊂ Rn , B ⊂ Rm là lồi và ánh xạ affine
f : Rn → Rm . Khi đó:
f (A) := { f (x) : x ∈ A}
và
f −1 (B) := { x ∈ Rn : f (x) ∈ B}
là các tập lồi.
Hệ quả 1.2.2. Hình chiếu của một tập lồi lên không gian affine con là
lồi.
Định lí 1.2.5. Cho A ⊂ Rn , ta có
k


k

αi xi : k ∈ N, x1 , . . . , xk ∈ A, α1 , . . . , αk ∈ [0, 1],

convA =
i=1

αi = 1 .
i=1

8


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. Kí hiệu B là tập bên phải. Giả sử C là một tập lồi chứa
A thì B ⊂ C nên B ⊂ convA. Mặt khác, B là tập lồi, do
β(α1 x1 + . . . + αk xk ) + (1 − β)(γ1 y1 + . . . + γm ym )
= βα1 x1 + . . . + βαk xk + (1 − β)γ1 y1 + . . . + (1 − β)γm ym
với xi , yi ∈ A và hệ số β, αi , γi ∈ [0, 1], α1 + . . . + αk = 1,γ1 + . . . + γk = 1
và βα1 + . . . + βαk + (1 − β)γ1 + . . . + (1 − β)γk = 1.
Vậy B là tập lồi chứa A, mà convA là tập lồi nhỏ nhất chứa A, suy ra
convA ⊂ B.
Nhận xét 1.2.3. A là lồi nếu và chỉ nếu A = convA.
Định nghĩa 1.2.1. a) Bao lồi của hữu hạn các điểm x1 , x2 , . . . , xk ∈ Rn
được gọi là một hình đa diện P .
b) Bao lồi của các điểm độc lập được gọi là 1 đơn hình, r-đơn hình là
bao lồi của r + 1 điểm độc lập.

Định nghĩa 1.2.2. Một điểm x thuộc hình đa diện P được gọi là một
đỉnh của P nếu x ∈
/ P \{x}. Tập tất cả các đỉnh của P ký hiệu là vertP .
Nhận xét 1.2.4. Mỗi đơn hình là một tập lồi.
Ví dụ 1.2.1. 1-đơn hình là đoạn thẳng, 2-đơn hình là tam giác, 3-đơn
hình là tứ diện
Định lí 1.2.6. Cho P là một hình đa diện trong Rn và x1 , x2 , . . . , xk ∈
Rn là các điểm phân biệt.
(i) Nếu P = conv {x1 , . . . , xk }, thì x1 là đỉnh của P nếu và chỉ nếu
x1 ∈
/ conv{x2, . . . , xk }.
(ii) P là bao lồi của các đỉnh đó.
9


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. (i) Giả sử x1 là đỉnh của P khi đó P \ {x1 } là lồi và x1 ∈
/
P \ {x1 }. Do đó, conv {x1 , . . . , xk } ⊂ P \ {x1 }, vì vậy x1 ∈
/ conv {x2 , . . . , xk }.
Ngược lại, giả sử rằng x1 ∈
/ conv {x2, . . . , xk }. Nếu x1 không là đỉnh
thì tồn tại 2 điểm phân biệt a, b ∈ P \ {x1 } và λ ∈ (0; 1) sao cho
x1 = (1−λ)a+λb. Nên ∃k ∈ N để µ1 , . . . , µk ∈ [0; 1] và τ1, . . . , τk ∈ [0; 1]
với µ1 + . . . + µk = 1 và τ1 + . . . + τk = 1
k


a=

sao cho µ1 , τ1 = 1 và

k

µi xi , b =
i=1

τi xi .
i=1

Vì vậy
k

((1 − λ)µi + λτi )xi ,

x1 =
i=1

suy ra
k

x1 =
i=2

(1 − λ)µi + λτi
xi ,
1 − (1 − λ)µ1 − λτ1


trong đó (1 − λ)µ1 + λτ1 = 1 và vế phải của đẳng thức trên và là một tổ
hợp lồi của x2 , . . . , xk . Mâu thuẫn.
(ii) Sử dụng (i), ta cũng có thể lấy lần lượt các điểm từ {x1 , . . . , xk }
sao cho chúng không phải là đỉnh của bao lồi khác. Hơn nữa, nếu x ∈
/
{x1 , . . . , xk } và x không phải là một đỉnh của P thì P = conv{x, x1 , . . . , xk }
tức là x ∈
/ conv{x1 , . . . , xk } = P. Mâu thuẫn.
Định lí 1.2.7. Cho x1 , x2 , . . . , xm ∈ Rn là các điểm độc lập affine. Khi
đó tồn tại một sự tách
{1, . . . , m} = I ∪ J, I ∩ J = ∅
sao cho
conv {xi : i ∈ I} ∩ conv {xj : j ∈ I} = ∅.

10


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Định lí 1.2.8. Cho X1 , X2 , . . . , Xm là các tập lồi trong Rn , trong đó
m > n. Nếu giao của một bộ n + 1 tập là khác rỗng, thì giao của tất cả
các tập đó khác rỗng, nghĩa là
m

Xj = ∅.
j=1

Định lí 1.2.9. Cho tập A ∈ Rn và x ∈ Rn thì các khẳng định sau đây

tương đương:
(i) x ∈ convA,
(ii) Có r-đơn hình (0 ≤ r ≤ n) P , nếu x ∈ P thì tập các đỉnh của P
chứa trong A.
Cho A là một tập hợp trong Rn , intA là phần trong của A, clA là
bao đóng của A.
Định lí 1.2.10. Cho A là một tập lồi trong Rn , khi đó intA và clA là
các tập lồi.
Chứng minh. Lấy x1 ∈ intA, x2 ∈ A. Khi đó, tồn tại lân cận U của x1
sao cho U ⊂ A.
Đặt x = λx1 + (1 − λ)x2 , (0 < λ ≤ 1), ta có λU + (1 − λ)x2 là một lân
cận của x và λU + (1 − λ)x2 ⊂ A, suy ra x ∈ intA. Do đó, intA lồi.
Bây giờ lấy x1 , x2 ∈ clA. Đặt x = λx1 + (1 − λ)x2 , (0 < λ < 1).
Giả sử U là một lân cận lồi của O.
Do xi ∈ clA nên
(xi + U ) ∩ A = ∅, (i = 1, 2) .
Suy ra,
∃xi ∈ (xi + U ) ∩ A, (i = 1, 2) .
11


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Đặt x = λx1 + (1 − λ)x2 . Khi đó,
x = λ(x1 + U ) + (1 − λ)(x2 + U )
Kéo theo (x + U ) ∩ A = ∅.
Suy ra x ∈ clA, dẫn đến clA lồi.


1.3
1.3.1

Tập lồi đa diện
Khái niệm

Định nghĩa 1.3.1. Tích vô hướng của 2 vectơ x, y ∈ Rn là số thực

x, y = x1 .y1 + x2 .y2 + . . . + xn .yn ,
với x = (x1 , x2 , . . . , xn ), y = (y1 , y2 , . . . , yn ) .
Định nghĩa 1.3.2. Tập hợp có thể quy về dạng {x ∈ Rn : a, x = b}
(a = 0, b ∈ R) được gọi siêu phẳng trong Rn .
Ví dụ 1.3.1. Trong R2 , tập (x, y) ∈ R2 : 2x − y = 3 (đường thẳng)
là một siêu phẳng. Trong R3 , tập (x, y, z) ∈ R3 : x − 2y + z = 1 (mặt
phẳng) là một siêu phẳng.
Nhận xét 1.3.1. Siêu phẳng là một tập affine.
Định nghĩa 1.3.3. Tập hợp có thể quy về dạng {x ∈ Rn : a, x ≤ b}
(a = 0, b ∈ R) được gọi là nửa không gian đóng trong Rn .
Ví dụ 1.3.2. Tập

(x, y) ∈ R2 : x + 3y ≤ 4

là nửa không gian đóng

trong R2 . Tập (x, y, z) ∈ R3 : x + 4y − z ≤ 2 là nửa không gian đóng
trong R3 .
12


Khóa luận tốt nghiệp Đại học


BÙI THỊ THÙY DƯƠNG

Nhận xét 1.3.2. Nửa không gian đóng là một tập lồi và đóng.
Định nghĩa 1.3.4. Tập D ⊂ Rn được gọi là tập lồi đa diện nếu D là
giao hữu hạn các nửa không gian đóng.
Ví dụ 1.3.3. Trong R2 , tập nghiệm của hệ bất phương trình



2x − y ≥ 0


x−y ≤2



x≥0

là một tập lồi đa diện. Hơn nữa, đoạn thẳng và hình tam giác trong R2
cũng là các tập lồi đa diện.
Nhận xét 1.3.3. Tập lồi đa diện là một tập lồi và đóng.
Chú ý 1.3.1. Cho D ⊂ Rn là tập lồi đa diện. D =

m

Hi trong đó Hi
i=1

là các nửa không gian đóng. Biểu diễn



a
. . . a1n
 11

Hi = {x ∈ Rn : ai , x ≤ bi ; ai = (ai1 , ai2 , ..., ain } ; A =  ... . . . ...

am1 · · · amn




b
 1 


b =  ...  .


bm
Khi đó, ta có thể biểu diễn D dưới dạng

D = x ∈ Rn : ai , x ≤ bi , ∀i = 1, m

13

hoặc D = {x ∈ Rn : Ax ≤ b} .





,



Khóa luận tốt nghiệp Đại học

1.3.2

BÙI THỊ THÙY DƯƠNG

Điểm cực biên

Định nghĩa 1.3.5. Cho D là tập lồi đóng, điểm x ∈ D được gọi là
điểm cực biên của D nếu không tồn tại y, z ∈ D, y = z sao cho x ∈
[y, z] \ {y, z} tức là không tồn tại y, z ∈ D và λ ∈ (0, 1) sao cho x =
λy + (1 − λ)z. Tập hợp các điểm cực biên của D được kí hiệu là extD.
Ví dụ 1.3.4. Trong R2 , nếu tập lồi đa diện là đoạn thẳng P Q thì P và
Q là hai điểm cực biên của đoạn thẳng P Q, nếu tập lồi đa diện là tam
giác ABC thì ba đỉnh A, B, C là ba điểm cực biên của tam giác ABC.
Bổ đề 1.3.1. Cho D là tập lồi đa diện khác rỗng và không chứa đường
thẳng. Khi ấy, nếu x thuộc D và x không phải là điểm cực biên thì tồn
tại y thuộc D thỏa mãn
(γ1 ) Nếu ai , x = bi thì ai , y = bi .
(γ2 ) Tồn tại i = 1, m sao cho ai , x < bi và ai , y = bi .
Chứng minh. (γ1 ) Vì x ∈
/ extD nên tồn tại y, z ∈ D y = z và λ ∈ (0, 1)
sao cho x = λy + (1 − λ)z. Vậy nếu ai , x = bi thì ta có
λbi ≥ λ ai , y = ai , x − (1 − λ) ai , z ≥ bi − (1 − λ)bi = λbi

suy ra ai , y = bi . Tương tự đối với z. Vậy ta có
ai , y = ai , z = ai , x = b i .
(γ2 ) Trước hết ta chứng tỏ tồn tại i ∈ 1, m sao cho
ai , x < bi .

14


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Giả sử ngược lại ai , x = bi với mọi i ∈ 1, m. Theo như chứng minh
phần trên, ta có
ai , y = ai , z = ai , x = b i .
Vậy với mọi λ > 0, ta có
ai , λy + (1 − λ)z = λ ai , y + (1 − λ) ai , z = bi , ∀i = 1, m.
Suy ra D chứa đường thẳng qua y, z. Điều này mâu thuẫn với giả thiết
D không chứa đường thẳng. Vậy tồn tại i ∈ 1, m sao cho ai , x < bi . Do
D không chứa đường thẳng nên đoạn thẳng [y; z] không thể kéo dài mãi
về 2 phía (mà vẫn còn nằm trong D). Không mất tính tổng quát ta xem
đường thẳng qua y, z thoát ra khỏi D tại y. Giả sử với mọi i = 1, m nếu
ai , x < bi thì ta cũng có ai , y < bi . Không mất tính tổng quát ta giả
sử
ai , y = ai , x = bi , ∀i ∈ 1, k;
ai , y < bi , ai , x < bi , ∀i = k + 1, m.
Với mỗi t > 0 ta đặt y t = y + t(y − x). Với mỗi i = k + 1, m chọn ci < bi
sao cho ai , y < ci . Khi ấy, với t > 0 đủ nhỏ, ta có
ai , yt = ai , y + t ai , y − x < ci + t ai , y − x < bi , ∀i = k + 1, m.
Mặt khác, ai , yt = bi , ∀i = 1, k do ai , y = ai , x = bi , ∀i = 1, k. Vậy

nên yt ∈ D với t > 0 đủ nhỏ. Như vậy đoạn thẳng [y, z] có thể kéo dài
về phía y tới yt sao cho nó vẫn còn nằm trong D. Điều này mâu thuẫn
với giả sử đường thẳng qua y, z thoát ra khỏi D tại y.
15


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Định lí 1.3.1. Tập lồi đa diện khác rỗng nếu không chứa đường thẳng
thì có điểm cực biên.
Chứng minh. Xét D là tập lồi đa diện khác rỗng và không chứa đường
thẳng. Chọn x ∈ D bất kỳ. Nếu x ∈ extD, ta có điều phải chứng minh.
Ngược lại, giả sử x ∈
/ extD. Theo Bổ đề 1.3.1 có x1 ∈ D sao cho tồn tại
i ∈ 1, m thỏa mãn
ai , x < bi và ai , x1 = bi .
Đặt Hi = {x ∈ Rn : ai , x = bi }. Ta có x ∈
/ Hi . Đặt D1 = Hi ∩ D.
Ta chứng minh dim D1 < dim D. Thật vậy, giả sử dim D1 = dim D. Vì
D1 ⊂ D nên affD1 ⊂ affD. Lại có dim D1 = dim D nên affD1 = affD.
Vì D1 ⊂ Hi nên affD1 ⊂ affHi = Hi . Suy ra affD ⊂ Hi . Điều này mâu
thuẫn vì x ∈ D ⊂ affD nhưng x ∈
/ H i . Ta chứng minh extD1 ⊂ extD.
Xét x ∈ extD1 . Giả sử x ∈
/ extD. Khi ấy tồn tại y, z ∈ D, y = z và
λ ∈ (0, 1) sao cho x = λy + (1 − λ)z. Vì x ∈ D1 = Hi ∩ D nên ai , x = bi .
Do x = λy + (1 − λ)z với λ ∈ (0, 1) nên ta cũng có ai , y = ai , z = bi .
Suy ra y, z ∈ D ∩ Hi nghĩa là y, z ∈ D1 . Vậy tồn taị y, z ∈ D1 , y = z và

λ ∈ (0, 1) sao cho x = λy + (1 − λ)z. Điều này mâu thuẫn với giả thiết
x ∈ extD1 . Do đó extD1 ⊂ extD. Vậy nếu x1 là điểm cực biên của D1
thì x1 cũng là điểm cực biên của D. Ta có điều phải chứng minh. Ngược
lại nếu x1 không là điểm cực biên của D1 thì ta lập luận như trên và
giảm được dim D1 vì D1 cũng là tập lồi đa diện khác rỗng và không chứa
đường thẳng. Qúa trình lập luận này phải dừng lại ở một bước k nào
đó mà xk là điểm cực biên của Dk . Do extDk ⊂ . . . ⊂ extD1 ⊂ extD nên
xk là điểm cực biên của D.
16


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Định lí 1.3.2. Cho tập lồi đa diện D khác rỗng. Nếu x là điểm cực biên
của D thì tồn tại hệ gồm n vectơ độc lập tuyến tính {aj1 , aj2 , . . . , ajn } lấy
từ hệ {a1 , a2 , . . . , am } sao cho aji , x = bji ∀i = 1, n.
Chứng minh. Giả sử ngược lại có tối đa k < n vectơ độc lập tuyến tính
{aj1 , aj2 , . . . , ajk } lấy từ hệ {a1 , a2 , . . . , am } sao cho aji , x = bji , ∀i =
1, k.
Đặt L = {aj1 , aj2 , . . . , ajk }.Vì dim L⊥ = n − dim L = n − k ≥ 1 nên tồn
tại h ∈ L⊥ , h = 0. Vậy với ε > 0 đủ nhỏ, ta có ai , x ± εh = ai , x ≤ bi
nếu ai ∈ L và ai , x ± εh < bi nếu ai ∈
/ L. Như vậy x ± εh ∈ D và
1
1
x + εh = x − εh do h = 0. Mặt khác, ta có x = (x + εh) + (x − εh).
2
2

Điều này mâu thuẫn với x là điểm cực biên.
Số cách chọn n vectơ từ m vectơ là hữu hạn. Do đó ta có hệ quả sau
Hệ quả 1.3.1. Tập hợp các điểm cực biên của tập lồi đa diện có hữu
hạn phần tử.
1.3.3

Phương vô tận

Định nghĩa 1.3.6. Cho u ∈ Rn được gọi là phương vô tận của tập lồi
đóng D nếu u = 0 và x + λu ∈ D, ∀x ∈ D, λ > 0.
Ví dụ 1.3.5. Cho tập lồi đa diện D = (x, y) ∈ R2 : x ≥ 0, y ≥ 0 thì
vectơ u(1, 2) là phương vô tận của D.
Định lí 1.3.3. Cho tập đa diên D khác rỗng. Khi ấy u là phương vô tận
của D nếu và chỉ nếu
u = 0 và Au ≤ 0.

17


Khóa luận tốt nghiệp Đại học

BÙI THỊ THÙY DƯƠNG

Chứng minh. Nếu u là phương vô tận của D thì u = 0 và với x ∈ D,
ta có A(x + λu) ≤ b, ∀λ > 0. Nghĩa là ai , x + λu ≤ bi , ∀λ > 0. Nếu
ai , u > 0 thì với λ đủ lớn, ta có ai , x + λu > bi . Như vậy ta phải có
ai , u < 0, ∀i = 1, m hay Au ≤ 0.
Nếu u = 0 và Au ≤ 0 thì x ∈ D, ta có A(x + λu) = Ax + λAu ≤ b
,∀λ > 0 do Ax ≤ b, Au ≤ 0, λ > 0. Vậy u là phương vô tận của D.
1.3.4


Phương cực biên

Định nghĩa 1.3.7. Cho D là tập lồi đóng, u ∈ Rn được gọi là phương
cực biên của D nếu u là phương vô tận của D và không tồn tại hai phương
vô tận độc lập tuyến tính v, w của D và α, β > 0 sao cho u = αv + βw.
Định lí 1.3.4. Cho tập lồi đa diện D khác rỗng. Nếu u là phương cực
biên của D thì tồn tại hệ n−1 vectơ độc lập tuyến tính aj1 , aj2 , . . . , ajn−1
lấy từ hệ {a1 , a2 , . . . , am } sao cho aji , u = 0, ∀i = 1, n − 1.
Chứng minh. Giả sử ngược lại có tối đa k < n−1 vectơ độc lập tuyến tính
{aj1 , aj2 , . . . , ajk } lấy từ hệ {a1 , a2 , . . . , am } sao cho aji , u = 0, ∀i = 1, k.
Đặt L = {aj1 , aj2 , . . . , ajk }. Ta có u ∈ L⊥ ; aji , u = 0 nếu ai ∈ L và
ai , u < 0 nếu ai ∈
/ L. Vì dim L⊥ = n − dim L = n − k ≥ 2 nên
tồn tại h ∈ L⊥ độc lập tuyến tính với u. Vậy với ε > 0 đủ nhỏ, ta có
ai , u + εh = 0 nếu ai ∈ L và ai , u + εh = 0. Do vậy theo Định lý
1.3.1, hai vectơ u ± εh là các phương vô tận và là các phương vô tận độc
lập tuyến tính do 2 vectơ u, h độc lập tuyến tính.
1
1
Mặt khác, ta có u = (u + εh) + (u − εh). Điều này mâu thuẫn với u
2
2
là phương cực biên.

18


Khóa luận tốt nghiệp Đại học


BÙI THỊ THÙY DƯƠNG

Hệ quả 1.3.2. Tập hợp các phương cực biên của tập lồi đa diện (không
kể các phương cực biên cùng phương) có hữu hạn phần tử.
1.3.5

Tập lồi đa diện không chứa đường thẳng

Định lí 1.3.5. Tập lồi đa diện bị chặn chính là bao lồi của các điểm cực
biên của nó.
Chứng minh. Xét D là tập lồi đa diện bị chặn. Ta sẽ chứng minh D =
conv(extD). Vì D là tập lồi chứa extD nên conv (extD) ⊂ D. Ta chứng
minh D ⊂ conv (extD)(∗) bằng quy nạp theo n = dim D.
Ta thấy (∗) đúng với n = 0 vì khi ấy D có một phần tử duy nhất. Giả
sử (∗) đúng với mọi n < k, ta chứng minh (∗) cũng đúng với n = k.
Thật vậy, xét x ∈ D. Nếu x ∈ extD thì ta có điều phải chứng minh.
Giả sử x ∈
/ extD. Khi ấy tồn tại y, z ∈ D, y = z và λ ∈ (0; 1) sao cho
x = λy + (1 − λ) z. Do D bị chặn nên đường thẳng qua y, z thoát ra khỏi
D tại 2 điểm. Không mất tính tổng quát ta giả sử hai điểm đó là y và
z. Theo Bổ đề 1.3.1, ta có tồn tại i ∈ 1, m thỏa mãn
ai , x < bi và ai , y = bi .
Đặt Hi = {x ∈ Rn : ai , x = bi }. Đặt D1 = Hi ∩ D. Ta có dim D1 <
dim D và extD1 ⊂ extD. Theo giả thiết quy nạp ta có D1 ⊂ conv (extD1 ).
Suy ra y ∈ D1 ⊂ conv (extD1 ) ⊂ conv (extD) (extD1 ⊂ extD). Tương
tự ta cũng có z ∈ conv (extD). Vậy x ∈ [y; z] ⊂ conv (extD).
Định lí 1.3.6. Tập lồi đa diện D khác rỗng và không chứa đường thẳng
có thể biểu diễn dưới dạng D = conv (extD) + {u ∈ Rn : Au ≤ 0}.
19