2

MỤC LỤC

Mở đầu

3

1 Kiến thức cơ sở

5

1.1 Một số vấn đề cơ sở của lý thuyết xác suất và thống kê . . . .

5

1.2 Bài toán qui hoạch ngẫu nhiên . . . . . . . . . . . . . . . . . .

10

1.3 Bài toán quy hoạch ngẫu nhiên rời rạc . . . . . . . . . . . . . .

14

2 Phương pháp xấp xỉ trung bình mẫu

16

2.1 Phép lấy mẫu . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2 Thuật toán xấp xỉ trung bình mẫu . . . . . . . . . . . . . . . .

26

2.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Kết luận

37

Tài liệu tham khảo

38


3

MỞ ĐẦU

Bài toán quy hoạch với sự tham gia của yếu tố ngẫu nhiên được gọi là bài
toán quy hoạch ngẫu nhiên. Trong các bài toán quy hoạch ngẫu nhiên, bài tốn
quy hoạch ngẫu nhiên rời rạc là một mơ hình dành cho nhiều bài tốn thực tế.
Cũng như lý thuyết quy hoạch, việc xét tới các bài toán quy hoạch ngầu
nhiên rời rạc cũng gặp nhiều khó khăn. Gần đây các cơng trình nghiên cứu về
bài tốn quy hoạch ngẫu nhiên rời rạc đã cho ta những thuật toán hữu hiệu
góp phần quan trọng khơng chỉ vào lý luận mà cả việc giải quyết bài toán thực
tế đặt ra. Chẳng hạn các cơng trình của Hochberg và Tamhane; Morton và

Wood; Anton J. Kleywegt, Alexander Sharpio và Tito Homem-De-Mello.
Với sự quan tâm, chú ý tới những khía cạnh phù hợp của nó, cùng thời gian
và mức độ cho phép, chúng tơi cố gắng xem xét nội dung có liên quan đến cơng
trình của Anton J. Kleywegt, Alexander Sharpio và Tito Homem-De-Mello.
Đó là lí do chọn đề tài Phương pháp xấp xỉ trung bình mẫu giải bài
tốn quy hoạch ngẫu nhiên rời rạc.
Nội dung của luận văn bao gồm hai chương:
Chương 1. Kiến thức cơ sở. Trong chương này, chúng tôi trình bày những
khái niệm và kiến thức cơ sở của lý thuyết xác suất và thống kê nhằm phục vụ
cho việc nghiên cứu của đề tài. Đồng thời đưa ra các hướng tiếp cận để giải
bài toán quy hoạch ngẫu nhiên rời rạc.
Chương 2. Phương pháp xấp xỉ trung bình mẫu. Trong chương này, trước
hết chúng tơi trình bày phép lấy mẫu của bài toán được nêu ra trong đề tài.


4

Tiếp đó chúng tơi trình bày các tính chất cơ bản của bài toán được đặt ra.
Cuối cùng đưa ra thuật tốn và ví dụ minh họa.
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 và chỉ bảo tận tình của thầy giáo PGS. TS. Trần Xuân Sinh. Tác
giả xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy giáo hướng dẫn, các
cô giáo, thầy giáo trong tổ Xác suất thống kê và Toán ứng dụng, Khoa toán
trường Đại học Vinh, Khoa Đào tạo Sau Đại học, cùng các bạn đã góp ý và
tạo điều kiện cho tác giả hồn thành luận văn này.
Mặc dù đã cố gắng, nhưng do thời gian cũng như năng lực bản thân còn
nhiều hạn chế nên luận văn khơng tránh khỏi những thiếu sót. Tác giả mong
nhận được những góp ý của thầy, cơ giáo và bạn bè.
Vinh, ngày


tháng 12 năm 2010
Tác giả


5

CHƯƠNG 1

KIẾN THỨC CƠ SỞ

1.1

Một số vấn đề cơ sở của lý thuyết xác suất và thống kê

1.1.1 Đại số và σ - đại số. Giả sử Ω = ∅ và P(Ω) là họ tất cả các tập con
của Ω . Mỗi họ A ⊂ P(Ω) sẽ được gọi là lớp.
Lớp A ⊂ P(Ω) được gọi là một đại số nếu thỏa mãn:
1) Ω ∈ A,
2) với A ∈ A thì AC = Ω \ A ∈ A,
3) với A, B ∈ A thì A ∪ B ∈ A.
Lớp F ⊂ P(Ω) được gọi là một σ - đại số nếu thỏa mãn:
1) Ω ∈ F ,
2) với A ∈ F thì AC = Ω \ A ∈ F ,

∞

An ∈ F .

3) với An ∈ F, (∀n = 1, 2, . . .), thì
n=1


1.1.2 Khơng gian đo và độ đo xác suất. Cặp (Ω, F) được gọi là một
không gian đo, trong đó Ω là tập bất kì khác rỗng, F là một σ - đại số các
tập con của Ω .
Giả sử (Ω, F) là một không gian đo. Một ánh xạ P : F → R được gọi là
một độ đo xác suất trên F nếu:
1) P (A) ≥ 0, ∀A ∈ F ,
2) P (Ω) = 1,


6

3) với An ∈ F, ∀n = 1, 2, . . . , Ai

Aj = ∅, i = j thì

∞

P(

∞

An ) =

n=1

P (An ).
n=1

Sau đây là một số tính chất của xác suất thường được dùng trong lý thuyết

quy hoạch ngẫu nhiên:
1. P (∅) = 0;
2. Nếu A ⊂ B; A, B ∈ F thì P (A) ≤ P (B);
3. Nếu A, B ∈ F thì P (A ∪ B) = P (A) + P (B) − P (AB);
1.1.3 Không gian xác suất. Giả sử Ω là tập hợ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.

Tập Ω được gọi là không gian biến cố sơ cấp.
σ - đại số F được gọi là σ - đại số các biến cố.

Mỗi A ∈ F được gọi là một biến cố.
Không gian xác suất (Ω, F, P ) được gọi là không gian xác suất đầy đủ nếu
mọi tập con của biến cố có xác suất khơng đều là biến cố.
1.1.4 Biến ngẫu nhiên. Giả sử (Ω, F, P ) là một không gian xác suất, G là
σ - đại số con của σ - đại số F . B(R) là σ - đại số Borel trên đường thẳng R.

