用matlab编程解决整数规划

将下渣锋面函数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求解一致。

---