BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI TRIỆU THU THỦY MÔ HÌNH ĐIỀU KHIỂN MARKOV RỜI RẠC VỚI THỜI GIAN VÔ HẠN Chuyên ngành : LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC Mã số : 60 46 01.06 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS NGUYỄN HỒNG HẢI HÀ NỘI - 2017 Mục lục Lời cam đoan Phần mở đầu Lời cảm ơn Kiến thức chuẩn bị 1.1 Quá trình Markov xích Markov 1.2 Mô hình điều khiển Markov 1.2.1 Định nghĩa mô hình điều khiển Markov 1.2.2 Chiến lược điều khiển 1.2.3 Quá trình điều khiển Markov với thời gian rời rạc 1.3 Chiến lược điều khiển Markov 1.3.1 Chiến lược điều khiển Markov 1.3.2 Quá trình điều khiển Markov rời rạc Bài toán điều khiển ngẫu nhiên dạng hàm giá suy giảm với thời gian vô hạn 2.1 Một số khái niệm mở đầu 2.2 Phương trình tối ưu dạng Bellman 2.2.1 Định nghĩa nghiệm phương trình tối ưu Bellman 2.2.2 Chiến lược tối ưu 2.3 Một số tính chất bổ sung cho phương trình tối ưu Bellman 2.4 Chiến lược lặp xấp xỉ giá tối ưu 2.4.1 Xấp xỉ hàm giá bị chặn 2.4.2 Xấp xỉ đệ quy giá bị chặn 2.4.3 Chiến lược lặp 2.5 Điều kiện tối ưu 2.6 Tiệm cận tối ưu 2.6.1 Định nghĩa tiệm cận tối ưu 9 10 10 11 12 13 13 15 19 19 20 20 21 27 31 32 32 32 34 38 39 2.7 2.6.2 Điều kiện để tiệm cận điểm tối ưu tiệm cận tối ưu 40 2.6.3 Chiến lược lặp 41 Bài toán tối ưu với hàm giá dạng bậc 44 Bài toán điều khiển trình Markov với dạng hàm giá trung bình khoảng thời gian vô hạn 3.1 Định nghĩa mô hình điều khiển ngẫu nhiên 3.1.1 Xây dựng mô hình 3.1.2 Định nghĩa giá bước nhảy thứ n 3.1.3 Định nghĩa hàm giá 3.1.4 Định nghĩa chiến lược điều khiển tối ưu 3.2 Công thức tính xác suất chuyển số tính toán bổ trợ 3.2.1 Định nghĩa xác suất chuyển 3.2.2 Xác định rn (x, µ) 3.3 Sự tồn chiến lược tối ưu 3.4 Tìm chiến lược tối ưu giá tối ưu 48 48 48 49 50 50 51 51 51 52 55 Kết luận 61 Tài liệu tham khảo 62 Lời cam đoan Tôi xin cam đoan luận văn kết nghiên cứu cá nhân Các số liệu tài liệu trích dẫn luận văn trung thực Kết nghiên cứu không trùng với công trình công bố trước Tôi chịu trách nhiệm với lời cam đoan Hà Nội, ngày 05 tháng năm 2017 Tác giả luận văn Triệu Thu Thủy Phần mở đầu I LÝ DO CHỌN ĐỀ TÀI Trong năm gần đây, mô hình điều khiển trình Markov ý nghiên cứu nhiều Những mô hình với giả định khác không gian trạng thái, không gian điều khiển, dạng hàm giá xem xét nhiều tác giả như: I.I Gikhman, A.B Skorokhod, Arapostathis, Kumar and Tangiralla; Bokar, Xi-Ren Cao, Chang, Fard, Marcus Shayman; Liu Một số ứng dụng mô hình điều khiển Markov lĩnh vực khác kinh tế, khoa học nghiên cứu Sennott, Karel Sladky, Trong luận văn này, tác giả giới thiệu số kết mô hình điều khiển Markov rời rạc với hai dạng hàm giá bản: Thứ nhất, hàm giá dạng suy giảm với thời gian vô hạn: ∞ V (π, x) := Exπ αt c(xt , at ) , π ∈ Π, x ∈ X t=0 Thứ hai, hàm giá dạng trung bình với thời gian vô hạn Ψx (U ) = n lim ExU n→∞ n rk (xk , µk ) k=1 Kết thu luận văn đưa phương trình tối ưu dạng Bellman, nêu định nghĩa, điều kiện tồn cách xác định chiến lược điều khiển tối ưu giá tối ưu Ngoài ra, xây dựng mô hình trình ngẫu nhiên rời rạc điều khiển khoảng thời gian vô hạn Với lý trên, hướng dẫn tận tình TS Nguyễn Hồng Hải, chọn luận văn thạc sĩ mang tên Mô hình điều khiển Markov rời rạc với thời gian vô hạn II MỤC ĐÍCH NGHIÊN CỨU Giới thiệu mô hình điều khiển trình Markov rời rạc với thời gian vô hạn Cụ thể phương trình tối ưu Bellman, nghiên cứu giá tối ưu chiến lược tối ưu với hai dạng hàm giá: dạng suy giảm dạng trung bình khoảng thời gian vô hạn III ĐỐI TƯỢNG NGHIÊN CỨU • Mô hình điều khiển Markov • Mô hình điều khiển Markov rời rạc với thời gian vô hạn • Phương trình tối ưu Bellman, giá tối ưu chiến lược điều khiển tối ưu với dạng hàm giá khác IV PHƯƠNG PHÁP NGHIÊN CỨU • Phương pháp nghiên cứu lí luận: đọc tài liệu, sách báo liên quan đến luận văn, tìm kiếm tài liệu mạng • Sử dụng phương pháp phân tích để nắm vững vấn đề cách chi tiết • Sử dụng phương pháp tổng hợp, tổng hợp lại kiến thức, trình bày vấn đề theo trình tự logic V NHỮNG ĐÓNG GÓP CỦA LUẬN VĂN Tổng hợp trình bày hai mô hình điều khiển trình Markov với dạng hàm giá suy giảm hàm giá dạng trung bình khoảng thời gian vô hạn VI.CẤU TRÚC LUẬN VĂN Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo nội dung bao gồm chương: Chương Kiến thức chuẩn bị nêu lên khái niệm, tính chất cần thiết cho chương sau định nghĩa trình điều khiển Markov, chiến lược điều khiển Markov Chương 2: Bài toán điều khiển ngẫu nhiên dạng hàm giá suy giảm với thời gian vô hạn Trong chương nêu định nghĩa, điều kiện tồn giá tối ưu chiến lược tối ưu, phương pháp xấp xỉ hàm giá tối ưu Phần cuối chương giới thiệu toán cụ thể với hàm giá dạng bậc đưa phương pháp xác định hàm giá tối ưu trường hợp cụ thể Chương 3: Bài toán điều khiển trình Markov với dạng hàm giá trung bình khoảng thời gian vô hạn Trong chương tác giả xây dựng mô hình điều khiển cho toán điều khiển trình Markov với bước nhảy Poisson liên quan đến trình semi Markov Lời cảm ơn Trong trình học tập, nghiên cứu hoàn thành luận văn "Mô hình điều khiển Markov rời rạc với thời gian vô hạn", nhận hướng dẫn, giúp đỡ động viên nhiều cá nhân tập thể, xin bày tỏ lòng biết ơn tới tất cá nhân tập thể tạo điều kiện giúp đỡ Đầu tiên, xin bày tỏ lòng biết ơn chân thành tới thầy cô giáo khoa Toán, đặc biệt thầy Bộ môn Toán ứng dụng Trường Đại học Sư phạm Hà Nội mang đến cho kiến thức bổ ích năm học vừa qua công việc tới Tôi xin gửi lời cảm ơn sâu sắc đến TS Nguyễn Hồng Hải - Người thầy trực tiếp hướng dẫn, tận tình bảo, giúp đỡ trình nghiên cứu hoàn thành luận văn Cuối xin gửi lời cảm ơn đến gia đình, bạn bè bên tôi, động viên khuyến khích trình thực đề tài nghiên cứu Tôi mong nhận ý kiến đóng góp thầy cô, bạn bè người quan tâm để luận văn hoàn thiện phát triển Tôi xin chân thành cảm ơn! Hà Nội, ngày 05 tháng năm 2017 Triệu Thu Thủy Chương Kiến thức chuẩn bị 1.1 Quá trình Markov xích Markov Định nghĩa 1.1.1 Trên không gian xác suất (Ω, F, P ), xét trình ngẫu nhiên Xt với t ≥ Ký hiệu σ - đại số cảm sinh sau: F≤t = σ(Xs |s ≤ t) Ft = σ(Xt ) Quá trình Xt gọi trình Markov thỏa mãn điều kiện sau: E(Xh |F≤t ) = E(Xh |Ft ) với ∀h > t (1.1) Hệ thức (1.1) gọi tính Markov Các trường hợp đặc biệt trình Markov: Ký hiệu E không gian trạng thái trình Xt vớit ≥ 0, tức là: E := {Xt | ∀t} + Nếu lực lượng tập E không đếm trình Xt gọi xích Markov + Nếu t ∈ [0, +∞) Xt gọi trình Markov với thời gian liên tục + Nếu t = 0, 1, 2, hay t ∈ N Xt gọi trình Markov với thời gian rời rạc + Nếu xích Markov có t ∈ [0, +∞) Xt gọi Xích Markov với thời gian liên tục + Nếu xích Markov có t ∈ N Xt gọi Xích Markov với thời gian rời rạc Định nghĩa 1.1.2 Xét {Xt } xích Markov với thời gian rời rạc Đặt: p(s, i, t, j) = P{X(t) = j|X(s) = i}, (s < t) xác suất để thời điểm s xích trạng thái i, đến thời điểm t chuyển sang trạng thái j , gọi tắt xác suất chuyển Nếu xác suất chuyển phụ thuộc vào (t − s) tức là, p(s, i, t, j) = p(s + h, i, t + h, j) với ∀h > ta xích Markov rời rạc theo thời gian 1.2 1.2.1 Mô hình điều khiển Markov Định nghĩa mô hình điều khiển Markov Trước định nghĩa trình điều khiển Markov, ta có số quy ước ký hiệu sau: Không gian Borel: X không gian Borel X không gian metric đầy, khả ly σ− đại số sinh tập mở X σ− đại số Borel, kí hiệu B(X) Hàm đo được: Xét hai không gian đo (X, B(X)) (E, B(E)) Một hàm số f : X → E gọi đo "Borel đo được" f −1 (A) ∈ B(X) với A ∈ B(E) Hạt nhân ngẫu nhiên: Cho X Y hai không gian Borel Một hạt nhân ngẫu nhiên X cho Y hàm số P (.|.) thỏa mãn điều kiện sau: (i) P (.|y) độ đo xác suất X với y ∈ Y cố định (ii) P (B|.) hàm số đo Y với B ∈ B(X) cố định Lớp tất hạt nhân ngẫu nhiên X cho Y ký hiệu P(X|Y ) 10 Chương Bài toán điều khiển trình Markov với dạng hàm giá trung bình khoảng thời gian vô hạn 3.1 3.1.1 Định nghĩa mô hình điều khiển ngẫu nhiên Xây dựng mô hình Giả sử tồn hai dãy biến ngẫu nghiên độc lập {ηn |n = 1, 2, } {ξn |n = 1, 2, } xác định không gian xác suất (Ω, A, P ) Từng dãy độc lập thỏa mãn điều kiện sau: (i) ξn > với n = 1, 2, (mod P ), ηn > với n = 1, 2, (mod P ) (ii)   E|ξn |p < +∞, n = 1, 2, , p ≥  E|ηn |q < +∞, n = 1, 2, , q ≥ Xét hệ thống điều khiển ngẫu nhiên với trình trạng thái {xn } ∈ R với n = 1, 2, 3, Điều khiển trình trạng thái xn {un = u(µn )|n = 1, 2, } miêu tả sau: Với trạng thái ban đầu tùy ý x1 = x(x ∈ R) Tại bước nhảy thứ nhất, 48 xác định dãy biến điều khiển sau: u1 = u(µ1 ) := {ξ1,j |j = 1, 2, , νµ1 (ξ1 ) + 1}, a.s ξ1,j dãy biến ngẫu nhiên độc lập có phân phối mũ tham số µ1 (µ1 > 0) νµ1 (ξ1 ) biến ngẫu nhiên định nghĩa sau: νµ1 (ξ1 ) νµ1 (ξ1 )+1 ξ1,j ≤ ξ1 < j=1 ξ1,j a.s j=1 Giá trị µ1 gọi tham số điều khiển bước nhảy Bằng quy nạp, bước nhảy thứ n (n ≥ 1), trình trạng thái xn biến điều khiển un = u(µn ) chọn tương ứng với tham số µn (µn > 0), trạng thái xn+1 xác định biểu thức sau: xn+1 = ηn + xn − νµn (ξn ), đó, dãy biến điều khiển xác định un+1 = u(µn+1 ) := {ξn+1,j |j = 1, 2, , νµn+1 (ξn+1 ) + 1} ξn+1,j dãy biến ngẫu nhiên độc lập có phân phối mũ với tham số µn+1 (µn+1 > 0) νµn+1 (ξn+1 ) dãy biến ngẫu nhiên xác định bởi: νµn+1 (ξn+1 ) νµn+1 (ξn+1 )+1 ξn+1,j ≤ ξn+1 < j=1 ξn+1,j , a.s j=1 µn+1 gọi tham số điều khiển bước nhảy thứ n + U = {un = u(µn )|n = 1, 2, } gọi chiến lược điều khiển Hàm giá r : K −→ R định nghĩa phần sau 3.1.2 Định nghĩa giá bước nhảy thứ n Nếu bước nhảy thứ n, trình trạng thái x điều khiển u với tham số µ(µ > 0) ta định nghĩa giá bước nhảy công thức: ξn rn (x, µ) = E a[νµn (ξn ) + 1] + [ηn + xn − νµn (t)]2 dt|xn =x,µn =µ , (3.1) a số dương, νµ (t) số biến ngẫu nhiên độc lập, có phân phối mũ với tham số µ(µ > 0) cho tổng chúng nhỏ t(t > 0) (νµ (t) có phân phối Poisson với tham số µt) 49 3.1.3 Định nghĩa hàm giá Nếu U = {un = u(µn )|n = 1, 2, } chiến lược điều khiển trình ngẫu nhiên X = {xn , n = 1, 2, } với trạng thái ban đầu x1 = x Tại thời điểm t = n ta có giá trị trung bình giá là: n n rk (xk , µk ) k=1 Khi đó, hàm giá xác định sau: Ψx (U ) = n lim E U n→∞ x n rk (xk , µk ) , (3.2) k=1 đó, ExU (.) ký hiệu kỳ vọng lấy theo độ đo xác suất cảm sinh từ trình {Xk |k = 1, 2, } biểu thức với trạng thái ban đầu x1 = x chiến lược điều khiển U Ta ký hiệu M tập hợp gồm chiến lược U cho giới hạn sau tồn hữu hạn: lim ExU n→∞ 3.1.4 n n rk (xk , µk ) , ∀x ∈ R k=1 Định nghĩa chiến lược điều khiển tối ưu Hàm số ρ(x) = inf Ψx (U ) U ∈M với ∀x ∈ R gọi giá tối ưu Một chiến lược U ∗ thỏa mãn Ψx (U ∗ ) = Ψx (U ), ∀x ∈ R U ∈M gọi chiến lược tối ưu tồn 50 (3.3) 3.2 Công thức tính xác suất chuyển số tính toán bổ trợ 3.2.1 Định nghĩa xác suất chuyển Ta dễ thấy {xn , n = 1, 2, } xích Markov Xét xác suất Pn+1 (x, y, µ) xác suất bước nảy thứ n + hệ thống trạng thái y với điều kiện bước n rạng thái x điều khiển u = u(µn ), µn tham số điều khiển bước thứ n: Pn+1 (x, y, µ) = P [xn+1 < y|xn =x,µn =µ ] = P [ηn + x − νµ (ξn ) < y] = P {∪∞ k=0 [ηn + x − νµ (ξn ) < y] ∩ [νµ (ξn ) = k]} ∞ P {[ηn + x − νµ (ξn ) < y] ∩ [νµ (ξn ) = k]} = k=0 ∞ P {νµ (ξn ) = k}.P {[ηn + x − νµ (ξn ) < y]|νµ (ξn )=k } = k=0 ∞ = e k=0 ∞ = e k µt (µt) k! k µt (µt) k! k=0 Fξn (dt) P {ηn + x − k < y} Fξn (dt) Fηn (y − x + k) ta có: ∞ Pn+1 (x, dy, µ) = k µt (µt) e k=0 k! Fξn (dt) Fηn (dy − x + k) (3.4) Do đó, ta thu được: V (y)Pn+1 (x, dy, µ) = EV (ηn + x − νµ (ξn )) 3.2.2 (3.5) Xác định rn (x, µ) Ta có: ξn rn (x, µ) = E a[νµ (ξn ) + 1] + 51 [ηn + x − νµ (t)]2 dt (3.6) từ Eνµ (ξn ) = µE(ξn ) ξn Eξn2 E νµ (t)dt = µ ξn Eξn2 2 Eξn +µ , E νµ (t)dt = µ ta có với ∀x ∈ N+ : Eξn Eξn2 rn (x, µ) = µ + aE(ξn ) + − (Eηn + x)Eξn2 µ+[a+E(ξn )E(ηn +x)2 ] (3.7) Xét trường hợp {ηn |n = 1, 2, } {ξn |n = 1, 2, } độc lập phân phối với ξ, η ξ, η độc lập: Fξn (t) ≡ Fξ (t), n = 1, 2, Fηn (t) ≡ Fη (t), n = 1, 2, trường hợp rn (x, µ) ≡ r(x, µ), n = 1, 2, 3.3 Sự tồn chiến lược tối ưu Định lí 3.3.1 Nếu tồn số S hàm số V (x) cho: V (x) ≤ Ax2 + Bx + C, ∀x ∈ R S + V (x) = inf µ>0 r(x, µ) + V (y)P (x, dy, µ) (3.8) với A, B, C số, S ≤ inf Ψx (U ) U ∈M (3.9) Chứng minh Giả sử U ∈ M chiến lược bất kỳ, X = {xk |k = 1, 2, , x1 = x} trạng thái tương ứng với chiến lược U , thì: n n n−1 r(xk , µk ) = n n−1 k=1 52 n−1 r(xk , µk ) + r(xn , µn ) n k=1 thế: ExU n n r(xk , µk ) k=1 n−1 U = Ex n n−1 n−1 r(xk , µk ) + ExU {r(xn , µn )} n k=1 U ∈ M nên giới hạn sau tồn hữu hạn: lim ExU n→∞ n n r(xk , µk ) Theo công thức (3.9) (3.10) ta có: Ex2n = 0, lim n→∞ n Exn lim = n→∞ n 53 (3.12) Vì V (x) ≤ Ax2 + Bx + C với ∀x ∈ R ta có: EV (xn ) E(Ax2n + Bxn + C) ≤ n n (3.13) Đặt Fn = σ(x1 , µ1 , x2 , µ2 , , xn , µn ) F1 ⊂ F2 ⊂ ⊂ Fn ⊂ A Áp dụng tính Markov từ phương trình Bellman (3.8) ta thu được: E(V (xk )|Fk−1 ) = V (y)P (xk−1 , dy, µk−1 ) ≥ S + V (xk−1 ) − r(xk−1 , µk−1 ) ⇒ S + V (xk−1 ) ≤ r(xk−1 , µk−1 ) + E(V (xk )|Fk−1 ), ⇒ ExU (S + V (xk−1 )) ≤ ExU [r(xk−1 , µk−1 ) + E(V (xk )|Fk−1 )], ⇒ S + EV (xk−1 ) ≤ ExU r(xk−1 , µk−1 ) + E(V (xk )), n n ⇒ [ExU r(xk−1 , µk−1 ) + EV (xk )], [S + EV (xk−1 )] ≤ k=2 k=2 n ExU r(xk−1 , µk−1 ) + EV (xn ) − EV (x1 ), ⇒ (n − 1)S ≤ k=2 ⇒S≤ n−1 ExU n−1 r(xk , µk ) + k=1 n EV (xn ) EV (x1 ) − , (3.14) n−1 n n−1 Bằng công thức (3.9) (3.10) ta có: S≤ ExU n−1 n−1 r(xk , µk ) k=1 ⇒S≤ lim ExU n→∞ n E(Ax2n + Bxn + C) EV (x1 ) + − , n−1 n n−1 n−1 n−1 r(xk−1 , µk−1 ) k=1 từ (3.12) lim n→∞ n E(Ax2n + Bxn + C) EV (x1 ) − n−1 n n−1 ⇒ S ≤ Ψx (U ), ∀x ∈ R 54 =0 Vì U chiến lược tùy ý nên ta có: S ≤ inf Ψx (U ), ∀x ∈ R U ∈M Hệ 3.3.2 Nếu tồn số S hàm số V (x) cho: |V (x)| ≤ Ax2 + Bx + C, ∀x ∈ R S + V (x) = r(x, µ) + V (y)P (x, dy, µ) µ>0 = r(x, µ∗ (x)) + V (y)P (x, dy, µ∗ (x)), ∀x ∈ R với A, B, C, (A > 0) số, U ∗ = {u∗n = u(µ∗n )|n = 1, 2, } chiến lược tối ưu Ψx (U ∗ ) = S 3.4 Tìm chiến lược tối ưu giá tối ưu Đặt: Rn (x) = inf U ∈M ExU n n r(xk , µk ) , ∀x ∈ R, n = 1, 2, (3.15) k=1 Bổ đề 3.4.1 Hàm số Rn (x) thỏa mãn phương trình Bellman, với ∀x ∈ R, n ≥ Rn+1 (x) = inf µ>0 n r(x, µ) + n+1 n+1 55 Rn (y)P (x, dy, µ) (3.16) Chứng minh Ta có: Rn+1 (x) = inf U ∈M = inf U ∈M = inf U ∈M = inf µ>0 = inf µ>0 ExU ExU ExU n+1 n+1 r(xk , µk ) k=1 n r(x1 , µ1 ) + n+1 n+1 n n+1 r(xk , µk ) k=2 n r(x1 , µ1 ) + ExU2 n+1 n+1 n n+1 r(xk , µk ) k=2 n r(x, µ) + Rn (x2 ) n+1 n+1 n r(x, µ) + Rn (y)P (x, dy, µ) n+1 n+1 Vậy ta chứng minh (3.16) Giả sử x biến ngẫu nhiên tùy ý, ta nói x thỏa mãn điều kiện (I) nếu: x> aEξ + − Eη (modP ) aEξ 2 (3.17) Bổ đề 3.4.2 Nếu bước nhảy thứ n với (n ≥ 1), trạng thái x hệ thống thỏa mãn điều kiện (I) µ∗ (x) > 0, ngược lại điều kiện (I) không thỏa mãn µ∗ (x) = 0, µ∗ (x) xác định phương trình: r(x, µ∗ (x)) = inf r(x, µ) µ>0 Chứng minh Từ biểu thức: r(x, µ) = với từ Eξ Eξ µ + aEξ + − (Eη + x)Eξ µ + [a + EξE(η + x)2 ], ∂r(x, µ) 2Eξ Eξ = µ + aEξ + − (Eη + x)Eξ , ∂µ ∂r(x,µ) ∂µ (Eη + x)Eξ − aEξ − =0⇔µ= 3 Eξ 56 Eξ 2 Vì Eξ 3 > nên r(x, µ) đạt giá trị nhỏ tại: (Eη + x)Eξ − aEξ − ∗ µ=µ = 3 Eξ Eξ 2 Eξ µ > ⇔ (Eη + x)Eξ − aEξ − >0 aEξ ⇔x> + − Eη Eξ 2 ∗ Nếu điều kiện (I) không thỏa mãn µ∗ (x) = 0, vì: inf r(x, µ) = r(x, 0) µ>0 r(x, 0) = a + EξE(η + x)2 Khi đó, bổ đề chứng minh Bổ đề 3.4.3 Giả sử U = {u(µn )|n = 1, 2, } (với µn = µ∗n (x)) chiến lược điều khiển trình {xn |n = 1, 2, , x1 = x} Thì lim Exn = A n→∞ lim Ex2n = B n→∞ lim n n→∞ lim n n→∞ lim n n→∞ n n n n Exk − A = A1 x + B1 k=1 n (Exk )2 − A2 = A2 x2 + B2 x + C2 k=1 n Ex2k − B = A3 x2 + B3 x + C3 k=1 A, B, A1 , B1 , A2 , B2 , C2 , A3 , B3 , C3 số Chứng minh Từ cách xác định µ∗ ta có phương trình sau: xn = ηn−1 + xn−1 − νµ∗n−1 (ξn−1 ), n = 2, 3, Không tính tổng quát, giả sử Eη > (trong trường hợp Eη < thu kết tương tự ) 57 Chúng ta ký hiệu chiến lược với tham số µ∗n xác định bổ đề 3.4.2 U ∗ := {u∗n = un (µ∗n )|n = 1, 2, } trình điều khiển chiến lược U ∗ với điều kiện ban đầu x∗1 = x {x∗n |n = 1, 2, } Nếu bước nhảy thứ k , điều kiện (I) không thỏa mãn thì: x∗k = η + x∗k−1 tương đương với x∗n =   η + x∗n−1 − νµ∗ (ξn−1 ), n−1  η + x∗ , n−1 bước nhảy thứ n điều kiện (I) thỏa mãn Chúng ta thiết lập trình {x∗n |n = 1, 2, } xác định sau:   x∗n = x∗n−1  x∗ n = lEη + x∗n , điều kiện (I) thỏa mãn, l số nguyên dương cho: lEη + x∗n ≤ aEξ + < (1 + l)Eη + x∗n , (mod P ) Eξ Theo bổ đề 3.4.3, dễ thấy dãy phương sai Dx∗n = Ex∗n − (Ex∗n )2 bị chặn Kết hợp với kết bổ đề 3.4.3, sử dụng luật mạnh số lớn, với xác suất ta có lim x∗n = A > n→∞ aEξ + < (1 + l)Eη + x∗n Eξ thế, tồn số nguyên dương N cho ∀n ≥ N điều kiện (I) thỏa mãn hầu chắn Mặt khác, với ∀n ≥ N x∗n = x∗n , a.s 58 Vì vậy, áp dụng bổ đề 3.4.3 thỏa mãn cho trình {x∗n |n = 1, 2, } Dễ thấy rằng: ∗ lim ExU n→∞ n ∗ lim ExU n→∞ n = ∗ lim ExU n→∞ n r(x∗k , µ∗k ) = k=1 n ∗ lim ExU m→∞ m n r(x∗k , µ∗k ) − k=1 n n r(x∗k , µ∗k ) n ∗ lim ExU n→∞ − k=1 ∗ lim ExU m→∞ r(x∗k , µ∗k ) , k=1 m r(x∗k , µ∗k ) k=1 m m r(x∗k , µ∗k ) k=1 Từ mối quan hệ ta thu kết bổ đề Bổ đề 3.4.4 Kết bổ đề 3.4.3 thỏa mãn với trình {x∗n |n = 1, 2, } dãy thỏa mãn điều kiện (I) Bổ đề 3.4.5 Với ∀x ∈ R có: lim Rn (x) = S, n→∞ lim n[Rn (x) − S] = Ax2 + Bx + C n→∞ Cách chứng minh tương tự bổ đề 3.4.3 Định lí 3.4.6 Hằng số S hàm số V (x) xác định bổ đề 3.4.5 thỏa mãn phương trình Bellman sau: S + V (x) = inf µ>0 V (y)P (x, dy, µ) , ∀x ∈ R r(x, µ) + Chứng minh Chúng ta có: Rn+1 (x) = inf µ>0 n r(x, µ) + n+1 n+1 ⇒ S+(n+1)[Rn+1 (x)−S] = inf µ>0 S + V (x) = inf µ>0 r(x, µ) + n r(x, µ) + Vậy định lý chứng minh xong 59 Rn (y)P (x, dy, µ) , [Rn (y) − S]P (x, dy, µ) , V (y)P (x, dy, µ) Từ kết phát biểu chứng minh ta đến định lý sau: Định lí 3.4.7 Nếu tồn chiến lược U ∗ thỏa mãn S + V (x) = inf µ>0 r(x, µ) + = r(x, µ) + µ>0 = r(x, µ∗ (x)) + V (y)P (x, dy, µ) , V (y)P (x, dy, µ) , V (y)P (x, dy, µ∗ (x)), U ∗ chiến lược tối ưu với trình ngẫu nhiên tương ứng {x∗n |n = 1, 2, } giá S = Ψx (U ) hữu hạn với ∀x ∈ R 60 Kết luận Những kết đạt luận văn: Đối với hàm giá dạng suy giảm với thời gian vô hạn: ∞ V (π, x) := Exπ αt c(xt , at ) , π ∈ Π, x ∈ X t=0 Luận văn đưa phương trình tối ưu Bellman, định nghĩa giá tối ưu chiến lược tối ưu, điều kiện tồn chiến lược tối ưu số phương pháp xấp xỉ giá tối ưu Ngoài ra, luận văn đưa công thức cụ thể giá tối ưu chiến lược tối ưu cho dạng đặc biệt với hàm giá bậc hai c(x, a) = q.x2 + r.a2 (với q, r số dương) Tiếp theo, luận văn xây dựng mô hình điều khiển liên quan đến trình Semi - Markov với bước nhảy Poisson khoảng thời gian vô hạn, với hàm giá dạng trung bình: Ψx (U ) = n lim ExU n→∞ n rk (xk , µk ) k=1 Với mô hình đó, luận văn đưa phương trình tối ưu Bellman, điều kiện tồn chiến lược tối ưu giá tối ưu cho toán Một số ý định nghiên cứu tiếp theo: nghiên cứu số dạng mô hình ứng dụng thực tiễn 61 Tài liệu tham khảo [1] Nguyễn Duy Tiến, Đặng Hùng Thắng.Các mô hình xác suất ứng dụng Phần I Xích Markov ứng dụng NXB Đại học Quốc gia Hà Nội Hà Nội (2001) [2] Nguyễn Duy Tiến, Vũ Viết Yên Lý thuyết xác suất NXB Giáo dục Hà Nội (2006) [3] I.I Gihman, A.V.Skorohod Controlled Stochatic Processes Translated by Samuel Kotz Springer - Verlag (1980) [4] Nguyen Hong Hai, Đang Thanh Hai The Model of Stochastic Control and Applications Vietnam Journal of Mathematics 409 - 419 Ha Noi (2005) [5] Onésimo Hernánder Lema, Jean Bernard Lasserre.Discrete - Time Markov Controll Processes Basic optimality criteria Springer (1996) 62 ... Nguyễn Hồng Hải, chọn luận văn thạc sĩ mang tên Mô hình điều khiển Markov rời rạc với thời gian vô hạn II MỤC ĐÍCH NGHIÊN CỨU Giới thiệu mô hình điều khiển trình Markov rời rạc với thời gian vô hạn. .. tối ưu với hai dạng hàm giá: dạng suy giảm dạng trung bình khoảng thời gian vô hạn III ĐỐI TƯỢNG NGHIÊN CỨU • Mô hình điều khiển Markov • Mô hình điều khiển Markov rời rạc với thời gian vô hạn •... khiển Markov với thời gian rời rạc 1.3 Chiến lược điều khiển Markov 1.3.1 Chiến lược điều khiển Markov 1.3.2 Quá trình điều khiển Markov rời rạc Bài toán điều