Khi đó ánh xạ X : Ω → R được gọi là biến ngẫu nhiên G - đo được nếu với
mọi B ∈ B(R) ta có
X −1 (B) = {w : X(w) ∈ B} ∈ G.

Nếu biến ngẫu nhiên X chỉ nhận hữu hạn giá trị thì nó được gọi là biến ngẫu
nhiên đơn giản.
Biến ngẫu nhiên còn được gọi là đại lượng ngẫu nhiên.


7

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.

1.1.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. 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.

Hàm phân phối có tính chất:
1. 0 ≤ F (x) ≤ 1;
2. a < b thì F (b) − F (a) = P (a ≤ X < b), do đó F (x) là hàm khơng giảm;
3. lim F (x) = 1, lim F (x) = 0.
x→+∞

x→−∞

1.1.6 Kì vọng của biến ngẫu nhiên. Giả sử X : (Ω, F, P ) → (R, B(R))
là đại lượng 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
XdP.

EX =
Ω

Kì vọng có các tính chất cơ bản sau đây:
1. Nếu X ≥ 0 thì EX ≥ 0;
2. Nếu X = c thì EX = c;
3. Nếu tồn tại EX thì với mọi c ∈ R, ta có E(cX) = c(EX);
4. Nếu tồn tại EX và EY thì E(X ± Y ) = EX ± EY ;


xi pi nếu X rời rạc nhận các giá trị x1 , x2 , . . .




i

5. EX = với p(X = xi ) = pi
+∞




 xp(x)dx nếu X liên tục có hàm mật độ p(x).
−∞


8

6. (Định lý P.Levi về hội tụ đơn điệu). Nếu Xn ↑ X (tương ứng Xn ↓ X )
và tồn tại n để EXn− < ∞ (tương ứng EXn+ < ∞), thì EXn ↑ EX (tương
ứng EXn ↓ EX ).
7. (Bổ đề Fatou). Nếu Xn ≥ Y với mọi n ≥ 1 và EY > −∞ thì
E lim Xn ≤ lim EXn .

8. (Định lí Lebesgue về hội tụ bị chặn). Nếu |Xn | ≤ Y với mọi n ≥ 1,
EY < ∞ và Xn → X thì X khả tích, E|Xn − X| → 0 và EXn → EX

(khi n → ∞).
9. (Bất đẳng thức Markov). Giả sử X là biến ngẫu nhiên khơng âm. Khi đó
nếu tồn tại EX thì với mọi ε > 0 ta có
P (X ≥ ε) ≤


EX
.
ε

1.1.7 Phương sai của biến ngẫu nhiên. Giả sử X : Ω → E là biến 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 .
Phương sai có các tính chất cơ bản sau đây:
1. DX = EX 2 − (EX)2 ;
2. DX ≥ 0;
3. DX = 0 khi X = EX = const h.c.c;
4. D(cX) = c2 DX .
1.1.8 Một số dạng hội tụ của các biến ngẫu nhiên. Ta nói dãy biến
ngẫu nhiên (Xn , n ≥ 1) hội tụ đến biến ngẫu nhiên X (khi n → ∞) là
- hội tụ yếu (theo phân phối) nếu lim Fn (x) = F (x), ∀x ∈ C(F ),
n→∞

trong đó Fn (x) và F (x) tương ứng là hàm phân phối của các biến ngẫu nhiên
D

Xn và X ; C(F ) là tập hợp các điểm mà tại đó F (x) liên tục, ký hiệu Xn −
→ X.


9

- hội tụ hầu chắc chắn (h.c.c) nếu P ( lim |Xn − X| = 0) = 1, ký hiệu
n→∞

hcc


Xn −−→ X .

- hội tụ theo xác suất nếu với mọi ε > 0 thì lim P (|Xn − X| > ε) = 0, ký
n→∞

P

hiệu Xn −
→ X.
1.1.9 Mẫu ngẫu nhiên và mẫu quan sát. Mẫu ngẫu nhiên kích thước n
đối với một biến ngẫu nhiên X là tập hợp n biến ngẫu nhiên X1 , X2 , . . . , Xn
độc lập, có cùng phân phối với X , kí hiệu là W = (X1 , X2 , . . . , Xn ).
Biến ngẫu nhiên X được gọi là biến ngẫu nhiên gốc.
Các biến ngẫu nhiên Xi được gọi là các bản sao của X .
Mẫu quan sát là thể hiện cụ thể của mẫu ngẫu nhiên W = (X1 , X2 , . . . , Xn ).
1.1.10 Đặc trưng của mẫu ngẫu nhiên
• Trung bình mẫu

- Giả sử W = (X1 , X2 , . . . , Xn ) là một mẫu ngẫu nhiên (của biến ngẫu
nhiên X ), khi đó trung bình mẫu là thống kê được cho bởi biểu thức
1
X=
n

n

Xi .
i=1

- Trung bình mẫu là một biến ngẫu nhiên.

- Vì mỗi bản sao Xi là biến ngẫu nhiên độc lập, cùng phân phối với X , do
đó nếu X có kì vọng m và phương sai σ 2 thì kì vọng và phương sai của
trung bình mẫu là:
E(X) = m,
• Phương sai mẫu S 2

D(X) =

σ2
.
n


10

- Là thống kê được xác định bởi biểu thức
1
S2 =
n−1

n

(Xi − X)2 .
i=1

- S 2 cũng là một biến ngẫu nhiên.
- Nếu X là biến ngẫu nhiên có phương sai σ 2 thì phương sai mẫu S 2 có kì
vọng E(S 2 ) = σ 2 .
• Tần suất mẫu


- Nếu A là một biến cố nào đó với xác suất xuất hiện A là p, nếu gọi
X ∼ A(p) và nếu W = (X1 , X2 , . . . , Xn ) là mẫu ngẫu nhiên kích thước n

của X , khi đó trung bình mẫu
1
X=
n

n

Xi
i=1

mà ta kí hiệu là f , là biến ngẫu nhiên chỉ tần suất xuất hiện biến cố A,
gọi là tần suất mẫu.
- Như vậy E(f ) = p và D(f ) =
1.2

(1 − p)p
.
n

Bài toán qui hoạch ngẫu nhiên

