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

一 . 什么是指派问题;问题模型;二. 定理;由此，每行每列减去最小数，总可以得到每行每列至少有一个0;第二个定理;指派问题的解法;对无圈的行打勾 （下面横线无圈）直线就覆盖了所有加圈的0元所在的行） 在已打勾的行中对有删除标记所在的列打勾;（未被行线覆盖的作竖线） 在已打勾的列中对有圈标记所在的行打勾;（用列线覆盖过的就吧要行线了） (4) 重复 (2), (3), 直到无勾可打为止. (5) 对没有打勾的行画一横线, 对打勾的列画一竖线. 这样剩下没有画线的元素中没有零元素. ;第三步：加0元;在求最优值时，还要回到原来的矩阵去，除非你每次都记录下了所做的加减的总数。 第三步中有点麻烦，可以改为：划去后的矩阵中全部减去最小数，这样就不麻烦了，不过就必须回原效率矩阵，对于全矩阵来说加减已经乱了。为什么可以这么做呢？因为剩下的部分的最优已经无关于划线部分了，（自己的想法而已，可不理会）;例;1 ） 用红圈标出一些某行或某列仅有的零元素，再 通过行列交换把这些零换到左上角（后者非必须）;2 ） 在没有红圈的右下角如果有 零，一定是新的独立零元素;4 ） 在直线未覆盖处找零，如果没有零停止，否则 会出现以下两种情况，其中黑实圈圈住的是新零;;两个简便的方法;关于指派问题还有很多内容，限于水平、时间等就不多掰了;;Matlab 线性规划的解法;常用matlab矩阵运算;解多项式方程;整数规划matlab指令;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)))0.00005 %得到最优解（如果没错的话），因为用 %linpro 的时候已经吧实数得到最优了，这里判断整数的就好了 if upper-ftemp0.00005 %in order to avoid error %有错的时候 opt=x;upper=ftemp; return; else %没错的时候 opt=[opt;x]; return; end; end; notintx=find(abs(x-round(x))=0.00005); %找到非整数的 intx=fix(x);tempvlb=vlb;tempvub=vub; %化为整数，上限，下限 if vub(notintx(1,1),1)=intx(notintx(1,1),1)+1; tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1; %上限值取这个整数+与上限的最小 ftemp=IntLP(tempvlb,vub); %右边 end; if vlb(notintx(1,1),1)=intx(notintx(1,1),1) tempvub(notin