如何通过约束将含max函数的目标转化为线性规划问题

你可以通过引入辅助变量的方式完成转换，具体操作如下：

• 第一步：引入新的辅助变量 t，新增两条约束条件让t大于等于max函数的两个输入项：
  • t ≥ 0
  • t ≥ x - 10
• 第二步：把原目标函数里的max(0, x-10)替换为t，得到新的线性目标函数。

转换有效性说明 #

因为原目标是最小化表达式，优化器会自动在满足约束的前提下把t压缩到最小可行值，这个最小值刚好和max(0, x-10)的计算结果完全一致：

• 当x ≥ 10时，x-10 ≥ 0，此时t的最小可行值就是x-10，和max输出一致
• 当x < 10时，x-10 < 0，此时t的最小可行值就是0，也和max输出一致

最终标准线性规划形式 #

目标函数：

minimize 1000 + 3*t

约束条件：

t ≥ x - 10
t ≥ 0

如果你的问题本身对x有非负要求，可以额外添加约束x ≥ 0，无特殊要求的话x可以取任意实数值。

内容的提问来源于stack exchange，提问作者J. Doe