多目标优化与软约束

许多决策同时有多个合理的质量指标。配送方案可能用更晚的到达换取更低的运营成本；生产方案可能保护服务质量但消耗更多容量。多目标优化把这种政策明确写出来，而不是藏在一个没有解释的标量分数中。

本页用配送延迟与运营成本的示例区分硬约束和软违规、加权和与字典序优先级，以及业务容差和求解器数值容差。下面的公式与求解器无关，不规定某个 OSPF 或后端 API。

1. 硬规则、软规则与目标维度

令 $X$ 表示由硬规则定义的集合。硬规则属于可行性：不在 $X$ 中的方案即使在其他指标上得分很好，也不是候选方案。例如，每个订单必须恰好服务一次、车辆容量必须遵守、法定工时上限必须满足，都是硬规则。

软规则不强制满足，而是被测量。如果软上界为 $g(x)\le b$，则其非负违规量为

$$v(x)=max\{0,g(x)-b\}.$$

对于软下界 $g(x)\ge b$ 和软等式 $g(x)=b$，分别使用

$$v(x)=max\{0,b-g(x)\},v(x)=|g(x)-b|.$$

$v$ 的单位继承自 $g$：配送延迟以天或小时计，预算违规以元或美元计。求解器的可行性容差不是业务违规量。

硬规则先定义 $X$，再在其上建立目标向量：

$$f(x)=(f_1(x),f_2(x),\dots ,f_K(x)),$$

每个分量都有方向、单位和政策含义。对于最小化问题，如果 $x$ 在每个分量上都不差于 $x^{\prime }$，且至少一个分量严格更好，则称 $x$ Pareto 支配 $x^{\prime }$。加权和依据交换率政策选择一个点；字典序目标声明指标的重要顺序。

2. 加权和与字典序

2.1 加权和

对非负权重的最小化指标，可以写成：

$$F_w(x)=\sum _{k=1}^K{w}_k{\overline{f}}_k(x),$$

其中 ${\overline{f}}_k$ 应是无量纲的，或者已经明确换算到同一业务单位。一个常用的归一化是：

$${\overline{f}}_k(x)=\frac{f_k(x)-{\ell }_k}{u_k-{\ell }_k},$$

这里 ${\ell }_k,u_k$ 是声明过的参考下界和上界，要求 $u_k>{\ell }_k$；恒定指标需要单独处理，不能除以零。只有相对于这种归一化，权重才有可解释性。直接把“天数 + 金额”相加，会暗中指定一个任意的交换率。

当指标之间确实可以补偿时，加权和很有用。但它也可能错过非凸 Pareto 前沿上的点；如果某个权重足够有利，还可能接受一个软规则的大违规量。

2.2 字典序目标

两个最小化指标的字典序最小化 $(f_1,f_2)$ 表示：

1. 先找到 $f_1$ 的最小可达值；
2. 在达到该值的方案中，再找到 $f_2$ 的最小值。

第一个指标不会为了第二个指标的改善而牺牲。这适用于“任何一天延迟都比允许的成本节省更重要”的情形，也适用于必须先优化的监管要求。

只有在知道目标范围和可达分辨率时，单个标量才能复现字典序政策。如果 $f_1$ 的最小可达间隔为 ${\delta }_1>0$，$f_2$ 的可能变化最多为 ${\mathrm{\Delta }}_2$，则取

$$M>\frac{{\mathrm{\Delta }}_2}{{\delta }_1}$$

并最小化 $M{f}_1+f_2$。如果没有正的分辨率或有限的第二目标上界，随意选一个很大的权重并不能证明它等价于字典序。

2.3 优先级层的容差

有时第一个指标允许小幅变差，以换取第二个指标的明显改善。设第一个指标已证明的最优值为 $f_1^{\ast }$，设业务容差 ${\epsilon }_1$ 与 $f_1$ 使用同一单位。对最小化问题，第二层可以在以下条件下求解：

$$f_1(x)\le f_1^{\ast }+{\epsilon }_1.$$

这是业务政策容差，不是浮点可行性容差。应说明它是绝对容差还是相对容差，并在结果证据中保留其单位。

3. 可手算示例：配送延迟与路线成本

3.1 业务描述

