Mục lục
trang
Mở đầu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
Chương 1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1. Bài toán quy hoạch phi tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1. Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2. Hàm Lagrange và tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Các phương pháp tiếp cận giải bài toán quy hoạch phi tuyến . . . . . . 9
1.2.1. Phương pháp Gradien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2. Phương pháp nhân tử Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Một số khái niệm cơ sở của lý thuyết xác suất . . . . . . . . . . . . . . . . . . . .11
1.3.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2. Kỳ vọng và phương sai của biến ngẫu nhiên . . . . . . . . . . . . . . . . . . 13
1.4. Bài toán quy hoạch ngẫu nhiên hai giai đoạn . . . . . . . . . . . . . . . . . . . . . 15
1.4.1. Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2. Giai đoạn thứ nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3. Giai đoạn thứ hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Chương 2. Một lớp bài toán quy hoạch phi tuyến ngẫu nhiên
và thuật toán giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1. Bài toán quy hoạch phi tuyến ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1. Bài toán thực tế . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.2. Mô hình tổng quát bài toán quy hoạch phi tuyến ngẫu nhiên
hai giai đoạn (2SSN LP ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2. Bài toán quy hoạch phi tuyến ngẫu nhiên hai giai đoạn có sự
chuyển đổi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1. Bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn có sự
chuyển đổi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2. Bài toán quy hoạch phi tuyến ngẫu nhiên hai giai đoạn có sự


chuyển đổi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

quy hoạch phi tuyến ngẫu nhiên cùng một số hướng tiếp cận giải. Khi
tiếp cận với cuốn sách Optimization Theory II, Spring, 2007, Chapter 1
[4], chúng tôi nhận được những kết quả nghiên cứu chi tiết hơn. Vì lẽ đó,
trong phạm vi luận văn tốt nghiệp cao học, tôi đã cố gắng nghiên cứu về
thuật toán giải cho một lớp bài toán quy hoạch phi tuyến ngẫu nhiên. Đó
là lý do chúng tôi lựa chọn đề tài "Tiếp cận giải một lớp bài toán
quy hoạch phi tuyến ngẫu nhiên".
Mục tiêu và nhiệm vụ nghiên cứu của đề tài là: Trình bày một cách hệ
thống những khái niệm và kiến thức cơ sở nhằm phục vụ cho việc nghiên


4

cứu các nội dung có liên quan trong luận văn. Trên cơ sở đó nghiên cứu
một lớp bài toán quy hoạch phi tuyến ngẫu nhiên tổng quát. Từ đó xét bài
toán quy hoạch phi tuyến ngẫu nhiên bậc hai và nêu thuật toán giải nó.
Luận văn được chia làm hai chương:
Chương 1. Kiến thức chuẩn bị. Trong chương này, chúng tôi trình
bày các nội dung: Bài toán quy hoạch phi tuyến; các phương pháp tiếp cận
giải bài toán quy hoạch phi tuyến; một số khái niệm cơ sở của lý thuyết
xác suất.
Chương 2. Một lớp bài toán quy hoạch phi tuyến ngẫu nhiên
và thuật toán giải. Trong chương này, chúng tôi trình bày các nội dung
chính của luận văn. Để có được mô hình bài toán quy hoạch phi tuyến,
trước hết chúng tôi nghiên cứu một mô hình thực tế. Từ đó nghiên cứu
bài toán quy hoạch phi tuyến ngẫu nhiên hai giai đoạn có sự chuyển đổi.
Cuối cùng, chúng tôi xét một lớp bài toán đặc biệt để tìm ra cách giải.
Luận văn được thực hiện và hoàn thành tại trường Đại học Vinh, dưới
sự hướng dẫn khoa học của PGS. TS. Trần Xuân Sinh. Tác giả xin bày tỏ
lòng biết ơn sâu sắc tới thầy về sự hướng dẫn tận tâm đối với tác giả trong

x ∈ X ⊂ Rn ,

(1.1.3)

với điều kiện

trong đó X = {(x1 , x2 , ..., xn ) | xi ≥ 0, i = 1, n }, các hàm f0 (x), fi (x), (i =
1, n), đơn trị, khả vi và ít nhất một trong các hàm đó là phi tuyến.
Hàm f0 (x) gọi là hàm mục tiêu, các điều kiện (1.1.2), (1.1.3) gọi là điều
kiện buộc. Điểm x = (x1 , x2 , ..., xn ) thoả mãn các điều kiện buộc (1.1.2),
(1.1.3) gọi là phương án, ký hiệu tập phương án là M . Phương án x∗ làm
cực tiểu hàm mục tiêu f0 (x) gọi là phương án tối ưu (hoặc nghiệm) của bài
toán. Điều đó có nghĩa rằng x∗ là phương án tối ưu của bài toán (1.1.1)(1.1.3) khi và chỉ khi f0 (x∗ ) = minx∈M f0 (x), hay là
f0 (x∗ ) ≤ f0 (x), ∀x ∈ M.
Điểm x(0) được gọi là điểm cực tiểu địa phương của hàm f0 (x) nếu tồn
tại lân cận W0 sao cho
f0 (x(0) ) ≤ f0 (x), ∀x ∈ M ∩ W0 .


6

1.1.1.2. Bài toán quy hoạch lồi từng phần
Bây giờ chúng ta xét bài quy hoạch phi tuyến đặc biệt, đó là bài toán
quy hoạch lồi từng phần.
Cho K là phức hợp hữu hạn các tập lồi đóng. Một phức hợp lồi đóng
hữu hạn các phần tử của K, được gọi là tế bào của K, nếu giao của hai tế
bào là rỗng.
Xét bài toán quy hoạch lồi từng phần (P.C.P ) (Piecewise Convex Program)
(P.C.P )


k

sau đây:

f1 (x) = 1 x, 0 ≤ x ≤ 2,
2
f (x) =
f (x) = (x − 1)2 , x ≥ 2.
2

Rõ ràng hàm số này là lồi từng khúc (2 khúc) trên M = R+ , nhưng
f2 (x) > f1 (x) = f (x) trên [0; 1/2]
1.1.1.3. Thuật toán giải bài toán (P.C.P )
Từ việc nghiên cứu bài toán quy hoạch lồi từng phần, tác giả F. V.
Louveaux [5] đã đưa ra thuật toán giải bài toán (P.C.P ) như sau:
Thuật toán (P.C.P )
Bước chuẩn bị. Chọn x0 ∈ M . Đặt M1 := M, k := 1, chuyển sang
bước 1.
Bước 1. Xác định Ck sao cho xk−1 ∈ Ck ∩ intMk = ∅.
Bước 2. Xác định xk ∈ arg min{fk (x) : x ∈ Mk },
wk ∈ arg min{fk (x) : x ∈ Ck }.
Nếu wt là điểm tới hạn của một tia là hướng giảm của fk (.) tới −∞ thì
bài toán (P.C.P ) ban đầu bị chặn, chuyển tới bước 4.
Ngược lại, chuyển sang bước 3.
Bước 3. Nếu ∇fk (wk ).(xk − wk ) = 0, chuyển sang bước 4.
Ngược lại, gán
Mk+1 := Mk ∩ {x : ∇fk (wk ).(x − wk ) ≤ 0}, k := k + 1,
trở lại bước 1.
Bước 4. Thuật toán kết thúc: wk là phương án tối ưu.
1.1.1.4. Định lý [5]. Thuật toán 1.1.1.3 sẽ nhận được phương án tối ưu


L(x, y) = f0 (x) +

yi fi (x).
i=1

trong đó x = (x1 , x2 , ..., xn ); y = (y1 , y2 , ..., ym ).
Hàm L(x, y) được gọi là hàm Lagrange của bài toán đã cho.
Các giá trị yi , i = 1, 2, ..., m gọi là nhân tử Lagrange.
Ký hiệu ∇f là vectơ đạo hàm riêng của hàm f (x), nghĩa là
∇f = (fx1 , fx2 , ..., fxn ); ∇f ∗ = ∇f (x∗ ), B ∗ = {i : fi (x∗ ) = 0}.
Tại phương án x∗ , ta ký hiệu
Rn1 = {z ∈ Rn : z, ∇fi∗ ≥ 0, i ∈ B ∗ ; z, ∇f0∗ ≥ 0}
Rn2 = {z ∈ Rn : z, ∇fi∗ ≥ 0, i ∈ B ∗ ; z, ∇f0∗ < 0}
Rn3 = {z ∈ Rn : ∃i ∈ B ∗ , z, ∇fi∗ < 0}.
Điểm (x∗ , y ∗ ) thoả mãn điều kiện
L(x∗ , y) ≤ L(x∗ , y ∗ ) ≤ L(x, y ∗ )

(1.1.9)


9

được gọi là điểm yên ngựa của hàm Lagrange L(x, y).
Một số tính chất của bài toán
1.1.2.1. Định lý. Nếu các hàm số f0 , fi , i = 1, 2, ..., m là các hàm lồi,
X là tập lồi thì bài toán (1.1.6) − (1.1.8) luôn tồn tại điểm yên ngựa.
1.1.2.2. Định lý. (về sự tồn tại nhân tử Lagrange) Cho phương án x∗ .
Nếu tập Rn2 = ∅ thì tồn tại vectơ y ∗ ≥ 0 thoả mãn điều kiện
fi (x∗ ) ≥ 0; yi∗ fi (x∗ ) = 0, i = 1, m; ∇L(x∗ , y ∗ ) = 0.



10

1.2.1. Phương pháp Gradien
Ta đã biết vectơ Gradien (đạo hàm riêng) tại điểm x(0) chỉ hướng tăng
và đối Gradien là hướng giảm của hàm mục tiêu từ điểm đó. Từ đó ta có
thuật toán như sau:
Thuật toán
Bước xuất phát. Chọn một phương án x(0)
Bước k, k = 1, ... Ta đã có x(k) , (k ≥ 0).
k.1. Dịch chuyển từ x(k) theo hướng −∇f0 (x(k) ) tới điểm x(k) +λ[−∇f (x(k) )]
sẽ làm biến đổi hàm f0 một số gia
∆f0 = −f0 [x(k) − λ∇f0 (x(k) )] + f0 (x(k) ).
Giá trị λ được xác định sao cho số gia ∆f0 đạt lớn nhất, là nghiệm của
phương trình
d∆f0
= 0 ≈ −∇f0 [x(k) − λ∇f0 (x(k) ](−∇f0 (x(k) ) = 0.
dλ

(1.2.1)

Từ (1.2.1), ta tìm được λ∗
Nếu tại λ∗ có

d2 ∆f0
dλ2

< 0 thì ta có điểm cực đại của hàm ∆f0 .


 ∂L = b − f (x) = 0.
∂yi

i

i

Bước 2. Giải hệ trên, được các điểm dừng (x, y). Chọn các điểm dừng
là phương án. Lấy một điểm dừng (x∗ , y ∗ )
Bước 3. Kiểm tra điều kiện
∇fi (x∗ )T ∇2xx L(x∗ , y ∗ )∇fi (x∗ ) > 0?
Nếu có thì x∗ là điểm cực tiểu địa phương. So sánh các điểm cực tiểu
địa phương và các điểm biên để tìm phương án tối ưu.
Ngược lại, trở lại bước 2 với điểm dừng khác.
1.3. Một số khái niệm cơ sở của lý thuyết xác suất
1.3.1. Định nghĩa
1.3.1.1. σ-đại số
Giả sử Ω là một tập tuỳ ý khác rỗng. Ký hiệu P(Ω) là tập hợp gồm tất
cả các tập con của Ω.
• Lớp A ⊂ P(Ω) được gọi là một đại số nếu:
A1) Ω ∈ A,
A2) Nếu A ∈ A thì A = Ω\A ∈ A,
A3) Nếu A, B ∈ A thì A ∪ B ∈ A, (hoặc A ∩ B ∈ A).
• Lớp F ⊂ P(Ω) được gọi là σ-đại số nếu nó là đại số và ngoài ra


