matlab整数规划程序

可以用YALMIP工具箱解整数规划

定义变量：

sqdvar（）实型

intvar（）整型

binvar（）0-1型

设定目标函数 :

f=目标函数

设定限定条件：

F=set（限定条件）

多个限定条件用加号相连：

F=set（限定条件）+set（限定条件1）+set（限定条件2）……

求解： solvesdp（F,f）

这里解得是F条件下目标函数f的最小值，要求最大值f前面加个负号

求解之后查看数值 :

double（f） double（变量）

intvar（m，n）:生成整数型变量；

sdpvar（m，n）：生产变量；

solvesdp（F，f）：求解最优解（最小值），其中F为约束条件（用set连接），f为目标函数

double：显示求解的答案

有个例子：

已知非线性整数规划为：

Max z=x1^2+x2^2+3*x3^2+4*x4^2+2*x5^2-8*x1-2*x2-3*x3-x4-2*x5

s.t.

0<=xi<=99(i=1,2,...,5)

x1+x2+x3+x4+x5<=400

x1+2*x2+2*x3+x4+6*x5<=800

2*x1+x2+6*x3<=800

x3+x4+5*x5<=200

matlab中输入

>>x=intvar(1,5)

f=[1 1 3 4 2]*(x'.^2)-[8 2 3 1 2]*x'F=set(0<=x<=99)

F=F+set([1 1 1 1 1]*x'<=400)+set([1 2 2 1 6]*x'<=800)+set(2*x(1)+x(2)+6*x(3)<=800)

F=F+set(x(3)+x(4)+5*x(5)<=200)solvesdp(F,-f)

max=double(f)

sx=double(x)

* Starting YALMIP integer branch &bound.

* Lower solver : fmincon-standard

* Upper solver : rounder

* Max iterations : 300

Warning : The relaxed problem may be nonconvex. This means

that the branching process not is guaranteed to find a

globally optimal solution, since the lower bound can be

invalid. Hence, do not trust the bound or the gap...

Node Upper Gap(%) LowerOpen

1 : -8.020E+004 0.03-8.025E+004 2

2 : -8.020E+004 0.03-8.025E+004 1

3 : -8.020E+004 0.00-8.020E+004 2

+ 3 Finishing. Cost: -80199

max =

80199

sx =

53999999 0

将下面函数fzdj保存为fzdj.m文件。

function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub)

x=zeros(n,1)

x1=zeros(n,1)

m1=2

m2=1

[x1,val1]=linprog(f,a,b,aeq,beq,lb,ub)

if (x1==0)

x=x1

val=val1

elseif (round(x1)==x1)

x=x1

val=val1

else

e1={0,a,b,aeq,beq,lb,ub,x1,val1}

e(1,1)={e1}

zl=0

zu=-val1

while (zu~=zl)

for c=1:1:m2

if (m1~=2)

if (cell2mat(e{m1-1,c}(1))==1)

e1={1,[],[],[],[],[],[],[],0}

e(m1,c*2-1)={e1}

e(m1,c*2)={e1}

continue

end

end

x1=cell2mat(e{m1-1,c}(8))

x2=zeros(n,1)

s=0

s1=1

s2=1

lb1=cell2mat(e{m1-1,c}(6))

ub1=cell2mat(e{m1-1,c}(7))

lb2=cell2mat(e{m1-1,c}(6))

ub2=cell2mat(e{m1-1,c}(7))

for d=1:1:n

if (abs((round(x1(d))-x1(d)))>0.0001)&&(s==0)

s=1

lb1(d)=fix(x1(d))+1

if (a*lb1<=b)

s1=0

end

ub2(d)=fix(x1(d))

if (a*lb2<=b)

s2=0

end

end

end

e1={s1,a,b,aeq,beq,lb1,ub1,[],0}

e2={s2,a,b,aeq,beq,lb2,ub2,[],0}

e(m1,c*2-1)={e1}

e(m1,c*2)={e2}

end

m1=m1+1

m2=m2*2

for c=1:1:m2

if (cell2mat(e{m1-1,c}(1))==0)

[x1,val1]=linprog(f,cell2mat(e{m1-1,c}(2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)))

e1={cell2mat(e{m1-1,c}(1)),cell2mat(e{m1-1,c}(2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)),x1,val1}

e(m1-1,c)={e1}

end

z=val1

if ((-z)<(-zl))

e1={1,[],[],[],[],[],[],[],0}

e(m1-1,c)={e1}

elseif (abs(round(x1)-x1)<=0.0001)

zl=z

end

end

for c=1:1:m2

if (cell2mat(e{m1-1,c}(1))==0)

zu=cell2mat(e{m1-1,c}(9))

end

end

for c=1:1:m2

if (-cell2mat(e{m1-1,c}(9))>(-zu))

zu=cell2mat(e{m1-1,c}(9))

end

end

end

for c=1:1:m2

if (cell2mat(e{m1-1,c}(1))==0)&&(cell2mat(e{m1-1,c}(9))==zu)

x=cell2mat(e{m1-1,c}(8))

end

end

val=zu

end

然后在命令窗口中输入：

n=2f=[0-1]%转化为求最小

a=[3 2-3 2]

b=[60]

lb=[00]

ub=[inf,inf]

aeq=[]

beq=[]

[x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub)

结果：

x =

1

1

val =

-1

即在点（1,1）最大为1

1、求解整数规划问题并不是MATLAB的强项，如果不是有要求必需要用MATLAB，可以考虑使用Lingo求解，求解速度快，程序也很简单：

max=120*x1+560*x2

0.6*x1+(1+0.5*x2)*x2=300

x1>=0

x2>=0

@GIN(x1)@GIN(x2)

end

得到的结果是x1=500，x2=0。

2、用MATLAB求解整数规划，官方好像并没有提供有效的手段（仅有一个用于求解0-1规划问题的bintprog函数）。我知道的有两个第三方函数：

一个是bnb20，是十几年前编写的，现在用的话需要做一些改动。而且对非线性约束的处理似乎有问题，我使用它求解并未得到正确答案。

另一个是lpsolve，其实是用C语言编的，提供了MATLAB的调用接口而已。由于调用动态链接库涉及到32位/64位的问题，配置起来比较麻烦，似乎没必要用它而不是Lingo。

3、就本题而言，由于变量少，问题规模不大，可以采用穷举法。听起来穷举法似乎是一种比较笨的方法，但其实对于一些简单问题来说却最为直接有效。

由于x1, x2>=0，又存在一个等式约束，不难得到，满足约束的x2最大值为23.5153，考虑到整数约束，x2的取值其实只有一共24种可能（0-23）；再考虑到等式约束，计算出的x2满足整数要求的仅有8个数而已。在8个数里面选一个最大的，应该不是难事吧？

参考代码：

ezplot('0.6*x1+(1+0.5*x2)*x2-300',[0 500 0 24])

hold on

x2 = 0:23

x1 = ( 300 - (1+0.5*x2).*x2) / 0.6

valid = abs(x1-fix(x1)) <= eps

x1 = x1(valid)

x2 = x2(valid)

z = 120*x1+560*x2

[inx,inx] = max(z)

[x1(inx) x2(inx)]

scatter(x1,x2,40,z,'filled')

colorbar

得到结果与用Lingo求解一致。

---