Two-stage stochastic optimization
Posted: 14/02/2026
Lập trình tuyến tính/số nguyên truyền thống được thiết kế cho các bài toán xác định (deterministic), giả định rằng tất cả các dữ liệu đều đã biết và cố định. Mặc dù điều này giúp việc mô hình hóa trở nên đơn giản hơn, nhưng nó hiếm khi phản ánh đúng điều kiện thực tế. Ví dụ, trong thị trường chứng khoán, việc dự đoán giá hoặc lợi nhuận trong tương lai thường chứa rất nhiều yếu tố khó đoán.
Một số phương pháp đã được đề xuất để xử lý các thách thức liên quan đến sự không chắc chắn (uncertainty) trong các tham số, bao gồm: sensitivity analysis, robust optimization, chance constraints, và two-stage stochastic programming with recourse. Trong bài viết này, chúng ta sẽ tập trung vào phương pháp two-stage stochastic optimization.
1. Tổng quan
Trong two-stage stochastic optimization, chúng ta chia các biến quyết định thành hai giai đoạn:
- Biến quyết định giai đoạn một (First-stage decision variables): Đây là các quyết định phải được đưa ra trước khi sự không chắc chắn xảy ra. Chúng thường được gọi là các quyết định “here-and-now”, và những quyết định này thường không thể thay đổi hoặc rất tốn kém để điều chỉnh sau khi đã thực hiện. Ví dụ như mức sản xuất ban đầu hoặc quyết định vị trí xây dựng cơ sở lớn.
- Biến quyết định giai đoạn hai (Second-stage decision variables): Đây là các quyết định được đưa ra sau khi sự không chắc chắn đã xảy ra. Chúng thường được gọi là ‘recourse decisions’ vì chúng ta đang phản ứng lại các tình huống xảy ra và các quyết định đã đưa ra ở giai đoạn một.
Việc lựa chọn biến nào thuộc giai đoạn một hay giai đoạn hai là do người ra quyết định quyết định, và phụ thuộc vào bản chất của bài toán.
Trong bài toán two-stage stochastic programming, sự không chắc chắn được mô tả bằng một tập các kịch bản (scenarios), mỗi kịch bản có xác suất xảy ra và giá trị tham số khác nhau. Ví dụ, nếu chúng ta có sự không chắc chắn về cả nhu cầu (demand) và khả năng hoạt động của máy móc (machine availability), thì chúng ta sẽ có một tập các kịch bản như sau.
| Scenario | Probability | Demand | Availability |
|---|---|---|---|
| 1 | 0.2 | 35 | 1 |
| 2 | 0.1 | 25 | 1 |
| 3 | 0.05 | 15 | 0 |
| 4 | 0.2 | 30 | 1 |
| 5 | 0.3 | 25 | 0 |
| 6 | 0.03 | 45 | 0 |
| 7 | 0.12 | 40 | 1 |
Lưu ý rằng tổng các xác suất của các kịch bản bằng 1.
Mục tiêu của two-stage stochastic optimization là tối thiểu hóa hoặc tối đa hóa tổng giá trị kỳ vọng (expected objective value) của hàm mục tiêu, đồng thời xem xét cả biến quyết định giai đoạn một và giai đoạn hai. Trong một số tài liệu, bài toán này thường được viết dưới dạng sau:
$$ \min_{x \in X} \; c^\top x + \mathbb{E}_{\xi}[ Q(x, \xi) ] $$trong đó hàm chi phí giai đoạn hai được định nghĩa bởi:
$$ Q(x, \xi) = \min_{y} \; q(\xi)^\top y $$ $$ \text{s.t.} \quad W(\xi)y = h(\xi) - T(\xi)x, \quad y \ge 0. $$Trong đó, \( x \in X \subseteq \mathbb{R}^n \) là các biến quyết định giai đoạn một (first-stage decision variables), được lựa chọn trước khi sự không chắc chắn xảy ra. Ký hiệu \( \xi \) biểu diễn biến ngẫu nhiên (random vector) mô tả sự không chắc chắn của các tham số trong bài toán.
Hàm \( Q(x, \xi) \) là giá trị tối ưu của bài toán giai đoạn hai (second-stage problem), còn được gọi là hàm recourse, và phụ thuộc vào cả quyết định giai đoạn một \( x \) và giá trị thực hiện của biến ngẫu nhiên \( \xi \).
Ký hiệu \( \mathbb{E}_{\xi}[Q(x,\xi)] \) là giá trị kỳ vọng (expected value) của chi phí giai đoạn hai theo phân phối xác suất của \( \xi \). Do đó, hàm mục tiêu bao gồm chi phí giai đoạn một \( c^\top x \) và chi phí kỳ vọng của giai đoạn hai.
Trong bài toán giai đoạn hai, \( y \) là các biến quyết định giai đoạn hai (second-stage decision variables), được lựa chọn sau khi \( \xi \) được quan sát. Các ma trận và vector \( W(\xi), h(\xi), T(\xi), q(\xi) \) phụ thuộc vào giá trị của biến ngẫu nhiên \( \xi \).
Nếu chúng ta có một số lượng kịch bản hữu hạn (ví dụ, Ω = 4), thì dạng mở rộng tương đương (equivalent extensive form) có thể được viết như sau:
$$ \begin{aligned} \min_{x, y_1, y_2, y_3, y_4} \quad & c^\top x + p_1 q(\xi_1)^\top y_1 + p_2 q(\xi_2)^\top y_2 + p_3 q(\xi_3)^\top y_3 + p_4 q(\xi_4)^\top y_4 \\ \text{s.t.} \quad & Ax = b, \\ & W(\xi_1) y_1 = h(\xi_1) - T(\xi_1) x, \\ & W(\xi_2) y_2 = h(\xi_2) - T(\xi_2) x, \\ & W(\xi_3) y_3 = h(\xi_3) - T(\xi_3) x, \\ & W(\xi_4) y_4 = h(\xi_4) - T(\xi_4) x, \\ & x, y_1,y_2,y_3,y_4 \ge 0. \end{aligned} $$Trong đó, \( x \) là các biến quyết định giai đoạn một (first-stage decision variables), được dùng chung cho tất cả các kịch bản. Với mỗi kịch bản \( \xi_i \), ta có một tập biến quyết định giai đoạn hai riêng biệt \( y_i \). Hàm mục tiêu là tổng chi phí giai đoạn một và chi phí kỳ vọng của các bài toán giai đoạn hai.
Lưu ý rằng:
- Các ràng buộc (constraints) được xác định cho từng kịch bản, do đó làm tăng kích thước bài toán và độ phức tạp tính toán.
- Hàm mục tiêu bao gồm giá trị kỳ vọng trên tất cả các kịch bản có thể xảy ra.
- Nghiệm của giai đoạn một phải khả thi (feasible) cho tất cả các khả năng xảy ra của các ràng buộc ở giai đoạn hai.
2. Một số ví dụ
Bài toán Network Design
Bài toán network design là ví dụ kinh điển sử dụng 2 stage stochastic optimization, trong đó nhiều loại hàng hóa cần được vận chuyển qua một mạng lưới phải được thiết kế trước khi nhu cầu của các hàng hóa này được biết. Mỗi tuyến đường nếu được mở sẽ phát sinh chi phí cố định. Sau khi mở, tuyến đó có một giới hạn công suất và mỗi đơn vị hàng vận chuyển qua sẽ phát sinh chi phí biến đổi.
Giai đoạn 1: Quyết định đầu tư
Trước khi biết nhu cầu thực tế, ta phải quyết định tuyến đường nào sẽ được mở. Gọi biến quyết định:
- xa = 1 nếu mở tuyến a,
- xa = 0 nếu không mở.
Chi phí cố định phải trả là:
$$ \sum_{a \in A} c_a x_a $$
Giai đoạn 2: Quyết định vận chuyển sau khi biết kịch bản
Khi một kịch bản i xảy ra và nhu cầu được biết, ta quyết định lượng hàng của mỗi loại c vận chuyển qua mỗi tuyến a. Gọi:
- yaci là lượng hàng hóa c đi qua tuyến a trong kịch bản i.
Chi phí vận chuyển trong kịch bản i là:
$$ \sum_{c \in C} \sum_{a \in A} q_{ac} y_{ac}^i $$
Hàm mục tiêu: Tối thiểu hóa chi phí kỳ vọng
Vì mỗi kịch bản xảy ra với xác suất như nhau (giả sử có N kịch bản), ta tối thiểu hóa tổng chi phí kỳ vọng:
$$ \min \quad \sum_{a \in A} c_a x_a + \frac{1}{N} \sum_{i=1}^{N} \sum_{c \in C} \sum_{a \in A} q_{ac} y_{ac}^i $$
Các ràng buộc
1. Bảo toàn dòng (flow conservation)
Tại mỗi nút, với mỗi loại hàng và mỗi kịch bản, tổng dòng vào và dòng ra phải cân bằng theo nhu cầu:
$$ \sum_{a: a(0)=v} y_{ac}^i - \sum_{a: a(1)=v} y_{ac}^i = d_{vc}^i $$
Điều này đảm bảo hàng hóa được vận chuyển đúng từ điểm xuất phát đến điểm đích.
2. Ràng buộc công suất
Tổng lượng hàng đi qua tuyến a trong mỗi kịch bản không được vượt quá công suất nếu tuyến đó được mở:
$$ \sum_{c \in C} y_{ac}^i \le u_a x_a $$
3. Điều kiện biến
$$ x_a \in \{0,1\}, \quad y_{ac}^i \ge 0 $$
Liên hệ với cấu trúc two-stage stochastic
Mô hình này có cấu trúc hai giai đoạn rất rõ ràng:
- Giai đoạn 1: quyết định xa trước khi biết nhu cầu.
- Giai đoạn 2: quyết định yaci sau khi nhu cầu được tiết lộ.
Hàm mục tiêu tính theo kỳ vọng qua các kịch bản, thể hiện việc tối ưu hóa quyết định hiện tại dựa trên rủi ro tương lai.
Bài toán Capacitated Warehouse Location
Một ví dụ khác cũng hay được sử dụng phương pháp 2 stage stochastic optimization là bài toán Capacitated Warehouse Location (CWL). Ý tưởng cơ bản là ta phải quyết định vị trí mở kho và sau đó phân bổ kho đó cho khách hàng, trong khi sự xuất hiện của khách hàng là ngẫu nhiên.
Giai đoạn 1: Quyết định mở kho
Trước khi biết khách hàng thực tế xuất hiện, ta phải quyết định kho nào sẽ được mở. Gọi biến quyết định:
- xf = 1 nếu mở kho tại vị trí f,
- xf = 0 nếu không mở.
Chi phí cố định phải trả cho việc mở kho:
$$ \sum_{f \in F} c_f x_f $$
Giai đoạn 2: Phân bổ khách hàng theo kịch bản
Khi một kịch bản i xảy ra và khách hàng xuất hiện, ta quyết định mỗi khách hàng được phục vụ bởi kho nào. Gọi:
- ycfi = 1 nếu khách hàng c được phục vụ bởi kho f trong kịch bản i, 0 nếu không.
- zfi ≥ 0 là lượng công suất bổ sung cần thiết cho kho f trong kịch bản i nếu nhu cầu vượt quá công suất sẵn có.
Chi phí phân bổ và bổ sung công suất trong kịch bản i là:
$$ \sum_{c \in C} \sum_{f \in F} q_{cf} y_{cf}^i + \sum_{f \in F} b_f z_f^i $$
Hàm mục tiêu: Tối thiểu hóa chi phí kỳ vọng
Giả định mỗi kịch bản xảy ra với xác suất bằng nhau (giả sử có N kịch bản), chúng ta tối thiểu hóa tổng chi phí kỳ vọng (thực tế thì xác suất có thể random tùy vào điều kiện thực tế):
$$ \min \quad \sum_{f \in F} c_f x_f + \frac{1}{N} \sum_{i=1}^{N} \left( \sum_{c \in C} \sum_{f \in F} q_{cf} y_{cf}^i + \sum_{f \in F} b_f z_f^i \right) $$
Các ràng buộc
1. Giới hạn tổng số kho mở
Tổng số kho mở không vượt quá v:
$$ \sum_{f \in F} x_f \le v $$
2. Giới hạn công suất
Tổng nhu cầu của các khách hàng gán cho kho f trong kịch bản i không vượt quá công suất sẵn có cộng với công suất bổ sung:
$$ \sum_{c \in C} d_{cf} y_{cf}^i \le u x_f + z_f^i \quad \forall f, i $$
3. Không phục vụ nếu kho không mở (Big-M constraint)
Ràng buộc đảm bảo nếu kho f không được mở (xf = 0) thì biến zfi bắt buộc bằng 0. Đây là một ràng buộc kiểu Big-M, giúp đảm bảo rằng không thể phân bổ thêm cho khách hàng hoặc thêm công suất cho một kho không tồn tại.
$$ z_f^i \le M x_f \quad \forall f, i $$
4. Mỗi khách hàng được phục vụ đúng scenario
Nếu khách hàng c xuất hiện trong kịch bản i, nó phải được phục vụ bởi một kho. Ràng buộc đảm bảo rằng nếu khách hàng xuất hiện trong một kịch bản thì phải được gán cho đúng một kho. Nếu khách hàng không xuất hiện trong kịch bản đó, thì không được gán cho kho nào.
$$ \sum_{f \in F} y_{cf}^i = h_c^i \quad \forall c, i $$
5. Điều kiện biến
$$ x_f \in \{0,1\}, \quad y_{cf}^i \in \{0,1\}, \quad z_f^i \ge 0 $$
Liên hệ với cấu trúc two-stage stochastic
Mô hình CWL có cấu trúc hai giai đoạn rất rõ ràng:
- Giai đoạn 1: quyết định xf trước khi biết khách hàng xuất hiện.
- Giai đoạn 2: quyết định ycfi và zfi sau khi kịch bản về khách hàng được tiết lộ.
Hàm mục tiêu tính theo kỳ vọng qua các kịch bản, thể hiện việc tối ưu hóa quyết định hiện tại dựa trên rủi ro tương lai, đúng bản chất của 2-stage stochastic optimization.