TRƯỜNG ĐẠI HỌC CẦN THƠ
TRƯ
KHOA SƯ PHẠM
BỘ MÔN SP TOÁN HỌC
------------

LU
LUẬN
VĂN TỐT NGHIỆP

Đề tài:

SỰ
Ự ĐẶT CHỈNH NGHIỆM CỦA BÀI
BÀI TOÁN
CÂN BẰNG
ẰNG VÀ
V CÁC VẤN ĐỀ LIÊN
ÊN QUAN

Giáo viên hướng
ớng dẫn
TS. Lâm Quốc Anh

Sinh viên thực
ực hiện
Phùng Thị Thùy Trang
MSSV:: 1100073
Lớp: SP Toán học K36

Cần Thơ, 2014


Tập hợp số vô tỉ
Tập số thực mở rộng
Dãy {xn } hội tụ về phần tử x0

d (x, y )

Khoảng cách giữa điểm x và điểm y

d (x, M )

Khoảng cách giữa điểm x và tập M

diam M

Đường kính của tập M

:

⟶

Ánh xạ đơn trị từ tập X vào tập L

:

⟶2

Ánh xạ đa trị từ tập X vào tập Y

grS



PHẦN MỞ ĐẦU
1. Lí do chọn đề tài
Một trong những hướng nghiên cứu phát triển mạnh và có nhiều ứng dụng
trong thực tế trong giai đoạn hiện nay là Tối ưu hoá. Một trong những bài
toán trọng yếu của lý thuyết này là bài toán cân bằng. Mô hình bài toán cân
bằng được đưa ra vào năm 1994 bởi hai nhà toán học Blum và Oettly, bài
toán này chứa nhiều bài toán quan trọng trong tối ưu hoá như, bài toán bất
đẳng thức biến phân, bài toán tối ưu, bài toán bù, lý thuyết trò chơi, bài toán
cân bằng mạng giao thông,…. Cho đến nay đã có nhiều công trình nghiên
cứu về bài toán cân bằng, các kết quả nghiên cứu tập trung vào các chủ đề
trọng điểm như điều kiện tồn tại nghiệm, tính ổn định nghiệm, thuật toán tìm
nghiệm. Sự đặt chỉnh nghiệm của bài toán là chủ đề có mối liên hệ mật thiết
với tính ổn định nghiệm và thuật toán giải nghiệm và do đó có định hướng
ứng dụng rất cao. Với mong muốn tìm hiểu một lĩnh vực mới mẽ và có nhiều
khả năng phát triển trong thời gian tới, nên chúng tôi chọn đề tài “Sự đặt
chỉnh nghiệm của bài toán cân bằng và các vấn đề liên quan”, với ming
muốn là tiền đề cho sự học tập tiếp nối của bản thân trong giai đoạn tiếp
theo.
2. Mục đích nghiên cứu
+ Thông qua việc nghiên cứu đề tài này, tôi mong muốn giới thiệu một phần
cơ sở lí thuyết nghiên cứu sự đặt chỉnh của bài toán cân bằng, bài toán tối ưu
với mục đích giúp các bạn sinh viên trong quá trình nghiên cứu cũng như học
tập tốt hơn.
+ Qua đó cũng để tạo nền tảng kiến thức để tôi có thể học tập và nghiêm cứu
về sau.
3. Nội dung nghiên cứu
Luận văn này xoay quanh nghiên cứu về mô hình và ứng dụng của bài toán
cân bằng, ánh xạ đa trị, ánh xạ đơn trị, lí thuyết sự đặt chỉnh, và nghiên cứu

KIẾN THỨC BỔ TRỢ

1.1 Không gian mêtric
1.1.1 Định nghĩa không gian mêtric
Định nghĩa 1.1.1 Cho tập X   , một ánh xạ

:

×

⟶ ℝ được gọi là một

mêtric trên X nếu các điều kiện sau thỏa mãn với mọi x , y , z  X :
(i)

d ( x , y )  0,
d ( x , y )  0  x  y;

(ii) d ( x, y )  d(y, x);
(iii) d ( x , y )  d ( x , z )  d(z, y).
Nếu X được trang bị mêtric d thì ta gọi cặp ( X , d ) là một không gian mêtric. Khi
ấy,
+ Mỗi phần tử của X được gọi là một điểm của không gian ( X , d ) .
+ d ( x , y ) là khoảng cách giữa hai điểm x và y.

