Mục lục trang Mở đầu Chương Kiến thức chuẩn bị 1.1 Một số vấn đề sở lý thuyết xác suất thống kê 1.1.1 Một số vấn đề sở lý thuyết xác suất 1.1.2 Một số vấn đề sở lý thuyết thống kê 1.2 Một số nội dung toán quy hoạch ngẫu nhiên 11 1.2.1 Bài toán quy hoạch tuyến tính ngẫu nhiên 11 1.2.2 Bài toán quy hoạch rời rạc ngẫu nhiên 14 1.3 Một số vấn đề chung giải toán quy hoạch phương pháp xấp xỉ 15 1.3.1 Phương pháp tụt 15 1.3.2 Phương pháp thử thống kê 17 Chương Một phương pháp tối ưu dịng thơng tin trận địa pháo 20 2.1 Bài toán 20 2.1.1 Bài toán thực tế 20 2.1.2 Xác lập mơ hình toán học 20 2.2 Phép lấy mẫu hội tụ phương pháp trung bình mẫu 21 2.2.1 Phép lấy mẫu 21 2.2.2 Sự hội tụ phương pháp trung bình mẫu 21 2.3 Sự hội tụ nghiệm xấp xỉ thuật toán xấp xỉ trung bình mẫu 28 2.3.1 Sự hội tụ nghiệm xấp xỉ 28 2.3.2 Thuật tốn xấp xỉ trung bình mẫu 31 2.3.3 Thuật toán xấp xỉ trung bình mẫu đánh giá hiệu 38 Kết luận 40 Tài liệu tham khảo 41 Mở đầu Trong hoạt động Binh chủng Pháo binh, có đặc thù riêng có nhiều đặc thù phải tuân thủ quy luật chung hệ thống Chẳng hạn: Cấu tạo, kỹ thuật, tính tác dụng, phương thức hoạt động đặc thù riêng; Mối quan hệ đối tượng, quy luật tồn phát triển đặc thù chung Trong đặc thù chung hệ thống, đáng quan tâm mối quan hệ hệ thống với môi trường ảnh hưởng nhiễu, tác động nhiễu từ môi trường làm sai lệch quỹ đạo hệ thống thường xuyên xảy Việc theo dõi để điều chỉnh hệ thống quỹ đạo vạch trách nhiệm quan điều khiển đối tượng điều khiển Đã có nhiều nghiên cứu có giá trị toán tối ưu hoạt động Binh chủng Pháo binh (chẳng hạn toán tối ưu bố trí trận địa pháo, tốn đuổi bắt mục tiêu, ) Nhưng nghiên cứu xét tới trạng thái tĩnh với thông tin liệu đầy đủ Do nhiễu tác động vào hệ thống nên thông tin liệu phụ thuộc đại lượng ngẫu nhiên Việc xem xét, nghiên cứu toán tối ưu Binh chủng Pháo binh có tính đến yếu tố nhiễu có ý nghĩa khoa học ý nghĩa thực tiễn Khi tiếp cận với báo: Phương pháp xấp xỉ trung bình mẫu giải tốn tối ưu rời rạc ngẫu nhiên (The Sample Average Approximation Method for Stochastic Discrete Optimization), tác giả A J Kleywegt, cộng sự, công bố năm 2000, thấy có nhiều nội dung liên quan đến tốn tối ưu binh chủng pháo binh Vì vậy, chọn đề tài nghiên cứu: "Phương pháp xấp xỉ trung bình mẫu giải tốn thơng tin huy trận địa pháo có tính ngẫu nhiên" Mục tiêu đề tài nghiên cứu lớp toán tối ưu dịng thơng tin đội pháo trận địa pháo, dịng thơng tin truyền kênh chịu ảnh hưởng nhiễu Từ sử dụng phương pháp xấp xỉ trung bình mẫu để tìm phương án tối ưu cho toán Luận văn chia làm hai chương: Chương trình bày kiến thức chuẩn bị Trong chương này, nêu khái niệm kiến thức cở sở lý thuyết xác suất thống kê nhằm phục vụ cho việc nghiên cứu đề tài; toán quy hoạch ngẫu nhiên rời rạc hướng tiếp cận để giải Chương nghiên cứu tốn tối ưu dịng thơng tin huy trận địa pháo Trước hết chúng tơi nêu tốn thực tế đặt ra, từ mơ hình hố dạng tốn học Tiếp theo trình bày phương pháp xấp xỉ trung bình mẫu giải tốn đặt Luận văn hoàn thành hướng dẫn thầy giáo PGS.TS Trần Xuân Sinh, xin bày tỏ lòng biết ơn sâu sắc tới thầy cảm ơn thầy giáo tổ xác suất thống kê giảng dạy, bảo cho suốt thời gian học tập nghiên cứu Cũng xin gửi lời cảm ơn tới thầy giáo cô giáo khoa Tốn, Phịng Sau đại học trường Đại học Vinh Tôi xin bày tỏ lời cảm ơn tới trường Sĩ quan Pháo binh, thuộc Binh chủng Pháo binh - nơi công tác, đồng nghiệp, bạn bè gia đình tạo điều kiện thuận tiện cho tơi hồn thành luận văn Vinh, ngày 20 tháng 10 năm 2012 Tác giả Chương Kiến thức chuẩn bị 1.1 Một số vấn đề sở lý thuyết xác suất thống kê 1.1.1 Một số vấn đề sở lý thuyết xác suất 1.1.1.1 Các định nghĩa • Đại số σ - đại số Giả sử Ω tập tùy ý khác rỗng Ký hiệu P(Ω) tập tất tập Ω Lớp A ⊂ P(Ω) gọi đại số A1) Ω ∈ A, A2) A ∈ A ⇒ A¯ = Ω\A ∈ A, A3) A, B ∈ A ⇒ A ∪ B ∈ A (hoặc A ∩ B ∈ A) Lớp F ⊂ P(Ω) gọi σ-đại số đại số thoả mãn A4) An ∈ F, ∀n = 1, 2, ∞ ∞ An ∈ F, (hoặc n=1 An ∈ F) n=1 • Độ đo xác suất Giả sử (Ω, F) không gian đo Một ánh xạ P : F → R gọi độ đo xác suất F P1) P(A) ≥ 0, A ∈ F, P2) P(Ω) = 1, P3) Nếu Ai ∈ F, i = 1, 2, , Ai ∩ Aj = ∅, i = j ∞ ∞ Ai = P i=1 P(Ai ) i=1 • Khơng gian đo không gian xác suất Cặp (Ω, F) gọi không gian đo (Ω, F, P) gọi khơng gian xác suất, Ω = ∅ bất kỳ, F σ-đại số tập Ω • Biến ngẫu nhiên Giả sử (Ω, F) không gian đo, R = [−∞; +∞] Hàm thực X = X(ω) xác định Ω lấy giá trị R gọi hàm F - đo gọi biến ngẫu nhiên suy rộng {ω : X(ω) ∈ B} = X −1 (B) ∈ F với B ∈ B(R) (trong B(R) σ - đại số tập Borel trục thực R ) Nếu X : Ω → R = (−∞; +∞) X gọi biến ngẫu nhiên đại lượng ngẫu nhiên • Hàm Borel Hàm ϕ : (Rn , B(Rn )) → (R, B(R)) gọi hàm Borel, hàm B(Rn ) - đo được, nghĩa ϕ−1 (B) ∈ B(Rn ), với B ∈ B(R) • Hàm phân phối xác suất biến ngẫu nhiên Giả sử X biến ngẫu nhiên xác định (Ω, F, P), nhận giá trị R Hàm số FX (x) = P[X < x], (x ∈ R) gọi hàm phân phối biến ngẫu nhiên X 1.1.1.2 Kỳ vọng biến ngẫu nhiên • Định nghĩa Kỳ vọng hay giá trị trung bình biến ngẫu nhiên X số EX, xác định EX = XdP Ω • Các tính chất Nếu X ≥ EX ≥ Nếu X = C EX = C, với C số Nếu tồn EX với số λ, ta có E(λX) = λEX Nếu tồn EX EY E(X ± Y ) = EX ± EY    k xk pk , X rời rạc, P(X = xk ) = pk , EX =   +∞ xp(x)dx, X liên tục, có hàm mật độ p(x) −∞ (Định lý P Levy hội tụ đơn điệu) Nếu Xn ↑ X (tương ứng Xn ↓ X) tồn n để EXn− < ∞ (tương ứng EXn+ < ∞) EXn ↑ EX (tương ứng EXn ↓ EX) (Bổ đề Fatou) Nếu Xn ≥ Y, ∀n ≥ EY > −∞ ElimXn ≤ limEXn , Nếu Xn ≤ Y, ∀n ≥ EY < ∞ ElimXn ≥ limEXn , Nếu |Xn | ≤ Y, ∀n ≥ EY < ∞ ElimXn ≤ limEXn ≤ limEXn ≤ ElimXn (Định lý Lebesgue hội tụ bị chặn) Nếu |Xn | ≤ Y, ∀n ≥ 1, EY < ∞ Xn → X X khả tích, E|Xn − X| → EXn → EX, n → ∞ Nếu ϕ hàm lồi, X ϕ(X) khả tích E(ϕ(X)) ≥ ϕ(EX) 10 Nếu X Y độc lập E(XY ) = EX.EY 1.1.1.3 Phương sai biến ngẫu nhiên • Định nghĩa Phương sai biến ngẫu nhiên X, ký hiệu DX (hay varX) số xác định DX = E(X − EX)2 Khi DX =    k (xk   +∞ −∞ (x − EX)2 pk , X rời rạc, P (X = xk ) = pk , − EX)2 p(x)dx, X liên tục, có hàm mật độ p(x) • Các tính chất DX ≥ 0, DX = X = EX = số h.c.c Với số λ D(λX) = λ2 DX DX = EX − (EX)2 Nếu X, Y độc lập D(X ± Y ) = DX + DY Với số λ, ta có E(X − λ)2 ≥ E(X − EX)2 Dấu xảy EX = λ 1.1.2 Một số vấn đề sở lý thuyết thống kê 1.1.2.1 Mẫu cách xác định mẫu • Tổng thể mẫu ◦ Trong thực tế, thông tin đối tượng tượng cần nghiên cứu có nhờ vào quan sát phép thử Các thơng tin có phải đảm bảo tính xác, tính ngẫu nhiên nó, phải đại diện cách trung thực cho đối tượng tượng mà cần nghiên cứu Các quan sát (phép thử) tiến hành cách độc lập với Kết quan sát (phép thử) không phụ thuộc vào kết quan sát (phép thử) khác không ảnh hưởng đến khả xảy kết quan sát (phép thử) khác Để có quan sát (phép thử), cần chọn mẫu (lấy mẫu) ◦ Tập hợp có phần tử đối tượng mà nghiên cứu gọi tổng thể Số phần tử tổng thể gọi kích thước tổng thể Nếu từ tổng thể, ta chọn n phần tử n phần tử gọi mẫu có kích thước n hay cỡ n chọn từ tổng thể ◦ Khi chọn mẫu, phần tử chọn loại khỏi tổng thể, lần chọn gọi mẫu khơng hồn lại Nếu phần tử chọn trả lại tổng thể, chọn phần tử gọi mẫu có hồn lại ◦ Mẫu gọi mẫu ngẫu nhiên chọn cách để bảo đảm tính khách quan, ngẫu nhiên Giả sử tiến hành n quan sát độc lập biến ngẫu nhiên X Ta gọi Xj việc quan sát lần thứ j biến ngẫu nhiên X Khi ta có (X1 , X2 , , Xn ) mẫu ngẫu nhiên cỡ n Ta ký hiệu xj kết quan sát lần thứ j (x1 , x2 , , xn ) n giá trị cụ thể ta quan sát • Các cách xác định mẫu ◦ Ta gọi mẫu định tính mẫu mà ta quan tâm đến phần tử có tính chất A hay khơng ◦ Ta gọi mẫu định lượng mẫu mà ta quan tâm đến yếu tố lượng phần tử mẫu, chẳng hạn chiều dài, khối lượng 1.1.2.2 Đặc trưng mẫu • Tỷ lệ mẫu Cho mẫu định tính kích thước n, có m phần tử có tính chất A Khi ta gọi f = fn = tỷ lệ mẫu m n 10 • Trung bình mẫu ◦ Định nghĩa Trung bình mẫu xác định theo cơng thức X= n n Xj j=1 Giả sử ta nghiên cứu biến ngẫu nhiên X Ký hiệu µ = EX, σ = DX Cho (X1 , X2 , , Xn ) mẫu ngẫu nhiên rút từ X Ta ký hiệu biến ngẫu nhiên rời rạc X nhận n giá trị mẫu với xác suất đều, tức P(X = Xj ) = 1/n Khi ta có hàm phân phối thực nghiệm Fn (x) (còn gọi hàm phân phối mẫu) Fn (x) = P(X < x) Từ ta có khái niệm kỳ vọng mẫu, phương sai mẫu, ◦ Tính chất Nếu X = C số X = C Nếu X ≥ X ≥ Với số λ ta có (λX) = λX Với biến quan sát X, Y (X ± Y ) = X ± Y Ta có a) EX = a = EX; DX = n→∞ σ2 n; b) F (X−a)√n (x) −−−→ Φ(x) = σ √1 2π x − t2 e dt −∞ ◦ Nhận xét Từ tính chất 5, kích thước mẫu n lớn người ta thường xấp xỉ: + X ≈ a = EX; √ (X−a) n + σ σ2 N (a, n ) có phân phối xấp xỉ N (0, 1), X có phân phối xấp xỉ 27 Hơn nữa, giả thiết (A) đúng, γ(δ, ε) > Chứng minh Bất đẳng thức (2.16) hệ trực tiếp bất đẳng thức (2.15) Nó kéo theo −δ > −ε∗ ≥ −E[H(x, W )] Từ theo giả thiết (A) Ix (−δ) > với x ∈ D \ Dε Địều có nghĩa γ(δ, ε) > Định lý chứng minh xong Kết sau hệ trực tiếp bất đẳng thức (2.15) lim sup N →∞ δ ˆN log[1 − P D ⊂ Dε ] ≤ −γ(δ, ε) N (2.18) Vì vậy, số γ(δ, ε) cho (2.17) xấp xỉ γ(δ, ε) ≈ ε x∈D\D −δ − E[H(x, W )] 2σx2 (ε − δ)2 (ε − δ)2 ≥ > , 2 2σmax 2σmax (2.19) σmax := max ε var [C u(x), W −C(x, W )] (2.20) x∈D\D ˆ δ ⊂ Dε hội Bất đẳng thức (2.18) có nghĩa xác suất biến cố D N tụ nhanh theo hàm mũ N → ∞ Địều gợi ý phương pháp Monte Carlo, kết hợp với phương pháp hiệu dụng để giải tốn xấp xỉ trung bình mẫu tất định, giải cách hiệu lớp tốn nghiên cứu đây, đưa số γ(δ, ε) khơng q nhỏ Từ (2.8) có −δ − E[H(x, W )] Ix (−δ) ≈ 2σx2 (ε − δ)2 ≥ 2σx2 (2.21) σx2 := var [H(x, W )] = var [C u(x), W −C(x, W )] Để minh họa vài kéo theo giới hạn (2.16) bàn bạc độ phức tạp việc giải toán ngẫu nhiên, đặt mức ý ˆ δ ⊂ Dε nghĩa α ∈ (0, 1) ước lượng kích cỡ mẫu N cần để xác suất P D N trở thành nhỏ − α Bằng cách lợi dụng vế phải (2.16) nhỏ 28 với α, ta N≥ log γ(δ, ε) D \ Dε α (2.22) (ε − δ)2 Hơn nữa, từ (2.9) (2.17) ta có γ(δ, ε) ≥ với ε ≥ đủ nhỏ 3σmax Do giữ nguyên với tất ε > đủ nhỏ δ ∈ [0, ε), điều kiện đủ để (2.22) |D| 3σmax log N≥ (ε − δ)2 α (2.23) Cận (2.23) dè dặt ước lượng thực tế kích cỡ mẫu yêu cầu Tuy nhiên, ước lượng (2.23) có hệ trực tiếp thú vị việc đánh giá độ phức tạp Một đặc trưng (2.23) N phụ thuộc logarith kích cỡ tập D cho phép xác suất cho phép α Một cách giải thích hợp ta đưa giả thiết: 1) Kích cỡ tập D cho phép tăng theo số mũ với độ dài liệu toán đưa vào, 2) Phương sai σmax phụ thuộc đa thức theo độ dài liệu toán đưa vào, 3) Độ phức tạp việc tìm nghiệm tối ưu δ toán (2.2) tăng đa thức theo độ dài liệu đầu vào tốn kích cỡ mẫu N Khi nghiệm tối ưu tạo thành thời gian đa thức theo độ dài liệu đầu vào toán, với xác suất − α, tốn (2.2) có nghiệm ε tối ưu 2.3 Sự hội tụ nghiệm xấp xỉ thuật tốn xấp xỉ trung bình mẫu 2.3.1 Sự hội tụ nghiệm xấp xỉ Bây giả sử tốn tất định có nghiệm tối ưu đơn trị x∗ , tức D∗ = {x∗ } ta xét toán xấp xỉ trung bình mẫu (2.2) 29 có nghiệm tối ưu đơn trị xˆN xˆN = x∗ Chúng ta biểu thị kiện {ˆ xN = x∗ } Hơn nữa, xét ánh xạ u : D \ Dε → {x∗ }, tức u(x) ≡ x∗ số tương ứng γ ∗ = γ(0, 0) Vì γ∗ = Ix (0), x∈D\{x∗ } (2.24) với Ix (.) hàm tốc độ độ lệch lớn C(x∗ , W ) − C(x, W ) Chú ý E[C(x∗ , W ) − C(x, W )] = c(x∗ ) − c(x) E[C(x∗ , W ) − C(x, W )] < với x ∈ D \ {x∗ } Vì vậy, giả thiết (A) còn, tức hàm sinh moment C(x∗ , W ) − C(x, W ) hữu hạn giá trị lân cận 0, γ ∗ > 2.3.1.1 Định lý Giả sử toán tất định có nghiệm tối ưu đơn trị x∗ hàm sinh moment biến ngẫu nhiên C(x∗ , W ) − C(x, W ), x ∈ D \ {x∗ }, hữu hạn giá trị R Khi log[1 − P(ˆ xN = x∗ )] = −γ ∗ N →∞ N lim (2.25) Chứng minh Từ (2.17) ta có lim sup N →∞ log[1 − P(ˆ xN = x∗ )] ≤ −γ ∗ N (2.26) Xem phần bù biến cố {ˆ xN = x∗ } ký hiệu {ˆ xN = x∗ } Biến cố {ˆ xN = x∗ } hợp biến cố {ˆ cN (x) ≤ cˆN (x∗ ) }, x ∈ D \ {x∗ } Do đó, với x ∈ D \ {x∗ }, P(ˆ xN = x∗ ) ≥ P cˆN (x) ≤ cˆN (x∗ ) Bằng cách sử dụng giới hạn (2.6) định lý độ lệch lớn Cramer ta có bất đẳng thức lim inf N →∞ log[1 − P(ˆ xN = x∗ )] ≥ −Ix (0) N (2.27) với x ∈ D \ {x∗ } Bất đẳng thức (2.26) (2.27) kéo theo (2.25) 30 Định lý chứng minh xong Bây xem xét tính gần giá trị hàm mục tiêu tối ưu xấp xỉ trung bình mẫu vˆN Với tập D D bất đẳng thức vˆN ≤ cˆN (x) Trong thực tế, cách lấy D = D∗ , ta x∈D có vˆN ≤ min∗ cˆN (x) từ x∈D cN (x)] = v ∗ E[ˆ vN ] ≤ E[min∗ cˆN (x)] ≤ min∗ E[ˆ x∈D x∈D Vì vậy, cơng thức ước lượng vˆN có sai số âm Từ Định lý 2.3.1.1, với xác suất 1, N đủ lớn, tập hợp SˆN nghiệm tối ưu tốn xấp xỉ trung bình mẫu thuộc D∗ Trong trường hợp vˆN = cˆN (x) ≥ min∗ cˆN (x) x∈D x∈SˆN Ta thấy bất đẳng thức ngược lại đúng, với xác suất 1, vˆN − min∗ cˆN (x) = N đủ lớn Nhân hai vế phương trình √ x∈D √ với N , ta có với xác suất 1, N [ˆ vN − min∗ cˆN (x)] = N đủ lớn x∈D √ lim N →∞ N [ˆ vN − min∗ cˆN (x)] = 0, với xác suất x∈D (2.28) Từ hội tụ với xác suất nghĩa hội tụ theo xác suất, từ (2.28) có √ N [ˆ vN − min∗ cˆN (x)] hội tụ theo xác suất tới 0, tức x∈D vˆN = min∗ cˆN (x) + Op (N −1/2 ) x∈D Hơn nữa, từ v ∗ = c(x) với x ∈ D∗ , √ √ N [ min∗ cˆN (x)] − v ∗ ] = min∗ { N [ˆ cN (x) − c(x)]} x∈D x∈D Giả sử với x ∈ D, phương sai σ (x) := var[C(x, W )] (2.29) tồn Khi theo định lý giới hạn trung tâm, với x ∈ D, √ N [ˆ cN (x) − c(x)] hội tụ theo phân phối tới biến phân phối chuẩn 31 Z(x) với giá trị trung bình phương sai σ (x) Hơn nữa, lại theo định lý giới hạn trung tâm, biến ngẫu nhiên Z(x) có hàm hiệp phương sai giống C(x, W ) Địều cho thấy Z(x) Z(x ) giống C(x, W ) C(x , W ), với x, x ∈ D Do có Định D lý 2.3.1.2 sau (chúng sử dụng "− →" để biểu thị hội tụ theo phân phối) 2.3.1.2 Định lý Giả sử phương sai σ (x), xác định (2.29), tồn với x ∈ D∗ Khi √ D N (ˆ vN − v ∗ ) − → min∗ Z(x), x∈D (2.30) Z(x) biến ngẫu nhiên phân phối chuẩn với giá trị trung bình hàm hiệp phương sai cho hàm hiệp phương sai tương ứng C(x, W ) Trong thực tế, D∗ = {x∗ } nhất, √ D N (ˆ vN − v ∗ ) − → N 0, σ (x∗ ) (2.31) Mặc dù với x cho sẵn giá trị trung bình (giá trị kỳ vọng) Z(x) Giá trị cực tiểu Z(x) tập D D khơng âm trở thành nhỏ với tập D rộng Vì vầy, từ (2.30) cho thấy với tốn điều kiện yếu mà tập hợp nghiệm tối ưu gần tối ưu rộng, công thức ước lượng vˆN v ∗ có sai số lớn 2.3.2 Thuật tốn xấp xỉ trung bình mẫu Như biết, nhiều toán tối ưu rời rạc ngẫu nhiên khó để giải Trong luận văn này, chúng tơi đưa phương pháp xấp xỉ trung bình mẫu để giải toán tối ưu rời rạc ngẫu nhiên ý tưởng phương pháp mẫu ngẫu nhiên tạo thành hàm giá trị kì vọng xấp xỉ hàm trung bình mẫu tương ứng Bài tốn tối ưu trung bình mẫu thu được giải phương pháp lặp lại tiêu chuẩn dừng thỏa mãn 32 2.3.2.1 Sự lựa chọn kích cỡ mẫu Trong thuật tốn, kích cỡ mẫu hữu hạn dãy kích cỡ mẫu hữu hạn phải lựa chọn thuật toán phải dừng sau lượng thời gian hữu hạn Một câu hỏi quan trọng làm lựa chọn thực ứớc lượng (2.23) đưa giới hạn kích cỡ mẫu u cầu để tìm nghiệm ε - tối ưu với xác suất nhỏ − α ứớc lượng có hai khuyết điểm cho mục đích tính tốn Đầu tiên, với nhiều tốn thật khơng dễ để tính ước lượng, σmax số tốn |D| tính vất vả Thứ hai, giới hạn có bảo đảm xa để thu ước lượng thực tế kích cỡ mẫu yêu cầu Để chọn N , cân đối khác nên đưa vào tính tốn Với N rộng hơn, hàm mục tiêu toán xấp xỉ trung bình mẫu trở thành ước lượng xác hàm mục tiêu đúng, nghiệm tối ưu tốn xấp xỉ trung bình mẫu trở thành nghiệm tốt giới hạn tương ứng khoảng tối ưu nghiên cứu sau trở nên chặt Tuy nhiên, trình giải phụ thuộc vào tốn xấp xỉ trung bình mẫu (2.2) phương pháp sử dụng để giải toán xấp xỉ trung bình mẫu, độ phức tạp để giải tốn xấp xỉ trung bình mẫu tăng lên tuyến tính thường hàm mũ kích cỡ mẫu N Vì vậy, lựa chọn kích cỡ mẫu N , cân đối chất lượng nghiệm tối ưu tốn xấp xỉ trung bình mẫu, giới hạn khoảng tối ưu mặt nỗ lực tính tốn mặt khác nên đưa vào tính tốn Cũng vậy, lựa chọn kích cỡ mẫu N điều chỉnh cách thích hợp, phụ thuộc vào kết tính tốn sơ ý tưởng nói đến chi tiết phần sau Đặc biệt, việc ước lượng giá trị mục tiêu c(x) phương án x ∈ D trung bình mẫu cˆN (x) địi hỏi nỗ lực tính tốn nhiều so với 33 việc giải tốn xấp xỉ trung bình mẫu (với kích cỡ mẫu N ) Vì vậy, xét đến độ phức tạp tính tốn phương pháp để chọn kích cỡ mẫu N tương đối nhỏ tốn xấp xỉ trung bình mẫu, tạo phương hướng để chọn kích cỡ mẫu N rộng để thu ước lượng xác cˆN (ˆ xN ) giá trị mục tiêu c(ˆ xN ) nghiệm tối ưu xˆN tốn xấp xỉ trung bình mẫu Một thước đo độ xác ước lượng trung bình mẫu cˆN (ˆ xN ) c(ˆ xN ) cho xN )/N , tính từ phương sai mẫu tương ứng SN2 (ˆ mẫu cỡ N Sự lựa chọn N bao hàm cân đối nỗ lực tính tốn độ xác, đo SN2 (ˆ xN )/N 2.3.2.2 Quá trình lặp lại Nếu độ phức tạp tính tốn việc giải tốn xấp xỉ trung bình mẫu tăng lên nhanh so với kích cỡ mẫu N , ta chọn kích cỡ mẫu N nhỏ để tạo thành giải vài tốn xấp xỉ trung bình mẫu với mẫu độc lập phân phối Do đó, cần lặp lại tạo thành giải toán xấp xỉ trung bình mẫu Một câu hỏi liệu có phải có bảo đảm nghiệm tối ưu (hoặc ε - tối ưu) toán tất định tạo số đủ tốn xấp xỉ trung bình mẫu, dựa mẫu độc lập cỡ N giải Câu hỏi xem phương pháp phép thử Bernoulli với xác suất thành công p = p(N ) "Thành công" nghĩa nghiệm tối ưu xˆN tính tốn xấp xỉ trung bình mẫu nghiệm tối ưu toán Từ Định lý 2.2.2.1, xác suất p dần tới N → ∞ nữa, theo Định lý 2.2.2.2 dần nhanh theo hàm mũ giả thiết (A) Tuy nhiên, với N hữu hạn xác suất p nhỏ chí khơng Xác suất việc tạo nghiệm tối ưu toán tất định lần M phép thử − (1 − p)M xác suất 34 dần tới M → ∞ tạo p dương Vì câu hỏi xác đáng liệu có bảo đảm p dương với kích cỡ mẫu N cho sẵn Ví dụ sau kích cỡ mẫu N địi hỏi p dương đặc trưng tốn, khơng phụ thuộc vào số phương án mà rộng cách tùy ý Ví dụ: Giả sử D := {−1, 0, 1}, W nhận hai giá trị w1 w2 với xác suất tương ứng 1−γ γ c(−1, W1 ) := −1, c(0, W1 ) := 0, c(1, W1 ) := c(−1, W2 ) := 2k, c(0, W2 ) := 0, c(1, W2 ) := −k, k số dương tùy ý Đặt γ = 1/(k + 1) Khi c(x) = (1 − γ)c(x, W1 ) + γc(x, W2 ) c(−1) = k/(k + 1), c(0) = c(1) = k/(k + 1) Vì x∗ = nghiệm tối ưu đơn trị tốn tất định Nếu mẫu khơng chứa quan sát w2 nào, xˆN = −1 = x∗ Giả sử mẫu chứa quan sát w2 Thì cˆN (1) ≤ [2(N − 1) − k]/N Vì cˆN (1) < = cˆN (0) N ≤ + k/2 xˆN = = x∗ Vậy mẫu cỡ N > k/2 yêu cầu, để x∗ = nghiệm tối ưu tốn xấp xỉ trung bình mẫu Chú ý var[c(−1, W ) − c(0, W )] var[c(1, W ) − c(0, W )] (k) (tăng trưởng bậc theo k), nguyên nhân toán trở nên khó k tăng lên Một việc khác phải nói đến, cách chọn số M lần lặp lại Tương tự với cách chọn kích cỡ mẫu N , số M (sự lặp lại chọn) nghiên cứu phần tới Để trình bày đơn giản, giả sử lặp lặp lại xấp xỉ trung bình mẫu tạo nghiệm đại diện, nghiệm tối ưu (ε - tối ưu) toán xấp xỉ trung bình mẫu Đặt xˆm N biểu thị nghiệm đại diện tạo lặp lại xấp xỉ trung bình mẫu ∗ thứ m (phép thử) Khoảng tối ưu c xˆm N − v ước lượng mô tả phần tới Nếu tiêu chuẩn dừng dựa ước lượng khoảng tối ưu thỏa mãn, khơng lặp lại thực Mặt 35 khác, phép cộng lặp lại xấp xỉ trung bình mẫu với kích cỡ mẫu N thực hiện, kích cỡ mẫu N tăng lên Bằng cách đưa hướng đơn giản xấp xỉ trung bình mẫu với kích cỡ mẫu N , tạo nghiệm tốt nhiều so với nghiệm tốt tìm thấy Chú ý rằng, theo cách xây dựng biến ngẫu nhiên c(ˆ xm N ), m = 1, 2, , độc lập phân bố cách đồng phân phối xác suất chung chúng có hữu hạn tập D hữu hạn Giả sử M lặp lại với kích cỡ mẫu N thực nhiều Nếu phân phối xác suất c(ˆ xN ) tiếp diễn xác suất mà lặp lại xấp xỉ trung bình mẫu thứ (M + 1) với kích cỡ mẫu tạo nghiệm tốt nhiều so với nghiệm tốt tạo M lặp lại, 1/(M + 1) Bởi thực tế phân phối c(ˆ xN ) rời rạc, xác suất nhỏ 1/(M + 1) Vì vậy, 1/(M + 1) trở thành đủ nhỏ, phép cộng lặp lại xấp xỉ trung bình mẫu với kích cỡ mẫu dường khơng đáng kể kích cỡ mẫu N tăng lên phương pháp dừng Để có việc tạo thành qui luật dừng, tốt mục đích biểu diễn ước lượng khác, cách thích hợp để tính khoảng tối ưu chọn c(ˆ x) − v ∗ , với nghiệm cho sẵn xˆ ∈ D Như vậy, cˆN (ˆ x) := N N c(ˆ x, W j ) j=1 công thức ước lượng không chệch c(ˆ x) phương sai cˆN (ˆ x) ước lượng SN2 (ˆ x)/N , SN2 (ˆ x) phương sai mẫu c(ˆ x, W j ), dựa mẫu cỡ N 36 Một công thức ước lượng v ∗ cho M v¯N := M M m vˆN , m=1 m vˆN biểu thị giá trị mục tiêu tối ưu lặp lại xấp xỉ trung bình M ] = E[ˆ vN ] từ cơng thức ước lượng mẫu thứ m Chú ý E[¯ vN M có sai số âm vˆN Định lý 2.2.3.1 chứng tỏ sai số v¯N trở thành lớn hơn, với toán điều kiện yếu với tập hợp nghiệm tối ưu, M gần tối ưu rộng Xét công thức ước lượng tương ứng cˆN (ˆ x) − v¯N khoảng tối ưu c(ˆ x) − v ∗ , điểm xˆ Từ M E[ˆ c (ˆ x) − v¯N ] = c(ˆ x) − E[ˆ vN ] ≥ c(ˆ x) − v ∗ , (2.32) cho thấy trung bình cơng thức ước lượng đánh giá cao khoảng tối ưu c(ˆ x) − v ∗ Nó sai số v ∗ − E[ˆ vN ] giảm cách đều kích cỡ mẫu N M Phương sai v¯N ước lượng M SM m M = (ˆ vN − v¯N ) M M (M − 1) m=1 (2.33) Nếu M mẫu cỡ N ước lượng mẫu cỡ N độc lập, phương sai M công thức ước lượng khoảng tối ưu cˆN (ˆ x) − v¯N ước lượng SN2 (ˆ x)/N + SM /M Một công thức ước lượng khoảng tối ưu c(ˆ x) − v ∗ với khả M phương sai nhỏ c¯M x) − v¯N , N (ˆ c¯M x) N (ˆ := M M cˆm x) N (ˆ m=1 cˆm x) giá trị mục tiêu trung bình mẫu xˆ mẫu xấp xỉ trung N (ˆ bình thứ m cỡ N , cˆm x) N (ˆ := N N c(ˆ x, W mj ) j=1 37 M ước lượng x) − v¯N Phương sai c¯M N (ˆ M SM m M = [ cˆm x) − vˆN − c¯M x) − v¯N ], N (ˆ N (ˆ M M (M − 1) m=1 cơng thức ước lượng khoảng tối ưu có phương sai nhỏ m , tốt kích cỡ mẫu N , x) vˆN phụ thuộc vào tương quan cˆm N (ˆ N M Với nhiều áp dụng, hy vọng tương quan dương m x) với m = 1, 2, , M , nên Phép tính cˆm x) vˆN cˆm N (ˆ N (ˆ đưa vào tính tốn đánh giá rút gọn phương sai Mặt khác, định lý giới hạn trung tâm áp dụng với cơng thức M M , độ xác x) − v¯N c¯M ước lượng khoảng tối ưu cˆN (ˆ x) − v¯N N (ˆ cơng thức ước lượng khoảng tối ưu đưa vào tính tốn cách thêm bội số zα độ lệch tiêu chuẩn ước lượng với cơng thức ước lượng khoảng trống zα := Φ−1 (1 − α), Φ(z) hàm phân phối tích lũy phân phối chuẩn mẫu Chẳng hạn, xˆ ∈ D ký hiệu nghiệm đại diện với giá trị tốt cˆN (ˆ x) tìm thấy sau M lặp lại, công thức ước lượng khoảng tối ưu lấy độ xác vào tính tốn cho 1/2 SN2 (ˆ x) SM M cˆN (ˆ x) − v¯N + zα + N M SM M √ c¯M (ˆ x ) − v ¯ + z α N N 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 thành phần Ví dụ M cˆN (ˆ x) − v¯N + zα S (ˆ x) N N + SM M 1/2 = M = cˆN (ˆ x)−c(ˆ x) + c(ˆ x)−v ∗ +(v ∗ − v¯N )+zα S (ˆ x) N N S2 + MM 1/2 (2.34) Trong số hạng bên phải phương trình trên, số hạng có giá trị kì vọng 0, số hạng thứ hai khoảng tối ưu thật, số hạng thứ ba 38 số hạng sai số, có giảm giá trị kì vọng dương kích cỡ mẫu N số hạng thứ tư số hạng độ xác, giảm số M lần lặp lại kích cỡ mẫu N Vì điều khơng thuận lợi công thức ước lượng khoảng tối ưu cơng thức ước lượng khoảng rộng M, N N nhỏ, xˆ nghiệm tối ưu, tức c(ˆ x) − v ∗ = Giả sử qui tắc tạo để dừng, ví dụ cơng thức ước lượng khoảng tối ưu trở thành đủ nhỏ giai đoạn nghiệm đại diện xˆ ∈ D với giá trị tốt cˆN (ˆ x) chọn lựa nghiệm chọn Tuy nhiên, đánh giá để biểu diễn đánh giá chi tiết nghiệm đại diện tạo suốt q trình lặp lại Có phương pháp lựa chọn sàng lọc thống kê khác để chọn tập hợp nghiệm nghiệm đơn, tập hữu hạn (nhỏ hợp lý) nghiệm, sử dụng mẫu giá trị mục tiêu nghiệm 2.3.3 Thuật tốn xấp xỉ trung bình mẫu đánh giá hiệu 2.3.3.1 Thuật tốn xấp xỉ trung bình mẫu Từ kết nêu trên, chúng tơi trình bày thuật toán lớp toán tối ưu rời rạc ngẫu nhiên nghiên cứu luận văn Bước Chọn kích cỡ mẫu ban đầu N N , qui luật qui định việc xác định số M việc lặp lại xấp xỉ trung bình mẫu (có thể gồm số cực đại M việc lặp lại xấp xỉ trung bình mẫu với kích cỡ mẫu, cho 1/(M + 1) đủ nhỏ), qui luật qui định tăng lên kích cỡ mẫu N N cần sai số ε Bước Với m = 1, 2, , M , ta thực hiện: 2.1 Tạo mẫu cỡ N giải tốn xấp xỉ trung bình mẫu m nghiệm ε - tối ưu xˆm (2.2), với giá trị mục tiêu vˆN N 39 ∗ 2.2 Ước lượng khoảng tối ưu c(ˆ xm N ) − v phương sai theo công thức ước lượng khoảng 2.3 Nếu khoảng tối ưu phương sai công thức ước lượng khoảng đủ nhỏ, sang bước Bước Nếu khoảng tối ưu phương sai cơng thức ước lượng khoảng q rộng, tăng kích cỡ mẫu N N lên trở lại bước Bước Chọn nghiệm tốt xˆ tất nghiệm đại diện xˆm N tạo ra, sử dụng phương pháp chọn lựa sàng lọc Dừng 2.3.3.2 Đánh giá hiệu thuật toán Kết nêu cho thấy xác suất trình lặp thuật tốn xấp xỉ trung bình mẫu cho phương án tối ưu có độ phức tạp tăng theo hàm mũ với kích cỡ mẫu N Người ta nhận thấy tốc độ hội tụ phụ thuộc vào toán với số biến khác Các tác giả đưa nhiều ví dụ sử dụng thuật toán 2.3.3.1 mà phải thực với vài bước lặp kích cỡ mẫu nhỏ Tuy nhiên, công thức ước lượng khoảng tối ưu trường hợp yếu để tìm thấy nghiệm xấp xỉ tối ưu Do vậy, công thức ước lượng khoảng có cải tiến q trình thực thuật tốn Phương hướng cải tiến tìm cách giảm bớt mức độ tính tốn số bước lặp, điều cịn phụ thuộc vào thực tế toán 40 Kết luận Kết nghiên cứu, luận văn nêu số nội dung sau: Trình bày cách hệ thống khái niệm kiến thức sở nhằm phục vụ cho việc nghiên cứu vấn đề có liên quan luận văn Cụ thể trình bày vấn đề: số nội dung cần thiết lý thuyết xác suất thống kê, toán quy hoạch nguyên ngẫu nhiên, phương pháp xấp xỉ giải gần toán quy hoạch Xem xét tốn tối ưu dịng thơng tin huy trận địa pháo khía cạnh thực tế tốn học Trình bày phép lấy mẫu lựa chọn kích cỡ mẫu Trên sở phát biểu chứng minh số định lý hội tụ phương pháp xấp xỉ trung bình mẫu hội tụ việc xấp xỉ nghiệm toán Xây dựng thuật toán xấp xỉ trung bình mẫu giải tốn đặt phân tích hiệu thuật tốn Khi có điều kiện, chúng tơi tiếp nghiên cứu nội dung: • Xây dựng thuật tốn hồn chỉnh lập trình giải cho hai tốn đề cập luận văn • Mở rộng xét với số tốn nhằm phục vụ cơng tác giảng dạy huấn luyện trường Sĩ quan Pháo binh, thuộc Binh chủng Pháo binh 41 Tài liệu tham khảo [1] Đào Hữu Hồ (1996), Xác suất thống kê, NXB Đại học Quốc gia, Hà Nội [2] Nguyễn Văn Quảng (2007), Giáo trình xác suất, NXB Đại học Quốc gia, Hà Nội [3] Trần Xuân Sinh (2004), Các phương pháp ngẫu nhiên giải toán quy hoạch, Đại học Vinh [4] Nguyễn Duy Tiến - Vũ Viết Yên (2001), Lý thuyết xác suất, NXB Giáo dục, Hà Nội [5] P Kall and S W Wallace (2003), Stochastic Programming, John & Sons, February 4, 2003 [6] A Shapiro, D Dentcheva and A Ruszczy´ nski (2010), Lectures on Stochastic Programming: Modeling and Theory, Mathematical Programming Society Philadelphia [7] A J.Kleywegt, A Shapiro and T Homem-de-Mello (2000), The Sample Average Approximation Method for Stochastic Discrete Optimization, Department of Industrial, Welding and Systems Engineerin, The Ohio State University, Columbus ... chặt Tuy nhiên, trình giải phụ thuộc vào tốn xấp xỉ trung bình mẫu (2.2) phương pháp sử dụng để giải tốn xấp xỉ trung bình mẫu, độ phức tạp để giải tốn xấp xỉ trung bình mẫu tăng lên tuyến tính thường... để giải Trong luận văn này, đưa phương pháp xấp xỉ trung bình mẫu để giải tốn tối ưu rời rạc ngẫu nhiên ý tưởng phương pháp mẫu ngẫu nhiên tạo thành hàm giá trị kì vọng xấp xỉ hàm trung bình mẫu. .. thấy có nhiều nội dung liên quan đến tốn tối ưu binh chủng pháo binh Vì vậy, chọn đề tài nghiên cứu: "Phương pháp xấp xỉ trung bình mẫu giải tốn thơng tin huy trận địa pháo có tính ngẫu nhiên"