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ử Ω 6= ∅ 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:
Lớp F ⊂ P(Ω) được gọi là một σ - đại số nếu thỏa mãn:
Không gian đo và độ đo xác suất được định nghĩa bởi cặp (Ω,F), trong đó Ω là một tập không rỗng và 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:
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:
Không gian xác suất được định nghĩa bởi bộ ba (Ω, F, P), trong đó Ω là tập hợp không rỗng, F là σ - đại số các tập con của Ω, và P là độ đo xác suất trên F.
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ố.
Biến ngẫu nhiên được định nghĩa trong không gian xác suất (Ω,F, P), với G là σ - đại số con của σ - đại số F Ánh xạ X : Ω → R được xem là biến ngẫu nhiên G - đo được nếu với mọi B ∈ B(R), điều kiện xác suất được thỏa mãn.
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.
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ố
F X (x) =P[X < x], (x ∈ R) được gọi là hàm phân phối của biến ngẫu nhiên
Hàm phân phối có tính chất:
2 a < b thì F(b)−F(a) = P(a ≤X < b), do đó F(x) là hàm không giảm;
Giới hạn khi x tiến tới dương vô cùng của hàm F(x) là 1, trong khi giới hạn khi x tiến tới âm vô cùng là 0 Đối với một biến ngẫu nhiên X: (Ω,F, P) → (R, B(R)), nếu tích phân Lebesgue của X theo độ đo P tồn tại, thì giá trị này được gọi là kì vọng của X và được ký hiệu là EX.
Kì vọng có các tính chất cơ bản sau đây:
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;
P i x 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).
6 (Đị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).
7 (Bổ đề Fatou) Nếu X n ≥Y với mọi n≥ 1 và EY > −∞ thì
8 (Đị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 → ∞).
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ó
Phương sai của biến ngẫu nhiên X, ký hiệu là DX, được định nghĩa là E(X − EX)², với điều kiện nó tồn tại Phương sai này thể hiện sự phân tán của biến ngẫu nhiên quanh giá trị kỳ vọng EX Các tính chất cơ bản của phương sai bao gồm khả năng đo lường độ biến thiên và sự ổn định của dữ liệu.
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 (X n , 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 n→∞F n (x) = F(x),∀x ∈ C(F), trong đó F n (x) và F(x) tương ứng là hàm phân phối của các biến ngẫu nhiên
X n và X; C(F) là tập hợp các điểm mà tại đó F(x) liên tục, ký hiệuX n −→ D X.
- hội tụ hầu chắc chắn (h.c.c) nếu P( lim n→∞|X n − X| = 0) = 1, ký hiệu
- hội tụ theo xác suất nếu với mọi ε > 0 thì lim n→∞P(|X n −X|> ε) = 0, ký hiệu X n −→ P X.
Mẫu ngẫu nhiên kích thước n đối với biến ngẫu nhiên X bao gồm n biến ngẫu nhiên độc lập, đồng phân phối với X, được ký hiệu là W = (X1, X2, , Xn) Mẫu này giúp nghiên cứu và phân tích các đặc tính của biến ngẫu nhiên trong thống kê.
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 X i đượ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ênW = (X 1 , X 2 , , X n ). 1.1.10 Đặc trưng của mẫu ngẫu nhiên
- Giả sử W = (X 1 , X 2 , , X n ) 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
- Trung bình mẫu là một biến ngẫu nhiên.
Mỗi bản sao X_i là một biến ngẫu nhiên độc lập và cùng phân phối với X Nếu X có kì vọng m và phương sai σ², thì kì vọng và phương sai của trung bình mẫu sẽ tương ứng là m và σ²/n, trong đó n là số lượng bản sao.
- Là thống kê được xác định bởi biểu thức
- 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
- 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 = (X 1 , X 2 , , X n ) là mẫu ngẫu nhiên kích thước n của X, khi đó trung bình mẫu
X i 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.
Bài toán qui hoạch ngẫu nhiên
Bài toán quy hoạch tổng quát được định nghĩa là tối thiểu hóa hàm số f(x) trên tập M, với M là một tập con của R^n Khi các dữ liệu liên quan đến các biến cố ngẫu nhiên, bài toán này trở thành bài toán quy hoạch ngẫu nhiên.
Bài toán quy hoạch tuyến tính ngẫu nhiên (SLP) được mô tả dưới dạng tối thiểu hóa hàm mục tiêu min{cx : Ax = b, x ≥0} Trong đó, các đại lượng c, b, A phụ thuộc tuyến tính vào biến ngẫu nhiên θ = (t1, t2, , tr) Cụ thể, c j có thể được biểu diễn dưới dạng c j = c j0 + c j1 t1 + + c jr tr với j = 1, 2, , n; b i được xác định bởi b i = b i0 + b i1 t1 + + b ir tr với i = 1, 2, , m; và a ij được biểu diễn bởi a ij = a ij0 + a ij1 t1 + + a ijr tr với i = 1, 2, , m và j = 1, 2, , n.
Kí hiệumn+n+m = s Giả thiết rằng r ≤ s và các tham sốt k , 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.
Bài toán quy hoạch tuyến tính ngẫu nhiên (SLP) có những tính chất quan trọng Nếu chỉ có b là ngẫu nhiên, thì tập M các giá trị θ để T(θ) khác rỗng là một tập lồi Tương tự, tập M' chứa tất cả các phương án x sao cho T(x) cũng khác rỗng cũng là một tập lồi.
Để chứng minh rằng tập M là tập lồi, giả sử θ₁, θ₂ ∈ M Nếu hệ phương trình Ax ≥ b(θ₁) có nghiệm x₁ và Ax ≥ b(θ₂) có nghiệm x₂, thì với λ ∈ [0,1], ta xét λθ₁ + (1−λ)θ₂ Hệ Ax ≥ b(λθ₁ + (1−λ)θ₂) cũng sẽ có nghiệm, cụ thể là nghiệm λx₁ + (1−λ)x₂ Do đó, λθ₁ + (1−λ)θ₂ cũng thuộc M, chứng minh rằng M là tập lồi.
- Chứng minh tương tự, lấy x 1 , x 2 ∈ M 0 Nếu Ax 1 ≥ b(θ) có nghiệm θ 1 , Ax 2 ≥ b(θ) có nghiệm θ 2 Với λ ∈ [0,1], xét λx 1 + (1 − λ)x 2 thì hệ
A(λx 1 + (1−λ)x 2 ) ≥ b(θ) cũng sẽ có nghiệm, chẳng hạn đó là nghiệm λθ 1 +
Theo định lý Kall, để tồn tại phương án x cho bài toán (SLP) với mọi cách chọn b, điều kiện cần và đủ là phải có các số thực a_j ≥ 0 và các số thực λ_j ≤ 0 (với j = 1, 2, , n) Điều này có nghĩa là λx_1 + (1−λ)x_2 thuộc tập M_0, với λ nằm trong khoảng [0,1], cho thấy M_0 là tập lồi.
X j=m+1 à j A j , ở đây A j là cột thứ j (j = 1,2, , n)của ma trận A = (a ij ),hệ A 1 , A 2 , , A m 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 ta ký hiệu T ∗ là tập hợp các phương án tối ưu x ∗ của bài toán đã cho, và M ∗ là tập hợp các giá trị θ sao cho T ∗ (θ) không rỗng Mục tiêu của chúng ta là chứng minh rằng với c ngẫu nhiên, tập M ∗ là tập lồi.
Khi xét hai yếu tố θ 1 và θ 2 thuộc tập M ∗, ta có thể biểu diễn một phương án tối ưu x ∗ dưới dạng λθ 1 + (1−λ)θ 2 với λ nằm trong khoảng [0,1] Do chi phí c là ngẫu nhiên, nó không ảnh hưởng đến tập phương án, từ đó dẫn đến kết luận rằng c(θ 1 )x ∗ ≤ c(θ 1 )x và c(θ 2 )x ∗ ≤ c(θ 2 )x cho mọi phương án x Kết quả là, ta có c(λθ 1 + (1−λ)θ 2 )x ∗ ≤ c(λθ 1 + (1−λ)θ 2 )x cho mọi phương án x.
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 điều kiện Ax = b với x ≥ 0, ta đặt b := b 0 và giả sử cực tiểu của c(θ, x) là c(θ, x ∗ ) = v(b 0 ) Tương tự, với b := b 00, ta có cực tiểu c(θ, y ∗ ) = v(b 00 ) Xét b ◦ = λb 0 + (1−λ)b 00 với λ ∈ [0,1], ta đặt z ∗ = λx ∗ + (1−λ)y ∗, và nhận thấy z ∗ thuộc M 0 Kết quả là c(θ, z ∗ ) = c(θ, λx ∗ + (1−λ)y ∗ ) = λc(θ, x ∗ ) + (1−λ)c(θ, y ∗ ).
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 toá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 ∗ )
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à minx {c(θ 1 , x)} = c(θ 1 , x (1) ); minx {c(θ 2 , x)} = c(θ 2 , x (2) ).
Do c(θ, x) là hàm lõm của θ nên ta có minx {c(λθ 1 + (1−λ)θ 2 , x)}
Vậy min x {c(θ, x)} là hàm lõm của θ trên miền Ω.
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.
Trong luận văn này, chúng tôi nghiên cứu các bài toán tối ưu với dạng minx∈S {g(x) := E P G(x, W)}, trong đó W là véc tơ ngẫu nhiên với phân phối xác suất P, S là một tập hợp hữu hạn, ví dụ như tập con hữu hạn của R n với tọa độ nguyên Hàm G(x, w) được định nghĩa là hàm giá trị thực của hai biến véc tơ x và w.
Hàm G(x, w)P(dw) đại diện cho giá trị kỳ vọng, với giả thiết rằng hàm giá trị kỳ vọng g(x) được xác định rõ Đối với mỗi x thuộc S, hàm G(x, ) là P đo được và có E P {|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) := E P 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 toán được một cách dễ dàng.
2 Hàm G(x, w) là dễ tính toá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.
Các bài toán tối ưu rời rạc thường rất khó giải, đặc biệt khi hàm mục tiêu g(x) phức tạp và khó tính toán Các bài toán tối ưu rời rạc ngẫu nhiên càng trở nên thách thức hơn, nhưng lý thuyết trong lĩnh vực này cho phép xác định công thức ước lượng g(x) cho mỗi x với số nghiệm cho phép nhỏ Nhiều nhà nghiên cứu như Hochberg, Tamhane, Bechhofer, Santner, Goldsman, Futschik, Pflug và Nelson đã quan tâm đến lý thuyết này Các phương pháp mô phỏng cũng đã được nghiên cứu để đếm các sự kiện khi giá trị hàm mục tiêu không rõ ràng, với sự đóng góp của Gelfand, Milter, Alrefaei, Andradattir, Fox, Heine, Gutjahr, Pflug và Homem-de-Mello Một phương pháp nhánh để giải bài toán quy hoạch nguyên ngẫu nhiên đã được Norkin, Ermokiev, Ruszczynski, và Norkin, Pflug, Ruszczynski đề xuất Cuối cùng, Schultz, Stougie và Van der Vlerk đã gợi ý một cách tiếp cận đại số thông qua hệ dàn của sự rút gọn cơ sở Grobner để giải quy hoạch ngẫu nhiên.
Trong luận văn này, chúng tôi nghiên cứu mô hình hóa Monte Carlo dựa trên các bài toán tối ưu rời rạc ngẫu nhiên Mô hình này sử dụng một mẫu ngẫu nhiên của W để xấp xỉ hàm giá trị kỳ vọng bằng hàm trung bình mẫu Bài toán tối ưu trung bình mẫu được giải quyết lặp đi lặp lại cho đến khi đạt tiêu chuẩn dừng Việc sử dụng xấp xỉ trung bình mẫu để giải quy hoạch ngẫu nhiên là một phương pháp tự nhiên, đã được nhiều tác giả áp dụng trong suốt nhiều năm, như trong bài báo của Morton và Wood về bài toán cái túi ngẫu nhiên.
PHƯƠNG PHÁP XẤP XỈ TRUNG BÌNH MẪU
Phép lấy mẫu
2.1.1 Bài toá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 ˆ g N (x) = 1
G(x, W j ) và bài toán kết hợp minx∈S gˆ N (x) (2.1)
Trong bối cảnh tập S 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 được ký hiệu là S ∗ và Sˆ N Giá trị tối ưu được định nghĩa là v ∗ := min x∈S g(x) và ˆv N := ˆg N (x) cho từng bài toán tương ứng Ngoài ra, chúng tôi cũng nghiên cứu các nghiệm ε-tối ưu, tức là các điểm ¯ x ∈ S thỏa mãn g(¯x) ≤ v ∗ +ε với ε ≥ 0, trong đó x¯ được coi là một nghiệm ε.
Tối ưu của (1.1) và khái niệm nghiệm ε - tối ưu của (2.1) cho phép ta xác định tập hợp tất cả các nghiệm ε - tối ưu, được ký hiệu là S ε và Sˆ N ε Khi ε = 0, tập hợp S ε sẽ trùng với tập hợp ban đầu, cho thấy sự liên kết giữa các nghiệm tối ưu trong hai trường hợp này.
S ∗ và tập hợp Sˆ N ε trùng với tập hợp Sˆ N
Định lý dưới đây chứng minh rằng giá trị hàm mục tiêu và nghiệm của bài toán sẽ hội tụ với xác suất 1 khi áp dụng công thức ước lượng thống kê đã nêu.
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 → ∞ ii) Cho bất kì ε ≥ 0, biến cố {Sˆ N ε ⊂ S ε } xảy ra với xác suất 1, khi N đủ lớn.
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 tiến tới vô cùng Vì tập S là hữu hạn và sự kết hợp của một số hữu hạn các tập hợp có độ đo không cũng có độ đo không, điều này chứng minh rằng với xác suất 1, gˆ N (x) hội tụ tới g(x) cho mọi x ∈ S Do đó, δ N := max x∈S |ˆg N (x)−g(x)| tiến tới 0 với xác suất 1 khi N tiến tới vô cùng.
Từ |ˆv N −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 x∈S\S ε g(x)−v ∗ −ε (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 theogˆ N (x) > v ∗ +ε+p(ε)/2 Nếux ∈ S\S ε thì gˆ N (x) > ˆv N +ε và do đó x không thuộc tập Sˆ N ε Vì vậy Sˆ N ε ⊂ S ε
Nếu δ nằm trong khoảng [0, ε], thì ta có S δ ⊂ S ε và Sˆ N δ ⊂ Sˆ N ε Theo định lý, với bất kỳ δ ∈ [0, ε], biến cố {Sˆ N δ ⊂ S ε} xảy ra với xác suất 1 khi N đủ lớn Nếu S ε = {x ∗} là duy nhất, thì Sˆ N ε cũng sẽ bằng {x ∗} với xác suất 1 khi N lớn Trong trường hợp bài toán xác định (1.1) có nghiệm tối ưu đơn trị x ∗, thì với xác suất 1, bài toán xấp xỉ (2.1) sẽ có nghiệm tối ưu đơn trị xˆ N và xˆ N = x ∗ khi N đủ lớn Xét tập A := {g(x) − v ∗ : x ∈ S}, tập A là tập con của R+ với |A| ≤ |S|, nên A là hữu hạn Do đó, với bất kỳ ε ∈ R+\A, biến cố {Sˆ N ε = S ε} xảy ra với xác suất 1 khi N đủ lớn Định lý chưa đề cập đến tốc độ hội tụ của vˆ N và Sˆ δ, và trong phần tiếp theo, chúng ta sẽ khảo sát các tính chất về tốc độ hội tụ của chúng, sử dụng lý thuyết Large Deviations để chỉ ra rằng xác suất của biến cố Sˆ δ ⊂ S ε tiến nhanh với tốc độ hàm mũ khi δ ∈ [0, ε].
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 X có giá trị thực với giá trị trung bình E[X] Hàm tạo thành moment M(t) = E[e^(tX)] là một hàm giá trị mở rộng, có thể nhận giá trị +∞ Điều này dẫn đến M(t) > 0 với mọi t ∈ R, và M(0) = 1 Miền xác định của hàm tạo thành moment, {t : M(t) < +∞}, là một khoảng chứa 0.
{tz −Λ(t)}, (2.4) của hàm tạo thành moment logarithΛ(t) := logM(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 là kết quả của các thí nghiệm lặp lại của biến ngẫu nhiên X độc lập và cùng phân phối, ta định nghĩa ZN = N^(-1) ∑(i=1 đến N) Xi là trung bình mẫu Với bất kỳ số thực a và t ≥ 0, ta có P(ZN ≥ a) = P(e^(tZN) ≥ e^(ta)) Từ bất đẳng thức Chebyshev, ta có thể áp dụng để phân tích xác suất này.
Bằng cách lấy logarith cả hai vế của bất đẳng thức, đặt t 0 := t
N và giá trị cực tiểu trờn t 0 ≥ 0 Với a ≥ à thỡ
N log[P(Z N ≥ a] ≤ −I(a) cho thấy rằng khi a ≥ a, chỉ cần lấy giá trị cực đại trong công thức (2.4) của I(a) với t ≥ 0, do đó ràng buộc này không còn cần thiết Bất đẳng thức (2.5) phản ánh 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(Z N ≥ a) hội tụ tới 0 với a > à Điều này xỏc định từ cận dưới lim inf
Theo định lý độ lệch lớn của Cramer, ta có N log[P(Z N ≥ a)] ≥ −I(a) Để điều này giữ nguyên, một điều kiện đủ đơn giản là hàm tạo thành moment M(t) phải có giá trị hữu hạn với mọi t ∈ R Hàm tốc độ I(z) có đặc tính lồi, đạt cực tiểu tại z = a và I(a) = 0 Nếu hàm tạo thành moment M(t) hữu hạn trong lân cận của t = 0, nó sẽ được xác định bởi định lý hội tụ chi phối M(t); từ đó, hàm Λ(t) có sự khác biệt rõ rệt tại t = 0 với Λ'(0) = a Đối với a > a, đạo hàm của ψ(t) := ta − Λ(t) tại t = 0 sẽ lớn hơn 0, dẫn đến ψ(t) > 0 với t > 0 đủ nhỏ.
I(a) > 0 Cuối cựng giả sử X cú phương sai hữu hạn σ 2 Vậy thỡ I 0 (à) = 0 và
I 00 (à) =σ −2 và do đú bằng sự mở rộng của Taylor
Kết quả, với a gần sỏt à cú thể xấp xỉ I(a) bởi (a − à)
2σ 2 Hơn nữa, với bất kì ˜ ε > 0, tồn tại lõn cận N của à sao cho
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ˆ N δ ⊂ S ε } Ta có
Xét một ánh xạ u : S \S ε 7→S Từ (2.10) ta có
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)
Nếu u(.) là một ánh xạ từ S\S ε vào S ∗, với u(x) ∈ S ∗ cho x ∈ S\S ε, thì điều kiện (2.12) vẫn giữ nguyên với ε ∗ := min x∈S\S ε g(x)−v ∗ và ε ∗ > ε khi S là hữu hạn Do đó, luôn tồn tại một ánh xạ u(.) thỏa mãn điều kiện (2.12).
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 ˆh N (x) := 1
Giả sử I x (.) 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
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 đó
S \S ε e −N γ (δ,ε) (2.15) trong đó γ(δ, ε) := min x∈S\S ε I x (−δ) (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ì
I x (−δ) > 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
Bất đẳng thức (2.17) chỉ ra rằng xác suất của biến cố Sˆ N δ ⊂ S ε hội tụ nhanh theo hàm mũ khi N tiến tới vô cùng Điều này mở ra khả năng áp dụng phương pháp Monte Carlo, kết hợp với một phương pháp hiệu quả để giải quyết bài toán xấp xỉ trung bình mẫu tất định Nhờ đó, chúng ta có thể giải quyết hiệu quả các bài toán nghiên cứu liên quan, đồng thời đưa ra hằng số γ(δ, ε) không quá nhỏ.
Vì vậy, hằng số γ(δ, ε) cho trong (2.16) có thể được xấp xỉ bởi γ(δ, ε) ≈ min x∈S\S ε
2σ 2 max , (2.19) trong đó σ 2 max := max x∈S\S ε Var [G u(x), W
Để minh họa ảnh hưởng của giới hạn (2.15) đến độ phức tạp trong việc giải bài toán ngẫu nhiên, chúng ta xác định một mức ý nghĩa α ∈ (0,1) và ước lượng kích cỡ mẫu N cần thiết để xác suất P Sˆ N δ ⊂S ε giảm xuống mức tối thiểu 1−α Bằng cách sử dụng điều kiện từ vế phải của (2.15) nhỏ hơn hoặc bằng α, chúng ta có thể đạt được kết quả mong muốn.
Hơn nữa, từ (2.8) và (2.16) ta có γ(δ, ε) ≥ (ε−δ) 2
3σ max 2 với mọi ε ≥ 0 đủ nhỏ Do đó nó giữ nguyên với tất cả ε > 0 đủ nhỏ và δ ∈ [0, ε), một điều kiện đủ để (2.21) đúng là
Cận dưới (2.22) có thể quá dè dặt trong việc ước lượng kích cỡ mẫu cần thiết, nhưng lại mang đến những hệ quả thú vị cho việc đánh giá độ phức tạp Đặc điểm nổi bật của (2.22) là N chỉ phụ thuộc vào logarith của kích cỡ tập S cho phép và xác suất cho phép α Để giải quyết vấn đề này, chúng ta cần đưa ra các giả thiết thích hợp.
(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ương sai σ 2 max phụ thuộc đa thức theo độ dài dữ liệu của bài toán đưa vào,
Độ phức tạp của việc tìm nghiệm tối ưu δ cho bài toán (2.1) tăng theo độ dài dữ liệu đầu vào và kích cỡ mẫu N Nghiệm tối ưu có thể được xác định trong thời gian đa thức dựa trên dữ liệu đầu vào, với xác suất ít nhất 1−α, đảm bảo rằng bài toán (1.1) có nghiệm là ε tối ưu.
Giả sử bài toán xác định có nghiệm tối ưu duy nhất x ∗, tức là S ∗ = {x ∗ } Chúng ta xem xét bài toán xấp xỉ trung bình mẫu (2.1) với nghiệm tối ưu đơn trị xˆ N và xˆ N = x ∗, được biểu thị bởi sự kiện {ˆx N = x ∗ } Hơn nữa, ánh xạ u : S\S ε 7→ {x ∗ } được định nghĩa là u(x) ≡ x ∗, với hằng số tương ứng γ ∗ = γ(0,0).
Thuật toán xấp xỉ trung bình mẫu
Trong nhiều bài toán tối ưu rời rạc ngẫu nhiên, việc tìm kiếm giải pháp là rất khó khăn Luận văn này giới thiệu một phương pháp xấp xỉ trung bình mẫu nhằm giải quyết các bài toán này Phương pháp dựa trên việc tạo ra một mẫu ngẫu nhiên và sử dụng hàm trung bình mẫu để xấp xỉ hàm giá trị kỳ vọng Quá trình giải bài toán tối ưu trung bình mẫu sẽ được lặp lại cho đến khi đạt được tiêu chuẩn dừng nhất định.
Trong việc lựa chọn kích cỡ mẫu cho thuật toán, cần xác định một kích cỡ hữu hạn và dừng sau một khoảng thời gian nhất định Một ước lượng quan trọng (2.22) cung cấp giới hạn trên kích cỡ mẫu cần thiết để tìm nghiệm ε-tối ưu với xác suất nhỏ nhất 1−α Tuy nhiên, ước lượng này có hai nhược điểm: khó khăn trong việc tính toán σ² max và |S| trong nhiều bài toán thực tế, cùng với việc giới hạn này không đảm bảo độ chính xác thực tế cho kích cỡ mẫu Để lựa chọn N, cần cân nhắc giữa độ rộng của N và độ chính xác của hàm mục tiêu, nhằm cải thiện nghiệm tối ưu và chặt chẽ hơn cho khoảng tối ưu Tuy nhiên, độ phức tạp trong việc giải bài toán xấp xỉ trung bình mẫu (2.1) có thể tăng lên theo cấp số nhân với kích cỡ mẫu N, do đó việc lựa chọn kích cỡ mẫu là rất quan trọng.
Sự cân đối giữa chất lượng nghiệm tối ưu của bài toán xấp xỉ trung bình mẫu và nỗ lực tính toán là rất quan trọng Kích cỡ mẫu N có thể được điều chỉnh dựa trên kết quả tính toán sơ bộ Việc ước lượng giá trị mục tiêu g(x) từ trung bình mẫu gˆ N (x) yêu cầu ít nỗ lực hơn so với giải bài toán xấp xỉ trung bình mẫu Mặc dù việc xem xét độ phức tạp tính toán khuyến khích chọn kích cỡ mẫu N nhỏ, nhưng nó cũng mở ra hướng đi để chọn kích cỡ mẫu N 0 lớn hơn nhằm có được ước lượng chính xác gˆ N 0 (ˆx N ) cho giá trị mục tiêu g(ˆx N ) Độ chính xác của ước lượng trung bình mẫu gˆ N 0 (ˆx N ) được đo bằng phương sai mẫu S N 2 0(ˆx N )/N 0, có thể tính từ mẫu cỡ N 0 Việc lựa chọn N 0 cần cân nhắc giữa nỗ lực tính toán và độ chính xác, được đo bởi S 2.
Nếu độ phức tạp tính toán của việc giải bài toán xấp xỉ trung bình mẫu tăng nhanh hơn tuyến tính theo kích cỡ mẫu N, thì việc chọn kích cỡ mẫu N nhỏ hơn và thực hiện nhiều bài toán xấp xỉ trung bình mẫu với các mẫu độc lập cùng phân phối có thể hiệu quả hơn Do đó, cần lặp lại quá trình tạo thành và giải quyết các bài toán này.
Khi thảo luận về các phương pháp khác nhau, một câu hỏi quan trọng là liệu có đảm bảo rằng một nghiệm tối ưu hoặc ε-tối ưu cho bài toán xác định sẽ được tìm thấy nếu giải quyết đủ các bài toán xấp xỉ trung bình mẫu từ các mẫu độc lập có kích thước N Câu hỏi này có thể được xem như một phép thử Bernoulli với xác suất thành công p = p(N), trong đó "thành công" được định nghĩa là nghiệm tối ưu xˆ N của bài toán xấp xỉ trung bình mẫu cũng là nghiệm tối ưu cho bài toán xác định.
Theo Định lý 2.1.2.1, xác suất p tiến gần đến 1 khi N → ∞, và theo Định lý 2.1.2.2, nó tăng nhanh theo hàm mũ nếu giả thiết A vẫn đúng Tuy nhiên, với N hữu hạn, xác suất p có thể nhỏ hoặc bằng 0 Xác suất tạo ra một nghiệm tối ưu ít nhất một lần trong M phép thử là 1−(1−p) M, và xác suất này tiến tới 1 khi M → ∞ với p dương Do đó, câu hỏi quan trọng là liệu có đảm bảo rằng p dương với kích cỡ mẫu N nhất định Ví dụ dưới đây cho thấy kích cỡ mẫu N cần thiết cho p dương phụ thuộc vào đặc trưng của bài toán, không chỉ vào số lượng các phương án.
Giả sử S := {−1,0,1} và W có hai giá trị w1 và w2 với xác suất 1−γ và γ Các hàm G được định nghĩa như sau: G(−1, W1) = −1, G(0, W1) = 0, G(1, W1) = 2; G(−1, W2) = 2k, G(0, W2) = 0, G(1, W2) = −k, với k là số dương Khi γ = 1/(k + 1), ta có g(x) = (1−γ)G(x, W1) + γG(x, W2), dẫn đến g(−1) = k/(k + 1), g(0) = 0, và g(1) = k/(k + 1) Kết quả cho thấy x∗ = 0 là nghiệm tối ưu đơn trị Nếu mẫu không có sự quan sát w2 nào, thì xˆN = −1 khác với x∗ Ngược lại, nếu mẫu có ít nhất một sự quan sát w2, thì gˆN(1) ≤ [2(N − 1) − k]/N, từ đó suy ra ˆgN(1) < 0 = ˆgN(0).
Để xấp xỉ trung bình mẫu, cần ít nhất một mẫu cỡ N > k/2 để x ∗ = 0 trở thành nghiệm tối ưu Variance của G(−1, W)−G(0, W) và G(1, W)−G(0, W) tăng theo k, làm cho bài toán trở nên phức tạp hơn Số lần lặp lại M có thể được chọn linh hoạt, tương tự như cách chọn kích cỡ mẫu N Giả sử mỗi lần lặp lại tạo ra một nghiệm đại diện, có thể là nghiệm tối ưu (ε - tối ưu) Khoảng tối ưu g(ˆx m N −v ∗ ) sẽ được ước lượng như mô tả Nếu tiêu chuẩn dừng dựa trên ước lượng này được thỏa mãn, sẽ không có thêm lặp lại nào Ngược lại, có thể thực hiện thêm lặp lại với cùng kích cỡ mẫu N hoặc tăng kích cỡ mẫu N, từ đó cải thiện nghiệm tìm được.
Chú ý rằng các biến ngẫu nhiên g(ˆx m N ) là độc lập và phân bố đồng nhất, với xác suất chung hữu hạn do tập S là hữu hạn Khi thực hiện M lần lặp lại với kích cỡ mẫu N, xác suất để lặp lại mẫu thứ (M + 1) tạo ra nghiệm tốt hơn nghiệm tốt nhất từ M lần lặp lại là 1/(M + 1) Tuy nhiên, trong thực tế, phân phối của g(ˆx N ) là rời rạc, do đó xác suất này nhỏ hơn hoặc bằng 1/(M + 1) Khi giá trị 1/(M + 1) trở nên đủ nhỏ, việc lặp lại để xấp xỉ trung bình mẫu với cùng kích cỡ mẫu không còn đáng kể, dẫn đến việc tăng kích cỡ mẫu N hoặc dừng phương pháp Để xác định các qui luật dừng và ước lượng chính xác, ta nên chọn g(ˆx) − v ∗ với một nghiệm xˆ∈ S đã cho.
G(ˆx, W j ) là một công thức ước lượng không chệch củag(ˆx)và phương sai củagˆ N 0 (ˆx)được ước lượng bởi S 2
N 0 (ˆx) là phương sai mẫu của G(ˆx, W j ), dựa trên mẫu cỡ N 0
Một công thức ước lượng của v ∗ được cho bởi ¯ v N M := 1
Giá trị mục tiêu tối ưu của sự lặp lại xấp xỉ trung bình mẫu thứ m được biểu thị bởi vˆ N m, với E[¯v N M] = E[ˆv N], cho thấy công thức ước lượng ¯v N M có cùng sai số âm như vˆ N Định lý 2.1.2.4 chứng minh rằng sai số này sẽ tăng lên trong trường hợp điều kiện yếu với tập hợp các nghiệm tối ưu hoặc gần tối ưu rộng hơn Hơn nữa, công thức ước lượng gˆ N 0 (ˆx)−v¯ N M liên quan đến khoảng tối ưu g(ˆx)−v ∗ tại điểm xˆ.
Công thức ước lượng E[ ˆg(ˆx)−¯v N M ] = g(ˆx)−E[ˆv N ] ≥g(ˆx)−v ∗ chỉ ra rằng trung bình của ước lượng có thể đánh giá quá cao khoảng tối ưu g(ˆx) −v ∗ Điều này cho thấy rằng sai số giữa v ∗ và E[ˆv N ] sẽ giảm dần khi kích cỡ mẫu N tăng lên.
Phương sai của v¯ M N được ước lượng bởi
Nếu M mẫu cỡ N và sự ước lượng mẫu cỡ N 0 là độc lập, thì phương sai của công thức ước lượng khoảng tối ưu gˆ N 0 (ˆx) − v¯ N M có thể được ước lượng bởi
Một công thức ước lượng của khoảng tối ưu g(ˆx)−v ∗ với khả năng phương sai nhỏ hơn là g¯ N M (ˆx)−v¯ N M , trong đó ¯ g N M (ˆx) := 1
X m=1 ˆ g N m (ˆx) và gˆ N m (ˆx) là giá trị mục tiêu trung bình mẫu tại xˆ của mẫu xấp xỉ trung bình thứ m cỡ N, ˆ g N m (ˆx) := 1
Phương sai của g¯ N M (ˆx)−v¯ N M được ước lượng bởi
Công thức ước lượng khoảng tối ưu có phương sai nhỏ nhất phụ thuộc vào sự tương quan giữa gˆ N m (ˆx) và vˆ N m, cùng với kích cỡ mẫu N, N 0 và M Trong nhiều ứng dụng, sự tương quan dương giữa ˆ g m N (ˆx) và vˆ m N là điều mong đợi Việc tính toán gˆ N m (ˆx) với m = 1, 2, , M cũng cần được xem xét khi đánh giá sự rút gọn phương sai Định lý Central Limit có thể áp dụng cho công thức ước lượng khoảng tối ưu gˆ N 0 (ˆx)−v¯ N M và g¯ N M (ˆx)−v¯ N M, từ đó cho phép tính toán độ chính xác của công thức ước lượng bằng cách thêm bội số z α của độ lệch tiêu chuẩn ước lượng Nếu xˆ ∈ S là nghiệm đại diện cho giá trị tốt nhất của gˆ N 0 (ˆx) sau M lần lặp, công thức ước lượng khoảng tối ưu có tính đến độ chính xác được cho bởi ˆ g N 0 (ˆx)−¯v M N +z α S 2.
√M. Để kiểm tra thuật toán, ta tách công thức ước lượng khoảng tối ưu vào trong thành phần của nó Ví dụ ˆ g N 0 (ˆx)−v¯ N M +z α S 2
Trong bốn số hạng của phương trình, số hạng đầu tiên có giá trị kỳ vọng bằng 0, số hạng thứ hai là khoảng tối ưu đúng, số hạng thứ ba là sai số với giá trị kỳ vọng dương giảm theo kích cỡ mẫu N, và số hạng thứ tư là độ chính xác, giảm theo số lần lặp lại M và kích cỡ mẫu N0 Một nhược điểm của các công thức ước lượng khoảng tối ưu là khoảng ước lượng có thể rộng nếu M, N hoặc N0 nhỏ, ngay cả khi xˆ là nghiệm tối ưu, tức là g(ˆx)−v ∗ = 0.
Giả sử một quy tắc được thiết lập để dừng lại khi công thức ước lượng khoảng tối ưu đạt giá trị đủ nhỏ Tại thời điểm này, nghiệm đại diện xˆ ∈ S với giá trị tốt nhất gˆ N 0 (ˆx) có thể được chọn làm nghiệm cuối cùng Tuy nhiên, việc đánh giá này có thể được sử dụng để thể hiện một cái nhìn chi tiết hơn về các nghiệm đại diện đã được tạo ra trong quá trình lặp lại Có nhiều phương pháp lựa chọn và sàng lọc thống kê khác nhau để xác định các tập hợp con của các nghiệm hoặc một nghiệm duy nhất từ một tập hữu hạn (hợp lý) của các nghiệm, dựa trên mẫu của các giá trị mục tiêu của các nghiệm.
Chúng tôi giới thiệu một thuật toán cho lớp bài toán tối ưu rời rạc ngẫu nhiên, dựa trên các kết quả đã được trình bày trong luận văn này.
Ví dụ
2.3.1 Mô hình bài toán phân bổ kinh phí
Chúng tôi áp dụng phương pháp phân bổ nguồn kinh phí cho bài toán lựa chọn một tập con trong k dự án đã biết để đầu tư Với một số lượng q nguồn chi phí tương đối thấp, mục tiêu là phân bổ nguồn này một cách hiệu quả Tổng số lượng W i của nguồn cần thiết cho mỗi dự án i không được xác định tại thời điểm quyết định, nhưng người ra quyết định có thể ước lượng phân phối xác suất của W = (W 1 , , W k ) Mỗi dự án i có kỳ vọng lãi suất là r i, và kế hoạch phân bổ kinh phí cần được thiết lập nhằm tối đa hóa tổng lãi suất.
Mô hình thực tế đã cho đẫn đến mô hình bài toán tối ưu như sau: max x∈{0,1} k
Bài toán cái túi ngẫu nhiên tĩnh (SSKP) được mô tả như một bài toán trong đó một tập con của k khoảng phải được chọn để vừa với một túi có kích thước q Mỗi khoảng i có kích thước W i là ngẫu nhiên, và mỗi đơn vị lãi c cần được bù đắp cho sức chứa vượt quá giới hạn của túi Bài toán này được lựa chọn do số hạng giá trị kỳ vọng tương tự như số hạng trong hàm mục tiêu của (2.34), xuất hiện trong nhiều bài toán tối ưu ngẫu nhiên thú vị.
2.3.2 Kết quả tính toán bằng số
Trong bài báo của A J Kleywegt, A Shapiro và Tito Homem-de-Mello, các tác giả đã thực hiện tính toán số cho bài toán SSKP với hai tập biến lựa chọn: 10 biến ở tập đầu và 20 biến ở tập thứ hai Họ đã áp dụng phương pháp này cho một ví dụ cụ thể, được ký hiệu là 10D và 20D, với số ràng buộc K lớn được lựa chọn ngẫu nhiên.
Bảng 2.1 trình bày các biến lựa chọn 10R và 20R, cùng với số điều kiện buộc K, giá trị tối ưu v∗, giá trị g(¯x) của phương án tối ưu x¯, và giá trị tối đa x G(x, E[W]) cho từng sự lựa chọn.
Bảng 2.1 Số điều kiện buộc K, giá trị tối ưu v ∗ và giá trị g(¯x) của phương án tối ưu x¯ và giá trị max x G(x, E[W]) đối với mỗi sự lựa chọn.
Sự lựa chọn Số điều kiện K Giá trị tối ưu v ∗ Giá trị kỳ vọng g(¯x)
Trong ví dụ đã nêu, các biến W i có phân phối chuẩn độc lập Mức ý nghĩa a i được tạo ra theo phân phối đều trong khoảng (20, 30), trong khi độ lệch chuẩn σ i cũng được tạo ra theo phân phối đều trong khoảng (5, 15) Đối với bài toán thực tế ở mục 2.3.1, kỳ vọng lãi r i có phân phối đều trong khoảng (10, 20) và tất cả các giá trị c đều bằng 4.
Nếu W i ∼N(à i , σ i 2 ), với i = 1, , k là các biến ngẫu nhiên có phân phối chuẩn độc lập, thì hàm mục tiêu của bài toán có thể được biểu diễn dưới dạng đóng Biến ngẫu nhiên Z(x) := Pk i=1W i x i −q được xác định là phân phối chuẩn với mức ý nghĩa à(x) =Pk i=1à i x i −q và phương sai σ 2 (x) = Pk i=1σ i 2 x 2 i Từ đó, ta có thể suy ra rằng Z(x) ∼ N(à(x), σ(x) 2 ).
, ở đây Φ ký hiệu cho hàm phân phối tích lũy chuẩn Do vậy g(x) k
Sự diễn đạt dạng đóng mang lại lợi ích lớn bởi vì giá trị hàm mục tiêu g(x) có thể được tính toán một cách nhanh chóng và chính xác Điều này rất tiện lợi cho việc giải quyết các bài toán nhỏ thông qua các phương pháp như liệt kê hoặc nhánh và cận.
Luận văn đã giải quyết được một số vấn đề sau:
Bài viết này trình bày các khái niệm cơ bản và kiến thức nền tảng về xác suất thống kê, đồng thời giới thiệu bài toán quy hoạch ngẫu nhiên và quy hoạch ngẫu nhiên rời rạc Ngoài ra, bài viết cũng đề cập đến một số phương pháp tiếp cận để giải quyết các bài toán này, giúp người đọc hiểu rõ hơn về ứng dụng của xác suất thống kê trong quy hoạch.
2 Với bài toán đã nêu, xây dựng được phép lấy mẫu ngẫu nhiên và sự chọn lọc kích cỡ mẫu nhằm tiến tới xây dựng thuật toán giải.
3 Phát biểu và chứng minh một số Định lý của bài toán đang xét Từ đó nêu ra thuật toán giải tương ứng.
4 Đưa ra ví dụ về một mô hình thực tế và thể hiện bằng số để thấy rõ hiệu quả của thuật toán.
Do thời gian và trình độ có hạn nên một số vấn đề cần được tiếp tục nghiên cứu bao gồm:
• Xây dựng phần mềm giải bài toán bằng thuật toán đã nêu.
• Xây dựng các mô hình ứng dụng khác trong các bài toán thực tế.