12

A4) Nếu An ∈ F, ∀n = 1, 2, ... thì
∞

i=1 Ai

i=1

P(Ai ).
i=1

Giả sử Ω là tập bất kỳ khác rỗng, F là một σ-đại số các tập con của
Ω, P là độ đo xác suất trên F. Khi đó, bộ ba (Ω, F, P) được gọi là không
gian xác suất.
1.3.1.4. Đại lượng ngẫu nhiên. Giả sử (Ω, F, P) là không gian xác suất;
G là σ-đại số con của σ-đại số F; B là σ-đại số Borel trên R. Khi đó ánh
xạ
X:Ω→R
được gọi là biến ngẫu nhiên G-đo được, nếu nó là ánh xạ G/B(R)-đo được.
Lúc này, biến ngẫu nhiên còn được gọi là đại lượng ngẫu nhiên. Trong
trường hợp đặc biệt, khi X là biến ngẫu nhiên F-đo được thì X gọi một
cách đơn giản là biến ngẫu nhiên.


13

1.3.1.5. Hàm Borel. Hàm ϕ : (Rn , B(Rn )) → (R, B(R)) được gọi là
hàm Borel nếu nó là B(Rn ) - đo được, nghĩa là ϕ−1 (B) ∈ B(Rn ) với mỗi
B ∈ B(R).
1.3.1.6. Hàm phân phối xác suất của biến ngẫu nhiên. Giả sử X là biến
ngẫu nhiên xác định trên (Ω, F, P) nhận giá trị trên R. Hàm số FX (x) =
P[X < x], (x ∈ R) được gọi là hàm phân phối của biến ngẫu nhiên X.
1.3.2. Các đặc trưng của đại lượng ngẫu nhiên
1.3.2.1. Khái niệm

