BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
ĐINH THỊ THU PHƯƠNG
TIẾP CẬN TỐI ƯU VÉC TƠ
VỚI MÔ HÌNH NASH-COURNOT SUY RỘNG
LUẬN VĂN THẠC SỸ TOÁN HỌC
Hà Nội – Năm 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
ĐINH THỊ THU PHƯƠNG
TIẾP CẬN TỐI ƯU VÉC TƠ
VỚI MÔ HÌNH NASH-COURNOT SUY RỘNG
Chuyên ngành: Toán giải tích
Mã số: 60 46 01 02
LUẬN VĂN THẠC SỸ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS.NGUYỄN VĂN QUÝ
Hà Nội – Năm 2016
LỜI CẢM ƠN
Lời đầu tiên của luận văn tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất
tới thầy giáo hướng dẫn TS. Nguyễn Văn Quý, người thầy đã định hướng chọn đề
tài và tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình làm và hoàn thiện luận
văn này.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các thầy cô
giáo giảng dạy chuyên ngành Toán giải tích, Trường Đại học sư phạm Hà Nội 2 đã
giúp đỡ tôi trong suốt quá trình học tập tại trường.
Nhân dịp này tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn cổ vũ,
động viên, giúp đỡ tôi trong suốt quá trình học tập và hoàn thành luận văn này.
Hà Nội, tháng 7 năm 2016
Tác giả
Đinh Thị Thu Phương
LỜI CAM ĐOAN
Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của TS. Nguyễn Văn Quý, luận
văn chuyên ngành Toán giải tích với đề tài: “ Tiếp cận tối ưu véc tơ với Mô
hình Nash-Cournot suy rộng ” được hoàn thành bởi sự nhận thức và tìm hiểu
của bản thân tác giả.
Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa những kết
quả của các nhà khoa học với sự trân trọng và biết ơn.
Hà Nội, tháng 7 năm 2016
Tác giả
Đinh Thị Thu Phương
Mục lục
LỜI MỞ ĐẦU
1
1 Kiến thức cơ bản
3
1.1
1.2
1.3
Tập lồi và hàm lồi trong không gian Rn . . . . . . . . .
3
1.1.1
Tập lồi . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Nón lồi . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.3
Hàm lồi . . . . . . . . . . . . . . . . . . . . . .
9
1.1.4
Dưới vi phân của hàm lồi . . . . . . . . . . . .
15
1.1.5
Hàm lồi khả vi . . . . . . . . . . . . . . . . . .
19
1.1.6
Cực trị của hàm lồi . . . . . . . . . . . . . . . .
22
Bài toán cân bằng và bài toán liên quan . . . . . . . .
26
1.2.1
Bài toán cân bằng . . . . . . . . . . . . . . . .
26
1.2.2
Bài toán bất đẳng thức biến phân . . . . . . . .
27
1.2.3
Bài toán tối ưu . . . . . . . . . . . . . . . . . .
28
1.2.4
Bài toán tựa cân bằng . . . . . . . . . . . . . .
30
Bài toán tối ưu véc tơ . . . . . . . . . . . . . . . . . .
31
1.3.1
Quan hệ thứ tự theo nón . . . . . . . . . . . . .
31
1.3.2
Quan hệ thứ tự trong không gian Rn . . . . . .
32
i
1.3.3
2
Điểm Pareto (Điểm hữu hiệu) trong không gian
Rn . . . . . . . . . . . . . . . . . . . . . . . . .
33
1.3.4
Bài toán tối ưu véc tơ . . . . . . . . . . . . . .
35
1.3.5
Bài toán vô hướng hóa . . . . . . . . . . . . . .
36
Tiếp cận tối ưu véc tơ với Mô hình Nash-Cournot suy
rộng
2.1
2.2
2.3
41
Phát biểu Mô hình Nash-Cournot . . . . . . . . . . . .
41
2.1.1
Mô hình Nash-Cournot cổ điển . . . . . . . . .
41
2.1.2
Mô hình Nash-Cournot suy rộng . . . . . . . . .
42
Tiếp cận tối ưu véc tơ với Mô hình Nash-Cournot suy
rộng . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
2.2.1
Các giả thiết cơ bản . . . . . . . . . . . . . . .
45
2.2.2
Tiếp cận tối ưu véc tơ . . . . . . . . . . . . . .
47
Sử dụng kỹ thuật vô hướng hóa cho bài toán tối ưu véc
tơ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4
50
Phương pháp nhánh cận giải bài toán vô hướng hóa ứng
với Mô hình Nash-Cournot suy rộng . . . . . . . . . . .
2.4.1
2.4.2
52
Kỹ thuật tính cận để giải bài toán vô hướng hóa
(SQVP) . . . . . . . . . . . . . . . . . . . . . .
54
Quy tắc chia nhánh . . . . . . . . . . . . . . . .
62
Kết luận
73
Tài liệu tham khảo
74
ii
LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Mô hình cân bằng thị trường độc quyền Nash-Cournot do A.Cournot
đưa ra vào năm 1838 và đã được rất nhiều các tác giả trên thế giới
tập trung nghiên cứu. Mô hình Nash-Cournot là một Mô hình cơ bản
trong kinh tế học.
Ngày nay, Mô hình Nash-Cournot đã được phát triển và mở rộng
thêm nhiều bởi tính ứng dụng của nó không chỉ trong lĩnh vực kinh
tế mà còn trong nhiều lĩnh vực khác. Nghiên cứu các tính chất và
phương pháp giải với Mô hình Nash-Cournot cổ điển và suy rộng là
một chủ đề đang được nhiều nhà toán học trong và ngoài nước quan
tâm.
Hiện nay, các cách tiếp cận trong nghiên cứu Mô hình Nash-Cournot
là tiếp cận bất đẳng thức biến phân, tiếp cận cân bằng và tiếp cận
tối ưu véc tơ. Với mỗi cách tiếp cận đều có những ưu điểm nhất định
trong việc đưa ra các phương pháp giải mô tả các ứng dụng của Mô
hình.
Đề tài chọn cách tiếp cận tối ưu véc tơ để nghiên cứu và đưa ra
phương pháp giải với Mô hình Nash-Cournot suy rộng là một đề tài
có tính khoa học, tính thời sự và tính thực tiễn.
1
2. Mục đích nghiên cứu
Nghiên cứu cách tiếp cận tối ưu véc tơ với Mô hình Nash-Cournot
suy rộng và đưa ra phương pháp giải.
3. Nhiệm vụ nghiên cứu
Mô tả Mô hình kinh tế Nash-Cournot cổ điển và suy rộng dưới
dạng bài toán tối ưu véc tơ và trình bày phương pháp giải bài toán.
4. Đối tượng và phạm vi nghiên cứu
Trong luận văn sử dụng các kiến thức bổ trợ chủ yếu là Giải tích
lồi và Lý thuyết tối ưu véc tơ. Đối tượng áp dụng chính là Mô hình
kinh tế Nash-Cournot cổ điển và Mô hình kinh tế Nash-Cournot suy
rộng.
5. Phương pháp nghiên cứu
Nghiên cứu các tài liệu từ giáo viên hướng dẫn. Tìm tòi thu thập
thêm tư liệu từ các bài giảng, sách, báo, internet,...từ đó sắp xếp, biên
soạn lại hình thành nội dung đề tài.
2
Chương 1
Kiến thức cơ bản
1.1
1.1.1
Tập lồi và hàm lồi trong không gian Rn
Tập lồi
Định nghĩa 1.1. [2]
Tập D ⊂ Rn khác rỗng được gọi là lồi nếu với mọi x, y ∈ D và với
mọi 0 ≤ λ ≤ 1 ta đều có:
λx + (1 − λ)y ∈ D.
Định nghĩa 1.2. [2]
Ta nói x là tổ hợp lồi của các véc tơ x1 , ..., xk ∈ Rn nếu:
x=
k
P
λj xj ,
j=1
trong đó λj ≥ 0 với mọi j = 1, 2, ..., n và
k
P
λj = 1.
j=1
Mệnh đề dưới đây được suy ra trực tiếp từ định nghĩa.
Mệnh đề 1.1. [2]
(i) Giao của một họ hữu hạn hoặc vô hạn các tập lồi là một tập
lồi.
3
(ii) Tích Đề-Các của một họ hữu hạn các tập lồi là một tập lồi.
(iii) Cho A và B là hai tập lồi trong không gian Rn . Khi đó, tổng
đại số của A và B được định nghĩa và ký hiệu bởi:
A + B := {x + y : x ∈ A, y ∈ B}.
(iv) Cho C là một tập lồi trong không gian Rn và λ là một số thực
bất kỳ. Khi đó, tập:
Cλ := {λx : x ∈ C}.
(v) Ảnh và nghịch ảnh của một tập lồi qua một ánh xạ tuyến tính
cũng là một tập lồi.
Định nghĩa 1.3. [2]
Cho A là một tập khác rỗng trong không gian Rn . Tập hợp tất cả
các tổ hợp lồi của một số hữu hạn các điểm thuộc A được gọi là bao
lồi của A và ký hiệu bởi CoA.
Mệnh đề 1.2. [2]
Cho A là một tập khác rỗng trong không gian Rn .
(i) CoA là một tập lồi.
(ii) CoA là một tập lồi nhỏ nhất chứa A.
(iii) A lồi khi và chỉ khi A = CoA.
Định nghĩa 1.4. [1]
Một tập được gọi là tập lồi đa diện, nếu nó là giao của một số hữu
hạn các nửa không gian đóng.
Do mỗi phương trình tuyến tính có thể biểu diễn tương đương bằng
hai bất phương trình tuyến tính nên một tập đa diện cũng là tập hợp
nghiệm của một hệ hữu hạn các bất phương trình tuyến tính.
4
Định nghĩa 1.5. [1]
Một tập hợp S ⊂ Rn được gọi là một đơn hình có thứ nguyên bằng
k (hoặc nói ngắn gọn là k−đơn hình), nếu S là tổ hợp lồi của k + 1
véc tơ độc lập a-phin. Các véc tơ này được gọi là đỉnh của đơn hình.
Định nghĩa 1.6. [1]
Điểm x∗ được gọi là điểm cực biên của tập lồi D nếu không tồn tại
hai điểm khác nhau x1 , x2 ∈ D sao cho:
1
1
x∗ = x1 + x2 .
2
2
Điều này tương đương với nếu x1 , x2 ∈ D thỏa mãn:
1
1
x∗ = x1 + x2 ,
2
2
thì x∗ = x1 = x2 .
Tập các điểm cực biên của tập lồi ký hiệu là Ext(D).
1.1.2
Nón lồi
Định nghĩa 1.7. [2]
Cho K là một tập khác rỗng trong Rn .
(a) K được gọi là nón có đỉnh tại 0 nếu với mọi x ∈ K và với mọi
λ > 0 ta đều có:
λx ∈ K.
(b) K được gọi là nón có đỉnh tại x0 , nếu K − x0 là nón có đỉnh
tại 0.
5
(c) Nón K (đỉnh tại 0 hoặc x0 ) được gọi là nón lồi nếu K là một
tập lồi.
(d) Nón K (đỉnh tại 0 hoặc x0 ) được gọi là nón lồi đóng nếu K
là một tập lồi đóng.
Mệnh đề 1.3. [2]
K là một nón lồi, có đỉnh tại 0 khi và chỉ khi với mọi x, y ∈ K và
với mọi λ, µ > 0 ta đều có:
λx + µy ∈ K.
Ví dụ 1.1.1. Các tập trong Rn sau đây:
Rn+ := {(ξ1 , ..., ξn ) ∈ Rn : ξi ≥ 0, ∀i = 1, ..., n}
(orthan không âm).
Rn++ := {(ξ1 , ..., ξn ) ∈ Rn : ξi > 0, ∀i = 1, ..., n}
(orthan dương).
Đều là các nón lồi có đỉnh tại 0. Đây là các nón lồi quan trọng
trong Rn .
Hệ quả 1.1. [2]
Tập K khác rỗng trong Rn là nón lồi có đỉnh tại 0 khi và chỉ khi K
chứa tất cả các tổ hợp tuyến tính dương của một số hữu hạn các phần
tử trong K. Tức là, với mọi x1 , ..., xm ∈ K (m là một số tự nhiên bất
kỳ) và với mọi λ1 , ..., λm > 0 thì:
m
P
λi xi ∈ K.
i=1
Hệ quả 1.2. [2]
Giả sử A là tập bất kỳ trong Rn , K là tập tất cả các tổ hợp tuyến
tính dương của A. Khi đó, K là nón lồi nhỏ nhất chứa A.
6
Định nghĩa 1.8. [1]
Cho C là một tập lồi khác rỗng trong Rn và điểm x0 ∈ C.
(a) Điểm x∗ ∈ Rn được gọi là véc tơ pháp tuyến ngoài (hay pháp
tuyến ngoài) của C tại x0 nếu:
hx∗ , x − x0 i ≤ 0 với mọi x ∈ C.
(b) Tập tất cả các véc tơ pháp tuyến ngoài của C tại x0 ký hiệu
là NC (x0 ).
Mệnh đề 1.4. [1]
Cho C là một tập lồi khác rỗng trong Rn và điểm x0 ∈ C. Tập
NC (x0 ) là một nón lồi đóng có đỉnh tại 0.
Chứng minh.
Hiển nhiên 0 ∈ NC (x0 ) nên suy ra NC (x0 ) là khác rỗng.
Mặt khác, giả sử u, v ∈ NC (x0 ) và λ, µ > 0.
Từ định nghĩa ta có:
hu, x − x0 i ≤ 0 và hv, x − x0 i ≤ 0,
và dẫn đến:
hλu + µv, x − x0 i = λhu, x − x0 i + µhv, x − x0 i ≤ 0 với mọi x ∈ C.
Từ đó suy ra λu + µv ∈ NC (x0 ) và theo Mệnh đề (1.3) thì NC (x0 )
là một nón lồi có đỉnh tại 0.
Để chứng tỏ NC (x0 ) là một tập đóng ta giả sử {un } là một dãy
7
nằm trong NC (x0 ) và un → u khi và chỉ khi n → ∞.
Ta phải chứng minh u ∈ NC (x0 ). Thực vậy, với mỗi x ∈ C cố định
thì:
fx (u) = hu, x − x0 i ≤ 0 với mọi u ∈ NC (x0 ),
và là một hàm liên tục trên NC (x0 ). Từ đó, và theo tính chất của giới
hạn suy ra:
lim fx (un ) = hu, x − x0 i ≤ 0.
n→∞
Điều này đúng với mọi x ∈ C.
Vậy u ∈ NC (x0 ) và ta có điều cần chứng minh.
2
Định nghĩa 1.9. [2]
Giả sử A ⊂ Rn là một tập lồi và khác rỗng. Ta nói tập A lùi xa
theo phương d ∈ Rn , d 6= 0, nếu:
A + λd ⊂ A, ∀λ ≥ 0,
hay
x + λd ∈ A với mọi x ∈ A và mọi λ ≥ 0.
(1.1)
Từ định nghĩa ta dễ dàng suy ra, nếu tập các phương lùi xa của
tập A mà khác rỗng thì nó là một nón có đỉnh tại 0.
Định nghĩa 1.10. [2]
Tập các véc tơ d ∈ Rn thỏa mãn (1.1) và véc tơ d = 0 được gọi là
nón lùi xa của A, ký hiệu là o+ A.
Mệnh đề 1.5. [2]
Nếu A là một tập lồi thì o+ A là một nón lồi có đỉnh tại 0.
8
1.1.3
Hàm lồi
Trước tiên chúng ta trình bày một số khái niệm thông thường.
Cho D ⊆ Rn là tập lồi khác rỗng và hàm số f : D → R̄.
Ta ký hiệu:
domf := {x ∈ D | f (x) < +∞}.
Tập domf được gọi là miền hữu hiệu của f . Tập:
epif := {(x, µ) ∈ D × R | f (x) ≤ µ}
được gọi là trên đồ thị của hàm f .
Một hàm f được gọi là chính thường nếu domf = ∅ và f (x) > −∞
với mọi x.
Bằng cách cho f (x) = +∞ nếu x ∈
/ D, ta có thể coi f được xác
định trên toàn không gian và hiển nhiên là:
domf = {x ∈ Rn | f (x) < +∞}
và
epif = {(x, µ) ∈ Rn × R | f (x) ≤ µ}.
Khi làm việc với hàm số nhận cả giá trị −∞ và +∞, như thường
lệ, ta quy ước: Nếu λ = 0 thì λf (x) = 0 với mọi x.
Định nghĩa 1.11. [1]
Cho D ⊆ Rn là một tập lồi, khác rỗng và f : D → R̄. Ta nói f là
hàm lồi trên D, nếu epif là một tập lồi trong Rn+1 .
9
Mệnh đề 1.6. [1]
Cho D ⊆ Rn là một tập lồi, khác rỗng và f : D → R ∪ {+∞}. Khi
đó, f là hàm lồi trên D khi và chỉ khi:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y),
(1.2)
với mọi x, y ∈ D và với mọi λ ∈ [0, 1].
Chứng minh.
Với λ = 0 hay λ = 1 thì (1.2) luôn đúng.
Nên ta chỉ xét với 0 < λ < 1.
Giả sử f là hàm lồi trên D. Nếu x ∈
/ domf hoặc y ∈
/ domf thì hiển
nhiên (1.2) là đúng.
Bây giờ ta xét với x, y ∈ domf . Do:
(x, f (x)) ∈ epif
;
(y, f (y)) ∈ epif,
mà epif lồi nên:
(λx + (1 − λ)y, λf (x) + (1 − λ)f (y)) ∈ epif.
Theo định nghĩa của epif suy ra (1.2).
Ngược lại, giả sử (1.2) đúng, ta cần chứng minh epif là lồi. Thực
vậy, với mọi (x, µ), (y, ν) ∈ epif ta phải chứng minh:
λ(x, µ) + (1 − λ)(y, ν) = (λx + (1 − λ)y, λµ + (1 − λ)ν) ∈ epif.
Điều này đúng vì theo định nghĩa của epif và λ > 0, (1 − λ) > 0
10
nên :
λf (x) ≤ λµ ; (1 − λ)f (y) ≤ (1 − λ)ν,
kết hợp với (1.2) suy ra:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ≤ λµ + (1 − λ)ν.
2
Vậy mệnh đề được chứng minh.
Hệ quả 1.3. [1]
Nếu f là hàm lồi và nhận giá trị hữu hạn trên tập lồi D, thì với
mọi số tự nhiên m, mọi x1 , ..., xm ∈ D và với mọi bộ số:
λ1 ≥ 0, ..., λm ≥ 0,
m
X
λj = 1,
j=1
ta đều có:
f(
m
P
j
λj x ) ≤
j=1
m
P
λj f (xj ) (Bất đẳng thức Jensen).
j=1
Định nghĩa 1.12. [1]
Cho D là một hàm lồi khác rỗng trong Rn .
(a) Hàm f được gọi là lồi chặt trên D nếu:
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y),
(1.3)
với mọi x, y ∈ D và với mọi λ ∈ (0, 1).
(b) Hàm f : Rn → R ∪ {+∞} được gọi là lồi mạnh trên D với hệ
số η > 0, nếu ∀x, y ∈ D, ∀λ ∈ (0, 1) có:
1
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)kx − yk2 .
2
11
(c) Hàm f được gọi là một hàm lõm trên D, nếu −f là hàm lồi
trên D.
(d) Hàm f được gọi là tựa lồi trên D nếu ∀λ ∈ R tập mức dưới:
Lλ f := {x ∈ D : f (x) ≤ λ}
là tập lồi.
(e) Hàm f được gọi là tựa lõm trên D nếu −f là hàm tựa lồi trên
D.
Mệnh đề 1.7. [1]
Cho D là một tập lồi khác rỗng trong Rn . Hàm f lồi mạnh trên D
với hệ số η > 0 khi và chỉ khi hàm:
η
h(.) := f (.) − k.k2 .
2
Mệnh đề 1.8. [1]
Một hàm f : D → R̄ là lồi trên D khi và chỉ khi:
∀x, y ∈ D, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1].
⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β.
Chứng minh.
Chứng minh điều kiện cần:
Giả sử f lồi. Chọn x, y, α, β như đã nêu trong mệnh đề.
0
0
Chọn α ∈ (f (x), α) và β ∈ (f (y), β).
0
0
Vậy (x, α ) và (y, β ) thuộc epif .
Do epif lồi , nên:
12
0
0
((1 − λ)x + λy, (1 − λ)α + λβ ) ∈ epif .
Do đó:
0
0
f ((1 − λ)x + λy) ≤ (1 − λ)α + λβ < (1 − λ)α + λβ.
Chứng minh điều kiện đủ:
Chọn (x, µ) và (y, ν) thuộc epif và λ ∈ (0, 1).
Thế thì với mọi ε > 0, ta có:
f (x) < µ + ε, f (y) < ν + ε.
Do đó:
0
0
f [(1 − λ)α + λβ ] < (1 − λ)(µ + ε) + λ(ν + ε)
= (1 − λ)µ + λν + ε.
Điều này đúng với mọi ε > 0, nên cho ε → 0, ta được:
0
0
f [(1 − λ)α + λβ ] ≤ (1 − λ)µ + λν.
Chứng tỏ:
(1 − λ)(x, µ) + λ(y, ν) ∈ epif.
2
Vậy f là hàm lồi.
Mệnh đề 1.9. [1]
Cho C là một tập lồi khác rỗng trong Rn . Khi đó, hàm chỉ của tập
13
C được định nghĩa trên toàn Rn theo công thức:
δC (x) =
0, x ∈ C;
+∞, x ∈
/ C.
là hàm lồi trên Rn .
Định nghĩa 1.13. [3]
Cho A là một ma trận vuông, đối xứng cấp n × n.
(a) Ma trận A được gọi là xác định dương nếu:
xT Ax > 0 với mọi x ∈ Rn , x 6= 0.
(b) Ma trận A được gọi là nửa xác định dương nếu:
xT Ax ≥ 0 với mọi x ∈ Rn ,
và tồn tại x 6= 0 để xT Ax = 0.
Mệnh đề 1.10. [3]
Cho A là một ma trận vuông, đối xứng cấp n × n.
(i) Ma trận A là xác định dương khi và chỉ khi tất cả các giá trị
riêng của A đều dương.
(ii) Ma trận A là nửa xác định dương khi và chỉ khi tất cả các giá
trị riêng của A đều không âm và có tồn tại ít nhất một giá trị riêng
bằng không.
Mệnh đề 1.11. [3]
Cho A là một ma trận vuông, đối xứng cấp n × n, và véc tơ c ∈ Rn .
14
- Xem thêm -