建模打卡第二天，整数规划问题

本文主要是介绍建模打卡第二天，整数规划问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

先忽略最后x1,x2为整数的条件，求解x1,x2的值

clc;
clear all;
c=[40 90];

a=[9 7;7 20];
b=[56 70];

aeq=[];
beq=[];

lb=[0;0];
ub=[inf;inf];

[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

 求解答案为：

 x1,x2=0时，Z=0；可以知道Z的范围是0<=Z<=356，再对x1和x2任意一个进行分支；

B1问题，先对x进行分支，把x1分为两个子集：x1<=[4.8092]=4,x1>[4.8092]+1=5;

川川给我们求了x1在0到4范围内的分支，现在我来求x>=5的分支；

代码如下：

clc;
clear all;
c=[40 90];

a=[9 7;7 20];
b=[56 70];

aeq=[];
beq=[];

lb=[5;0];                   %x1的下限为5，上限为无穷
ub=[inf;inf];

[x,fval]=linprog(-c,a,b,aeq,beq,lb,ub);
x
best=c*x

 运行的结果为:

 接下来是对B1问题再进行分支，B1中只有x2是小数，对x2进行分支，x2的两个子集为:

0<=x2<=[2.1]=2;x2>=[2.1]+1=3;

同样的，川川写了0<=x2<=[2.1]的分支，我写x2>=[2.1]+1=3的分支，代码如下：

clc;
clear all
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
best=c*x

运行结果为：

 接下来对B2问题进行分支，B2问题为:

对X2进行分支，0<=x2<=[1.5714]=1,x2>=[1.5714]+1=2;得到的问题B21为：

 目标函数：Max z = 40*x1 + 90*x2

约束条件为：

9*x1+7*x2<=56
7*x1+20*x2<=70
x1>=5  1>x2>0

计算代码如下

clc;
clear all
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
best=c*x

运行结果为：

 再取x2>=2取分支，代码为：

clc;
clear all
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
best=c*x

运行结果为：

 运行为无解；

通过分支，所有问题的解分别为：

B1：

 B2：

 B11：

B12：

B21

B22： 

从所有的解里我们可以看到，只有B11符合我们的要求，有小数的，无解的 ，都不可取，这个叫做剪枝，通过这一系列分支剪支，求出最优解，最后总结：

将要求的整数规划问题设为A，相应的线性规划问题为B，其中：

1、若 B没有可行解，A也没有可行解，则停止，即该整数规划无解。

2、若B有最优解，且符合A的整数条件，则B的最优解即为A的最优解。

3、若B有最优解，但不符合A的整数条件，通过分枝，剪支，求出最优解。

最后，还是感谢川川带大家学习，在这段时间就坚持下去好好学，以上也是我自己的理解，有很多不足的地方还需改进。

这篇关于建模打卡第二天，整数规划问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！