Tài liệu Luận văn mô hình điều khiển markov rời rạc với thời gian hữu hạn và một ứng dụng trong lý thuyết đổi mới

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN - TIN ————————–o0o————————– LUẬN VĂN THẠC SĨ TOÁN HỌC Tên đề tài MÔ HÌNH ĐIỀU KHIỂN MARKOV RỜI RẠC VỚI THỜI GIAN HỮU HẠN VÀ MỘT ỨNG DỤNG TRONG LÍ THUYẾT ĐỔI MỚI Chuyên ngành Mã số Học viên Giảng viên hướng dẫn : : : : Lý thuyết Xác suất và Thống kê Toán học 60.46.01.06 Nguyễn Đức Anh TS.Nguyễn Hồng Hải HÀ NỘI - 2017 Mục lục Phần mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 KIẾN THỨC CHUẨN BỊ 1.1 Giới thiệu chung về quá trình điều khiển Markov 1.1.1 Giải thích . . . . . . . . . . . . . . . . . 1.2 Các ví dụ . . . . . . . . . . . . . . . . . . . . . 1.2.1 Ví dụ về quản lí nghề cá . . . . . . . . . 1.2.2 Ví dụ danh mục đầu tư lựa chọn . . . . . 1.2.3 Ví dụ về hệ thống tồn kho - sản xuất . . 1.3 Chính xác hóa về quá trình điều khiển Markov . 1.4 Các chiến lược Markov . . . . . . . . . . . . . . 1.5 Tính chất Markov . . . . . . . . . . . . . . . . . 2 BÀI TOÁN VỚI THỜI GIAN HỮU HẠN 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . 2.2 Quy hoạch động . . . . . . . . . . . . . . . 2.3 Điều kiện chọn đo được . . . . . . . . . . . 2.4 Biến thể của phương trình quy hoạch động 2.5 Bài toán giá có dạng giá tuyến tính bậc hai 2.6 Bài toán tiêu thụ - đầu tư . . . . . . . . . . 2.7 Một hệ thống tồn kho - sản xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 8 8 9 10 11 14 15 . . . . . . . 18 18 18 21 23 26 29 31 3 MÔ HÌNH QUÁ TRÌNH ĐIỀU KHIỂN MARKOV BƯỚC NHẢY VÀ ÁP DỤNG 3.1 Xây dựng mô hình điều khiển . . . . . . . . . . . . . . . . . 3.2 Sự tồn tại chiến lược tối ưu . . . . . . . . . . . . . . . . . . 3.3 Phương pháp xây dựng chiến lược tối ưu và chiến lược ε tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Chiến lược tối ưu và giá tối ưu trong trường hợp đại lượng ngẫu nhiên ξ có phân phối mũ . . . . . . . . . . . . . . . . 1 3 5 34 35 36 39 41 Kết luận 43 Tài liệu tham khảo 44 2 Phần mở đầu I. LÝ DO CHỌN ĐỀ TÀI Trong những năm gần đây, mô hình xích Markov điều khiển được đang được nhiều nhà toán học quan tâm nghiên cứu. Các tác giả I.I. Gikhman, A.B. Skorokhod, Arapostathis A., Kumar R., Tangirala S., Bokar V. S, Xi-Ren Cao, Liu P. T xét mô hình xích Markov điều khiển được với các điều kiện mở rộng khác nhau: Mở rộng không gian trạng thái; mở rộng không gian pha của điều khiển và xét các dạng hàm giá khác nhau. Một số tác giả khác quan tâm nghiên cứu ứng dụng của mô hình xích Markov điều khiển được để giải quyết các bài toán trong các lĩnh vực khác nhau của thực tiễn. Chẳng hạn Brock W. A, Tapiero C. S, Goel., Richter N., Hanson F.B,.v.v.. Trong luận văn này, chúng tôi trình bày kết quả nghiên cứu về mô hình Markov rời rạc điều khiển được với khoảng thời gian hữu hạn và ứng dụng để giải quyết một lớp bài toán trong lí thuyết đổi mới, cụ thể là: sử dụng mô hình quá trình Markov điều khiển được, chúng tôi đã xây dựng mô hình và giải quyết bài toán xác định thời điểm kiểm tra tối ưu theo quan điểm của lí thuyết các quá trình ngẫu nhiên điều khiển được. Qua đó chúng tôi đã đưa ra phương pháp để giải quyết bài toán này, đồng thời đưa ra các kết quả đối với mô hình quá trình Markov điều khiển được đã được xây dựng tương ứng. II. MỤC ĐÍCH NGHIÊN CỨU Giới thiệu các khái niệm về mô hình điều khiển quá trình Markov rời rạc với thời gian hữu hạn, tập trung chính vào các vấn đề: sự tồn tại chiến lược tối ưu, xây dựng chiến lược tối ưu và nghiên cứu giá tối ưu. 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 hữu hạn. • Mô hình quá trình Markov bước nhảy bị điều khiển và ứng dụng. 3 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 và các bài báo liên quan đến luận văn, tìm kiếm tài liệu trên mạng. • Sử dụng phương pháp phân tích để nắm vững vấn đề một cách chi tiết. • Sử dụng phương pháp tổng hợp, tổng hợp lại các kiến thức, trình bày vấn đề theo trình tự logic V. CẤU TRÚC LUẬN VĂN Nội dung của luận văn bao gồm ba chương: Chương 1: Kiến thức chuẩn bị Nêu ra những khái niệm, tính chất cần thiết cho các chương sau như định nghĩa quá trình điều khiển Markov, các ví dụ về quá trình điều khiển và định nghĩa chiến lược Markov. Chương 2: Bài toán với thời gian hữu hạn Chương này đưa ra định lí về quy hoạch động và các biến thể của phương trình quy hoạch động, các điều kiện chọn đo được và bài toán tuyến tính bậc hai. Chương 3: Mô hình quá trình Markov bước nhảy bị điều khiển và áp dụng Trong chương này chúng tôi trình bày một mô hình Markov bước nhảy bị điều khiển và ứng dụng trong lí thuyết đổi mới. Để thực hiện điều đó, chúng tôi trình bày: xây dựng mô hình điều khiển phù hợp với bài toán trong lí thuyết đổi mới, chứng minh sự tồn tại chiến lược tối ưu và phương pháp xây dựng chiến lược tối ưu. 4 Lời cảm ơn Trong quá trình học tập, nghiên cứu và 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 hữu hạn và một ứng dụng trong lí thuyết đổi mới", chúng tôi đã nhận được sự hướng dẫn, giúp đỡ và động viên của TS.Nguyễn Hồng Hải. Chúng tôi xin bày tỏ lòng biết ơn chân thành đến sự hướng dẫn nhiệt tình của thầy. Đồng thời, chúng tôi xin gửi lời cảm ơn sâu sắc tới các thầy cô giáo trong khoa Toán, đặc biệt là các thầy trong Bộ môn Toán ứng dụng - Trường đại học Sư phạm Hà Nội đã mang đến cho chúng tôi những kiến thức bổ ích trong năm học vừa qua và trong những công việc sắp tới. Cuối cùng, chúng tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn ở bên chúng tôi, động viên và giúp đỡ chúng tôi trong quá trình thực hiện đề tài nghiên cứu của mình. Vì thời gian và trình độ có hạn, luận văn chắc chắn không thể tránh khỏi những thiếu sót. Chúng tôi hi bọng sẽ nhận được sự đóng góp ý kiến của các thầy cô và các bạn. Chúng tôi xin chân thành cảm ơn! Hà Nội, ngày 07 tháng 06 năm 2017 Nguyễn Đức Anh 5 Chương 1 KIẾN THỨC CHUẨN BỊ 1.1 Giới thiệu chung về quá trình điều khiển Markov Mô hình điều khiển với thời gian rời rạc là bộ năm: (X, A, {A(x)|x ∈ X}, Q, c) (1.1) trong đó X và A được cho trước, được gọi là không gian trạng thái và tập điều khiển tương ứng. {A(x)|x ∈ X} là một họ các tập con khác rỗng A(x) của A, với A(x) là tập các điều khiển khả thi ( hoặc các hành động khả thi ) với trạng thái x ∈ X . Cuối cùng, Q là một luật chuyển đổi, và c là một hàm chi phí mỗi giai đoạn ( hoặc hàm chi phí). Trong một số trường hợp có thể xét hàm lãi r thay vì hàm chi phí c để thuận lợi hơn. 1.1.1 Giải thích Mô hình điều khiển (1.1) là một mô hình ngẫu nhiên của hệ thống điều khiển được quan sát ở thời điểm t=0, 1, 2...Trạng thái của hệ thống kí hiệu bởi xt , còn at là điều khiển được áp dụng tại thời điểm t tương ứng, sự phát triển của hệ thống được mô tả như sau: Nếu hệ thống ở trạng thái xt = x ∈ X ở thời điểm t và điều khiển tại at = a ∈ A(x) được áp dụng thì có hai điều xảy ra: (i) chi phí c(x, a) phát sinh. (ii) hệ thống di chuyển sang trạng thái tiếp theo xt+1 , đó là một giá trị biến X - ngẫu nhiên với phân phối Q(·|x, a), tức là., Q(B|x, a) := P rob(xt+1 ∈ B|xt = x, at = a), B ⊂ X. (1.2) Khi qúa trình chuyển đổi sang trạng thái mới, một điều khiển mới được chọn và quá trình này được lặp đi lặp lại. (i) và (ii) là một đặc điểm chính của một quá trình điều khiển Markov, tức là, tại bất kì thời điểm nào, chi phí (hoặc lãi) và các luật chuyển tiếp chỉ phụ thuộc vào trạng thái hiện tại của hệ thống và các hành động hiện tại. Đối với thời điểm này, chúng 6 ta hãy giải thích chiến lược điều khiển như một chuỗi π = {at } của các hành động có tính khả thi với at ∈ A(xt ), t = 0, 1, ... và gọi Π là tập hợp của tất cả các chiến lược. Một chiến lược π và một trạng thái ban đầu xo = x quyết định một quá trình ngẫu nhiên " dạng - Markov" được gọi là quá trình điều khiển Markov ( MCP). Thực tế, do sự lạm dụng thuật ngữ, toàn bộ họ của MCPs được quyết định bởi Π được gọi là một MCP. Trong nhiều ứng dụng, sự phát triển của một MCP được xác định bởi phương trình thời gian rời rạc có dạng: xt+1 = F (xt , at , ξt ), t = 0, 1, ...; (1.3) x0 cho trước. Trong đó, {ξt } là một chuỗi các biến ngẫu nhiên độc lập cùng phân phối (i.i.d) với các giá trị trong không gian S và có phân phối chung µ, độc lập với trạng thái ban đầu x0 . (Các dãy {ξt } được gọi là một quá trình xáo trộn, nhưng thỉnh thoảng nó được gọi là một quá trình điều khiển hoặc quá trình môi trường hoặc quá trình ngoại sinh ). Trong trường hợp này, luật chuyển tiếp Q ở (1.2) được cho bởi: Q(B|x, a) = µ({s ∈ S|F (x, a, s) ∈ B}) Z = IB [F (x, a, s)]µ(ds) (1.4) S = EIB [F (x, a, ξ)] Trong đó, IB (.) là hàm chỉ tiêu của tập hợp B, E là kì vọng, và ξt là biến ngẫu nhiên với phân phối chung µ. Quan sát (1.3), trong trường hợp đặc biệt, hệ thống điều khiển tất định là xt+1 = F (xt , at ), luật chuyển tiếp (1.4) sẽ trở thành Q(B|x, a) = IB [F (x, a)] . Như đã lưu ý, để xác định một vấn đề điều khiển tối ưu, ngoài một hệ thống hành dộng và tập hợp những chiến lược, chúng ta cần một hiệu suất tiêu chuẩn - còn được gọi là chỉ số hiệu suất hoặc hàm chỉ tiêu. Trong trường hợp của chúng ta, một tiêu chuẩn hiệu suất điển hình là dự kiến tổng chi phí lên tới thời gian nhất định N , đó là, "N # X JN (π, x) := Exπ c(xt , at ) (1.5) t=0 Trong đó Exπ là kì vọng lấy theo độ đo xác suất cảm sinh của quá trình {Xk |k = 0, 1, 2...} khi sử dụng chiến lược π = {at }, với trạng thái ban đầu xo = x. Một chiến lược π ∗ sao cho JN (π ∗ , x) = inf Q JN (π, x), 7 ∀x ∈ X (1.6) được gọi là một chiến lược tối ưu, với chi phí tối thiểu (1.6), tức là: JN∗ (x) := inf ∀x ∈ X , Q JN (π, x), được gọi là hàm giá của bài toán điều khiển hoặc chi phí tối ưu. Số N trong (1.5) được gọi là sự kế hoạch hóa ( hoặc tối ưu hóa ) thời gian. Nó đại diện cho số giai đoạn trong đó hệ thống sẽ được vận hành, và nó có thể là hữu hạn hoặc vô hạn. Trong trường hợp đầu, bài toán trên được coi là một bài toán với thời gian hữu hạn, và trong trường hợp sau nó là bài toán với thời gian vô hạn. Tất nhiên, nếu N = +∞, thì tổng trong (1.5) có thể không hội tụ - ít nhất đối với một số chiến lược π . Hàm giá JN (π, x) trong (1.5) được gọi là giá tổng chi phí. Ngoài ra người ta còn xét giá dạng suy giảm theo thời gian: "N # X V (π, x) := Exπ αt c(xt , at ) + CN (xN , aN ) (1.7) t=0 trong đó α ( 0 < α < 1) được gọi là một tham số suy giảm hay còn gọi là tỷ lệ chiết khấu. Cuối cùng, nếu chi phí mỗi giai đoạn c(x, a) được thay thế bằng lãi mỗi giai đoạn r (x, a), thì kết quả điều khiển tối ưu để tối đa hóa các tiêu chuẩn chất lượng nhất định. 1.2 1.2.1 Các ví dụ Ví dụ về quản lí nghề cá Hãy xem xét một số lượng cá. Ví dụ, cá hồi, trong bất cứ mùa nào cũng có thể bị bắt và phần còn lại sẽ đẻ trứng cho mùa tới. Như vậy, trong bất kỳ mùa nào, trạng thái x của hệ thống là quy mô dân số, và hành động a là dân số được để lại để đẻ trứng. Trong trường hợp này, một giai đoạn " lãi " là bắt hoặc thu hoạch r(x, a) := x − a, và mô hình tăng trưởng dân số được giả định là hình thức (gọi là mô hình Ricker) xt+1 = θ1 at · exp(−θ2 at + ξt ), t = 0, 1, 2, ... (1.8) Trong đó θ1 và θ2 là các hằng số, và {ξt } là một chuỗi các biến ngẫu nhiên i.i.d. Để xác định một mô hình điều khiển Markov trong (1.8), chúng ta có thể lấy không gian trạng thái và hành động là X = A = R+ , trong đó R+ := [0, ∞). Khi dân số còn lại cho sinh sản không vượt quá tổng quy mô dân số, tập các hành động khả thi là A(x) := [0, x] mỗi khi hệ thống đang ở trạng thái x. Với sự phân bố xác suất của các biến "môi trường" ξt , 8 luật của quá trình chuyển đổi Q được xác định bởi (1.8), như trong (1.3) - (1.4). 1.2.2 Ví dụ danh mục đầu tư lựa chọn Ví dụ này liên quan đến các vấn đề phải đối mặt của một "nhà đầu tư nhỏ" (nghĩa là một đại lý kinh tế mà hành động không thể ảnh hưởng đến giá cả thị trường), người có quyền quyết định chiến lược tiêu thụ đầu tư tốt nhất, ông ấy / bà ấy muốn phân bổ tổng mức đầu tư các tài sản khác nhau với mức giá khác nhau. Chúng ta xem xét hai tài sản: một trong số đó là tài sản phi rủi ro hay an toàn (ví dụ, một trái phiếu) với một lãi suất cố định i, và một tài sản khác là một tài sản rủi ro (cổ phiếu) với một tỷ suất lợi nhuận ngẫu nhiên ξt đầu tư tại thời điểm t. Một chiến lược tiêu thụ đầu tư là một chuỗi π = {(pt , ct ), t = 0, 1, ...} bao gồm một quá trình danh mục vốn đầu tư {pt } và một quá trình tiêu thụ {ct }. Đó là, tại mỗi thời điểm t, pt (resp.1 − pt ) là hàm của tài sản đầu tư vào các cổ phiếu, (resp là các tài sản an toàn.) và ct là số lượng tài sản tiêu thụ; chúng phải thỏa mãn các hạn chế 0 ≤ pt ≤ 1, 0 ≤ ct ≤ 1 (1.9) trong đó xt biểu thị tài sản của nhà đầu tư tại thời điểm t. Như vậy, trạng thái hay tài sản quá trình xt phát triển theo phương trình xt+1 = [(1 − pt )(1 + i) + pt ξt ](xt − ct ), t = 0, 1, ..., (1.10) với tài sản ban đầu x0 = x > 0. Trong ví dụ này, chúng ta có thể đưa ra không gian trạng thái X := R+ và điều khiển A := [0, 1] × R+ . Từ (1.9), các tập điều khiển khả thi a = (p, c) là A(x) := [0, 1] × [0, x] bất cứ khi nào trạng thái hay tài sản là x. Giả sử {ξt } là một chuỗi các biến ngẫu nhiên i.i.d. với phân phối µ, luật chuyển đổi Q được xác định từ (1.10), như trong (1.3) - (1.4). Cuối cùng, để hoàn thành các đặc điểm kỹ thuật của một mô hình điều khiển trong (1.1), chúng ta giới thiệu một hàm lãi r(x, a) (thay vì một hàm chi phí c). Một sự lựa chọn tiêu biểu của r trong kinh tế tài chính như một "lợi ích từ tiêu dùng", tức là, với a = (p, c) ∈ A(x), r(x, a) := u(c), (1.11) trong đó u là một hàm "lợi ích" nhất định. Do đó, ví dụ, hiệu suất chỉ số trong (1.7) - thay thế c bởi r trong (1.11) - trở thành tổng dự kiến tiện ích chiết khấu từ sự tiêu thụ, và vấn đề điều khiển tối ưu tương ứng là để tối đa hóa tiêu chuẩn này trong tập tất cả chiến lược tiêu thụ đầu tư thỏa mãn (1.9). 9 1.2.3 Ví dụ về hệ thống tồn kho - sản xuất Hãy xem xét một hệ thống hàng tồn kho - sản xuất trong đó biến trạng thái xt là mức tồn kho bắt đầu của thời kỳ t (t = 0, 1, ...). Biến điều khiển hoặc biến hành động at là số lượng đặt hàng (hoặc sản xuất) và ngay lập tức được cung cấp ngay từ đầu thời kỳ t, và "nhiễu loạn" hay "ngoại sinh" biến ξt là nhu cầu trong thời gian đó. Chúng ta giả sử ξt là biến ngẫu nhiên i.i.d. Các dạng của phương trình hệ thống phụ thuộc vào các giả thiết. Ví dụ, nếu hệ thống có một sức chứa vô hạn và nhu cầu không được hoàn thành ở cuối mỗi giai đoạn đã mất, thì phương trình hệ thống là xt+1 = max(0, xt + at − ξt ), t = 0, 1, ..., (1.12) và chúng ta có thể coi không gian trạng thái và không gian hành động là X = A = A(x) = R+ với mọi x ∈ X . Tuy nhiên, nếu hệ thống có công suất C hữu hạn, phương trình hệ thống sẽ trở thành (1.12), nhưng X và A trở thành X = A = [0, C], vì tài sản hiện tại cộng với số tiền đặt hàng không thể vượt quá năng lực của hệ thống, tập các hành động khả thi là A(x) = [0, C − x] cho mỗi x ∈ X . Mặt khác, chúng ta có thể cho phép mức tồn kho "âm" bằng cách giả sử rằng số lượng đơn hàng yêu cầu vượt quá đơn hàng chưa được xử lí và đơn hàng đã được đáp ứng khi hàng tồn kho bổ sung sẵn sàng . Trong trường hợp này, thay vì (1.12), chúng ta có xt+1 = xt + at − ξt , t = 0, 1, ..., (1.13) và không gian trạng thái là X = R hoặc X = (−∞, C], dù công suất của hệ thống là vô hạn hay hữu hạn. Tương tự như vậy, các chỉ số hiệu suất có thể có các dạng khác nhau. Ví dụ, nếu chúng ta muốn tối đa hóa doanh thu dự kiến cho hoạt động của hệ thống, chúng ta có thể lấy lưới doanh thu ở giai đoạn t là r(xt , at , ξt ) := s · min(ξt , xt + at ) − d · at − h · (xt + at ) (1.14) Doanh thu bán hàng bằng doanh số bán hàng trừ đi chi phí sản xuất và trừ đi chi phí đang giữ. Trong (1.14), s, d, h là các số dương biểu thị đơn giá bán, chi phí sản xuất và đơn vị giữ chi phí tương ứng. Mặt khác, chúng ta có thể giảm thiểu chi phí vận hành dự kiến. Ví dụ, trong (1.13), cho phép hàng tồn kho âm, điển hình một giai đoạn hàm chi phí là c(xt , at , ξt ) = d · at + h · max(0, xt+1 ) + p · max(0, −xt+1 ) (1.15) trong đó d là chi phí các đơn vị sản xuất (hoặc sức mua), h là đơn vị nắm giữ chi phí cho hàng tồn kho dư thừa, và p là chi phí thiếu hụt (hoặc chi phí xử phạt) dành cho yêu cầu chưa được hoàn thành. Với bất kì phương 10 trình hệ thống và lãi hoặc hàm chi phí nào chúng ta có, chúng ta cũng có thể viết các mô hình theo dạng (1.1). Đặc biệt, viết các chi phí (1.15) dưới dạng c(x, a), mà chỉ phụ thuộc vào trạng thái và điều khiển nhưng không phải trên các biến xáo trộn, chúng ta có thể định nghĩa c(x, a) := E[c(xt , at , ξt )|xt = x, at = a] Z = c(x, a, s)µ(ds) trong đó µ là kí hiệu phân bố của ξ . 1.3 Chính xác hóa về quá trình điều khiển Markov Trước khi định nghĩa quá trình điều khiển Markov, ta có một số quy ước và ký hiệu sau: Không gian Borel: X là một không gian Borel nếu X là tập Borel con của một không gian metric đầy, khả ly. σ− đại số Borel sinh bởi các tập con mở của X ký hiệu là B(X). Hàm đo được: Xét hai không gian đo (X, B(X)) và (E, B(E)). Một hàm số f : X → E gọi là đo được hay là "Borel đo được" nếu f −1 (A) ∈ B(X) với mọi A ∈ B(E) Hạt nhân ngẫu nhiên: Cho X và Y là hai không gian Borel. Một hạt nhân ngẫu nhiên trên X được cho bởi Y là một hàm số P (.|.) thỏa mãn 2 điều kiện sau: (i) P (.|y) là một độ đo xác suất trên X với mọi y ∈ Y cố định. (ii) P (B|.) là hàm số đo được trên Y với mọi B ∈ B(X) cố định. Lớp tất cả các hạt nhân ngẫu nhiên trên X được cho bởi Y được ký hiệu là P(X|Y ). Định nghĩa 1.3.1. Một mô hình điều khiển là bộ gồm 5 tham số (X, A, {A(x)|x ∈ X}, Q, c). (1.16) bao gồm (a) Một không gian X , X được gọi là không gian trạng thái và mỗi phần tử thuộc X gọi là một trạng thái. (b)A là một không gian Borel được gọi là tập điều khiển hoặc tập hành động. (c)Họ {A(x)|x ∈ X} khác rỗng các tập đo được A(x) của A, trong đó 11 A(x) kí hiệu là tập hợp điều khiển được hoặc những hành động khi hệ thống ở trạng thái x ∈ X và với tính chất đó thì tập K := {(x, a)|x ∈ X, a ∈ A(x)} (1.17) là tập các cặp trạng thái và hành động đo được, là tập con đo được của không gian X × A. (d) Một hạt nhân ngẫu nhiên Q từ X vào K, được gọi là luật chuyển tiếp; (e)Một hàm đo được c : K → R được gọi là hàm giá ( hoặc hàm chi phí mỗi giai đoạn). Trong một số trường hợp để thuận tiện thì ta có thể xem một hàm lãi mỗi giai đoạn là r : K → R thay vì hàm giá c. Hơn nữa, chúng ta đảm bảo rằng tập hợp các chiến lược điều khiển là không rỗng. Vì vậy, ngoài tập K ⊂ X × A đo được, chúng ta có giả thiết sau đây. Giả thiết 1.3.2. K chứa đồ thị của những hàm số đo được từ X vào A, đó là có một hàm số đo được f : X → A sao cho f (x) ∈ A(x) với ∀x ∈ X . Chiến lược: Xem xét mô hình điều khiển trong định nghĩa 1.3.1 và với mỗi t = 0, 1, ... định nghĩa không gian Ht của quá khứ chấp nhận được cho đến thời điểm t khi H0 := X , và Ht := Kt × X = K × Ht−1 , t = 1, 2, ... (1.18) trong đó K là tập trong (1.17). Mỗi phần tử ht của Ht được goi là một t quá khứ chấp nhận được hoặc đơn giản ta gọi là t - quá khứ, là một vectơ có dạng: ht = (x0 , a0 , ..., xt−1 , at−1 , xt ), (1.19) với (xi , ai ) ∈ K với i = 0, 1, ..., t − 1 và xt ∈ X . Để đảm bảo rằng các điều kiện phần sau được dùng đến, ta xét không gian compact: H t := (X × A)t × X = (X × A) × H t−1 , t = 1, 2, ... (1.20) và H 0 := H0 = X. Định nghĩa 1.3.3. Một chiến lược điều khiển ngẫu nhiên - hay nói ngắn gọn là một chiến lược điều khiển hoặc một chiến lược là một dãy π = {πt , t = 0, 1, 2, ...} với hạt nhân ngẫu nhiên πt trên tập điều khiển A được cho bởi Ht thỏa mãn điều kiện sau: πt (A(xt )|ht ) = 1, ∀ht ∈ Ht , t = 0, 1, ... 12 (1.21) Ký hiệu tập hợp tất cả những chiến lược bằng Π. Trong phần tiếp theo, chúng ta sẽ giới thiệu một số lớp con quan trọng của tập các chiến lược Một chiến lược π = {πt } có thể được xác định rõ ràng khi biết một dãy con {at } của tập các hành động A, sao cho, với mọi t - quá khứ ht trong (1.19) và t = 0, 1, ..., phân phối của at là πt (.|ht ), bởi (1.21), được tập trung trên A(xt ), tập hợp các hành động thực hiện được ở trạng thái xt . Giải thích này của π được thực hiện trong phương trình (1.22b). Xây dựng chính tắc. Cho (Ω, F) là không gian đo được bao gồm không gian mẫu Ω := H ∞ = (X × A)∞ và F là σ - đại số. Những phần tử của Ω là các dãy con có dạng ω = (x0 , a0 , x1 , a1 , ...) với xt ∈ X và at ∈ A với mọi t = 0, 1, .... Ta thấy H∞ = K∞ ⊂ Ω. Cho π = {πt } là một chiến lược điều khiển tùy ý và ν là độ đo xác suất tùy ý trên X được gọi là "phân phối ban đầu". Kí hiệu Pνπ là độ đo xác suất trên Ω cảm sinh bởi chiến lược π = (π1 , π2 , ...) với điều kiện ν . Vì thế, từ định lý Ionescu - Tulcea tồn tại duy nhất một độ đo xác suất Pνπ trên không gian (Ω, F), thỏa mãn Pνπ (H∞ ) = 1 và hơn thế nữa với mọi B ∈ B(X), C ∈ B(A) và ht ∈ Ht , t = 0, 1, 2, ... : Pνπ (x0 ∈ B) = ν(B) Pνπ (at ∈ C|ht ) = πt (C|ht ) Pνπ (xt+1 ∈ B|ht , at ) = Q(B|xt , at ) (1.22a) (1.22b) (1.22c) Định nghĩa 1.3.4. Quá trình ngẫu nhiên (Ω, F, Fνπ , {xt }) được gọi là một quá trình điều khiển Markov thời gian rời rạc (hoặc quá trình quyết định Markov ). Quá trình {xt } trong định nghĩa 1.3.4 phụ thuộc vào chiến lược cụ thể π và phân phối ban đầu ν . Vì thế, nói theo cách khác, chúng ta nên viết xπ,ν thay cho xt . Tuy nhiên,chúng ta sẽ giữ ký hiệu đơn giản xt và ngầm t hiểu rằng nó phụ thuộc vào π và ν . Mặt khác, chúng ta đôi khi coi họ {(Ω, F, Fνπ , {xt })|π ∈ Π} có thể thay thế cho ν như Quá trình điều khiển Markov (MCP). Họ này cùng với việc thực hiện các tiêu chuẩn tối ưu được gọi là một Bài toán điều khiển Markov. Kỳ vọng của Pνπ được ký hiệu là Eνπ . Đặc biệt, nếu ν chỉ tập trung tại "trạng thái ban đầu" x ∈ X thì ta viết Pxπ thay cho Pνπ và Exπ thay cho Fνπ . Phương trình (1.22c) như là một điều kiện Markov, nhưng tất nhiên, nói chung quá trình trạng thái {xt } là không có tính Markov theo nghĩa thông thường. Tuy nhiên, nếu π được hạn chế trên một dãy con thích hợp 13 của chiến lược (gọi là chiến lược Markov) thì {xt } trở thành một quá trình Markov. 1.4 Các chiến lược Markov Định nghĩa 1.4.1. Φ là ký hiệu tập hợp tất cả các hạt nhân ngẫu nhiên ϕ trong P(A|X) sao cho ϕ(A(x)|x) = 1 với mọi x ∈ X , và F là tập hợp tất cả các hàm số đo được f : X → A thỏa mãn f (x) ∈ A(x) với mọi x ∈ X , những hàm số trong F được gọi là một bộ chọn từ x 7→ A(x). Chú ý. Từ giả thiết 1.3.2 đảm bảo rằng F 6= ∅ và Φ 6= ∅ Một hàm số f ∈ F có thể được xác định với một hạt nhân ngẫu nhiên ϕ ∈ Φ, vì thế ϕ(·|x) là đo được Dirac tại f (x) với ∀x ∈ X , ∀x ∈ X, C ∈ B(A) ϕ(C|x) = IC [f (x)], ở đó IC là hàm chỉ tiêu của C . Vì thế, chúng ta có thể thấy rằng F là một tập con của Φ, F ⊂ Φ. (1.23) Định nghĩa 1.4.2. Một chiến lược π = {πt } ∈ Π được gọi là một: (a) Một chiến lược Markov ngẫu nhiên nếu tồn tại một dãy {ϕt } các hạt nhân ngẫu nhiên ϕt ∈ Φ sao cho: πt (·|ht ) = ϕt (·|xt ), ∀ht ∈ Ht , t = 0, 1, ...; (1.24) (b)Một chiến lược ngẫu nhiên dừng nếu tồn tại một hàm ϕ ∈ Φ sao cho πt (·|ht ) = ϕ(·|xt ), ∀ht ∈ Ht , t = 0, 1, ...; Tập tất cả các chiến lược Markov ngẫu nhiên ký hiệu là ΠRM , tập hợp tất cả các chiến lược ngẫu nhiên dừng ký hiệu là ΠRS . Ghi chú rằng ΠRS ⊂ ΠRM ⊂ Π Hơn nữa, π = {πt } ∈ Π được gọi là một (c)Chiến lược tất định là nếu tồn tại một dãy {gt } mà {gt } là dãy các hàm số đo được gt : Ht → A sao cho với mọi ht ∈ Ht và với mọi t = 0, 1, ... thì gt (ht ) ∈ A(xt ) và πt (·|ht ) trùng gt (ht ), tức là πt (C|ht ) = IC [gt (ht )], ∀C ∈ B(A) (d)Một chiến lược Markov tất định nếu tồn tại một dãy {ft } ∈ F sao cho πt (·|ht ) trùng ft (xt ) ∈ A(xt ) với mọi ht ∈ Ht và với mọi t = 0, 1, ..., (e)Một chiến lược tất định dừng nếu tồn tại một hàm số f ∈ F sao cho πt (·|ht ) trùng f (xt ) ∈ A(xt ) với mọi ht ∈ Ht và với mọi t = 0, 1, ..., 14 Đặt ΠD , ΠDM , ΠDS lần lượt là tập hợp tất cả các chiến lược xác định, Markov xác định và xác định dừng, khi đó ta có: ΠDS ⊂ ΠDM ⊂ ΠD ⊂ Π Chú ý 1.4.3. (a) Nếu π ∈ ΠRM là một chiến lược Markov ngẫu nhiên và {ϕt } là một hạt nhân ngẫu nhiên thỏa mãn định nghĩa πt (·|ht ) = ϕt (.|xt ) thì chúng ta sẽ viết π = {ϕt } thay vì π = {πt }, ngoài ra nếu π ∈ ΠRS và ϕ ∈ Φ thỏa mãn πt (·|ht ) = ϕ(·|xt ) thì chúng ta sẽ viết π thành ϕ∞ . Tương tự, những chiến lược được định nghĩa 1.4.2 (c), (d), (e), chúng ta sẽ viết π như {gt }; {ft } và f ∞ nếu π thuộc ΠD , ΠDM , ΠDS . (Một số tác giả ký hiệu ΠRS với Φ và ΠDS với F, vì thế họ viết ϕ∞ thay cho ϕ và f ∞ thay cho f ). (b) Giả sử F và Φ là những tập đã được định nghĩa 1.4.1 và c là một hàm giá và Q là một luật chuyển tiếp. Chúng ta xác định, với mọi x ∈ X , Z c(x, ϕ) := c(x, a)ϕ(da|x) (1.25) A và Z Q(·|x, ϕ) := Q(·|x, a)ϕ(da|x) (1.26) A Trên thực tế, cho một hàm số f ∈ F(⊂ Φ) thì công thức (1.22) và (1.26) trở thành: c(x, f ) = c(x, f (x)) và Q(B|x, f ) = Q(B|x, f (x)) Chú ý rằng mỗi hàm số đều đo được với x ∈ X . Đó là nguyên nhân chỉ ra rằng tại sao những hạt nhân ngẫu nhiên đều cần thiết phải đo được, một điều kiện tầm thường thỏa mãn với những không gian đo X và A. Chúng ta sẽ nhắc lại định nghĩa về quá trình Markov với thời gian rời rạc và chỉ ra các kết quả khi sử dụng một chiến lược Markov điều khiển quá trình Markov. 1.5 Tính chất Markov Giả sử {Rt } là một dãy hạt nhân ngẫu nhiên cho trước thuộc P(X|X), và giả sử {yt } là một X - giá trị ngẫu nhiên của quá trình. Thì {yt } được gọi là một quá trình Markov không thuần nhất với hạt nhân chuyển {Rt } nếu với mọi B ∈ B(X) và t = 0, 1, 2, ... thì P (yt+1 ∈ B|y0 , ..., yt ) = P (yt+1 ∈ B|yt ) = Rt (B|yt ) 15 (1.27) Phương trình (1.27) được gọi là tính Markov (có thể nói, (1.27) cố định P - hầu chắc chắn với P là độ đo xác suất trên không gian mà {yt } được định nghĩa. Tuy nhiên, trừ khi xác định trên một không gian khác, chúng ta luôn hiểu là "P - hầu chắc chắn" khi quyết định các điều kiện về xác suất). Nếu Rt là bất biến đối với hạt nhân ngẫu nhiên cho trước R ∈ P(X|X) thì dãy {yt } được gọi là một quá trình Markov thuần nhất với hạt nhân chuyển R. Mệnh đề Giả sử ν là một phân phối ban đầu tùy ý. Nếu π = {ϕt } là một chiến lược Markov ngẫu nhiên (tức là π ∈ ΠRM ) thì {xt } là một quá trình Markov không thuần nhất với hạt nhân chuyển {Q(·|·, ϕt )}, có nghĩa là điều kiện (1.27) trở thành, với B ∈ B(X) và t = 0, 1, ... thì Pνπ (xt+1 ∈ B|x0 , ..., xt ) = Pνπ (xt+1 ∈ B|xt ) = Q(B|xt , ϕt ) (1.28) Trên thực tế, nếu π = {ft } ∈ ΠDM là một chiến lược Markov xác định, (1.28) thỏa mãn cho hạt nhân chuyển Q(·|·, ft ). Hơn thế, với chiến lược dừng ϕ∞ ∈ ΠRS và f ∞ ∈ ΠDS , thì {xt } là quá trình Markov thuần nhất theo thời gian với hạt nhân chuyển {Q(·|·, ϕ)} và {Q(·|·, f )}. Chứng minh. Giả sử với chiến lược ban đầu tùy ý π = {ϕt }, ta chứng minh: Z Pνπ (xt+1 ∈ B|ht ) = Q(B|xt , at )πt (dat |ht ) (1.29) A với mọi B ∈ B(X) và t = 0, 1, .... Với các tính chất của kỳ vọng điều kiện ta có: Pνπ (xt+1 ∈ B|ht ) = Eνπ [Pνπ (xt+1 ∈ B|ht , at )|ht ] = Eνπ [Q(B|xt , at )|ht ] [(1.22c)] Z = Q(B|xt , at )πt (dat |ht ) [(1.22b)] A Vậy ta chứng minh được (1.29). Đặc biệt, nếu π = {ϕt } là một chiến lược Markov ngẫu nhiên, π ∈ ΠRM thì (1.29) trở thành: Z π Pν (xt+1 ∈ B|ht ) = Q(B|xt , at )ϕt (dat |xt ) = Q(B|xt , ϕt ) (1.30) A 16 bởi vì công thức (1.26) cách xác định Q(·|x, ϕ). Như vậy, đặt xt0 := (x0 , x1 , ..., xt ), khi đó vế trái của (1.28) có thể viết thành: Pνπ (xt+1 ∈ B|xt0 ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt0 ] = Eνπ [Q(B|xt , ϕt )|xt0 ] = Q(B|xt , ϕt ) Tương tự, trong trường hợp này (1.28) thỏa mãn: Pνπ (xt+1 ∈ B|xt ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt ] = Eνπ [Q(B|xt , ϕt )|xt ] = Q(B|xt , ϕt ) Vậy ta có điều phải chứng minh.  17 Chương 2 BÀI TOÁN VỚI THỜI GIAN HỮU HẠN 2.1 Giới thiệu Trong chương này, chúng ta xem xét các mô hình điều khiển Markov (X, A, {A(x)|x ∈ X} , Q, c) (2.1) giới thiệu trong định nghĩa 1.3.1, và vấn đề điều khiển chúng ta quan tâm ở đây là cực tiểu hóa tiêu chuẩn thực hiện với thời gian hữu hạn "N −1 # X J(π, x) := Exπ c(xt , at ) + cN (xN ) (2.2) t=0 với cN là hàm chi phí cuối cùng, một hàm đo được đưa ra trên X. Do đó, hàm giá trị biểu thị bởi J ∗ , tức là, J ∗ (x) := inf Q J(π, x), x∈X (2.3) Q vấn đề là phải tìm một chiến lược π ∗ ∈ mà ∗ ∗ J(π , x) = J (x), ∀x ∈ X 2.2 Quy hoạch động Định lý 2.2.1. Cho Jo , J1 , ..., JN là các hàm được định nghĩa trên X ( hoặc là theo chiều ngược lại, từ t = N tới t = 0) bởi JN (x) := cN (x), và cho t = N − 1, N − 2, ..., 0,   Z Jt (x) := min c(x, a) + Jt+1 (y)Q(dy|x, a) A(x) X 18 (2.4) (2.5) Giả sử rằng những hàm đó là đo được và với mỗi t = 0, ..., N − 1, đó là một hàm chọn ft ∈ F sao cho ft (x) ∈ A(x) đạt được cực tiểu trong (2.5) với mọi x ∈ X ; đó là, ∀x ∈ X và t = 0, ..., N − 1, Z Jt (x) := c(x, ft ) + Jt+1 (y)Q(dy|x, ft ) (2.6) Khi đó chiến lược π ∗ = {0, ..., fN −1 } là tối ưu, và hàm giá J ∗ bằng Jo , tức là, J ∗ (x) = Jo (x) = J(π ∗ , x), ∀x ∈ X. (2.7) Chứng minh. Đặt π = {πt } là một chiến lược bất kì và đặt Ct (π, x) là tổng chi phí dự kiến tương ứng từ thời điểm t đến thời điểm cuối N, căn cứ vào trạng thái xt = x tại thời điểm t, tức là nếu t = 0, 1, ...N − 1 "N −1 # X Ct (π, x) := E π c(xn , an ) + cN (xN )|xt = x (2.8) n=t π CN (π, x) := E [cN (xN )|xN = x] = cN (x) (2.9) Ct (π, x) được gọi là "chi phí đi" hoặc chi phí từ thời điểm t trở đi khi sử dụng chiến lược π và xt = x. Đặc biệt, lưu ý rằng từ (2.2) J(π, x) = C0 (π, x) (2.10) Để chứng minh định lý, chúng ta thấy rằng, với mọi x ∈ X và t = 0, ..., N, Ct (π, x) ≥ Jt (x) (2.11) với π = π ∗ , tức là, Ct (π ∗ , x) = Jt (x) (2.12) Đặc biệt, đối với t = 0 J(π, x) ≥ J0 (x), với J(π ∗ , x) = J0 (x) ∀x trong đó lợi nhuận mong muốn (2.7), với J(π, ·) ≥ J0 (x) cho tùy ý π sao cho J ∗ (·) ≥ J0 (·). Sự chứng minh của (2.11) - (2.12) là phép quy nạp ngược. Chú ý rằng (2.11) - (2.12) một cách tầm thường giữ cho t = N , từ (2.9) và (2.4), CN (π, x) = JN (x) = cN (x) Bây giờ chúng ta giả sử đối với một số t = N − 1, ..., 0, Ct+1 (π, x) ≥ Jt+1 (x), x ∈ X. 19 (2.13)