《matlab源代码:整数线性规划问题.doc》由会员分享,可在线阅读,更多相关《matlab源代码:整数线性规划问题.doc(8页珍藏版)》请在三一办公上搜索。
1、%本程序是用分枝定界法求解整数线性规划问题%问题的标准形式:% min c*x% s.t. A*x= UB) FN(1)=;if isempty(FN)=1 flag=1;elsek=FN(1);A=AAk;b=BBk;endelsefor i=1:NLif abs(x(i)-round(x(i)1e-7 kk=FN(end);FN=FN,kk+1,kk+2; temp_A=zeros(1,NL);temp_A(i)=1;temp_A1=A;temp_A;AA(kk+1)=temp_A1;b1=b;fix(x(i);BB(kk+1)=b1;temp_A2=A;-temp_A;AA(kk+2)=
2、temp_A2;b2=b;-(fix(x(i)+1);BB(kk+2)=b2;FN(1)=;k=FN(1);A=AAk;b=BBk;break; endendif (i=NL) & (abs(x(i)-round(x(i)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;en
3、d;m1=m1+1;m2=m2*2;for c=1:1:m2if (cell2mat(em1-1,c(1)=0)x1,val1=linprog(f,cell2mat(em1-1,c( 2),cell2mat(em1-1,c(3),cell2mat(em1-1,c(4),cell2mat(em1-1,c(5),cell2mat(em1-1,c(6),cell2mat(em1-1,c(7);e1=cell2mat(em1-1,c(1),cell2mat(em1-1,c(2),cell2mat(em1-1,c(3),cell2mat(em1-1,c(4),cell2mat(em1-1,c(5),cell2mat(em1-1,c(6),cell2mat(em1-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)(-zu)zu=cell2mat(em1-1,c(9);end;end;end;for c=1:1:m2if (cell2mat(em1-1,c(1)=0)&(cell2mat(em1-1,c(9)=zu)x=cell2mat(em1-1,c(8);end;end;val=zu;end;