LèI CÁM ƠN

Em xin chân thành cám ơn Thay giáo Nguyen Văn Tuyên đã t¾n
tình hưóng dan, giúp đõ em trong suot thòi gian thnc hi¾n khóa lu¾n.
Em xin chân thành cám ơn các thay, các cô trong to giái tíchkhoa Toán, trưòng Đai hoc sư pham Hà N®i 2 đã tao moi đieu ki¾n
giúp đõ em hoàn thành khóa lu¾n này.
Em xin chân thành cám ơn gia đình và ban bè đã tao moi đieu
ki¾n thuân loi cho em trong quá trình thnc hi¾n khóa lu¾n.
Em xin chân thành cám ơn!

Hà N®i, tháng 05 năm 2012
Sinh viên

Lưu Th% Hong

i


LèI CAM ĐOAN

Em xin cam đoan, dưói sn hưóng dan cna Thay giáo Nguyen Văn
Tuyên khóa lu¾n “SN tách nón cho bài toán toi ưu vector” đưoc
hoàn thành không trùng vói bat kỳ đe tài nào khác.
Trong quá trình hoàn thành khóa lu¾n, em đã thùa ke nhung
thành tnu cna các nhà khoa hoc vói sn trân trong và biet ơn.

Hà N®i, tháng 05 năm 2012
Sinh viên

Lưu Th% Hong

ii


Mnc lnc

Má đau

1

1

4

Bài toán toi ưu vector
1.1. M®t so khái ni¾m cơ bán . . . . . . . . . . . . . . . . . .

4

1.2. Quan h¾ hai ngôi và quan h¾ thú tn . . . . . . . . . . . .

9

1.3. Điem huu hi¾u...........................................................................11
1.4. Sn ton tai cna điem huu hi¾u....................................................14
1.5. Bài toán toi ưu vector (VOP).................................................15
1.6. Đoi ngau Lagrange..................................................................... 16
2 SN tách nón cho bài toán toi ưu vector

19


2.1. Sn tách vector trong không gian ánh......................................... 19
2.2. Sn tách nón cna các t¾p............................................................23
2.3. Áp dung cho bài toán toi ưu vector...........................................29
Ket lu¾n

38

Tài li¾u tham kháo

39

iii


Mé ĐAU
1. Lý do chon đe tài
Phân tích không gian ánh (ISA) là m®t phương pháp đe nghiên
cúu các bài toán cnc tr% có ràng bu®c, bat đang thúc bien phân, và tong
quát hơn có the áp dung cho m®t lóp các bài toán, kí hi¾u là P , mà có
the bieu dien dưói m®t h¾ bat đang thúc tham so. Trong vi¾c phân tích
không gian ánh, m®t h¾ bat đang thúc tham so có the quy ve hai t¾p
con thích hop ròi nhau K và H cna không gian ánh tương úng vói P .
T¾p K đưoc đ%nh nghĩa như là ánh cna các hàm tham gia trong P , trong
khi H là m®t nón loi chí phu thu®c vào kieu đieu ki¾n (đang thúc, bat
đang thúc, ...) trên lóp các bài toán P . Sn ròi nhau cna K và H có the
đưoc chí ra bang cách đ¾t chúng trong hai t¾p múc ròi nhau cna m®t
hàm vector tách. Trong trưòng hop này, khi P là m®t bài toán toi ưu
vector (VOP) đã có các nghiên cúu đưoc đưa ra, chang han như: các
đieu ki¾n can toi ưu kieu Lagrange, các đieu ki¾n cho điem yên ngna,
sn ton tai nghi¾m, đieu ki¾n chính quy và phương pháp vô hưóng hóa

[1, 2, 6, 7, 9, 10]. Muc đích chính cna khóa lu¾n này nham phân tích sâu
hơn sn tách vector trong không gian ánh và sn liên h¾ vói các loai khác,
như: tách tuyen tính tùng khúc và tách nón. Đ¾c bi¾t là moi liên h¾ vói
đieu ki¾n ton tai điem yên ngna cho bài toán toi ưu vector.
Khóa lu¾n đưoc chia thành hai chương. Chương 1 giói thi¾u m®t
so kien thúc cơ bán ve giái tích loi, ve bài toán toi ưu vector và phương
pháp vô hưóng hóa.
Chương 2 giói thi¾u m®t so đ¾c điem chung cna tách vector trong
không gian ánh tương úng vói m®t bài toán toi ưu vector. Sau đó se


5

phân tích moi quan h¾ giua tách vector và tách nón. Đ¾c bi¾t, khóa lu¾n
se trình bày m®t đieu ki¾n can và đn cho sn ton tai cna tách nón chính
quy cna các t¾p K và H. Cuoi cùng, chúng ta se áp dung cho bài toán
toi ưu vector và se chí ra sn tương đương cna tách vector vói sn tách
nón.

2. Mnc đích nghiên cNu
Bưóc đau làm quen vói nghiên cúu khoa hoc, tù đó hình thành tư
duy logic đ¾c thù cna b® môn.
Tìm hieu nhung kien thúc ve bài toán toi ưu vector, phân tích moi
quan h¾ giua sn tách nón và sn tách vector cna 2 t¾p cũng như trong
không gian ánh. Đe áp dung cho bài toán toi ưu vector.

