目录
一、前言
1.问题
2.Matlab求解以及线性规划图
3.运行结果
二、整数规划问题求解
三、Matlab求解整数规划（分枝定界法）
3.1Matlab（对变量x1的分枝）的求解
3.2（对变量x1的分枝）运行结果
3.3Matlab（对变量x1的分枝）的求解2
3.4（对变量x1的分枝）运行结果2
3.5.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解
3.5.2（对变量x2的分枝）运行结果
3.6.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解2
3.6.2（对变量x2的分枝）运行结果2
3.7.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解3
3.7.2（对变量x2的分枝）运行结果3
3.8.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解4
3.8.2（对变量x2的分枝）运行结果4
四、结论
一、前言
对于线性规划，整数规划与之相比，只不过增加了相应的限制条件。即变量必须为整数。首先对于整数规划问题，应用线性规划有（来源：川川菜鸟）
1.问题
2.Matlab求解以及线性规划图
clear
c=[40,90]; %目标函数的系数矩阵
a=[9 7;7 20]; %约束条件的系数矩阵
b=[56;70]; %约束条件的右端项列向量
aeq=[]; %约束条件中无等式
beq=[]; %约束条件中无等式
lb=[0;0]; %变量的下界为0
ub=[inf;inf]; %变量无上界
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub); %linprog求解线性规划问题的最优解x1和x2
Optimization terminated.
x
abs(fval) %目标函数的最优值
maxz=c*x线性规划图
3.运行结果
>>x
x =
4.8092
1.8168
>> abs(fval)
ans =
355.8779
>> maxz=c*x
maxz =
355.8779二、整数规划问题求解
通过@川川菜鸟大佬的介绍，采用分支定界法求解整数规划问题的理解如下：
1.首先利用linprog函数求解整数规划问题对应的线性规划问题，得出的结论如下：
1.1若相应的线性规划的最优解为整数，则对于相应的整数规划也是最优解。
1.2若相应的线性规划的最优解为小数，则对相应的变量进行单变量的子集划分，采用分支定界法进行下一步的linprog求解，比如说有2个变量，则对变量需进行4次分支，然后相应的进行剪枝操作，对比求出最优解。
1.3若相应的线性规划无解，则相应的整数规划也无解。
三、Matlab求解整数规划（分枝定界法）
分枝定界法是对线性规划后的最优解进行一个范围的划分，也就是说首先对最优解的变量x1进行范围的划分。利用取整函数对变量范围进行划分，分别在各自的定义域内求解目标函数。
由上述线性规划的解可以得知，z=355.8779，可以得知，z的取值范围为[0,356]，因为上述x1,x2都不是整数，所以采用分枝定界法进行划分，将自变量x1划分为两个定义域进行求解。
3.1Matlab（对变量x1的分枝）的求解
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[0;0];ub=[4;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.2（对变量x1的分枝）运行结果
对第一个区域进行约束，得到的最优化取值为x1=4.0000,x2=2.1000,最优化的最大值为349.0000.
x =
4.0000
2.1000
maxz =
349.00003.3Matlab（对变量x1的分枝）的求解2
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[5;0];ub=[inf;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.4（对变量x1的分枝）运行结果2
x =
5.0000
1.5714
maxz =
341.4286结果分析：在对x1自变量进行分枝时，在[0,4]和[5,inf]中，可以看到当在[0,4]中，可以看到，当x1=4,x2=2.1时，取得最大值maxz=349。在[5,inf]此区域内，可以看到，当x1=5，x2=1.5714时，取得最大值341.4286.但因为x2是小数，并不能判别到底是在第一区域内取最大值，还是第二区域内取最大值，所以对两区域内的x2变量进行分枝。
3.5.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解
对x1的第一个范围[0,4]内对x2取整后划分范围为[0,2]和[3,inf]，继续进行分支定界法。
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[0;0];ub=[4;2];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.5.2（对变量x2的分枝）运行结果
x =
4.0000
2.0000
maxz =
340.00003.6.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解2
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[0;3];ub=[4;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.6.2（对变量x2的分枝）运行结果2
x =
1.4286
3.0000
maxz =
327.1429由此，可以确定的最大值的范围为[0,340].
3.7.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解3
对x1的第二个范围[5,inf]内对x2取整后划分范围为[0,1]和[2,inf]，继续进行分支定界法。
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[5;0];ub=[inf;1];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.7.2（对变量x2的分枝）运行结果3
x =
5.4444
1.0000
maxz =
307.7778因为自变量中仍然有小数部分，不符合整数规划的要求，所以舍去。
3.8.1Matlab（在变量x1的基础上，对变量x2的分枝）的求解4
clear
c=[40,90];
a=[9,7;7,20];
b=[56;70];
aeq=[];beq=[];
lb=[5;2];ub=[inf;inf];
[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
maxz=abs(fval)3.8.2（对变量x2的分枝）运行结果4
Exiting: One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far:
the primal appears to be infeasible (and the dual unbounded).
(The dual residual < OptimalityTolerance=1.00e-08.)
x =
5.0000
2.0000
maxz =
380.0000可以发现，最大值超出线性规划范围，不可取。采取剪枝操作。
因此，最优解为：
四、结论
1.在使用分枝定界法时，对每一个变量都要进行分枝操作，或者说在第一变量的基础上，对第二变量进行，依次分枝。文章来源：https://www.toymoban.com/news/detail-467039.html
2.在判断结果时，一定要根据线性规划的最优解取值范围进行判断，否则超出范围都不可取。文章来源地址https://www.toymoban.com/news/detail-467039.html
到了这里，关于Matlab求整数规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