2n ( 2n ≤X< 2n )

Khi đó
EX := lim EXn .
n→∞

Nếu X là biến ngẫu nhiên bất kỳ thì X = X + − X − , trong đó
X + = max(X, 0) ≥ 0; X − = max(−X, 0) ≥ 0.
Khi đó EX := EX + − EX − (nếu có nghĩa).
Phương sai. Giả sử X là đại lượng ngẫu nhiên. Khi đó số DX =
E(X − EX)2 (nếu tồn tại) gọi là phương sai của X.


14

Như vậy, phương sai có thể tồn tại hoặc không tồn tại. Nếu tồn tại thì
được tính theo công thức


2

nếu X rời rạc và P(X = xi ) = pi
 (xi − EX) pi
i
DX =
+∞


(x − EX)2 p(x)dx nếu X liên tục và có hàm mật độ là p(x).


Bài toán quy hoạch ngẫu nhiên, thông thường có thể xẩy ra một giai
đoạn, hai giai đoạn hoặc nhiều giai đoạn. Về mặt hình thức có thể thấy
quá trình tối ưu phụ thuộc biến ngẫu nhiên thì sẽ xuất hiện theo lược đồ:
Phương án ⇒ điều chỉnh ⇒ ... ⇒ điều chỉnh ⇒ phương án.
+ Nếu quá trình đó chỉ xảy ra một lần xét phương án mà không cần
điều chỉnh thì bài toán đó được gọi là bài toán một giai đoạn.
+ Nếu quá trình đó xảy ra hai lần xét tới phương án thì bài toán đó
được gọi là bài toán hai giai đoạn.
+ Nếu quá trình đó chỉ xảy ra hơn hai lần xét phương án thì bài toán
đó được gọi là bài toán nhiều giai đoạn.
Thật ra, nhìn nhận một cách tương đối nếu lấy một thời điểm nào đó
làm phương án xuất phát và coi đó là giai đạn thứ nhất thì giai đoạn tiếp
theo là giai đoạn thứ hai. Cứ như vậy cho thấy bài toán quy hoạch nhiều
giai đoạn được thực hiện nhờ vào bài toán quy hoạch hai giai đoạn bằng
công thức đệ quy.
Vì lẽ đó, để ngắn gọn, trong mục này, chúng tôi chỉ trình bày lược đồ
phân chia theo hai giai đoạn của bài toán quy hoạch tuyến tính.
1.4.1. Bài toán
Xét bài toán quy hoạch tuyến tính
min f (x) = cT x ,

 Ax = b
