Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
matlab求整数规划问题_matlab求解01整数规划,希望能够帮助你!!!。

目录

一、前言

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.0000

3.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.0000

3.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  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.在使用分枝定界法时，对每一个变量都要进行分枝操作，或者说在第一变量的基础上，对第二变量进行，依次分枝。

2.在判断结果时，一定要根据线性规划的最优解取值范围进行判断，否则超出范围都不可取。

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。