典型运筹优化问题

建模参考：https://docs.mosek.com/modeling-cookbook/linear.html#linear-modeling

1. 线性规划 LP

即约束条件和目标函数都是线性函数 y = ax + b

------非线性线性化----------

最大值

可以使用凸分段线性公式表达max函数

绝对值

最大值的特例

L1范式优化

原理及实现参考：https://blog.csdn.net/weixin_46584887/article/details/123958774
即：绝对值可以化作一般的线性规划问题
不等式数量远远小于变量，即方程欠定，存在无穷多个解，但真正有用的是“稀疏解”

最大值范式

最大值max｜xi｜,其实就是Max{-x1,x1,-x2,x2,……}然后约束中又是-1<=x1<=t……
最大值就是t
L1范式的对偶范式是l∞范式

分式-均质化

直接令z = 1/(ax+b)，如果令y=zx,其他约束有x变y，常数变z

最大元素之和

其中t和u是变量，解就是前xi前m大

分段函数线性化

http://www.tup.tsinghua.edu.cn/upload/books/yz/091090-01.pdf

  1. xi和y都是01变量，xi只要有1个大于0，则y=1；否则等于0
    x1+x2+……\geq y\\ x1+x2+……\leq My
  2. xi和y都是01变量，xi全部为1，则y=1；否则等于0
    x1+x2+……\geq sy\\ x1+x2+……\leq (s-1)(1-y) + My
    其中s是全部xi的和
  3. x是01变量，y是连续变量，如果x=0,y=0; x=1,y<=c.（x,y都>=0)
    y \leq c\\ y \leq mx
  4. x是01变量，y是连续变量，在2的基础上，如果x=0,y=0; x=1,y=c
    y \leq c\\ y \leq mx\\ y \geq -M(1-x)+c
  5. 异或问题
    问题：表达 x<=x1 或 x>=x2
    引入辅助变量 b={1,0}
    x \geq bx1\\\ y \leq (1-b)x2 + bM
    其中M是一个大值

  6. 最小值表示
    引入一个辅助变量y表示最小值，用y>=x和y<=x来获取y=x这样一个结果


    image.png

2. 混合整数规划 MIP

有整数变量的线性规划是MILP，有整数变量的非线性规划是MIQP等

3. 二次规划 QCP

gurobi 求解非线性规划：https://zhuanlan.zhihu.com/p/413706576?utm_id=0

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容