优化 ｜ 线性规划和整数规划的若干建模技巧
编者按
大家在对实际问题按照线性规划建模时，有没有因为一些特殊的变量或者约束而束手无策。例如目标函数是个求最大最小值问题，变量带绝对值符号，约束条件只能二选一。这篇文章介绍的建模技巧，让你轻松地将上述棘手难题转换为线性规划问题。
文章申明
文章作者：liuao0910(运筹学分享交流)
责任编辑：蓝
文章由『运筹OR帷幄』授权转载发布，如需转载请在公众号后台获取转载须知
1. 线性规划问题建模的重要性
现实生活中，有很多问题可以描述成优化问题，然后利用运筹优化的知识加以解决。它们通常遵循以下流程：
可以看出，比较核心的两个步骤是：建模(modeling)和求解(solve)。
对于现在有很多成熟的软件或者工具包，可以求解线性规划问题。比如，lingo, cplex, gurobi, glpk，lpsolve, scip，matlab optimization toolbox等。
实际问题成千上万万，它们的约束、目标等各不相同。如何对实际问题建模，并将它归结为一个线性规划问题，是应用线性规划求解问题时最重要，往往也是最困难的一步。问题建模是否合理，很大程度上会影响到后续的模型求解过程。
但是，受限于实际问题特征、建模经验、建模技巧等因素，我们在对问题建立初步模型之后，目标函数和约束条件往往包含一些特殊约束或者特殊变量：
- 含有绝对值。比如，LASSO回归是L1范数回归，目标函数包含绝对值
- 含有最大(最小)值。比如，风险决策涉及的最小机会损失准则( min-max)，也称最小最大后悔准则。
- 二选一约束。比如，同时生产两种产品A和B，产量分别为x和y，要么采用高负荷生产，满足2x+3y<=100，要么采用低负荷生产，x+y <=50。
- 其他特殊约束或变量。
对于上述含有特殊约束或者特殊变量的问题，尽管看起来不是线性规划问题，但是通过一些建模技巧，可以将它们转化成线性规划问题。
2. 含有绝对值的建模
比如，有如下规划问题：
为了将其转化为线性规划问题，引入两个新的非负向量u和v，满足以下条件：
上述规划问题就转化为如下线性规划问题：
3. 含有最大(最小)值的建模
比如，有如下规划问题：
为了将其转化为线性规划问题，引入新的变量u，满足以下条件：
上述规划问题就转化为如下线性规划问题：
4. 二选一约束的建模
比如，有如下约束：
该约束实际上是一个二选一约束，为了将其转换为线性约束。引入一个0-1变量z和一个充分大的数M(大M法):
5.多选多约束的建模
比如，有如下3个约束，要满足其中2个约束：
该约束实际上是一个3选2约束，为了将其转换为线性约束，引入3个0-1变量z和一个充分大的数M(大M法):
6. 固定成本约束的建模
在库存问题中，通常考虑订货的固定成本和可变成本。就是说，只要订货x>0，就有一个固定成本k，和可变成本cx，它的成本函数就是：
该约束实际上是一个二选一约束，为了将其转换为线性约束。引入一个0-1变量y和一个充分大的数M(大M法):
7. 分段线性函数的建模
比如，在现实生活中，购买商品的数量越多，它的单价会有折扣。在数学中，它的一个成本或者利润函数就可以表示成如下的分段线性函数：
对于分段线性函数，可以通过引入SOS2约束(a special order set (SOS) constraint of type 2)，将其转换为线性规划。以下是一种比较通用的建模技巧。
事实上，像CPLEX、LP_SOLVE等solver，已经支持直接对分段线性函数建模，不需要建模人员将其进行线性转换。
参考资料
[1]Special Ordered Sets (SOS)
http://lpsolve.sourceforge.net/5.1/SOS.htm
[2]Modeling piecewise linear functions
http://homepages.rpi.edu/~mitchj/handouts/ piecewise/
[3]Matlab随笔之分段线性函数化为线性规划
https://blog.csdn.net/weixin_34269583/article/details/86014299
[4]Piecewise Linearity in CPLEX
https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.1/ilog.odms.cplex.h
相关文章推荐
更多运筹学学习方法可参考如下文章：
点击蓝色标题，即可阅读《主编推荐 | 千里之行，始于足下，运筹学学习路线规划与入门法则精选》
其他
加入『运筹OR帷幄』知识星球的好处
- 中国你能说出名字的几乎所有大厂（资深）算法工程师入驻
- 欧美数家大厂（资深）软件工程师入驻
- 以上所有公司独家内推机会
- 简历修改指导
- 面试咨询， 模拟面试
- 得到一对一指导、解答工作中的疑惑
- 多家Offer选择指导
- 以面试题为学习资料学习真正的算法干货，从小白变成大咖
- 不定期的线上、线下交流会和聚会,拓展人脉。
欢迎关注『运筹OR帷幄』公众号