với điều kiện
 T x = h x ≥ 0.

(1.4.1)

trong đó c = (cj ) là ma trận cỡ 1 × n, x = (xj ) là ma trận cỡ 1 × n,
A = (aij ) là ma trận cỡ m × n, b = (bi ) là ma trận cỡ 1 × m, cT là ma trận
chuyển vị của c, h là ma trận cỡ p × 1 và T là ma trận cỡ p × n.

lượng phạt q T y với những điều kiện đặt ra dưới sự tác động của ω, tạo nên
sự cân bằng mới. Do vậy ta có bài toán ở giai đoạn hai (thứ hai) với biến


17

y là
Q(x, ω) = min q T y

 T (ω)x + W y(ω) = h(ω)
với điều kiện
 y ≥ 0.

(1.4.2)

Hàm Q(x, ω) được gọi là hàm hiệu chỉnh, vectơ x và y tương ứng là biến
của giai đoạn thứ nhất và giai đoạn thứ hai.
Ký hiệu
Q(x) := E Q(x, ω) .
Khi đó bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn có dạng
min cT x + Q(x)

Ax = b
với điều kiện
x ≥ 0,
trong đó Q(x) := E Q(x, ω) , với
Q(x, ω) = min q T y

 T (ω)x + W y(ω) = h(ω)