3. Nhi¾m vn nghiên cNu
Nghiên cúu sn tách nón cho bài toán toi ưu vector đe chí ra đieu
ki¾n can cho sn ton tai cna m®t điem yên ngna vector cna hàm Lagrange
tương úng vói bài toán toi ưu vector.


4. Phương pháp nghiên cNu
Đoc tài li¾u, phân tích, so sánh, tong hop và theo sn chí đao cna
ngưòi hưóng dan đe hoàn thành muc tiêu đe ra.


5. Cau trúc khóa lu¾n
Ngoài phan mó đau, ket lu¾n, danh muc tài li¾u tham kháo thì đe
tài bao gom 2 chương:
Chương 1: Bài toán toi ưu vector.
Chương 2: Sn tách nón cho bài toán toi ưu vector.


Chương 1
Bài toán toi ưu vector
1.1.

M®t so khái ni¾m cơ bán
Giá sú E là không gian tuyen tính, R là t¾p các so thnc.

Đ%nh nghĩa 1.1. T¾p A ⊂ E đưoc goi là loi, neu:
∀x1, x2 ∈ A; ∀λ ∈ R : 0 ™ λ ™ 1 ⇒ λx1 + (1 − λ)x2 ∈ A.
Ví dn 1.1. Các núa không gian là các t¾p loi. Hình tam giác, hình tròn
trong m¾t phang là các t¾p loi. Hình cau đơn v% trong không gian
Banach là t¾p loi...
Đ%nh nghĩa 1.2. Giá sú A ⊂ E. Giao cna tat cá các t¾p loi chúa A
đưoc goi là bao loi cna t¾p A, và kí hi¾u coA.
Nh¾n xét 1.1. a) coA là m®t t¾p loi. Đó là t¾p loi bé nhat chúa A;
b) A loi khi và chí khi A = coA.
Đ%nh nghĩa 1.3. T¾p C ⊂ E đưoc goi là nón có đính tai 0 neu:

∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C.
C đưoc goi là nón có đính tai x0, neu C − x0 là nón có đính tai 0.


8

Đ%nh nghĩa 1.4. Nón C có đính tai 0 đưoc goi là nón loi, neu C là m®t
t¾p loi, nghĩa là:
∀x, y ∈ C, ∀λ, µ > 0 ⇒ λx + µy ∈ C.
Ví dn 1.2. Các t¾p sau đây trong Rn:
{ξ1, ξ2, ..., ξn ∈ Rn : ξi “ 0, i = 1, ..., n}
(nón orthant không âm)
{ξ1, ξ2, ..., ξn ∈ Rn : ξi > 0, i = 1, ..., n}
(nón orthant dương)
là các nón loi có đính tai 0. Đó là nón loi quan trong trong Rn.
Ngoài ra, neu cho D ⊆ Rm là m®t nón loi, nón cnc dương cna D
đưoc xác đ%nh bói:
D∗ := {x∗ ∈ Rm :< x∗, x >“ 0, ∀x ∈ D} .
Cho a, b ∈ Rm, a “D b khi và chí khi a − b ∈ D; a “ 0 khi và chí
khi ai “ 0, i = 1, ..., m. Kí+hi¾u Rm := {x ∈ Rm : x “ 0} và cho g
: X → Rm. Hàm g đưoc goi là D-giong loi trên S ⊆ X khi và chí khi :
∀x1, x2 ∈ S, ∀α ∈ [0, 1], ∃x ∈ S,
ˆ
sao
cho

(1 − α)g(x1) + αg(x2) − g(x) ∈ D.
ˆ

Đieu này đưoc biet đen trong [13] rang g là m®t hàm D-giong loi khi và

chí khi t¾p g(S) + D là loi.
Đ%nh nghĩa 1.5. Phan trong tương đoi cna t¾p A ⊂ Rn là phan trong
cna A trong af f A (bao affine); kí hi¾u là riA. Các điem thu®c riA đưoc
goi là điem trong tương đoi cna t¾p A.


Nh¾n xét 1.2. intA := {x ∈ Rn : ∃s > 0, x + sB ⊂ A} ,

