指派问题运筹学PPT学习教案

会计学1件事是否做第决策变量ixiix10做第i件事不做第i件事ni,2, 1n件事中必须做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21n件事中至少做k件事nxxx21k做第i件事的充要条件是做第j件事jixx 做第i件事的充要条件是不做第j件事jixx1只在做了第i件事前提下才考虑是否做第j件事ijxx第1页/共47页该公司只有600万资金可用于投资，由于技术上的原因，投资受到以下约束： 1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项 3、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）121015023002103100604130805260180)5 , 2 , 1ixi为决策变量（解：设ix10投资第i个项目不投资第i个项目Z表示投资效益投资项目模型： 543211808060210150maxxxxxxZts.60026013010030021054321xxxxx1321xxx143 xx15xx5 , 2 , 11 , 0ixi第2页/共47页例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140 请为该市制定一个最节省的计划解：01ix在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2, ,6布点问题模型：654321minxxxxxxZ6 , 2 , 11 , 0ixits.121 xx1621xxx143 xx1543xxx1652xxx最优解x2=1, x4=1最优值Z=2第3页/共47页（适合于变量个数较少的0-1规划）10,64342422.253max3213221321321321或例：求xxxxxxxxxxxxxt sxxxZ（x1 x2 x3)Z值 约束条件（1）（2）（3）（4）过滤条件（0 0 0）（0 0 1）（0 1 0）（1 0 0）（1 0 1）（1 1 0）（0 1 1）（1 1 1） 0Z0枚举法：检验可行解：32次运算-25 Z5318 366111321Zxxx最优值，最优解：运算次数：21计算目标函数值：8次 第4页/共47页三、指派问题与匈牙利法第5页/共47页 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 j n12in指派问题模型： jiijijxcZmin1.21inijiixxxxt si=1,2, ,n121njijjjxxxxj=1,2, ,nnjnixij, 2 , 1;, 2 , 11 , 0解：第i个人做第j 人件事Z表示总费用i=1,2, ,n; j=1,2, ,n第i个人不做第j 人件事01ijxnnnjnninijiinjnjcccccccccccccccc21212222211112111、指派问题的数学模型第6页/共47页jiijijxcZminnnnnnnnnnnnnxcxcxcxcxcxcxcxcxc2211222222212111121211111.21inijiixxxxt s121njijjjxxxxi=1,2, ,nj=1,2, ,n当n=4时，有16变量，8个约束方程111.21222221111211nnnjnnnjnjxxxxxxxxxxxxt s11121222212112111nninnnninixxxxxxxxxxxx第7页/共47页例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人费用1 2 3 412343 5 4 56 7 6 88 9 8 1010 10 9 11解：ijx10第i人做第j 件事Z表示总费用i=1,2, 3,4; j=1,2, 3,4第i人不做第j 件事141312115453maxxxxxZ242322218676xxxx3433323110898xxxx444342411191010 xxxx1.14131211xxxxts124232221xxxx134333231xxxx144434241xxxx141312111xxxx142322212xxxx143332313xxxx144342414xxxxnjnixij,2,1,2,11 ,0第8页/共47页2、费用矩阵 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 j n12innnnjnninijiinjnjcccccccccccccccc2121222221111211nnnnnncccccccccC212222111211取cij表示第i个人做第j件事的费用费用矩阵第9页/共47页工作人收费用1 2 3 412343 5 4 56 7 6 88 9 8 1010 10 9 11费用矩阵11910101089886765453C0753193506650016532054321C设对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用0第10页/共47页定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。n个人n个工作的指派问题1nnnniniinnccccccccccccC21212222111211-bnnnniniinncccbcbcbcccccccC21212222111211iniicccb,min213、匈牙利法n个人n个工作的指派问题2第11页/共47页Zminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc22112211222222212111121211111.21inijiixxxxt s121njijjjxxxxnjnixij, 2 , 1;, 2 , 11 , 0i=1,2, ,nj=1,2, ,nZminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()(nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC212122221112111.21inijiixxxxt s121njijjjxxxxnjnixij, 2 , 1;, 2 , 11 , 0i=1,2, ,nj=1,2, ,n-b第12页/共47页Zminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()()(212211221122222221211112121111iniinnnnnnnnininiiiinnnnxxxbxcxcxcxcxcxcxcxcxcxcxcxcbxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn2211221122222221211112121111第13页/共47页ZminZminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc2211221122222221211112121111bxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn2211221122222221211112121111nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-b1.21inijiixxxxt s121njijjjxxxxnjnixij, 2 , 1;, 2 , 11 , 0i=1,2, ,nj=1,2, ,n1.21inijiixxxxt s121njijjjxxxxnjnixij, 2 , 1;, 2 , 11 , 0i=1,2, ,nj=1,2, ,nbZ bZ 第14页/共47页ZminZmin的最优解是若ZXmin0的最优解也是，则ZXmin0的最优值是若ZZmin0的最优值是，则若ZbZmin0任务：对C的行和列减去某个常数， 将C化的尽可能简单，简单到可一眼看出该问题的最优解nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-bbZ bZ 第15页/共47页三、指派问题与匈牙利法第16页/共47页费用1 2 j n12in指派问题模型： jiijijxcZmin1.21inijiixxxxt si=1,2, ,n121njijjjxxxxj=1,2, ,nnjnixij, 2 , 1;, 2 , 11 , 0解：第i个人做第j 人件事Z表示总费用i=1,2, ,n; j=1,2, ,n第i个人不做第j 人件事01ijxnnnjnninijiinjnjcccccccccccccccc21212222211112111、指派问题的数学模型 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。第17页/共47页2、费用矩阵 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 j n12innnnjnninijiinjnjcccccccccccccccc2121222221111211nnnnnncccccccccC212222111211取cij表示第i个人做第j件事的费用费用矩阵0第18页/共47页定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。nnnniniinnccccccccccccC21212222111211-bnnnniniinncccbcbcbcccccccC21212222111211iniicccb,min213、匈牙利法ZminZmin的最优解是若ZXmin0的最优解也是，则ZXmin0bZ bZ 第19页/共47页指派问题的最优解： 若C中有n 个位于不同行不同列的零元素， 则令这些零元素对应的变量取1，其余变量 取零，既得指派问题的最优解00102350960607130C例如：ijijijxcZ4141min1.4321iiiixxxxt si=1,2, 3,414321jjjjxxxxj=1,2, 3,44 , 3 , 2 , 1; 4 , 3 , 2 , 11 , 0jixij0，取114x, 122x, 131x143x0,ijx其余可行解Z总费用1414xc2222xc3131xc4343xc0最优解第20页/共47页对费用矩阵C的行和列减去某个常数，将C化成有n 个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解第21页/共47页工作人时间英 日 德 俄甲乙丙丁2 15 13 410 4 14 15 9 14 16 13 7 8 11 99118713161491514410413152C-2-4-9-72410475011100621113000102350960607130?最优方案： 甲翻译俄文，乙翻译日文丙翻译英文，丁翻译德文，最优解114x, 122x, 131x143x0,ijx其余总费用：28小时-4 -2第22页/共47页9118713161491514410413152C-2-4-9-72410475011100621113000102350960607130-4-2最优解的取法：从含0元素最少的行或列开始，圈出一个0元素，用 表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推，若能得到n个，则得最优解X0，最优解114x, 122x, 131x143x0,ijx其余4141jiijijxcZ最优值：14c22c31c43c28第23页/共47页例：求费用矩阵为右表的 指派问题的最优解工作人费用A B C D E甲乙丙丁戊12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 661071041066141512141217766698979712C-7-6-7-6-426360400895751000003220205得4个，且不存在没打的0修改方法！第24页/共47页对n阶费用矩阵C，若C有n 个位于不同行不同列的零元素，即可得最优解X0。否则，对C进行调整。-2+2041404008115751020003420207-204140400811353800003420207最优指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？，最优解112x, 123x, 131x143x0,ijx其余1,55x26360400895751000003220205第25页/共47页当C没有n 个位于不同行不同列的零元素时，对C进行调整。第一步：做能复盖所有0元素的最小直线集合：1）对没有的行打号2）对打号的行上所有0元 素的列打号3）再对打号的列上所有的 行打号4）重复以上步骤直到得不出新的 打号为止5）对没有打号的行画横线，所有 打号的列画纵线，所得到的直线 既是复盖所有0元素的最小直线集合具体步骤：26360400895751000003220205第26页/共47页第二步：在没有被直线复盖的元素中找出最 小元素，让打号的列加上这个元 素，打号的行减去这个元素第三步：对所得到的矩阵画，若能得到n个， 则得最优解，否则重复以上步骤，直至得 到n个。26360400895751000003220205+2263624008115751020003420207-204140400811353800003420207-2第27页/共47页例：求费用矩阵为下表的 指派问题的最优解工作人费用A B C D E甲乙丙丁戊12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 661071041066141512141217766698979712C-7-6-7-6-426360400895751000003220205+2-2-204140400811353800003420207，最优解112x, 123x, 131x144x0,ijx其余1,55x最优指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做E工作Z最优值=3232，即总费用为第28页/共47页第一步：变换指派问题的费用矩阵，使其在各行 各列都出现0元素：方法：首先每行元素减去该行的最小元素， 然后每列减去该列的最小元素第二步：进行试指派（画）方法：从含0元素最少的行或列开始，圈出一个0 元素，用 表示，然后划去该所在的行 和列中的其余0元素，用表示，依次类推。若矩阵中的的个数等于n，则得最优解若矩阵中的的个数n工作人费用1 2 j nmnmjmminijiinjnjcccccccccccccccc212122222111121112imn+1 n+2 m 000000000000用匈牙利法求解第39页/共47页例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。工作人时间1 2 3 41234565 6 00000000000012 7 9 7 7 17 12 14 15 14 6 6 4 10 7 10 6 5 5 84 5 7 6 00675400855600107104006614150014121770079712C00220000400200425000019110087123001428 分派方案： 第3个人第4项工作第4个人第1项工作第5个人第3项工作第6个人第2项工作第1、2个人没工作总时间=6+4+5+5=20第40页/共47页工作人费用1 2 j nmnmjmminijiinjnjcccccccccccccccc212122222111121112imm+1 m+2 n 000000000000(b)mn用匈牙利法求解第41页/共47页(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题（4）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：充分大取费用系数ijc如在maxZ问题中，第k个人一定不能做第t件事，0ijc取效率系数第42页/共47页例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，求使总费用最少的指派方案商店建筑公司报价B1 B2 B3 B4 B5A1A2A34 8 7 15 12 7 9 17 14 10 6 9 12 8 7 781296781296101417971014179712157841215784B1 B2 B3 B4 B5A11A12A21A22A31A32每家公司最多可承建两家商店：人数工作数：B1 B2 B3 B4 B5 B6A11A12A21A22A31A32078129607812960101417970101417970121578401215784B3不能由A1承办：5050第43页/共47页07812960781296010141797010141797012155084012155084C0000120000120365130365130573800057380010001210001202540202540215738001573800100012100012025402025402157380015738003000343000342254242254243573822357382230003430003400320200320213536001353600B1 B2 B3 B4 B5 B6A11A12A21A22A31A32由A1承建B1、B2指派方案：，由A2承建B5由A3承建B3、B4总费用=42第44页/共47页 6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。工作人收益1 2 3 41234563 5 4 5 6 7 6 8 8 9 8 10 10 10 9 1112 11 10 1213 12 11 13分派方案：第3个人第2项工作第4个人第3项工作第5个人第1项工作第6个人第4项工作第1、2个人没工作第45页/共47页第一步：变换费用矩阵，使其在各行各列都出现0元素：方法：每行减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画）方法：从含0元素最少的行或列开始，圈出一个0元素，用 表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推。 若矩阵中的的个数等于n，则得最优解若矩阵中的的个数n，则进行第三步第三步：做能复盖所有0元素的最小直线集合：1）对没有的行打号2）对打号的行上所有0元素的列打号3）再对打号的列上所有的行打号4）重复以上步骤直到得不出新的打号为止5）对没有打号的行画横线，所有打号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合第四步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。 转第一步第46页/共47页