RA QUYẾT ĐỊNH MARKOV

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa, ĐHQG TPHCM

1.  MÔ HÌNH QUYẾT ĐỊNH MARKOV

Mô hình quyết định Markov hỗ trợ ra quyết định trong hệ thống biểu thị bởi quá trình Markov. Hệ thống ở đây là hệ thống ngẫu nhiên với không gian trạng thái hữu hạn.

Các khái niệm cơ bản trong mô hình quyết định Markov bao gồm:

          - Ma trận chuyển dịch

          - Ma trận lợi nhuận

          - Bước hay giai đoạn

          - Phương án quyết định

          - Chính sách tối ưu.

Ma trận chuyển dịch

Ma trận chuyển trạng thái của chuỗi Markov mô tả hệ thống:

Ma trận lợi nhuận

Gọi lợi nhuận khi hệ thống chuyển từ trạng thái i sang trạng thái j là r_ij. Ma trận lợi nhuận:

Hệ thống có thể được khảo sát với số bước hay giai đoạn là hữu hạn hay vô hạn. Ở mỗi giai đoạn có một phương án quyết định trong tập k phương án. Các ma trận chuyển dịch P, lợi nhuận R phụ thuộc vào phương án chọn lựa.

Chính sách là tập các phương án theo trạng thái hệ thống. Chiến lược tối ưu là tập các chính sách theo các giai đoạn của hệ thống nhằm tối ưu một hàm mục tiêu xác định như cực đại lợi nhuận.

Mô hình quyết định Markov ứng dụng trong nhiều bài toán thực tế như bài toán tồn kho, bài toán thay thế… Các mô hình thường dùng trong bài toán quyết định Markov là quy hoạch động hay quy hoạch tuyến tính. Trong mô hình quy hoạch động với số bước vô hạn, các phương pháp thường dùng là phương pháp liệt kê và phương pháp lặp.

2.  BÀI TOÁN NGƯỜI LÀM VƯỜN

Bài  toán người làm vườn được sử dụng nhằm minh họa cho bài toán quyết định Markov và các phương pháp giải. Trong bài  toán người làm vườn, hệ thống gồm ba trạng thái theo tình trạng đất ở đầu mùa vụ hàng năm và sản lượng thu hoạch trong năm như ở bảng sau.

Có hai phương án chọn lựa bón phân và không bón phân:

Có thể giả sử tình trạng đất hay sản lượng năm nay chỉ phụ thuộc vào trạng thái đất năm trước. Ma trận chuyển dịch theo hai phương án tuần tự như sau:

Ma trận lợi nhuận (triệu đồng) theo hai phương án tuần tự như sau:

Theo tình trạng đất có nhiều chính sách, một chính sách có thể chọn lựa là chỉ bón phân khi đất xấu:

                   i = 1, 2  ®  k = 1

                   i = 3  ®  k = 2

Với chính sách này, ma trận chuyển dịch và ma trận lợi nhuận như sau:

Vấn đề ở đây là chọn chiến lược tối ưu nhằm cực đại lợi nhuận tích lũy.

3.  MÔ HÌNH QUY HOẠCH ĐỘNG HỮU HẠN

Mô hình này giải bài toán ra quyết định Markov với số bước hữu hạn bằng phương pháp quy hoạch động. Tham số mô hình gồm số giai đoạn N, số phương án K, số trạng thái m, ma trận chuyển dịch và ma trận lợi nhuận theo các phương án k = 1 ¸ K.

Nhằm xác định phương trình hồi quy ngược của mô hình, gọi:

  - kỳ vọng thu nhập khi chuyển từ trạng thái i ở phương án k

 - kỳ vọng thu nhập tích lũy ngược ở giai đoạn n, trạng thái i, phương án k

f_n(i) - kỳ vọng thu nhập tích lũy ngược tối ưu ở giai đoạn n, trạng thái i.

thì có:

Phương trình hồi quy:

Ví dụ: Xét bài toán người làm vườn trong thời gian 3 năm: N = 3, m = 3, k = 2. Ma trận chuyển dịch và ma trận lợi nhuận theo từng phương án:

Xét ở năm thứ 3:

Năm thứ 2:

Năm thứ 1:

Từ các bảng trên, chiến lược tối ưu là ở năm đầu và năm thứ 2, phương án tốt nhất là bón phân bất chấp tình trạng đất, sang năm thứ 3 nếu đất tốt thì không bón còn nếu đất xấu hay vừa thì bón phân.

Với chính sách này, kỳ vọng lợi nhuận là cực đại với giá trị là 10,74 triệu đồng nếu tình trạng đất đầu năm 1 là tốt; là 7,92 triệu đồng nếu tình trạng đất đầu năm 1 là trung bình; là 4,23 triệu đồng nếu tình trạng đất đầu năm 1 là xấu.

