Đăng ký Đăng nhập
Trang chủ Tiếp cận tối ưu véc tơ với mô hình nash cournot suy rộng (lv02016)...

Tài liệu Tiếp cận tối ưu véc tơ với mô hình nash cournot suy rộng (lv02016)

.PDF
81
227
146

Mô tả:

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 -

Tài liệu liên quan