1.1.2 Khoảng cách giữa điểm và tập hợp, giữa tập hợp và tập hợp
Định nghĩa 1.1.2 Trong không gian mêtric ( , ), xét điểm x và tập
đó, khoảng cách từ x đến

được định nghĩa là:

}⊂

được gọi là hội tụ (theo mêtric d ) về

nếu
lim

→

(

) = 0.

,

Hay
∀ > 0, ∃
Kí hiệu: lim

=

→

⟹ (

∈ ℕ: ∀ ≥
⟶

hoặc



Nói cách khác,
∀ > 0, ∃

∈ ℕ: ∀ ,

⟹ (

≥

,

)< .

* Các tính chất:
+ Nếu dãy {

} hội tụ thì nó là dãy Cauchy.

+ Nếu dãy {

} là dãy Cauchy và có dãy con

hội tụ về

hội tụ về

thì {

} cũng


của

.

gọi là tập bị chặn nếu đường kính của
( ) = sup{ ( , ): ,

- Tập con
điểm

đều có một dãy

của

∈ } < ∞.

gọi là tập hoàn toàn bị chặn nếu mọi

,

,

…,

∈

ℎ

⊂⋃

( , ).
Nếu chỉ ký hiệu không gian tôpô là
một tôpô nào đó.

thì ta ngầm hiểu rằng trên

5

đã được trang bị


1.2.2 Không gian tôpô compact
* Các định nghĩa
- Trên không gian tôpô , cho ⊂ và { } ∈ là họ các tập con của . Khi đó,
{ } ∈ được gọi là phủ của nếu ⋃ ∈
⊃ . Nếu Ga là các tập mở thì phủ gọi
là phủ mở của .
được gọi là không gian compact nếu mọi phủ mở của đều
tồn tại một phủ con hữu hạn. Tức là với mọi phủ mở { } ∈ của đều tồn tại hữu
- Không gian tôpô
hạn các chỉ số
- Tập con
tôpô trên

( = 1,2, … , ) sao cho ⋃

∈

được gọi là tập compact nếu



∈ }

tức là cận trên đúng của các khoảng cách giữa các điểm thuộc A.
* Các tính chất:
Tính chất 1:
Giả sử A là tập con của không gian mêtric ( , )
Khi đó:

( )=

( ̅ ).

Chứng minh:
Vì

⊂ ̅, ta có

( )≤

( ̅)

6


> 0. Khi đó, lấy

Giả sử

∈ ̅ sao cho:


)+ ( ,

( )≥ ( ,

Do đó:

)+ (

)≥ ( ,

)−

)+

2
3

( ̅) −

≥

> 0 , ta có:

Vì điều này đúng với mọi

( ̅ ).

( )≥
( ̅ ).

Chọn lân cận:
(Với

=( ( ,

)− , ( ,

=

( , )≤ ( ,

×

⊂

. Với

)+ ( ,

Suy ra: ( , ) − ( ,
( ,

× .

) + ) của

( ,

)



)< ( , )+


Do đó, | ( , ) − ( ,

)|

1.5 Ánh xạ đa trị
Định nghĩa 1.5.1 Ánh xạ đa trị F từ tập X vào tập Y, kí hiệu
phép cho tương ứng mỗi phần tử
( ).

∈

với một tập con của

:

⟶ 2 , là một

, mà ta ký hiệu là

Ánh xạ đa trị còn có các tên gọi khác như: Hàm đa trị hay ánh xạ điểm vào tập.
Nếu với mỗi ∈ , tập ảnh
xạ đơn trị từ X vào Y.

( ) chỉ gồm một phần tử của Y , thì ta nói F là ánh

Định nghĩa 1.5.2 Cho ánh xạ đa trị

:

⟶ 2 , miền hiệu quả của F, kí hiệu là

domF, được xác định như sau:

8

compact,...

1.6 Độ đo không compact
Định nghĩa 1.6.1 Cho M là tập con khác rỗng của không gian mêtric X.
(i) Độ đo Kuratowski của M là
n

  M   inf {   0 | M   M k và diam M k   , k  1,..., n, với

∈

}.

k 1

(ii) Độ đo Hausdorff của M là
n

  M   inf {   0 | M   B  xk ,  , xk  X , với

∈

}.

k 1

(i)

Độ đo Istratescu của M là:
  M   inf   0 | M không có vô hạn  -rời rạc tập con}.

⟶ ℝ là tựa nửa

liên tục dưới. Thì ( , ) được gọi là đặt chỉnh Tykhonov nếu:
(i)
Tồn tại duy nhất ∈ sao cho ( ) ≤ ( ), ∀ ∈ ;
(ii)
Mọi dãy { } ta có ( ) ⟶ inf khi
⟶ ̅.

1.8 Các khái niệm và tính chất của ánh xạ nửa liên tục.
Định nghĩa 1.8.1 Cho X là không gian tôpô, x0  X và :

⟶ ℝ.

a) f được gọi là nửa liên tục trên, viết ngắn gọn là usc tại x0 nếu mọi dãy  xn 
hội tụ đến x0 thì
f ( x0 )  lim sup f ( xn ) ,

b) f được gọi là nửa liên tục dưới, viết ngắn gọn là lsc tại x0 nếu mọi dãy  xn 
hội tụ đến x0 thì
f ( x0 )  lim inf f ( xn ) .

