一、线性规划

image.png

二、整数规划

原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
③有可行解（当然就存在最优解），但最优解值变差。

分枝定界法
一般地，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， 这样，许多子集可不予考虑，这称剪枝。

重点：0-1规划
0-1 变量可以描述开关、取舍、有无等逻辑关系、顺序关系，可以处理背包问题、指派问题、选址问题 、计划安排、线路设计 、人员安排等各种决策规划问题。进而，任何整数都可以用二进制表达，整数变量就可以表示为多个 0-1 变量的组合，因此任何整数规划都可以转化为 0-1 规划问题来处理。
在数学建模中，0-1 规划主要用于求解互斥的决策问题、互斥的约束条件问题、固定费用问题和分派问题。
讲解及python实现：
https://zhuanlan.zhihu.com/p/378283709

https://blog.csdn.net/weixin_45508265/article/details/112978882?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-1.pc_relevant_aa&spm=1001.2101.3001.4242.2&utm_relevant_index=4

三、非线性规划

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。

Python 解决非线性规划
非线性规划可以简单分两种，目标函数为凸函数or非凸函数
（1）凸函数的非线性规划，有很多常用库完成，比如cvxpy
（2）非凸函数的非线性规划(求极值)，可以尝试以下方法:
①纯数学方法，求导求极值
②神经网络、深度学习(反向传播算法中链式求导过程)
python函数：

  1. scipy . optimize .minimize (fun, x0, args= (), method=None, jaC=None, hess=None,
  2.      hessp=None, bounds=None, constaints= (), tol =None, callback=None, options=None)

fun:求最小值的目标函数
args:常数值
method:求极值方法，一般默认。
constraints:约束条件
x0:变量的初始猜测值，注意minimize是局部最优