ĐẠ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 2
1 Kiến thức chuẩn bị
4 4 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 8 . . . . . . . . . . . . . . . . . . . . . . 1.3 Toán tử đơn điệu . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . 14
2 Mô hình Nash - Cournot với cước phí lõm
18 2.1 Mô hình Nash - Cournot cổ điển . . . . . . . . . . . . . . . 18 2.1.1 Khái niệm mô hình . . . . . . . . . . . . . . . . . . 18 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 . . . . . . . . . . . . . . . . . . . . 22 2.2 Mô hình cân bằng Nash - Cournot với cước phí lõm . . . . . 27 2.2.1 Mô hình cân bằng Nash - Cournot với cước phí lõm . 27 . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.2 Thuật giải
Kết luận 38
Tài liệu tham khảo 39
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ả
3
Nguyễn Thị Mai
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].
n (cid:88)
(cid:104)x, y(cid:105) :=
xiyi,
i=1
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,
đượ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:
(cid:107)x(cid:107) :=
(cid:104)x, y(cid:105),
d (x, y) := (cid:107)x − y(cid:107) .
1.1 Tập lồi, hàm lồi, hàm lõm
(cid:113)
λx + (1 − λ) y ∈ C.
Đị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ó:
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à:
f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) .
(i) Lồi trên C nếu với mọi λ ∈ (0, 1), mọi x, y ∈ C ta có:
Chương 1. Kiến thức chuẩn bị
f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) .
(ii) Lồi chặt trên C nếu mọi λ ∈ (0, 1), mọi x, y ∈ C, mọi x (cid:54)= y ta có:
η > 0 ta có:
f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) −
λ (1 − λ) η(cid:107)x − y(cid:107)2.
1 2
(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,
domf = {x ∈ S : f (x) < +∞} ,
(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
epif = {(x, α) ∈ S × R : f (x) ≤ α} .
và
đượ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 (cid:54)= φ; 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 (cid:54)= φ. Đị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.
f ((1 − λ) x + λy) = f (x + λd) = ϕ (λ) = ϕ ((1 − λ) .0 + λ.1)
≤ (1 − λ) ϕ (0) + λϕ (1) = (1 − λ) f (x) + λf (y) .
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ó:
(cid:3)
Định nghĩa 1.4. Một hàm a-phin là hàm số có dạng f (x) = (cid:104)c, x(cid:105) + α trong đó c ∈ Rn, α ∈ R cho trước tùy ý.
λ + β = 1 ta có:
f (λx + βy) = λf (x) + βf (y).
Nếu f (x) là hàm a-phin thì với mỗi x, y ∈ Rn và mọi số λ, β sao cho
Một hàm a-phin f (x) = (cid:104)c, x(cid:105) + α không lấy giá trị âm thì phải đồng
f (λx) = (cid:104)c, x(cid:105) + α → −∞,
nhất với một hằng số (véctơ c phải bằng 0), vì nếu c (cid:54)= 0 thì ta sẽ có:
5
khi λ → −∞.
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 .
λx ∈ M . Chứng minh.
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à
Nếu M là một nón lồi thì thì λM ⊂ M, ∀λ > 0 theo định nghĩa của 2 (x + y) ∈ M , do đó theo nón. Hơn nữa, lấy x, y ∈ M thì do M lồi nên 1 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ừ đó, (cid:3) (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.
≤
λkxk
λk = 1, λk ≥ 0 với mọi
m (cid:80) k=1
k, trong đó m là số nguyên ≥ 2 ( Bất đẳng thức Jensen).
(cid:19) +) f * 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 λkf (cid:0)xk(cid:1), ∀xk ∈ S, (cid:80) k=1 (cid:18) m (cid:80) k=1
* 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 giản ta thường xét hàm lồi trên toàn Rn.
Đị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.
riC := {a ∈ C|∃B : (a + B) ∩ affC ⊂ C} .
6
Đị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ó:
Chương 1. Kiến thức chuẩn bị
riC = {a ∈ affC|∃B : (a + B) ∩ affC ⊂ C} .
trong đó B là một lân cận mở của gốc. Hiển nhiên
yk, trong đó xk, yk ∈ C với mọi k. Với
xk, b = lim k→∞
Đị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 k→∞ mọi λ ∈ [0, 1] ta có: (1 − λ) xk + λyk ∈ C. Từ đó:
(1 − λ) a + λb = lim k→∞
(cid:8)(1 − λ) xk + λyk(cid:9) ∈ C.
(x + B) ∩ af f C = (1 − λ) (a + B) ∩ af f C + λ (b + B) ∩ af f C ⊂ C.
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ó:
(cid:3) Như vậy x ∈ riC, nghĩa là riC lồi.
Tính chất 1.1.
C + D = {x + y : x ∈ C, y ∈ D} , αC = {αx : x ∈ C, α ∈ R} , C − D = C + (−1) D.
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) 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.
λx + (1 − λ) y với 0 < λ < 1 đều là điểm trong của C.
Tập C ∈ Rn được gọi là lồi chặt nếu với mọi x, y ∈ C, x (cid:54)= y, mọi điểm
Mệnh đề 1.1.
A ∩ B (cid:54)= φ. Khi đó, hàm (λf ) + (βg) lồi trên, với mọi λ, β ≥ 0;
(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
7
(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
Chương 1. Kiến thức chuẩn bị
fi (x) cũng lồi trên C;
thì hàm f (x) := lim 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
1.2 Cực trị của hàm lồi
trên khoảng I, sao cho f (C) ⊆ I,thì hàm hợp ϕ0f lồi trên C.
f (x∗) ≤ f (x) ∀x ∈ U ∩ C;
Đị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 ∈ 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.
Nếu
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
f (x∗) ≤ f (x) ∀x ∈ U ∩ C.
đó tồn tại lân cận U của x∗ sao cho:
f (x∗) ≤ f (xλ) ≤ (1 − λ) f (x∗) + λf (x) .
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) .
8
Từ đây suy ra:
Chương 1. Kiến thức chuẩn bị
f (z∗) ≤ (1 − λ) f (y∗) + λf (x∗) ≤ f (x) .
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:
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 (cid:3) đ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).
b =
x +
a.
1 λ
λ − 1 λ Với mọi λ > 0, theo tính lồi của f ta có:
f (b) ≤
f (x) +
f (a) .
λ − 1 λ
1 λ
(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 đó:
f (b) − f (a) ≤
f (x) −
f (a) ≤
[m − f (a)] .
1 λ
1 λ
1 λ
Từ đây và do giả thiết f (x) ≤ m < ∞ với mọi x ∈ M , ta suy ra
9
Đ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
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.
(cid:3)
(cid:104)x∗, z − x(cid:105) + f (x) ≤ f (z)∀z.
Đị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:
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) (cid:54)= φ 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
dom (∂f ) := {x|∂f (x) (cid:54)= φ} .
tử đa trị, ta sẽ kí hiệu:
Mệnh đề 1.4. Cho f : Rn → R ∪ {+∞} lồi, chính thường.
(i) x∗ ∈ ∂f (x) khi và chỉ khi f (cid:48) (x, y) ≥ (cid:104)x∗, y(cid:105) , ∀y. Nếu x ∈ ri (domf )
(cid:104)x∗, y(cid:105) , ∀y;
x∗∈∂f (x)
thì f (cid:48) (x, y) = sup
(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.
x∗ ∈ ∂f (x) ⇔ (cid:104)x∗, z − x(cid:105) + f (x) ≤ f (z) , ∀z,
(i) Theo định nghĩa
(cid:104)x∗, λy(cid:105) + f (x) ≤ f (x + λy) ,
Với bất kỳ y ta lấy, z = x + λy, λ > 0, ta có:
(cid:104)x∗, y(cid:105) ≤
, ∀λ > 0,
f (x + λy) − f (x) λ
từ đây suy ra:
10
Theo định nghĩa dưới vi phân của f (cid:48)(x, y), từ đây suy ra ngay:
Chương 1. Kiến thức chuẩn bị
(cid:104)x∗, y(cid:105) ≤ f (cid:48) (x, y) , ∀y;
f (x + y) − f (x) ≥ f (cid:48) (x, y) = f (cid:48)(x, z − x) ≥ (cid:104)x∗, z − x(cid:105) , ∀z,
Ngược lại (cid:104)x∗, y(cid:105) ≤ f (cid:48) (x, y) ∀y thỏa mãn. Lấy z bất kỳ và áp dụng (cid:104)x∗, y(cid:105) ≤ f (cid:48) (x, y) ∀y với y = z − x và λ = 1. Ta có:
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
f (x) ≥ f (x) = f ∗∗ (x) ≥ (cid:104)x∗, x(cid:105) − f ∗ (x∗) = f (x) ,
liên hợp và do x∗ ∈ ∂f (x) ta có:
f (z) ≥ f (z) ≥ f (x) + (cid:104)y∗, z − x(cid:105) = f (x) + (cid:104)y∗, z − x(cid:105) .
Từ đây suy ra: f (x) = f (x). Nếu y∗ ∈ ∂f (x), thì với mọi z có:
f (cid:2)(1 − t) z + tz0(cid:3) .
f (z) = lim t↓0
Suy ra ∂f (x) ⊆ ∂f (x) . Để chứng minh điều ngược lại, lấy z0 ∈ ri (domf). Với mọi z ta có:
f (cid:2)(1 − t) z + tz0(cid:3) ≥ f (x) + (cid:10)x∗, (1 − t) z + tz0 − x(cid:11) ,
Vậy theo định nghĩ dưới vi phân ta có:
f (x) ≥ f (x) + (cid:104)x∗, z − x(cid:105) = f (x) + (cid:104)x∗, z − x(cid:105) .
Cho t (cid:38) 0 ta được:
Chứng tỏ x∗ ∈ ∂f (x).
1.3 Toán tử đơn điệu
(cid:3)
Đị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à:
(cid:104)Q (u) − Q (v) , u − v(cid:105) ≥ 0.
11
(i) Đơn điệu trên C nếu mỗi cặp điểm u, v ∈ C ta có:
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
(cid:104)Q (u) − Q (v) , u − v(cid:105) ≥ η||u − v||2.
có:
(cid:104)Q (u) − Q (v) , u − v(cid:105) > 0.
(iii) Đơn điệu ngặt trên C nếu với mọi u, v ∈ C và mọi u (cid:54)= v ta có:
(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 (cid:104)Q (v) , u − v(cid:105) ≥ 0 thì (cid:104)Q (u) , u − v(cid:105) ≥ 0.
grF = {(x, y) ∈ X × Y : y = F (x)} ;
domF = {x ∈ X : ∃y : F (x) = y} ;
rge = {y ∈ Y : ∃x ∈ X : y = F (x)} .
Đị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:
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.
(cid:104)x − y|u(cid:105) + f (y) ≥ f (x) ,
Lấy (x, u) và (y, v) ∈ gra∇f . Ta có:
(cid:104)y − x|v(cid:105) + f (x) ≥ f (y) ,
và
(cid:104)x − y|u − v(cid:105) ≥ 0.
Cộng theo vế hai bất đẳng thức trên ta được:
(cid:3)
(cid:104)Az, z(cid:105) ≥ 0, ∀z ∈ Rn.
12
Đị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:
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
(cid:104)A (x) − A (y) , x − y(cid:105) ≥ 0, ∀x, y ∈ Rn,
là toán tử đơn điệu khi và chỉ khi:
(cid:104)A (x − y) , x − y(cid:105) ≥ 0, ∀x, y ∈ Rn,
hay
(cid:104)A (z) , z(cid:105) ≥ 0, ∀z ∈ Rn.
Đặt z = x − y ta có:
(cid:3) 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ì λ1T1 + λ2T2 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ì λ1T1 + λ2T2 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.
dom (λ1T1 + λ2T2) = {z ∈ Rn : λ1T1 (z) + λ2T2 (z) (cid:54)= 0}
= domT1 ∩ domT2.
(i) Hiển nhiên ta có:
u ∈ (λ1T1 + λ2T2) (x) = λ1T1 (x) + λ2T2 (x) ,
v ∈ (λ1T1 + λ2T2) (y) = λ1T1 (y) + λ2T2 (y) .
Giả sử: x, y ∈ domT1 ∩ domT2 và
u = λ1u1 + λ2u2;
v = λ1v1 + λ2v2.
Lấy ui ∈ Ti (x) , vi ∈ Ti (y) , i = 1, 2 sao cho:
(cid:104)u1 − v1, x − y(cid:105) ≥ 0,
13
do T1, T2 là toán tử đơn điệu nên ta có:
Chương 1. Kiến thức chuẩn bị
(cid:104)u2 − v2, x − y(cid:105) ≥ 0.
(cid:104)u − v, x − y(cid:105) ≥ 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:
Điều này chứng tỏ λ1T1 + λ2T2 là toán tử đơn điệu.
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ó:
(cid:104)v − u, y − x(cid:105) = (cid:104)A∗v1 − A∗u1, y − x(cid:105)
= (cid:104)v1 − u1, (Ay + b) − (Ax + b)(cid:105) ≥ 0.
(ii) Lấy x, y ∈ domT , u ∈ S(x) = A∗T (Ax + b),
(cid:104)v1 − u1, (Ay + b) − (Ax + b)(cid:105) > 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 (cid:54)= y thì Ax (cid:54)= Ay kéo theo Ax + b (cid:54)= 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
(cid:104)v − u, y − x(cid:105) > 0.
Suy ra:
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
(cid:3)
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:
(cid:104)F (x∗) , x − x∗(cid:105) ≥ 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.
14
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
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:
(cid:104)F (x∗) , x − x∗(cid:105) + ϕ (x) − ϕ (x∗) ≥ 0, ∀x ∈ C.
(1.2)
trong đó, (cid:104)., .(cid:105) 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:
(cid:104)F (x∗) + ∇ϕ (x∗) , x − x∗(cid:105) ≥ 0, ∀x ∈ C.
(1.3)
Với bài toán (1.2) ta xét hàm đánh giá sau:
g(x) := − min
(cid:104)F (x), y − x(cid:105) +
(cid:104)y − x, G(y − x)(cid:105) + ϕ(y) − ϕ(x), y ∈ C
,
1 2
(cid:26) (cid:27)
(1.4)
(cid:104)y − x, G(y − x)(cid:105) , y ∈ C
.
(cid:104)F (x) + ∇ϕ(x), y − x(cid:105) +
g1 (x) = − min
1 2
(cid:27) 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á: (cid:26)
(1.5)
(cid:104)F (x∗) , x − x∗(cid:105) ≥ 0, ∀x ∈ C.
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:
Φ (x) := PC (x − F (x)) .
Chứng minh. Xây dựng ánh xạ Φ bằng cách với mỗi x ∈ C đặt:
Φ : C → C,
15
Ta có:
Chương 1. Kiến thức chuẩn bị
x∗ = Φ (x∗) .
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∗) := PC (x∗ − F (x∗)) .
Theo định nghĩa của Φ, thì:
(cid:104)F (x∗) , x − x∗(cid:105) ≥ 0, ∀x ∈ C.
Theo tính chất của hình chiếu, ta có:
(cid:3) Vậy bài toán bất đẳng thức biến phân (1.1) có nghiệm.
R trong đó (cid:80)
R là hình cầu đóng
Cho tập lồi C (cid:54)= φ, đặt CR = C ∩ (cid:80)
bán kính R tâm O ∈ Rn. Khi đó CR là tập compact. Từ đó ta có:
xR ∈ CR : (cid:104)F (xR) , y − xR(cid:105) ≥ 0, ∀y ∈ CR.
(1.6)
F : C → Rn,
Định lý 1.7. Cho C ∈ Rn là tập lồi, đóng và ánh xạ:
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:
(cid:107)xR(cid:107) < R.
(1.7)
(cid:107)xR(cid:107) < R,
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à:
x ∈ CR ⊂ C. Giả sử xR ∈ CR thỏa mãn (cid:107)xR(cid:107) < 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 ≤ (cid:104)F (xR) , w − xR(cid:105) = ε (cid:104)F (xR) , y − xR(cid:105) , ∀y ∈ C.
vì:
16
(cid:3) Điều này có nghĩa là xC là một nghiệm của bài toán (1.1)
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
17
(1.1) có nghiệm duy nhất.
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
n (cid:80) i=1
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ụ xi, thuộc vào tổng sản lượng hàng hóa của cả công ty. Kí hiệu là: σ :=
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:
fi (x1, ..., xn) = xipi
xi
− hi (xi) , (i = 1, ..., n).
i=1
(cid:32) n (cid:33) (cid:88) (2.1)
1, ..., x∗
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∗ 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∗
n) , (∀i = 1, ...., n),
1, ..., x∗
n) ≤ fi (x∗
i+1, ..., x∗
i−1, yi, x∗
1, ..., x∗
(2.2)
Chương 2. Mô hình Nash - Cournot với cước phí lõm
fi (x∗
1, ..., x∗
i−1, yi, x∗
i+1, ..., x∗
n) = fi (x∗ [yi]) , (∀i = 1, ...., n),
Đặt
Khi đó (2.2) sẽ tương đương với:
fi (x∗ [yi]) ≤ fi (x∗
1, ..., x∗
n) , (∀i = 1, ...., n), yi ∈ Ci.
(2.3)
n (cid:88)
ψ(x, y) := −
fi (x1, ..., xi−1, yi, xi+1, ..., xn) = −
fi (x [yi]),
i=1
i=1
Từ đây ta thấy rằng tại điểm cân bằng lợi nhuận của các công ty là cao nhất. Vì vậy nếu có một công ty rời khỏi vị trí cân bằng mà các công ty vẫn giữ nguyên ở vị trí đó thì lợi nhuận của công ty đó sẽ bị giảm đi chứ không tăng lên. Do đó, mà các công ty đều muốn ở vị trí cân bằng của mình. Với mỗi x = (x1, ..., xn) và y = (y1, ..., yn) ta đặt: n (cid:88) (2.4)
và
Φ (x, y) := ψ(x, y) − ψ (x, x) .
(2.5)
Khi đó, bài toán tìm điểm cân bằng của mô hình cân bằng Nash – Cournot tương đương với bài toán sau: Tìm x∗ ∈ U sao cho:
Φ (x∗, y) ≥ 0, ∀y ∈ U.
(2.6)
Mệnh đề 2.1. Điểm x∗ ∈ U là điểm cân bằng của mô hình Nash - Cournot và chỉ khi x∗ là nghiệm của bài toán cân bằng (2.6).
fi (x∗ [yi]) ≤ fi (x∗) , (∀i = 1, ...., n),∀yi ∈ Ui,
Chứng minh. Giả sử x∗ ∈ U là điểm cân bằng của mô hình. Khi đó,
fi (x∗ [yi]) ≤
fi (x∗), (∀i = 1, ...., n), ∀yi ∈ Ui,
n (cid:80) i=1
n (cid:80) i=1
suy ra:
−
fi (x∗ [yi]) ≥ −
fi (x∗), (∀i = 1, ...., n), ∀yi ∈ Ui,
n (cid:80) i=1
n (cid:80) i=1
hay
ψ (x∗, y) ≥ ψ (x∗, x∗) , ∀y ∈ U,
19
Tức là ta có:
Chương 2. Mô hình Nash - Cournot với cước phí lõm
Φ (x∗, y) := ψ(x∗, y) − ψ (x∗, x∗) ≥ 0, ∀y ∈ U.
Khi đó:
Φ (x∗, y) ≥ 0, ∀y ∈ U,
Vậy x∗ là nghiệm của bài toán cân bằng. Ngược lại, x∗ là nghiệm của bài toán cân bằng nên nó thỏa mãn:
Φ (x∗, y) := ψ(x∗, y) − ψ (x∗, x∗) ≥ 0, ∀y ∈ U,
nên:
ψ(x∗, y) ≥ ψ (x∗, x∗) , ∀y ∈ U,
suy ra:
−
fi (x∗ [yi]) ≥ −
fi (x∗), (∀i = 1, ...., n), ∀yi ∈ Ui,
n (cid:80) i=1
n (cid:80) i=1
Vậy
fi (x∗ [yi]) ≤
fi (x∗), (∀i = 1, ...., n),∀yi ∈ Ui,
n (cid:80) i=1
n (cid:80) i=1
Điều này có nghĩa rằng:
fi (x∗ [yi]) ≤ fi (x∗) , (∀i = 1, ...., n), ∀yi ∈ Ui.
Do đó:
20
(cid:3) Vậy x∗ ∈ U là điểm cân bằng của mô hình.
Chương 2. Mô hình Nash - Cournot với cước phí lõm
Hình 2.1: Mô hình cân bằng Nash - Cournot với cước phí tuyến tính
Nhận xét 2.1.
- Hiển nhiên x ∈ D là nghiệm tối ưu toàn cục của bài toán (P ) thì x là
nghiệm tối ưu địa phương của bài toán (P ).
- Nếu D là một tập lồi và f là một hàm lồi trên D thì bài toán (P )
được gọi là một bài toán quy hoạch lồi.
xT Qx,
f (x) = qT x +
1 2
- Nếu D = Rn thì bài toán (P ) được gọi là bài toán tối ưu không ràng buộc. Một trường hợp riêng quan trọng của bài toán tối ưu (P ) là bài toán quy hoạch toàn phương lồi mạnh với ràng buộc tuyến tính, tức là:
min {f (x) : x ∈ D} ,
trong đó q ∈ Rn và Q là ma trận đối xứng xác định dương. Ta cần mệnh đề sau đây: Xét bài toán quy hoạch lồi:
(cid:107)x(cid:107)2,
g (x) := f (x) −
α 2
trong đó f là hàm lồi mạnh trên D và D là một tập lồi đóng. Khi đó, bài toán này có duy nhất nghiệm. Chứng minh. Giả sử α > 0 là hệ số lồi mạnh của hàm f , tức là hàm:
21
là hàm lồi.
Chương 2. Mô hình Nash - Cournot với cước phí lõm
(cid:107)x(cid:107)2,
f (x) = g (x) +
α 2
Dễ thấy rằng hàm:
min {f (x) : x ∈ D} ,
thỏa mãn điều kiện bức trên D, nghĩa là: f (x) → ∞ khi x ∈ D, (cid:107)x(cid:107) → +∞ (Xem bổ đề 11.2 trong [2].) Vì vậy bài toán:
x∗ = y∗.
luôn tồn tại. Để chứng minh tính duy nhất ta giả sử bài toán min {f (x) : x ∈ D} có hai nghiệm là x∗ và y∗. Khi đó, do tính lồi mạnh của f ta suy ra:
(cid:3)
Phần tiếp theo chúng ta sẽ trình bày cách chuyển bài toán (2.6) về bài
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
toán tối ưu một hàm toàn phương.
n (cid:88)
Trong mô hình cân bằng kinh tế thị trường Nash – Cournot cổ điển hàm giá và hàm chi phí của mỗi công ty giả sử là hàm a-phin, có dạng sau:
pi(σ) ≡ p (σ) = α0 − β.σ, α0 > 0, β > 0, σ =
xi,
i=1
(2.7)
hi(xi) ≡ µixi + ξi, µi > 0, ξi > 0(i = 1, ...n).
22
(2.8)
Chương 2. Mô hình Nash - Cournot với cước phí lõm
n (cid:88)
n (cid:88)
Φ (x, y) := ψ(x, y) − ψ (x, x) =
fi (x) −
fi (x [yi])
i=1
i=1
Như vậy, hàm giá là chung cho mọi công ty. Từ (2.4), và (2.5) ta có:
n (cid:88)
n (cid:88)
=
xipi
xi
(xj [yi])
− hi (xi) − yipi
i=1
i=1
(cid:32) n (cid:33) (cid:88) + hi (yi)
j(cid:54)=i,j=1 (cid:32)
xi
− (µixi + ξi) − yi
xi
α0 − β
α0 − β
(xj [yi])
n (cid:80) i=1
n (cid:80) i=1
n (cid:80) j(cid:54)=i,j=1
=
+µiyi + ξi}
(cid:40) (cid:33) (cid:19) (cid:18)
n (cid:88)
n (cid:88)
n (cid:88)
=
(xi − yi) α0 − β
(xj) + βy2 i
x2 i + µi (yi − xi) − βyi
i=1
i=1
j(cid:54)=i,j=1
n (cid:88)
n (cid:88)
=
(yi − xi)
xj − α0 + µi
i − βx2 i
i=1
j(cid:54)=i,j=1
β + βy2
n (cid:88)
n (cid:88)
n (cid:88)
n (cid:88)
+ β
=
xj − α0 + µi
(yi − xi)
y2 i − β
x2 i
i=1
i=1
i=1 (cid:68)
j(cid:54)=i,j=1 (cid:69)
=
+ yT By − xT Bx.
β
(cid:101)Bx + µ − α, y − x
trong đó:
B :=
; (cid:101)B :=
...
...
β 0 0 ... 0 0 β 0 ... 0 ... ... ... ... 0 ... β 0
... 0
0 β β ... β β 0 β ... β ... ... ... β β β ... 0
αT = (α0, α0, ...., α0) , µT = (µ1, µ2, ..., µn) .
và
Do đó, bài toán tìm điểm cân bằng trong của mô hình cân bằng Nash – Cournot có thể được viết lại thành bài toán bất đẳng thức biến phân hỗn hợp sau: Tìm x ∈ U sao cho:
+ yT By − xT Bx ≥ 0, ∀y ∈ U ;
23
(cid:68) (cid:69) (2.9) (cid:101)Bx + µ − α, y − x
Chương 2. Mô hình Nash - Cournot với cước phí lõm
Q :=
,
...
cho :
2β β β ... β β 2β β ... β ... ... ... ... β β ... 2β β
xT Qx + (µ − α)T x
;
min x∈U
Do β > 0, ma trận B và (cid:101)B là đối xứng và Q = 2B + (cid:101)B là ma trận đối xứng xác định dương, nên bài toán bất đẳng thức biến phân (2.9) tương đương với bài toán quy hoạch lồi toàn phương sau: (cid:27) (2.10) (cid:26)1 2
β
xi +
+ µi − αi + λ2i−1 − λ2i = 0,
xj
n (cid:80) j=1
λ2i−1 (xi − ai) = 0,
Áp dụng định lý Kuhn – Tucker cho quy hoạch tuyến tính (2.10), x là nghiệm tối ưu khi và chỉ khi tồn tại các số thực không âm λ2i, λ2i−1, i = (1, 2, ..., n) thỏa mãn hệ: (cid:33) (cid:32)
(2.11)
λ2i (−xi + bi) = 0, ai ≤ xi ≤ bi, λ2i−1 ≥ 0, λ2i ≥ 0(i = 1, 2, ..., n).
Do β > 0, với i = (1, 2, ..., n) hệ (2.11) được viết lại là:
+ 1
xj
xi +
β (µi − αi) + 1
β λ2i−1 − 1
β λ2i = 0,
(cid:32) (cid:33)
(2.12)
n (cid:80) j=1 1 β λ2i−1 (xi − ai) = 0, 1 β λ2i (−xi + bi) = 0, ai ≤ xi ≤ bi, β λ2i−1 ≥ 0, 1 1
β λ2i ≥ 0 (i = 1, 2, ..., n) .
qi =
(µi − αi) ; v2i−1 =
λ2i−1; v2i =
λ2i, ∀i = 1, 2, ..., n.
1 β
1 β
1 β
Đặt:
+ qi + v2i−1 − v2i = 0,
xi +
xj
n (cid:80) j=1
v2i−1 (xi − ai) = 0,
Khi đó hệ (2.12) được viết lại là: (cid:33) (cid:32)
(2.13)
v2i (−xi + bi) = 0, ai ≤ xi ≤ bi, v2i−1 ≥ 0, v2i ≥ 0(i = 1, 2, ..., n).
24
Chương 2. Mô hình Nash - Cournot với cước phí lõm
Theo định lý Kuhn – Tucker, hệ (2.13) chính là điều kiện cần và đủ để x là nghiệm tối ưu của quy hoạch toàn phương lồi mạnh:
xT Bx + qT x
;
min x∈U
(cid:27) (2.14) (cid:26)1 2
trong đó:
B :=
; qT = (q1, q2, ..., qn) .
2 1 ... 1
1 2 ... 1
1 ... 1 1 ... 1 ... ... ... 1 ... 2
Bài toán có duy nhất một nghiệm tối ưu và nó cũng là điểm cân bằng duy nhất của mô hình cân bằng thị trường kinh tế Nash – Cournot cổ điển. Hiển nhiên nghiệm tối ưu của bài toán quy hoạch lồi toàn phương cũng là nghiệm tối ưu của bài toán sau:
xT Qx
;
αT x − µT x −
max x∈U
1 2
(cid:27) (cid:26) (2.15)
Điều này có nghĩa là điểm cân bằng Nash là điểm có tổng lợi ích của các công ty là lớn nhất với ma trận hệ số giá:
,
Q :=
...
2β β β ... β β 2β β ... β ... ... ... ... β β ... 2β β
n (cid:88)
f (x) :=
fi (x) = αT x − µT x − xT Gx;
i=1
Theo (2.1) và (2.6) tổng lợi ích của các công ty là:
Ta có thể giải bài toán quy hoạch toàn phương lồi mạnh:
max x∈U
(2.16) (cid:8)αT x − µT x − xT Gx(cid:9) ;
theo các phương pháp đã có của quy hoạch toán học. Trong đó:
G =
,
...
...
β β β ... β β β β ... β ... ... ... β β β ... β
25
được gọi là ma trận hệ số giá.
Chương 2. Mô hình Nash - Cournot với cước phí lõm
Ví dụ 2.1.
h1 (x1) = 2x1 + 1,
Có hai công ty. Gọi U1 = [0, 10] là tập chiến lược của công ty thứ nhất, U2 = [0, 5] là tập chiến lược của công ty thứ hai. Giả sử: Hàm chi phí của công ty thứ nhất khi sản xuất x1 đơn vị hàng hóa là:
h2 (x2) = 5x2 + 2,
Hàm chi phí của công ty thứ hai khi sản xuất x2 đơn vị hàng hóa là:
f1 (x1, x2) = x1p (x1 + x2) − h1 (x1) ,
f2 (x1, x2) = x2p (x1 + x2) − h2 (x2) ,
Hàm giá của cả hai công ty là chung: p (σ) = 10 − 0.5 (x1 + x2). Vậy hàm lợi nhuận của các công ty lần lượt là:
Q =
Để chuyển về bài toán toàn phương (2.10) ta có: (cid:19)
0.5 1
; µ = (µ1, µ2) = (2, 5); α = (α1, α2) = (10, 10). (cid:18) 1 0.5
⇒ qT = (−8, −5) ,
q =
Từ đây suy ra: (cid:19)
(cid:18) −8 −5
Do đó ta có:
+ (−8, −5)
(x1, x2)
(cid:19) (cid:19)
0.5 1
1 2
=
x1x2 − 8x1 − 5x2.
x2 1 +
x2 2 +
1 2
1 2
1 2
(cid:18) 1 0.5 (cid:19) (cid:18) x1 x2 (cid:18) x1 x2
Suy ra, bài toán toàn phương lồi mạnh là:
,
x1x2 − 8x1 − 5x2
x2 1 +
x2 2 +
(cid:27)
1 2
1 2
min x1∈U1 x2∈U2
(cid:26)1 2
Sử dụng công cụ tính toán MALAB với hàm quadprog trong gói opti-
moization toolbox ta giải được nghiệm của bài toán là:
(cid:26) x1 = 7.3 x2 = 1.3
f1 (x1, x2) = 26.01
f2 (x1, x2) = −1.09
26
Từ đây suy ra hàm giá của cả hai công ty là: p (δ) = 5.7 và giá trị hàm lợi nhuận của các công ty lần lượt là :
Chương 2. Mô hình Nash - Cournot với cước phí lõm
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
Trong chương này, chúng ta sẽ giới thiệu hai cách tiếp cận cho mô hình cân bằng Nash - Cournot. Cách tiếp cận thứ nhất là tiếp cận thông qua bài toán quy hoạch toàn phương lồi mạnh cho mô hình cổ điển, tức là mô hình với cước phí tuyến tính. Đối với mô hình với cước phí lõm chúng ta sẽ giới thiệu việc chuyển mô hình về bài toán bất đẳng thức biến phân hỗn hợp DC và trình bày một thuật toán tìm điểm cân bằng cho loại mô hình này. Những kiến thức trong chương này được lấy từ các tài liệu [5], [6].
pi (σ) := p
xj
= αi − βj
xj, αi ≥ 0, βj ≥ 0, (i = 1, ..., n) .
Trong mô hình cân bằng kinh tế Nash - Cournot cổ điển, hàm chi phí đã được giả thiết là hàm tăng, a-phin theo số lượng sản xuất. Tuy nhiên trong thực tế, chi phí để sản xuất một đơn vị hàng hóa thường là giảm khi số lượng hàng hóa sản xuất tăng. Hơn nữa, giá sản xuất của mỗi công ty là không giống nhau. Do đó trong phần này chúng ta sẽ xét mô hình cân bằng Nash - Cournot với chi phí sản xuất là hàm lõm và giá thành sản xuất của mỗi công ty là khác nhau. Cụ thể ta cho hàm giá pi (σ) được xác định như sau: (cid:33)
n (cid:80) j=1
(cid:32) n (cid:80) j=1
27
và hàm chi phí của hãng thứ i là hi (xi) là một hàm lõm. Khi đó ta có:
Chương 2. Mô hình Nash - Cournot với cước phí lõm
n (cid:88)
n (cid:88)
Φ (x, y) := ψ(x, y) − ψ (x, x) =
fi (x) −
fi (x [yi])
i=1
i=1
n (cid:88)
n (cid:88)
=
xipi
xi
(xj [yi])
− hi (xi) − yipi
i=1
i=1
(cid:32) n (cid:33) (cid:88) + h (y)
j(cid:54)=i,j=1 (cid:32)
xi
αi − βi
xi
− h (x) − yi
αi − βi
(xj [yi])
n (cid:80) i=1
n (cid:80) i=1
n (cid:80) j(cid:54)=i,j=1
=
+h (y)} (cid:32)
(cid:40) (cid:33) (cid:18) (cid:19)
(yi − xi)
βi
xj − αi
+ βi
y2 i − βi
x2 i
n (cid:80) i=1
n (cid:80) i=1
n (cid:80) i=1
n (cid:80) j(cid:54)=i,j=1
=
+h (y) − h (x) (cid:68)
(cid:32) (cid:33)(cid:33)
=
+ yT By − xT Bx + h (y) − h (x) ,
(cid:69) (cid:101)Bx − α, y − x
trong đó:
B =
,
; (cid:101)B =
... 0
β1 0 0 ... 0 0 β2 0 ... 0 ... ... ... ... 0 ... βn 0
... β1 0 β1 β1 ... β2 0 β2 β2 ... ... ... ... ... βn βn βn ... 0
n (cid:88)
h (x) :=
hi (xi),
i=1 với hi (i = 1, 2, ..., n) là hàm lõm. Rõ ràng B là ma trận đối xứng xác định dương. Cho
và
F (x) := (cid:101)Bx − α,
(2.17)
ϕ (x) := xT Bx + h (x) .
(2.18)
Vậy bài toán cân bằng trở thành bài toán bất đẳng thức biến phân hỗn hợp sau: Tìm x∗ ∈ C sao cho:
Φ (x∗, y) := (cid:104)F (x∗) , y − x∗(cid:105) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ C.
(2.19)
28
trong đó, F (.) là toán tử a-phin và ϕ (.) là hàm D.C được cho theo công thức (2.17) và (2.18). Chú ý rằng vì ϕ không lồi nên (2.19) không tương
Chương 2. Mô hình Nash - Cournot với cước phí lõm
đương với bài toán: Tìm x∗ ∈ C sao cho:
Φ (x∗, y) := (cid:104)F (x∗) , y − x∗(cid:105) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ U ∩ C.
(2.20)
trong đó U là lân cận của x∗. Điểm x∗ ∈ C thỏa mãn (2.20) được gọi là nghiệm địa phương.
Uj và một bài toán thứ nguyên (n − 1) chiều được tính
Chú ý rằng khi βi = 0 với một công ty i nào đó, tức là giá sản phẩm của công ty i đồng nhất bằng hằng số αi. Trong trường hợp này thì chiến lược cân bằng của công ty i có thể được thực hiện bằng cách tối đa hóa lợi nhuận thông qua bổ đề sau.
Cho U −i := (cid:81) j(cid:54)=i
thông qua bài toán n chiều bằng cách xóa đi mục i. Cụ thể ta có định nghĩa như sau: Tìm x−i0 ∈ U −i0 sao cho:
(cid:10)F −i0(x−i0), y−i0 − x−i0(cid:11) + ϕ−i0(y−i0) − ϕ−i0(x−i0) ≥ 0, ∀y−i0 ∈ U −i0,
(2.21)
F −i0(x−i0) := (cid:101)B−i0x−i0 − α−i0
trong đó:
ϕ−i0(x−i0) :=
ϕi (xi)
n (cid:80) i(cid:54)=i0
với (cid:101)B−i0 là ma trận cấp (n − 1) × (n − 1) nhận được từ ma trận (cid:101)B bằng cách xóa đi hàng i0 và cột j0.
Định lý 2.1. (Định lý Kakutani về điểm bất động) Cho U là một tập lồi, compact trong Rn và H : U → 2U là ánh xạ nửa liên tục trên tại mọi điểm của U . Giả sử H(x) là một tập khác rỗng, lồi, compact với mọi x ∈ U . Khi đó, H có một điểm cố định.
Với mỗi x ∈ U , ta định nghĩa:
{Φ (x, y) := (cid:104)F (x) , y − x(cid:105) + ϕ (y) − ϕ (x)} ,
θ (x) := min y∈U
(2.22)
H (x) := arg min
{(cid:104)F (x) , y(cid:105) + ϕ (y)} .
y∈U
(2.23)
Trong đó, U là compact, ϕ là ánh xạ liên tục, θ hữu hạn, H (x) (cid:54)= φ với mọi x.
29
Mệnh đề 2.2. Cho U là tập lồi, đóng, khác rỗng trong Rn. Khi đó ta có:
Chương 2. Mô hình Nash - Cournot với cước phí lõm
(i) θ (x) ≤ 0, ∀x ∈ U ;
(ii) x∗ ∈ U là nghiệm của bài toán (2.19) khi và chỉ khi θ (x∗) = 0.
Chứng minh.
(i) Hiển nhiên Φ (x, x) = 0, ∀x ∈ U .
Từ đây kết hợp với (2.22) ta suy ra θ (x) ≤ 0, ∀x ∈ U.
x∗ ∈ U và:
(cid:104)F (x∗) , y − x∗(cid:105) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ U.
(ii) Giả sử x∗ ∈ U là nghiệm của bài toán (2.19) theo định nghĩa ta có
θ (x∗) = 0.
Điều này chứng tỏ rằng θ (x∗) ≥ 0. Kết hợp với (i) ta suy ra:
Φ (x∗, y) ≥ 0, ∀y ∈ U.
Ngược lại, giả sử θ (x∗) = 0. Điều này và từ (2.22) ta suy ra:
(cid:104)F (x∗) , y − x∗(cid:105) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ U.
Theo định nghĩa của hàm Φ ta suy ra:
Điều này chứng tỏ x∗ là nghiệm của bài toán (2.19).
(cid:3)
Mệnh đề 2.3. Giả sử rằng βi0 = 0. Đặt (cid:98)xi0 là một nghiệm tối ưu của bài toán:
min {hi0 (yi0) − αi0yi0|yi0 ∈ Ui0} , (2.24) và đặt (cid:98)x−i0 là một nghiệm của bài toán bất đẳng thức biến phân hỗn hợp (cid:0)P −i0(cid:1). Khi đó, (cid:98)x := (cid:0) (cid:1) là một nghiệm của bài toán (2.19). Ngược (cid:98)x−i0, (cid:98)xi0 lại, mọi nghiệm (cid:98)x của bài toán (2.19) đều có dạng (cid:98)x := (cid:0) (cid:1) với (cid:98)x−i0 và (cid:98)xi0 là nghiệm tương ứng của bài toán (2.24) và (2.21). Chứng minh.
(cid:98)x−i0, (cid:98)xi0
Bài toán bất đẳng thức biến phân hỗn hợp (2.19) được viết lại tương
(yi − xi) +
βi
i
xj − αi
βi
i − x2
n (cid:80) i=1
n (cid:80) i=1
n (cid:80) j(cid:54)=i
đương với bài toán: Tìm x ∈ U sao cho: (cid:33) (cid:32) (cid:1) (cid:0)y2
+
(hi(yi) − hi(xi)), ∀y ∈ U.
n (cid:80) i=1
30
(2.25)
Chương 2. Mô hình Nash - Cournot với cước phí lõm
U = U1 × U2 × ... × Un,
Giả sử x = (x1, x2, ..., xn)T ∈ U là nghiệm của bài toán này. Cố định i và lấy yj = xj với mọi i (cid:54)= j. Khi đó, vì:
Từ (2.25) chúng ta có:
βi
xj − αi
βi
i
(yi − xi) +
i − x2
n (cid:80) i=1
n (cid:80) j(cid:54)=i
(cid:32) (cid:33) (cid:1) (cid:0)y2
+hi(yi) − hi(xi) ≥ 0, ∀yi ∈ Ui.
(2.26)
đúng với mọi i(i = 1, 2, ..., n).
Ngược lại, nếu (2.26) đúng với mọi i(i = 1, 2, ..., n) thì hiển nhiên (2.25)
αi0 (yi0 − xi0) + hi0(yi0) − hi0(xi0) ≥ 0, ∀yi0 ∈ Ui0.
đúng. Thay βi0 = 0 vào (2.24) ta có:
Điều này chứng tỏ xi0 là một nghiệm tối ưu của bài toán (2.24). Với i = i0 và xi0 = (cid:98)xi0 thì (2.26) được rút gọn thành:
βi
(yi − xi)
xj − αi + βiˆxi0
n (cid:80) j(cid:54)=i,i0
(cid:32) (cid:33)
(2.27)
+βi
i − x2 i
(cid:0)y2 (cid:1) + hi(yi) − hi(xi) ≥ 0.
Điều này đúng với mọi yi ∈ Ui, (i = 1, 2, ..., n), i (cid:54)= i0. Bằng một cách tương tự, ta có thể thấy rằng (cid:98)x−i0 thỏa mãn (2.27) nếu và chỉ nếu (cid:98)x−i0 là (cid:1) là một nghiệm của nghiệm của bài toán (2.21). Tóm lại, (cid:98)x = (cid:0)ˆx−i0, ˆxi0 (cid:3) bài toán (2.19).
0, ηn ni
U = (cid:2)η1
Từ mệnh đề trên, không mất tính tổng quát, ta giả sử rằng βi > 0 với (cid:3) với i = (1, 2, ..., n), ta có: mọi i. Với Ui = (cid:2)ηi
0 , ηn nn
0, η1 n1
0, η2 n2 Đặt Γi là họ gồm tất cả các đoạn con kế tiếp nhau của đoạn Ui(i = 1, 2, ..., n), nghĩa là:
(cid:3) × ... × (cid:2)ηn (cid:3) × (cid:2)η2 (cid:3) ,
Γi = (cid:8)(cid:2)ηi
j−1, ηi j
(cid:9) , (cid:3) |j = 1, ..., ni
:= {I|I = I1 × I2 × ... × In : Ii ∈ Γi, i = 1, ..., n} .
31
Đặt: (cid:88)
Chương 2. Mô hình Nash - Cournot với cước phí lõm
I
Ii và U = (cid:83) I∈(cid:80)
Hiển nhiên với mọi (i = 1, ..., n) ta có: Ui = (cid:83) Ii∈Γi Với mỗi hộp con I ∈ (cid:80) chúng ta giải bài toán bất đẳng thức biến phân hỗn hợp có dạng: Tìm điểm xI ∈ I sao cho:
Φ (cid:0)xI, y(cid:1) := (cid:10)F (cid:0)xI, y − xI(cid:1)(cid:11) + ϕ(y) − ϕ(xI) ≥ 0∀y ∈ I.
(2.28)
Chú ý rằng bài toán phụ (2.28) có thể được viết lại thành: Tìm điểm xI ∈ I sao cho:
≥ 0∀y ∈ I.
(cid:68) (2.29) (cid:101)QxI + q, y − xI(cid:69)
Trong đó:
,
... β1 2β1 β1 β1 ... β2 β2 2β2 β2 ... ... ... ... ... βn βn ... 2βn βn
(2.30) (cid:101)Q =
và qT = (q1, ..., qn) với
qi = ai
ji−1 − αi (i = 1, ..., n) .
(2.31)
Định lý 2.2.
(i) Với mỗi I ∈ (cid:80) bài toán phụ (2.28) có duy nhất nghiệm;
(ii) Bài toán bất đẳng thức biến phân hỗn hợp (2.19) có nghiệm khi và chỉ khi tồn tại I∗ ∈ (cid:80) sao cho θ (cid:0)xI∗(cid:1) = 0, trong đó θ được định nghĩa theo (2.22). Chứng minh.
(i) Do từ bài toán (2.28) có thể được đưa về dạng bài toán (2.29). Và bài toán (2.29) tương đương với bài toán quy hoạch hàm toàn phương lồi mạnh (2.14). Do đó bài toán phụ (2.28) có duy nhất nghiệm.
xI∗ là nghiệm của bài toán (2.19). Ngược lại, giả sử rằng x∗ ∈ U là một nghiệm của bài toán (2.19) . Với
(ii) Giả sử rằng tồn tại xI∗ ∈ U sao cho θ (cid:0)xI∗(cid:1) = 0. Theo mệnh đề (2.2)
U =
I,
I∈(cid:80) nên tồn tại hộp con I∗ ∈ (cid:80) sao cho x∗ ∈ I∗. Theo phần (i), x∗ phải bằng xI∗. Lại theo mệnh đề (2.2) xI∗ chúng ta có θ (x∗) = 0.
(cid:91)
32
(cid:3)
Chương 2. Mô hình Nash - Cournot với cước phí lõm
2.2.2 Thuật giải
0, ηi ni
Trong phần này chúng ta sẽ đưa ra một phương pháp giải mô hình kinh tế Nash - Cournot trong trường hợp hàm chi phí lõm, tuyến tính từng khúc.
< +∞, (ni ≥ 1) ,
0 < ηi
1 < ... < ηi ni
Một trong những dạng hàm chi phí hi sát với thực tiễn là dạng hàm lõm tuyến tính từng khúc. Một cách cụ thể, chúng ta giả sử rằng tập chiến lược của công ty i (i = 1, 2, ..., n) là Ui := (cid:2)ηi (cid:3) được chia thành ni khoảng: 0 ≤ ηi
hi (xi) :=
(2.32)
0 ≤ xi ≤ ηi ηi 1, 1 ≤ xi ≤ ηi ηi 2, ... ni−1 ≤ xi ≤ ηi ni.
khi khi ... ni−1 khi ηi
Trên mỗi đoạn nhỏ thì hi là hàm affine, cụ thể có dạng sau: 0xi + bi ai 0 1xi + bi ai 1 ... ni−1xi + bi ai
Trong đó,
< ... < ai
1 < ai
0 < +∞, αi > ai
0∀i,
0 < ai ni
(2.33)
0 ≤ bi
, (i = 1, 2, ..., n) .
0 < bi
1 < ... < bi ni
(2.34)
hi (xi) = min
jxi + bi j
0≤j≤ni−1
Các giả thiết (2.20) và (2.21) là hoàn toàn tự nhiên, khi sản lượng xi của công ty i vượt qua một giá trị nhất định thì hệ số chi phí biến đổi sẽ giảm. Nếu ni = 1 thì hi là affine trên đoạn Ui. Một cách tổng quát thì hi (i = 1, 2, ..., n) có thể viết dưới dạng sau: (cid:8)ai (cid:9) .
Trong thuật toán sẽ được mô tả dưới đây, với mỗi I ∈ (cid:80) ta phải giải bài toán một bài toán quy hoạch toàn phương lồi mạnh (2.10). Giả sử I = I1 × ... × In với:
Ii := (cid:2)ηi
ji−1, ηi ji
(cid:3) (i = 1, 2, ..., n) .
aI = (cid:0)a1
Để tính vectơ cT = (c1, ..., cn) trong hàm mục tiêu của bài toán (2.10), trước hết chúng ta cần tính:
ji−1, ..., an
jn−1
(cid:1) ,
Sau đó lấy:
ji−1, ..., αi
1 βi
33
(cid:1) (i = 1, 2, ..., n) . (cid:0)a1 (cid:101)ci =
Chương 2. Mô hình Nash - Cournot với cước phí lõm
+ ϕ (y) − ϕ (cid:0)xI(cid:1)(cid:111)
,
min y∈U
(cid:110)(cid:68) (2.35) Đặt xI là một nghiệm tối ưu duy nhất của bài toán (2.10). Sử dụng nghiệm thu được xI, chúng ta tính θ (cid:0)xI(cid:1) là giá trị tối ưu của bài toán: (cid:101)BxI − α, y − xI(cid:69)
ϕi (yi). Từ hàm
n (cid:80) i=1
trong đó, khi h tách được, từ (2.17) và (2.18), ϕ (y) :=
mục tiêu của bài toán (2.35) là tách được, bài toán này có thể được rút gọn thành n bài toán tối ưu một biến, mỗi bài toán có dạng sau:
{fi (yi)} (i = 1, 2, ..., n) ,
f ∗ i := min yi∈Ui
(2.36)
f ∗ i .
n (cid:80) i=1
Từ định nghĩa, ta có θ (cid:0)xI(cid:1) =
Dưới đây là nội dung cụ thể của thuật toán.
THUẬT TOÁN
Chọn một sai số ε ≥ 0
Bước 1: Chọn một hộp con I ∈ (cid:80) . Bước 2: Giải bài toán quy hoạch hàm toàn phương lồi mạnh (2.10) để
nhận được nghiệm lồi tối ưu duy nhất xI.
n (cid:88)
θ (cid:0)xI(cid:1) =
f ∗ i .
i=1
Bước 3: Giải n bài toán tối ưu một chiều (2.36) nhận được f ∗ i (i = 1, ..., n) Lấy:
(a) Nếu θ (cid:0)xI(cid:1) ≥ −ε thì dừng, chúng ta lấy xI là một điểm ε cân bằng; (b)Nếu θ (cid:0)xI(cid:1) < −ε và (cid:80) = φ thì dừng. Trường hợp này bài toán không có điểm cân bằng. Mặt khác, thay (cid:80) bởi ((cid:80) \ {I}) và quay lại bước 1. Tính hiệu quả của thuật toán được khằng Định bởi định lý 2.2. Vì (cid:80) là một tập hữu hạn nên thuật toán phải kết thúc ở trường hợp (a) hoặc trường hợp (b). Trong trường hợp xấu nhất, thuật toán phải tìm kiếm trên toàn bộ số hộp con trong (cid:80) .
Ví dụ 2.2.
U2 = [0, 5] là tập chiến lược của công ty thứ hai. Giả sử: Hàm chi phí của công ty thứ nhất khi sản xuất x1 đơn vị hàng hóa là:
h1 (x1) = min {2x1 + 1, 3x1} ,
34
Có hai công ty. Gọi U1 = [0, 10] là tập chiến lược của công ty thứ nhất,
Chương 2. Mô hình Nash - Cournot với cước phí lõm
h2 (x2) = 2x2 + 1.
Hàm chi phí của công ty thứ hai khi sản xuất x2 đơn vị hàng hóa là:
f1 (x1, x2) = x1p (x1 + x2) − min {2x1 + 1, 3x1} ,
f2 (x1, x2) = x2p (x1 + x2) − (2x2 + 1) .
Hàm giá của cả hai công ty là chung: p (σ) = 10 − 0.5 (x1 + x2). Vậy hàm lợi nhuận của các công ty lần lượt là:
Áp dụng thuật giải trên ta có: Do hàm chi phí của công ty thứ nhất là lõm tuyến tính trên hai đoạn [0, 1] và [1, 10], còn hàm chi phí của công ty thứ hai là affine nên tập chiến lược của mô hình được chia ra thành hai tập.
Tập chiến lược thứ nhất: Chiến lược của công ty thứ nhất: U1 = [0, 1], chiến lược của công ty thứ
h1 (x1) = 3x1,
h2 (x2) = h2 (x2) = 2x2 + 1.
hai: U2 = U2 = [0, 5] . Với hàm chi phí tương ứng của các công ty lần lượt là:
p (σ) = 10 − 0.5 (x1 + x2) .
Hàm giá của cả hai công ty là chung và không thay đổi:
f1 (x1, x2) = x1p (x1 + x2) − h1 (x1) ,
f2 (x1, x2) = x2p (x1 + x2) − h2 (x2) .
Vậy hàm lợi nhuận của mỗi công ty lần lượt là:
Q =
Áp dụng thuật toán chuyển bài toán này về dạng toàn phương lồi mạnh Cách làm tương tự ví dụ 2.1 Ta có: (cid:19)
0.5 1
; µ = (µ1, µ2) = (3, 2); α = (α1, α2) = (10, 10). (cid:18) 1 0.5
Từ đây suy ra:
q =
⇒ qT = (−7, −8) .
(cid:19)
(cid:18) −7 −8
Suy ra ta có:
+ (−7, −8)
(x1, x2)
(cid:19) (cid:19)
0.5 1
1 2
35
(cid:18) 1 0.5 (cid:19) (cid:18) x1 x2 (cid:18) x1 x2
Chương 2. Mô hình Nash - Cournot với cước phí lõm
=
x1x2 − 7x1 − 8x2.
x2 1 +
x2 2 +
1 2
1 2
1 2
Suy ra, bài toán toàn phương lồi mạnh là:
,
x1x2 − 7x1 − 8x2
x2 1 +
x2 2 +
(cid:27)
1 2
1 2
min x1∈U1 x2∈U2
(cid:26)1 2
Sử dụng công cụ tính toán MALAB với hàm quadprog trong gói opti-
moization toolbox ta giải được nghiệm của bài toán là:
(cid:26) x1 = 1 x2 = 5
f1 (x1, x2) = 4, f2 (x1, x2) = 24.
Từ đây suy ra hàm giá của cả hai công ty ứng với tập chiến lược thứ nhất là: p (δ) = 7. và giá trị hàm lợi nhuận của mỗi công ty ứng với tập chiến lược thứ nhất lần lượt là:
Tập chiến lược thứ hai: Chiến lược của công ty thứ nhất: (cid:102)U1 = [1, 10], chiến lược của công ty
thứ hai: (cid:102)U2 = [0, 5] . Với hàm chi phí tương ứng của các công ty lần lượt là:
(cid:101)h1 (x1) = 2x1 + 1,
(cid:101)h2 (x2) = h2 (x2) = 2x2 + 1.
p (σ) = 10 − 0.5 (x1 + x2) .
Hàm giá của cả hai công ty là chung và không thay đổi:
Vậy hàm lợi nhuận của mỗi công ty lần lượt là:
(cid:101)f1 (x1, x2) = x1p (x1 + x2) − (cid:101)h1 (x1) ,
(cid:101)f2 (x1, x2) = x2p (x1 + x2) − (cid:101)h2 (x2) .
Q =
Áp dụng thuật toán chuyển bài toán này về dạng toàn phương lồi mạnh Cách làm tương tự ví dụ 2.1 Ta có: (cid:19)
0.5 1
; µ = (µ1, µ2) = (2, 2); α = (α1, α2) = (10, 10). (cid:18) 1 0.5
36
Từ đây suy ra:
Chương 2. Mô hình Nash - Cournot với cước phí lõm
q =
⇒ qT = (−8, −8) .
(cid:19)
(cid:18) −8 −8
Suy ra ta có:
+ (−8, −8)
(x1, x2)
(cid:19) (cid:19)
0.5 1
1 2
=
x1x2 − 8x1 − 8x2.
x2 1 +
x2 2 +
1 2
1 2
1 2
(cid:18) 1 0.5 (cid:19) (cid:18) x1 x2 (cid:18) x1 x2
Suy ra, bài toán toàn phương lồi mạnh là:
.
x1x2 − 8x1 − 8x2
x2 1 +
x2 2 +
(cid:27)
1 2
1 2
min x1∈(cid:102)U1 x2∈(cid:102)U2
(cid:26)1 2
Sử dụng công cụ tính toán MALAB với hàm quadprog trong gói opti-
moization toolbox ta giải được nghiệm của bài toán là:
(cid:26) x1 = 5.5 x2 = 5
Từ đây suy ra hàm giá của cả hai công ty ứng với tập chiến lược thứ hai là: p (δ) = 4.75 và giá trị hàm lợi nhuận của mỗi công ty ứng với tập chiến lược thứ hai lần lượt là:
(cid:101)f1 (x1, x2) = 14.125, (cid:101)f2 (x1, x2) = 12.75.
Vậy thực chất của việc giải bài toán ban đầu đã cho, chúng ta đưa về
giải hai bài toán quy hoạch hàm toàn phương lồi mạnh sau:
,
x1x2 − 7x1 − 8x2
x2 1 +
x2 2 +
(cid:27)
1 2
1 2
min x1∈U1 x2∈U2
(cid:26)1 2
.
x1x2 − 8x1 − 8x2
x2 1 +
x2 2 +
và (cid:27)
1 2
1 2
min x1∈(cid:102)U1 x2∈(cid:102)U2
37
(cid:26)1 2
38
Kết luận
Mô hình kinh tế Nash - Cournot là một vấn đề quan trọng trong toán ứng dụng bởi phạm vi ứng dụng của nó rất rộng rãi và nó 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ế. Bản luận văn này nhằm mục đích giới thiệu về mô hình Nash - Cournot và nghiên cứu về mô hình Nash - Cournot khi cước phí là lõm. Đồng thời giới thiệu một phương pháp giải cho bài toán lõm tuyến tính từng khúc. Cụ thể như sau:
Chương 1: Ta tìm hiểu về các kiến thức giải tích cơ bản, cực trị của
hàm lồi, bất đẳng thức biến phân.
Chương 2: Ta tìm hiểu về mô hình cân bằng Nash - Cournot cổ điển, cách đưa mô hình về dạng bài toán toàn phương lồi mạnh. Rồi tìm hiểu cách đưa mô hình về bài toán bất đẳng thức biến phân hỗn hợp khi mô hình có cước phí là lõm. Đồng thời, giới thiệu một phương pháp để giải bài toán với cước phí lõm tuyến tính từng khúc.
39
Tài liệu tham khảo
Tiếng Việt
[1] Nguyễn Văn Hiền, Lê Dũng Mưu, Nguyễn Hữu Điển (2015), Giáo
trình Giải tích lồi ứng dụng, NXB ĐHQG, Hà Nội.
[2] Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học
và Kỹ thuật, Hà Nội.
[3] Lê Dũng Mưu (1998), Nhập môn các phương pháp tối ưu , NXB
Khoa học và Kỹ thuật, Hà Nội.
[4] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi
tuyến, NXB ĐHQG Hà Nội.
Tiếng Anh
[5] Konnov I. (2001), Combined Relaxation Methods for Variational
Inequalities, Springer, Berlin.
[6] Muu L. D, Nguyen V. H, Quy N. V. (2008), "On Nash – Cournot oligopolistic market equilibrium models with concave cost functions", J. Glob Optim 41, pp. 351 – 364.
[7] Tuy H. (2008), Convex Analysis and Global Optimization, Springer.
