机会约束

机会约束（chance constraint）要求一个随机约束以不低于指定水平的概率成立。决策通常在随机量揭晓前作出，允许一小部分情景违反约束。其可靠性既取决于概率计算，也取决于所假设的随机模型是否适合实际问题。

用概率决定库存

库存量q在需求D出现前确定，单位库存成本为一，希望最小化q，并以至少九成概率满足需求。设需求为1、3、5的概率依次为 $1/2,3/10,1/5$，约束是 $Pr(D\le q)\ge 9/10$。

当 $q<1$ 时服务概率为零，$1\le q<3$ 时为1/2，$3\le q<5$ 时为4/5，$q\ge 5$ 时为一。因成本随q增加，最优q=5。只准备平均需求 $𝔼D=12/5$ 时服务概率只有一半，平均值并不是九成服务的库存阈值。

实心点属于右侧平台，空心点表示左极限；九成服务需要库存五，八成则库存三已恰好达标。

有解变式允许两成违约，即要求服务概率至少4/5，此时q=3已经恰好达标，最优值变成三。概率等号必须保留：把约束误写成严格大于4/5，就会将答案推到五。

定义、分位数与联合事件

设 $x\in X\subseteq {ℝ}^n$ 是确定性决策，$\xi$ 为具有指定分布的随机向量；对每个x，$g(x,\xi )$ 可测。给定违约容许量 $0<\epsilon <1$，单个机会约束写为 $$Pr\{g(x,\xi )\le 0\}\ge 1-\epsilon .$$ 库存例中 $g(q,D)=D-q$。若F是D的分布函数，采用下分位数 $F^{-1}(\eta )=inf\{t:F(t)\ge \eta \}$，则约束等价于 $q\ge F^{-1}(1-\epsilon )$。理由是F单调且右连续，分位数处达到至少η，此后全部达标，其前均不达标。此处 $0<\eta <1$ 保证实值随机变量的相应分位数有限。

对m个约束，联合机会约束要求它们同时成立：$Pr(\bigcap _{i=1}^m\{g_i(x,\xi )\le 0\})\ge 1-\epsilon$。每条各有九成成功并不能保证联合九成。两条独立事件若各有九成成功，联合只有 $0.9^2=0.81$。

一百个等可能格子中，绿色八十一格同时成功，红色十九格至少一项失败。

一种充分方法是分配非负风险额度 ${\epsilon }_i$，使 $\sum _i{\epsilon }_i\le \epsilon$，并分别要求 $Pr(g_i>0)\le {\epsilon }_i$。因为“至少一条失败”的概率不大于各失败概率之和，联合成功至少为 $1-\sum _i{\epsilon }_i\ge 1-\epsilon$。这不需要独立性，但可能保守。例如两条失败事件完全重合时，失败概率只算一次，而求和会重复计算。

高斯仿射约束的确定性等价式

令随机系数 $a\sim N(\mu ,\Sigma )$，其中 $\Sigma$ 对称半正定，决策x确定，b为常数。令 $\eta =1-\epsilon \in [1/2,1)$。固定x后，$Y=a^{𝖳}x$ 为均值 ${\mu }^{𝖳}x$、方差 ${\sigma }^2=x^{𝖳}\Sigma x$ 的正态变量。若 $\sigma >0$，标准化给出 $$Pr(Y\le b)=\Phi \left(\frac{b-{\mu }^{𝖳}x}{\sigma }\right)\ge \eta ⟺{\mu }^{𝖳}x+{\Phi }^{-1}(\eta )\Vert {\Sigma }^{1/2}x{\Vert }_2\le b.$$ 这里Φ是标准正态分布函数。若σ=0，Y几乎必然等于其均值，原约束直接等价于 ${\mu }^{𝖳}x\le b$，也与右侧式一致。由于η至少一半，分位数系数非负，右式为凸的二阶锥约束；η小于一半时系数为负，不能再据此断言凸性。该化简针对单条高斯仿射事件，多条的联合事件通常不能原样逐条等价替换。

机会约束不等于对所有可能情景成立的鲁棒约束。若需求为无上界正态模型，任何有限q都有正的极端需求概率，仍可能满足小于一的服务水平，却无法保证所有需求都被覆盖。反过来，用有限样本中达标的频率替代真实概率后，得到的只是经验约束；其总体保证需要额外的抽样误差分析。

精确计算离散库存阈值

下面用 Python 3 标准库的有理数逐级累积概率，避免把临界的0.8误作不足。输入为有限的“需求、概率”对及容许违约概率；概率用可精确表示的十进制数、字符串或Fraction给出，须非负且总和恰为一。函数复制、合并和排序输入，返回最小库存及累计概率表，不改写原列表。S个情景需要 $O(S\log S)$ 比较时间、$O(S)$ 空间；有理数位数增长的算术成本另计。

Python 3

from fractions import Fraction

def exact_stock(scenarios, epsilon):
    eps = Fraction(str(epsilon))
    if not 0 < eps < 1:
        raise ValueError("epsilon must lie strictly between zero and one")
    masses = {}
    for demand,probability in scenarios:
        q,p = Fraction(str(demand)),Fraction(str(probability))
        if p < 0:
            raise ValueError("nonnegative probabilities required")
        if p:
            masses[q] = masses.get(q,Fraction(0))+p
    if sum(masses.values()) != 1:
        raise ValueError("probabilities must sum exactly to one")
    target,total,answer = 1-eps,Fraction(0),None
    table = []
    for q,p in sorted(masses.items()):
        total += p
        table.append((q,total))
        if answer is None and total >= target:
            answer = q
    return answer,table

data = [(1,.5),(3,.3),(5,.2)]
for eps in (.1,.2):
    answer,table = exact_stock(data,eps)
    print(eps,float(answer),[(float(q),float(p)) for q,p in table])
assert exact_stock(data,.2)[0] == 3

两次输出最小库存分别为5和3，表中三个累计概率为0.5、0.8、1。这是已知离散分布下的精确枚举；若概率本身来自估计，计算精确不等于模型没有不确定性。