整数规划分支定界法

Matlab课后作业2年级：2008级专业：经济数学学号：40826116姓名：吴德华一、编程利用Matlab的线性规划指令：[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)编写计算整数规划函数，输入与输出与上述指令相同分枝定界法（递归实现）function[x,fval,status]=intprog(f,A,B,I,Aeq,Beq,lb,ub,e)%整数规划求解函数intprog()%其中f为目标函数向量%A和B为不等式约束Aeq与Beq为等式约束%I为整数约束%lb与ub分别为变量下界与上界%x为最优解，fval为最优值%例子:%maximize20x1+10x2%S.T.%5x1+4x2=24%2x1+5x2=13%x1,x2=0%x1,x2是整数%f=[-20,-10];%A=[54;25];%B=[24;13];%lb=[00];%ub=[infinf];%I=[1,2];%e=0.000001;%[xvs]=IP(f,A,B,I,[],[],lb,ub,,e)%x=41v=-90.0000s=1%控制输入参数ifnargin9,e=0.00001;ifnargin8,ub=[];ifnargin7,lb=[];ifnargin6,Beq=[];ifnargin5,Aeq=[];ifnargin4,I=[1:length(f)];end,end,end,end,end,end%求解整数规划对应的线性规划,判断是否有解options=optimset('display','off');[x0,fval0,exitflag]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);ifexitflag0disp('没有合适整数解');x=x0;fval=fval0;status=exitflag;return;else%采用分支定界法求解bound=inf;[x,fval,status]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);end子函数function[newx,newfval,status,newbound]=branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e)%分支定界法求解整数规划%f,A,B,Aeq,Beq,lb,ub与线性规划相同%I为整数限制变量的向量%x为初始解，fval为初始值options=optimset('display','off');[x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);%递归中的最终退出条件%无解或者解比现有上界大则返回原解ifstatus0=0||fval0=boundnewx=x;newfval=fval;newbound=bound;status=status0;return;end%是否为整数解,如果是整数解则返回intindex=find(abs(x0(I)-round(x0(I)))e);ifisempty(intindex)newx(I)=round(x0(I));newfval=fval0;newbound=fval0;status=1;return;end%当有非整可行解时，则进行分支求解%此时必定会有整数解或空解%找到第一个不满足整数要求的变量n=I(intindex(1));addA=zeros(1,length(f));addA(n)=1;%构造第一个分支x=floor(x(n))A=[A;addA];B=[B,floor(x(n))];[x1,fval1,status1,bound1]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第一个分支，若为更优解则替换，若不是则保持原状status=status1;ifstatus10&&bound1boundnewx=x1;newfval=fval1;bound=fval1;newbound=bound1;elsenewx=x0;newfval=fval0;newbound=bound;end%构造第二分支A=[A;-addA];B=[B,-ceil(x(n))];[x2,fval2,status2,bound2]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第二分支，并与第一分支做比较，如果更优则替换ifstatus20&&bound2boundstatus=status2;newx=x2;newfval=fval2;newbound=bound2;end二、求解利用上述指令求解下列问题：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量小型中型大型现有量钢材（吨）1251000劳动时间（小时）250125150120000利润（万元）35121、若每月生产的汽车必须为整车，试制订月生产计划，使工厂的利润最大2、如果生产某一类型汽车，则至少要生产50辆，那么最优的生产计划应作何改变？解：1f=[-3-5-12];A=[125;250125150];B=[1000120000];I=[1:length(f)];lb=[000];[x,fval,status]=intprog(f,A,B,I,[],[],lb)答案为x=3073441fval=-2653status=12lb=[505050]答案为x=35020050fval=-2.6500e+003status=1