Tổng quát, xác suất và lợi nhuận  phụ thuộc giai đoạn n, khi ấy  phương trình hồi quy tổng quát như sau:

Nếu tính đến giá trị thời gian của tiền tệ, gọi a = (P/F, r, 1) = 1/(1 + r), với r là lãi suất thực trong thời đoạn là 1 bước phương trình hồi quy:

4.  MÔ HÌNH QUY HOẠCH ĐỘNG VÔ HẠN

Mô hình giải bài toán ra quyết định Markov với số bước vô hạn bằng phương pháp quy hoạch động. Với số giai đoạn vô hạn, thường xét hệ thống ở trạng thái xác lập. Chuỗi Markov ở xác lập có đặc tính độc lập với trạng thái ban đầu.

Chiến lược tối ưu với số bước vô hạn hay chính sách xác lập tối ưu là chính sách cực đại kỳ vọng thu nhập chuyển giai đoạn. Các phương pháp xác định chính sách xác lập tối ưu bao gồm:

          - Phương pháp liệt kê

          - Phương pháp lặp.

a.  Phương pháp liệt kê

Phương pháp liệt kê và so sánh các chính sách. Số chính sách L ở hệ thống m trạng thái, K phương án là L = K^m. Với mỗi chính sách l trong tập chính sách sẽ có một ma trân chuyển dịch P^l và ma trận lợi nhuận R^l tương ứng.

Phương pháp liệt kê gồm các bước sau:

          - Xác định tập chính sách và các ma trận tương ứng: l, P^l, R^l.

          - Tính kỳ vọng thu nhập khi chuyển từ trạng thái i ở chính sách l.

                            ,  l = 1 ¸ L

          - Tính ma trận tới hạn cho các chính sách l = 1 ¸ L

                            ,  l = 1 ¸ L

                            P^l = P^lP^l

          - Xác định kỳ vọng thu nhập E^l ở chính sách l = 1 ¸ L

                            E^l = å_i=1¸mp_i^lv_i^l

          - Xác định chính sách tối ưu l*   

                            E = E^l* = max_l [E^l]                                                     

Ví dụ: Áp dụng phương pháp liệt kê cho bài toán người làm vườn với số bước vô hạn. Với 3 trạng thái và 2 phương án hệ thống có 8 chính sách như ở bảng sau:

Ma trận chuyển dịch và ma trận lợi nhuận tương ứng với chính sách l = 1 - 8 như sau:

Kỳ vọng thu nhập khi chuyển từ trạng thái i ở chính sách l tính ở bảng sau:

Kết quả tính toán xác suất giới hạn như ở bảng sau:

Kỳ vọng thu nhập E^l ở chính sách l = 1 ¸ L có kết quả tính toán như ở bảng sau:

Từ bảng kỳ vọng thu nhập, ta thấy chính sách tối ưu là chính sách số 2, đó là bón phân cho mọi trạng thái đất. Với chính sách này, kỳ vọng thu nhập hàng năm là cực đại với giá trị 2,256 triệu. Để ý rằng kết quả này khác với kết quả của bài toán số bước hữu hạn ở trên.

b.  Phương pháp lặp

Phương pháp liệt kê tuy đơn giản nhưng có lượng tính toán lớn nhất là khi quá trình có số trạng thái hay số phương án lớn. Để giảm thiểu lượng tính toán, có thể dùng phương pháp lặp. Mục tiêu mô hình là cực đại kỳ vọng thu nhập chuyển giai đoạn theo các chính sách:

Kỳ vọng thu nhập chuyển giai đoạn theo các chính sách l:

trong đó f(i) là các hằng số trạng thái theo chính sách.

Đây là hệ m phương trình với  m+1 ẩn số có thể giải bằng quá trình lặp theo hai bước định trị và cải thiện chính sách.

Bước định trị ta chọn một chính sách bất kỳ l mà ta gọi là l_p, xác định các ma trận tương ứng P^l, R^l và giải hệ phương trình:

trong đó tùy chọn .

Bước cải thiện chính sách, xác định chính sách mới l_n. Với mỗi trạng thái i, định phương án tối ưu k*:

Nếu chính sách mới l_n trùng chính sách cũ l_p, chính sách mới là tối ưu. Nếu chính sách mới l_n khác chính sách cũ l_p, thay chính sách cũ l_p bởi chính sách mới và quay lại bước định trị.

Ví dụ: Sử dụng phương pháp lặp với bài toán làm vườn. Xem chính sách ban đầu là không bón phân với mọi tình trạng đất:

                   k = 1, i = 1, 2, 3