riA := {x ∈ af f A : ∃s > 0, (x + sB) ∩ af f A ⊂ A} ,
trong đó B là hình cau đơn v% đóng trong Rn.
Tiep theo chúng ta se đi xem xét m®t so nón thưàng g¾p
Cho C là nón loi trong không gian vector tôpô E. Kí hi¾u l(C) :=
C ∩ (−C) (phan tuyen tính cna C); clC (bao đóng cna C); m®t t¾p con
A ⊆ E, Ac là phan bù cna A trong E, nghĩa là Ac = E\A.
Đ%nh nghĩa 1.6. Chúng ta nói nón C là:
(a) Nhon neu l(C) = 0;
(b) Nón sac neu bao đóng cna nó là nhon;
(c) Nón có giá ch¾t neu C\l(C) là đưoc chúa trong m®t núa không gian mó
thuan nhat;
(d) Nón đúng neu (clC) + C\l(C) ⊆ C, ho¾c tương đương
clC + C\l(C) ⊆ C\l(C).
Ví dn 1.3. 1. Cho Rn là không gian Euclid n-chieu. Khi đó, nón orthant
không âm Rn gom tat cá các vectơr cna Rn vói toa đ® không âm là nón
+
loi, sac, đóng, có giá ch¾t và là nón đúng.
T¾p {0} cũng là m®t nón, nhưng là nón tam thưòng.
T¾p là hop cna 0 và các vector vói toa đ® đau tiên dương là
m®t nón đúng, nhon, có giá ch¾t nhưng không là nón sac.
Bat kì núa không gian đóng thuan nhat là nón đúng, có giá ch¾t
nhưng không là nón nhon.



2. Cho Ω là không gian vectơr gom tat cá dãy x = {xn} so thnc.
Cho C = {x ∈ Ω : xn “ 0, ∀n}, thì C là nón nhon, loi. Tuy nhiên,
ta chưa biet nón C là nón đúng ho¾c nón sac vì ta chưa biet tôpô xác đ
%nh trên không gian này.
3. Nón thú tn tù đien: Cho
p

l = ,x ∈ Ω : "x" = (

.

p1

|xn| )p , , 1 ™ p < ∞.

Kí hi¾u C là hop cna 0 và các dãy mà so hang đau tiên khác không cna
dãy là dương. Đây là m®t nón loi, còn goi là nón thú tn tù đien. Nó là
nón nhon nhưng không là nón đúng và cũng không phái là nón có giá
ch¾t.
M¾nh đe 1.1. Nón C là đúng khi và chs khi m®t trong các các đieu
ki¾n sau thoá mãn:
(a) C là đóng;
(b) C\l(C) là mó, khác rong;
(c) C là hop cúa 0 và giao cúa các núa không gian mó và núa không
gian đóng trong E.
Chúng minh. (a) Hien nhiên.
(b) Neu C\l(C) mó thì intC ƒ= ∅ và intC = C\l(C). Do đó, ta có
clC + C\l(C) = (clC) + intC ⊆ C,

hay C là nón đúng.
(c) Giá sú C = {0} ∪ (∩ {Hλ : λ ∈ Λ}), ó đây Hλ là núa không gian
đóng ho¾c mó trong E. Neu tat cá Hλ là đóng thì đieu này tương
đương vói C là đóng. Do đó, ta có the giá sú ít nhat m®t núa không
gian là mó thì l(C) = {0} và b ∈ C\l(C) khi và chí khi b ∈ Hλ, ∀λ
∈ Λ. Hơn the nua, ta thay a ∈ clC khi và chí khi a ∈ clHλ, ∀λ ∈ Λ
nên clHλ + Hλ ∈ Hλ.


V¾y Hλ là mó ho¾c đóng thì a + b ∈ C, a ∈ C, b ∈ C\l(C).
M¾nh
đe đưoc chúng minh.
Đ%nh nghĩa 1.7. Cho m®t nón C trong không gian E. M®t t¾p B ⊆ E
sinh ra nón C và viet C = cone(B) neu
C = {tb : b ∈ B, t “ 0} .
Hơn nua, neu B không chúa 0 và vói moi c ∈ C, c ƒ= 0, ton tai duy
nhat b ∈ B, t > 0 sao cho c = tb thì B đưoc goi là cơ só cna C. Khi
B là m®t t¾p huu han, cone(conv(B)) đưoc goi là m®t nón đa di¾n.
Nh¾n xét 1.3. Rõ ràng trong không gian huu han chieu m®t nón có
có só là loi, đóng b% ch¾n khi và chí khi nó là nhon, đóng. Tuy nhiên nó
không đúng trong không gian vô han chieu.
M¾nh đe 1.2. Neu E là không gian Hausdorff thì m®t nón vói m®t cơ
só loi, đóng b% ch¾n là nón đóng, nhon vì v¾y nó là nón đúng.
Chúng minh. Trưóc het ta chí ra rang C là đóng. Cho dãy{cα} là m®t
lưói tù C h®i tu tói c. Do B là m®t cơ só nên ton tai m®t lưói {bα}
tù B và m®t lưói {tα} các so dương mà cα = tαbα. De thay tα là b%
ch¾n. Th¾t v¾y, giá sú ngưoc lai limtα = ∞. Vì E là không gian
Hausdorff
nên lưói ,bα =


cα
,
tα

h®i tu tói 0. Hơn the nua B là đóng, dan tói mâu

thuan: 0 = limbα ∈ B. Bang cách này, ta có the giá sú {tα} h®i tu tói
điem to “ 0. Neu to = 0 thì tù tính b% ch¾n cna B, limtαbα = 0. Do
đó
c = 0 và hien nhiên c ∈ C. Neu to > 0,ta có the giá sú tα > s, ∀α, s >
0.
Tù bα =

cα
tα

h®i tu tói

c
to

