Tài liệu Hai tiếp cận cho mô hình cân bằng nash - cournot

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐÀO THỊ LÀNH HAI TIẾP CẬN CHO MÔ HÌNH CÂN BẰNG NASH-COURNOT Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học GS.TSKH. LÊ DŨNG MƯU Thái Nguyên - Năm 2014 i LỜI CẢM ƠN Lời đầu tiên của khóa luận này, tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo hướng dẫn GS.TSKH. Lê Dũng Mưu, người thầy đã 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. Trong quá trình học tập chương trình cao học tại trường Đại học khoa học, tôi đã nhận được sự giúp đỡ và sự giảng dạy tận tình của GS.TSKH Lê Dũng Mưu, GS.TS. Trần Vũ Thiệu, PGS. Nông Quốc Chinh, PGS.TS. Lê Thị Thanh Nhàn, PGS.TS. Tạ Duy Phượng, TS. Nguyễn Thị Thanh Thủy, cùng rất nhiều thầy cô công tác tại Viện Toán học Việt Nam, Trường Đại học Thăng Long, Trường Đại học Khoa học - Đại học Thái Nguyên. Tôi xin bày tỏ lòng biết ơn sâu sắc đến các thầy, các cô. Nhận dịp này, tôi cũng xin gửi lời cảm ơn tới các thầy giáo, cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm, tạo điều kiện giúp đỡ tôi trong suốt quá tình học tập. Đồng thời, tôi cũng xin gửi lời cảm ơn tới gia đình và bạn bè đã luôn động viên, giúp đỡ tôi trong suốt quá trình học tập và làm luận văn tốt nghiệp. Đặc biệt, cảm ơn anh Lưu Đình Trung đã giúp đỡ tôi rất nhiều trong quá trình hoàn thành luận văn. Thái Nguyên, ngày 21 tháng 06 năm 2014 Tác giả Đào Thị Lành ii Mục lục Mở đầu 1 1 Tiếp cận cân bằng Nash cho mô hình kinh tế bán độc quyền Cournot. 2 1.1 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . 2 Tập lồi, hàm lồi và toán tử đơn điệu . . . . . . . . 1.1.2 Bài toán cân bằng . . . . . . . . . . . . . . . . . . 1.2 Mô hình cân bằng với cước phí tuyến tính . . . . . . . . . . 1.2.1 Phát biểu mô hình Nash - Cournot . . . . . . . . . 1.2.2 Trường hợp cước phí tuyến tính . . . . . . . . . . . 1.3 Mô hình cân bằng Nash - Cournot với cước phí lõm . . . . . 1.3.1 Mô hình cân bằng Nash - Cournot với cước phí lõm 1.3.2 Sự tồn tại nghiệm của mô hình . . . . . . . . . . . 3 1.1.1 7 15 15 17 21 21 22 2 Tiếp cận tối ưu vectơ cho mô hình kinh tế bán độc quyền Cournot Các kiến thức cơ bản về tối ưu vectơ . . . . . . . . 2.1.1 Bài toán tối ưu một mục tiêu . . . . . . . . 2.1.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . 2.1.3 Bài toán tối ưu đa mục tiêu . . . . . . . . . 2.1.4 Định lý vô hướng hóa . . . . . . . . . . . . . 2.2 Bài toán tối ưu vectơ cho mô hình Cournot . . . . . 2.2.1 Mô hình Cournot . . . . . . . . . . . . . . . 2.2.2 Tiếp cận tối ưu vectơ cho mô hình Cournot 2.1 25 . . . . 25 . . . . 25 . . . . 25 . . . . 26 . . . . 28 . . . . 30 . . . . 30 . . . . 31 i Kết luận 38 Tài liệu tham khảo 39 1 MỞ ĐẦU Mô hình cân bằng thị trường độc quyền do A. Cournot đưa ra vào năm 1838 và đã được rất nhiều tác giả trên thế giới tập trung nghiên cứu. Mô hình Cournot có vai trò rất quan trọng trong thực tiễn cuộc sống, đặc biệt là trong lĩnh vực kinh tế. Một trong những hướng nghiên cứu quan trọng của mô hình này là xây dựng cách tiếp cận cho mô hình Cournot. Hai cách tiếp cận quan trọng cho mô hình Cournot đó là tiếp cận cân bằng và tiếp cận tối ưu đa mục tiêu. Nội dung của luận văn này, trình bày về cách tiếp cận cân bằng cho mô hình Cournot. Bản luận văn gồm hai chương: Chương 1. Tiếp cận cân bằng Nash cho mô hình kinh tế bán độc quyền Cournot. Trong chương này ta tìm hiểu các kiến thức về tập lồi, hàm lồi, toán tử đơn điệu và bài toán cân bằng. Sau đó, trình bày về mô hình cân bằng với cưới phí tuyến tính và mô hình cân bằng với cước phí lõm. Chương 2. Tiếp cận tối ưu vectơ cho mô hình bán độc quyền Cournot Chương hai gồm các kiến thức về tối ưu vectơ như : Bài toán tối ưu một mục tiêu, sự tồn tại nghiệm và bài toán tối ưu đa mục tiêu, sau đó trình bày về định lý vô hướng hóa và tiếp cận tối ưu vectơ cho mô hình Cournot. Tôi rất mong được sự đóng góp ý kiến của các thầy cô cùng toàn thể bạn đọc. 2 Chương 1 Tiếp cận cân bằng Nash cho mô hình kinh tế bán độc quyền Cournot. Trong chương này chúng ta xét nội dung bao gồm: Một số kiến thức liên quan đến không gian Rn , giải tích lồi, bất đẳng thức biến phân...Tiếp sau đó là mô hình Cournot theo tiếp cận mô hình Nash. Đồng thời trình bày về mô hình cân bằng với cước phí tuyến tính và mô hình cân bằng với cước phí lõm. Các kiến thức trong chương này được lấy chủ yếu ở các tài liệu [1], [2], [3], [4], [5]. 1.1 Kiến thức chuẩn bị Trong luận văn này chúng ta kí hiệu Rn là không gian Euclide thực n chiều. Một phần tử x = (x1 , x2 , ..., xn )T ∈ Rn là một vectơ cột Rn . Ta nhắc lại rằng, với hai vectơ x = (x1 , x2 , ..., xn ), y = (y1 , y2 , ..., yn ) ∈ Rn , hx, yi := n X i=1 xi yi 3 được gọi là tích vô hướng của hai vectơ. Chuẩn Euclide của phần tử x và khoảng cách Euclide giữa hai phần tử x, y được định nghĩa tương ứng bởi q k x k:= hx, yi, d(x, y) :=k x − y k . Ta gọi R = [−∞, +∞] = R ∪ {−∞} ∪ {+∞} là tập số thực mở rộng. Trước hết ta nhắc lại một số khái niệm và tính chất cơ bản của giải tích lồi và toán tử đơn điệu. Tập lồi, hàm lồi và toán tử đơn điệu 1.1.1 Định nghĩa 1.1. Một tập hợp C ⊂ Rn được gọi là lồi nếu ∀x, y ∈ C, 0 ≤ λ ≤ 1 ⇒ λx + (1 − λ)y ∈ C. Các ví dụ về tập lồi: Tập không gian Rn , siêu phẳng, hình vuông, hình tròn... Tuy nhiên đường tròn hay hình vành khăn không phải tập lồi. '$ y x &% A A x A H HH@ A H@ A H@ A H y H H @ @ Các tập hợp không lồi x H @ @ @ @ @ HH H @ @ HHy @ @ @ Các tập hợp lồi 4 Một số tính chất cơ bản của tập lồi a) Giao của một số bất kì các tập lồi là một tập lồi. b) Nếu tập hợp C và D là lồi thì C + D, αC (và do đó cả C − D) cũng lồi. c) Bao đóng của một tập hợp lồi là tập hợp lồi. d) 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 trong Rn là một tập hợp lồi. Tập hợp C ⊂ Rn được gọi là lồi chặt nếu ∀x, y ∈ C, x 6= y , mọi điểm λx + (1 − λ)y với 0 < λ < 1 đều là điểm trong của C . Định nghĩa 1.2 (Xem [4], Định nghĩa 1.1.3). Hàm f : Rn → Rn \ {+∞} được gọi là (i) lồi trên C nếu với mọi λ ∈ (0, 1), ∀x, y ∈ C ta có f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), (ii) lồi chặt trên C nếu với mọi λ ∈ (0, 1), ∀x, y ∈ C, x 6= y ta có f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), (iii) lồi mạnh trên C nếu tồn tại τ ∈ R, τ > 0 với mọi λ ∈ (0, 1), ∀x, y ∈ C ta có 1 f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − λ(1 − λ)τ k x − y k2 , 2 (iv) lõm trên C nếu -f là hàm lồi trên C. Định nghĩa 1.3. Một hàm aphin là hàm số có dạng f (x) = hc, xi + α trong đó c ∈ Rn , α ∈ R cho trước tùy ý. Nếu f (x) là hàm afin thì với mỗi x, y ∈ Rn và mọi số λ, µ sao cho λ + µ = 1 ta có f (λx + µy) = λf (x) + µf (y). Một hàm afin f (x) = hc, xi + α không lấy giá trị âm thì phải đồng nhất với một hằng số (vectơ c phải bằng 0), vì nếu c 6= 0 thì ta sẽ có f (λc) = hc, xi + α → −∞ khi λ → −∞. 5 Định nghĩa 1.4 ( Xem [4], Định nghĩa 1.1.1). Cho C là tập lồi trong Rn , Q: C → Rn là một ánh xạ. Ánh xạ Q được gọi là (i) Đơn điệu trên C nếu mỗi cặp điểm u, v ∈ C , ta có hQ(u) − Q(v), u − vi ≥ 0. (ii) Đơn điệu mạnh trên C với mỗi hằng số τ > 0 nếu mỗi cặp u, v ∈ C , ta có hQ(u) − Q(v), u − vi ≥ τ k u − v k2 . (iii) Đơn điệu ngặt trên C nếu với mọi u, v ∈ C , ta có hQ(u) − Q(v), u − vi > 0. (iv) Giả đơn điệu trên C nếu mỗi cặp điểm u, v ∈ C ta có nếu hQ(v), u − vi ≥ 0. thì hQ(u), u − vi ≥ 0. Định nghĩa 1.5. Đồ thị (epiF), miền hữu hiệu (domF), miền ảnh (rgeF) của ánh xạ đa trị F : X → 2Y được định nghĩa tương ứng bằng công thức sau epiF = {(x, y) ∈ X × Y : y ∈ F (x)}; domF = {x ∈ X : F (x) 6= 0}; rge = {y ∈ Y : ∃x ∈ X : y ∈ F (x)}. Ví dụ 1.6. Cho toán tử T đơn trị xác định trên R như sau T (x) = x, ∀x ∈ R. Khi đó, T là toán tử đơn điệu vì ∀x, y ∈ R ta có: hT (x) − T (y), x − yi = hx − y, x − yi = (x − y)2 ≥ 0 Định lý 1.7. Toán tử tuyến tính A : Rn → Rn là đơn điệu khi và chỉ khi hAz, zi ≥ 0, ∀z ∈ Rn . Chứng minh. Hiển nhiên domA = Rn và A là toán tử đơn điệu. Theo định nghĩa, A là toán tử đơn điệu khi và chỉ khi hA(x) − A(y), x − yi ≥ 0, ∀x, y ∈ Rn , 6 hay hA(x − y), x − yi ≥ 0, ∀x, y ∈ Rn . Đặt z = x − y ta có hAz, zi ≥ 0, ∀z ∈ Rn . Định nghĩa 1.8 (Phép toán bảo toàn tính đơn điệu). Các tính chất sau luôn đúng n n (i) T : Rn → 2R đơn điệu khi và chỉ khi T −1 : Rn → 2R là đơn điệu. n (ii) Nếu T1 , T2 là toán tử đơn điệu từ Rn → 2R và nếu λ1 , λ2 ≥ 0 thì λ1 T1 + λ2 T2 cũng là toán tử đơn điệu. Nếu thêm điều kiện T1 hoặc T2 là đơn điệu chặt thì λ1 T1 + λ2 T2 là đơn điệu chặt. n (iii) Nếu T : Rn → 2R là toán tử đơn điệu và A : Rn → Rn là toán tử tuyến tính, A∗ là toán tử liên hợp của A thì S(x) = A∗ T (Ax + b) cũng là toán tử đơn điệu. Ngoài ra nếu A là đơn ánh và T là toán tử đơn điệu chặt thì S là toán tử đơn điệu chặt. Chứng minh. (i) Theo định nghĩa toán tử T là đơn điệu khi và chỉ khi hx − y, u − vi ≥ 0, ∀x, y ∈ domT, x 6= y, ∀u ∈ T (x), ∀v ∈ T (y), hay hx − y, u − vi ≥ 0; ∀x, y ∈ domT −1 , x 6= y, ∀x ∈ T −1 (u), ∀y ∈ T −1 (v). Điều này chứng tỏ T −1 là toán tử đơn điệu. (ii Hiển nhiên ta có dom(λ1 T1 + λ2 T2 ) = {z ∈ Rn : λ1 T1 (z) + λ2 T2 (z) 6= 0} = domT1 ∩ domT2 . Giả sử x, y ∈ domT1 ∩ domT2 và u ∈ (λ1 T1 + λ2 T2 )(x) = λ1 T1 (x) + λ2 T2 (x). v ∈ (λ1 T1 + λ2 T2 )(y) = λ1 T1 (y) + λ2 T2 (y). Lấy ui ∈ Ti (x), vi ∈ Ti (y), i = 1, 2 sao cho u = λ1 u1 + λ2 u2 , v = λ1 v1 + λ2 v2 , do T1 , T2 là toán tử đơn điệu nên ta có 7 hu1 − v1 , x − yi ≥ 0, hu2 − v2 , x − yi ≥ 0. Nhân lần lượt hai biểu thức trên với λ1 và λ2 rồi cộng lại ta được hu − v, x − yi ≥ 0. Điều này chứng tỏ λ1 T1 + λ2 T2 là toán tử đơn điệu. (iii) Lấy x, y ∈ domT, u ∈ S(x) = A∗ T (Ax + b), v ∈ S(y) = A∗ T (Ay + b), chọn u1 ∈ T (Ax + b) và v1 ∈ T (Ay + b) sao cho u = A∗ u1 , v = A∗ v1 . Do tính đơn điệu của T ta có hv − u, y − xi = hA∗ v1 − A∗ u1 , y − xi = hv1 − u1 , (Ay + b) − (Ax + b)i ≥ 0. Từ đó suy ra S là toán tử đơn điệu. Giả sử A là đơn ánh và T là toán tử đơn điệu chặt, khi đó nếu x 6= y thì Ax 6= Ay kéo theo Ax + b 6= Ay + b. Giả sử u, v, u1 , v1 được lấy như trên, vì T là toán tử đơn điệu chặt nên hv1 − u1 , (Ay + b) − (Ax + b)i > 0. Suy ra hv − u, y − xi > 0. Từ đó chứng tỏ S là toán tử đơn điệu chặt. Định nghĩa 1.9 (Song hàm cân bằng, xem [4]). Cho U là tập lồi, đóng, khác rỗng trong Rn , Φ : U × U → R ∪ {+∞} được gọi là một song hàm cân bằng trên U nếu Φ(u, u) = 0, ∀u ∈ U. Ví dụ 1.10. Cho hàm Φ(x, y) = x2 − y 2 ; x, y ∈ R. Hiển nhiên ta có Φ(x, x) = 0, ∀x ∈ R. Vậy Φ là một song hàm cân bằng trên R. 1.1.2 Bài toán cân bằng Bài toán cân bằng là bài toán có nhiều ứng dụng, nhất là trong lĩnh vực kinh tế. Sau đây ta sẽ trình bày bài toán cân bằng và một số tính chất của bài toán cân bằng. 8 Định nghĩa 1.11 (Bài toán cân bằng, Xem [4], Định nghĩa 2.1.4). Cho U là tập lồi, đóng, khác rỗng trong Rn , Φ : U × U → R ∪ {+∞} là một song hàm cân bằng trên U. Bài toán cân bằng là bài toán Tìm u∗ ∈ U sao cho Φ(u∗ , v) ≥ 0, ∀v ∈ U. (EP ) Ta kí hiệu tập nghiệm của bài toán cân bằng (EP) là SOL-EP(Φ, U). Định nghĩa 1.12 (Bài toán đối ngẫu của bài toán cân bằng, Xem [4]). Cho U là một tập lồi, đóng, khác rỗng trong Rn , Φ : U × U → R ∪ {+∞} là một song hàm cân bằng trên U. Bài toán đối ngẫu của bài toán cân bằng (EP) là bài toán Tìm v ∗ ∈ U sao cho Φ(u, v ∗ ) ≤ 0, ∀v ∈ U. (DP ) Ta kí hiệu tập nghiệm của bài toán đối ngẫu của bài toán cân bằng là (EP) là SOL-DP(Φ, U). Sau đây chúng ta sẽ tìm hiểu về sự tồn tại nghiệm và tính chất của bài toán cân bằng. Mệnh đề 1.13 (Xem [4]). Cho U là tập con lồi, đóng, khác rỗng của Rn , Φ : U × U → R ∪ {+∞} là một song hàm cân bằng sao cho với mỗi v ∈ U thì Φ(., v) là hàm nửa liên tục trên và mỗi u ∈ U thì Φ(u, .) là giả lồi. Ngoài ít nhất một trong các điều kiện sau thỏa mãn (i) U là tập compact (ii) Tồn tại tập con compact W 6= ∅ của U sao cho với mỗi u ∈ U \W có v ∈ W thỏa mãn Φ(u, v) < 0. Khi đó bài toán cân bằng (EP) có nghiệm. Mệnh đề 1.14 (Xem [4]). Cho U là tập con lồi, đóng, khác rỗng của Rn , Φ : U × U → R ∪ {+∞} là một song hàm cân bằng. Khi đó (i) Nếu Φ là đơn điệu ngặt trên U thì bài toán cân bằng (EP) có nhiều nhất một nghiệm. (ii) Nếu Φ(., v) là nửa liên tục trên với mỗi v ∈ U, Φ(u, .) là nửa liên tục 9 dưới với mỗi u ∈ U . Nếu có thêm Φ là đơn điệu mạnh trên U thì bài toán cân bằng (EP) có nghiệm duy nhất. Chứng minh. (i) Giả sử u∗ và v ∗ là hai nghiệm phân biệt của bài toán cân bằng (EP). Khi đó ta có Φ(u∗ , v ∗ ) ≥ 0, và Φ(v ∗ , u∗ ) ≥ 0. Mặt khác do Φ là đơn điệu ngặt trên U nên ta có Φ(u∗ , v ∗ ) + Φ(v ∗ , u∗ ) < 0; ∀u∗ , v ∗ ∈ U. Điều này vô lý. Vậy nếu Φ là đơn điệu ngặt thì bài toán cân bằng (EP) có nhiều nhất một nghiệm. (ii) Theo kết quả của (i) ta chỉ cần chứng minh bài toán cân bằng (EP) có nghiệm. Thật vậy, lấy điểm t ∈ U . Từ giả thiết Φ(t, .) là nửa liên tục dưới ta luôn có số µ > −∞ sao cho Φ(t, ω) ≥ µ, ∀ω ∈ A(t, 1) ∩ U, trong đó A(t, 1) là quả cầu tâm t, bán kính bằng 1. Chọn bất kỳ u ∈ U \A(t, 1), và số λ= 1 . |t − u| Khi đó ta có ω = λu + (1 − λ)t ∈ A(t, 1) ∩ U. Áp dụng tính lồi của Φ ta có µ ≤ Φ(t, ω) ≤ Φ(t, u)/ k t − u k . 10 Mặt khác Φ là đơn điệu mạnh ta có Φ(v, t) ≤ −µ k t − u k −r k t − u k2 = − k t − u k (µ + r k t − u k) < 0, nếu như −µ . r Đặt W = U ∩ A(t, µ0 ) với µ0 = max{1, −µ r }, ta thấy điều kiện (ii) trong Mệnh đề 1.13 thỏa mãn . Theo (ii) của Mệnh đề 1.13 ta có kết luận bài toán cân bằng (EP) có nghiệm, do đó Φ đơn điệu mạnh nên (EP) có nghiệm duy nhất . k t − u k> Mệnh đề 1.15 (Xem [4], Mệnh đề 2.1.15). Cho U là tập lồi, đóng, khác rỗng của Rn , Φ : U × U → R ∪ {+∞} là một song hàm cân bằng. Khi đó (i) Nếu Φ(u, .)là tựa lồi và liên tục dưới với mỗi u ∈ U thì tập nghiệm của bài toán đối ngẫu DP(Φ,U) lồi và đóng. (ii) Nếu Φ(., v) là nửa liên tục trên với mỗi v ∈ U và Φ(u, .) là lồi với mỗi u ∈ U thì tập nghiệm của bài toán đối ngẫu nằm trong tập nghiệm của bài toán cân bằng, nghĩa là SOL-EP(Φ, U)⊂ SOL-EP(Φ,U). (iii) Nếu Φ là giả đơn điệu thì tập nghiệm của bài toán cân bằng nằm trong tập nghiệm của bài toán đối ngẫu, nghĩa là SOL − EP (Φ, U ) ⊆ SOL − DP (Φ, U ). Bài toán bất đẳng thức biến phân đa trị Định nghĩa 1.16. Cho C là một tập con lồi, đóng khác rỗng của Rn , n F : C → 2R là ánh xạ đa trị . Khi đó bài toán bất đẳng thức biến phân đa trị được phát biểu như sau (MVI) : Tìm x∗ ∈ C và w∗ ∈ F (x∗ ) sao cho hw∗ , x − x∗ i ≥ 0, ∀x ∈ C. • F được gọi là ánh xạ giá của bài toán bất đẳng thức biến phân (MVI). • Khi F là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân ( viết tắt là (VI)) có dạng 11 Tìm x∗ ∈ C sao cho : hF (x∗ ), x − x∗ i ≥ 0, ∀x ∈ C. • Bài toán bất đẳng thức biến phân (MVI) có liên hệ mật thiết với nhiều bài toán như: Bài toán bù phi tuyến tính, bài toán điểm bất động, bài toán quy hoạch lồi,... Bài toán điểm bất động Kakutani Cho C là một tập lồi đóng tùy ý trong Rn và T là ánh xạ đa trị từ C vào 2c . Bài toán điểm bất động của ánh xạ đa trị T được phát biểu như sau Tìm x∗ ∈ C sao cho x∗ ∈ T (x∗ ). (1.1) Đặc biệt, nếu T là ánh xạ đơn trị thì bài toán điểm bất động Kakutani trở thành bài toán điểm bất động Brouwer có dạng Tìm x∗ ∈ C sao cho x∗ = T (x∗ ). Mệnh đề sau đây cho thấy mối liên hệ giữa bài toán (MVI) với bài toán điểm bất động (1.1). Mệnh đề 1.17. Giả sử ánh xạ F được xác định bởi F (x) = x−T (x), ∀x ∈ C . Khi đó, bài toán bất đẳng thức biến phân đa trị (MVI) tương đương với bài toán điểm bất động (1.1). Chứng minh. Giả sử x∗ là nghiệm bài toán (MVI) và F (x) = x − T (x), tức là hw∗ , x − x∗ i ≥ 0, ∀x ∈ C, w∗ ∈ F (x∗ ). Do w∗ ∈ F (x∗ ) = x∗ − T (x∗ ) nên tồn tại ξ ∗ ∈ T (x∗ ) sao cho w∗ = x∗ − ξ ∗ . Ta có hx∗ − ξ ∗ , x − x∗ i ≥ 0, ∀x ∈ C. Cho x = ξ ∗ ta được k x∗ − ξ ∗ k≤ 0. Suy ra x∗ = ξ ∗ hay x∗ ∈ T (x∗ ). Vậy nên x∗ là nghiệm của bài toán (1.1). Chiều ngược lại hiển nhiên đúng. 12 Bài toán bù phi tuyến. Chú ý rằng C là một nón lồi trong Rn thì bài toán (MVI) trở thành bài toán bù Tìm x∗ ∈ C, w∗ ∈ F (x∗ ), w ∈ C 0 sao cho hw∗ , x∗ i = 0, (CP ) trong đó C 0 = {y ∈ Rn |hx, yi ≥ 0; ∀x ∈ C} được gọi là nón đối ngẫu của C. Khi đó ta có mệnh đề sau Mệnh đề 1.18. Nếu C là nón lồi, đóng trong Rn thì bài toán bù (CP) tương đương với bài toán bất đẳng thức biến phân (MVI). Chứng minh. Nếu x∗ là nghiệm của bài toán bất đẳng thức biến phân (MVI) và w∗ ∈ F (x∗ ) thì hw∗ , x − x∗ i ≥ 0, ∀x ∈ C. (1.2) Do C là nón lồi, x∗ ∈ C nên x∗ + x ∈ C, ∀x ∈ C. Trong bất đẳng thức (1.2) ta thay x bởi x∗ + x, ta được hw∗ , x∗ + x − x∗ i = hw∗ , xi ≥ 0, ∀x ∈ C. Suy ra w∗ thuộc nón đối ngẫu C 0 . Còn nếu thay x = 0 vào (1.2) ta được hw∗ , x∗ i ≤ 0. Suy ra hw∗ , x∗ i = 0, hay x∗ ∈ C, w∗ ∈ F (x∗ ), w∗ ∈ C 0 là nghiệm của bài toán bù (CP). Ngược lại, nếu x∗ ∈ C là nghiệm của bài toán bù thì hw∗ , x∗ i = 0, w∗ ∈ F (x∗ ), w∗ ∈ C 0 . Hay x∗ ∈ C, w∗ ∈ F (x∗ ) là nghiệm của bài toán (MVI). 13 Bài toán quy hoạch lồi. Cho C ⊆ Rn là một tập lồi, đóng, khác rỗng và f : C → R ∪ {+∞} là một hàm lồi trên C . Bài toán quy hoach lồi được phát biểu như sau Tìm x∗ ∈ C sao cho f (x) = min{f (x)|x ∈ C}. (1.3) Trong trường hợp f là hàm lồi, khả vi, ta có mệnh đề sau Mệnh đề 1.19. Giả sử f : C → R là hàm khả vi, lồi trên tập lồi C ⊂ Rn . Khi đó, x∗ ∈ C là nghiệm của bài toán (1.3) khi và chỉ khi x∗ là nghiệm của bài toán bất đẳng thức biến phân (VI), với F (x) := ∇f (x). Chứng minh. Giả sử x∗ là nghiệm của bài toán (1.3), tức là f (x∗ ) ≤ f (x); ∀x ∈ C. Để chứng minh x∗ nghiệm cuả bài toán (VI), ta giả sử ngược lại rằng h∇f (x∗ ), x − x∗ i < 0, ∀x ∈ C. Khi đó, lấy α > 0 đủ nhỏ, do C là tập lồi nên yα = x∗ + α(x − x∗ ) = αx + (1 − α)x∗ ∈ C, ∀x ∈ C, và f (yα ) = f (x∗ ) + αh∇f (x∗ ), x − x∗ i + θ(x) < f (x∗ ), tức x∗ không là nghiệm của bài toán (1.3). Điều này trái với giả thiết. Vậy, x∗ là nghiệm của bài toán (VI). Ngược lại, nếu x∗ là nghiệm của bài toán (VI), tức là h∇f (x∗ ), x − x∗ i ≥ 0, ∀x ∈ C. Do f là hàm lồi, khả vi nên f (x) − f (x∗ ) ≥ h∇f (x∗ ), x − x∗ i, ∀x ∈ C. Suy ra f (x) ≥ f (x∗ ), ∀x ∈ C, hay, x∗ là nghiệm của bài toán (1.3). 14 Trong trường hợp f là hàm không lồi thì ta có thể mở rộng Mệnh đề trên cho trường hợp khả vi dưới vi phân như sau Mệnh đề 1.20 (Xem [3], 3.5). Cho C ⊂ Rn là một tập lồi, đóng, khác rỗng. Giả sử f : C → R là hàm lồi, khả dưới vi phân trên C . Khi đó, x∗ là nghiệm của bài toán (1.3) khi và chỉ khi x∗ là nghiệm của bài toán bất đẳng thức biến phân (MVI), với F (x) := ∂f (x). Chứng minh. Giả sử x∗ ∈ C và w∗ ∈ ∂f (x) nên hw∗ , x − x∗ i ≥ 0, ∀x ∈ C. Vì w∗ ∈ ∂f (x∗ ) nên hw∗ , x − x∗ i ≤ f (x) − f (x∗ ), ∀x ∈ C. Từ đó suy ra f (x∗ ) ≤ f (x), ∀x ∈ C, hay, x là nghiệm của bài toán (1.3) Ngược lại, hiển nhiên đúng. Ví dụ 1.21 (Bài toán xác định phương án sản xuất). Gọi C là tập phương án sản xuất chấp nhận được và x = (x1 , x2 , ..., xn ) ∈ Rn được gọi là số lượng sản phẩm, với xi là sản phẩm thứ i. Đặt F (x) là tập các chi phí sản xuất ứng với phương án sản xuất x. Bài toán đặt ra là hãy tìm một phương án sản xuất chấp nhận đước sao cho ứng với phương án này có một chi phí là thấp nhất. Bài toán này có thể được mô ta dưới bài toán bất đẳng thức biến phân sau Tìm x∗ ∈ C sao cho hF (x∗ ), x − x∗ i ≥ 0, ∀x ∈ C. 15 1.2 1.2.1 Mô hình cân bằng với cước phí tuyến tính Phát biểu mô hình Nash - Cournot Giả sử trong nền kinh tế thị trường có n hãng tham gia sản xuất cùng một loại sản phẩm. Kí hiệu xi ∈ Vi ⊆ R+ là sản phẩm mã hàng i(i = 1, 2, ..., n) dự định sẽ thực hiện. Ta giả sử rằng giá của một đơn vị sản phẩm do hãng i cung cấp là pi và nó phụ thuộc vào tổng sản lượng n P xi , nghĩa là ta có pi := pi (σ). Đặt của tất cả các hãng, kí hiệu là σ := i=1 hi (xi ) là tổng chi phí sản xuất của hãng i khi hãng thực hiện kế hoạch sản lượng xi và hàm lợi nhuận của hãng được xác định bởi n X fi (x1 , x2 , ..., xn ) = xi pi ( xi ) − hi (xi ), i = 1, 2, ..., n, i=1 trong đó hi là hàm chi phí của hãng i chỉ phụ thuộc trên mức sản suất của nó. Mỗi hãng đều có chung một mong muốn là tìm một phương án sản xuất để là cực đại hàm lợi nhuận của hãng mình. Ta gọi Vi (i = 1, 2, .., n) là tập chiến lược sản phẩm của hãng i và đặt V = V1 × V2 × ... × Vn là tập chiến lược của tất cả các hãng. Từ đó ta có định nghĩa sau Định nghĩa 1.22. Điểm x∗ = (x∗1 , x∗2 , ..., x∗n ) ∈ V được gọi là điểm cân bằng Nash của mô hình cân bằng Nash-Cournot nếu ∀i = 1, 2, ..., n, và với mọi yi ∈ Vi ta đều có fi (x∗1 , x∗2 , ..., x∗i−1 , yi , x∗i+1 , ..., x∗n ) ≤ fi ((x∗1 , x∗2 , ..., x∗i−1 , xi , x∗i+1 , ..., x∗n ). (1.4) Đặt (x∗1 , x∗2 , ..., x∗i−1 , yi , x∗i+1 , ..., x∗n ) = (x∗ [yi ]), thì (1.4) tương đương với fi (x∗ [yi ]) ≤ fi (x∗1 , x∗2 , ..., x∗i−1 , xi , x∗i+1 , ..., x∗n ). Từ định nghĩa trên ta nhận thấy điểm cân bằng có ý nghĩa kinh tế như sau 16 Tại điểm cân bằng, nếu một hãng i0 (1 ≤ i0 ≤ n) nào đó tự ý thay đổi sản lượng của hãng mình, trong khi các hãng khác giữ nguyên sản lượng cân bằng, thì lợi nhuận không tăng thêm. Do đó các hãng đều muốn mình ở vị trí cân bằng. Với mỗi x = (x1 , x2 , ..., xn ) ∈ V và y = (y1 , y2 , ..., yn ) ∈ V, ta đặt Ψ(x, y) = − n X fi (x∗1 , x∗2 , ..., x∗i−1 , yi , x∗i+1 , ..., x∗n ), (1.5) i=1 và Φ(x, y) = Ψ(x, y) − Ψ(x, x). (1.6) Mệnh đề dưới đây nói rằng, bài toán tìm điểm cân bằng của mô hình Nash - Cournot tương đương bài toán cân bằng sau Tìm x∗ ∈ V sao cho Φ(x, y) ≥ 0, ∀y ∈ V . Mệnh đề 1.23. Điểm x∗ ∈ V là một điểm cân bằng khi và chỉ khi x∗ là một nghiệm của bài toán cân bằng (EP). Chứng minh. Giả sử x∗ ∈ V là điểm cân bằng của mô hình. Khi đó fi (x∗ [yi ]) ≤ fi (x∗ ), ∀i = 1, 2, ..., n, ∀yi ∈ Vi , suy ra n X ∗ fi (x [yi ]) ≤ i=1 hay − n X i=1 n X fi (x∗ ), ∀i = 1, 2, ..., n, ∀yi ∈ Vi , i=1 ∗ fi (x [yi ]) ≥ − n X fi (x∗ ), ∀i = 1, 2, ..., n, ∀yi ∈ Vi , i=1 tức là ta có Ψ(x∗ , y) ≥ Ψ(x∗ , x∗ ), ∀y ∈ V. Khi đó Φ(x∗ , y) = Ψ(x∗ , y) − Ψ(x∗ , x∗ ) ≥ 0, ∀y ∈ V.