指派问题及实现代码示例.ppt

一 . 什么是指派问题 指派问题就是分配问题： 比如有n个人去做n件事，规定： 每件事只能有且仅有一个人来做 事与人决定时间 求最高的效率的情况 问题模型 二. 定理 第二个定理 覆盖0元的最小直线（行或列）数k，等于位于不同行且不同列的0元的最大个数l。 指派问题的解法 第二步：做最少覆盖0元的直线 对无圈的行打勾 （下面横线无圈）直线就覆盖了所有加圈的0元所在的行） 在已打勾的行中对有删除标记所在的列打勾;（未被行线覆盖的作竖线） 在已打勾的列中对有圈标记所在的行打勾;（用列线覆盖过的就吧要行线了） (4) 重复 (2), (3), 直到无勾可打为止. (5) 对没有打勾的行画一横线, 对打勾的列画一竖线. 这样剩下没有画线的元素中没有零元素. 第三步：加0元 求出其中的最小元素. 各行都减去这个最小元素（同一个数）, 这时在已被划横线的元素中的零元素变成负元素, 在它们所在的列中加上这个最小元素. 还不够所需0元，转步骤2. 在求最优值时，还要回到原来的矩阵去，除非你每次都记录下了所做的加减的总数。 第三步中有点麻烦，可以改为：划去后的矩阵中全部减去最小数，这样就不麻烦了，不过就必须回原效率矩阵，对于全矩阵来说加减已经乱了。为什么可以这么做呢？因为剩下的部分的最优已经无关于划线部分了，（自己的想法而已，可不理会） 两个简便的方法 1.先列后行 2.max-min（不是很严谨） 只是对匈牙利方法不能直接给出解答的带来方便。 （1）行最小 （2）最小元中的最大先指派，划去行列 （3）重复 关于指派问题还有很多内容，限于水平、时间等就不多掰了 Matlab 线性规划的解法 在用矩阵求解方程组时，不一定要确切的数值代入，Matlab中可以用字母来表示。 比如：计算行列式： 常用matlab矩阵运算 加减乘除、数乘等 求逆 inv(A) 行列式值 det(A) 最简形 R=rref(A) 特征值，特征向量：[V,D]=eig(A) (V的列为特征向量) 求秩：rank(A) 迹（特征值之和）trace(A) 解多项式方程 整数规划matlab指令 [X,FVAL,EXITFLAG,OUTPUT,LAMBDA] = LINPROG(f,A,b,Aeq,beq,LB,UB) min f‘*x such that Aeq*x = beq A*x = b , x = 0. LB = X = UB 用一个分支定界法的代码来说明一下 可以求全整型或混合的 Y=min f*x subject to :G*x=h Geq*x=heq Function [x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options) %eq表示等式，否则为小于等于 %为了解决混合的问题，必须用id指明x中那个是整型（1），哪些是实型（0） global upper opt c x0 A Aeq beq ID options; %这一句不用管，我也看不懂，可能引入变量 %为了不改原变量 If nargin10, options=optimset({}); options.Display=off; options.LargeScale=off; end if nargin9, id=ones(size(f)); end if nargin8, x=[]; end if nargin7 |isempty(ub), ub=inf*ones(size(f)); end if nargin6 |isempty(lb), lb=zeros(size(f)); end if nargin5, heq=[]; end if nargin4, Geq=[]; end upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id; %变量处理，不用管 ftemp=ILP(lb(:),ub(:)); x=opt;y=upper; %下面是子函数 function ftemp=ILP(vlb,vub) global upper opt c x0 A b Aeq beq ID options; [x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options); if how =0 return; end;%标志=0 ，则不收敛或达到迭代次数，结束 if ftemp-upper0.00005 %in order to avoid error %得到的解比想象的大 return; end; if max(abs(x.*ID-round(x.*ID)))