1.2.1 Bài toán. Bài tốn quy hoạch tổng qt có dạng: min{f (x) | x ∈ M }
trong đó f (x) là hàm số xác định trên tập M ⊂ Rn , lấy giá trị trong R.
Trong trường hợp các dữ liệu phụ thuộc các biến cố ngẫu nhiên, ta có bài
tốn quy hoạch ngẫu nhiên.
1.2.2 Bài tốn quy hoạch tuyến tính ngẫu nhiên. Bài tốn quy hoạch
tuyến tính ngẫu nhiên (SLP) có dạng

min {cx : Ax = b, x ≥ 0},


11

trong đó c = (cj ), b = (bi ), A = (aij ) là các đại lượng phụ thuộc tuyến tính
vào biến ngẫu nhiên θ = (t1 , t2 , . . . , tr ), nghĩa là có thể biểu diễn
cj = cj0 + cj1 t1 + · · · + cjr tr , j = 1, 2, . . . , n
bi = bi0 + bi1 t1 + · · · + bir tr , i = 1, 2, . . . , m
aij = aij0 + aij1 t1 + · · · + aijr tr , i = 1, 2, . . . , m; j = 1, 2, . . . , n.

Kí hiệu mn + n + m = s. Giả thiết rằng r ≤ s và các tham số tk , k = 1, 2, . . . , r
có cùng phân phối xác suất.
Kí hiệu T là tập tất cả các tham số θ, giả thiết rằng T là tập lồi.
T (x) là tập tất cả các θ sao cho thỏa mãn x ≥ 0.
T (θ) là tập tất cả các phương án x ứng với θ ∈ T .

Nếu T là tập lồi thì T (x) là tập lồi và nếu T là tập lồi đa diện thì T (x) là tập
lồi đa diện.
1.2.3 Các tính chất của bài tốn quy hoạch tuyến tính ngẫu nhiên
1.2.3.1 Nếu bài tốn (SLP ) chỉ có b là ngẫu nhiên. Khi đó tập M các
giá trị θ để T (θ) = ∅ là tập lồi. Tương tự, tập M tất cả các phương án x
sao cho T (x) = ∅ là tập lồi.
Chứng minh. - Lấy θ1 , θ2 ∈ M . Nếu Ax ≥ b(θ1 ) có nghiệm x1 , Ax ≥ b(θ2 ) có
nghiệm x2 . Với λ ∈ [0, 1], xét λθ1 + (1 − λ)θ2 thì hệ Ax ≥ b (λθ1 + (1 − λ)θ2 )
cũng sẽ có nghiệm, chẳng hạn đó là nghiệm λx1 + (1 − λ)x2 . Do vậy λθ1 + (1 −
λ)θ2 ∈ M với λ ∈ [0, 1]. Vậy M là tập lồi.

- Chứng minh tương tự, lấy x1 , x2 ∈ M . Nếu Ax1 ≥ b(θ) có nghiệm
θ1 , Ax2 ≥ b(θ) có nghiệm θ2 . Với λ ∈ [0, 1], xét λx1 + (1 − λ)x2 thì hệ

A (λx1 + (1 − λ)x2 ) ≥ b(θ) cũng sẽ có nghiệm, chẳng hạn đó là nghiệm λθ1 +
(1 − λ)θ2 . Do vậy λx1 + (1 − λ)x2 ∈ M với λ ∈ [0, 1]. Vậy M là tập lồi.

1.2.3.2 Định lý Kall. Để tồn tại phương án x của bài toán (SLP ) với


12

mọi cách chọn b thì điều kiện cần và đủ là tồn tại các số thực µj ≥ 0 và
số thực λj ≤ 0, (j = 1, 2, . . . , n), sao cho
m

n

λj Aj =
j=1

µj Aj ,
j=m+1

ở đây Aj là cột thứ j (j = 1, 2, . . . , n) của ma trận A = (aij ), hệ A1 , A2 , . . . , Am
là một cơ sở (nếu khác thì đánh số lại thứ tự).
Chứng minh. Xem tài liệu [2].
1.2.3.3 Nếu bài toán (SLP ) chỉ có c là ngẫu nhiên thì M ∗ là tập lồi.
Chứng minh. Ta kí hiệu T ∗ là tập các phương án tối ưu x∗ của bài toán đã
cho, M ∗ là tập các giá trị θ để T ∗ (θ) = ∅. Ta cần chứng minh với c ngẫu nhiên
thì M ∗ là tập lồi.
Thật vậy, lấy θ1 , θ2 ∈ M ∗ . Xét λθ1 + (1 − λ)θ2 , λ ∈ [0, 1], tương ứng phương
án tối ưu x∗ . Do chỉ có c ngẫu nhiên nên c không làm ảnh hưởng đến tập
phương án, do đó ta có

c(θ1 )x∗ ≤ c(θ1 )x, ∀x phương án
c(θ2 )x∗ ≤ c(θ2 )x, ∀x phương án.

Khi đó
c (λθ1 + (1 − λ)θ2 ) x∗ ≤ c (λθ1 + (1 − λ)θ2 ) x, ∀x phương án.

Suy ra λθ1 + (1 − λ)θ2 ∈ M ∗ với λ ∈ [0, 1] hay M ∗ là tập lồi.
1.2.3.4 Cho c(θ, x) là hàm lồi với x trên miền chấp nhận. Cực tiểu của
c(θ, x) là hàm lồi của b.

Chứng minh. Để đơn giản, ta chứng minh điều kiện Ax = b bao gồm cả điều
kiện x ≥ 0. Đặt b := b , giả sử cực tiểu của c(θ, x) là c(θ, x∗ ) = v(b ). Tương


13

tự, đặt b := b , giả sử cực tiểu của c(θ, x) là c(θ, y ∗ ) = v(b ). Với λ ∈ [0, 1], xét
b◦ = λb + (1 − λ)b . Đặt z ∗ = λx∗ + (1 − λ)y ∗ thì z ∗ ∈ M . Ta thấy
c(θ, z ∗ ) = c (θ, λx∗ + (1 − λ)y ∗ ) = λc(θ, x∗ ) + (1 − λ)c(θ, y ∗ )
≤ λc(θ, x) + (1 − λ)c(θ, x) = c(θ, x), ∀x ∈ M.

Như vậy, tương ứng với b◦ , ta nhận được giá trị cực tiểu z ∗ . Ta có
Az ∗ = A (λx∗ + (1 − λ)y ∗ ) = λAx∗ + (1 − λ)Ay ∗ = b.