Nhận xét 1.8.1 Chú ý rằng f là usc tại x0 nếu và chỉ nếu với mọi xn   x0 và
∀ ∈ ℝ,

 f ( xn )  b, n    f ( x0 )  b .

10




⟶ ℝ.

nếu, với mọi dãy bất kỳ {

} hội tụ

thì
(

) ≤ 0, ∀ ⟹ ( ) ≤ 0.

Nhận xét 1.8.2 Trong Định nghĩa 1.8.2 và Định nghĩa 1.8.3 nếu ta thay 0 bởi b ∈ ℝ,
thì “0-mức” sẽ được thay bằng “b-mức”.
Nhận xét 1.8.3 Nếu f và g là usc tại x0 và y0 , tương ứng, thì f là 0-mức đóng
trên tương ứng với g

tại  x0 , y0  . Thật vậy, nếu

 x , y    x , y 
n

n

0

0

và


ế
∈ℚ
( )=
1, ế
∈ ℝ\ℚ
Khi đó f là 0-mức đóng trên tương ứng với id tại  x, y  , với mọi ( , ) ∈ ℝ × ℝ ,
nhưng f không là usc tại mọi

∈ ℚ cũng không là lsc tại mọi

Định nghĩa 1.8.2 Cho X là không gian tôpô và :

∈ ℝ\ℚ .

⟶ℝ.

(a) f được gọi là tựa nửa liên tục trên tại x0  X nếu,
 f  x   f  x0    [với mọi { xn }  x0 , f  x  > lim sup f  xn  ].

(b) f được gọi là tựa nửa liên tục dưới tại x0  X nếu,
 f  x   f  x0    [với mọi { xn }  x0 , f  x  < lim inf f  xn  ].

(c) f được gọi là tựa liên tục tại x0  X , nếu f là tựa nửa liên tục trên và tựa
nửa liên tục dưới tại x0 .
Các lớp hàm nửa liên tục trên (dưới) chứa nghiêm ngặt các hàm nửa liên tục trên
(dưới). Chúng ta có một số ví dụ minh họa.
Ví dụ 1.8.2 Cho : ℝ ⟶ ℝ được xác định bởi:

 x  1,


2
Thì f1 là tựa nửa liên tục dưới tại 0 và g liên tục tại 0. Nhưng
  x  1,
 f1  g1  x    x
  2 ,

x  0,
x  0,

thì không tựa nửa liên tục dưới tại 0.
Tương tự cho tựa nửa liên tục trên. Cho
−1,
≥0
( )=
à g ( )= .
− ,


Bây giờ, nếu

( ) < lim sup (
→

), thì [ ( ), ( )] ∩

( ) = , điều này mâu

sup ( ) ≤ ( ) < ( ). Tương tự như vậy, f
là tựa nửa liên tục dưới tại y, ta được ( ) ≤ lim → inf ( ) và khi đó
lim sup ( ) ≤ ( ) < ( ) ≤ lim inf ( ) .
thuẫn với giả thiết. Vì vậy lim

→

→

→

đó là tính chất của f.
Ta chứng minh phần đảo. Xét ( ) < ( ),

⟶

và ( )

sao cho



Cho ánh xạ g:

f ( x , y ,  )  0.

× Λ ⟶ ℝ (trong đó ℝ = (−∞; +∞]) và K : X    2 X .

Bài toán tựa tối ưu chứa tham số là, với mỗi    ,

(

)

min g( , )
ℎ
∈ ( , )

