资源描述：
《指派问题(含非标准指派问题).docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、..第五章整数规划§1整数划的数学模型及特点要求一部分或全部决策量必取整数得划称整数划。其模型：nMax(或min)z=cjxjj1naijxij(,)bii1,2,mj1s.txj0j1,2,nx1,x2,xn中部分或全部取整数若要求决策量只能取0或1的整数划称0-1型整数性划。§5指派问题一．指派的准形式及数学模型在生活中，有各种性的指派。例如，有若干工作需要分配若干人（或部）来完成；有若干合同需要若干个投者来承包；有若干班需要安排在各教室上等等。如此的，它的基本要求是在足特定的指派要求条件下，使指派方案的体效果最佳。由于指派的多性，有
2、必要定指派的准形式。指派的准形式（以人和事例）是：有n个人和n件事，已知第i个人作第j件事的用cij(i,j1,2,n)，要求确定人和事之的一一的指派方案，是完成n件事的用最少。了建立准指派的数学模型，引入n2个0-1量：0若不指派第i人作第j事xiji人作第j件事i，j=1,2,⋯n1若指派第，的数学模型可写成nnminzcijxij（5.1）i1j1n（5.2）xij1j1,2,ni1ns.txij1i1,2,n（5.3）j1xij0,1i,j1,2,n（5.4）其中，（5.1）表示每件事必且只有一个人去做，（5.2）表示每个人必做且只
3、做一件事。注：○1指派是量（ai）、量（bj）相等，且ai=bj=1，i，j=1,2,⋯n的运;...。○有也称cij第i个人完成第j件工作所需的源数，称之效率系数（或价系2数）。并称矩c11c12c1nC=(cij)nn=c21c22c2n（5.5）cn1cn2cnn效率矩（或价系数矩）。并称决策量xij排成的n×n矩x11x12x1nX=(xij)nn=x21x22x2n（5.6）xn1xn2xnn决策量矩。(5.6)的特征是它有n个1，其它都是0。n个1位于不同行、不同列。每一种情况指派的一个可行解。共n!个解。其的用z=C⊙X里的⊙
4、表示两矩元素的，然后相加。是：把n个1放到X的n2个位置的什么地方可使耗的源最少？（解最）例1已知效率矩50202300C=56704800则01000100X（1）=0001，X（2）=00101000100000100001都是指派的最解例12/P-149：某商公司划开五家新商店。了尽早建成，商公司决定由5家建筑公司分承建。已知建筑公司Ai（i=1，2，⋯5）新商店Bj（1，2，⋯5）的建造用的价（万元）cij（i，j=1,2,⋯5）,表5-9。商公司当5家建筑公司怎分派建筑任，才能使的建筑用最少？表5-9;...cijB1B2B3B4
5、B5A14871512A279171410A3691287A46714610A56912106解：是一准的指派。若1当Ai承建Bj时xij=当Ai不承建Bj时00-1量i,j=1,2,⋯5的数学模型Minz=4x11+8x12+⋯+10x54+6x555xij1j1,2,5i15s.txij1i1,2,5j1xij0,1i,j1,2,5若看成运，且xij如上所述，表5-9为商B1B2B3B4B5任店公司A1（4）（8）（7）（15）（12）1x11x12x13x14x15A2（7）(9)(17)(14)(10)1x21x22x23x24x
6、25A3(6)(9)(12)(8)(7)1x31x32x33x34x35A4(6)(7)(14)(6)(10)1x41x42x43x44x45A5(6)(9)(12)(10)(6)1x51x52x53x54x55;...所选的公司数111115当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。二．匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效
7、地减少计算量。1955年，库恩（W.W.Kuhn）提出了匈牙利法。定理1：设指派问题的效率矩阵为C=(cij)nn，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵C(cij)nn，则以C为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为Z.则有nnnnnnnnZ=cijxij=cijxij+cijxij=cijxij+(ckjt)xkji1j1i1j1j1i
8、1j1j1ikiknnnnnn=cijxij+ckjxkj-txkj=cijxij-t·1=Z-ti1j1j1j1i1j1ik因此有MinZ=min(Z-t)=minZ-t而新问