Điều đó chứng tỏ tại b bài tốn có tập phương án khác rỗng.
Do c(θ, x) là hàm lồi với x ta được
v(b◦ ) = c(θ, z ∗ ) = c (θ, λx∗ + (1 − λ)y ∗ )
≤ λc(θ, x∗ ) + (1 − λ)c(θ, y ∗ ) = λv(b ) + (1 − λ)v(b ).

Vậy v(b) là hàm lồi với b.

1.2.3.5 Cho c(θ, x) là hàm lõm của θ xác định trên miền Ω lồi đóng.
Khi đó cực tiểu của c(θ, x) là hàm lõm của θ trong miền xác định đã cho.
Chứng minh. Lấy θ1 , θ2 tương ứng với các phương án tối ưu x(1) và x(2) , nghĩa
là
min { c(θ1 , x) } = c(θ1 , x(1) );
x

min { c(θ2 , x) } = c(θ2 , x(2) ).
x

Xét θ = λθ1 + (1 − λ)θ2 , λ ∈ [0, 1].
Do c(θ, x) là hàm lõm của θ nên ta có
min { c (λθ1 + (1 − λ)θ2 , x) }
x

≥ min { λc(θ1 , x) + (1 − λ)c(θ2 , x) }
x

≥ min λc(θ1 , x) + min(1 − λ)c(θ2 , x)
x

x

=λ min c(θ1 , x) + (1 − λ) min c(θ2 , x).
x

x


14


Vậy min {c(θ, x)} là hàm lõm của θ trên miền Ω .
x

1.3

Bài toán quy hoạch ngẫu nhiên rời rạc

1.3.1 Bài toán. Bài toán quy hoạch ngẫu nhiên đã nêu trên nếu M là tập
rời rạc thì ta có bài toán quy hoạch ngẫu nhiên rời rạc.
1.3.2 Các hướng tiếp cận giải. Trong luận văn này, chúng tôi xét các bài
tốn tối ưu có dạng
min { g(x) := EP G(x, W ) }.
x∈S

(1.1)

Ở đây W là một véc tơ ngẫu nhiên có phân phối xác suất P , S là một tập
hợp hữu hạn (ví dụ như S có thể là tập con hữu hạn của Rn với tọa độ
nguyên), G(x, w) là một hàm giá trị thực của hai biến véc tơ x và w và
EP G(x, W ) =

G(x, w)P (dw) là tương ứng với giá trị kì vọng. Chúng tơi

giả thiết rằng hàm giá trị kì vọng g(x) được xác định rõ. Với mỗi x ∈ S hàm
G(x, .) là P đo được và EP {|G(x, W )|} < ∞.

Thực tế chúng tôi quan tâm tới các bài toán với những đặc điểm sau:
1. Hàm giá trị kì vọng g(x) := EP G(x, W ) khơng thể viết được trong một
dạng đóng hoặc giá trị của nó khơng thể tính tốn được một cách dễ dàng.

2. Hàm G(x, w) là dễ tính tốn đối với x và w cho sẵn.
3. Tập hợp S các nghiệm cho phép (phương án), mặc dù hữu hạn nhưng rất
rộng, vì vậy cách tiếp cận bằng liệt kê là không thể thực hiện được.
Ta đã biết rằng các bài toán tối ưu rời rạc rất khó để giải. Một khó khăn
ở đây là hàm mục tiêu g(x) có thể phức tạp hoặc khó để tính tốn ngay cả
với phương pháp xấp xỉ. Bởi thế các bài toán tối ưu rời rạc ngẫu nhiên là
thực sự khó. Có một lý thuyết các bài tốn tối ưu rời rạc ngẫu nhiên trong đó


15

số nghiệm cho phép là đủ nhỏ để xác định công thức ước lượng của g(x) đối
với mỗi x. Quan tâm tới lý thuyết này có Hochberg và Tamhane, Bechhofer,
Santner và Goldsman, Futschik và Pflug và Nelson et al. Cách tiếp cận khác
đã được nghiên cứu bao gồm các phương pháp mô phỏng tốt để đếm các sự
kiện mà giá trị hàm mục tiêu không được biết đến một cách chính xác. Làm
việc trên vấn đề này bao gồm Gelfand và Milter, Alrefaei và Andradattir, Fox
và Heine, Gut - jahr và Pflug và Homem-de-Mello. Một cách tiếp cận nhánh để
giải bài toán quy hoạch nguyên ngẫu nhiên đã được gợi ý bởi Norkin, Ermokiev
và Ruszczynski và Norkin, Pflug và Ruszczynski. Còn Schultz, Stougie và Van
der Vlerk đã gợi ý một cách tiếp cận đại số để giải quy hoạch ngẫu nhiên với
việc nhờ đến cách sử dụng một hệ dàn của sự rút gọn cơ sở Grobner.
Trong luận văn này chúng tơi nghiên cứu một mơ hình hóa Monte Carlo
dựa trên cách tiếp cận các bài toán tối ưu rời rạc ngẫu nhiên. Ý tưởng cơ bản
thực sự đơn giản - một mẫu ngẫu nhiên của W được tạo thành và hàm giá
trị kì vọng được xấp xỉ bởi hàm trung bình mẫu tương ứng. Bài tốn tối ưu
trung bình mẫu được giải quyết và phương pháp được nhắc lại một vài lần cho
đến khi một tiêu chuẩn dừng được thỏa mãn. Ý tưởng sử dụng xấp xỉ trung
bình mẫu để giải quy hoạch ngẫu nhiên là một ý tưởng tự nhiên và đã được
sử dụng qua nhiều năm bởi nhiều tác giả khác nhau. Chẳng hạn, cách xấp xỉ

được sử dụng với điều kiện của bài toán cái túi ngẫu nhiên trong một bài báo
của Morton và Wood.


16

CHƯƠNG 2

PHƯƠNG PHÁP XẤP XỈ TRUNG BÌNH MẪU

2.1

Phép lấy mẫu

2.1.1 Bài tốn. Trong chương này, chúng tơi quan tâm tới việc giải bài toán
tối ưu rời rạc ngẫu nhiên dạng (1.1). Đặt
1
gˆN (x) =
N

N

G(x, W j )
j=1

và bài toán kết hợp
min gˆN (x).
x∈S