với điều kiện

5

3

6

4

4

Ch.phí trồng (tr)

3

4

4

-

-

-

Ch.phí công (tr)

3

2


 x1 , x2 , x3 ∈ {0, 1}.
Ta ký hiệu


A=

3 4 4
3 2 1

, b=


 
 
0 3 2
4
x1


 
 
8
, C=
, c=
, x=
3 0 2
5
x2 



c = (cj ) ma trận cỡ n × 1, x = (xj ) cỡ n × 1.
2.1.2. Mô hình tổng quát bài toán quy hoạch phi tuyến ngẫu
nhiên hai giai đoạn (2SSN LP )
Xét bài toán quy hoạch phi tuyến
min z = f 1 (x)


20


 g 1 (x) ≤ 0, 1 ≤ i ≤ m1 ,
i
với điều kiện
 g 1 (x) = 0, m + 1 ≤ i ≤ m .
1
1
i
trong đó các hàm số f 1 : Rn1 → R, gi1 : Rn1 → R, 1 ≤ i ≤ m1 liên tục trên
R n1 .
Giả sử rằng bài toán đã cho, với dữ liệu đầy đủ, chúng ta đã tìm được
phương án tối ưu trong tập các phương án x đã xác định. Các phương án
x như vậy được coi là biến ở giai đoạn thứ nhất và bài toán nêu trên gọi
là bài toán giai đoạn thứ nhất.
Khi thông tin về dữ liệu trong điều kiện buộc phụ thuộc vào biến ngẫu
nhiên ω thì tập phương án sẽ thay đổi. Sự thay đổi này là do dưới sự tác
động của biến ngẫu nhiên ω làm thay đổi giá trị của vế trái điều kiện buộc.
Để thiết lập bài toán giai đoạn thứ hai, ta ký hiệu:
f 2 (., ω) : Rn2 → R là hàm số biểu diễn tổng số giá trị "phạt".
gi2 y(ω), ω) : Rn2 → R, 1 ≤ i ≤ m2 , là hàm số tạo ra từ hàm gi1 ở
những điều kiện có ảnh hưởng từ ω.

2
i
i
2.2. Bài toán quy hoạch phi tuyến ngẫu nhiên hai giai đoạn có sự
chuyển đổi
Để thuận lợi, trước khi trình bày bài toán quy hoạch phi tuyến ngẫu
nhiên hai giai đoạn có sự chuyển đổi, chúng ta trình bày bài toán quy hoạch
tuyến tính ngẫu nhiên hai giai đoạn có sự chuyển đổi.
2.2.1. Bài toán quy hoạch tuyến tính ngẫu nhiên hai giai đoạn
có sự chuyển đổi cố định
2.2.1.1. Định nghĩa. Giả sử A ⊂ Rm1 ×n1 , W ⊂ Rm2 ×n2 là các ma trận
cố định, T (ω) ⊂ Rm2 ×n1 là ma trận ngẫu nhiên phụ thuộc biến ngẫu nhiên
ω, c ∈ Rn1 , b ∈ Rm1 là các vectơ cố định và q(ω) ∈ Rn2 , h(ω) ∈ Rm2 là các
vectơ ngẫu nhiên phụ thuộc biến ngẫu nhiên ω.
Ký hiệu N := n2 + m2 + (m2 × n1 ). Đặt
ξ T (ω) := q(ω)T , h(ω)T , T1 (ω), ..., Tm2 (ω) ∈ RN ,
trong đó Ti (ω), 1 ≤ i ≤ m2 , là các hàng của ma trận T (ω).
Như đã nêu trong mục 1.4 chương 1, ta có bài toán
min cT x + Eξ min q(ω)T y(ω)



Ax = b



với điều kiện
T (ω)x + W y(ω) = h(ω)



hai.
Ký hiệu
K1 := x ∈ Rn1 : Ax = b ,

(2.2.4)