và hơn nua B đóng nên vector

c ∈ C và C đóng nên C nhon là hien nhiên.

c
to

∈ B. Do đó



1.2.

Quan h¾ hai ngôi và quan h¾ thN tN
Cho m®t t¾p hop E tuỳ ý, m®t quan h¾ hai ngôi trong E đưoc đ%nh

nghĩa bói m®t t¾p con B cna t¾p hop tích E × E. Đieu này có nghĩa là
m®t phan tú x ∈ E có quan h¾ vói y ∈ E neu (x, y) ∈ B.
Đ%nh nghĩa 1.8. Cho B là m®t quan h¾ hai ngôi trong E. Ta nói quan
h¾ này là:
(a) Phán xa neu (x, x) ∈ B vói moi x ∈ E;
(b) Đoi xúng neu(x, y) ∈ B suy ra (y, x) ∈ B vói moi x, y ∈ E;
(c) Bac cau neu (x, y) ∈ B,(y, z) ∈ B suy ra (x, z) ∈ B vói x, y, z ∈ B;
(d) Đay đn ho¾c liên thông neu (x, y) ∈ B ho¾c (y, x) ∈ B vói moi
x, y ∈ E, x ƒ= y;
(e) Tuyen tính trong trưòng hop E là không gian vector thnc neu (x, y) ∈
B suy ra (tx + z, ty + z) ∈ B vói moi x, y, z ∈ E, t > 0;
(f) Đóng trong trưòng hop E là không gian vector tôpô, neu nó là đóng
như m®t t¾p con cna không gian tích E × E.
Đe làm rõ đ%nh nghĩa này chúng ta xem xét m®t so ví du co đien
sau. Cho E là m®t c®ng đong dân cư cna m®t thành pho và chúng ta
đ%nh nghĩa quan h¾ hai ngôi như sau (so dân cư đưoc gán bói x, y, z,...)
1. (x, y) ∈ B1 neu x, y là nhung ngưòi tuoi cao ho¾c có tuoi.
2. (x, y) ∈ B2 neu x, y là hai giói tính khác nhau.
3. (x, y) ∈ B3 neu x, y là nhung ngưòi có ho.
Ta thay rang B1 là phán xa, bac cau, không đoi xúng, đay đn. B2
không phán xa, đoi xúng, không bac cau, không đay đn. B3 là phán xa,
không bac cau, đoi xúng, không đay đn.



Đ%nh nghĩa 1.9. Quan h¾ hai ngôi là m®t quan h¾ thú tn neu nó là
phán xa, bac cau.
Th¾t v¾y, neu B là m®t quan h¾ thú tn mà là tuyen tính trong
m®t không gian vector thì t¾p
C = {x ∈ E : (x, 0) ∈ B}
là m®t nón loi. Hơn nua, neu B là không đoi xúng thì C là nhon. Ngưoc
lai, moi nón loi trong E cho m®t quan h¾ hai ngôi
BC = {(x, y) ∈ E × E : x − y ∈ C}
là phán xa, bac cau và tuyen tính. Ngoài ra, neu C là nhon thì BC là
không đoi xúng.
Bây giò, chúng ta se xét m®t vài thú tn sinh ra bói các nón loi.
Đôi khi chúng ta viet:
x “C y thay cho x − y ∈ C;
ho¾c x “ y neu nó chac chan là quan h¾ hai ngôi đưoc đ%nh
nghĩa bói C;
x >C y neu x “C y và không phái là y “C x,
hay là x ∈ y + C\l(C). Khi intC ƒ= 0, x

C

y nghĩa là x >K y

vói
K = {0} ∪ intC.
Ví dn 1.4. 1. Cho Rn và t¾p C = R+n . Thì BC là phán xa, bac
cau, tuyen tính, đóng, không đoi xúng nhưng không đay đn.
Cho x = (x1, ..., xn) , y = (y1, ..., yn) ∈ Rn:
x “C y khi và chí khi xi “ yi vói i = 1,..., n;
x >C y khi và chí khi xi “ yi vói i = 1,..., n và ít nhat m®t
bat đang thúc là ng¾t;



x “C y khi và chí khi xi > yi vói moi i = 1,..., n.
2. Trong R2. Neu C = .R1, 0. thì BC là phán xa, bac cau, tuyen tính,
đóng và đoi xúng. Trong trưòng hop này x “C y khi và chí khi hai
thành phan cna các vector trùng nhau. Thú tn này không đay đn.
3. Nón thú tn tù đien là m®t quan h¾ phán xa, bac cau, tuyen tính đay đn
trong lp.

1.3.

Điem hÑu hi¾u