(2.1)


Chú ý rằng E[ˆ
gN (x)] = g(x).
Từ tập S cho phép là hữu hạn, bài toán (1.1) và (2.1) có các tập hợp tối ưu
khác rỗng, kí hiệu theo thứ tự là S ∗ và SˆN . Đặt v ∗ và vˆN biểu thị các giá trị
tối ưu
v ∗ := min g(x); vˆN := gˆN (x)
x∈S

của bài toán tương ứng. Chúng tôi cũng xem xét đến tập hợp các nghiệm ε tối ưu (xấp xỉ tối ưu với độ chính xác ε). Tức là, chúng ta xem xét tới các điểm
x¯ ∈ S , với ε ≥ 0, thỏa mãn g(¯
x) ≤ v ∗ + ε, lúc này ta nói x¯ là một nghiệm ε

- tối ưu của (1.1). Tương tự ta cũng có được khái niệm nghiệm ε - tối ưu của
(2.1). Tập hợp tất cả các nghiệm ε - tối ưu của (1.1) và (2.1) được biểu thị
ε . Rõ ràng, với ε = 0, tập hợp S ε trùng với tập hợp
theo thứ tự bởi S ε và SˆN
S ∗ và tập hợp Sˆε trùng với tập hợp SˆN .
N


17

2.1.2 Tính chất
Định lý sau đây cho thấy sự hội tụ với xác suất 1, đối với giá trị hàm mục
tiêu và nghiệm của bài tốn khi thực hiện cơng thức ước lượng thống kê nêu
trên.
2.1.2.1 Định lý. Hai tính chất sau đây là tương đương
i) vˆN → v ∗ , với xác suất 1, khi N → ∞
ε ⊂ S ε } xảy ra với xác suất 1, khi N đủ

