matlab求整数规划问题_matlab求解01整数规划

(4) 2024-07-05 12:12

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.问题

matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第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

线性规划图

 matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第2张

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划分为两个定义域进行求解。

matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第3张

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

可以发现,最大值超出线性规划范围,不可取。采取剪枝操作。

因此,最优解为:

 matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第4张

matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第5张

matlab求整数规划问题_matlab求解01整数规划_https://bianchenghao6.com/blog__第6张

四、结论

1.在使用分枝定界法时,对每一个变量都要进行分枝操作,或者说在第一变量的基础上,对第二变量进行,依次分枝。

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

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

上一篇

已是最后文章

下一篇

已是最新文章

发表回复