如何将最小化加权绝对值和的优化问题转化为线性规划？

步骤1：引入辅助变量线性化绝对值项 #

对每个$i \in {1,2,...,n}$，定义两个非负辅助变量$u_i \geq 0$和$v_i \geq 0$，满足：
$$w_i - a_i = u_i - v_i$$
此时绝对值项可以表示为：
$$|w_i - a_i| = u_i + v_i$$
这个转换的核心逻辑是：$u_i$对应$w_i - a_i$的正部，$v_i$对应其负部，两者的和恰好等于绝对值，差等于原差值。

步骤2：重构目标函数 #

将原目标函数$\min \sum_{i=1}^n b_i |w_i - a_i|$替换为：
$$\min \sum_{i=1}^n b_i (u_i + v_i)$$
无论$b_i$为正或负，这个目标函数都是关于变量$u_i, v_i, w_i$的线性表达式，符合线性规划的要求。

步骤3：转换约束条件 #

原约束$\sum_{i=1}^n c_i w_i = 0$，结合$w_i = a_i + u_i - v_i$，代入后得到线性约束：
$$\sum_{i=1}^n c_i (a_i + u_i - v_i) = 0$$
整理后为：
$$\sum_{i=1}^n c_i u_i - \sum_{i=1}^n c_i v_i = -\sum_{i=1}^n c_i a_i$$

步骤4：补充变量非负约束 #

所有辅助变量必须满足非负性：
$$u_i \geq 0, \quad v_i \geq 0 \quad (i=1,2,...,n)$$
（注：$w_i$本身无额外非负约束，原问题未提及相关限制）

最终线性规划模型 #

综合以上步骤，完整的线性规划模型为：
$$
\begin{align*}
\min \quad & \sum_{i=1}^n b_i (u_i + v_i) \
\text{s.t.} \quad & \sum_{i=1}^n c_i (a_i + u_i - v_i) = 0 \
& w_i - a_i = u_i - v_i \quad (i=1,2,...,n) \
& u_i \geq 0, , v_i \geq 0 \quad (i=1,2,...,n)
\end{align*}
$$
若希望消去$w_i$变量，直接将$w_i = a_i + u_i - v_i$代入约束，模型可简化为仅包含$u_i$和$v_i$的形式：
$$
\begin{align*}
\min \quad & \sum_{i=1}^n b_i (u_i + v_i) \
\text{s.t.} \quad & \sum_{i=1}^n c_i u_i - \sum_{i=1}^n c_i v_i = -\sum_{i=1}^n c_i a_i \
& u_i \geq 0, , v_i \geq 0 \quad (i=1,2,...,n)
\end{align*}
$$

内容的提问来源于stack exchange，提问作者Pique