b=400,800,200,200; enddata max=@sum(col: Cl*x2+C2*x)i @for(row(i): sum(col(]):a(i,j)*x(3))<b(1)) @for(col: @gin(x)) @for(col: @bnd(0,x,99))i §5指派问题的计算机求解 整数规划问题的求解可以使用 Lingo等专用软件。对于一般的整数规划问题,无法 直接利用 Matlab的函数,必须利用 Matlab编程实现分枝定界解法和割平面解法。但对 于指派问题等0-1整数规划问题,可以直接利用 Matlab的函数 bintprog进行求解。 例8求解下列指派问题,已知指派矩阵为 222 375 103 87297 84235 解:编写 Matlab程序如下: [382103;87297;64275 84235;9106910]; a= zeros(10,25); for i=l: 5 a(i,(i-1)+5+1:5*i)=1 a(5+i,i:5:25)=1 b=ones(10, 1) [x, y]=bintprog(c,[],[], a,b)i x=reshape(x,[5, 51) 求得最优指派方案为x15=x23=x2=x4=x51=1,最优值为21。 求解的 LINGO程序如下: link(var, var): c,xi ndsets data c=382103 87297 64275 9106910 min=@sum (link:c*x)i @for(var(): @sum(var(3):x(1,3))=1) @for(var(3): @sum(var (1):x(1,3))=1)-23- 0 0 1 1 5; b=400,800,200,200; enddata max=@sum(col:c1*x^2+c2*x); @for(row(i):@sum(col(j):a(i,j)*x(j))<b(i)); @for(col:@gin(x)); @for(col:@bnd(0,x,99)); end §5 指派问题的计算机求解 整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，无法 直接利用 Matlab 的函数，必须利用 Matlab 编程实现分枝定界解法和割平面解法。但对 于指派问题等0 −1整数规划问题，可以直接利用 Matlab 的函数 bintprog 进行求解。 例 8 求解下列指派问题，已知指派矩阵为 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ 9 10 6 9 10 8 4 2 3 5 6 4 2 7 5 8 7 2 9 7 3 8 2 10 3 解：编写 Matlab 程序如下： c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5 8 4 2 3 5;9 10 6 9 10]; c=c(:); a=zeros(10,25); for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1; end b=ones(10,1); [x,y]=bintprog(c,[],[],a,b); x=reshape(x,[5,5]),y 求得最优指派方案为 x15 = x23 = x32 = x44 = x51 = 1，最优值为 21。 求解的 LINGO 程序如下： model: sets: var/1..5/; link(var,var):c,x; endsets data: c=3 8 2 10 3 8 7 2 9 7 6 4 2 7 5 8 4 2 3 5 9 10 6 9 10; enddata min=@sum(link:c*x); @for(var(i):@sum(var(j):x(i,j))=1); @for(var(j):@sum(var(i):x(i,j))=1);