Tối ưu hoá 7 — Tối ưu dưới bất định

Khi input không còn là con số chắc chắn

Ở các bài trước — LP, MILP, danh mục & ALM — chúng ta luôn giả định các tham số đầu vào là biết chắc (deterministic): nhu cầu rút tiền tại ATM là 1,2 tỷ/ngày, lợi suất trái phiếu là 6,5%, chi phí vận chuyển là 3 triệu/chuyến. Solver nhận những con số này, trả về một nghiệm tối ưu — nhưng tối ưu với đúng bộ số đó.

Vấn đề: gần như không tham số nào trong ngân hàng là chắc chắn. Nhu cầu rút tiền cuối tuần dao động ±40%, lãi suất thị trường đổi theo chính sách, hành vi tất toán sớm của khách phụ thuộc tương lai không ai biết. Khi bạn cắm giá trị kỳ vọng (mean) vào mô hình deterministic rồi tối ưu, nghiệm nhận được thường quá khít với đúng kịch bản trung bình đó — và vỡ trận khi thực tế lệch đi. Ví dụ: tối ưu tồn quỹ ATM theo nhu cầu trung bình sẽ đặt vừa đủ tiền cho ngày thường, nhưng hết tiền (out-of-cash) vào ngày lễ khi nhu cầu vọt lên.

Đây gọi là flaw of averages (nghịch lý của giá trị trung bình): nghiệm tối ưu tại mean không phải là mean của các nghiệm tối ưu. Bài này trình bày ba trường phái xử lý bất định — stochastic programming, robust optimization, và chance constraints / risk-averse — cùng cách chọn giữa chúng, và mối liên hệ với dự báo (time series) và sai số ước lượng.

1. Ba cách nhìn về bất định

Trước khi vào chi tiết, cần phân biệt ta biết gì về bất định, vì đó quyết định chọn công cụ:

Không có công cụ nào "đúng" tuyệt đối — chúng đánh đổi giữa mức bảo thủ, dữ liệu cần có, và độ phức tạp tính toán khác nhau.

2. Stochastic programming — mô hình hoá bằng kịch bản

Quy hoạch ngẫu nhiên (stochastic programming) giả định ta có phân phối xác suất của tham số bất định, thường được rời rạc hoá thành một tập kịch bản (scenarios) hữu hạn ξ₁, ξ₂, …, ξ_S, mỗi kịch bản s có xác suất pₛ (với Σ pₛ = 1).

Thay vì tối ưu một hàm mục tiêu cố định, ta tối ưu kỳ vọng trên các kịch bản:

min   E[cost(x, ξ)]  =  Σ_s  pₛ · cost(x, ξₛ)

2.1 Two-stage recourse — quyết định trước, điều chỉnh sau

Mô hình mạnh nhất và phổ biến nhất là two-stage với recourse (điều chỉnh). Ý tưởng bám sát cách ra quyết định thực tế:

• Stage 1 (here-and-now): quyết định trước khi biết bất định. Ví dụ: chiều nay quyết định tiếp bao nhiêu tiền vào ATM cho ngày mai. Biến x.
• Quan sát bất định: sang ngày mai, nhu cầu thực tế ξ được lộ ra.
• Stage 2 (recourse / điều chỉnh): hành động sửa sai sau khi biết ξ. Ví dụ: nếu ATM sắp hết tiền → gọi xe tiếp quỹ khẩn cấp (đắt); nếu tồn quá nhiều → chịu chi phí vốn ứ đọng. Biến y(ξ) — phụ thuộc kịch bản.

Công thức tổng quát:

min_x   c·x  +  E_ξ[ Q(x, ξ) ]

với  Q(x, ξ) = min_y  q·y      (chi phí điều chỉnh stage 2)
              s.t.  W·y  ≥  h(ξ) − T·x
                    y ≥ 0

Q(x, ξ) là giá trị recourse: chi phí tối thiểu để "sửa" quyết định stage-1 x sau khi kịch bản ξ xảy ra. Vì ξ rời rạc thành S kịch bản, toàn bộ bài toán trở thành một LP/MILP lớn — có x chung và mỗi kịch bản một bộ biến yₛ riêng:

min   c·x  +  Σ_s  pₛ · q·yₛ
s.t.  W·yₛ  ≥  h(ξₛ) − T·x     ∀ s = 1..S
      x ≥ 0,  yₛ ≥ 0           ∀ s

Đây gọi là deterministic equivalent — vẫn là LP/MILP nên giải được bằng solver thường (solvers & tools), chỉ là to hơn S lần ở phần stage-2.

2.2 Ví dụ: tồn quỹ ATM two-stage (minh hoạ)

Pseudocode dưới đây chỉ minh hoạ mô hình, không phải SQL chạy được:

# MINH HOẠ — không phải SQL chạy được
# Stage 1: nap x đồng vào ATM chiều nay (chưa biết nhu cầu ngày mai)
# Scenarios: nhu cau ngay mai
scenarios = {
    "thap":   {"demand": 0.8e9, "prob": 0.25},
    "trung":  {"demand": 1.2e9, "prob": 0.50},
    "cao":    {"demand": 1.8e9, "prob": 0.25},
}
c_hold  = 0.0002   # chi phi von u dong / dong / ngay
c_emerg = 0.05     # chi phi tiep quy khan cap / dong thieu (rat dat)

# min  c_hold * x  +  E[ recourse ]
#   recourse(s):  neu demand_s > x -> tiep khan cap (demand_s - x) * c_emerg
#                 con lai -> ton du (x - demand_s) * c_hold
# Solver chon x can bang: du cao de it khi het tien, du thap de it u dong

Nghiệm two-stage thường cao hơn mức "vừa đủ nhu cầu trung bình" — vì nó tự bảo hiểm trước kịch bản cao, do chi phí thiếu (c_emerg) đắt hơn chi phí thừa (c_hold) nhiều lần. Đây chính là điều mô hình deterministic-tại-mean bỏ sót.

2.3 Sinh kịch bản (scenario generation)

Chất lượng nghiệm phụ thuộc hoàn toàn vào chất lượng kịch bản. Các cách sinh:

• Từ lịch sử: lấy các ngày quá khứ làm kịch bản (empirical), gán xác suất bằng nhau.
• Từ dự báo: dùng mô hình time series hoặc hồi quy để dự báo trung bình + phân phối sai số → mô phỏng Monte Carlo → gom cụm thành ít kịch bản đại diện.
• Scenario reduction: S quá lớn làm bài toán không giải nổi; dùng clustering (k-means, forward selection) để rút về vài chục kịch bản giữ nguyên phân phối.
• Kịch bản stress: chèn thêm kịch bản cực đoan (khủng hoảng thanh khoản) với xác suất nhỏ nhưng hậu quả lớn — quan trọng cho ngân hàng.

Cây kịch bản two-stage:

3. Robust optimization — an toàn cho trường hợp xấu nhất

Stochastic programming đòi phân phối xác suất — nhưng nhiều khi ta không có đủ dữ liệu để ước lượng phân phối đáng tin. Robust optimization (RO) bỏ hẳn xác suất: chỉ cần biết tham số bất định nằm trong một tập bất định (uncertainty set) U, rồi tối ưu cho trường hợp xấu nhất trong U:

min_x   max_{ξ ∈ U}   cost(x, ξ)

Ta tìm quyết định x tốt nhất trong tình huống tệ nhất (min-max). Nghiệm không bao giờ vi phạm ràng buộc với mọi ξ ∈ U — rất an toàn, nhưng cũng dễ quá bảo thủ (over-conservative) nếu U quá lớn.

3.1 Định nghĩa uncertainty set

Hình dạng U quyết định mức bảo thủ và độ khó tính toán:

3.2 Kiểm soát mức bảo thủ — budget of uncertainty

Điểm hay của tập budgeted (Bertsimas & Sim): thay vì giả định tất cả tham số cùng lệch xấu nhất (phi thực tế), ta cho phép tối đa Γ trong số n tham số lệch. Tham số Γ ∈ [0, n] là "ngân sách bất định" — cần bằng an toàn với hiệu quả:

• Γ = 0 → về deterministic (không phòng gì).
• Γ = n → bảo thủ tối đa (worst-case như box).
• Γ trung gian → phòng vừa đủ, và mô hình RO vẫn giữ dạng LP/MILP giải được.

Sơ đồ box vs ellipsoidal uncertainty set (2 tham số):

RO đặc biệt hợp khi: (a) thiếu dữ liệu ước lượng phân phối, (b) cần đảm bảo tuyệt đối không vi phạm (ví dụ giới hạn thanh khoản pháp lý), (c) chi phí sai lầm quá lớn để chấp nhận rủi ro xác suất.

4. Chance constraints — thoả ràng buộc "hầu hết thời gian"

Đôi khi worst-case của RO quá đắt: để luôn luôn đủ tiền dù nhu cầu cực đại có thể phải nạp gấp đôi vốn cần thiết. Thực tế ta chấp nhận thỉnh thoảng thiếu, miễn là hiếm. Chance constraint (ràng buộc xác suất) phát biểu:

P( ràng buộc được thoả )  ≥  p        (ví dụ p = 0.95)

Đọc là: "đủ tiền mặt tại ATM với xác suất ≥ 95% thời gian". p gọi là mức tin cậy (service level). Cụ thể cho tồn quỹ:

P( x  ≥  nhu_cầu )  ≥  0.95

Nếu nhu cầu ~ Normal(μ, σ), ràng buộc này quy về một dạng đóng đơn giản:

x  ≥  μ  +  z_0.95 · σ      (z_0.95 ≈ 1.645)

Đây chính là công thức safety stock trong quản lý tồn kho — z·σ là đệm an toàn (buffer). Tăng p từ 95% → 99% (z ≈ 2.33) làm đệm dày hơn, đủ tiền thường xuyên hơn, nhưng ứ đọng nhiều hơn. Đây là đánh đổi service level ↔ chi phí vốn cốt lõi trong tối ưu tồn quỹ ATM.

Khi phân phối không chuẩn / có nhiều ràng buộc phụ thuộc nhau, chance constraint được xấp xỉ bằng kịch bản: đảm bảo ràng buộc thoả trong ít nhất ⌈p·S⌉ trên S kịch bản (scenario approximation — thường thành MILP với biến chỉ báo vi phạm).

5. Risk-averse — không chỉ quan tâm kỳ vọng

Tối ưu kỳ vọng (E[cost]) là risk-neutral — coi trọng trung bình, bỏ qua độ phân tán. Nhưng ngân hàng thường ghét rủi ro đuôi (tail risk): một tổn thất cực lớn ở kịch bản xấu tệ hơn nhiều lần một tổn thất trung bình đều đặn. Ta cần đo rủi ro đuôi và đưa vào mục tiêu.

• VaR (Value-at-Risk) ở mức α: mức tổn thất mà chỉ (1−α)% kịch bản vượt quá. Trực quan nhưng không lồi → khó tối ưu.
• CVaR (Conditional VaR / Expected Shortfall): trung bình tổn thất trong (1−α)% kịch bản tệ nhất. CVaR là lồi và tối ưu được bằng LP (công thức Rockafellar–Uryasev) → là lựa chọn chuẩn.

Mục tiêu risk-averse điển hình đánh đổi kỳ vọng với rủi ro qua tham số λ:

min   E[cost]  +  λ · CVaR_α(cost)

• λ = 0 → risk-neutral (chỉ tối ưu trung bình).
• λ lớn → né đuôi tổn thất mạnh, nghiệm bảo thủ hơn, kỳ vọng tệ đi chút nhưng an toàn hơn nhiều ở kịch bản xấu.

Đây chính là cầu nối giữa stochastic (tối ưu trung bình) và robust (tối ưu worst-case): CVaR là "worst-case mềm" — quan tâm phần đuôi chứ không chỉ một điểm tệ nhất tuyệt đối.

6. Đo giá trị của việc mô hình hoá bất định

Có đáng công sức dựng mô hình stochastic không? Có hai chỉ số kinh điển trả lời:

VSS — Value of the Stochastic Solution: so nghiệm stochastic với nghiệm deterministic-tại-mean (cắm giá trị trung bình rồi giải).

VSS  =  (chi phí kỳ vọng của nghiệm deterministic-tại-mean)
      − (chi phí kỳ vọng của nghiệm stochastic)

VSS lớn ⇒ mô hình deterministic tốn kém đáng kể, đáng đầu tư stochastic. VSS ≈ 0 ⇒ bất định không quan trọng lắm, deterministic là đủ.

EVPI — Expected Value of Perfect Information: giá trị của việc biết trước bất định.

EVPI  =  (chi phí kỳ vọng của nghiệm stochastic)
       − (chi phí nếu biết trước ξ mỗi kịch bản rồi mới quyết)

EVPI = mức tối đa đáng chi để mua thông tin/dự báo tốt hơn. Nếu EVPI nhỏ, đầu tư thêm vào dự báo không giúp nhiều; nếu lớn, cải thiện dự báo (ts-08) sẽ trực tiếp giảm chi phí.

7. Predict-then-optimize & sai số ước lượng

Trong thực tế, tham số của mô hình tối ưu (nhu cầu, lợi suất) thường đến từ một mô hình dự báo/ML — quy trình predict-then-optimize: dự báo ξ̂ trước, rồi tối ưu như thể ξ̂ là đúng. Cạm bẫy:

• Nghiệm nhạy input: LP/MILP có thể rất nhạy với sai số nhỏ ở tham số (một hệ số lệch chút làm đổi hẳn nghiệm cực biên). Sai số dự báo lan sang quyết định.
• Sai số không cân xứng về hậu quả: dự báo lệch cùng độ lớn nhưng chiều "thiếu tiền" tốn hơn "thừa tiền" nhiều — mô hình dự báo tối thiểu hoá MSE không biết điều đó.

Cách xử lý:

• Robust / chance constraint bao quanh sai số dự báo: coi khoảng tin cậy của dự báo làm uncertainty set, tự động phòng sai số ước lượng.
• Decision-focused / end-to-end learning: huấn luyện mô hình dự báo để tối ưu chất lượng quyết định cuối (decision loss / regret), không phải để tối ưu độ chính xác dự báo. Đây là hướng khái quát hoá predict-then-optimize, thu hẹp khoảng cách giữa "dự báo đúng" và "quyết định đúng".

Use case thực tế

Bài toán: tối ưu tồn quỹ ATM dưới nhu cầu bất định — mạng 120 máy ATM khu vực Hà Nội.

Phòng Quản lý tiền mặt cần quyết định mỗi chiều nạp bao nhiêu tiền vào từng ATM cho ngày hôm sau. Ràng buộc: chi phí xe tiếp quỹ khẩn cấp = 2 triệu/chuyến + rủi ro uy tín khi khách gặp máy hết tiền; chi phí vốn ứ đọng ≈ lãi suất qua đêm 4%/năm trên số dư nằm chết trong ATM.

Cách làm cũ (deterministic-tại-mean): nạp = nhu cầu trung bình lịch sử của máy đó. Kết quả: out-of-cash 11% số ngày (đặc biệt cuối tuần, cận lễ), khách phàn nàn.

Cách mới (chance constraint + kịch bản):

1. Ước lượng phân phối nhu cầu mỗi ATM theo ngày trong tuần từ 12 tháng lịch sử giao dịch rút tiền (mean μ và độ lệch chuẩn σ). SQL bên dưới chuẩn bị chính các thống kê này.
2. Đặt service level 98%: nạp x = μ + z_0.98·σ với z_0.98 ≈ 2.05 → mỗi máy có đệm an toàn 2.05·σ.
3. Ràng buộc tổng vốn khả dụng của kho quỹ khu vực (tổng nạp ≤ tồn kho quỹ) → không giải rời từng máy mà là bài toán phân bổ có ràng buộc chung → MILP nhỏ.
4. Chèn 2 kịch bản stress (ngày lễ, đầu tháng lương) với σ nhân 1,8.

