Quy hoạch ngẫu nhiên

Lập trình ngẫu nhiên (tiếng Anh: stochastic programming) — một nhánh của lập trình toán học, phát triển các mô hình và phương pháp giải các bài toán tối ưu hóa trong điều kiện bất định, khi một số tham số của mô hình không được biết chính xác mà được biểu diễn dưới dạng các biến ngẫu nhiên với phân phối xác suất đã biết hoặc được ước lượng.

Khác với các bài toán tất định, nơi tất cả dữ liệu được coi là các hằng số đã cho, lập trình ngẫu nhiên đặt mục tiêu tìm một nghiệm (hoặc chính sách ra quyết định) tối ưu theo một nghĩa thống kê nào đó. Thông thường điều này có nghĩa là cực tiểu hóa hoặc cực đại hóa kỳ vọng toán học của hàm mục tiêu. Ý tưởng cốt lõi là tìm một chính sách ra quyết định tốt nhất «trung bình» trên tất cả các thực hiện có thể của các tham số ngẫu nhiên, điều này đặc biệt quan trọng đối với các bài toán mà quyết định được đưa ra nhiều lần trong các điều kiện tương tự (ví dụ, trong quản lý hàng tồn kho hoặc hệ thống năng lượng).

Phát biểu toán học của bài toán

Dưới dạng tổng quát, bài toán lập trình ngẫu nhiên có thể được phát biểu như sau: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ trong đó:

• $x$ — vectơ các biến điều khiển (quyết định) cần xác định.
• $X$ — tập các nghiệm chấp nhận được đối với $x$, được xác định bởi các ràng buộc tất định.
• $\xi$ — vectơ ngẫu nhiên biểu diễn các tham số bất định của bài toán (ví dụ, nhu cầu, giá cả, điều kiện thời tiết).
• $f(x,\xi )$ — hàm mục tiêu, giá trị của nó phụ thuộc cả vào quyết định đã chọn $x$ lẫn vào thực hiện của vectơ ngẫu nhiên $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — toán tử kỳ vọng toán học, được tính theo phân phối xác suất của vectơ $\xi$.

Nguyên lý quan trọng nhất làm nền tảng cho các mô hình ngẫu nhiên đa giai đoạn là nguyên lý không tiên liệu trước (tiếng Anh: non-anticipativity principle). Nguyên lý này phát biểu rằng các quyết định được đưa ra ở bất kỳ giai đoạn nào chỉ có thể phụ thuộc vào thông tin sẵn có tại thời điểm đó và không thể «nhìn vào tương lai».

Bài toán hai giai đoạn với quyền bù đắp

Mô hình phổ biến nhất là bài toán hai giai đoạn với quyền bù đắp (tiếng Anh: two-stage stochastic program with recourse). Quá trình ra quyết định được chia thành hai giai đoạn:

1. Giai đoạn một: Quyết định «ở đây và ngay bây giờ (here-and-now) được đưa ra — xác định vectơ $x$. Quyết định này phải được đưa ra trước khi biết được thực hiện cụ thể của vectơ ngẫu nhiên $\xi$.
2. Giai đoạn hai: Sau khi sự kiện ngẫu nhiên xảy ra, quyết định điều chỉnh hoặc bù đắp (recourse decision) — vectơ $y(\xi )$ — được đưa ra nhằm cực tiểu hóa các hậu quả tiêu cực hoặc tận dụng các cơ hội thuận lợi phát sinh từ sự kết hợp giữa quyết định giai đoạn một $x$ và kết quả $\xi$.

Về mặt toán học, bài toán lập trình tuyến tính ngẫu nhiên hai giai đoạn được phát biểu như sau: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ với các ràng buộc giai đoạn một: $Ax=b,x\ge 0$. Ở đây $Q(x,\xi )$ — hàm bù đắp (recourse function), biểu diễn giá trị tối ưu của bài toán giai đoạn hai: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ trong đó $\xi$ — vectơ ngẫu nhiên bao gồm các tham số $q(\xi ),T(\xi )$ và $h(\xi )$; còn $c,A,b$ và $W$ — là các tham số tất định.

Các tính chất và định lý cơ bản

• Tính lồi: Một trong những kết quả nền tảng của lý thuyết là đối với bài toán lập trình tuyến tính ngẫu nhiên hai giai đoạn, hàm bù đắp kỳ vọng $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ là một hàm lồi. Tính chất này có ý nghĩa vô cùng quan trọng vì nó đảm bảo rằng bài toán giai đoạn một tổng thể là một bài toán lập trình lồi, cho phép áp dụng các phương pháp giải hiệu quả và tối ưu toàn cục trùng với tối ưu cục bộ.
• Tương đương tất định: Nếu vectơ ngẫu nhiên $\xi$ có số hữu hạn các thực hiện (kịch bản) có thể ${\xi }_1,\dots ,{\xi }_K$ với xác suất $p_1,\dots ,p_K$, thì bài toán lập trình ngẫu nhiên có thể được phát biểu lại dưới dạng một bài toán tối ưu tất định lớn duy nhất. Trong trường hợp này, kỳ vọng toán học được thay thế bằng tổng có trọng số trên tất cả các kịch bản. Tuy nhiên, kích thước của bài toán này tăng tuyến tính theo số kịch bản, dẫn đến «lời nguyền của chiều số liệu» và khiến phương pháp này không thể giải được về mặt tính toán khi số kịch bản lớn.

So sánh với tối ưu hóa bền vững

Lập trình ngẫu nhiên là một trong số các phương pháp tiếp cận tối ưu hóa trong điều kiện bất định. Điểm khác biệt chính của nó so với tối ưu hóa bền vững nằm ở cách mô hình hóa sự bất định và tiêu chí tối ưu.

So sánh các phương pháp tiếp cận tối ưu hóa trong điều kiện bất định

Tiêu chí	Tối ưu hóa ngẫu nhiên	Tối ưu hóa bền vững
Biểu diễn sự bất định	Các tham số là các biến ngẫu nhiên với phân phối xác suất đã biết	Các tham số thuộc một tập bất định cho trước, không yêu cầu phân phối
Tiêu chí tối ưu	Tối ưu hóa kỳ vọng toán học của hàm mục tiêu	Tối ưu hóa trong kịch bản xấu nhất (minimax)
Tính chất của nghiệm	Chính sách tối ưu «trung bình», có thể không chấp nhận được đối với các kịch bản hiếm	Nghiệm được đảm bảo chấp nhận được đối với mọi thực hiện; có thể mang tính bảo thủ

Ví dụ

• Bài toán người bán báo (tiếng Anh: newsvendor problem): Bài toán quản lý hàng tồn kho cổ điển, trong đó người bán phải quyết định mua bao nhiêu hàng mà không biết chính xác nhu cầu trong tương lai. Nghiệm cân bằng giữa rủi ro thua lỗ do dư thừa và rủi ro mất lợi nhuận do thiếu hụt.
• Bài toán người nông dân: Người nông dân quyết định phân bổ bao nhiêu mẫu đất cho các loại cây trồng khác nhau trên tổng diện tích, mà không biết thời tiết trong tương lai, vốn ảnh hưởng đến năng suất. Sau khi thời tiết được biết, người nông dân có thể thực hiện các hành động điều chỉnh (ví dụ, bán phần dư thừa hoặc mua thêm sản lượng còn thiếu trên thị trường).

Xem thêm

• Lập trình toán học
• Nghiên cứu vận trù học
• Tối ưu hóa bền vững
• Lập trình động
• Lý thuyết điều khiển

Chú thích

</references>