K2 := x ∈ Rn1 : Q(x) < ∞ .
Tập K1 gọi là tập phương án giai đoạn thứ nhất và K2 tương ứng là tập
phương án của giai đoạn thứ hai.
Giả sử Σ ⊂ RN sao cho P {ξ ∈ Σ} = 1. Nếu Σ là hữu hạn, Q(x) là
tổng có trọng số của những giá trị hữu hạn Q(x, ξ). Chúng ta quy ước rằng
nếu xảy ra giá trị ±∞ thì ta xem như +∞ + (−∞) = +∞.
Ta lại ký hiệu
K2 (ξ) := x ∈ Rn1 : Q(x, ξ) < ∞ ,

(2.2.5)

K2P := x ∈ Rn1 : ∀ξ ∈ Σ, ∃y ≥ 0 sao cho W y = T x =

K2 (ξ).
ξ∈Σ


23

Các tập trong (2.2.5) gọi là tập phương án cơ sở của giai đoạn thứ hai và
là thể hiện có thể giải thích về tập phương án ở giai đoạn thứ hai.
Bài toán quy hoạch (2.2.1) được gọi là:
- có sự chuyển đổi hoàn chỉnh tương đối nếu K1 ⊂ K2 ,
- có sự chuyển đổi hoàn chỉnh nếu với mọi z ∈ Rm2 thì tồn tại y ≥ 0 sao


24

(i) Q(x, ξ) là hàm tuyến tính từng khúc và lồi theo x, với (h, T ) cố định.
(ii) Q(x, ξ) là hàm tuyến tính từng khúc và lồi theo z = W y, với q cố
định.
(iii) Q(x, ξ) là hàm tuyến tính từng khúc và lồi theo x với mọi x ∈
K1 ∩ K2 .
Chứng minh. Tính tuyến tính từng khúc trong (i)-(iii) đã được chỉ ra
trong [7].
Để chứng minh tính lồi theo x với (h, T ) cố định, ta chứng minh hàm
g(z) := min q T y : W y = z
là lồi theo z.
Với mỗi λ ∈ [0; 1] và z1 , z2 , (z1 = z2 ), ta đặt z(λ) := λz1 + (1 − λ)z2 và
ký hiệu yi∗ , 1 ≤ i ≤ 2 là phương án tối ưu của bài toán cực tiểu thứ tự tại
z = z1 , z = z2 . Khi đó y ∗ (λ) := λy1∗ + (1 − λ)y2∗ là một phương án đối với
z = z(λ). Nếu yλ∗ là phương án tối ưu tương ứng thì ta có
g z(λ) := q T yλ∗ ≤ q T y ∗ (λ) =
:= λq T y1∗ + (1 − λ)q T y2∗ = λg(z1 ) + (1 − λ)g(z2 ).
Việc chứng minh tính lồi theo q là tương tự.
2.2.1.4. Định lý. (Điều kiện tối ưu) Giả sử bài toán (2.2.2) có giá trị
tối ưu hữu hạn. Một nghiệm x∗ ∈ K1 là phương án tối ưu của (2.2.2) nếu
và chỉ nếu tồn tại λ∗ ∈ Rm1 , µ∗ ∈ Rn+1 , (µ∗ )T x∗ = 0 sao cho
−c + AT λ∗ + µ∗ ∈ ∂Q(x∗ ),

(2.2.7)

ở đây ∂Q(x) ký hiệu cho đạo hàm riêng của hàm Q(x).
Chứng minh. Như chúng ta đã biết trong [2], bài toán
min{J(x) := cT x + Q(x) : Ax = b, x ≥ 0}

N (K2 , x) = v ∈ Rn1 : v T y ≤ 0, ∀y sao cho x + y ∈ K2 ,
trong đó N (K2 , x) là nón chuẩn (nón pháp tuyến - xem [2], mục 1.1 chương
1) của tập phương án K2 giai đoạn hai.
Chứng minh. Tính toán trực tiếp ∂Q(x) hàm lồi ngẫu nhiên thể hiện
qua kỳ vọng toán học người ta nhận được
∂Q(x) = Eξ ∂Q x, ξ(ω) + rec ∂Q(x)
ở đây rec ∂Q(x) là nón suy thoái của vi phân, tức là
rec ∂Q(x) = v ∈ Rn1 : u + λv ∈ ∂Q(x), λ ≥ 0, u ∈ ∂Q(x) .
Chúng ta có thể viết lại như sau:
rec ∂Q(x) = v ∈ Rn1 : y T (u + λv) + Q(x) ≤ Q(x + y), λ ≥ 0, y ∈ Rn1 .

Trích đoạn Các giả thiết và định nghĩa

---