ii) Cho bất kì ε ≥ 0, biến cố {SˆN

lớn.
Chứng minh. Theo luật mạnh số lớn đối với mỗi x ∈ S, gˆN (x) hội tụ tới g(x)
với xác suất 1 khi N → ∞. Từ tập S là hữu hạn và sự kết hợp một số hữu
hạn các tập hợp mà mỗi tập hợp có độ đo khơng cũng có độ đo khơng, nó cho
thấy rằng với xác suất 1, gˆN (x) hội tụ tới g(x) theo mọi x ∈ S . Vì vậy
δN := max |ˆ
gN (x) − g(x)| → 0, với xác suất 1, khi N → ∞.
x∈S

(2.2)

Từ |ˆ
vN − v ∗ | ≤ δN , với xác suất 1, vˆN → v ∗ khi N → ∞.
Với mỗi ε ≥ 0 cho trước xét số
p(ε) := min g(x) − v ∗ − ε.
x∈S\S ε

(2.3)

Từ bất kì x ∈ S \ S ε kéo theo g(x) > v ∗ + ε và tập hợp S là hữu hạn nên
p(ε) > 0.

Chọn N đủ lớn sao cho δN < p(ε)/2. Thì vˆN < v ∗ + p(ε)/2 và với bất kì
x ∈ S \S ε kéo theo gˆN (x) > v ∗ +ε+p(ε)/2. Nếu x ∈ S \S ε thì gˆN (x) > vˆN +ε
và do đó x khơng thuộc tập Sˆε . Vì vậy Sˆε ⊂ S ε .
N

N


δ ⊂S
ˆε . Từ
Chú ý rằng nếu δ là một số sao cho 0 ≤ δ ≤ ε thì S δ ⊂ S ε và SˆN
N
Định lý trên với bất kì δ ∈ [0, ε] biến cố {Sˆδ ⊂ S ε } xảy ra với xác suất 1, khi N
N

ε = {x∗ } với
đủ lớn. Nó cũng cho thấy rằng nếu S ε = {x∗ } là duy nhất, thì SˆN


18

xác suất 1 khi N đủ lớn. Trong thực tế, nếu bài tốn tất định (1.1) có nghiệm
tối ưu đơn trị x∗ , thì với xác suất 1 và N đủ lớn bài tốn xấp xỉ (2.1) có một
nghiệm tối ưu đơn trị xˆN và xˆN = x∗ . Xét tập A := { g(x) − v ∗ : x ∈ S }.
Tập A là một tập con của tập R+ các số không âm và |A| ≤ |S| và do đó A
là tập hữu hạn. Từ sự phân tích trên cho thấy với bất kì ε ∈ R+ \ A, biến cố
{Sˆε = S ε } xảy ra với xác suất 1 khi N đủ lớn.
N

Định lý nêu trên chưa nói gì tới tốc độ hội tụ của vˆN và Sˆδ . Trong phần tiếp
theo, sẽ đưa ra các tính chất về tốc độ hội tụ của chúng. Chúng ta sẽ sử dụng
lý thuyết của Large Deviations [5] để chỉ ra rằng với các điều kiện đã đưa ra
và δ ∈ [0, ε], xác suất của biến cố Sˆδ ⊂ S ε tiến nhanh với tốc độ hàm mũ khi
N → ∞. Để hiểu được phần cơ bản của lý thuyết của Large Deviations, chúng

tơi tóm tắt một số ý chính đã được vạch ra.
Ta xét biến ngẫu nhiên (giá trị thực) X có giá trị trung bình µ := E[X]. Hàm

tạo thành moment của nó M (t) := E[etX ] được xem như là một hàm giá trị
mở rộng, nó có thể nhận giá trị +∞. Do đó M (t) > 0 với mọi t ∈ R, M (0) = 1
và miền xác định {t : M (t) < +∞} của hàm tạo thành moment là một khoảng
chứa 0. Hàm liên hợp
I(z) := sup {tz − Λ(t)},

(2.4)

t∈R

của hàm tạo thành moment logarith Λ(t) := log M (t), gọi là hàm tốc độ (rate)
của X . Có thể thấy rằng cả hai hàm Λ(t) và I(.) đều lồi.
Xét dãy X1 , . . . , Xn của sự lặp lại thí nghiệm của biến ngẫu nhiên X độc
lập cùng phân phối và đặt Zn := N −1

N
i=1 Xi

là trung bình mẫu tương ứng.

Thì với bất kì số thực a và t ≥ 0 kéo theo P (ZN ≥ a) = P (etZN ≥ eta ) và từ
bất đẳng thức Chebyshev’s ta có
P (ZN ≥ a) ≤ e−ta E[etZN ] = e−ta [M (t/N )]N .


19

Bằng cách lấy logarith cả hai vế của bất đẳng thức, đặt t :=

t

và giá trị cực
N

tiểu trên t ≥ 0. Với a ≥ µ thì
1
log[P (ZN ≥ a] ≤ −I(a).
N

(2.5)

Chú ý rằng a ≥ µ nó chỉ cần lấy cực đại trong công thức (2.4) của I(a) với
t ≥ 0 và do đó sự ràng buộc này được bỏ đi. Bất đẳng thức (2.5) tương ứng

với giới hạn dưới của định lý độ lệch lớn của Cramer.
Hằng số I(a) trong (2.5) đã cho, có tốc độ hàm số mũ tốt nhất tại xác suất
P (ZN ≥ a) hội tụ tới 0 với a > µ. Điều này xác định từ cận dưới
lim inf
N →∞

1
log[P (ZN ≥ a)] ≥ −I(a)
N

(2.6)

của định lí độ lệch lớn của Cramer. Một điều kiện đủ đơn giản để (2.6) giữ
nguyên là hàm tạo thành moment M (t) là hữu hạn giá trị với mọi t ∈ R.
Hàm tốc độ I(z) có những đặc tính sau. Hàm I(z) là lồi, đạt cực tiểu tại
z = µ và I(µ) = 0. Hơn nữa, giả sử hàm tạo thành moment M (t) là hữu hạn


giá trị với mọi t trong một lân cận của t = 0 thì nó xác định bằng định lý hội
tụ được chi phối bởi M (t); và từ đó hàm Λ(t) là khác nhau rất nhiều tại t = 0
và Λ (0) = µ. Với a > µ đạo hàm của ψ(t) := ta − Λ(t) tại t = 0 lớn hơn 0 và
do đó ψ(t) > 0 với t > 0 đủ nhỏ. Người ta xác định rằng trong trường hợp đó
I(a) > 0. Cuối cùng giả sử X có phương sai hữu hạn σ 2 . Vậy thì I (µ) = 0 và
I (µ) = σ −2 và do đó bằng sự mở rộng của Taylor
(a − µ)2
I(a) =
+ o(|a − µ|2 ).
2
2σ

Kết quả, với a gần sát µ có thể xấp xỉ I(a) bởi

(2.7)

(a − µ)2
. Hơn nữa, với bất kì
2σ 2

ε˜ > 0, tồn tại lân cận N của µ sao cho
(a − µ)2
I(a) ≥
(2 + ε˜)σ 2

∀a ∈ N .

(2.8)



20

Trong thực tế có thể lấy ε˜ = 1.
Bây giờ chúng ta trở lại bài toán (1.1) và (2.1). Xét ε ≥ 0, δ ∈ [0, ε] và biến
cố { Sˆδ ⊂ S ε }. Ta có
N

δ
{ SˆN

Sε } =

{ gˆN (x) ≤ gˆN (y) + δ }.

(2.9)

x∈S\S ε y∈S

Do đó
δ
P (SˆN

S ε) ≤

{ gˆN (x) ≤ gˆN (y) + δ } .

P
x∈S\S ε

(2.10)


y∈S

Xét một ánh xạ u : S \ S ε → S . Từ (2.10) ta có
δ
P SˆN

Sε ≤

P gˆN (x) − gˆN (u(x)) ≤ δ .

(2.11)

x∈S\S ε

Bây giờ giả sử ánh xạ u(x) được chọn theo một cách mà với một số ε∗ > ε,
g(u(x)) ≤ g(x) − ε∗ với ∀x ∈ S \ S ε .

(2.12)

Chú ý rằng nếu u(.) là một ánh xạ từ S \ S ε vào trong tập S ∗ , tức là u(x) ∈ S ∗
với x ∈ S \ S ε , thì (2.12) giữ nguyên với ε∗ := min g(x) − v ∗ và ε∗ > ε từ
x∈S\S ε

khi tập S là hữu hạn. Vì vậy một ánh xạ u(.) mà thỏa mãn điều kiện (2.12)
luôn luôn tồn tại.
Với mỗi x ∈ S \ S ε , đặt
H(x, w) := G u(x), w −G(x, w).

Chú ý rằng E[H(x, W )] = g u(x) −g(x) và từ đó E[H(x, W )] ≤ −ε∗ . Đặt

W 1 , . . . , W n là mẫu ngẫu nhiên độc lập cùng phân phối của N phép thử theo

véc tơ ngẫu nhiên W và xét hàm trung bình mẫu
ˆ N (x) := 1
h
N

N

H(x, W j ) = gˆN u(x) −ˆ
gN (x).
j=1


21

Từ (2.11) ta có
δ
P SˆN

ˆ N (x) ≥ −δ .
P h

Sε ≤

(2.13)

x∈S\S ε

Giả sử Ix (.) là ký hiệu hàm tốc độ độ lệch lớn của H(x, W ). Bất đẳng thức

(2.13) cùng với (2.5) kéo theo
δ
P SˆN

e−N Ix (−δ) .

Sε ≤

(2.14)

x∈S\S ε

Cần chú ý rằng bất đẳng thức (2.14) trên khơng gần đúng và có hiệu quả với
bất kì mẫu ngẫu nhiên cỡ N .
Giả thiết (A). Với mỗi x ∈ S hàm tạo thành moment của biến ngẫu nhiên
H(x, W ) là hữu hạn giá trị trong một lân cận của 0.

Giả thiết (A) luôn được giữ nguyên trong những lý luận tiếp theo.
2.1.2.2 Định lý. Giả sử ε và δ là các số không âm sao cho δ ≤ ε. Khi
đó
δ
P SˆN

S ε ≤ S \ S ε e−N γ(δ,ε)

(2.15)

trong đó
γ(δ, ε) := min Ix (−δ).
x∈S\S ε


(2.16)

Hơn nữa, nếu giả thiết (A) vẫn đúng, thì γ(δ, ε) > 0.
Chứng minh. Bất đẳng thức (2.15) là một hệ quả trực tiếp của bất đẳng thức
(2.14). Nó kéo theo −δ > −ε∗ ≥ −E[H(x, W )]. Từ đó theo giả thiết (A) thì
Ix (−δ) > 0 với mỗi x ∈ S \ S ε . Điều này có nghĩa là γ(δ, ε) > 0.

Kết quả sau là một hệ quả trực tiếp của bất đẳng thức (2.14).
lim sup
N →∞

1
δ
log[1 − P SˆN
⊂ S ε ] ≤ −γ(δ, ε).
N

(2.17)


22

δ ⊂ S ε hội tụ nhanh
Bất đẳng thức (2.17) có nghĩa là xác suất của biến cố SˆN

theo hàm mũ khi N → ∞. Điều này gợi ý phương pháp Monte Carlo, kết hợp
với một phương pháp hiệu dụng để giải bài tốn xấp xỉ trung bình mẫu tất
định, có thể giải một cách hiệu quả loại bài tốn nghiên cứu dưới đây, đưa ra
hằng số γ(δ, ε) không quá nhỏ.

Từ (2.7) có
−δ − E[H(x, W )]
Ix (−δ) ≈
2σx2

2

(ε − δ)2
≥
2σx2

(2.18)

trong đó σx2 := Var [H(x, W )] = Var [G u(x), W −G(x, W )].
Vì vậy, hằng số γ(δ, ε) cho trong (2.16) có thể được xấp xỉ bởi
γ(δ, ε) ≈ min

x∈S\S ε

−δ − E[H(x, W )]
2σx2

2

(ε − δ)2
(ε − δ)2
≥
>
,
2

2
2σmax
2σmax

(2.19)

trong đó
2
σmax
:= max Var [G u(x), W −G(x, W )].
x∈S\S ε

(2.20)

Để minh họa một vài sự kéo theo của giới hạn (2.15) đối với sự bàn bạc độ
phức tạp của việc giải bài toán ngẫu nhiên, chúng ta đặt một mức ý nghĩa
α ∈ (0, 1) và ước lượng kích cỡ mẫu N cần để xác suất P Sˆδ ⊂ S ε trở thành
N

nhỏ nhất 1 − α. Bằng cách lợi dụng vế phải của (2.15) nhỏ hơn hoặc bằng với
α, ta được
1
N≥
log
γ(δ, ε)

S \ Sε
α

.


(2.21)

(ε − δ)2
Hơn nữa, từ (2.8) và (2.16) ta có γ(δ, ε) ≥
với mọi ε ≥ 0 đủ nhỏ. Do
2
3σmax
đó nó giữ nguyên với tất cả ε > 0 đủ nhỏ và δ ∈ [0, ε), một điều kiện đủ để

(2.21) đúng là
N≥

2
3σmax
|S|
log
.
(ε − δ)2
α

(2.22)


23

Cận dưới (2.22) có thể quá dè dặt đối với các ước lượng thực tế của các kích
cỡ mẫu được yêu cầu. Tuy nhiên, ước lượng (2.22) có hệ quả trực tiếp thú vị
đối với việc đánh giá độ phức tạp. Một đặc trưng của (2.22) là N chỉ phụ thuộc
logarith trên cả kích cỡ của tập S cho phép và trên cả xác suất cho phép α.

Một cách giải quyết thích hợp là ta đưa ra các giả thiết:
(1) kích cỡ của tập S cho phép là tăng theo số mũ với độ dài dữ liệu của bài
toán đưa vào,
2
phụ thuộc đa thức theo độ dài dữ liệu của bài toán đưa
(2) phương sai σmax

vào,
(3) độ phức tạp của việc tìm một nghiệm tối ưu δ đối với bài toán (2.1)
tăng đa thức theo độ dài dữ liệu đầu vào của bài tốn và kích cỡ mẫu N . Khi
đó một nghiệm tối ưu có thể được tạo thành trong thời gian đa thức theo độ
dài dữ liệu đầu vào của bài tốn, với xác suất ít nhất 1 − α, bài tốn (1.1) có
nghiệm là ε tối ưu.
Bây giờ giả sử bài tốn tất định có nghiệm tối ưu đơn trị x∗ , tức là S ∗ = {x∗ }
là duy nhất và ta xét bài toán xấp xỉ trung bình mẫu (2.1) có nghiệm tối ưu
đơn trị xˆN và xˆN = x∗ . Chúng tôi biểu thị sự kiện bởi {ˆ
xN = x∗ }. Hơn nữa, xét
ánh xạ u : S \ S ε → {x∗ }, tức là u(x) ≡ x∗ và hằng số tương ứng γ ∗ = γ(0, 0).
Vì vậy
γ∗ =

min

x∈S\{x∗ }

Ix (0),

(2.23)

với Ix (.) là hàm tốc độ độ lệch lớn của G(x∗ , W ) − G(x, W ). Chú ý rằng

E[G(x∗ , W ) − G(x, W )] = g(x∗ ) − g(x) và do đó E[G(x∗ , W ) − G(x, W )] < 0

với mỗi x ∈ S \ {x∗ }. Vì vậy, nếu giả thiết (A) vẫn giữ nguyên, tức là hàm tạo
thành moment của G(x∗ , W ) − G(x, W ) là hữu hạn giá trị trong một lân cận
của 0, thì γ ∗ > 0.
2.1.2.3 Định lý. Giả sử bài tốn tất định có nghiệm tối ưu đơn trị x∗ và


24

hàm tạo thành moment của mỗi biến ngẫu nhiên G(x∗ , W ) − G(x, W ), x ∈
S \ {x∗ }, là hữu hạn giá trị trên R. Khi đó
1
log[1 − P (ˆ
xN = x∗ )] = −γ ∗ .
N →∞ N
lim

(2.24)

Chứng minh. Từ (2.17) ta có
lim sup
N →∞

1
log[1 − P (ˆ
xN = x∗ )] ≤ −γ ∗ .
N

(2.25)


Xem như phần bù của biến cố {ˆ
xN = x∗ } được kí hiệu là {ˆ
xN = x∗ }. Biến
cố {ˆ
xN = x∗ } bằng với tập hợp các biến cố {ˆ
gN (x) ≤ gˆN (x∗ ) }, x ∈ S \ {x∗ }.
Do đó, với bất kì x ∈ S \ {x∗ },
P (ˆ
xN = x∗ ) ≥ P gˆN (x) ≤ gˆN (x∗ ) .

Bằng cách sử dụng giới hạn dưới (2.6) của định lí độ lệch lớn của Cramer ta
có bất đẳng thức
lim inf
N →∞

1
log[1 − P (ˆ
xN = x∗ )] ≥ −Ix (0).
N

(2.26)

luôn đúng với mọi x ∈ S \ {x∗ }. Bất đẳng thức (2.25) và (2.26) kéo theo
(2.24)
Phần tới chúng tơi xem xét tính gần đúng của giá trị hàm mục tiêu tối
ưu xấp xỉ trung bình mẫu vˆN . Với bất kì tập con S của S bất đẳng thức
vˆN ≤ min gˆN (x) luôn đúng. Trong thực tế, bằng cách lấy S = S ∗ , ta có
x∈S


vˆN ≤ min∗ gˆN (x) và từ đó
x∈S

E [ˆ
vN ] ≤ E {min∗ gˆN (x)} ≤ min∗ E [ gˆN (x) ] = v ∗ .
x∈S

x∈S

Vì vậy, cơng thức ước lượng vˆN có sai số âm.
Từ Định lý 2.1.2.1, với xác suất 1, khi N đủ lớn, tập hợp SˆN các nghiệm tối
ưu của bài toán xấp xỉ trung bình mẫu được bao gồm trong S ∗ . Trong trường


25

hợp đó
vˆN = min gˆN (x) ≥ min∗ gˆN (x).
x∈SˆN

x∈S

Ta có thể thấy rằng bất đẳng thức ngược lại ln đúng, do vậy với xác suất 1,
vˆN − min∗ gˆN (x) = 0 khi N đủ lớn. Nhân cả hai vế của phương trình này với
x∈S
√
√
N , ta có với xác suất 1, N [ˆ
vN − min∗ gˆN (x)] = 0 khi N đủ lớn và do đó
x∈S

√
lim N [ˆ
vN − min∗ gˆN (x)] = 0 với xác suất 1.
(2.27)
N →∞
x∈S
√
Từ sự hội tụ với xác suất 1 nghĩa là hội tụ theo xác suất, từ (2.28) có N [ˆ
vN −
min gˆN (x)] hội tụ theo xác suất tới 0, tức là

x∈S ∗

vˆN = min∗ gˆN (x) + op (N −1/2 ).
x∈S

Hơn nữa, từ v ∗ = g(x) với bất kì x ∈ S ∗ ,
√
√
√
N [ min∗ gˆN (x)] − v ∗ ] = N min∗ [ gˆN (x)] − v ∗ ] = min∗ { N [ gˆN (x) − g(x) ]}.
x∈S