Ma trận chuyển dịch và ma trận lợi nhuận tương ứng chính sách ban đầu:

Hệ phương trình:

                   E = 5,3  + 0,2 f(1) + 0,5 f(2) + 0,3 f(3) – f(1)

                   E = 3 +  0 f(1)  + 0,5 f(2)  + 0,5 f(3) – f(2)

                   E = -1 + f(1) + f(2) + 1 f(3) – f(3)

Với f(3) = 0 giải hệ phương trình trên ta được:

                   E = -1;  f(1) = 12,88;  f(2) = 8;  f(3) = 0

Chính sách mới tương ứng với phương án tối ưu cho từng trạng thái định bởi bảng sau:

Từ bảng trên ta thấy chính sách mới là chọn phương án 2 cho mọi trạng thái hay bón phân cho mọi tình trạng đất, chính sách mới này khác chính sách cũ nên được chọn là chính sách hiện tại.

Với chính sách mới hiện tại, ma trân chuyển dịch và lợi nhuận như sau:

                   E = 4,7 + 0,3 f(1)  + 0,6 f(2) + 0,1 f(3) – f(1)

                   E = 3,1 + 0,1 f(1)  + 0,6 f(2) + 0,3 f(3) – f(2)

                   E = 4  + 0,05 f(1)  + 0,4 f(2) + 0,55 f(3) – f(3)

                   f(3) = 0 ® E = 2,26;  f(1) = 6,7;  f(2) = 3,8;  f(3) = 0

Chính sách mới lại là chính sách chọn phương án 2 cho mọi trạng thái, đây là chính sách tối ưu và giá trị tối ưu của hàm mục tiêu là E = 2,26.

5.  MÔ HÌNH QUY HOẠCH TUYẾN TÍNH VÔ HẠN

Phần này áp dụng mô hình quy hoạch tuyến tính cho bài toán quyết định Markov với số giai đoạn vô hạn. Với số giai đoạn vô hạn, bài toán có hàm mục tiêu là cực đại kỳ vọng thu nhập chuyển giai đoạn theo các chính sách.

Gọi  là xác suất chọn phương án k khi hệ thống ở trạng thái i. Bài toán có thể mô hình như sau: 

Với các ràng buộc: 

Chú ý rằng p_ij  là hàm của chính sách hay tập phương án chọn lựa.

Để đưa về mô hình tuyến tính, gọi w_ik là xác suất khi hệ thống ở trạng thái i và chọn phương án k thì có theo định luật Bayes: 

Từ lý thuyết xác suất:

Có thể suy ra  từ w_ik:

Từ đó, mô hình trên có thể viết lại thành mô hình tuyến tính sau với mK biến và (m + 1) ràng buộc:

Với các ràng buộc: 

Ví dụ: Áp dụng mô hình quy hoạch tuyến tính cho bài toán làm vườn. Kỳ vọng thu nhập khi ở trạng thái i, phương án k tính được ở bảng sau:

Mô hình:

     Max E = 5,3 w₁₁ + 4,7w₁₂ + 3w₂₁ +3,1w₂₂ – w₃₁  + 0,4w₃₂

     St:

          w₁₁ + w₁₂ – (0,2w₁₁ + 0,3w₁₂  + 0,1w₂₂ + 0,5w₃₂) = 0

          w₂₁ + w₂₂ – (0,5w₁₁ + 6w₁₂ + 0,5w₂₁ + 0,6w₂₂  + 0,4w₃₂ ) = 0

          w₃₁ + w₃₂ – (0,3w₁₁ + 0,1w₁₂ + 0,5w₂₁ + 0,3w₂₂ + w₃₁ + 0,55w_32­) = 0

          w₁₁ + w₁₂ + w₂₁ + w₂₂ + w₃₁ + w₃₂  = 1

          w₁₁w_­ik ³ 0,  " i, k

Giải mô hình ta được:   w₁₁ = w₂₁ = w₃₁ = 0

                                      w₁₂ = 6/59

                                      w₂₂  = 31/59

                                      w₃₂  = 22/59

Từ đó:                           q₁₁ = w₁₁ / (w₁₁ + w₁₂) = 0

Tương tự:                      q₁₂ = q₁₃ = 0

                                      q₁²  =  q₂² =  q₃² = 1

Chính sách tối ưu là chọn phương án 2 cho mọi trạng thái 0, kỳ vọng thu nhập chuyển trạng thái tối ưu là:

TLTK

Nguyễn Như Phong. Vận trù ngẫu nhiên. NXBĐHQG. 2003, 2010, 2015