本文主要是介绍线性化技巧：绝对值变量的线性化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 1. 问题
- 2. 线性化
- 3. 缺少 x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi−=0 有什么问题
- 4. 延伸思考
- 5. 参考文献
1. 问题
以方述诚老师课件中的案例为例：
m a x 3 x 1 − 2 x 2 − 4 ∣ x 3 ∣ s . t . − x 1 + 2 x 2 ≤ − 5 3 x 2 − x 3 ≥ 6 2 x 1 + x 3 = 12 x 1 , x 2 ≥ 0 max \quad 3x_1-2x_2-4\vert x_3 \vert \\ s.t. -x_1+2x_2 \leq -5 \\ 3x_2-x_3 \geq 6 \\ 2x_1 + x_3 = 12 \\ x_1,x_2 \geq 0 max3x1−2x2−4∣x3∣s.t.−x1+2x2≤−53x2−x3≥62x1+x3=12x1,x2≥0
x 3 x_3 x3是一个自由变量，且在目标函数中它是以绝对值的形式存在，如果我们要将该模型转化成标准型，首先要做的就是将 x 3 x_3 x3线性化。
2. 线性化
对于每一个数字 x x x，我们都可以将它拆成正的个数 x + x^+ x+和负的个数 x − x^- x−，并将其表示为 x + − x − x^+ - x^- x+−x−（正的个数 - 负的个数），举个例子：
- 5：正的个数是5，负的个数是0，5-0=5；
- -5：正的个数是0，负的个数是5，0-5=-5。
直觉上十分合理对吧（intuition是方老师第一节课反复强调的重点），我们用数学表达式来表达上述思想。
x i ∈ R x_i \in R xi∈R
x i + = { x i , i f x i ≥ 0 0 , o t h e r w i s e x_i^+ = \begin{cases} x_i, \quad if \quad x_i \geq 0 \\ 0, otherwise \end{cases} xi+={xi,ifxi≥00,otherwise
x i − = { 0 , i f x i ≥ 0 − x i , o t h e r w i s e x_i^- = \begin{cases} 0, \quad if \quad x_i \geq 0 \\ -x_i, otherwise \end{cases} xi−={0,ifxi≥0−xi,otherwise
x i = x i + − x i − x_i = x_i^+ - x_i^- xi=xi+−xi−
x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi−=0
（很多教材和文章里直接省去了这个约束，其实是不对的，待会儿后面讲。）
x i + , x i − ≥ 0 x_i^+, x_i^- \geq 0 xi+,xi−≥0
3. 缺少 x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi−=0 有什么问题
x i + × x i − = 0 x_i^+ \times x_i^- = 0 xi+×xi−=0 该约束本质保证的是 x i + x_i^+ xi+ 和 x i − x_i^- xi− 至少有一个为0，如果没有该约束，5除了表示为5-0以外，还可以表示为6-1、7-2等等。也就是会使得原来只有一个解的问题，变成具有很多个新的解的问题。
4. 延伸思考
上述问题中的 ∣ x ∣ \vert x \vert ∣x∣是一个“V”字型的凸函数，它可以求极小值。如果要求 m a x ∣ x ∣ max \vert x \vert max∣x∣ 那就unbounded了。
5. 参考文献
- Linear Programming
这篇关于线性化技巧：绝对值变量的线性化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
