Trong các bài toán tối ưu hóa chuỗi cung ứng thực tế, một doanh nghiệp thời trang tại Đức nhập hàng từ Bangladesh đối mặt với một biến số then chốt: chu kỳ sản xuất và vận chuyển đường biển kéo dài nhiều tuần. Doanh nghiệp buộc phải chốt số lượng sản xuất vào mùa thu trước khi mùa đông bắt đầu. Sản xuất quá ít sẽ dẫn đến mất doanh thu; sản xuất quá nhiều dẫn đến tồn kho dư thừa và giảm giá thanh lý nặng nề. Vấn đề cốt lõi là nhu cầu thực tế không phải một số nguyên xác định, mà là một biến ngẫu nhiên.
Nếu bỏ qua tính bất định và xem nhu cầu là một hằng số đã biết, bài toán được thiết lập dưới dạng quy hoạch tuyến tính (Linear Programming – LP) chuẩn:
Trong đó, $x$ là số lượng sản phẩm cần đặt, $c$ là chi phí sản xuất trên một đơn vị, $h$ là nhu cầu dự kiến, và $T$ là ma trận hệ số kỹ thuật. Ràng buộc yêu cầu sản lượng tối thiểu đáp ứng nhu cầu. Tuy nhiên, khi nhu cầu là biến ngẫu nhiên $\xi$, mô hình trở thành:
Biểu thức này không thể giải trực tiếp bằng các bộ giải chuẩn (solvers) vì đây là một bài toán chưa xác định rõ ràng (ill-defined): ràng buộc chứa biến ngẫu nhiên không có tính khả thi tuyệt đối theo nghĩa đơn trị. Quy hoạch ngẫu nhiên (Stochastic Programming) cung cấp các nền tảng toán học chặt chẽ để chuyển đổi mô hình này thành bài toán tối ưu giải được.
Bốn phương pháp xử lý tính bất định trong tối ưu hóa
1. Tối ưu hóa bền vững (Robust Optimization): Dự phòng kịch bản xấu nhất
Phương pháp tối ưu hóa bền vững không yêu cầu xác định toàn bộ hàm phân phối xác suất của $\xi$, mà chỉ yêu cầu xác định tập giá trị khả dĩ (support), gọi là tập bất định (uncertainty set) $U$. Ràng buộc phải được thỏa mãn với mọi kịch bản $\xi \in U$:
Nếu khoảng nhu cầu dự báo là $U = [0, 10]$, nghiệm tối ưu bắt buộc phải chuẩn bị cho kịch bản nhu cầu bằng 10. Cách tiếp cận này đảm bảo an toàn tuyệt đối nhưng mang tính bảo thủ cao (conservative), dẫn đến chi phí dự phòng quá mức cho những tình huống có xác suất xảy ra cực thấp.
2. Ràng buộc cơ hội (Chance Constraints): Giảm thiểu rủi ro theo ngưỡng xác suất
Thay vì thỏa mãn với mọi trường hợp, ràng buộc cơ hội cho phép vi phạm ràng buộc ở một tỷ lệ nhỏ chấp nhận được. Với ngưỡng tin cậy $\alpha \in (0, 1)$ (thường chọn $0.95$ hoặc $0.99$), ràng buộc cơ hội đồng thời (joint chance constraint) yêu cầu:
Trường hợp yếu hơn là ràng buộc cơ hội riêng lẻ (individual chance constraints), áp dụng độc lập cho từng dòng thứ $i$:
Về mặt toán học, ràng buộc đồng thời luôn khắt khe hơn ràng buộc riêng lẻ khi có cùng giá trị $\alpha$. Tuy nhiên, hàm xác suất bên trong ràng buộc thường là phi tuyến và phi lồi (non-convex) đối với biến quyết định $x$, khiến việc giải trực tiếp trên các bộ giải LP tiêu chuẩn trở nên rất phức tạp, ngoại trừ một số dạng phân phối đặc thù như phân phối Gauss.
3. Mô hình bù đắp hai giai đoạn (Two-stage Recourse Models)
Trong thực tế, việc vi phạm nhu cầu không làm sụp đổ toàn bộ hệ thống mà phát sinh thêm hành động khắc phục (corrective action / recourse), ví dụ: sản xuất khẩn cấp nội địa hoặc chấp nhận chi phí phạt do mất doanh số. Trình tự ra quyết định được chuẩn hóa như sau:
- Giai đoạn 1: Đưa ra quyết định $x$ (ví dụ: sản lượng đặt sớm tại xưởng giá rẻ) trước khi biết giá trị của $\xi$.
- Biến cố ngẫu nhiên: $\xi$ được hiện thực hóa thành giá trị cụ thể.
- Giai đoạn 2: Đưa ra quyết định bù đắp $y$ (ví dụ: đặt thêm hàng bổ sung khẩn cấp) với chi phí $q(\xi)^T y$.
Mô hình toán học giai đoạn một tối thiểu hóa tổng chi phí cam kết ban đầu và kỳ vọng chi phí khắc phục trong tương lai:
Hàm giá trị tối ưu $v(\xi, x)$ ở giai đoạn hai được định nghĩa:
Vế phải $h(\xi) – T(\xi)x$ biểu diễn phần nhu cầu chưa được thỏa mãn bởi quyết định giai đoạn một. Biến $y$ sẽ bù đắp khoảng thiếu hụt này qua ma trận công nghệ bù đắp $W$. Hai khái niệm cốt lõi cần lưu ý:
- Fixed recourse: Ma trận $W$ cố định, không phụ thuộc vào hiện thực hóa của biến ngẫu nhiên $\xi$.
- Complete recourse (bù đắp hoàn toàn): Luôn tồn tại nghiệm khả dĩ $y \ge 0$ cho bài toán giai đoạn hai với bất kỳ giá trị $x$ và kịch bản $\xi$ nào. Nếu điều kiện này không thỏa mãn, miền khả dĩ của giai đoạn một sẽ bị giới hạn bởi các ràng buộc ẩn (implicit constraints).
4. Mô hình bù đắp đa giai đoạn (Multi-stage Recourse Models)
Khi các quyết định và biến cố diễn ra liên tiếp theo chuỗi thời gian $t = 1, 2, \dots, T$, bài toán trở thành quy hoạch ngẫu nhiên đa giai đoạn. Cấu trúc thông tin được mô hình hóa dưới dạng cây kịch bản (scenario tree):
Mỗi nút trên cây đại diện cho một trạng thái tại thời điểm $t$, phụ thuộc vào lịch sử biến ngẫu nhiên $\xi_{[t]} = (\xi_1, \dots, \xi_t)$. Ràng buộc cốt lõi trong mô hình đa giai đoạn là tính không đón trước (non-anticipativity): các quyết định tại thời điểm $t$ chỉ được phép sử dụng thông tin đã được quan sát đến thời điểm $t$, tuyệt đối không được tận dụng các biến cố thuộc tương lai chưa xảy ra.
Giải thuật và dạng tương đương xác định (Deterministic Equivalent)
Để giải một bài toán hai giai đoạn bằng các thuật toán quy hoạch tuyến tính (Simplex, Interior Point), mô hình được chuyển đổi thành dạng tương đương xác định (Deterministic Equivalent Formulation). Khi $\xi$ tuân theo phân phối rời rạc với $S$ kịch bản $\{\xi^1, \dots, \xi^S\}$ và xác suất tương ứng $p_s$ ($s = 1, \dots, S$):
Mô hình trở thành một bài toán LP quy mô lớn có cấu trúc góc khối đặc thù. Khi phân phối của $\xi$ liên tục, phương pháp xấp xỉ trung bình mẫu (Sample Average Approximation – SAA) được áp dụng bằng cách lấy mẫu ngẫu nhiên độc lập $S$ điểm dữ liệu để ước lượng kỳ vọng:
Khi số lượng kịch bản $S$ tăng cao, kích thước mô hình vượt quá khả năng xử lý nguyên khối của solver. Các thuật toán phân rã (decomposition methods) sẽ được khai thác:
Benders Decomposition (trong quy hoạch ngẫu nhiên còn gọi là L-shaped method) tách bài toán lớn thành một bài toán chủ (master problem) chứa biến $x$, và $S$ bài toán con độc lập chứa biến $y_s$. Bộ giải bổ sung lặp lại các vết cắt tối ưu (optimality cuts) và vết cắt khả dĩ (feasibility cuts) để tiến tới nghiệm tối ưu toàn cục.
Định lượng hiệu quả: EVPI và VSS
Trước khi đầu tư tài nguyên tính toán cho quy hoạch ngẫu nhiên, hai chỉ số lý thuyết quyết định chuẩn hóa được sử dụng để đánh giá giá trị kinh tế của mô hình:
- Value of Stochastic Solution (VSS): Đo lường mức cải thiện chi phí khi sử dụng mô hình ngẫu nhiên so với việc chỉ thay thế biến ngẫu nhiên bằng giá trị trung bình $\mathbb{E}[\xi]$ rồi giải mô hình xác định. VSS lớn chứng minh việc mô hình hóa phân phối bất định là bắt buộc.
- Expected Value of Perfect Information (EVPI): Đo lường số tiền tối đa doanh nghiệp nên chi trả để sở hữu dự báo hoàn hảo về tương lai trước khi đưa ra quyết định giai đoạn một. EVPI thiết lập trần lợi nhuận cho bất kỳ hệ thống dự báo dữ liệu nào.
Nguồn: Towards Data Science
Liên hệ qua Zalo
