matlab取整数 |
您所在的位置：网站首页 › matlab中取整数 › matlab取整数 |
matlab取整数
|
目录 一、前言 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.问题
线性规划图 通过@川川菜鸟大佬的介绍，采用分支定界法求解整数规划问题的理解如下： 1.首先利用linprog函数求解整数规划问题对应的线性规划问题，得出的结论如下： 1.1若相应的线性规划的最优解为整数，则对于相应的整数规划也是最优解。 1.2若相应的线性规划的最优解为小数，则对相应的变量进行单变量的子集划分，采用分支定界法进行下一步的linprog求解，比如说有2个变量，则对变量需进行4次分支，然后相应的进行剪枝操作，对比求出最优解。 1.3若相应的线性规划无解，则相应的整数规划也无解。 三、Matlab求解整数规划（分枝定界法）分枝定界法是对线性规划后的最优解进行一个范围的划分，也就是说首先对最优解的变量x1进行范围的划分。利用取整函数对变量范围进行划分，分别在各自的定义域内求解目标函数。 由上述线性规划的解可以得知，z=355.8779，可以得知，z的取值范围为[0,356]，因为上述x1,x2都不是整数，所以采用分枝定界法进行划分，将自变量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 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.在使用分枝定界法时，对每一个变量都要进行分枝操作，或者说在第一变量的基础上，对第二变量进行，依次分枝。 2.在判断结果时，一定要根据线性规划的最优解取值范围进行判断，否则超出范围都不可取。 |
【本文地址】