x∈S

x∈S

Giả sử với mỗi x ∈ S , phương sai
σ 2 (x) := V ar [G(x, W )]


tồn tại. Khi đó theo định lý Central Limit, với bất kì x ∈ S ,

(2.28)
√

N [ˆ
gN (x) − g(x)]

hội tụ theo phân phối tới một biến phân phối chuẩn Z(x) với giá trị trung bình
0 và phương sai σ 2 (x). Hơn nữa, lại theo định lý Central Limit, biến ngẫu nhiên
Z(x) có hàm covariance giống như G(x, W ). Điều đó cho thấy giữa Z(x) và
Z(x ) cũng giống như giữa G(x, W ) và G(x , W ), với bất kì x, x ∈ S . Do đó

chúng ta có được Định lý 2.1.2.4 sau đây (chúng tôi sử dụng “ ⇒” để biểu thị
sự hội tụ theo phân phối).
2.1.2.4. Định lý. Giả sử phương sai σ 2 (x), xác định trong (2.28), tồn
tại với mọi x ∈ S ∗ . Khi đó
√
N (ˆ
vN − v ∗ ) ⇒ min∗ Z(x),
x∈S

(2.29)


26

trong đó Z(x) là biến ngẫu nhiên phân phối chuẩn với giá trị trung bình 0
và hàm covariance được cho bởi hàm covariance tương ứng của G(x, W ).
Trong thực tế, nếu S ∗ = {x∗ } là duy nhất, thì