Kết quả (minh hoạ): out-of-cash giảm còn 1,8%, số chuyến tiếp quỹ khẩn cấp giảm ~70%; vốn ứ đọng tăng nhẹ nhưng tổng chi phí (khẩn cấp + vốn) giảm ròng ~22%. Đo VSS cho thấy chênh chi phí giữa nghiệm mean và nghiệm stochastic là đáng kể, xác nhận bất định đáng mô hình hoá.

Chuẩn bị thống kê bất định đầu vào — mean và độ lệch chuẩn của giá trị/số giao dịch rút tiền theo ngày trong tuần, dùng làm μ, σ cho các kịch bản chance-constraint:

-- ▶ Chạy được
WITH rut_theo_ngay AS (
    SELECT
        EXTRACT(DOW FROM t.created_at)  AS thu_trong_tuan,
        t.created_at::date              AS ngay,
        SUM(t.amount)                   AS tong_rut_ngay,
        COUNT(*)                        AS so_gd_ngay
    FROM transactions t
    WHERE t.kind = 'debit'
      AND t.created_at >= NOW() - INTERVAL '12 months'
    GROUP BY EXTRACT(DOW FROM t.created_at), t.created_at::date
)
SELECT
    thu_trong_tuan,
    COUNT(*)                                          AS so_ngay_quan_sat,
    ROUND(AVG(tong_rut_ngay)::numeric, 0)             AS mu_gia_tri_rut,
    ROUND(STDDEV(tong_rut_ngay)::numeric, 0)          AS sigma_gia_tri_rut,
    ROUND(AVG(so_gd_ngay)::numeric, 1)                AS mu_so_gd,
    ROUND(STDDEV(so_gd_ngay)::numeric, 1)             AS sigma_so_gd,
    ROUND((AVG(tong_rut_ngay) + 2.05 * STDDEV(tong_rut_ngay))::numeric, 0)
                                                      AS nap_de_xuat_98pct
FROM rut_theo_ngay
GROUP BY thu_trong_tuan
ORDER BY thu_trong_tuan;

Cột nap_de_xuat_98pct = μ + 2.05·σ chính là mức nạp gợi ý theo chance constraint mức 98% cho từng ngày trong tuần — đầu vào trực tiếp cho mô hình phân bổ.

Ghi nhớ

• Flaw of averages: cắm giá trị trung bình vào mô hình deterministic rồi tối ưu cho nghiệm rủi ro — nghiệm tối ưu tại mean ≠ mean của các nghiệm tối ưu.
• Stochastic programming: mô hình bất định bằng kịch bản có xác suất, tối ưu kỳ vọng. Cần có phân phối (từ lịch sử/dự báo).
• Two-stage recourse: quyết định trước (here-and-now) → quan sát bất định → điều chỉnh sau (recourse). Rời rạc kịch bản → deterministic equivalent là LP/MILP lớn.
• Robust optimization: không cần xác suất, tối ưu worst-case trong uncertainty set. An toàn nhưng dễ bảo thủ; điều khiển mức bảo thủ bằng budget Γ (Bertsimas–Sim).
• Chance constraint: ràng buộc thoả với xác suất ≥ p (ví dụ đủ tiền 95%). Với nhu cầu chuẩn → công thức safety stock μ + z·σ; đánh đổi service level ↔ chi phí vốn.
• Risk-averse (CVaR): đo trung bình đuôi tổn thất, lồi và tối ưu bằng LP; mục tiêu E[cost] + λ·CVaR cân bằng kỳ vọng và rủi ro đuôi.
• VSS đo giá trị của mô hình stochastic vs deterministic; EVPI đo giá trị tối đa của thông tin/dự báo hoàn hảo.
• Predict-then-optimize: nghiệm nhạy sai số ước lượng đầu vào; robust/chance-constraint bao quanh sai số dự báo giúp phòng; decision-focused learning tối ưu trực tiếp chất lượng quyết định.
• Bối cảnh ngân hàng: tối ưu tồn quỹ ATM/thanh khoản dưới nhu cầu bất định (đủ tiền xác suất cao mà không ứ đọng), phân bổ dưới lãi suất/kịch bản kinh tế bất định, và stress scenario.