一辆车在两个连续的一天时间槽 $0$ 和 $1$ 中配送订单 $A$、$B$。订单 $A$ 在第 $0$ 天开始时截止，订单 $B$ 在第 $1$ 天开始时截止。先访问 $A$ 的路线成本为 10 美元，先访问 $B$ 的路线成本为 2 美元。截止时间是软规则：允许迟到，但要按天计量。每个订单恰好配送一次、每个订单占用一个时间槽，是硬规则。

这个刻意缩小的数据集可以逐个检查全部候选解，也能说明加权政策与字典序政策的选择是业务决策，而不是事后才决定的代数细节。

3.2 变量与硬约束

令

$$y_{AB},y_{BA}\in \{0,1\}$$

表示选择的路线顺序。令 $d_A,d_B\in \{0,1\}$ 表示配送槽，其中 $0$ 是第一个槽，$1$ 是第二个槽。路线与槽位的硬规则为：

$$y_{AB}+y_{BA}=1,$$$$d_A+d_B=1,$$$$d_A=y_{BA},d_B=y_{AB}.$$

最后两条等式把路线选择与槽位分配连接起来。这些不是软约束：在同一个槽配送两次、或没有服务某个订单，都会使方案不可行。

3.3 软违规、中间值与成本

令截止槽位为 ${\tau }_A=0$、${\tau }_B=1$。一般模型中的延迟为：

$${\ell }_i=max\{0,d_i-{\tau }_i\}.$$

在本例的两个槽域中，它精确化为：

$${\ell }_A=d_A,{\ell }_B=0,L={\ell }_A+{\ell }_B.$$

因此 $L$ 是按天计算的总延迟。路线成本中间值为：

$$C=10y_{AB}+2y_{BA}\text{美元}.$$

两个目标维度为 $(L,C)$，都取最小值。若延迟变量只用下界表示，必须论证目标在没有其他耦合阻碍时将它压到正部值，或者另用精确函数图像约束定义它。仅添加上界不能保证等于正部值。

3.4 枚举并检查两条路线

只有两个可行的路线选择：

路线	$y_{AB}$	$y_{BA}$	$d_A$	$d_B$	${\ell }_A$	${\ell }_B$	$L$（天）	$C$（美元）
$A\to B$	$1$	$0$	$0$	$1$	$0$	$0$	$0$	$10$
$B\to A$	$0$	$1$	$1$	$0$	$1$	$0$	$1$	$2$

两行都满足全部硬约束。第二行节省 8 美元，但使订单 $A$ 延迟一天。

3.5 加权政策

为了明确单位，定义无量纲标量：

$$F_5(x)=5\frac{L}{1\text{天}}+1\frac{C}{1\text{美元}}.$$

两个方案的值为：

$$F_5(A\to B)=5(0)+10=10,$$$$F_5(B\to A)=5(1)+2=7.$$

按照这一交换率政策，成本节省获胜，选择 $B\to A$。如果把延迟权重改为 $9$，则

$$F_9(A\to B)=10,F_9(B\to A)=9+2=11,$$

此时选择 $A\to B$。没有哪个权重永远正确；每个权重都说明，在单位换算后业务如何评价“一天”相对于“一美元”。

如果还有多个软规则，可以把其违规量加入加权式，例如：

$$F_w=w_A\frac{{\ell }_A}{1\text{天}}+w_B\frac{{\ell }_B}{1\text{天}}+w_C\frac{C}{1\text{美元}}.$$

硬规则应作为定义 $X$ 的约束保留；只有业务明确授权的例外，才可以表示为软违规量。

3.6 字典序政策

按 $(L,C)$ 对两个最小化指标做字典序优化时，第一层得到：

$$L^{\ast }=0\text{天}.$$

只有 $A\to B$ 达到这个值，因此第二层没有剩余选择，结果为 $C=10\text{美元}$。因为成本是低优先级指标，8 美元的节省不能抵消一天违规。

在这个有限示例中，也可以用单个系数编码字典序。成本范围是 2 美元到 10 美元，最大差为 8 美元；延迟按整天变化，所以 $M=9$ 足够：

$$min9L+C.$$

两个方案的值分别为 $10$ 和 $11$。关键是这个推导：没有成本上界和延迟分辨率时，仅凭“系数看起来很大”不能证明它实现了字典序政策。

