1
0130
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
I HÅC THI NGUYN
TR×ÍNG I HÅC S× PHM
NGUYN THÀ HU
CC BI TON TÜA C
N BNG
TÊNG QUT V ÙNG DÖNG
LUN VN THC Sß TON HÅC
Th¡i Nguy¶n - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
I HÅC THI NGUYN
TR×ÍNG I HÅC S× PHM
NGUYN THÀ HU
CC BI TON TÜA C
N BNG
TÊNG QUT V ÙNG DÖNG
Chuy¶n ng nh: GII TCH
M¢ sè: 60.46.01
LUN VN THC Sß TON HÅC
Ng÷íi h÷îng d¨n khoa håc
GS.TSKH NGUYN XU
N TN
Th¡i Nguy¶n - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i
Möc löc
MÐ U
1 Mët sè ki¸n thùc chu©n bà
1.1
Mët sè khæng gian cì b£n . . . . . . . . . . . . . . . . .
1
4
4
1.1.1
Khæng gian metric . . . . . . . . . . . . . . . . .
4
1.1.2
Khæng gian ành chu©n . . . . . . . . . . . . . . .
5
1.1.3
Khæng gian Hilbert . . . . . . . . . . . . . . . . .
5
1.1.4
Khæng gian tæ pæ tuy¸n t½nh lçi àa ph÷ìng Haussdorff . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2
nh x¤ a trà v mët sè kh¡i ni»m li¶n quan . . . . . . .
7
1.3
Mët sè ành l½ iºm b§t ëng cì b£n . . . . . . . . . . .
10
2 B i to¡n tüa c¥n b¬ng têng qu¡t lo¤i I
2.1
°t b i to¡n v c¡c b i to¡n li¶n quan . . . . . . . . . .
11
11
2.1.1
°t b i to¡n . . . . . . . . . . . . . . . . . . . . .
11
2.1.2
C¡c b i to¡n li¶n quan . . . . . . . . . . . . . . .
12
2.2
ành l½ tçn t¤i nghi»m . . . . . . . . . . . . . . . . . . .
17
2.3
p döng cho c¡c b i to¡n li¶n quan . . . . . . . . . . . .
19
3 B i to¡n tüa c¥n b¬ng têng qu¡t lo¤i II
3.1
3.2
°t b i to¡n v c¡c b i to¡n li¶n quan . . . . . . . . . .
32
32
3.1.1
°t b i to¡n . . . . . . . . . . . . . . . . . . . . .
32
3.1.2
C¡c b i to¡n li¶n quan . . . . . . . . . . . . . . .
33
ành l½ tçn t¤i nghi»m . . . . . . . . . . . . . . . . . . .
36
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ii
3.3
p döng cho c¡c b i to¡n li¶n quan . . . . . . . . . . . .
KT LUN
T i li»u tham kh£o
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
49
51
http://www.lrc-tnu.edu.vn
1
MÐ U
Lþ thuy¸t tèi ÷u ¢ v ang thu hót ÷ñc sü quan t¥m r§t lîn cõa c¡c
nh to¡n håc tr¶n th¸ giîi. L½ thuy¸t n y ¢ th¥m nhªp v o r§t nhi·u
l¾nh vüc trong thüc t¸ v c¡c ng nh khoa håc k¾ thuªt kh¡c nhau.
Trong thüc ti¹n cuëc sèng ai công muèn cæng vi»c h ng ng y cõa
m¼nh ÷ñc ho n th nh mët c¡ch tèt nh§t, v t¼m ph÷ìng ¡n tèi ÷u º
thüc hi»n nâ. Nh÷ vªy, måi ng÷íi công ph£i gi£i c¡c b i to¡n tèi ÷u cõa
m¼nh theo mët ngh¾a n o â. V§n · quan trång nh§t °t ra èi vîi c¡c
b i to¡n nâi chung v b i to¡n tèi ÷u nâi ri¶ng: Vîi i·u ki»n n o b i
to¡n câ nghi»m, v n¸u câ nghi»m i·u g¼ s³ x£y ra? L½ thuy¸t tèi ÷u v²c
tì ÷ñc h¼nh th nh tø nhúng þ t÷ðng v· c¥n b¬ng kinh t¸, l½ thuy¸t gi¡
trà cõa Edgeworth tø n«m 1881 v Pareto tø n«m 1906. Cì sð to¡n håc
cõa l½ thuy¸t n y l nhúng khæng gian câ thù tü ÷a ra bði Cantor n«m
1897, Hausdorff n«m 1906, v nhúng ¡nh x¤ ìn trà công nh÷ a trà tø
mët khæng gian n y v o mët khæng gian câ thù tü kh¡c vîi nhúng t½nh
ch§t n o â. L½ thuy¸t trá chìi cõa Borel n«m 1921 v Von Neumann
n«m 1926, l½ thuy¸t v· l÷u thæng h ng hâa cõa Koopmans n«m 1947 l
nhúng cæng tr¼nh ¦u ti¶n trong l¾nh vüc n y. Nh÷ng ph£i nâi r¬ng cho
tîi nhúng n«m 1950 trð l¤i ¥y, sau nhúng cæng tr¼nh v· i·u ki»n c¦n
v õ cho tèi ÷u cõa Kuhn- Jucker n«m 1951, v· gi¡ trà c¥n b¬ng v
tèi ÷u Pareto cõa Deubreu n«m 1954, l½ thuy¸t tèi ÷u v²c tì mîi thüc
sü ÷ñc cæng nhªn l mët ng nh to¡n håc quan trång v câ nhi·u ùng
döng trong thüc t¸. Cho tîi nhúng n«m cuèi cõa th¸ k¿ 20, h ng tr«m
cuèn s¡ch v h ng ngh¼n b i b¡o vi¸t v· l¾nh vüc n y cung c§p cho ta
nhúng ph÷ìng ph¡p nghi¶n cùu v ùng döng trong nhúng l¾nh vüc kh¡c
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
nhau cõa c¡c ng nh khoa håc v k¾ thuªt công nh÷ thüc t¸.
¦u ti¶n ng÷íi ta nghi¶n cùu nhúng b i to¡n li¶n quan tîi ¡nh x¤ ìn
trà tø khæng gian Euclide câ sè chi·u húu h¤n n y sang khæng gian câ
sè chi·u húu h¤n kh¡c m thù tü trong nâ ÷ñc sinh ra bði nân orthan
d÷ìng. Trång t¥m l b i to¡n:
T¼m x̄ ∈ D º f (x̄) = min f (x)
x∈D
trong â f : D → R l h m sè, D l tªp con kh¡c réng cõa khæng gian
ành chu©n X . Tø b i to¡n n y vîi c§u tróc kh¡c nhau cõa tªp D v
t½nh ch§t cõa h m F , ng÷íi ta ph¥n lo¤i th nh nhi·u b i to¡n tèi ÷u
kh¡c nhau nh÷: qui ho¤ch tuy¸n t½nh, qui ho¤ch ph¥n tuy¸n, qui ho¤ch
to n ph÷ìng,...V sau â ph¡t triºn ra c¡c b i to¡n kh¡c nh÷:
- B i to¡n b§t ¯ng thùc bi¸n ph¥n Stampachia:
T¼m x̄ ∈ D sao cho hT (x̄), x − x̄i ≥ 0, ∀x ∈ D
trong â D ⊂ Rn , T : D → Rn .
- B i to¡n c¥n b¬ng Blum- Oettli:
T¼m x̄ ∈ D sao cho f (x, x̄) ≥ 0, ∀x ∈ D
trong â D l tªp lçi âng trong khæng gian v²c tì tæ pæ X , v f :
D × D → R l h m sè thäa m¢n f (x, x) = 0. B i to¡n n y bao gçm
nh÷ nhúng tr÷íng hñp °c bi»t c¡c b i to¡n: tèi ÷u, c¥n b¬ng Nash, b i
to¡n bò, b i to¡n b§t ¯ng thùc bi¸n ph¥n,...Rçi ti¸p töc mð rëng cho
c¡c b i to¡n trong khæng gian câ sè chi·u væ h¤n vîi nân b§t k¼. Vi»c
÷a ra kh¡i ni»m v chùng minh ÷ñc sü tçn t¤i cõa c¡c lo¤i iºm húu
hi»u cõa mët tªp hñp trong khæng gian câ thù tü sinh bði nân ¢ d¨n
tîi vi»c nghi¶n cùu c¡c b i to¡n tèi ÷u kh¡c nhau.
Sau â l½ thuy¸t n y ÷ñc ph¡t triºn cho nhúng b i to¡n li¶n quan
¸n ¡nh x¤ a trà trong khæng gian væ h¤n chi·u. Nhúng ành ngh¾a, t½nh
ch§t, sü ph¥n lîp,... c¡c ¡nh x¤ ìn trà d¦n d¦n ÷ñc mð rëng cho ¡nh
x¤ a trà. Berge ¢ ÷a ra c¡c kh¡i ni»m kh¡c nhau cõa ¡nh x¤ a trà.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
â l t½nh nûa li¶n töc tr¶n, nûa li¶n töc d÷îi cõa ¡nh x¤ a rà. T÷ìng
tü kh¡i ni»m lçi tr¶n, lçi d÷îi, Lipshitz tr¶n, Lipshitz d÷îi, t½nh kh£ vi,
kh£ d÷îi vi ph¥n,... công ÷ñc ÷a ra. Tø nhúng kh¡i ni»m n y ng÷íi
ta t¼m ÷ñc nhúng i·u ki»n c¦n v õ kh¡c nhau cho c¡c b i to¡n tèi
÷u, v công x¥y düng ÷ñc l½ thuy¸t tèi ÷u cho nhi·u lîp b i to¡n nh÷
lçi, Lipshitz,...Rçi mð rëng k¸t qu£ cho c¡c b i to¡n tüa nh÷: b i to¡n
tüa tèi ÷u, b i to¡n tüa c¥n b¬ng,...
Möc ½ch cõa luªn v«n l tr¼nh b y i·u ki»n õ cho sü tçn t¤i nghi»m
cõa b i to¡n tüa c¥n b¬ng têng qu¡t lo¤i I v b i to¡n tüa c¥n b¬ng têng
qu¡t lo¤i II. çng thíi nghi¶n cùu mèi quan h» giúa hai b i to¡n n y
vîi mët sè b i to¡n kh¡c nh÷ b i to¡n bao h m thùc tüa bi¸n ph¥n, b i
to¡n quan h» tüa bi¸n ph¥n,...Tø â cho ta c¡ch nh¼n bao qu¡t v· mèi
quan h» giúa c¡c b i to¡n kh¡c nhau trong l½ thuy¸t tèi ÷u v²c tì.
Luªn v«n gçm ph¦n mð ¦u, ba ch÷ìng v t i li»u tham kh£o. Cö
thº l
Ch÷ìng 1: Mët sè ki¸n thùc chu©n bà
Ch÷ìng 2: B i to¡n tüa c¥n b¬ng têng qu¡t lo¤i I
Ch÷ìng 3: B i to¡n tüa c¥n b¬ng têng qu¡t lo¤i II
Cuèi còng, tæi xin b y tä láng bi¸t ìn s¥u sc tîi th¦y gi¡o GS. TSKH
Nguy¹n Xu¥n T§n, ng÷íi ¢ tªn t¼nh h÷îng d¨n, t¤o måi i·u ki»n gióp
ï tæi ho n th nh luªn v«n n y. Tæi xin ch¥n th nh c£m ìn Ban chõ
nhi»m Khoa Sau ¤i håc, Ban chõ nhi»m Khoa To¡n Tr÷íng H S÷
ph¤m H Th¡i Nguy¶n còng c¡c th¦y gi¡o, cæ gi¡o ¢ tham gia gi£ng
d¤y kho¡ håc, xin ch¥n th nh c£m ìn gia ¼nh, b¤n b±, çng nghi»p v
c¡c b¤n còng lîp cao håc To¡n K17 ¢ luæn quan t¥m, ëng vi¶n v gióp
ï tæi trong suèt thíi gian håc tªp v l m luªn v«n.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
Ch֓ng 1
Mët sè ki¸n thùc chu©n bà
Trong ch÷ìng n y tr¼nh b y mët sè ki¸n thùc v· c¡c khæng gian th÷íng
dòng, ¡nh x¤ a trà v mët sè t½nh ch§t cõa nâ düa tr¶n t i li»u [6].
1.1 Mët sè khæng gian cì b£n
Trong to¡n håc hay b§t k¼ mët ng nh khoa håc n o kh¡c, mët b i
to¡n ÷ñc °t ra bao gií công gn vîi mët khæng gian n o â. V¼ vªy
vi»c nghi¶n cùu to¡n håc nâi chung, v nhúng b i to¡n cö thº trong to¡n
håc nâi ri¶ng, tr÷îc h¸t ta ph£i quan t¥m tîi c¡c khæng gian cõa b i
to¡n. Méi b i to¡n ph£i gn vîi mët hay nhi·u khæng gian nh§t ành.
Trong ch÷ìng n y ta nhc l¤i nhúng khæng gian cì b£n m trong c¡c
ch÷ìng sau cõa luªn v«n th÷íng · cªp ¸n.
1.1.1 Khæng gian metric
ành ngh¾a 1.1.
a) Vîi méi c°p ph¦n tû x, y cõa tªp hñp X ·u câ x¡c ành theo mët qui
tc n o â, mët sè thüc ρ(x, y),, gåi l kho£ng c¡ch giúa x v y;
b) Qui tc nâi tr¶n thäa m¢n c¡c i·u ki»n sau ¥y:
(i) ρ(x, y) > 0, n¸u x 6= y; ρ(x, y) = 0, n¸u x = y;
(ii) ρ(x, y) = ρ(y, x), ∀x, y;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
(iii) ρ(x, y) ≤ ρ(x, z) + ρ(z, y), ∀x, y, z.
H m sè ρ(x, y) ÷ñc gåi l metric cõa khæng gian X , v (X, ρ) ÷ñc
gåi l khæng gian metric.
1.1.2 Khæng gian ành chu©n
ành ngh¾a 1.2. Khæng gian tuy¸n t½nh ành chu©n l c°p (X, k.k),
trong â X l khæng gian tuy¸n t½nh cán k.k l mët ¡nh x¤ X → R thäa
m¢n
(i) ∀x ∈ X , k x k≥ 0 v k x k = 0 khi v ch¿ khi x = 0;
(ii) ∀x, y ∈ X , k x + y k≤k x k + k y k;
(iii) ∀x ∈ X , ∀λ ∈ K , k λx k =k λ kk x k.
1.1.3 Khæng gian Hilbert
ành ngh¾a 1.3. Cho X l khæng gian tuy¸n t½nh tr¶n tr÷íng K
{R, C}.
H m sè h., .i : X × X
→K
÷ñc gåi l t½ch væ h÷îng tr¶n
=
X
n¸u
(i) hy, xi = hx, yi, ∀x, y ∈ X . ( k½ hi»u hx, yi ch¿ sè phùc li¶n hñp cõa sè
phùc hy, xi);
(ii) hx + y, zi = hx, zi + hy, zi, ∀x, y ∈ X;
(iii) hλx, zi = λhx, zi, ∀λ ∈ K;
(iv) hx, xi ≥ 0; hx, xi = 0 ⇔ x = 0.
Khæng gian X ÷ñc trang bà t½ch væ h÷îng gåi l khæng gian ti·n
Hilbert.
Trong khæng gian ti·n Hilbert ta luæn câ b§t ¯ng thùc CauchySchwarz sau
| hx, yi |2 ≤ hx, xi.hy, yi, ∀x, y ∈ X.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
Thªt vªy, câ thº gi£ thi¸t y 6= 0, λ ∈ K ta câ hx + λy, x + λyi ≥ 0.
Cho n¶n
hx, xi + λhy, xi + λ̄hx, yi + λ2 hy, yi ≥ 0.
°t λ = − hx,yi
hy,yi , khi â
hx, xi −
| hx, yi |2
≥ 0.
hy, yi
Tø â ta suy ra hx, xi.hy, yi ≥| hx, yi |2 . Ta câ i·u c¦n chùng minh.
p
Tø b§t ¯ng thùc Cauchy-Schwarz ta câ kxk = hx, xi l mët chu©n
trong khæng gian X. Khæng gian ti·n Hilbert l mët khæng gian ành
chu©n. Do â, tr¶n â câ thº ành ngh¾a d¢y Cauchy v t½nh ¦y õ. Vªy
ta câ ành ngh¾a sau.
ành ngh¾a 1.4. Khæng gian ti·n Hilbert ¦y õ gåi l khæng gian
Hilbert
1.1.4 Khæng gian tæ pæ tuy¸n t½nh lçi àa ph÷ìng Haussdorff
ành ngh¾a 1.5. Cho tªp hñp X , gåi τ l c¡c tªp con cõa X . Khi â
÷ñc gåi l khæng gian tæpæ n¸u c¡c i·u ki»n sau ÷ñc thäa m¢n
(i) ∅ ∈ τ , X ∈ τ ;
(ii) Vîi {Ut}t∈T ⊂ τ th¼ t∈T
∪ Ut ∈ τ ;
(iii) Vîi ∀U1, U2 ∈ τ th¼ U1 ∩ U2 ∈ τ .
X
Mët khæng gian tuy¸n t½nh thüc hay phùc câ thº çng thíi ÷ñc trang
bà mët c§u tróc tæ pæ v mët c§u tróc ¤i sè (ph²p cëng hai ph¦n tû v
ph²p nh¥n mët sè vîi mët ph¦n tû). Khi §y ta câ mët khæng gian vøa
tuy¸n t½nh vøa tæ pæ. V§n · ¡ng chó þ l hai c§u tróc â câ quan h»
vîi nhau nh÷ th¸ n o º khæng gian n£y sinh ra nhi·u t½nh ch§t mîi. Ta
câ ành ngh¾a sau.
ành ngh¾a 1.6. Ta nâi r¬ng mët tæ pæ τ phò hñp vîi c§u tróc ¤i sè
trong khæng gian X , n¸u c¡c ph²p t½nh ¤i sè trong X li¶n töc trong tæ
pæ τ , tùc l n¸u:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
(i) x + y l mët ¡nh x¤ li¶n töc cõa hai bi¸n x, y; nâi rã hìn, vîi måi l¥n
cªn V cõa iºm x + y ·u tçn t¤i l¥n cªn Ux cõa x v l¥n cªn Uy cõa y
sao cho n¸u x0 ∈ Ux, y0 ∈ Uy th¼ x0 + y0+ ∈ V .
(ii) αx l ¡nh x¤ li¶n töc cõa hai bi¸n α, x; nâi rã hìn, vîi måi l¥n cªn
V cõa αx ·u câ mët sè > 0 v mët l¥n cªn U cõa x sao cho n¸u
|α0 − α| < , x0 ∈ U th¼ α0 x0 ∈ V.
Khæng gian tuy¸n t½nh X tr¶n â câ mët tæ pæ t÷ìng th½ch vîi c§u
tróc ¤i sè ÷ñc gåi l khæng gian tæ pæ tuy¸n t½nh.
ành ngh¾a 1.7. Khæng gian tæpæ tuy¸n t½nh X ÷ñc gåi l khæng gian
lçi àa ph÷ìng n¸u måi ph¦n tû cõa X câ cì sð l¥n cªn th nh lªp tø c¡c
tªp lçi. Hay t÷ìng ÷ìng, ph¦n tû 0 ∈ X câ cì sð l¥n cªn th nh lªp tø
c¡c tªp lçi.
ành ngh¾a 1.8. Khæng gian tæ pæ (X, τ ) ÷ñc gåi l khæng gian Haussdorff n¸u vîi méi x, y ∈ X, x 6= y bao gií công tçn t¤i l¥n cªn Ux cõa x
v Uy cõa y thäa m¢n Ux ∩ Uy = ∅.
1.2 nh x¤ a trà v mët sè kh¡i ni»m li¶n quan
Ph¦n n y tr¼nh b y ành ngh¾a v· ¡nh x¤ a trà, t½nh li¶n töc v t½nh
lçi theo nân cõa ¡nh x¤ a trà. V º thuªn ti»n cho vi»c theo dãi c¡c
chùng minh ð ch÷ìng 2 v ch÷ìng 3 chóng ta s³ ÷a ra mët sè ành
ngh¾a li¶n quan ¸n ¡nh x¤ KKM.
Trong c¡c ành ngh¾a d÷îi ¥y chóng ta luæn gi£ sû X, Y, Z, W l
c¡c khæng gian tæ pæ tuy¸n t½nh, lçi àa ph÷ìng, Haussdorff. D ⊂ X ,
K ⊂ Z , E ⊂ W l c¡c tªp con kh¡c réng v C l nân trong Y .
Tr÷îc h¸t ta câ ành ngh¾a v· ¡nh x¤ a trà nh÷ sau.
ành ngh¾a 1.9. K½ hi»u 2Y l tªp t§t c£ c¡c tªp con cõa Y .
nh x¤ F : X → 2Y m ùng vîi méi x ∈ X cho mët tªp con cõa Y
÷ñc gåi l ¡nh x¤ a trà.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
ành ngh¾a 1.10. Cho F : D → 2Y l ¡nh x¤ a trà.
l C − li¶n töc tr¶n (ho°c C − li¶n töc d÷îi) t¤i x0 ∈ D n¸u vîi
b§t k¼ l¥n cªn V cõa 0 trong Y ·u tçn t¤i l¥n cªn U cõa x0 trong X
sao cho
•F
F (x) ⊂ F (x0 ) + V + C
(ho°c F (x0 ) ⊂ F (x) + V − C)
vîi måi x ∈ U ∩ domf .
• F l C − li¶n töc t¤i x0 ∈ D n¸u F vøa l C − li¶n töc tr¶n v vøa
l C − li¶n töc d÷îi t¤i x0.
• F l C − li¶n töc tr¶n, C − li¶n töc d÷îi, ho°c C − li¶n töc tr¶n
D n¸u nâ l C − li¶n töc tr¶n, C − li¶n töc d÷îi, ho°c C − li¶n töc t¤i
∀x ∈ D.
• F l C − lãm tr¶n (ho°c C − lãm d÷îi) n¸u
αF (x) + (1 − α)F (y) ⊂ F (αx + (1 − α)y) − C
(ho°c F (αx + (1 − α)y) ⊂ αF (x) + (1 − α)F (y) + C)
vîi ∀x, y ∈ domF v α ∈ [0, 1].
• F l C − tüa lçi tr¶n tr¶n D n¸u vîi b§t k¼ x1 , x2 ∈ D, t ∈ [0, 1] ta
câ
F (x1 ) ⊆ F (tx1 + (1 − t)x2 ) + C
(ho°c F (x2 ) ⊆ F (tx1 + (1 − t)x2 ) + C.
câ
•F
l C − tüa lçi d÷îi tr¶n D n¸u vîi b§t k¼ x1, x2 ∈ D, t ∈ [0, 1] ta
F (tx1 + (1 − t)x2 )F (x1 ) ⊆ F (x1 ) − C
(ho°c F (tx1 + (1 − t)x2 ) ⊆ F (x2 ) − C.
ành ngh¾a 1.11. Cho F : K × D × D → 2Y , Q : D × D → 2K l c¡c
¡nh x¤ a trà. Cho C : K × D → 2Y l ¡nh x¤ a trà nân.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
÷ñc gåi l (Q, C) − tüa lçi tr¶n theo ÷íng ch²o èi vîi bi¸n thù
ba n¸u vîi b§t k¼ tªp húu h¤n {x1, x2, ..., xn} ⊆ D, x ∈ co{x1, x2, ..., xn},
câ j ∈ {1, 2, ..., n} sao cho
•F
F (y, x, xj ) ⊆ F (y, x, x) + C(y, x), ∀y ∈ Q(x, xj ).
÷ñc gåi l (Q, C) − tüa lçi d÷îi theo ÷íng ch²o èi vîi bi¸n thù
ba n¸u vîi b§t k¼ tªp húu h¤n {x1, x2, ..., xn} ⊆ D, x ∈ co{x1, x2, ..., xn},
câ j ∈ {1, 2, ..., n} sao cho
•F
F (y, x, x) ⊆ F (y, x, xj ) − C(y, x), ∀y ∈ Q(x, xj ).
ành ngh¾a 1.12. nh x¤ a trà F
vîi
b§t k¼ tªp húu h¤n
n
: D → 2X
{t1 , t2 , ..., tn } ⊂ D, d¨n
÷ñc gåi l KKM n¸u
¸n co{t1, t2, ..., tn} ⊆
∪ F (tj ).
j=1
ành ngh¾a 1.13. Cho F
: K × D × D → 2X , Q : D × D → 2K l
c¡c ¡nh x¤ a trà. F ÷ñc gåi l Q − KKM n¸u vîi b§t k¼ tªp húu h¤n
{t1 , t2 , ..., tn } ⊂ D v x ∈ co{t1 , t2 , ..., tn }, câ tj ∈ {t1 , t2 , ..., tn } sao cho
0 ∈ F (y, x, tj ), ∀y ∈ Q(x, tj ).
ành ngh¾a 1.14. Cho F : K × D × E → 2X , Q : D × E → 2K l c¡c
¡nh x¤ a trà. F ÷ñc gåi l Q − KKM têng qu¡t n¸u vîi b§t k¼ tªp húu
h¤n {t1, t2, ..., tn} ⊂ E câ mët tªp húu h¤n {x1, x2, ..., xn} ⊂ D º vîi b§t
k¼ x ∈ co{xi , xi , ..., xi }, câ ti ∈ {ti , ti , ..., ti } sao cho 0 ∈ F (y, x, tj ),
∀y ∈ Q(x, ti ).
ành ngh¾a 1.15. Cho R l quan h» hai ngæi tr¶n K × D. Chóng ta nâi
r¬ng R l âng n¸u vîi b§t k¼ d¢y suy rëng (yα, xα) → (y, x) v R(yα, xα)
x£y ra vîi måi α th¼ R(y, x) x£y ra.
ành ngh¾a 1.16. Cho R l quan h» tr¶n K × D × D. Chóng ta nâi
r¬ng R l Q − KKM n¸u vîi b§t k¼ tªp húu h¤n {t1, t2, ..., tn} ⊂ D v
x ∈ co{t1 , t2 , ..., tn } câ tj ∈ {t1 , t2 , ..., tn } sao cho R(y, x, tj ) x£y ra, vîi
måi y ∈ Q(x, tj ).
1
2
k
j
1
2
n
j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
1.3 Mët sè ành l½ iºm b§t ëng cì b£n
Ph¦n n y tr¼nh b y nëi dung cõa hai ành l½ iºm b§t ëng cì b£n l
ành l½ Park v ành l½ Browder- KyFan.
ành lþ 1.17. (Park [4]) Cho X l khæng gian tæ pæ tuy¸n t½nh lçi
àa ph÷ìng,
l tªp con lçi, ch§p nhªn ÷ñc, kh¡c réng cõa X v
F : D → 2D l ¡nh x¤ a trà com pc acyclic vîi gi¡ trà kh¡c réng. Th¼
∃x̄ ∈ D sao cho x̄ ∈ F (x̄).
ành lþ 1.18. (Browder- KyFan [8]) Cho D l tªp con kh¡c réng, lçi,
compc cõa X v F : D → 2D l ¡nh x¤ a trà thäa m¢n c¡c i·u ki»n
d÷îi ¥y
(i) ∀x ∈ D, x 6∈ F (x) v F (x) l lçi;
(ii) ∀y ∈ D, F −1(y) l mð trong D.
Th¼ ∃x̄ ∈ D sao cho F (x̄) = ∅.
D
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
Ch֓ng 2
B i to¡n tüa c¥n b¬ng têng qu¡t
lo¤i I
Trong ch÷ìng n y tr¼nh b y b i to¡n tüa c¥n b¬ng têng qu¡t lo¤i I
v i·u ki»n tçn t¤i nghi»m cõa nâ. çng thíi ¡p döng b i to¡n n y º
chùng minh mët sè b i to¡n li¶n quan nh÷ b i to¡n quan h» tüa bi¸n
ph¥n lo¤i I, b i to¡n bao h m thùc tüa bi¸n ph¥n lo¤i I,v.v... düa tr¶n
t i li»u [7]
2.1 °t b i to¡n v c¡c b i to¡n li¶n quan
2.1.1 °t b i to¡n
Cho X, Y, Z l c¡c tªp kh¡c réng. D ⊆ X , K ⊆ Z l c¡c tªp con kh¡c
réng. Gi£ sû
S : D × K → 2D , T : D × K → 2K , F : K × D × D × D → 2Y
l c¡c ¡nh x¤ a trà vîi gi¡ trà kh¡c réng.
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ 0 ∈ F (ȳ, x̄, x̄, z), ∀z ∈ S(x̄, ȳ)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
÷ñc gåi l b i to¡n tüa c¥n b¬ng têng qu¡t lo¤i I, k½ hi»u (GQEP )I .
Trong â c¡c ¡nh x¤ a trà S, T l r ng buëc v F l ¡nh x¤ a trà
th÷íng ÷ñc x¡c ành bði ¯ng thùc v b§t ¯ng thùc, ho°c bði c¡c bao
h m thùc v sü t÷ìng giao cõa c¡c ¡nh x¤ a trà.
2.1.2 C¡c b i to¡n li¶n quan
D÷îi ¥y l c¡c b i to¡n m ta câ thº ÷a v· b i to¡n (GQEP )I b¬ng
c¡ch x¡c ành ¡nh x¤ F th½ch hñp.
1) B i to¡n tüa tèi ÷u lo¤i I
Cho D, K, S, T nh÷ trong ph¦n 2.1.1. Gi£ sû G : K × D × D → R l
h m sè.
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ G(ȳ, x̄, x̄) = min G(ȳ, x̄, z),
z∈S(x̄,ȳ)
÷ñc gåi l b i to¡n tüa tèi ÷u lo¤i I ¢ ÷ñc A. Guerraggio v N. X.
T§n x²t trong [1].
Ta th§y r¬ng (GQEP )I l t÷ìng ÷ìng vîi b i to¡n tr¶n, v¼ n¸u ta
x¡c ành c¡c ¡nh x¤ a trà
M : K × D × D → 2X , F : K × D × D × D → 2X
nh÷ sau
M (y, x, z) = {t ∈ D | G(y, x, z) ≥ G(y, x, t)}, (y, x, z) ∈ K × D × D;
F (y, x, t, z) = t − M (y, x, z), (y, x, t, z) ∈ K × D × D × D.
Th¼ i·u ki»n
0 ∈ F (ȳ, x̄, x̄, z), ∀z ∈ S(x̄, ȳ),
s³ trð th nh
G(ȳ, x̄, x̄) = min G(ȳ, x̄, z).
z∈S(x̄,ȳ)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
2) B i to¡n tüa c¥n b¬ng væ h÷îng
Cho D, K, S, T nh÷ trong ph¦n 1). Gi£ sû g : K × D × D → R l
h m sè vîi g(y, x, x) = 0, ∀x ∈ D, y ∈ K .
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ g(ȳ, x̄, z) ≥ 0, ∀z ∈ S(x̄, ȳ).
÷ñc gåi l b i to¡n tüa c¥n b¬ng væ h÷îng, mð rëng cõa c¡c lo¤i b i
to¡n cê iºn cõa Stampachia v Minty ¢ ÷ñc A. Guerraggio v N. X.
T§n x²t trong [1].
B¬ng c¡ch x¡c ành c¡c ¡nh x¤ a trà
M : K × D × D → 2X , F : K × D × D × D → 2X
nh÷ sau
M (y, x, z) = {t ∈ D | g(y, x, z) ≥ g(y, x, t)}, (y, x, z) ∈ K × D × D;
F (y, x, t, z) = t − M (y, x, z), (y, x, t, z) ∈ K × D × D × D.
Th¼ b i to¡n (GQEP )I s³ trð th nh b i to¡n tr¶n v¼ khi â i·u ki»n
0 ∈ F (ȳ, x̄, x̄, z), ∀z ∈ S(x̄, ȳ),
l t÷ìng ÷ìng vîi i·u ki»n
g(ȳ, x̄, z) ≥ 0, ∀z ∈ S(x̄, ȳ).
3) B i to¡n quan h» tüa bi¸n ph¥n
Cho D, K, S, T nh÷ trong ph¦n 1). Gi£ sû R(y, x, t, z) l quan h» giúa
y ∈ K; x, t, z ∈ D. R l quan h» th÷íng cho bði ¯ng thùc, b§t ¯ng
thùc cõa h m sè, ho°c bði bao h m thùc, sü t÷ìng giao cõa c¡c ¡nh x¤
a trà.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ R(ȳ, x̄, x̄, z) x£y ra, ∀z ∈ S(x̄, ȳ)
÷ñc gåi l b i to¡n quan h» tüa bi¸n ph¥n lo¤i I v ÷ñc . T. Löc x²t
trong [5].
B i to¡n n y t÷ìng ÷ìng vîi b i to¡n (GQEP )I . V¼ n¸u ta x¡c ành
c¡c ¡nh x¤ a trà
M : K × D × D → 2X , F : K × D × D × D → 2X
nh÷ sau
M (y, x, z) = {t ∈ D | R(y, x, t, z) x£y ra}, (y, x, z) ∈ K × D × D;
F (y, x, t, z) = t − M (y, x, z), (y, x, t, z) ∈ K × D × D × D.
Th¼ hai i·u ki»n
R(ȳ, x̄, x̄, z) x£y ra , ∀z ∈ S(x̄, ȳ),
v
0 ∈ F (ȳ, x̄, x̄, z), ∀z ∈ S(x̄, ȳ)
l t÷ìng ÷ìng vîi nhau.
4) B i to¡n bao h m thùc tüa bi¸n ph¥n l½ t÷ðng tr¶n lo¤i I
Cho D, K, S, T nh÷ trong ph¦n 1). Gi£ sû H, G l c¡c ¡nh x¤ a trà
tr¶n K × D × D vîi gi¡ trà trong Y . Cho C : K × D → 2Y l ¡nh x¤ a
trà vîi gi¡ trà nân, lçi, âng kh¡c réng.
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ H(ȳ, x̄, z) ⊂ G(ȳ, x̄, x̄) + C(ȳ, x̄), ∀z ∈ S(x̄, ȳ).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
15
÷ñc gåi l b i to¡n bao h m thùc tüa bi¸n ph¥n l½ t÷ðng tr¶n lo¤i I, ¢
÷ñc C. J. Lin v N. X. T§n x²t trong [2].
Rã r ng (GQEP )I s³ trð th nh b i to¡n tr¶n n¸u ta x¡c ành c¡c
¡nh x¤ a trà
M : K × D × D → 2X , F : K × D × D × D → 2X
nh÷ sau
M (y, x, z) = {t ∈ D | H(y, x, z) ⊆ G(y, x, t)+C(y, x)}, (y, x, z) ∈ K×D×D;
F (y, x, t, z) = t − M (y, x, z), (y, x, t, z) ∈ K × D × D × D.
Th¼ khi â i·u ki»n
H(ȳ, x̄, z) ⊂ G(ȳ, x̄, x̄) + C(ȳ, x̄), ∀z ∈ S(x̄, ȳ),
t÷ìng ÷ìng vîi i·u ki»n
0 ∈ F (ȳ, x̄, x̄, z), ∀z ∈ S(x̄, ȳ).
5) B i to¡n bao h m thùc tüa c¥n b¬ng l½ t÷ðng tr¶n
Cho D, K, S, T nh÷ trong ph¦n 1). Gi£ sû G : K × D × D → 2Y l
¡nh x¤ a trà vîi gi¡ trà kh¡c réng v C : K × D → 2Y l ¡nh x¤ vîi gi¡
trà nân, lçi kh¡c réng sao cho G(y, x, x) ⊆ C(y, x), ∀(y, x, x) ∈ K×D×D.
B i to¡n: t¼m (x̄, ȳ) ∈ D × K sao cho
1/ x̄ ∈ S(x̄, ȳ);
2/ ȳ ∈ T (x̄, ȳ);
3/ G(ȳ, x̄, z) ⊂ C(ȳ, x̄), ∀z ∈ S(x̄, ȳ).
÷ñc gåi l b i to¡n bao h m thùc tüa bi¸n ph¥n l½ t÷ðng tr¶n lo¤i I ¢
÷ñc C. J. Lin v N. X. T§n x²t trong [2].
Ta th§y r¬ng (GQEP )I s³ trð th nh b i to¡n tr¶n n¸u ta x¡c ành
c¡c ¡nh x¤ a trà
M : K × D × D → 2X , F : K × D × D × D → 2X
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -
.PDF 
56 
377 
107 
