Question

整数规划

Answer 1

即利用线性规划求解之后，分别添加其整数解周围的判断，如x=3.25时，分别添加x>=4或者x<=3,如果有相应的整数解，那就记录下来，在所有的决策变量都进行定界的操作后，就可以获取最适合的值。
例子
maximize 20 x1 + 10 x2
S.T.
5 x1 + 4 x2 <=24
2 x1 + 5 x2 <=13
x1, x2 >=0
x1, x2是整数

如果松弛问题无解，则该整数规划无解
如果P的最优解为整数向量，那么他也是P的最优解
如果P的解含有非整数变量，那就增加个平面条件：增加一个线性约束，将其可行区域割掉一块，使得非整数解恰好在割掉的一块中，但有没有割掉他原来的可行解，然后重复上述步骤

松弛变量的引入
如x+y<=1,通过引入松弛变量z，变为x+y+z=1,同时z>=0.有几个不等式就有几个松弛变量。引入了松弛变量后就可以利用割平面算法来进行最优解的计算

也是以内0-1变量，根据相应的系数矩阵来列出解，然后用各列系数相加等于1来得到相应的数学模型

得到稀疏矩阵后，可以直接利用变成来进行计算，计算过程较为复杂。