3.7 容差政策

假设公司在路线更便宜时接受总延迟最多一天。先优化第一层得到 $L^{\ast }=0$。给定业务容差 ${\epsilon }_L=1$ 天，第二层为：

$$minC\text{s.t.}L\le L^{\ast }+{\epsilon }_L=1\text{天}.$$

两行都允许，于是结果是 $B\to A$，成本为 $2\text{美元}$。如果 ${\epsilon }_L=0$ 天，则只剩下 $A\to B$。本例中 $0.25$ 天的容差也会选择 $A\to B$，因为可达延迟只有整数天。

业务容差不等同于求解器的数值可行性区间。报告应该写“在最佳延迟的一天范围内接受”，而不只是写“在容差内”。

4. 在 OSPF 中组织目标语义

OSPF 模型可以用以下概念角色保持多目标政策的显式性：

1. 领域上下文定义配送决策与硬可行性规则。
2. 违规上下文计算带单位的非负量，如延迟、拒绝数量或加班时间。这些是语义中间值，而不是某条内部行的任意残差。
3. 目标上下文声明每个目标的名称、方向、单位、归一化参考、优先级层次和业务容差。
4. 编译边界根据声明的向量和政策选择加权目标、分阶段字典序求解或其他受支持的表示，同时保留目标语义。
5. 结果上下文记录每个目标分量、每个优先级层的最优值或界、使用过的容差以及最终的硬／软状态。

编译器架构 说明为什么目标政策应在转换成求解器机制后仍然存在。求解结果 说明为什么多目标结果不能只保留一个标量分数：用户需要每个分量及每一层的状态。临界约束分析 可以针对一个明确目标分析瓶颈，同时说明其他目标层是被固定、按字典序保留，还是允许权衡。

这里的组织是概念性的，不假定某个当前公共类、工厂或后端能力。

5. 常见陷阱

5.1 相加不同单位的量

当 $L$ 以天计、$C$ 以美元计时，表达式 $L+C$ 没有自然含义。应归一化每个分量，或声明诸如“一天价值 9 美元”的换算率。目标定义应同时保存单位和尺度。

5.2 用权重替代优先级规则

今天数据上有效的权重，可能在成本、容量或边界变化后失效。如果政策是“绝不牺牲服务水平”，应使用字典序层，或使用由上界与分辨率推导出的可证明支配系数。没有推导时，不要把单纯的大系数称为字典序。

5.3 意外地把硬规则变成罚分

订单必须服务、安全限制或法律约束应属于 $X$。给它一个很大的罚分，仍然允许在另一个目标足够有利时违反。如果业务存在受控例外，应显式建模该例外，并作为独立软违规量报告。

5.4 只给违规变量下界

像 ${\ell }_i\ge d_i-{\tau }_i$ 和 ${\ell }_i\ge 0$ 这样的行，只描述下包络。只有当目标或等式把 ${\ell }_i$ 压到最小时，它才等于预期违规量；否则模型可能返回被放大的违规量，报告也会失真。

5.5 用加权系数模拟优先级时忽略范围

在 $M{f}_1+f_2$ 中，$M$ 必须保证 $f_1$ 的一次可达改善能够压过 $f_2$ 的全部可能变化。如果第二目标无界，或者连续第一目标存在任意小的改善，任何随意选取的有限 $M$ 都不能证明字典序行为。

5.6 混淆业务容差与数值容差

一天的可接受范围和 ${10}^{-8}$ 的可行性容差回答的是不同问题。业务容差改变可接受方案的集合；数值容差描述求解器如何解释计算残差。二者应分开记录，并注明单位和方向。

5.7 只报告标量分数

两个方案可能有相同的加权分数，却有完全不同的延迟与成本。结果应包含目标向量、归一化分量、权重或优先级顺序、容差以及硬可行性状态。如果某一层没有证明最优，就应明确写出，而不是把 incumbent 标量呈现为已认证的政策最优值。

6. 相关页面

• 临界约束分析
• 不等式指示函数
• Slack
• 绝对值
• Maximum
• 求解结果
• 编译器架构
• 运筹学语言
• 建模工作流
• 符号表达式
• 滚动优化
• 不可行性分析
• 场景分析