Cho E là không gian vector tôpô thnc vói quan h¾ thú tn (“)
đưoc sinh bói m®t nón loi C.
Đ%nh nghĩa 1.10. Cho A là m®t t¾p con khác rong cna E. Ta nói rang:
(a) x ∈ A là m®t điem huu hi¾u lí tưóng (ho¾c cnc tieu lí tưóng) cna A
tương úng vói C neu y “ x, ∀y ∈ A;
T¾p các điem cnc tieu lí tưóng cna A đưoc kí hi¾u là IMin (A | C);
(b) x ∈ A là điem huu hi¾u (cnc tieu-Pareto ho¾c không cnc tieu) cna
A tương úng vói C neu x “ y, y ∈ A thì y “ x;
T¾p các điem huu hi¾u cna A kí hi¾u là Min(A | C);
(c) x ∈ A là điem huu hi¾u thnc sn (toàn cuc) cna A tương úng vói C neu
ton tai m®t nón loi K ƒ= E vói intK ⊇ C\l(C) sao cho x ∈ Min(A |
K);
T¾p các điem huu hi¾u toàn cuc cna A đưoc kí hi¾u là P rMin(A |
C);
(d) Giá sú intC ƒ= ∅, x ∈ A là m®t điem huu hi¾u yeu cna A tương úng
vói C neu x ∈ Min(A | {0} ∪ intC);
T¾p các điem huu hi¾u yeu cna A kí hi¾u là W Min(A | C).



Ví dn 1.5. Cho:
.
.
A = (x, y) ∈ R2 : x2 + y2 ™ 1, y ™ 0 ∪ {(x, y) : x “ 0, 0 “
y “ −1} ;
B = A ∪ {(−2, −2)}.
Neu cho C = R+2 , ta có:
IMin(B) = P rM in(B) = M in(B) = W Min(B) = {(−2, −2)};
IMin(B) = ∅,
.
.
P rM in(A) = (x, y) ∈ R2 : x2 + y2 = 1, 0 > x, 0 > y ,
Min(A) = P rMin(A) ∪ {(0, −1)} ∪ {(−1, 0)},
W Min(A) = Min(A) ∪ {(x, y) : y = −1, x “ 0}.
Bây giò cho C = (R1, 0) ⊆ R2. Ta có:
IMin(B) = ∅,
P rM in(B) = M in(B) = W Min(B) = B,
IMin(A) = ∅,
P rM in(A) = Min(A) = W Min(A) = A.
Tù đ%nh nghĩa cna các điem huu hi¾u, ta có m¾nh đe sau:
M¾nh đe 1.3. Cho A ⊆ E thì:
(a) x ∈ IMin(A) khi và chs khi x ∈ A và A ⊆ x + C;
(b) x ∈ IMin(A) khi và chs khi A ∩ (x − C) ⊆ x + l(C) ho¾c tương
đương vói không ton tai y ∈ A sao cho x > y. Đ¾c bi¾t khi C là
nhon, x ∈ Min(A) khi và chs khi A ∩ (x − C) = {x};
(c) Khi C ƒ= E, x ∈ W Min(A) khi và chs khi A ∩ (x − intC) = ∅
ho¾c tương đương vói không ton tai y ∈ A sao cho x


y.

M¾nh đe 1.4. Cho t¾p khác rong A ⊆ E có:
P rM in(A) ⊆ Min(A) ⊆ W Min(A).
Hơn nua, neu IMin(A) ƒ= ∅ thì IMin(A) = Min(A) và nó là
t¾p m®t điem khi C là nhon.


Chúng minh. Lay x ∈ P rMin(A). Neu x ƒ∈ Min(A) có y ∈ A và x − y
∈
C\l(C). Lâý nón loi K, K ƒ= E vói intK ⊆ C\l(C) và x ∈ Min(A | K).
Thì x − y ∈ intK ⊆ K\l(K). Đieu này mâu thuan vói x ∈ Min(A |
K) suy ra P rMin(A) ⊆ Min(A).
Lay x ∈ Min(A). Neu x ƒ∈ W Min(A) theo M¾nh đe 1.3 ton tai
y ∈ A sao cho x − y ∈ intC. Do C ƒ= E, intC ⊆ C\l(C) nên ta có x −
y ∈ C\l(C).Đieu này mâu thuan vói x ∈ MinA. V¾y Min(A) ⊆
W Min(A).
Rõ ràng IMin(A) ⊆ Min(A). Neu IMin(A) ƒ= ∅, cho x ∈
IMin(A) thì x ∈ Min(A). Cho y ∈ M in(A) thì y ≥ x vì v¾y x “ y.
Lay

m®t điem bat kì z ∈ A có z “ x vì x ∈ IMin(A) suy ra z “

y là y ∈ IM in(A). Do đó IM in(A) = M in(A). Ngoài ra, neu C là
nhon x “ y và

y ≥ x chí có the xáy ra trưòng hop x = y. V¾y

IMinA là t¾p m®t điem.
Đ%nh nghĩa 1.11. Cho x ∈ E. T¾p A ∩ (x − C) đưoc goi là m®t

