清华大学运筹学课件指派问题

《清华大学运筹学课件指派问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、指派问题例开办五家新商店，要五家建筑公司分别承建，各公司营造费用报价如下，如何指派使总造价最小商店费用报价B1B2B3B4B5公司A14871512A279171410A6912873A46714610A56912106标准指派问题的一般提法有nn件事要个人完成，每人做一件事，已知第i个人做第j件事的成本是cij，要确定人和事之间一对一的指派方案，使完成这n件事的总费用最小称Cc为指派问题的系数矩阵ijnn1若指派第i个人做第j件事定义xij0若不指派第i个人做第j件事nn整数规划模型mincijxijij11ns.t.x

2、ij1,i1,2,,nj1nxij1,j1,2,,ni1x0,1,i,jij去掉整数约束标准指派问题是下述产销平衡运输问题A1c11B111c12c1nA2B211cn1AncBn2n11cnn整数容量约束整数解0-1约束自动满足！求解下述运输问题可得标准指派问题的解nnmincijxiji1j1ns.t.xij1,i1,2,,nj1nxij1,j1,2,,ni1x0,i,jij尽管可以用求解运输问题的算法求解标准指派问题，由于存在大量的退化解，经常出现换基不能改进目标函数的情

3、况，这种做法效率不高进一步挖掘标准指派问题的特点可以获得更加有效的算法，这就是所谓的匈牙利算法标准指派问题的第一个有用的性质任取1kn和任意实数A，用C1和C2分别表示将C的第k行或第k列减去A以后得到的系数矩阵，则以C，C或C为系数矩阵的指12派问题的最优方案相同nnnnn理由：cijxijckjAxkjcijxijAi11jj1i11jiknnnnncijxijcikAxikcijxijAi11ji1ij11jk目标函数差一个常数，约束相同，最优解也相同标准指派问题的第二个

4、有用的性质nn如果CR的所有元素中没有负数，且存在n个行列号都互不相同的零元素（简称为独立零元素），那么对应的标准指派问题的最优目标值等于零，最优方案可以由独立零元素的位置确定例如13011800662C012101050412340最优解x13x22x31x44x551算法设想一、利用第一个性质产生零元素二、对给定矩阵找到最大的独立零元素组三、当最大的独立零元素组的零元素数目不够时增加独立零元素的数目通过以上步骤的迭代找到足够的独立零元素例、对以下矩阵各行列减去最小值得到含零等价矩阵487151

5、2043118030118791714100210730177369128703621023216714610018040050469121060364002340要解决的问题：1）如何找出最大的独立零元素组2）如果独立零元素不够怎么办如何找出最大的独立零元素组？用结点表示第i行，结点表示第j列，用边表示ij零元素位置，可得二分图（所有边端点分属两个点集）1103011822017730232133005044

6、40234055求左边矩阵最大独立零元素组等价于求右边二分图的最大基对集，即，互相之间没有相同端点的边的最大集合对于GNE,，给定对集ME（用红线表示），定义M-（非）饱和点：和M的边（不）关联的点M-交错路：由属于和不属于M的边交错形成的路M-增广路：起点和终点都是M-非饱和点的交错路匈牙利树：起点是M-非饱和点但终点不是的交错路覆盖KN：中每条边都有端点属于EK11最小覆盖：所含端点数最少的覆盖2233右图2144是M-增广路4424113是匈牙利树51451,

7、,,是覆盖5对集的边数和覆盖的点数之间的关系：任何对集的边数都不会大于任何覆盖的点数理由：对集每条边的两个端点至少有一个在覆盖中扩大给定对集M的途径：11在G中找M-增广路2233理由：如右图用21,,,44替换4414,就可扩大M55通过标号寻找二分图增广路22111111222222333333144444455555552增广路11114221223223331

8、4444445555重新标号331111111222222