√
N (ˆ
vN − v ∗ ) ⇒ N 0, σ 2 (x∗ ) .

(2.30)

Mặc dù với bất kì x cho sẵn giá trị trung bình (giá trị kỳ vọng) của Z(x)
bằng 0. Giá trị cực tiểu của Z(x) trên một tập con S của S có thể khơng âm
và trở thành nhỏ hơn với một tập S rộng hơn. Vì vây, từ (2.30) cho thấy rằng
với bài toán điều kiện yếu mà tập hợp các nghiệm tối ưu hoặc gần tối ưu rộng,
công thức ước lượng vˆN của v ∗ sẽ có sai số lớn.
2.2

Thuật tốn xấp xỉ trung bình mẫu

2.2.1 Đặt vấn đề. Như chúng ta đã biết, nhiều bài tốn tối ưu rời rạc ngẫu
nhiên rất khó để giải. Trong luận văn này, chúng tôi đưa ra một phương pháp
xấp xỉ trung bình mẫu để giải các bài toán tối ưu rời rạc ngẫu nhiên. Ý tưởng
cơ bản của phương pháp này là một mẫu ngẫu nhiên được tạo thành và một
cách logic hàm giá trị kì vọng được xấp xỉ bởi hàm trung bình mẫu tương ứng.
Bài tốn tối ưu trung bình mẫu thu được được giải quyết và phương pháp được
lặp lại cho đến khi một tiêu chuẩn dừng được thỏa mãn.
2.2.2 Sự lựa chọn kích cỡ mẫu. Trong một thuật tốn, một kích cỡ mẫu
hữu hạn hoặc một dãy các kích cỡ mẫu hữu hạn phải được lựa chọn và thuật
toán phải dừng sau một lượng thời gian hữu hạn. Một câu hỏi quan trọng là
làm thế nào những sự lựa chọn này sẽ được thực hiện. Ước lượng (2.22) đưa
ra một giới hạn trên kích cỡ mẫu được u cầu để tìm một nghiệm ε - tối ưu
với xác suất nhỏ nhất 1 − α. Ước lượng này có hai khuyết điểm cho mục đích
tính tốn. Đầu tiên, với nhiều bài tốn thật khơng dễ để tính ước lượng, bởi
2

vì σmax
và trong một số bài tốn |S| cũng có thể tính vất vả. Thứ hai, giới