nhát cat A tai x và kí hi¾u Ax .
M¾nh đe 1.5. Cho x ∈ E vói Ax ƒ= ∅. Ta có:
(a) IM in(Ax ) ⊆ IMinA neu IMinA ƒ= ∅;
(b) Min(Ax ) ⊆ MinA (tương tn cho W M in).
Chúng minh. (a) Cho y ∈ IMin(Ax) và z ∈ IMinA có Ax ⊆ y + C và
A ⊆ z + C. Thì z ∈ Ax và z − y ∈ l(C) suy ra
A ⊆ z + C = y + z − y + C = y + l(C) + C = y + C.
Do đó y ∈ IMinA.
(b) Giá sú y ∈ Min(Ax). Theo M¾nh đe 1.4 có Ax ∩ (y − C) ⊂ y + l(C)
suy ra y − C ⊆ x − C nên
A ∩ y − C ⊆ A ∩ (y − C) ∩ (x − C) ⊆ Ax ∩ (y − C) ⊆ y +
l(C).
Do đó y ∈ MinA.


Chúng minh tương tn cho W M in.
Nh¾n xét 1.4. Quan h¾ P rM in(Ax ) ⊆ P rM inA nói chung không đúng
trù m®t so trưòng hop đ¾c bi¾t.

1.4.

SN ton tai cúa điem hÑu hi¾u

Đ%nh nghĩa 1.12. Cho lưói {xα : α ∈ I} tù E đưoc goi là lưói giám
(tương úng vói C) neu xα >C xβ vói α, β ∈ I; β > α.
Đ%nh nghĩa 1.13. Cho A ⊆ E đưoc goi là C-đay đn (tương úng C-đay
đn manh) neu nó không có phn dang {(xα − clC)c : α ∈ I} (tương
úng
{(xα − C)c : α ∈ I}) vói {xα} là m®t lưói giám trong A.
Đ%nh lí 1.1. Giá sú C là m®t nón loi đúng và A là m®t t¾p khác rong

trong E. Thì Min(A | C) ƒ= ∅ khi và chs khi A có m®t nhát cat Cđay đú và khác rong.
Chúng minh. Neu Min(A | C) ƒ= ∅ thì moi điem cna t¾p này cho ta
m®t nhát cat C-đay đn vì không ton tai lưói giám. Ngưoc lai, cho Ax
khác rong là m®t nhát cat C-đay đn cna A. Theo M¾nh đe 1.5 thì ta
chí can chúng minh Min(Ax | C) ƒ= ∅. Xét t¾p P bao gom tat cá các
lưói giám trong A. Vì A ƒ= ∅ suy ra P ƒ= ∅. Vói a, b ∈ P ta viet a >
b neu b ⊆ a. Rõ ràng (>) là quan h¾ thú tn trong P , và m®t xích bat
kì trong P đeu có c¾n trên. Th¾t v¾y, giá sú {aλ; λ ∈ Λ} là m®t xích
trong P . Goi B là t¾p tat cá các t¾p con huu han B cna Λ đưoc sap
thú tn bói bao hàm và đ¾t
aB = ∪ {aα; α ∈ B} .
Và
ao = ∪ {aB : B ∈ B} .


Thì ao là m®t phan tú cna P và ao > aα vói moi α ∈ Λ nghĩa là ao là
m®t c¾n trên cna xích này. Áp dung bo đe Zorn, ton tai phan tú lón
nhat cna P , kí hi¾u là a∗ = {xα : α ∈ I} ∈ P . Bây giò, giá sú ngưoc
lai Min(Ax | C) = ∅. Chúng ta se chúng minh {(xα − clC)c : α ∈
I} phn Ax. Ta chí ra vói moi y ∈ Ax có α ∈ I mà (xα − clC)c chúa
y. Giá sú phán chúng y ∈ xα − clC, ∀α ∈ I. Vì M in(Ax | C) = ∅ có
z ∈ Ax vói y >C z. Do tính đúng cna C nên x − α >C z, (α ∈ I).
Thêm z vào lưói
a∗ ta thay rang lưói này không the lón nhat, dan tói mâu thuan. V¾y
đ%nh lí đưoc chúng minh.

1.5.

Bài toán toi ưu vector (VOP)
Cho X là m®t t¾p con khác rong cna m®t không gian tôpô và F là


m®t ánh xa đa tr% tù X vào E, ó đây E là không gian vector tôpô thnc
đưoc xap thú tn bói nón loi C.
Xét VOP:
minF (x)
vói ràng bu®c x ∈ X.
Điem x ∈ X đưoc goi là toi ưu (cnc tieu ho¾c huu hi¾u) cna VOP
neu F (x) ∩ Min(F (X) | C) ƒ= ∅.
é đây F (X) là hop cna các t¾p F (x) trên X. Các phan tú
cna M in(F (x) | C) đưoc goi là giá tr% toi ưu cna VOP. T¾p các điem
huu hi¾u cna VOP đưoc kí hi¾u là S(X; F ). Thay the IMin, P rM in,
W M in
cho M in(F (X) | C) chúng ta có các khái ni¾m IS(X; F ),
P rS(X; F ) và W S(X; F ).
Quan h¾ giua các điem huu hi¾u, huu hi¾u thnc sn và huu hi¾u
yeu cna VOP đưoc trình bày trong m¾nh đe sau:


