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

2023-11-13 21:11:04

先忽略最后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

运行结果为：