Thay vì viết (QEP ) :    cho họ các bài toán tham số, trong các phần sau chúng
ta chỉ viết đơn giản (QEP). (QOP) tương tự.
Định nghĩa 2.1.1 Cho n  hội tụ đến  . Lấy xn  K1 ( xn , n ) , dãy  xn  được gọi là
dãy xấp xỉ của (QEP) tương ứng đến n  , nếu  dãy  n  hội tụ đến 0  sao cho,
y  K 2 ( xn , n ),

f ( xn , y , n )   n  0 .

Định nghĩa 2.1.2 Bài toán (QEP) được gọi là đặt chỉnh tại  nếu,
(a) Tập nghiệm S ( ) của (QEP ) là khác rỗng.

15


đến x và yn  Q ( xn ) , có một dãy con  yn

k

 hội tụ đến

y  Q( x ) .

(ii) Hơn nữa, nếu Q ( x )   y  là một tập đơn phần tử thì giới hạn điểm y trên
phải là y và mọi dãy  yn  hội tụ đến y .
Bởi S ( ) biểu thị tập nghiệm của (QEP ) . Cho   0 , tập  -nghiệm của (QEP )
được định nghĩa bởi:

16


S (  ,  )  {x  K1 ( x,  ) | f ( x , y ,  )    0,  y  K 2 ( x ,  )}

Khi X và Y là không gian mêtric, với   0,   0 . Chúng ta định nghĩa tập nghiệm
xấp xỉ của họ (QEP) (Cho phép chúng là tham số để biến thiên xung quanh điểm
được xét đến) là:

 ( ,  ,  ) :   

S ( ,  )

B ( , )

Khi đó B ( ,  ) là hình cầu đóng tâm tại  và bán kính  .
Định lí 2.2.1 Giả sử rằng:

Chứng minh:
+ Trước tiên chứng minh rằng S (.,.) là usc tại   ,0  .
Giả thiết ngược lại, tồn tại tập con mở S ( , 0) của U sao cho với mọi  n ,  n  hội
tụ đến   ,0  trong Λ × ℝ , có xn  S  n ,  n  sao cho xn  U với mọi n.
Bởi tính compact của X, chúng ta có thể giả sử rằng  xn  hội tụ đến x0 , vì K1 đóng
tại  x0 ,   nên có x0  K1 ( x0 ,  ) . Nếu x0  S   , 0   S    , thì tồn tại y0  K 2 ( x0 ,  )
sao cho f ( x0 , y0 ,  )  0 . Tính nửa liên tục dưới của K2 chứng tỏ tồn tại
yn  K 2 ( xn , n ) sao cho  yn   y0 . Với xn  S  n ,  n  ta có f ( xn , yn , n )   n  0 .

Bởi tính đóng 0-mức trên tương ứng với id của f chúng ta có f ( x0 , y0 ,  )  0 (mâu
thuẫn). Do đó, x0  S   , 0   U điều này mâu thuẫn với việc xn  U với mọi n. Do
đó S là usc tại   ,0  .
+ Bây giờ để kiểm tra S ( ) là compact chúng ta chỉ cần kiểm tra tính đóng của nó.

17


Cho xn  S ( ) hội tụ đến x0 . Nếu x0  S ( ) tồn tại y0  K 2 ( x0 ,  ) sao cho
f ( x0 , y0 ,  )  0 . Từ tính nửa liên tục dưới của K2 có yn  K 2 ( xn ,  ) sao cho

 yn   y0 . Với mọi n, chúng ta có

f ( xn , y n ,  )  0 , x n  S (  ) .

Theo giả thiết (ii) ta có được f ( x0 , y0 ,  )  0 (điều này vô lí), do đó x0  S ( ) và do
đó S ( z ) là compact. Theo Nhận xét 2.2.1 ta có điều phải chứng minh.
Các ví dụ sau chỉ ra tính cốt yếu của các giả thiết trong Định lí 2.2.1:
Ví dụ 2.2.1 (Tính compact của X không thể bỏ)
Cho
= ℝ, = ℝ , ( , ) = ( , ) = ℝ, ̅ = 0 và f ( x, y ,  )  2 x  y   . Rõ

n
 n 

đến 0  K1 (0, 0).
Ví dụ 2.2.3 (Tính nửa liên tục dưới của

không thể bỏ qua)

Cho X   1,1 ,    0,1 , K1 ( x,  )  0,1 , f ( x, y ,  )  x  y ,   0 và
1,0,1,
K 2 ( x,  )  
0,1 ,

 0
 0

18