M¾nh đe 1.6. Cho VOP, chúng ta có các bao hàm thúc sau:
P rS(X; F ) ⊆ S(X; F ) ⊆ W S(X; F ).
Hơn nua, neu IS(X; F ) ƒ= ∅ thì IS(X; F ) = S(X; F ).
Chúng minh tương tn M¾nh đe 1.4.
Bo đe 1.1. Giá sú C là loi, X là t¾p compac khác rong và F là C-liên
tnc trên trong X vói F (x) + C là C-đay đú, đóng vói moi x ∈ X
thì F (X) là C-đay đú.
Chúng minh. Giá sú phán chúng rang F (X) không là C-đay đn. Đieu
này có nghĩa là, có m®t lưói giám {aα : α ∈ I} cna F (X) sao cho:
{(aα − cl(C))c : α ∈ I}
là phn cna F (X). Lay xα ∈ X vói aα ∈ F (xα). Không mat tính tong
quát, giá sú limxα = x ∈ X. Khi đó, vói moi lân c¾n V cna F (x)

trong E có m®t chí so β ∈ I sao cho
aα ∈ V + C, ∀α “ β.
Do {aα} là dãy giám, nên
aα ∈ aδ + C, ∀δ “ α.
Tù đây, suy
ra:

aα ∈ cl(F (x) + C) = F (x) + C, ∀α.

Dan tói mâu thuan: F (x) + C không the là C-đay đn.

1.6.

Đoi ngau Lagrange
Trong quy hoach toán hoc tương úng vói moi bài toán goc có m®t

bài toán đoi ngau. Bài toán goc và bài toán đoi ngau cna nó l¾p thành


m®t c¾p. Đe thay đưoc ý tưóng cna phương pháp này, ta xét bài toán
quy hoach tuyen tính, kí hi¾u (LP):
mincx
vói ràng bu®c x ∈ Rn, Ax “ b,
trong đó, c ∈ Rn, b ∈ Rm và A là ma tr¾n (n × m).
Thì bài toán đoi ngau cna nó kí hi¾u là (LD) viet dưói dang:
maxby
vói ràng bu®c y ∈ Rm, AT = c, y “ 0,
trong đó, AT là ma tr¾n chuyen v% cna A.
Bài toán goc và bài toán đoi ngau có các moi quan h¾ sau:
1. cx “ by vói moi x là điem chap nh¾n đưoc cna (LP), y là điem chap

nh¾n đưoc cna (LD);
2. (LP) có nghi¾m toi ưu khi và chí khi (LD) có nghi¾m toi ưu và giá tr%
toi ưu cna chúng bang nhau;
3. Neu (LP) không có nghi¾m toi ưu thì (LD) không có nghi¾m toi ưu và
ngưoc lai;
4. (LP) là bài toán đoi ngau cna (LD).
Kí hi¾u E1, E2, E3 là các không gian vector tôpô tách trên
trưòng so thnc, X là t¾p con khác rong cna E1, C ⊆ E2 và K ⊆ E3 là
nón loi nhon vói phan trong khác rong, F và G là t¾p ánh xa đa tr%
tù E1 tói E2 và E3 tương úng, vói X ⊆ domF ∩ domG.
Bài toán toi ưu vector (VOP) phát bieu dưói dang:
minF (x)
vói ràng bu®c x ∈ X, G(x) ∩ −K ƒ= ∅.


(K là m®t nón loi trên không gian vector tôpô E1).
T¾p Xo = {x ∈ X : G(x) ∩ −K ƒ= ∅} là t¾p các điem chap
nh¾n đưoc cna VOP.
Bây giò, cho Y là m®t nón loi trong C. Tương úng giua Y và VOP
ta có các đ%nh nghĩa:
(a) Hàm Lagrange là ánh xa L(., .) tù X × Y tói E2:
L(x, y) = F (x) + yG(x), x ∈ X, y ∈ Y.
(b) Ánh xa đoi ngau D(.) tù Y tói E2:
D(y) = Min(L(x, Y ) | C), y ∈ Y.
H¾ quá 1.1. Neu m®t điem chap nh¾n đưoc xo cúa VOP thoá mãn
F (xo) ∩ Max(D(Y ) | C),
thì nó là nghi¾m toi ưu cúa VOP.
Chúng minh. Cho ao ∈ F (xo) ∩ Max(D(Y ) | C) thì ton tai yo ∈ Y
sao cho:
ao ∈ D(yo) ∩ Max(D(Y | C)).

Theo đ%nh lí đoi ngau yeu khi đó không có b® 3 điem chap nh¾n đưoc
(x, a, b) cna VOP sao cho ao >C a. Đieu này có nghĩa là
ao ∈ Min(F (Xo) | C).
V¾y xo là nghi¾m toi ưu cna VOP.
Đ%nh nghĩa 1.14. Ta nói c¾p (xo, yo) ∈ X × Y là m®t điem yên
ngna cna L(.) neu:
L(xo, yo) ∩ Max(L(xo , Y ) | C) ∩ Min(L(yo , X) | C) ƒ= ∅.


Chương 2
SN tách nón cho bài toán toi ưu
vector
2.1.

SN tách vector trong không gian ánh
Cho nón C ⊂ Rl. Trong muc này ta se giá sú C là nón loi, đóng,

