指派问题运筹学.pptx

《指派问题运筹学.pptx》由会员分享，可在线阅读，更多相关《指派问题运筹学.pptx（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、一、决策问题与0-1变量10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事第1页/共47页该公司只有600万资金可用于投资，由于技术上的原因，投资受到以下约束：1、在项目1、2和3中必须有一项被选中 2、项目3和4只能选中一项 3、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收

2、益（万元）12101502300210310060413080526018010投资第i个项目不投资第i个项目Z表示投资效益投资项目模型：第2页/共47页例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140 请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1

3、,2,6布点问题模型：最优解x2=1,x4=1最优值Z=2第3页/共47页二、过滤隐枚举法（适合于变量个数较少的0-1规划）（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 36运算次数：21计算目标函数值：8次 第4页/共47页三、指派问题与匈牙利法第5页/共47页 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。

4、费用1 2 j n12in指派问题模型：i=1,2,nj=1,2,n第i个人做第j 人件事Z表示总费用i=1,2,n;j=1,2,n第i个人不做第j 人件事1、指派问题的数学模型第6页/共47页i=1,2,nj=1,2,n当n=4时，有16变量，8个约束方程第7页/共47页例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人费用1 2 3 412343 5 4 56 7 6 88 9 8 1010 10 9 1110第i人做第j 件事Z表示总费用i=1,2,3,4;j=1,

5、2,3,4第i人不做第j 件事第8页/共47页2、费用矩阵 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 j n12incij表示第i个人做第j件事的费用费用矩阵第9页/共47页例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1 2 3 412343 5 4 56 7 6 88 9 8 1010 10 9 11费用矩阵对应一个5个人5个工作的指派问题

6、第2个人做第4个工作的费用5第4个人做第2个工作的费用0第10页/共47页定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。n个人n个工作的指派问题1-b3、匈牙利法n个人n个工作的指派问题2第11页/共47页i=1,2,nj=1,2,ni=1,2,nj=1,2,n-b第12页/共47页第13页/共47页-bi=1,2,nj=1,2,ni=1,2,nj=1,2,n第14页/共47页任务：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解-b第15页/共47页三、指派问题与匈牙利法第16页/共47页费用1 2 j n12i

7、n指派问题模型：i=1,2,nj=1,2,n第i个人做第j 人件事Z表示总费用i=1,2,n;j=1,2,n第i个人不做第j 人件事1、指派问题的数学模型 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。第17页/共47页2、费用矩阵 设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用1 2 j n12incij表示第i个人做第j件事的费用费用矩阵第18页/共47页定理：在费用矩阵C=（cij）的任

8、一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。-b3、匈牙利法第19页/共47页指派问题的最优解：若C中有n 个位于不同行不同列的零元素，则令这些零元素对应的变量取1，其余变量 取零，既得指派问题的最优解i=1,2,3,4j=1,2,3,4可行解最优解第20页/共47页匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化成有n 个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解第21页/共47页例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，翻译成不同文字所需的

9、时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？工作人时间英 日 德 俄甲乙丙丁2 15 13 410 4 14 15 9 14 16 13 7 8 11 9-2-4-9-7最优方案：甲翻译俄文，乙翻译日文丙翻译英文，丁翻译德文总费用：28小时-4-2第22页/共47页-2-4-9-7-4-2最优解的取法：从含0元素最少的行或列开始，圈出一个0元素，用 表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推，若能得到n个，则得最优解X0第23页/共47页例：求费用矩阵为右表的 指派问题的最优解工作人费用A B C D E甲乙丙丁戊12 7 9 7 9 8 9 6 6

10、 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 6-7-6-7-6-4得4个，且不存在没打的0修改方法！第24页/共47页对n阶费用矩阵C，若C有n 个位于不同行不同列的零元素，即可得最优解X0。否则，对C进行调整。-2+2-2最优指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？第25页/共47页当C没有n 个位于不同行不同列的零元素时，对C进行调整。第一步：做能复盖所有0元素的最小直线集合：1）对没有的行打号2）对打号的行上所有0元 素的列打号3）再对打号的列上所有的 行打号4）重复以上步骤直到得不出新的 打号为止5）对没有打号的行画横线，所

11、有 打号的列画纵线，所得到的直线 既是复盖所有0元素的最小直线集合具体步骤：第26页/共47页第二步：在没有被直线复盖的元素中找出最 小元素，让打号的列加上这个元 素，打号的行减去这个元素第三步：对所得到的矩阵画，若能得到n个，则得最优解，否则重复以上步骤，直至得 到n个。+2-2-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 6-7-6-7-6-4+2-2-2最优指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做E工作

12、=32第28页/共47页匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行 各列都出现0元素：方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画）方法：从含0元素最少的行或列开始，圈出一个0 元素，用 表示，然后划去该所在的行 和列中的其余0元素，用表示，依次类推。若矩阵中的的个数等于n，则得最优解若矩阵中的的个数n工作人费用1 2 j n12imn+1 n+2 m 用匈牙利法求解第39页/共47页例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使

13、总时间最少的分派方案。工作人时间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 分派方案：第3个人第4项工作第4个人第1项工作第5个人第3项工作第6个人第2项工作第1、2个人没工作总时间=6+4+5+5=20第40页/共47页工作人费用1 2 j n12imm+1 m+2 n (b)mn用匈牙利法求解第41页/共47页(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问

14、题（4）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：如在maxZ问题中，第k个人一定不能做第t件事，第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

15、B1 B2 B3 B4 B5A11A12A21A22A31A32每家公司最多可承建两家商店：人数工作数：B1 B2 B3 B4 B5 B6A11A12A21A22A31A32B3不能由A1承办：5050第43页/共47页 B1 B2 B3 B4 B5 B6A11A12A21A22A31A32由A1承建B1、B2指派方案：，由A2承建B5由A3承建B3、B4总费用=42第44页/共47页作业：6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。工作人收益1 2 3 41234563 5

16、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页感谢您的观看！第47页/共47页