Khi đó X là compact, K1 đóng trong X   và (ii) đúng ( bởi tính liên tục của f
trong X  X   ). Nhưng S (0)  1 và S ( )  0,1 với mọi    0,1 . Do đó, (QEP)
không đặt chỉnh tại 0, Vì K2 không lsc trong X    .
Ví dụ 2.2.4 ((ii) không thể bỏ được)
Cho X   0,1 ,   0,1 , K1 ( x,  )  K 2 ( x,  )  0,1 và
x  y
f ( x, y ,  )  
y  x

 0
 0


f ( xn , yn , n )   n  f  0,1,   1  0
n


nhưng

f  0,1,0   1  0 .

Nhận xét 2.2.2 Trong trường hợp đặc biệt, ở đây K ( x ,  )  X , không khó để kiểm
tra rằng giả thiết (ii) cho f có thể quy về điều kiện tương tự cho f ., y,. với mọi
y  X . Do đó Định lí 2.2.1 được cải tiến thành Định lí 2.2.3. Thật vậy, kiểm tra

thấy thỏa mãn giả thiết (ii) của Định lí 2.2.1 từ tính đơn điệu của f .,.,   và tính
nửa liên tục dưới của f  x,.,. . Nếu  xn , n    x,   và  n  hội tụ đến 0  sao
cho
f  xn , y , n    n  0 ,

thì bởi sự đơn điệu, ta có bất đẳng thức sau:
f  y , x ,    lim inf f  y , xn , n   lim inf   f  xn , y , n    lim inf  n  0

kéo theo f  x, y ,    0 . Hơn nửa chú ý rằng chúng ta bỏ qua tính nửa liên tục của
f .,.,   và tính lồi của f  x ,.,   .

19


Định lí 2.2.2 Cho X và  là không gian mêtric.
Nếu (QEP) là đặt chỉnh duy nhất tại  , thì diam    ,  ,    0 với


f  xn2 , y , n2    n  0,

y  K  xn2 , n2 

và

nghĩa là x1n  và xn2  là dãy xấp xỉ của (QEP) tương ứng với n1  và n2  . Do đó,

x 
1
n

và

x 

d  xn1 , xn2  

2
n

hội tụ đến nghiệm duy nhất của (QEP ) , mâu thuẫn vì

r
 0 , với mọi n.
2

(ii) Cho n    và  xn  là dãy xấp xỉ của (QEP) tương ứng với n  . Khi đó, tồn
tại  n   0 sao cho với mọi


,  n   0 , nên  xn  là một dãy Cauchy và hội tụ đến x . Bởi tính đóng của

̅ , ̅ nên ta có ̅ ∈

̅ , ̅ . Lập luận như Định lí 2.2.1, chúng ta kết luận

rằng x  S    . Ta hoàn toàn chứng minh được rằng (QEP ) có một nghiệm duy
nhất. Nếu S    có hai nghiệm phân biệt x1 và x2 , không khó để thấy rằng x1 và x2
thuộc

   ,  ,   , với mọi  ,   0 . Thấy rằng
0  d  x , x   diam   ,  ,  
1

2

điều này vô lí.
Nhận xét 2.2.3 Nếu K  x,    X với lập luận tương tự như Nhận xét 2.2.2 chúng
ta thấy rằng Định lí 2.2.2 là cải tiến của Định lí 2.2.1. Ở đây chúng ta bỏ qua tính
nửa liên tục của f .,.,   và tính lồi của f  x,.,   .
Ví dụ 2.2.5 Cho X    0,1 , K1 ( x,  )  K 2 ( x,  )  0,1 và f  x, y,    1 . Khi đó
(QEP) là đặt chỉnh trong  . Nhưng

   , ,    0,1 và do đó đường kính của nó

không hội tụ về 0.
Định lí 2.2.3
(i)

Nếu (QEP) là đặt chỉnh tại  , thì      ,  ,     0 với

Trong đó H *  A, B   supaA d  a, B  và d  a, B   inf bB d  a, b  . Cho  xn  là một dãy
bất kỳ trong S    . Từ  xn  là một dãy xấp xỉ của (QEP), có một dãy con hội tụ đến
điểm của S    . Do đó S    là compact.
n



Nếu S      B zk ,   H     ,  ,   , S    
k 1



và do đó






  
Từ S    là compact,   S      0 . Nên chúng ta có
    , ,    H    , ,   , S   .
Bây giờ chúng ta chỉ ra rằng H     ,  ,   ,S      0 với  ,     0 ,0  . Thật
   , ,    H   , ,   , S     S   .





