Một số kiến thức cơ bản về lý thuyết xác suất
Không gian xác suất tổng quát
1.1.1.1 Đại số và σ-đại số Giả sử Ω là một tập tùy ý khác rỗng Ký hiệuP(Ω) là tập hợp gồm tất cả các tập con của Ω Khi đó, lớp A ⊆ P(Ω) được gọi là một đại số nếu:
Lớp F ⊆ P(Ω) được gọi là σ-đại số nếu nó là đại số và thỏa mãn thêm điều kiện:
Nhận xét Trong điều kiện (i) thì Ω ∈ A có thể thay thế bởi ∅ ∈ A.
Trong điều kiện (ii) thì A ∈ A ⇒ A = Ω\A ∈ A có thể thay thế bởi
Trong điều kiện (iii) thì A∪B có thể thay thế bởi A∩B.
Trong điều kiện (iv) thì S∞ n=1An có thể thay thế bởi T∞ n=1An.
1.1.1.2 Độ đo xác suất Giả sử A ⊂ P(Ω) là một đại số nào đó Hàm tập hợp P(ã) xỏc định trờn A được gọi là độ đo xỏc suất hữu hạn cộng tớnh (hay cộng tính hữu hạn) nếu:
Hàm tập hợp P(ã) xỏc định trờn đại số A được gọi là độ đo xỏc suất σ-cộng tính nếu nó thỏa mãn hai điều kiện (i) và (ii) và thỏa mãn:
Tính chất Từ điều kiện (iii), bằng quy nạp ta có thể suy ra rằng
Ai ∈ A, i= 1,2, , n và Ai ∩Aj = ∅ với mọi i 6= j thì:
Cũng từ điều kiện (ii) và (iii) suy ra P(A) = 1−P(A).
Tính chất σ-cộng tính của độ đo xác suất dẫn đến tính chất hữu hạn cộng tính, nhưng ngược lại không phải lúc nào cũng đúng Tuy nhiên, có một phát biểu khẳng định điều kiện cần và đủ để một độ đo xác suất hữu hạn cộng tính đạt được tính chất σ-cộng tính.
”Giả sử P là một độ đo xác suất hữu hạn cộng tính trên đại số A Khi đó, bốn điều kiện sau đây là tương đương:
1) P là cộng tính đếm được (σ-cộng tính);
2) P liên tục trên, tức là nếu A n ∈ A, n = 1,2, là dãy không giảm (A n ⊆ A n+1 ) và lim n→∞ A n = S∞ n=1A n ∈ A thì:
3)Pliên tục dưới, tức là nếuA n ∈ A, n = 1,2, là dãy giảm (A n ⊆ A n−1 ) và lim n→∞ A n = T∞ n=1A n ∈ A thì:
4) P liên tục tại không, tức là nếu A n ∈ A, A n ⊇ A n+1 , n = 1,2, và
Từ ∅∪∅ = ∅ và từ điều kiện (ii) và (iii) ta suy ra:
Suy từ A ⊆ B ⇒ B = A ∪ (B \ A), A ∩ (B \ A) = ∅ ⇒ P(B) P(A) +P(B \A) nên ta có tính chất đơn điệu của P:
Suy từ tính chất trên và A ⊆ Ω nên ta có:
Suy từ A∪B = A∪(B\A) và P(B \A) = P(B)−P(A∩B) nên ta có:
P(A∪B) = P(A) +P(B)−P(A∩B) (1.16) Tổng quát, bằng phương pháp quy nạp toán học ta chứng minh được:
Từ tính chất trên suy ra:
Suy từ đẳng thức S∞ n=1A n = S∞ n=1B n và từ điều kiện (iv), trong đó
Bn = An \Sn−1 k=0Ak, A0 = ∅, ta có:
Nếu A n ⊇ B n , n = 1,2, thì từ các tính chất trên và từ hệ thức (S∞ n=1A n )\(S∞ n=1B n ) ⊆S∞ n=1(A n \B n ) ta sẽ có:
1.1.1.3 Không gian đo và không gian xác suất Cặp (Ω,F), trong đó
Ω 6= ∅ bất kỳ, còn F là σ-đại số các tập con của Ω được gọi là một không gian đo.
Bộ ba (Ω, F, P) được định nghĩa trong lý thuyết xác suất, trong đó Ω là tập hợp các phần tử ω, F là σ-đại số của các tập con thuộc Ω, và P là độ đo xác suất σ-cộng tính, tạo thành không gian xác suất.
Tập Ω đại diện cho không gian chứa các biến cố sơ cấp, trong khi tập A thuộc F được xem là các biến cố Xác suất của biến cố A được ký hiệu là P(A), và P được định nghĩa là xác suất trên tập F.
Biến ngẫu nhiên và hàm phân phối
Giả sử (Ω,F) là không gian đo đã cho, R = [−∞,+∞].
1.1.2.1 Biến ngẫu nhiên Hàm thực X = X(ω) xác định trên Ω, lấy giá trị trên R gọi là hàm F-đo được (hoặc biến ngẫu nhiên suy rộng) nếu:
{ω : X(ω) ∈ B}= X −1 (B) ∈ F, (1.21) với mọi B ∈ B(R), trong đó B(R) là σ-đại số các tập Borel của R.
X : Ω → R= (−∞,+∞), (1.22) thì ta nói X là biến ngẫu nhiên.
1.1.2.2 Tính chất của biến ngẫu nhiên Giả sử X : Ω → R Khi đó, các mệnh đề sau là tương đương:
1.1.2.3 σ-đại số sinh bởi biến ngẫu nhiên Giả sử (Ω,F,P) là không gian xác suất Khi đó, nếu X là biến ngẫu nhiên thì họ:
F(X) = {X −1 (B) : B ∈ B(R)} (1.27) tạo thành một σ-đại số con của σ-đại số F Đây là σ-đại số nhỏ nhất mà biến ngẫu nhiên X có thể đo được, và được gọi là σ-đại số sinh bởi biến ngẫu nhiên X.
1.1.2.4 Hàm Borel Hàm ϕ : (R n ,B(R n )) → (R,B(R)) được gọi là hàm Borel nếu nó là B(R n )-đo được, nghĩa là: ϕ −1 (B) ∈ B(R n ) với mỗi B ∈ B(R) (1.28)
Tính chất Giả sử X 1 , X 2 , , X n là các biến ngẫu nhiên cùng xác định trên (Ω,F) và ϕ(t 1 , t 2 , , t n ) là hàm Borel giá trị thực Khi đó,
Y = ϕ(X1, X2, , Xn) cũng là biến ngẫu nhiên.
Từ đó suy ra rằng nếu X, Y là các biến ngẫu nhiên và a ∈ R thì aX, X ±Y, X.Y,max(X, Y),min(X, Y),
Y (Y 6= 0) (1.29) đều là các biến ngẫu nhiên.
Giả sử (Xn, n ≥ 1) là dãy các biến ngẫu nhiên và sup n Xn, infnXn hữu hạn trên Ω Khi đó ta có: sup n
X n , lim inf n X n , (1.30) là các biến ngẫu nhiên Đặc biệt, nếu limn→∞Xn = X, X hữu hạn thì X cũng là biến ngẫu nhiên.
1.1.2.5 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 = (−∞,+∞). Khi đó, hàm số
F X (x) =P[X < x], x ∈ R, (1.31) được gọi là hàm phân phối của biến ngẫu nhiên X.
Nhận xét Hàm phân phối F(x) = F X (x) có một số tính chất sau:
Tính đơn điệu, tức là: x ≤ y ⇒F(x) ≤ F(y).
Tính liên tục trái, có giới hạn phải tại mọi điểm.
1.1.2.6 Tính độc lập Giả sử (Ω,F,P) là một không gian xác suất Khi đó, họ hữu hạn {F i , i∈ I} các σ-đại số con của F được gọi là độc lập nếu:
Họ vô hạn {F i , i ∈ I} các σ-đại số con của F được gọi là độc lập nếu mọi họ con hữu hạn của nó là độc lập.
Họ các biến ngẫu nhiên {X i , i ∈ I} được gọi là độc lập nếu họ các σ-đại số sinh bởi chúng {F(X i ), i∈ I} là độc lập.
Họ các biến cố {A i , i ∈ I} ⊆ F được gọi là độc lập nếu họ các biến ngẫu nhiên {I A i, i ∈ I} là độc lập.
Các số đặc trưng của biến ngẫu nhiên
1.1.3.1 Kỳ vọng toán Giả sử X : (Ω,F,P) → (R,B(R)) là biến ngẫu nhiên Khi đó, tích phân Lebesgue của X theo độ đo P (nếu tồn tại) được gọi là kỳ vọng của X và ký hiệu là EX Vậy,
Lược đồ xây dựng kỳ vọng Lược đồ xây dựng kỳ vọng chính là lược đồ xây dựng tích phân Lebesgue.
Nếu X là biến ngẫu nhiên đơn giản:
Nếu X là biến ngẫu nhiên không âm thì X là giới hạn của một dãy tăng các biến ngẫu nhiên đơn giản (X n , n ≥ 1), chẳng hạn như:
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 tồn tại) (1.38)
1.1.3.2 Phương sai và hiệp phương sai Giả sử X, Y là các biến ngẫu nhiên Khi đó, số
Hiệp phương sai giữa hai biến ngẫu nhiên X và Y, ký hiệu là Cov(X, Y), được định nghĩa bởi công thức Cov(X, Y) := E(X − EX)(Y − EY) (nếu tồn tại) Đây là một khái niệm quan trọng trong thống kê, còn được gọi là Covarian hoặc Moment tương quan Đặc biệt, khi X và Y là giống nhau, hiệp phương sai sẽ cho thấy mối quan hệ nội tại của chúng.
(hay còn kí hiệu làV ar(X)) được gọi là phương sai của biến ngẫu nhiênX.
ChoX 1 , X 2 , , X n là dãy các biến ngẫu nhiên Với mỗi cặp1≤ i, j ≤n, ta ký hiệu λ i,j = Cov(X i , X j ) Khi đó, ma trận Σ = [λ i,j ]
, (1.41) được gọi là ma trận Covarian của dãy các biến ngẫu nhiên X 1 , X 2 , , X n
Rõ ràng ma trận Covarian là một ma trận đối xứng, xác định dương.
1.1.3.3 Một số tính chất Nếu X ≥ 0 thì EX ≥ 0.
Nếu tồn tại EX thì với mọi C ∈ R ta có E(CX) = CEX.
Nếu tồn tại EX,EY thì E(X ±Y) = EX ±EY.
P ix i p i nếu X rời rạc nhận các giá trị x 1 , x 2 , với P(X = x i ) =p i ,
−∞ xp(x)dx nếu X liên tục có hàm mật độ p(x).
Tổng quát, nếu f : R→ R là hàm đo được và Y = f(X) thì:
P if(xi)pi nếu X rời rạc nhận các giá trị x1, x2, với P(X = x i ) = p i ,
−∞ f(x)p(x)dx nếu X liên tục có hàm mật độ p(x).
(Định lý P Levi về hội tụ đơn điệu) Nếu X n ↑ X (tương ứng X n ↓ X) và tồn tại n để EX n − < ∞ (tương ứng EX n + < ∞) thì EX n ↑ EX (tương ứng EX n ↓ EX).
(Bổ đề Fatou) Nếu Xn ≥ Y với mọi n ≥ 1 và EY > −∞ thì:
ElimXn ≤ limEXn (1.42) Nếu X n ≤ Y với mọi n ≥1 và EY < ∞ thì: limEX n ≤ ElimX n (1.43) Nếu |X n | ≤Y với mọi n ≥1 và EY < ∞ thì:
(Định lý Lebesgue về hội tụ bị chặn) Nếu |X n | ≤ Y với mọi n ≥ 1,
EY < ∞ và X n →X thì X khả tích, E|X n −X| →0 và EX n →EX (khi n→ ∞).
Nếu ϕ là hàm lồi, X và ϕ(X) khả tích thì E(ϕ(X)) ≥ϕ(EX).
Nếu X, Y là hai biến ngẫu nhiên độc lập thì E(XY) =EX.EY.
Tổng quát, nếu (Xn, n ≥ 1) là dãy các đại lượng ngẫu nhiên độc lập thì với mọi số tự nhiên n > 1 ta đều có:
E(X 1 X 2 X n ) = EX 1 EX 2 EX n (1.45) Cov(X, Y) = E(XY)−EX.EY Đặc biệt là DX = EX 2 −(EX) 2
DX ≥ 0 và DX = 0 khi và chỉ khi X = EX h.c.c.
D(CX) =C 2 DX, với X là biến ngẫu nhiên và C ∈ R.
Nếu X, Y là hai biến ngẫu nhiên độc lập thì D(X ±Y) =DX + DY. Tổng quát, nếu (X i ) i=1,n là họ các biến ngẫu nhiên độc lập thì:
1.1.3.4 Bất đẳng thức Markov Giả sử(Ω,F,P) là không gian xác suất,
X là biến ngẫu nhiên Khi đó, với mỗi số thực ε > 0 thì ta có:
1.1.3.5 Bổ đề Borel-Cantelli Giả sử (An, n ≥ 1) là dãy các biến cố bất kỳ Khi đó, a) Nếu
P(A n ) = ∞, (1.50) và (An, n ≥1) độc lập thì:
An) = 1, (1.51) trong đó: lim sup n
Bài toán quy hoạch ngẫu nhiên hai giai đoạn
Một bài toán ngẫu nhiên hai giai đoạn cổ điển với sự hiệu chỉnh cố định có thể biểu diễn như sau (xem [7]): min{c T x+ E(Q(x,˜z))} với điều kiện:
T(z)x+Ww = h(z), wi ≥ 0,∀i ∈ I ⊆ {1,2, , n2}, (1.54) với c, f và b tương ứng là những vectơ trong R n 1 ,R n 2 và R m 1
Trong công thức này, ˜z ∈ R N đại diện cho vectơ các yếu tố ngẫu nhiên, thống nhất tất cả các yếu tố trong mô hình ngẫu nhiên Ký hiệu E được sử dụng để biểu thị kỳ vọng kết hợp với biến ngẫu nhiên ˜z Chúng ta xem xét các hàm T(˜z) và h(˜z) được xác định theo cách cụ thể.
Ma trận A và W tương ứng là ma trận trong R m 1 xn 1 và R m 2 xn 2
Trong giai đoạn thứ hai, giá trị Q(x,z) sẽ là +∞ nếu tập phương án của bài toán (1.54) là rỗng, và sẽ là −∞ nếu hàm mục tiêu của bài toán (1.54) không bị chặn dưới.
Mô hình ngẫu nhiên mô tả chuỗi sự kiện với hai giai đoạn quyết định Giai đoạn đầu tiên, vectơ x, phải được xác định trước khi giá trị thực tế của ˜z được thực hiện Sau khi quyết định x được thiết lập và các yếu tố ngẫu nhiên xảy ra, giai đoạn thứ hai, vectơ w, sẽ được hình thành như một quyết định hiệu chỉnh.
Với những điều kiện rất tổng quát, bài toán (1.53) là tương đương với:
Z STOC = min{c T x+E(f T w(˜z))} với điều kiện:
Y là không gian các ánh xạ từ R^N tới R^n^2, được đo lường theo không gian xác suất, trong đó vectơ ngẫu nhiên ˜z được xác định Hàm w(ã) đại diện cho vectơ của giai đoạn thứ hai, điều chỉnh cho sự thực hiện của ˜z.
Trong nhiều bài toán, chúng ta giả định rằng ma trận W không gặp vấn đề về điều kiện bất định, đây là nguyên tắc chung áp dụng cho các bài toán có hiệu chỉnh cố định.
Trong phần tiếp theo, chúng tôi không cung cấp cái nhìn đầy đủ về thông tin phân phối của các yếu tố ngẫu nhiên Chúng tôi giả định rằng các yếu tố ngẫu nhiên {˜z j } j=1,N là những biến ngẫu nhiên có trung bình bằng không và hiệp phương sai Σ, với giá trị ˜z nằm trong khoảng W = [−z ¯,¯z] Một số thành phần z ¯ và ¯z có thể vô hạn, cho thấy các giá trị không bị chặn.
Một số khái niệm về sự hiệu chỉnh đầy đủ và sự hiệu chỉnh nửa đầy đủ
Sự hiệu chỉnh đầy đủ
1.3.1.1 Quan hệ hiệu chỉnh đầy đủ Bài toán quy hoạch ngẫu nhiên (1.53) được gọi là có quan hệ hiệu chỉnh đầy đủ nếu với bất kỳ phương án x ∈ {x|Ax = b,x ≥ 0} thì Q(x,˜z) < +∞ với xác suất 1.
Trong các bài toán có quan hệ hiệu chỉnh đầy đủ, giai đoạn hai thường sẽ chấp nhận bất kỳ lựa chọn nào cho tính chấp nhận được của vectơ quyết định ở giai đoạn một x.
Việc nhận diện các điều kiện về quan hệ hiệu chỉnh đầy đủ không phải là điều dễ dàng Vì vậy, chúng ta sẽ xem xét một trường hợp tổng quát hơn, đó là sự hiệu chỉnh đầy đủ, được định nghĩa thông qua ma trận hiệu chỉnh W, mà chúng ta gọi là ma trận hiệu chỉnh đầy đủ.
1.3.1.2 Ma trận hiệu chỉnh đầy đủ Ma trận W cấp m ×n được gọi là ma trận hiệu chỉnh đầy đủ, nếu với mỗi vectơ cột t cấp m×1 đều tồn tại vectơ cột w = [w 1 w 2 w n ] T cấp n×1 sao cho w j ≥ 0,∀j = 1, n và
Trong bài viết này, chúng ta xem xét các vectơ cột W1, W2, , Wn của ma trận W, mà ma trận này được định nghĩa là ma trận hiệu chỉnh đầy đủ Dựa trên Định nghĩa 1.3.1.2, ta nhận thấy rằng hệ các vectơ cột {W1, W2, , Wn} là phụ thuộc tuyến tính, từ đó suy ra rằng hạng của ma trận W, ký hiệu là rank(W), sẽ không vượt quá giá trị nhỏ hơn giữa m và n-1, tức là rank(W) ≤ min{m, n−1}.
Định nghĩa sự hiệu chỉnh đầy đủ chỉ phụ thuộc vào cấu trúc của ma trận W, điều này giúp việc kiểm tra trở nên dễ dàng Ngoài ra, nhiều bài toán quy hoạch ngẫu nhiên cũng liên quan đến sự hiệu chỉnh đầy đủ.
Nghiên cứu các tính chất về sự hiệu chỉnh đầy đủ và sự hiệu chỉnh nửa đầy đủ, ta cần tới Mệnh đề sau:
1.3.1.3 Mệnh đề Trong không gian vectơ k-chiều R k , một hệ các vectơ {−→v 1 ,−→v 2 , ,−→v s } có hạng bé hơn k thì luôn có thể bổ sung một vectơ −−→v s+1 để rank{−→v 1 ,−→v 2 , ,−−→v s+1 } = rank{−→v 1 ,−→v 2 , ,−→v s }+ 1, (1.57) nghĩa là vectơ −−→v s+1 không thuộc không gian vectơ con h−→v 1 ,−→v 2 , ,−→v s i sinh bởi hệ vectơ {−→v 1 ,−→v 2 , ,−→v s }.
Sự hiệu chỉnh nửa đầy đủ
1.3.2.1 Bài toán xuất phát Để cải tiến quy tắc quyết định tuyến tính, đầu tiên chúng tôi khảo sát tỉ mỉ cấu trúc ma trận hiệu chỉnh W bằng việc xem xét bài toán tối ưu tuyến tính sau đây: f i = min{f T p} với điều kiện:
(1.58) với mỗi i ∈ I Nếu bài toán tối ưu tương ứng là không chấp nhận được, chúng ta có f i = ∞ Để thuận tiện, chúng ta định nghĩa những tập hợp sau đây:
I1 , {f i < ∞ | i ∈ I}, I2 , I\I 1 (1.59) Khi f i hữu hạn, chúng ta ký hiệu ¯p i là phương án tối ưu tương ứng. Hơn nữa, nếu bài toán gốc (1.55) bị chặn dưới, chúng ta có f i ≥0.
1.3.2.2 Ma trận hiệu chỉnh nửa đầy đủ Tập hợp tất cả các cột i ∈ I 1 của ma trận hiệu chỉnh W cho ta một ma trận W s Chúng ta gọi W s là một ma trận hiệu chỉnh nửa đầy đủ.
Bài toán (1.55) mở rộng hệ thống hiệu chỉnh cố định từ công thức tối ưu ngẫu nhiên cổ điển (1.53), cho thấy rằng bài toán tối ưu ngẫu nhiên hai giai đoạn với quan hệ hiệu chỉnh đầy đủ có thể được xấp xỉ tốt bằng những xấp xỉ mẫu ngẫu nhiên Tuy nhiên, trong trường hợp thiếu quan hệ hiệu chỉnh đầy đủ, các phương án từ xấp xỉ mẫu có thể không có ý nghĩa Ngay cả khi bài toán gốc không thể chấp nhận, giá trị hàm mục tiêu từ xấp xỉ mẫu vẫn có thể bị giới hạn Điều này khuyến khích việc nghiên cứu các bài toán quy hoạch ngẫu nhiên với các quy tắc quyết định, mở ra khả năng cho những bài toán hiệu chỉnh tổng quát hơn và các mô hình nhiều giai đoạn.
CÁC PHƯƠNG PHÁP XẤP XỈ GIẢI BÀI TOÁN QUY
Phép xấp xỉ bởi những quy tắc quyết định
Dyer và Stougie (2006) đã chứng minh rằng các bài toán quy hoạch ngẫu nhiên hai giai đoạn là NP-khó và các bài toán quy hoạch ngẫu nhiên nhiều giai đoạn cố định là PSPACE-khó, dưới giả thiết rằng các tham số ngẫu nhiên có phân phối độc lập Do số lượng trường hợp có thể xảy ra rất lớn, phương pháp mẫu Monte Carlo trở thành một công cụ xấp xỉ quan trọng cho các bài toán tối ưu ngẫu nhiên Tuy nhiên, hiệu quả của phương pháp này chỉ được chứng minh trong lý thuyết, với yêu cầu xấp xỉ độ chính xác trung bình tăng theo hàm mũ với số giai đoạn Một điểm quan trọng khác là để quản lý mẫu ngẫu nhiên, cần xác định chính xác các phân phối xác suất của tất cả các tham số ngẫu nhiên, nhưng việc này thường không khả thi trong thực tế tính toán Do đó, một xấp xỉ hữu ích cho mô hình là hạn chế các quyết định điều chỉnh theo các quy tắc quyết định lý thuyết đã được đề xuất bởi Ben-Tal và cộng sự.
Năm 2005, các quy tắc quyết định tuyến tính đã được áp dụng để cải thiện sự tương ứng mạnh Đến năm 2007, Chen và các cộng sự đã áp dụng những quy tắc này cùng với tính toán máy tính, mang lại những kết quả đầy triển vọng cho các quy hoạch ngẫu nhiên với các ràng buộc ngẫu nhiên.
Trong bài viết này, chúng tôi sẽ xem xét các biến hiệu chỉnh nửa đầy đủ và đề xuất những quy tắc quyết định tổng quát để giải quyết các bài toán liên quan Đầu tiên, chúng tôi kiểm tra các quy tắc quyết định tuyến tính và chỉ ra những hạn chế của chúng Tiếp theo, chúng tôi giới thiệu các quy tắc quyết định tuyến tính lệch và quy tắc quyết định tuyến tính cô lập, mở rộng khả năng của các quy tắc quyết định tuyến tính Cuối cùng, chúng tôi sẽ trình bày sự mở rộng cho xấp xỉ trong các bài toán quy hoạch ngẫu nhiên nhiều giai đoạn.
Quy tắc quyết định tuyến tính
Khái niệm
Chỳng ta ký hiệu L là khụng gian cỏc hàm tuyến tớnh Với w(ã) ∈ L ⊆ Y dẫn đến tồn tại một tập hợp các vectơ w 0 , ,w N sao cho: w(˜z) = w 0 +
Khi đó, chúng ta có thể xấp xỉ bài toán ngẫu nhiên (1.55) như sau:
Z LDR = min{c T x+f T w 0 } với điều kiện:
Quy tắc quyết định xác định bởi công thức (2.1) được gọi là quy tắc quyết định tuyến tính.
Tính chất
2.2.2.1 Định lý Với cùng điều kiện khách quan cho các bài toán quy hoạch ngẫu nhiên (1.55) và (2.2); ta luôn có:
Dưới cùng một điều kiện khách quan, mọi phương án chấp nhận được của bài toán (2.2) cũng đều có thể chấp nhận được trong bài toán (1.55), do đó, ta có thể khẳng định rằng Z STOC ≤ Z LDR.
2.2.2.2 Bản chất của bài toán quy hoạch ngẫu nhiên với quy tắc quyết định tuyến tính Với W = [−z ¯,¯z], ràng buộc nửa vô hạn: w i (z) ≥ 0,∀z ∈ W, (2.4) là tương đương với: w 0 i ≥
(z j sj +zjtj), (2.5) với s,t ≥ 0 thoả mãn s j −t j = w i j , j = 1, , N Do đó, bài toán (2.2) về bản chất là một bài toán tối ưu tuyến tính.
Tính không khả thi của những quy tắc quyết định tuyến tính
Mặc dù các quy tắc quyết định tuyến tính đã được áp dụng thành công trong nhiều lĩnh vực, nhưng những kết quả nghiên cứu của Ben-Tal và cộng sự (2005) cùng với Chen và cộng sự (2007) đã chứng minh tính hiệu quả của chúng trong các ứng dụng đa dạng.
Tuy nhiên, có nhiều trường hợp mà quy tắc quyết định tuyến tính không còn phù hợp cho bài toán tối ưu ngẫu nhiên, ngay cả khi đã được điều chỉnh đầy đủ Chẳng hạn, khi giá của ˜z là W = (−∞,∞), các ràng buộc không âm sẽ được xác định bởi w(˜z) = w 0 +.
Trong bài viết này, chúng ta xem xét một mô hình tối ưu ngẫu nhiên với điều kiện E(|b(˜z)|) và quy tắc quyết định dẫn đến việc w k = 0 cho mọi k trong tập {1, , N} Điều này cho thấy tính độc lập của các yếu tố ngẫu nhiên và dẫn đến một ví dụ không khả thi ngay cả khi đã thực hiện hiệu chỉnh đầy đủ Cụ thể, mô hình tối ưu xác định rằng min{E(w 1 (˜z) +w 2 (˜z)) | w 1 (˜z)−w 2 (˜z) =b(˜z), w 1 (˜z) ≥ 0, w 2 (˜z) ≥ 0} là một hiệu chỉnh đơn, và giả thiết rằng ˜z có giá trị vô hạn, chúng ta kết luận rằng w 1 (˜z) = w 0 1 và w 2 (˜z) = w 2 0, dẫn đến việc không thể thỏa mãn ràng buộc đẳng thức.
Chúng tôi nhằm cải tiến các quy tắc quyết định tuyến tính cho các biến có đặc tính hiệu chỉnh nửa đầy đủ Điều kiện hiệu chỉnh nửa đầy đủ vẫn có giá trị ngay cả khi có vi phạm ràng buộc do w(˜z), cho phép chúng ta tìm kiếm phương án chấp nhận được bằng cách gán cho nó một giá trị hữu hạn.
Quy tắc quyết định tuyến tính lệch
Khái niệm
Xét bất kỳ quy tắc quyết định r(˜z) thoả mãn:
T(˜z)x+ Wr(˜z) =h(˜z), r i (˜z) ≥0 ∀i ∈ I 2 , (2.10) và không nhất thiết không âm cho những biến hiệu chỉnh nửa đầy đủ r j (˜z), j ∈ I 1
Xuất phát từ quy tắc quyết định r(˜z) ở trên, chúng ta định nghĩa w(˜z) như sau: w(˜z) =r(˜z) +X i∈I 1
(r i (˜z) − )¯p i , (2.11) với một đại lượng vô hướng đã cho v, v − = max(0,−v).
Dễ dàng kiểm tra được rằng: w i (˜z) ≥ 0, ∀i ∈ I; Ww(˜z) = Wr(˜z) (2.12)
Với bất kỳ quyết định giai đoạn thứ nhất x nào, nếu tồn tại một quy tắc quyết định giai đoạn hai r(˜z) thỏa mãn điều kiện (2.10), chúng ta có thể xác định một quy tắc quyết định chấp nhận được w(˜z) theo công thức (2.11), được gọi là quy tắc quyết định tuyến tính lệch Cần lưu ý rằng tính khả thi của bài toán (2.10) phụ thuộc vào phương án giai đoạn thứ nhất x.
Bài toán quy hoạch ngẫu nhiên với quy tắc quyết định tuyến tính lệch
Từ công thức (2.11), chúng ta có: f T w(˜z) =f T r(˜z) +X i∈I 1 f¯ i E[r i (˜z) − ] (2.13)
Sử dụng quy tắc quyết định tuyến tính lệch w(ã) xuất phát từ quy tắc quyết định tuyến tính r(ã), chúng ta có thể xấp xỉ bài toán (1.55) một cách hiệu quả.
Z DLDR = min{c T x+f T r 0 +X i∈I 1 f¯ i E[r i (˜z) − ]} với điều kiện:
Chú ý là trong công thức thu được ở bài toán trên, chúng ta không thực sự cần ¯p i định nghĩa ở mục 1.3.2.1 Thực ra, chúng ta thật sự cần ¯f i , i ∈ I.
Tính chất
2.3.3.1 Định lý Nếu W là một ma trận hiệu chỉnh đầy đủ, chúng ta có
I2 = ∅ và với bất kỳ x, tồn tại một quy tắc quyết định tuyến tớnh r(ã) ∈ L thoả mãn:
T(˜z)x+Wr(˜z) =h(˜z) (2.15) Chứng minh Ta có: r(˜z) =r 0 +
Từ giả thiết của sự hiệu chỉnh đầy đủ, tồn tại r 0 ,r 1 , ,r N sao cho:
T k x+Wr k = h k , ∀k ∈ {0, , N} (2.17) Điều này dẫn đến kết quả thu được.
2.3.3.2 Định lý Với cùng điều kiện khách quan cho các bài toán quy hoạch ngẫu nhiên (1.55), (2.2) và (2.14) thì ta luôn có:
Chứng minh Bởi vì bất kỳ phương án chấp nhận được (x,w(˜z)) của bài toán (2.14) thì quy tắc quyết định: w(˜z) =r(˜z) +X i∈I 1
(r i (˜z) − )¯p i , (2.19) là chấp nhận được cho bài toán (1.55) nên với cùng điều kiện khách quan chúng ta có Z STOC ≤ Z DLDR
Hơn nữa, với phương án chấp nhận được bất kỳ (x,w(˜z)) của bài toán (2.2), chúng ta thấy rằng:
Từ đẳng thức r(˜z) = w(˜z) và điều kiện khách quan tương ứng, chúng ta có thể xác định một phương án chấp nhận được cho bài toán (2.14) Do đó, ta có thể kết luận rằng Z STOC ≤ Z DLDR ≤ Z LDR.
Chúng ta nhận thấy rằng những quy tắc quyết định tuyến tính lệch luôn chấp nhận được trong bất kỳ bài toán quy hoạch ngẫu nhiên với hiệu chỉnh đầy đủ Tuy nhiên, khái niệm "hiệu chỉnh nửa đầy đủ" được đưa ra vì nó dễ kiểm tra và vẫn cho phép những quy tắc quyết định tuyến tính lệch được chấp nhận ngay cả khi thiếu hiệu chỉnh đầy đủ, miễn là bài toán chứa ma trận phụ hợp Mặc dù vậy, việc giải quyết bài toán liên quan đến đại lượng E[ ¯f i w i (˜z) − ] trong hàm mục tiêu vẫn gặp khó khăn do tính không tuyến tính Để khắc phục, chúng ta sẽ xấp xỉ bài toán bằng kỹ thuật tối ưu mạnh, dẫn đến một dạng quy hoạch SOC, có khả năng mang lại hiệu quả trong cả lý thuyết và thực hành tính toán.
Tính bị chặn của hàm mục tiêu
2.3.4.1 Tính bị chặn Cho một biến ngẫu nhiên r˜với giá trị trung bình à và độ lệch tiờu chuẩn σ, khi đú:
Do đó, nếu giả thiết rằng y(˜z) = y0 + y T ˜z ∈ L với y = (y1, , yN), chúng ta có:
, (2.22) với Σ là ma trận hiệp phương sai của ˜z.
Tính bị chặn ở trên không chỉ ảnh hưởng đến hiệu quả của giá trị phân phối mà còn có thể hạn chế tính xấp xỉ Cụ thể, nếu y(˜z) ≥ 0, điều này dẫn đến E(y(˜z) − ) = 0 một cách hiển nhiên Ngược lại, nếu y(˜z) ≤ 0, chúng ta có E(y(˜z) − ) = −y 0 Trong các trường hợp này, tính bị chặn thể hiện sự yếu kém.
Từ đó, chúng tôi đưa ra tính bị chặn chặt sau đây để giải quyết những tình huống này trong khi vẫn giữ ưu điểm của quy hoạch SOC.
2.3.4.2 Định lý Cho ˜z ∈ R N là một vectơ của những biến ngẫu nhiên có trung bình 0 với ma trận hiệp phương sai Σ và nhận giá trị trong
Chứng minh (a) Bởi vì −z ¯≤˜z ≤¯z, chúng ta nhận thấy rằng:
T(tưv) +¯z T (sưu)) 2 + k Σ 1 2 (ưy+tưs+uưv) k 2 2
T(tưv) +¯z T (sưu)) 2 + k Σ 1 2 (ưy+tưs+uưv) k 2 2
, (2.31) với đẳng thức (2.28) và (2.29) suy ra từ x = x + −x − Bất đẳng thức (2.30) là do tính bị chặn (2.21).
(b) Chú ý rằng với s,t,u,v = 0, chúng ta có:
(c) Chúng ta giả thiết rằng y0 + y T z ≤ 0,∀z ∈ W Tiếp theo, cho s = t = 0, u k = (y k ) + , v k = (−y k ) + với k = 1, , N và z k ∗ z¯k nếu yk > 0,
−z k với những trường hợp còn lại.
Vì z ∗ ∈ W, chúng ta có y0+y T z ∗ ≤0 Hơn nữa, dễ dàng kiểm tra được rằng: y = u−v và y 0 +u T ¯z+ v T z ¯= y 0 +y T z ∗ ≤0.
Tương tự, nếu xảy ra trường hợp y0+y T z ≥ 0,∀z ∈ W thì chúng ta cho v = u = 0, s k = (−y k ) + , t k = (y k ) + với k = 1, , N và z k ∗ z¯ k nếu y k < 0,
−z k với những trường hợp còn lại.
Vì z ∗ ∈ W nên chúng ta có y0 + y T z ∗ ≥ 0 Hơn nữa, dễ dàng kiểm tra được rằng: y = t−s và y 0 −s T ¯z−t T z ¯= y 0 +y T z ∗ ≥0.
Từ đó, chúng ta có:
Phép xấp xỉ nón bậc hai với một quy tắc quyết định tuyến tính lệch
2.3.5.1 Bài toán tối ưu SOC Tổng hợp những kết quả trước, chúng ta đưa ra sự xấp xỉ cho bài toán (1.55) như sau:
Z¯ DLDR = min{c T x+f T r 0 + X i∈I 1 f¯ i g i } với điều kiện:
Rõ ràng, chúng ta có bài toán tối ưu SOC sau đây:
Z¯DLDR = min{c T x+f T r 0 + X i∈I 1 f¯igi} với điều kiện:
Hơn nữa, chúng ta có thể chứng tỏ được rằng quy tắc quyết định tuyến tính lệch cải tiến hơn quy tắc quyết định tuyến tính.
2.3.5.2 Định lý Quy tắc quyết định tuyến tính lệch cho một giá trị hàm mục tiêu của bài toán tối ưu ngẫu nhiên là bé hơn đối với quy tắc quyết định tuyến tính, nghĩa là:
Chứng minh Cho bất kỳ phương án chấp nhận được (x,w(˜z)) của bài toán (2.2), chúng ta nhận thấy rằng với mọi i ∈ I thì: w i (z) ≥ 0, ∀z ∈ W (2.38)
Từ đó và từ Định lý 2.3.4.2(mục c), chúng ta có: h(w i 0 ,(w 1 i , , w N i )) = 0 (2.39)
Từ đẳng thức r(˜z) = w(˜z), chúng ta có một phương án khả thi cho bài toán (2.35) với giá trị hàm mục tiêu thấp hơn so với bài toán (2.2) Do đó, ta kết luận rằng ¯ZDLDR ≤ ZLDR.
Quy tắc quyết định tuyến tính cô lập
Khái niệm
Một hạn chế của các quy tắc quyết định tuyến tính lệch là chúng chỉ áp dụng cho những quyết định hiệu chỉnh nửa đầy đủ Trong phần này, chúng tôi giới thiệu một cải tiến của các quy tắc này, cho phép áp dụng cho các bài toán hiệu chỉnh tổng quát Đầu tiên, chúng tôi định nghĩa các yếu tố ngẫu nhiên cô lập thông qua việc phân tích từng yếu tố ngẫu nhiên, cụ thể là z j 1, z˜ j + −zˆ j và z j 2, −˜z j − + ˆz j, với zˆ j = E(˜z j + ).
Vì những yếu tố ngẫu nhiên có các giá trị trung bình bằng không nên chúng ta có:
E(˜z j + ) = E(˜z j − ), (2.41) và từ đó, ta có:
Ta ký hiệu S là không gian các hàm quyết định tuyến tính cô lập Từ w(ã) ∈ S ⊆ Y suy ra rằng tồn tại một tập cỏc vectơ w 0 ,w 11 , ,w 1N và w 21 , ,w 2N sao cho: w(˜z 1 ,˜z 2 ) =w 0 +
(w 1j z˜ j 1 +w 2j z˜ 2 j ), (2.43) ta gọi nó là quy tắc quyết định tuyến tính cô lập.
Khi w 1j = w 2j, quy tắc quyết định w(˜z 1 ,˜z 2) trở thành một hàm tuyến tính của ˜z, dẫn đến L ⊆ S Quy tắc quyết định tuyến tính cô lập thực chất là sự kết hợp của các quy tắc quyết định tuyến tính trên từng tập hợp các yếu tố ngẫu nhiên cô lập.
Khi các giá trị z˜ j không bị chặn cả trên và dưới, quy tắc quyết định tuyến tính có thể trở nên không chấp nhận được hoặc chỉ là một hàm hằng tầm thường Tuy nhiên, trong những trường hợp xác định, các quy tắc quyết định tuyến tính cô lập có khả năng khắc phục những hạn chế của quy tắc quyết định tuyến tính.
Tính chất
Định lý Nếu với mỗi x, hệ sau đây:
Phương trình T(z)x + Ww(z) = h(z) với điều kiện w(z) ≥ 0 có một giải pháp chấp nhận được cho mọi z ∈ R^N Điều này đồng nghĩa với việc tồn tại một quy tắc quyết định tuyến tính cô lập, đảm bảo tính chấp nhận cho hệ thống (2.44) Để chứng minh điều này, ta xem xét bất kỳ quy tắc quyết định nào được coi là chấp nhận được.
(h j −T j x)z j , (2.45) nên tồn tại w 0 = w(0) ≥ 0 sao cho Ww 0 = h 0 −T 0 x.
Tiếp theo, chúng ta xem xét tới những quy tắc quyết định tuyến tính cô lập dạng sau: w(z) = w 0 +
Chú ý rằng w(z) ≥ 0 với mọi z ∈ R N nếu u j ,v j ≥ 0.
Bây giờ chúng ta chứng minh bằng phản chứng rằng tồn tại u j ,v j ≥ 0 sao cho
Nếu không tồn tại u j ≥ 0 sao cho Wu j = h j −T j x thì từ lý thuyết đối ngẫu mạnh của bài toán quy hoạch tuyến tính suy ra tồn tại y thỏa mãn:
Chú ý rằng với bất kỳ quan hệ z = te j , với e j là một vectơ đơn vị của thành phần thứ j thì đều tồn tại ˆw(t) ≥ 0 sao cho:
Tuy nhiên, ở trên tồn tại y sao cho W T y ≤ 0và (h j −T j x) T y > 0 Ngoài ra, chúng ta còn có:
(h j −T j x) T y = y T Ww(t)ˆ t − 1 t(h 0 −T 0 x) = lim t−→∞y T Ww(t)ˆ t ≤ 0, (2.50) là một mâu thuẫn.
Từ đó, tồn tại u j ≥ 0 sao cho Wu j = h j −T j x Tương tự, tồn tại v j ≥0 sao cho Wv j = −(h j −T j x).
Do đó, quy tắc quyết định tuyến tính cô lập: w(z) = w 0 +
(u j z j 1 −v j z j 2 ) (2.51) là một phương án chấp nhận được của hệ (2.44).
Mô hình của các yếu tố ngẫu nhiên cô lập, U 2
2.4.3.1 Mô hình bài toán quy hoạch ngẫu nhiên với các yếu tố ngẫu nhiên cô lập Chúng ta giả thiết rằng trung bình và hiệp phương sai (˜z + ,˜z − ) đã cho Nghĩa là, những yếu tố ngẫu nhiên cô lập (˜z 1 ,˜z 2 ) là những biến ngẫu nhiên có giá trị trung bình bằng 0, với hiệp phương sai Σˆ và giá trị ˜z 1 ∈ W 1 = [−ˆz,¯z−ˆz] và ˜z 2 ∈ W 2 = [−z ¯+ˆz,ˆz], với ˆz = E(˜z + ).
Vì ˜z = ˜z 1 +˜z 2 nên chúng ta có thể biểu diễn T(˜z 1 ,˜z 1 ) và h(˜z 1 ,˜z 1 ) bởi những yếu tố ngẫu nhiên cô lập như sau:
Từ đó, sử dụng quy tắc quyết định tuyến tính cô lập thì chúng ta có thể xấp xỉ mô hình ngẫu nhiên (1.55) như sau:
Z SLDR = min{c T x+ f T w 0 } với điều kiện:
2.4.3.2 Định lý Quy tắc quyết định tuyến tính cô lập cho một giá trị hàm mục tiêu bé hơn so với quy tắc quyết định tuyến tính, nghĩa là:
Chứng minh Cho x và w k , k = 1, , N là chấp nhận được cho bài toán (2.2) Chúng ta sẽ chứng tỏ rằng: w 1k = w 2k = w k , k = 1, , N, (2.56) là chấp nhận được cho bài toán (2.54).
Các ràng buộc tuyến tính trong bài toán (2.54) được coi là hợp lệ Để chứng minh tính chấp nhận được của hệ ràng buộc, nếu y 0 và y thỏa mãn điều kiện y 0 + y T z ≥ 0 với mọi z ∈ W, thì chúng cũng thỏa mãn y 0 + y T (z 1 + z 2 ) ≥ 0 với mọi z 1 ∈ W 1 và z 2 ∈ W 2 Điều này có thể được suy ra từ tính chấp nhận được trong hệ (2.57), dẫn đến y 0 + y T (z 1 + z 2 ) ≥ 0 với mọi z 1 + z 2 ∈ W Hơn nữa, với mọi z 1 ∈ W 1 và z 2 ∈ W 2, ta có z 1 + z 2 thuộc W.
Từ đó, y 0 và y còn chấp nhận được cho hệ (2.58).
Quy tắc quyết định tuyến tính lệch-cô lập
Khái niệm
Mặc dù các quy tắc quyết định tuyến tính cô lập thể hiện hiệu quả hơn so với các quy tắc quyết định tuyến tính thông thường, nhưng chúng không nhất thiết tốt hơn so với các quy tắc quyết định tuyến tính lệch.
Dựa trên những quy tắc quyết định tuyến tính cải tiến, quy tắc quyết định tuyến tính lệch-cô lập được định nghĩa như sau: w(˜z 1 ,˜z 2 ) = r(˜z 1 ,˜z 2 ) + X i∈I 1 r i (˜z 1 ,˜z 2 ) − p i, trong đó w(ã) ∈ S.
Với cách làm tương tự thì chúng ta đã bắt đầu dễ hơn, chúng ta cần tính bị chặn E r i (˜z 1 ,˜z 2 ) −
Tiếp theo, từ Định lý 2.3.4.2 và với mô hình của các yếu tố ngẫu nhiên cô lập U 2 , chúng ta có:
Cuối cùng, chúng ta đề xuất phép xấp xỉ sau đây cho bài toán (1.55) sử dụng quy tắc quyết định tuyến tính lệch-cô lập:
Z¯ SDLDR = min{c T x+f T r 0 +X i∈I 1 f¯ i g i } với điều kiện:
Tính chất
Định lý này nêu rõ rằng quy tắc quyết định tuyến tính lệch-cô lập áp dụng cho một giá trị hàm mục tiêu nhỏ hơn so với quy tắc quyết định tuyến tính lệch.
Chứng minh Cho x, g và r k , k = 0, , N là chấp nhận được cho bài toán (2.35) Chúng ta sẽ chứng tỏ rằng: r 1k = r 2k = r k , k = 0, , N, (2.65) còn chấp nhận được cho bài toán (2.63).
Chúng ta sử dụng tính chấp nhận được trong ràng buộc tuyến tính và kết quả trong chứng minh của Định lý2.4.3.2 Chúng ta cần chứng tỏ rằng: g i ≥ ˆh r i 0 ,(r i 1 , , r N i ),(r 1 i , , r i N )
, ∀i ∈ I 1 (2.66) Điều đó đủ để chứng tỏ được rằng: ˆh(y 0 ,y,y) ≤h(y 0 ,y) (2.67)Với s,t,u,v là phương án tối ưu trong sự tối ưu của bài toán (2.23),chúng ta có: ˆh(y0,y,y) ≤ 1
Phương pháp này cho thấy bản chất của việc phân chia các yếu tố ngẫu nhiên, từ đó cải tiến các quy tắc quyết định liên quan đến độ phức tạp tính toán.
Mô hình nhiều giai đoạn
Phương pháp của chúng ta có thể thuận lợi cho việc mở rộng để giải quyết các bài toán quy hoạch ngẫu nhiên nhiều giai đoạn như sau: min{c T x+E
Trong mô hình này, ξ˜ t được định nghĩa là (˜z 1 , ,˜z t ), trong đó các yếu tố ngẫu nhiên ˜z 1 ∈ R N 1 đến ˜z T ∈ R N T đại diện cho các giai đoạn từ đầu đến cuối, và ˜z t là vectơ các yếu tố ngẫu nhiên tại giai đoạn thứ t.
Chúng ta giả định rằng Tt( ˜ξt) và bt( ˜ξt) là tuyến tính với biến ξ˜t Việc áp dụng quyết định tuyến tính giúp xác định một giới hạn trên cho bài toán tối ưu ngẫu nhiên nhiều giai đoạn một cách dễ dàng Để cải tiến bài toán, chúng ta sử dụng quy tắc quyết định tuyến tính lệch, tương tự như trong bài toán (1.58) Đối với mọi t = 1, 2, , T và i ∈ It, chúng ta định nghĩa f¯ ti = min{.
Pk τ=tWkτp ti τ = 0, ∀k = t, , T, p ti ti = 1, p ti τ j ≥ 0, ∀τ = t, , T, j ∈ I τ ,
(2.69) với p ti τ j thể hiện thành phần thứ j của vectơ p ti τ
Tương tự, chúng ta định nghĩa:
I t 1 , {f¯ ti < ∞ | i ∈ It}, I t 2 , It \I t 1 , (2.70) và (¯p ti t , ,¯p ti T ) thể hiện phương án tối ưu tương ứng với t bất kỳ và i ∈ I t 1
Tương tự cho mô hình hai giai đoạn, quy tắc quyết định tuyến tính lệch có thể được định nghĩa như sau: r t ( ˜ξ t ) =r 0 t + t
Chú ý rằng quy tắc quyết định ở trên thực hiện đầy đủ những yêu cầu không cho biết trước.
Như vậy, chúng ta đã thu được một công thức về mô hình nhiều giai đoạn tương tự như mô hình hai giai đoạn đã trình bày ở phần trước.
SỰ HIỆU CHỈNH ĐẦY ĐỦ VÀ SỰ HIỆU CHỈNH NỬA ĐẦY ĐỦ
Vài nét giới thiệu về nội dung của chương
Lĩnh vực tối ưu hiện nay đang thu hút sự quan tâm của các nhà Toán học, đặc biệt là trong bài toán tối ưu ngẫu nhiên Nhóm nghiên cứu của Xin Chen đã công bố nhiều bài báo quan trọng về cải tiến phương pháp xấp xỉ cho bài toán này, nhấn mạnh tầm quan trọng của nó trong lý thuyết và ứng dụng thực tiễn Chen cùng các cộng sự nhận thấy rằng các quy tắc quyết định tuyến tính có thể dẫn đến những trường hợp không khả thi trong tối ưu ngẫu nhiên, yêu cầu cần phải làm mịn các quy tắc này Từ đó, họ đã đề xuất hai phép xấp xỉ, được trình bày chi tiết trong Chương 2.
Xấp xỉ đầu tiên được gọi là "những quy tắc quyết định tuyến tính lệch", được áp dụng cho bài toán tối ưu ngẫu nhiên với các biến hiệu chỉnh nửa đầy đủ.
Xấp xỉ thứ hai, được gọi là "những quy tắc quyết định tuyến tính cô lập", phù hợp cho bài toán tối ưu ngẫu nhiên với sự hiệu chỉnh tổng quát Điểm đặc biệt của hai quy tắc này là khả năng kết hợp chúng để tạo ra "quy tắc quyết định tuyến tính lệch-cô lập", mang lại độ xấp xỉ tốt hơn (mịn hơn) so với cả xấp xỉ tuyến tính và xấp xỉ tuyến tính lệch.
Chen và các cộng sự đã chỉ ra rằng ma trận hiệu chỉnh đầy đủ là một dạng của ma trận hiệu chỉnh nửa đầy đủ Chúng tôi đặt ra câu hỏi về các điều kiện cần và đủ để ma trận hiệu chỉnh nửa đầy đủ trở thành ma trận hiệu chỉnh đầy đủ Mục tiêu của Chương 3 là xác định các điều kiện này và thiết lập mối quan hệ giữa hai loại ma trận, nhằm trả lời triệt để câu hỏi trên.
Kết quả về điều kiện cần và đủ để ma trận hiệu chỉnh nửa đầy đủ trở thành ma trận hiệu chỉnh đầy đủ mà chúng tôi đã tìm ra mang lại hai ý nghĩa quan trọng.
Định nghĩa ma trận hiệu chỉnh đầy đủ khó kiểm tra và thiết lập hơn so với định nghĩa ma trận hiệu chỉnh nửa đầy đủ Do đó, kết quả nghiên cứu của chúng tôi đã giải quyết được những khó khăn này.
Bài toán quy hoạch ngẫu nhiên với hiệu chỉnh đầy đủ có thể chấp nhận các quy tắc quyết định tuyến tính lệch Tuy nhiên, quy tắc này vẫn có thể được chấp nhận ngay cả khi thiếu sự hiệu chỉnh đầy đủ, tức là các biến hiệu chỉnh nửa đầy đủ nhưng không hiệu chỉnh đầy đủ Câu hỏi đặt ra là khi nào điều này xảy ra? Chúng tôi chỉ ra rằng có những điều kiện cần và đủ để một ma trận hiệu chỉnh nửa đầy đủ không trở thành ma trận hiệu chỉnh đầy đủ.
Một số tính chất về ma trận hiệu chỉnh đầy đủ, ma trận hiệu chỉnh nửa đầy đủ
Ma trận hiệu chỉnh đầy đủ
3.2.1.1 Định lý Ma trận W cấp m×n là ma trận hiệu chỉnh đầy đủ khi và chỉ khi " Với số thực α bất kỳ, với mỗi vectơ cột t cấp m ×1 đều tồn tại vectơ cột w = [w 1 w 2 w n ] T với các biến bị chặn dưới bởi α, tức là wj ≥ α,∀j = 1, n thoả mãn Ww = t".
Giả sử W là ma trận hiệu chỉnh đầy đủ Đối với mỗi số thực α và vectơ cột t cấp m × 1, ta có thể xác định t ∗ = t − Wα ∗, với α ∗ = [α α α] T là vectơ cột cấp n×1.
Theo định nghĩa ma trận hiệu chỉnh đầy đủ, tồn tại vectơ cột y [y 1 y 2 y n ] T sao cho y j ≥ 0,∀j = 1, n thoả mãn Wy = t ∗ , hay Wy = t -
Wα ∗ , điều này tương đương với W(y+α ∗ ) =t.
Ta đặt w = y + α ∗ = [w 1 w 2 w n ] T với w j = y j + α ≥ α thì ta có
Ww = t thoả mãn các biến bị chặn dưới bởi α.
Ngược lại, ta dễ dàng có điều phải chứng minh với việc chọn α = 0.
3.2.1.2 Định lý Ma trận W cấp m×n là ma trận hiệu chỉnh đầy đủ khi và chỉ khi " Với số thực α bất kỳ, với mỗi vectơ cột t cấp m ×1 đều tồn tại vectơ cột w = [w 1 w 2 w n ] T với các biến bị chặn trên bởi α, tức là wj ≤ α,∀j = 1, n thoả mãn Ww = t".
Giả sử W là ma trận hiệu chỉnh đầy đủ, với mỗi số thực α và vectơ cột t cấp m×1, ta có thể xác định t ∗ = −t + Wα ∗, trong đó α ∗ là vectơ cột cấp n×1 với các phần tử đều bằng α.
Do W là ma trận hiệu chỉnh đầy đủ, tồn tại vectơ cột y = [y1, y2, , yn] T với yj ≥ 0 cho mọi j từ 1 đến n, thỏa mãn điều kiện Wy = t* hoặc Wy = -t + Wα* Điều này tương đương với W(-y + α*) = t Nếu đặt w = -y + α* = [w1, w2, , wn] T, với wj = -yj + α ≤ α, ta sẽ có kết quả mong muốn.
Ww = t thoả mãn các biến bị chặn trên bởi α.
Chúng ta chọn α = 0 và với mỗi vectơ cột t cấp m×1, đặt t ∗ = −t Theo giả thiết, tồn tại vectơ cột x = [x 1 x 2 x n ] T với các biến bị chặn trên bởi 0, tức là xj ≤ 0,∀j = 1, n, thoả mãn điều kiện Wx = t ∗ Điều này dẫn đến Ww = t, với w = - x = [w 1 w 2 w n ] T, sao cho w j = −x j ≥ 0,∀j = 1, n.
Theo Định nghĩa 1.3.1.2, ma trận W là ma trận hiệu chỉnh đầy đủ.
3.2.1.3 Định lý Ma trận W cấp m×n là ma trận hiệu chỉnh đầy đủ thì m < n và ma trận W có hạng bằng m.
Chứng minh Gọi W1, W2, , Wn là các vectơ cột của ma trận W, đây chính là các vectơ trong không gian vectơ R m
Trước tiên, ta chứng minh m < n Thật vậy, giả sử ngược lại:
Trong trường hợp m > n, ta có rank{W 1 , W 2 , , W n } < m, dẫn đến tồn tại vectơ cột t ∈ R m sao cho rank{W 1 , W 2 , , W n,t} = rank{W 1 , W 2 , , W n} + 1 Điều này cho thấy t không thuộc không gian vectơ sinh bởi {W 1 , W 2 , , W n }, từ đó suy ra không tồn tại vectơ cột w thỏa mãn Ww = t Kết luận là ma trận W không phải là ma trận hiệu chỉnh đầy đủ, dẫn đến một mâu thuẫn.
Trường hợp 2: m = n và rank(W) < m Lập luận hoàn toàn tương tự trường hợp 1.
Trường hợp 3: m = n và rank(W) = m Khi đó, ma trận W khả nghịch, suy ra hệ {W 1 , W 2 , , W n } là cơ sở của không gian vectơ R m
Theo giả thiết, ma trận W là ma trận hiệu chỉnh đầy đủ, từ đó suy ra W là ma trận hiệu chỉnh nửa đầy đủ Điều này có nghĩa là tồn tại một vectơ cột r = [r1, r2, , rn] T cấp n×1 với các thành phần rj > 0 cho mọi j = 1, n, và thỏa mãn điều kiện Wr = 0 Kết quả này dẫn đến mâu thuẫn với hệ {W1, W2, , Wn} là cơ sở.
Bây giờ ta chứng minh W có hạng bằng m Giả sử ngược lại, ma trận
Nếu hạng của ma trận W nhỏ hơn m, tức là rank{W 1 , W 2 , , W n } < m, theo Mệnh đề 1.3.1.3, tồn tại một vectơ cột t ∈ R m sao cho rank{W 1 , W 2 , , W n , t} = rank{W 1 , W 2 , , W n } + 1 Điều này có nghĩa là t không thuộc không gian vectơ sinh bởi {W 1 , W 2 , , W n }, dẫn đến việc không tồn tại vectơ cột w sao cho Ww = t Do đó, W không phải là ma trận hiệu chỉnh đầy đủ, từ đó phát sinh một mâu thuẫn.
3.2.1.4 Hệ quả Bài toán quy hoạch ngẫu nhiên có ràng buộc tuyến tính là bài toán có dạng: min{f(x)} với điều kiện:
Ax= b x ≥0, (3.4) trong đó các ma trận x = [x 1 x 2 x n ] T cấp n×1, b = [b 1 b 2 b m ] T cấp m×1,
A = [a ij ] cấp m×n, và các phần tử của các ma trận A, b; hàm mục tiêu f đều phụ thuộc vào các yếu tố ngẫu nhiên.
Khi đó nếu m ≥ n, hoặc m < n nhưng ma trận A có hạng bé hơn m thì tồn tại cách chọn ma trận cột b sao cho tập phương án:
{x | Ax = b,x ≥ 0} của bài toán quy hoạch ngẫu nhiên với ràng buộc tuyến tính (3.4) là rỗng.
Chúng ta sẽ chứng minh bài toán bằng phương pháp phản chứng Giả sử ngược lại, với mọi cách chọn vectơ cột b, tập phương án {x | Ax = b, x ≥ 0} của bài toán quy hoạch ngẫu nhiên là khác rỗng, điều này cho thấy ma trận A là ma trận hiệu chỉnh đầy đủ Tuy nhiên, theo Định lý 3.2.1.3, nếu ma trận A có kích thước m×n với m < n và hạng của ma trận A bằng m, thì sẽ xảy ra mâu thuẫn.
3.2.1.5 Định lý Giả sử ma trận W có cấp m×n(m < n), có hạng bằng m, thoả mãn điều kiện tồn tại vectơ cột r = [r 1 r 2 r n ] T cấp n×1, với r j ≥ 0,∀j = 1, n sao cho Wr = 0 và tập các vectơ cột tương ứng với các hệ số rj > 0 của ma trận W tồn tại một hệ các vectơ cột tạo thành cơ sở của không gian vectơ R m Khi đó, W là ma trận hiệu chỉnh đầy đủ.
Để chứng minh, ta gọi W1, W2, , Wn là các vectơ cột của ma trận W Không mất tính tổng quát, giả sử W1, W2, , Wm là hệ các cột cơ sở với các trọng số r1, r2, , rm đều lớn hơn 0 Theo giả thiết, ta có phương trình: r1W1 + r2W2 + + rnWn = 0 (3.5).
Với mọi vectơ cột t cấp m ×1 thì vectơ cột t biểu diễn được qua cơ sở {W 1 , W2, , Wm} là: t = t 1 W 1 +t 2 W 2 +ã ã ã+t m W m (3.7) (∗) Nếu tj ≥ 0,∀j = 1, m thì ta chọn: w j = t j ,∀j = 1, m, w j = 0,∀j = m + 1, n, (3.8)
, đây chính là điều phải chứng minh.
(∗) Nếu trái lại, ∃t j < 0 Do giả thiết r j > 0,∀j = 1, m nên tồn tại min{ r t j j | tj < 0, j = 1, m} Không mất tính tổng quát, ta giả sử: min{tj r j | t j < 0, j = 1, m} = tm r m (3.9)
Vì t m < 0, r m > 0 nên r t m m < 0 Ta đặt: wj = tj − t m r m rj, ∀j = 1, m
+) Nếu tj < 0 thì từ công thức (3.9) và (3.11) suy ra: t j r j ≥ t m r m ⇔ t j r j − t m r m ≥ 0 ⇒wj ≥ 0 (3.12)
+) Nếu tj > 0 thì do r t m m < 0 nên: w j = t j − tm r m r j ≥0 (3.13)
Tóm lại, theo cách đặt ở công thức (3.10) thì: wj ≥0,∀j = 1, m (3.14)
Từ công thức (3.10) suy ra được: t j = w j + t m rm
Thay t j trong công thức (3.15) vào công thức (3.7) và sử dụng công thức (3.6) ta có: t m
Bây giờ ta đặt: w j = −t m rm
Do t m < 0, r m > 0, r j ≥ 0 nên ta suy ra: w j ≥ 0,∀j = m+ 1, n (3.17)
Do đó, với w j xác định ở công thức (3.10) và công thức (3.16), đồng thời w m = 0 nên ta có: t n
, (3.18) hay Ww = t, có nghĩa là W là ma trận hiệu chỉnh đầy đủ.
Ma trận hiệu chỉnh nửa đầy đủ
3.2.2.1 Định lý Ma trận W cấp m ×n là ma trận hiệu chỉnh nửa đầy đủ khi và chỉ khi tồn tại vectơ cột r = [r 1 r 2 r n ] T cấp n ×1 sao cho r j > 0,∀j = 1, n và Wr = 0.
Để chứng minh, giả sử W là ma trận hiệu chỉnh nửa đầy đủ Theo định nghĩa tại mục 1.3.2.1, ta có thể kết luận rằng với mỗi i từ 1 đến n, tập phương án của bài toán (1.58) không rỗng, tức là tồn tại các vectơ cột p (i) = [p (i) 1 p (i) 2 p (i) n ] T thỏa mãn điều kiện đã nêu.
(3.19) Đặt vectơ cột r = p (1) +p (2) +ã ã ã+p (n) Khi đú, thành phần thứ j của vectơ cột r là: rj n
Từ hệ điều kiện (3.19) ta có p (j) j = 1 và p (i) j ≥ 0,∀i = 1, n nên r j > 0.
Rừ ràng ta cú Wr = Wp (1) +Wp (2) +ã ã ã+Wp (n) = 0.
∗ Điều kiện đủ: Giả sử tồn tại vectơ cột r = [r 1 r 2 r n ] T cấp n×1 sao cho r j > 0,∀j = 1, n và Wr = 0 Khi đó, với mỗi i = 1, n ta đặt: p (i) = 1 r i r (3.21)
> 0, (3.22) và Wp (i) = 0 nên tập phương án của bài toán (1.58) là khác rỗng Do đó, theo định nghĩa ở mục 1.3.2.1 thì W là ma trận hiệu chỉnh nửa đầy đủ.
3.2.2.2 Ví dụ Ma trận W là ma trận không thì W là ma trận hiệu chỉnh nửa đầy đủ, bởi vì với mọi vectơ cột r = [r1 r2 rn] T cấp n×1 sao cho r j > 0,∀j = 1, n đều thoả mãn Wr = 0 Tuy nhiên, W lại không phải là một ma trận hiệu chỉnh đầy đủ, vì ta chỉ cần chọn vectơ cột t cấp m×1 khác vectơ cột không thì đều không xảy ra đẳng thức Ww = t, với mọi cách chọn vectơ cột w.
Hai ma trận được các tác giả Chen và cộng sự sử dụng trong mô hình tính toán để minh hoạ cho xấp xỉ giải bài toán tối ưu ngẫu nhiên của họ Đây là hai ma trận hiệu chỉnh nửa đầy đủ, không phải là ma trận hiệu chỉnh đầy đủ, và bạn đọc có thể kiểm tra trực tiếp dựa vào định nghĩa ở mục 1.3.1.2 và mục 1.3.2.2.
Việc kiểm tra ma trận W có phải là ma trận hiệu chỉnh đầy đủ hay không trở nên khó khăn khi W có cấu trúc phức tạp Tuy nhiên, những kết quả mà chúng tôi thu được đã giúp giải quyết những khó khăn này.
Một trường hợp đặc biệt về sự hiệu chỉnh đầy đủ là hiệu chỉnh đơn, với
Mối quan hệ giữa ma trận hiệu chỉnh đầy đủ và ma trận hiệu chỉnh nửa đầy đủ
hiệu chỉnh nửa đầy đủ
3.2.3.1 Mệnh đề Một ma trận W thoả mãn điều kiện hiệu chỉnh đầy đủ là một ma trận hiệu chỉnh nửa đầy đủ, có nghĩa là I 1 = I.
Chứng minh rằng với định nghĩa hiệu chỉnh đầy đủ, tồn tại một vectơ s sao cho Ws = -Wv, với v có các thành phần v_i ≥ 1 cho mọi i ∈ I Điều này dẫn đến việc r_i = s_i + v_i ≥ 1 cho mọi i ∈ I và Wr = 0 Theo Định lý 3.2.2.1, có thể kết luận rằng W là ma trận hiệu chỉnh nửa đầy đủ.
3.2.3.2 Định lý Ma trận W cấp m×n(m < n), có hạng bằng m Khi đó,
W là ma trận hiệu chỉnh đầy đủ khi và chỉ khi W là ma trận hiệu chỉnh nửa đầy đủ.
Để chứng minh rằng ma trận W là ma trận hiệu chỉnh đầy đủ, ta cần xác định điều kiện cần Theo định nghĩa tại mục 1.3.1.2, vì W là ma trận hiệu chỉnh nửa đầy đủ, nó sẽ thỏa mãn tất cả giả thiết của Định lý 3.2.1.5 Do đó, áp dụng Định lý 3.2.1.5, ta có thể kết luận rằng W là ma trận hiệu chỉnh đầy đủ.
∗ Điều kiện đủ: Suy trực tiếp từ Mệnh đề 3.2.3.1.
Ma trận W = [I, -I] cấp n×2n là ma trận hiệu chỉnh đầy đủ, cũng như ma trận hiệu chỉnh nửa đầy đủ, với I là ma trận đơn vị cấp n Điều này được suy ra từ Định lý 3.2.1.3 và Định lý 3.2.3.2, trong đó vectơ cột r được xác định là r = [1 1 1] T Ngoài ra, có thể kiểm tra trực tiếp theo định nghĩa ở mục 1.3.1.2 Ma trận này được gọi là ma trận hiệu chỉnh đơn.
3.2.3.3 Hệ quả Cho ma trận W cấp m ×n là ma trận hiệu chỉnh nửa đầy đủ Khi đó, ma trận W là ma trận hiệu chỉnh đầy đủ khi và chỉ khi m < n và ma trận W có hạng bằng m.
Chứng minh ∗ Điều kiện cần: Suy trực tiếp từ Định lý 3.2.3.2.
∗ Điều kiện đủ: Suy trực tiếp từ Định lý 3.2.1.3.
Thiết lập ma trận hiệu chỉnh đầy đủ và ma trận hiệu chỉnh nửa đầy đủ
3.2.4.1 Định lý Cho trước hai số tự nhiên m, n Khi đó, luôn tồn tại ma trận hiệu chỉnh nửa đầy đủ W có cấp m×n Hơn nữa, nếu n > 1 thì với số tự nhiên k bất kì sao cho k ≤min{m, n−1}, luôn tồn tại ma trận hiệu chỉnh nửa đầy đủ W có cấp m×n và có rank(W) = k.
Để chứng minh, khi n = 1, ta chọn ma trận W là ma trận cột không, tương ứng với vectơ không trong không gian vectơ R m Với lựa chọn này, ma trận W sẽ thỏa mãn điều kiện là ma trận hiệu chỉnh nửa đầy đủ.
∗ Nếu n > 1 thì ta chọn tuỳ ý các vectơ cột W 1 , W 2 , , W n−1 ∈ R m có hạng bằng k và các số thực dương tuỳ ý r j > 0,∀j = 1, n Ta đặt:
Gọi W là ma trận gồm các cộtW 1 , W 2 , , W n Khi đó, công thức (3.24) cho ta Wr = 0 Rõ ràng ma trận W có cấp m × n Do hệ vectơ cột
Ma trận W được xây dựng với các vectơ W 1, W 2, , W n−1 thuộc R m có hạng k, trong đó vectơ cột W n được biểu thị tuyến tính qua các vectơ này, dẫn đến việc suy ra rằng rank(W) = k Do đó, ma trận W là ma trận hiệu chỉnh nửa đầy đủ có kích thước m×n và hạng k.
3.2.4.2 Nhận xét Từ Hệ quả 3.2.3.3, ta có thể thiết lập ma trận hiệu chỉnh đầy đủ thông qua việc thiết lập ma trận hiệu chỉnh nửa đầy đủ bằng cách sử dụng Định lý 3.2.4.1 với việc chọn k = m.
1) Luận văn đã giải quyết được một số vấn đề sau:
1.1 Nghiên cứu, trình bày chi tiết các phép xấp xỉ bởi những quy tắc quyết định giải bài toán quy hoạch ngẫu nhiên hai giai đoạn và xây dựng cho bài toán quy hoạch ngẫu nhiên nhiều giai đoạn.
Trong bài viết này, chúng tôi bắt đầu bằng cách trình bày quy tắc quyết định tuyến tính, tiếp theo là phân tích tính không khả thi của quy tắc này Dựa trên những hạn chế đã chỉ ra, chúng tôi tiến hành xây dựng các quy tắc quyết định mới, cải tiến hơn so với quy tắc quyết định tuyến tính trước đó.
Quy tắc quyết định tuyến tính lệch là một phương pháp hiệu quả cho bài toán quy hoạch ngẫu nhiên với sự hiệu chỉnh nửa đầy đủ Nghiên cứu của chúng tôi chỉ ra rằng giá trị hàm mục tiêu đạt được thông qua quy tắc này nhỏ hơn so với quy tắc quyết định tuyến tính truyền thống.
Quy tắc quyết định tuyến tính cô lập, gần giống như quy tắc xấp xỉ thứ hai, thích hợp cho bài toán quy hoạch với sự điều chỉnh tổng quát Chúng tôi đã chứng minh rằng giá trị hàm mục tiêu đạt được từ quy tắc này thấp hơn so với quy tắc quyết định tuyến tính.
Hai quy tắc này có thể kết hợp để tạo thành quy tắc quyết định tuyến tính lệch-cô lập, mang lại giá trị hàm mục tiêu thấp hơn so với quy tắc quyết định tuyến tính lệch.
∗ Cuối phần này, chúng tôi xây dựng cho bài toán quy hoạch ngẫu nhiên nhiều giai đoạn tương tự như trong mô hình hai giai đoạn.
1.2 Trong Chương 3 chúng tôi tập trung nghiên cứu về sự hiệu chỉnh đầy đủ, sự hiệu chỉnh nửa đầy đủ và mối quan hệ giữa chúng và thu được một số kết quả mới khá thú vị Tất cả các kết quả chúng tôi trình bày trong chương này đều là kết quả mới mà chúng tôi thu được.
Chúng tôi đã phát hiện và chứng minh chi tiết các điều kiện tương đương liên quan đến sự hiệu chỉnh đầy đủ và nửa đầy đủ, cụ thể là trong Định lý 3.2.1.1, Định lý 3.2.1.2 và Định lý 3.2.2.1.
∗ Tiếp theo, chúng tôi chỉ ra một điều kiện cần rất tốt của sự hiệu chỉnh đầy đủ (Định lý 3.2.1.3) và cho một hệ quả của nó (Hệ quả 3.2.1.4).
Chúng tôi đã phát hiện ra một điều kiện đủ tốt cho sự hiệu chỉnh đầy đủ (Định lý 3.2.1.5) Dựa trên kết quả này, chúng tôi chỉ ra điều kiện cần và đủ để ma trận hiệu chỉnh nửa đầy đủ trở thành ma trận hiệu chỉnh đầy đủ (Định lý 3.2.3.2 và Hệ quả 3.2.3.3).
Chúng tôi đã xác định được phương pháp thiết lập sự hiệu chỉnh nửa đầy đủ và sự hiệu chỉnh đầy đủ, theo định lý 3.2.4.1 và nhận xét 3.2.4.2.
1.3 Kết quả mới chúng tôi thu được và đã trình bày ở Chương 3 của luận văn đã được công bố tại Hội thảo khoa học: "Nửa thế kỷ Trường Đại học Vinh anh hùng", được đăng trên Tạp chí Khoa học Trường Đại học Vinh số 38A/2009 (Vinh University Journal of Science).
2) Hướng mở của luận văn:
Sử dụng các phương pháp xấp xỉ dựa trên quy tắc quyết định giúp giải quyết các bài toán ứng dụng thực tiễn hiệu quả Đồng thời, việc xây dựng các tính toán cho các xấp xỉ với khối lượng lớn có thể được thực hiện thông qua phần mềm tin học, mang lại sự chính xác và tiết kiệm thời gian trong quá trình xử lý dữ liệu.
