整数规划Matlab-课件【PPT演示稿】.ppt

例:用分枝定界法求解整数规划问题(用图解法计算) ?????????????????且全为整数 0, 4 30 65 2 5 min 21 1 21 21 21xx x xx xx xxZ记为( IP) 解:首先去掉整数约束,变成一般线性规划问题(原整数规划问题的松驰问题) ?????????????????0, 4 30 65 2 5 min 21 1 21 21 21xx x xx xx xxZ记为( LP ) f=[-1 -5]; a=[-1 1;5 6;1 0]; b=[2 30 4]'; lb=[0 0]'; [x, fv]= linprog(f,a,b,[],[],lb ) % x1 =, x2=, fv = - function [a1,a2,b1,b2]=intp(k,n,a,b,p) % k为分支变量的编号,n为矩阵 a的列数,p是要分支变量值 d1=zeros(1,n); d1(k)=1; d2=d1; d2(k)=-1; a1=[a;d1] a2=[a;d2] c=fix(x) b1=[b;c] b2=[b;-1-c] 对于 x 1= 18/11 ≈ , 取值 x 1≤1,x 1≥2将( LP )划分为( LP1 ) 和( LP2 ). 用图解法求( LP )的最优解,如图所示。 x 1 x 2⑴⑵ 3 (18/11,40/11) ⑶ x 1= 18/11, x 2 =40/11 Z (0) =- 218/11 ≈(-) 21123 有下式: 1 2 1 2 1 2 11 1 2 min 5 2 5 6 30 ( 1) 4 1 , 0 ???? ????? ??????????? Z x x x x x x P x x x x 且为整数 1 2 1 2 1 2 11 1 2 min 5 2 5 6 30 ( 2) 4 2 , 0 ???? ????? ??????????? Z x x x x x x P x x x x 且为整数现在只要求出( P1 )和( P2 )的最优解即可。 p=x(1) %取x1 分枝,x1 ≤1,x1 ≥2 [a1,a2,b1,b2]=intp(1,2,a,b,p) % 形成分支后的约束矩阵. [x1,fv1,e1]=linprog(f,a1,b1,[],[],lb) %x1 =(1, 3), fv1 = -16, e1 = 1, 整数解不再分支. [x2,fv2,e2]=linprog(f,a2,b2,[],[],lb) % x2 = (2,10/3), fv2 = -<-16, e2 =1, 继续分支 x 1 x 2⑴⑵ 33 (18/11,40/11) ⑶先求( P1 ),如图所示。此时在 B点取得最优解。 x 1=1, x 2 =3, Z (1)=-16( 上界)找到整数解,问题已探明, 此枝停止计算。 1 1 同理求( P2 ),如图所示。在C点取得最优解。即x 1=2, x 2 =10/3, Z (2)=- 56/3 ≈- ∵Z 2 < Z 1=- 16∴原问题有比( -16) 更小的最优解,但 x 2 不是整数,故继续分支。 B AC -16 . 加入条件: x 2≤3, x 2≥4 有下式: 1 2 1 2 1 2 112 1 2 min 5 2 5 6 30 4 ( 3) 2 3 , 0 ???? ????? ?????????????? Z x x x x x x xPxx x x 且为整数 1 2 1 2 1 2 112 1 2 min 5 2 5 6 30 4 ( 4) 2