149
一般的指派（或分配）问题：
设某单位有n个人，有n项任务需要完成，由于各项任务的性质和每人的专长不同，如果分配每个人仅能完成一项任务，应如何分派才能使完成n项任务的总效益最高？
设该指派问题的效益矩阵C?(cij)n?n，其元素cij表示分配第i个人去完成第j项任务时效益.或者说：以cij表示给定的第i单位资源分配用于第j项活动时的有关效益.
设问题的决策变量为xij是0-1变量，即
?1,当第i个人去完成第j项任务时,xij?? （i,j=1,2,?0,当第i个人不去完成第j项任务时minz???cijxij,
i?1j?155,n)
?5??xij?1(i?1,2,,5),j?1??5s..t?
x?1(j?1,2,,5),??ij?i?1??xij?0或1(i,j?1,2,,5).其数学模型为
nnminz???cijxij,
i?1j?1?n??xij?1(i?1,2,,n),j?1??s..t?n
x?1(j?1,2,,n),??ij?i?1??xij?0或1(i,j?1,2,,n).7.5 应用MATLAB解整数规划问题
在本节中，将主要讲解如何用MATLAB求解一般整数规划中的问题，其中包括一般混合
整数规划问题和0-1规划问题.
7.5.1 整数规划枚举法
整数规划的解法有分枝定界法和割平面法等，7.2节内容我们介绍了分枝定界法，割平面法有兴趣的读者可参考有关运筹学著作．我们现在介绍整数规划枚举法，它利用计算机运算速度快，存储量大，而把所有可能的整型点的函数值都计算出来，再从中选取最优的方法．
150
整数规划枚举法计算步骤如下： （1）用线性规划函数linprog求出最优解和最优值，其最优解可作为选取整数变化范围的参考；
（2）用for-end语句作决策变量的整数型参数变化的循环，有多少个非决策变量，就要实施多少重循环；
（3）用if-end语句作不等式和等式结束满足的判断；
（4）对符合约束条件的一组决策变量，进行目标函数计算并储存，否则滑过； （5）用指令max和min，搜索目标函数的最大值和最小值及相应决策变量. 例7.12 用整数规划枚举法求解例7.1.
解 先取消整数限制，求出最优值和最优解. >>clear all; f=[4,5,6]; f1=-f;
a=[3,4,5]; b=[10];
vlb=[0,0,0]’;
[w,fval,exitflag]=linprog(fl,a,b,[],[],vlb,[])
此处求得fv=13.3333和w=[3.3333,0,0]’.
由以上结果定出决策变量x1、x2、x3的取值范围如下：
x1:0~5；x2:0~2；x3:0~2．
下面用枚举法求解. 编写M文件zsgh_1.m： k=1;
for x1=0:5 for x2=0:2
for x3=0:2
q=[x1,x2,x3]’; p=a*q; if p<=b
z(k)=f*q; v(k,:)=q’; k=k+1; end end end end
[zm,mi]=max(z) x=v(mi,:) zv=[z’,v]
当程序zsgh_1.m执行后，输出如下： zm = 13
151
mi = 11 x =
2 1 0 zv =
0 0 0 0 6 0 0 1 12 0 0 2 5 0 1 0 11 0 1 1 10 0 2 0 4 1 0 0 10 1 0 1 9 1 1 0 8 2 0 0 13 2 1 0 12 3 0 0
这说明所述整数解的最大值为13，其最优解为x1=2，x2=1，x3=0．
可以看到，取消整数时，其最大值为13.3333.这样，我们得到最优方案为：第一种货物装2件，第二种货物装1件，其总价值为13.
7.5.2 用MATLAB求解一般混合整数规划问题
由于MATLAB欧化工具箱中并未提供纯整数规划和混合整数规划的函数，因此需要自行根据需求和设定相关算法来实现，这里我们给出开罗大学的Sherif和Tawfik在MATLAB Central上发布的一个用于求解一般混合整数规划的程序，在此命为intprog.笔者在源程序的基础上做了简单的修改，将其选择用分枝变序的算法由自然序改造成按本章7.2节中所述分枝变量选择原则中的一种，即选择与整数值相差最大的非整数变量首先进行分枝，intprog函数的调用格式如下.
[x,fval,exitflag]=intprog(c,a,b,Aeq,Beq,lb,ub,M,TolXInteger) 该函数所解决的整数规划问题为
minf?cx?Ax?b?Aeqx?beq?s..t?.
vlb?x?vub???xj?0且取整数值在上述标准问题中，假设x为n维设计变量，且线性规划问题具有不等式约束m1个，等式约束m2个，则：c为n维行向量(c1,c2,,cn),x为n维列向量(x1,x2,,xn)T，b为m1维
152
列向量，beq为m2维列向量，A为m1?n维矩阵，Aeq为m2?n维矩阵.
在该函数中，输入参数有c,A,b,Aeq,beq,vlb,vub，M和TolXInteger.其中，c为目标函数所对应设计变量的系数，A为整数规划对应的不等式约束条件方程组构成的系数矩阵，b为不等式约束条件方程组右边的值构成的向量，Aeq为整数规划对应的等式约束方程组构成的系数矩阵，beq为等式约束方程组右边的值构成的向量。vlb和vub为设计变量对应的上界和下界，M为具有整数约束条件限制的设计变量的序号，例如，问题设计变量为x1,x2,,xn，要
求x2,x3和x6为整数，则M=[2；3；6]；若要求全为整数，则M=1:6,或者M=[1；2；3；4；5；6].TolXInteger为判定整数的误差值，即若某数x和最临近整数相差小于该误差值，则认为x即为该整数.
该函数的输出参数有x，fval和exitflag.其中x为整数规划问题的最优解向量，fval为整数规划问题的目标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量.
在MATLAB中实现intporg的代码和分析如下 %整数规划的MATLAB实现
%Originally Designed By Sherif A. Tawfik, Faculty of Engineering, Cairo % University Revised By LiMing, 2009-12-29
%函数调用形式[x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger) %函数求解如下形式的整数规划问题 %min f'*x %subject to
% A*x<=b % Aeq*x=beq % lb<=x<=ub
% M存储有整数约束的变量编号的向量 % TolXInteger是判定整数的误差限 %
%函数返回变量
%x:整数规划的最优解
%fval:目标函数在最优解处的函数值 %exitflag = 1 收敛到解x
% 0 达到线性规划的最大迭代次数 % -1 无解 %
function [x,fval,exitflag]=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger) %设置不显示求解线性规划过程中的提示信息 options = optimset('display','off'); %上界的初始值 bound=inf;
%求解原问题P0的松弛线性规划Q0，首先获得问题的初始解 [x0,fval0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options);
153
%利用递归法进行二叉树的遍历，实现分枝定界法对整数规划的求解
[x,fval,exitflag,b]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);
%分枝定界法的递归算法
%x为问题的初始解，v是目标函数在x处的取值
function [xx,fval,exitflag,bb]=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x,v,M, TolXInteger,bound)
options = optimset('display','off'); %求解不考虑整数约束的松弛线性规划
[x0,fval0,exitflag0]=linprog(f,A,b,Aeq,beq,lb,ub,[],options); %如果算法结束状态指示变量为负值，即表示无可行解，返回初始输入 %或者所目标函数值大于已经获得的上界，返回初始输入 if exitflag0<=0 | fval0>bound xx=x; fval=v;
exitflag=exitflag0; bb=bound; return; end
%确定所有变量是否均为整数，如是，则返回 %该条件表示x0(M)不是整数
ind=find(abs(x0(M)-round(x0(M)))>TolXInteger); %如果都是整数 if isempty(ind) exitflag=1;
%如果当前的解优于已知的最优解，则将当前解作为最优解 if fval0 x0(M)=round(x0(M)); xx=x0; fval=fval0; bb=fval0; %否则，返回原来的解 else xx=x; fval=v; bb=bound; end return; end %程序运行至此，说明松弛线性规划的解是一个可行解且目标函数值比当前记录的上界