Tài liệu Luận văn về một mô hình cân bằng nash cournot với cước phí lõm

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ———————o0o——————– NGUYỄN THỊ MAI VỀ MỘT MÔ HÌNH CÂN BẰNG NASH - COURNOT VỚI CƯỚC PHÍ LÕM LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2016 2 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ———————o0o——————– NGUYỄN THỊ MAI VỀ MỘT MÔ HÌNH CÂN BẰNG NASH - COURNOT VỚI CƯỚC PHÍ LÕM 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 2016 1 Mục lục Lời mở đầu 1 Kiến thức chuẩn bị 1.1 Tập lồi, hàm lồi, hàm lõm . 1.2 Cực trị của hàm lồi . . . . 1.3 Toán tử đơn điệu . . . . . 1.4 Bất đẳng thức biến phân . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 8 11 14 2 Mô hình Nash - Cournot với cước phí lõm 2.1 Mô hình Nash - Cournot cổ điển . . . . . . . . . . . . . . . 2.1.1 Khái niệm mô hình . . . . . . . . . . . . . . . . . . 2.1.2 Chuyển mô hình về bài toán quy hoạch hàm toàn phương lồi mạnh . . . . . . . . . . . . . . . . . . . . 2.2 Mô hình cân bằng Nash - Cournot với cước phí lõm . . . . . 2.2.1 Mô hình cân bằng Nash - Cournot với cước phí lõm . 2.2.2 Thuật giải . . . . . . . . . . . . . . . . . . . . . . . 18 18 18 Kết luận 38 Tài liệu tham khảo 39 22 27 27 33 2 Lời mở đầu Mô hình cân bằng thị trường bán độc quyền 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 chung 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 tiếp cận thường được dùng trong mô hình Cournot là sử dụng khái niệm cân bằng Nash. Một trong những hướng nghiên cứu quan trọng của mô hình là giải quyết các bài toán với mô hình cước phí lõm. Trong những bài toán thực tế, khi số lượng hàng hóa sản xuất tăng lên thì cước phí để sản xuất một đơn vị sản phẩm sẽ giảm đi. Do đó cước phí sẽ là lõm. Nội dung của luận văn này trình bày về cách tiếp cận mô hình cân bằng Nash - Cournot với cước phí lõm, và nghiên cứu về thuật toán để tìm ra điểm cân bằng khi mô hình có cước phí là lõm. Bản luận văn gồm hai chương: Chương 1: Kiến thức chuẩn bị Trong chương này tìm hiểu các kiến thức về tập lồi, hàm lồi, hàm lõm, toán tử đơn điệu, cực trị của hàm lồi. Sau đó là tìm hiểu về bất đẳng thức biến phân. Chương 2: Mô hình Nash - Cournot với cước phí lõm Giới thiệu về mô hình Nash - Cournot cổ điển và cách chuyển mô hình về dạng bài toán quy hoạch hàm toàn phương lồi mạnh. Sau đó, nghiên cứu mô hình Nash - Cournot với cước phí lõm và giới thiệu một phương pháp giải mô hình trong trường hợp hàm chi phí lõm và tuyến tính từng khúc. Nhân dịp 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. Tôi cũng xin kính gửi lời cảm ơn tới toàn thể thầy cô tham gia giảng dạy khóa học cao học 2014 - 2016, những người đã tâm huyết giảng dạy MỤC LỤC trang bị cho tôi những kiến thức cơ sở. Xin gửi lời cảm ơn tới Ban giám hiệu, phòng Đào tạo, khoa Toán - Tin trường Đại học Khoa học, Đại học Thái Nguyên đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập tại trường. Đồng thời, tôi cũng xin gửi lời cảm ơn tới gia đình, bạn bè đồng nghiệp và các thành viên trong lớp cao học toán K8A đã luôn quan tâm, động viên, giúp đỡ tôi trong thời gian học tập và quá trình làm luận văn. Thái Nguyên, ngày 25 tháng 05 năm 2016. Tác giả Nguyễn Thị Mai 3 4 Chương 1 Kiến thức chuẩn bị Trong chương này chúng ta sẽ giới thiệu những kiến thức cơ bản về tập lồi, hàm lồi, toán tử đơn điệu... Tiếp đó là trình bày về bài toán bất đẳng thức biến phân. Các kiến thức ở chương này được tổng hợp từ các tài liệu [1], [2], [3], [7]. 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 , ..., xn )T ∈ Rn là một vectơ cột. Ta nhắc lại với hai véctơ x = (x1 , ..., xn ), y = (y1 , ..., yn ) ∈ Rn , hx, yi := n X xi yi , i=1 đượ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 như sau: q kxk := hx, yi, d (x, y) := kx − yk . 1.1 Tập lồi, hàm lồi, hàm lõm Định nghĩa 1.1. Một tập C ⊂ Rn được gọi là tập lồi nếu với ∀x, y ∈ C , mọi 0 ≤ λ ≤ 1, ta có: λx + (1 − λ) y ∈ C. Một số ví dụ về tập lồi: Các tập afin (các siêu phẳng), hình tròn, hình vuông... Tuy nhiên, hình vành khăn, đường tròn không phải là tập lồi. Định nghĩa 1.2. Hàm f : Rn → R ∪ (+∞) được gọi là: (i) Lồi trên C nếu với mọi λ ∈ (0, 1), mọi x, y ∈ C ta có: f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) . Chương 1. Kiến thức chuẩn bị (ii) Lồi chặt trên C nếu mọi λ ∈ (0, 1), mọi x, y ∈ C , mọi x 6= y ta có: f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) . (iii) Lồi mạnh rên C nếu với mọi λ ∈ (0, 1), mọi x, y ∈ C , tồn tại η ∈ R, η > 0 ta có: 1 f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) − λ (1 − λ) ηkx − yk2 . 2 (iv) Lõm trên C nếu −f là hàm lồi trên C. Định nghĩa 1.3. Cho hàm bất kỳ: f : S → (−∞, +∞] với S ⊆ Rn , các tập domf = {x ∈ S : f (x) < +∞} , và epif = {(x, α) ∈ S × R : f (x) ≤ α} . được gọi lần lượt là miền hữu dụng và tập lồi trên đồ thị của hàm f . Nếu domf 6= φ; f (x) > −∞ ∀x ∈ S thì ta nói f là chính thường. Nói cách khác f là chính thường nếu domf 6= φ. Định lý 1.1. Hàm f (x), x ∈ Rn là hàm lồi khi và chỉ khi hàm một biến số ϕ (λ) ≡ f (x + λd) là hàm lồi theo λ với mỗi x, d ∈ Rn . Chứng minh. Ta thấy điều kiện cần là rõ ràng. Ta chứng minh điều kiện đủ. Giả sử ϕ (λ) là hàm lồi với mọi x, d ∈ Rn . Lấy bất kỳ x, y ∈ Rn và đặt d = x − y . Khi đó, với mọi λ ∈ [0, 1] ta có: f ((1 − λ) x + λy) = f (x + λd) = ϕ (λ) = ϕ ((1 − λ) .0 + λ.1) ≤ (1 − λ) ϕ (0) + λϕ (1) = (1 − λ) f (x) + λf (y) .  Định nghĩa 1.4. Một hàm a-phin 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 a-phin 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 a-phin f (x) = hc, xi + α không lấy giá trị âm thì phải đồng nhất với một hằng số (véctơ c phải bằng 0), vì nếu c 6= 0 thì ta sẽ có: f (λx) = hc, xi + α → −∞, khi λ → −∞. 5 Chương 1. Kiến thức chuẩn bị Định nghĩa 1.5. Một tập con M của Rn được gọi là nón (mũi tại 0) nếu x ∈ M, λ > 0 thì λx ∈ M . Nón M gọi là nón lồi nếu M là tập lồi. Điểm gốc 0 có thể thuộc hoặc không thuộc M. Nón M không chứa đường thẳng nào gọi là nón nhọn. Trong trường hợp này, gốc 0 gọi đỉnh của M. Mỗi nửa không gian (đóng hay mở) đều là một nón, nhưng không phải là một nón nhọn. Định lý 1.2. Tập con M của Rn là một nón lồi có đỉnh tại gốc khi và chỉ khi λM ⊂ M, ∀λ > 0 và M + M ⊂ M . Nghĩa là với mọi x, y thuộc M và với mọi số λ > 0 ta có x + y ∈ M và λx ∈ M . Chứng minh. Nếu M là một nón lồi thì thì λM ⊂ M, ∀λ > 0 theo định nghĩa của nón. Hơn nữa, lấy x, y ∈ M thì do M lồi nên 21 (x + y) ∈ M , do đó theo trên x + y ∈ M . Vì thế M + M ⊂ M . Ngược lại, nếu có λM ⊂ M, ∀λ > 0 và M + M ⊂ M thì M là một nón và với mọi x, y ∈ M , λ ∈ [0, 1] ta có: (1 − λ) x ∈ M, λy ∈ M . Từ đó, (1 − λ) x + λy ∈ M , nghĩa là M là một tập lồi.  Tập con M ∈ C là một nón lồi khi và chỉ khi nó chứa mọi tổ hợp tuyến tính không âm (còn gọi là tổ hợp nón) của các phần tử thuộc nó. Nhận xét 1.1. * Có thể chứng minh hàm f lồi trên S khi và chỉ khi: +) Tập trên đồthị epif là một tập lồi hoặc m m m
P P P +) f λk xk ≤ λk f xk , ∀xk ∈ S, λk = 1, λk ≥ 0 với mọi k=1 k=1 k=1 k , trong đó m là số nguyên ≥ 2 ( Bất đẳng thức Jensen). * Hàm lồi f : S → (−∞, +∞] có thể được mở rộng thành lồi xác định trên toàn không gian Rn bằng cách đặt f (x) = +∞ ∀x ∈ / S . Vì vậy, để n đơn giản ta thường xét hàm lồi trên toàn R . Định nghĩa 1.6. Bao đóng của một tập C, kí hiệu là C là giao của tất cả các tập đóng chứa C. Định nghĩa 1.7. Một điểm a ∈ C được gọi là điểm trong tương đối của C nếu nó là điểm trong của C theo tô-pô cảm sinh bởi af f C (tập a-phin nhỏ nhất chứa C). Kí hiệu tập các điểm trong tương đối của C là riC . Theo định nghĩa ta có: riC := {a ∈ C|∃B : (a + B) ∩ affC ⊂ C} . 6 Chương 1. Kiến thức chuẩn bị trong đó B là một lân cận mở của gốc. Hiển nhiên riC = {a ∈ affC|∃B : (a + B) ∩ affC ⊂ C} . Định lý 1.3. Bao đóng và phần trong tương đối của một tập lồi là tập lồi. Chứng minh. Giả sử C là một tập lồi và a, b ∈ C . Chẳng hạn a = lim xk , b = lim y k , trong đó xk , y k ∈ C với mọi k . Với k→∞ k→∞ k mọi λ ∈ [0, 1] ta có: (1 − λ) x + λy k ∈ C . Từ đó:  (1 − λ) a + λb = lim (1 − λ) xk + λy k ∈ C. k→∞ Như vậy, nếu a, b ∈ C thì [a, b] ⊂ C chứng tỏ C lồi. Bây giờ, giả sử a, b ∈ riC . Khi đó tìm được hình cầu B tâm O sao cho: (a + B) ∩ af f C và (b + B) ∩ af f C nằm trọn trong C. Với ∀x = (1 − λ) a + λb, λ ∈ [0, 1] , Ta có: (x + B) ∩ af f C = (1 − λ) (a + B) ∩ af f C + λ (b + B) ∩ af f C ⊂ C. Như vậy x ∈ riC , nghĩa là riC lồi.  Tính chất 1.1. a) Giao của một họ bất kỳ các tâp lồi là một tập lồi; b) Nếu C, D ∈ Rn là các tập lồi thì: C + D = {x + y : x ∈ C, y ∈ D} , αC = {αx : x ∈ C, α ∈ R} , C − D = C + (−1) D. c) Bao đóng của một tập hợp lồi là một tập lồi; d) Tập hợp của 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 C ∈ Rn được gọi là lồi chặt nếu với mọi 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. Mệnh đề 1.1. (i) Cho f và g là các hàm lồi lần lượt trên các tập lồi A và B, với A ∩ B 6= φ. Khi đó, hàm (λf ) + (βg) lồi trên, với mọi λ, β ≥ 0; (ii) Giới hạn theo từng điểm của một dãy các hàm lồi cũng là một hàm lồi. Tức là: fi : C → R (i ∈ N ) và dãy số {fi (x)} hội tụ với mỗi x ∈ C 7 Chương 1. Kiến thức chuẩn bị thì hàm f (x) := lim fi (x) cũng lồi trên C; i→∞ (iii) Nếu f : C → R lồi trên C và hàm một biến ϕ : I → R không giảm trên khoảng I, sao cho f (C) ⊆ I ,thì hàm hợp ϕ0 f lồi trên C. 1.2 Cực trị của hàm lồi Định nghĩa 1.8. Cho C ⊆ Rn khác rỗng và f : Rn → (−∞, +∞]. Một điểm x∗ ∈ C được gọi là cực tiểu địa phương của f trên C nếu tồn tại một lân cận U của x∗ sao cho: f (x∗ ) ≤ f (x) ∀x ∈ U ∩ C; Điểm x∗ ∈ C được gọi là cực đại địa phương nếu: f (x) ≤ f (x∗ ) ∀x ∈ U ∩ C; Nếu f (x) ≥ f (x∗ ) ∀x ∈ C; thì x∗ được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C. Và nếu: f (x) ≤ f (x∗ ) ∀x ∈ C; thì x∗ được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C. Mệnh đề 1.2. Cho f : Rn → Rn ∪ {+∞} lồi. Khi đó, mọi điểm cực tiểu địa phương của f trên một tập lồi đều là cực tiểu toàn cục. Hơn nữa tập hợp các điểm cực tiểu của f là một tập lồi. Nếu f lồi chặt, thì điểm cực tiểu nếu tồn tại sẽ là duy nhất. Chứng minh. Cho C ⊆ Rn . Giả sử x∗ là điểm cực tiểu địa phương của f trên C. Khi đó tồn tại lân cận U của x∗ sao cho: f (x∗ ) ≤ f (x) ∀x ∈ U ∩ C. với mọi x ∈ C , và 0 < λ < 1 do C lồi và U là lân cận của x∗ ∈ C , nên điểm xλ := (1 − λ) x∗ + λx ∈ C ∩ U khi λ đủ nhỏ. Do f (x∗ ) ≤ f (xλ ) và f lồi, ta có: f (x∗ ) ≤ f (xλ ) ≤ (1 − λ) f (x∗ ) + λf (x) . Từ đây suy ra: f (x∗ ) ≤ f (x) . 8 Chương 1. Kiến thức chuẩn bị Chứng tỏ x∗ là cực tiểu toàn cục của f trên C. Giả sử x∗ , y ∗ ∈ C là điểm cực tiểu của f trên C. Vậy f (x∗ ) = f (y ∗ ) ≤ f (x) với mọi x ∈ C . Lấy z ∗ := λx∗ + (1 − λ) y ∗ , với 0 < λ < 1. Do C lồi, nên z ∗ ∈ C và do f lồi, nên: f (z ∗ ) ≤ (1 − λ) f (y ∗ ) + λf (x∗ ) ≤ f (x) . Suy ra z ∗ cũng là điểm cực tiểu của f trên C. Chứng tỏ tập các điểm cực tiểu của f trên C là lồi. Dễ thấy tập hợp này chỉ gồm nhiều nhất một điểm khi f lồi chặt.  Mệnh đề 1.3. (i) Giả sử f là một hàm lồi chính thường trên Rn và C ⊆ Rn là một tập lồi. Khi đó, nếu f đạt cực đại trên C tại một điểm trong tương đối của C mà tại đó hàm có giá trị hữu hạn thì f là hằng số trên C. (ii) Nếu f là một hàm lồi chính thường trên Rn và bị chặn trên trong một tập a-phin, thì nó là hằng số trên tập này. Chứng minh. (i) Giả sử a ∈ riC là điểm tại đó f đạt cực đại của nó trên C. Theo tính chất của điểm trong tương đối, nên với mọi x ∈ C , đều tồn tại y ∈ C sao cho a ∈ (x, y). Do f (x) ≤ f (a), f (y) ≤ f (a) và f lồi, nên suy ra f (a) = f (b). (ii) Nếu f không là hằng số trên tập a-phin M, có nghĩa là tồn tại a, b ∈ M sao cho f (a) < f (b). Mọi điểm x thuộc nửa đường thẳng xuất phát từ a và có hướng b – a đều có dạng x = a + λ (b − a) với λ > 0. Khi đó: 1 λ−1 b= x+ a. λ λ Với mọi λ > 0, theo tính lồi của f ta có: f (b) ≤ 1 λ−1 f (x) + f (a) . λ λ Từ đây và do giả thiết f (x) ≤ m < ∞ với mọi x ∈ M , ta suy ra f (b) − f (a) ≤ 1 1 1 f (x) − f (a) ≤ [m − f (a)] . λ λ λ Điều này đúng với mọi λ > 1, nên khi cho λ → +∞ ở về phải, do f (a) hữu hạn, nên vế phải tiến tới 0, trong khi đó theo giả thiết, về trái 9 Chương 1. Kiến thức chuẩn bị f (b) − f (a) > 0. Mâu thuẫn. Vậy f phải là hằng số trên tập a-phin M.  Định nghĩa 1.9. Cho f : Rn → R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại x nếu: hx∗ , z − xi + f (x) ≤ f (z)∀z. Tương tự đối với hàm lồi khả vi thông thường, biểu thức này có nghĩa là phương trình tiếp tuyến nằm dưới đồ thị của hàm số. Tuy nhiên khác với trường hợp khả vi, tiếp tuyến ở đây có thể không duy nhất. Ký hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂f (x). Nói chung đây là một tập (có thể bằng rỗng) trong Rn . Khi ∂f (x) 6= φ thì ta nói hàm f khả vi dưới vi phân tại x. Theo định nghĩa, một điểm x∗ ∈ ∂f (x) khi và chỉ khi nó thỏa mãn một hệ vô hạn các bất đẳng thức tuyến tính. Như vậy ∂f (x) là giao của các nửa không gian đóng. Vậy ∂f (x) luôn là tập lồi đóng (có thể rỗng). Như trong lý thuyết toán tử đa trị, ta sẽ kí hiệu: dom (∂f ) := {x|∂f (x) 6= φ} . Mệnh đề 1.4. Cho f : Rn → R ∪ {+∞} lồi, chính thường. (i) x∗ ∈ ∂f (x) khi và chỉ khi f 0 (x, y) ≥ hx∗ , yi , ∀y. Nếu x ∈ ri (domf ) thì f 0 (x, y) = sup hx∗ , yi , ∀y; x∗∈∂f (x) (ii) Nếu f là hàm lồi chính thường trên Rn , thì với mọi x∗ ∈ dom (∂f ) ta có: f (x) = f (x) và ∂f (x) = ∂f (x) . Chứng minh. (i) Theo định nghĩa x∗ ∈ ∂f (x) ⇔ hx∗ , z − xi + f (x) ≤ f (z) , ∀z, Với bất kỳ y ta lấy, z = x + λy, λ > 0, ta có: hx∗ , λyi + f (x) ≤ f (x + λy) , từ đây suy ra: hx∗ , yi ≤ f (x + λy) − f (x) , ∀λ > 0, λ Theo định nghĩa dưới vi phân của f 0 (x, y), từ đây suy ra ngay: 10 Chương 1. Kiến thức chuẩn bị hx∗ , yi ≤ f 0 (x, y) , ∀y; Ngược lại hx∗ , yi ≤ f 0 (x, y) ∀y thỏa mãn. Lấy z bất kỳ và áp dụng hx∗ , yi ≤ f 0 (x, y) ∀y với y = z − x và λ = 1. Ta có: f (x + y) − f (x) ≥ f 0 (x, y) = f 0 (x, z − x) ≥ hx∗, z − xi , ∀z, Vậy x∗ ∈ ∂f (x). (ii) Cho x ∈ dom (∂f ) và x∗ ∈ ∂f (x). Theo định nghĩa của f , của hàm liên hợp và do x∗ ∈ ∂f (x) ta có: f (x) ≥ f (x) = f ∗∗ (x) ≥ hx∗ , xi − f ∗ (x∗ ) = f (x) , Từ đây suy ra: f (x) = f (x). Nếu y ∗ ∈ ∂f (x), thì với mọi z có: f (z) ≥ f (z) ≥ f (x) + hy ∗ , z − xi = f (x) + hy ∗ , z − xi . Suy ra ∂f (x) ⊆ ∂f (x) . Để chứng minh điều ngược lại, lấy z 0 ∈ ri (domf). Với mọi z ta có:   f (z) = lim f (1 − t) z + tz 0 . t↓0 Vậy theo định nghĩ dưới vi phân ta có:    f (1 − t) z + tz 0 ≥ f (x) + x∗ , (1 − t) z + tz 0 − x , Cho t & 0 ta được: f (x) ≥ f (x) + hx∗ , z − xi = f (x) + hx∗ , z − xi . Chứng tỏ x∗ ∈ ∂f (x).  1.3 Toán tử đơn điệu Định nghĩa 1.10. Cho C là một 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. 11 Chương 1. Kiến thức chuẩn bị (ii) Đơn điệu mạnh trên C với mỗi hằng số η > 0 nếu với mỗi cặp u, v ∈ C có: hQ (u) − Q (v) , u − vi ≥ η||u − v||2 . (iii) Đơn điệu ngặt trên C nếu với mọi u, v ∈ C và mọi u 6= v ta có: hQ (u) − Q (v) , u − vi > 0. (iv) Giả đơn điệu trên C nếu với 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.11. Đồ thị (grF ), miền hữu dụng (domF ), miền ảnh (rgeF ) của ánh xạ đơn trị F : X → Y , được định nghĩa tương ứng bằng công thức sau: grF = {(x, y) ∈ X × Y : y = F (x)} ; domF = {x ∈ X : ∃y : F (x) = y} ; rge = {y ∈ Y : ∃x ∈ X : y = F (x)} . Trong không gian hữu hạn chiều Rn toán tử tuyến tính được cho là một ma trận và toán tử liên hợp chính là chuyển vị của ma trận đó. Ví dụ 1.1. Cho f : H → (−∞, +∞] là hàm lồi chính thường khả vi. Khi đó, ∇f là đơn điệu. Chứng minh. Lấy (x, u) và (y, v) ∈ gra∇f . Ta có: hx − y|ui + f (y) ≥ f (x) , và hy − x|vi + f (x) ≥ f (y) , Cộng theo vế hai bất đẳng thức trên ta được: hx − y|u − vi ≥ 0.  Định lý 1.4. Toán tử tuyến tính A : Rn → Rn là đơn điệu trên Rn khi và chỉ khi: hAz, zi ≥ 0, ∀z ∈ Rn . 12 Chương 1. Kiến thức chuẩn bị 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 , hay hA (x − y) , x − yi ≥ 0, ∀x, y ∈ Rn , Đặt z = x − y ta có: hA (z) , zi ≥ 0, ∀z ∈ Rn .  Suy ra điều phải chứng minh. Định lý 1.5. (Phép toán bảo toàn tính đơn điệu) Các tính chất sau luôn đúng (i) Nếu T1 , T2 là toán tử đơn điệu từ Rn → Rn 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. (ii) Nếu T : Rn → Rn 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) 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ó: hu1 − v1 , x − yi ≥ 0, 13 Chương 1. Kiến thức chuẩn bị hu2 − v2 , x − yi ≥ 0. Nhân lần lượt hai vế của 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. (ii) 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 (Ax + 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.  1.4 Bất đẳng thức biến phân Cho C là tập con lồi đóng khác rỗng của H và ánh xạ F : C → H là liên tục. Bài toán bất đẳng thức biến phân được định nghĩa như sau: Tìm x∗ ∈ C sao cho: hF (x∗ ) , x − x∗ i ≥ 0, ∀x ∈ C. (1.1) Bài toán bất đẳng thức biến phân được kí hiệu là VIP (C; F). Tập tất cả các nghiệm của VIP (C; F) được kí hiệu là SOL - VIP (C; F). Khi F là đạo hàm của hàm lồi thì bài toán VIP tương đương với bài toán quy hoạch lồi. Cho H là không gian Rn , C là tập con lồi đóng khác rỗng của H , F : C → H là ánh xạ đơn điệu và ϕ là hàm lồi chính thường của H . Ta 14 Chương 1. Kiến thức chuẩn bị xét bài toán bất đẳng thức biến phân tổng quát sau (còn gọi là bất đẳng thức biến phân hỗn hợp): Tìm x∗ ∈ C sao cho: hF (x∗ ) , x − x∗ i + ϕ (x) − ϕ (x∗ ) ≥ 0, ∀x ∈ C. (1.2) trong đó, h., .i là tích vô hướng trong H . Thấy rằng khi ϕ khả vi liên tục trên C , bất đẳng thức (1.2) tương đương với: Tìm x∗ ∈ C sao cho: hF (x∗ ) + ∇ϕ (x∗ ) , x − x∗ i ≥ 0, ∀x ∈ C. (1.3) Với bài toán (1.2) ta xét hàm đánh giá sau:   1 g(x) := − min hF (x), y − xi + hy − x, G(y − x)i + ϕ(y) − ϕ(x), y ∈ C , 2 (1.4) trong đó G là ma trận đối xứng xác định dương. Trong trường hợp ϕ là khả vi ta thu được hàm đánh giá:   1 g1 (x) = − min hF (x) + ∇ϕ(x), y − xi + hy − x, G(y − x)i , y ∈ C . 2 (1.5) Chú ý rằng hàm mục tiêu trong bài toán xác định g1 (x) là hàm toàn phương lồi mạnh.Vì C là lồi đóng và hàm mục tiêu là lồi mạnh nên bài toán quy hoạch (1.4) và (1.5) luôn giải được với x ∈ C . Cho h (x) và h1 (x) tương ứng là nghiệm duy nhất của bài toán (1.4) và (1.5). Nếu ϕ là hàm hằng thì hai ánh xạ h (x) và h1 (x) là trùng nhau. Vì thế, trong trường hợp này h (x) = h1 (x) với mọi x ∈ U . Ngoài ra, cả h (x) và h1 (x) có tính chất chung là một điểm x∗ là nghiệm của bài toán bất đẳng thức biến phân hỗn hợp (1.2) nếu và chỉ nếu h (x∗ ) = h1 (x∗ ) = x∗ . Định lý 1.6. Cho C khác rỗng, C ⊂ Rn là tập compact và lồi, ánh xạ F : C → Rn liên tục, khi đó bài toán bất đẳng thức biến phân (1.1) có nghiệm, tức là tồn tại x∗ ∈ C thỏa mãn: hF (x∗ ) , x − x∗ i ≥ 0, ∀x ∈ C. Chứng minh. Xây dựng ánh xạ Φ bằng cách với mỗi x ∈ C đặt: Φ (x) := PC (x − F (x)) . Ta có: Φ : C → C, 15 Chương 1. Kiến thức chuẩn bị Do F liên tục trên C và phép chiếu PC liên tục nên Φ liên tục. Vậy định lý điểm bất động Brouwer tồn tại: x∗ = Φ (x∗ ) . Theo định nghĩa của Φ, thì: x∗ = Φ (x∗ ) := PC (x∗ − F (x∗ )) . Theo tính chất của hình chiếu, ta có: hF (x∗ ) , x − x∗ i ≥ 0, ∀x ∈ C. Vậy bài toán bất đẳng thức biến phân (1.1) có nghiệm.  P P Cho tập lồi C 6= φ, đặt CR = C ∩ R trong đó R là hình cầu đóng bán kính R tâm O ∈ Rn . Khi đó CR là tập compact. Từ đó ta có: xR ∈ CR : hF (xR ) , y − xR i ≥ 0, ∀y ∈ CR . (1.6) Định lý 1.7. Cho C ∈ Rn là tập lồi, đóng và ánh xạ: F : C → Rn , liên tục trên C . Điều kiện cẩn và đủ để tồn tại nghiệm của bài toán bất đẳng thức biến phân (1.1) là tồn tại một số R > 0 sao cho có một nghiệm xR ∈ CR của bài toán (1.6) thỏa mãn: kxR k < R. (1.7) Chứng minh. Rõ ràng nếu tồn tại một nghiệm x của bài toán (1.1) thì x là một nghiệm của bài toán (1.6), miễn là: kxR k < R, vì: x ∈ CR ⊂ C. Giả sử xR ∈ CR thỏa mãn kxR k < R cũng là một nghiệm của bài toán (1.1). Thật vậy, vì |xR | < R, cho y ∈ C , w = xR + ε (y − xR ) ∈ CR với ε ≥ 0 đủ nhỏ. Vì vậy xR ∈ CR ⊂ C : 0 ≤ hF (xR ) , w − xR i = ε hF (xR ) , y − xR i , ∀y ∈ C. Điều này có nghĩa là xC là một nghiệm của bài toán (1.1) 16  Chương 1. Kiến thức chuẩn bị Mệnh đề 1.5. Cho C là tập con lồi, đóng, khác rỗng của Rn , F : C → Rn là một ánh xạ liên tục. Khi đó: (i) Nếu F là đơn điệu ngặt trên C thì bài toán bất đẳng thức biến phân (1.1) có nhiều nhất một nghiệm. (ii) Nếu F là đơn điệu mạnh trên C thì bài toán bất đẳng thức biến phân (1.1) có nghiệm duy nhất. 17 18 Chương 2 Mô hình Nash - Cournot với cước phí lõm 2.1 Mô hình Nash - Cournot cổ điển 2.1.1 Khái niệm mô hình Trong mô hình cân bằng thị trường, giả sử có n công ty đang cùng sản xuất một mặt hàng đồng nhất. Kí hiệu, xi ∈ Ui ⊆ R+ là mức sản lượng sản phẩm của công ty thứ i(i = 1, 2, ..., n) dự định sẽ thực hiện. Ta giả sử rằng pi là giá của một đơn vị sản phẩm do công ty thứ i sản xuất, nó phụ n P thuộc vào tổng sản lượng hàng hóa của cả công ty. Kí hiệu là: σ := xi , i=1 nghĩa là ta có pi := pi (σ). Đặt hi (xi ) là hàm chi phí của công ty thứ i khi mức sản lượng của công ty đạt được là xi . Giả sử lợi nhuận của công ty i đạt được cho bởi hàm: ! n X fi (x1 , ..., xn ) = xi pi xi − hi (xi ) , (i = 1, ..., n). (2.1) i=1 trong đó hi là hàm chi phí của công ty thứ i được giả định là chỉ phụ thuộc vào sản phẩm lượng hàng sản xuất của nó. Mỗi công ty tìm cách tối đa hóa lợi nhuận của riêng công ty mình bằng cách chọn sản phẩm lượng hàng sản xuất cho riêng mình. Gọi Ui ⊂ R (i = 1, ..., n) là tập các chiến lược sản xuất của công ty i. Đặt U := U1 × ... × Un là tập chiến lược của tất cả các công ty. Từ đó, ta có định nghĩa sau: Định nghĩa 2.1. Một điểm x∗ = (x∗1 , ..., x∗n ) ∈ U được gọi là một điểm cân bằng Nash của mô hình Nash – Cournot nếu với mọi i = 1, 2, ..., n và với mọi yi ∈ Ui ta đều có: fi (x∗1 , ..., x∗i−1 , yi , x∗i+1 , ..., x∗n ) ≤ fi (x∗1 , ..., x∗n ) , (∀i = 1, ...., n), (2.2)