nhon, khác rong. Kí hi¾u Co := C\ {O}.
Cho f : X → Rl và g : X → Rm là các hàm vector đưoc xác đ%nh
trên m®t t¾p con X cna không gian Banach χ. Chúng ta xét VOP sau:
minCo f (x)
vói ràng bu®c x ∈ R := {x ∈ X : g(x) “D O} ,

(2.1)

vói D là nón loi, đóng trong Rm và minCo là vector cnc tieu tương úng
vói nón Co: x¯ ∈ R là vector cnc tieu (toàn cuc) (v. m. p) cna (2.1)
và chí khi
khi
Neu

C=
Rl

f (x¯) §Co f (x), ∀x ∈ R.
+

(2.2)

thì (2.1) tró thành bài toán toi ưu vector Pareto co đien.

Bài toán toi ưu vector yeu là thưòng tương úng vói (2.1) và đưoc


23

đ%nh nghĩa bói
minintC
f (x)
vói ràng bu®c x ∈ R,

(2.3)

trong đó minintC là vector cnc tieu tương úng vói nón
intC:
v.p.m (toàn cuc) cna (2.3) khi và chí khi

x¯ ∈ R
là

f (x¯) §intC f (x), ∀x ∈ R.


(2.4)

Vói C = R+l , (2.3) đưoc goi là VOP Pareto yeu.
Can chú ý rang (2.2) se thoá mãn khi và chí khi h¾ (vói bien x)
f (x¯) − f (x) “Co O, g(x) “D O, x ∈ X,
là vô nghi¾m. Xét các t¾p
.
H := (u, v)) ∈ Rl × Rm : u

(2.5)

.

o

O, v “D O = Co × D,

“C
và
.
Kx¯ := (u, v) ∈ Rl × Rm : u = f (x¯) − f (x), v = g(x), x ∈
.
X .
H và

là các t¾p hop con cna Rl+m đưoc goi là không gian ánh, Kx¯

Kx¯
đưoc goi là ánh tương úng vói bài toán (2.1).

Tù các đ%nh nghĩa trưóc ta thay x¯ ∈ R là v.m.p cna (2.1) khi
chí khi
và
Kx¯ ∩ H = ∅.

(2.6)

Nói chung ánh cna bài toán toi ưu có the không loi ngay cá khi các hàm
tương úng có m®t so tính chat loi. Đe khac phuc khó khăn này, chúng ta
se đưa ra tiêu chuan cna ánh Kx¯ , cu the là mó r®ng nó đoi vói nón
clH:
Ex¯ : = Kx¯ − clH


24

.
= (u, v) ∈ Rl × Rm : u ™C f (x¯) − f (x), v ™D g(x), x
.
∈X .
T¾p Ex¯ đưoc goi là ánh mó r®ng tương úng vói (2.1). M¾nh đe sau cho
ta m®t tiêu chuan cna Ex¯ . Đ¾t Hu := {(u, v) ∈ H : v = O} = Co ×
{Om } .


M¾nh đe 2.1. Đieu ki¾n (2.6) thoá mãn khi và chs khi

ho¾c tương
đương


Ex¯ ∩ H = ∅,

(2.7)

Ex¯ ∩ Hu = ∅.

(2.8)

Chúng minh. Đe chúng minh tương đương giua (2.6) và (2.7) ta can chú
ý rang
H + clH = H,

(2.9)

và do đó Kx¯ − H = Kx¯ − (H + clH) = (Kx¯ − clH) − H = Ex¯ −
H. Ta se chí ra (2.7) và (2.8) là tương đương. Rõ ràng, (2.7) suy ra
(2.8) do Hu ⊆ H. Đe chúng minh quan h¾ ngưoc lai, ta giá sú phán
chúng rang (2.8) thoá mãn nhưng (2.7) không thoá mãn; nghĩa là ∃(u¯,
v¯) ∈ Ex¯ ∩ H. Tù
Ex¯ − clH = Kx¯ − (clH + clH) = Ex¯ ,
(2.10)
thì (u¯, v¯) − (O, v¯) = (u¯, O) ∈ Ex¯ . Như v¾y (u¯, O) ∈ Hu . Đieu
này dan tói mâu thuan. V¾y m¾nh đe đưoc chúng minh.
M®t h¾ quá trnc tiep cna M¾nh đe 2.1 là đieu ki¾n toi ưu cna x¯ có
the bieu dien qua moi quan h¾ giua các t¾p

vàH.

Ex¯
M¾nh đe 2.2. x¯ ∈ R là v.m.p cúa (2.1) khi và chs khi (2.7) thoá

mãn.
Nh¾n xét 2.1. Dưói các giá thiet thích hop ve tính loi suy r®ng trên
hàm Ax¯ (x) := (f (x¯) − f (x), g(x)) có the đám báo tính loi cna
t¾p ánh
mó r®ng Ex¯ . Đ¾c bi¾t, đieu này đưoc chí ra trong [13] rang
Ex¯
và chí khi
−Ax¯

là C × D-giong loi trên X.

là loi khi