3.4指派问题(经典运筹学)课件

3.40-1整数规划3.4指派问题(经典运筹学)一、决策问题与0-1变量10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事3.4指派问题(经典运筹学)该公司只有600万资金可用于投资，由于技术上的原因，投资受到以下约束：

1、在项目1、2和3中必须有一项被选中

2、项目3和4只能选中一项

3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案，使投资收益最大例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）12101502300210310060413080526018010投资第i个项目不投资第i个项目Z表示投资效益投资项目模型：3.4指派问题(经典运筹学)例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140

请为该市制定一个最节省的计划在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型：最优解x2=1,x4=1最优值Z=23.4指派问题(经典运筹学)二、过滤隐枚举法（适合于变量个数较少的0-1规划）（x1x2x3)Z值

约束条件（1）（2）（3）（4）过滤条件（000）（001）（010）（100）（101）（110）（011）（111）√√√√0Z≥0枚举法：检验可行解：32次运算-25√√√√Z≥5318×

36运算次数：21计算目标函数值：8次√√√√3.4指派问题(经典运筹学)三、指派问题与匈牙利法3.4指派问题(经典运筹学)

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…n指派问题模型：i=1,2,…,nj=1,2,…,n第i个人做第j人件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事1、指派问题的数学模型3.4指派问题(经典运筹学)i=1,2,…,nj=1,2,…,n当n=4时，有16变量，8个约束方程3.4指派问题(经典运筹学)例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人费用123412343545676889810101091110第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,4第i人不做第j件事3.4指派问题(经典运筹学)2、费用矩阵

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵3.4指派问题(经典运筹学)例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1234123435456768898101010911费用矩阵对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用03.4指派问题(经典运筹学)定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。n个人n个工作的指派问题1-b3、匈牙利法n个人n个工作的指派问题23.4指派问题(经典运筹学)i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n-b3.4指派问题(经典运筹学)3.4指派问题(经典运筹学)-bi=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n3.4指派问题(经典运筹学)任务：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解-b3.4指派问题(经典运筹学)3.40-1整数规划三、指派问题与匈牙利法3.4指派问题(经典运筹学)费用12…j…n12…i…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件事的费用,求总费用最低的指派方案。3.4指派问题(经典运筹学)2、费用矩阵

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。费用12…j…n12…i…ncij表示第i个人做第j件事的费用费用矩阵3.4指派问题(经典运筹学)定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。-b3、匈牙利法3.4指派问题(经典运筹学)指派问题的最优解：若C中有n个位于不同行不同列的零元素，则令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解i=1,2,3,4j=1,2,3,4可行解最优解3.4指派问题(经典运筹学)匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化成有n个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解3.4指派问题(经典运筹学)例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？工作人时间英日德俄甲乙丙丁2151341041415914161378119-2-4-9-7最优方案：

甲翻译俄文，乙翻译日文丙翻译英文，丁翻译德文总费用：28小时-4-23.4指派问题(经典运筹学)-2-4-9-7-4-2最优解的取法：从含0元素最少的行或列开始，圈出一个0元素，用○表示，然后划去该○所在的行和列中的其余0元素，用×表示，依次类推，若能得到n个○，则得最优解X03.4指派问题(经典运筹学)例：求费用矩阵为右表的指派问题的最优解工作人费用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4得4个○，且不存在没打×的0修改方法！3.4指派问题(经典运筹学)对n阶费用矩阵C，若C有n个位于不同行不同列的零元素，即可得最优解X0。否则，对C进行调整。-2+2-2最优指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？？3.4指派问题(经典运筹学)当C没有n个位于不同行不同列的零元素时，对C进行调整。第一步：做能复盖所有0元素的最小直线集合：1）对没有○的行打√号2）对打√号的行上所有0元素的列打√号3）再对打√号的列上所有○的行打√号4）重复以上步骤直到得不出新的打√号为止5）对没有打√号的行画横线，所有打√号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合具体步骤：√√√3.4指派问题(经典运筹学)第二步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这个元素第三步：对所得到的矩阵画○，若能得到n个○，则得最优解，否则重复以上步骤，直至得到n个○。√√√+2-2-23.4指派问题(经典运筹学)例：求费用矩阵为下表的指派问题的最优解工作人费用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4√√√+2-2-2最优指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做E工作=323.4指派问题(经典运筹学)匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行各列都出现0元素：方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素第二步：进行试指派（画○）方法：从含0元素最少的行或列开始，圈出一个0

元素，用○表示，然后划去该○所在的行和列中的其余0元素，用×表示，依次类推。若矩阵中的○的个数等于n，则得最优解若矩阵中的○的个数<n，则进行第三步3.4指派问题(经典运筹学)第三步：做能复盖所有0元素的最小直线集合：1）对没有○的行打√号2）对打√号的行上所有0元素的列打√号3）再对打√号的列上所有○的行打√号4）重复以上步骤直到得不出新的打√号为止5）对没有打√号的行画横线，所有打√号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合第四步：在没有被直线复盖的元素中找出最小元素，让打√号的列加上这个元素，打√号的行减去这个元素。转第一步3.4指派问题(经典运筹学)

例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人收费用1234123415182124192322182617161919212317最优方案：第一个人做第一件事；

第二个人做第四件事；第三个人做第三件事；第四个人做第二件事；总费用：703.4指派问题(经典运筹学)√√√√√√√√3.4指派问题(经典运筹学)4、一般的指派问题(1)求maxZ的指派问题(2)人数与工作数不等的指派问题(3)一个人可做几件事的指派问题(4)某事一定由（不能由）某人做的指派问题3.4指派问题(经典运筹学)收益12…j…n12…i…n指派问题模型：i=1,2,…,nj=1,2,…,n第i个人做第j人件事Z表示总收益i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事

设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的收益,求总收益最大的指派方案。(1)求maxZ的指派问题3.4指派问题(经典运筹学)工作人收益12…j…n12…i…n指派问题最大化的数学模型：i=1,2,…,nj=1,2,…,n指派问题最小化的数学模型：i=1,2,…,nj=1,2,…,n用匈牙利法3.4指派问题(经典运筹学)i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n3.4指派问题(经典运筹学)对maxZ的指派问题工作人收益12…j…n12…i…n用匈牙利法求C，3.4指派问题(经典运筹学)例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作的效益如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总效益最大的分派方案。工作人收益12341279771712141514664107101234分派方案：第1个人第3项工作，第2个人第2项工作第3个人第1项工作，第4个人第4项工作总效益=9+17+15+10=513.4指派问题(经典运筹学)（2）人数与工作数不等的指派问题

设有n个工作，要由m个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。(a)m>n工作人费用12…j…n12…i…mn+1n+2…m用匈牙利法求解3.4指派问题(经典运筹学)例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。工作人时间123412345656

00000000000012797717121415146641071065584576分派方案：第3个人第4项工作第4个人第1项工作第5个人第3项工作第6个人第2项工作第1、2个人没工作总时间=6+4+5+5=203.4指派问题(经典运筹学)工作人费用12…j…n12…i…mm+1m+2…n(b)m<n用匈牙利法求解3.4指派问题(经典运筹学)(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事：把第k个人视为t个人，这t个人做同一件事的费用系数都一样问题化为人数为n-1+t个人的指派问题（4）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：如在maxZ问题中，第k个人一定不能做第t件事，3.4指派问题(经典运筹学)例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由3家建筑公司分别承建。已知第Ai(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B3家商店不能由第A1个建筑公司承办，求使总费用最少的指派方案商店建筑公司报价B1B2B3B4B5A1A2A3487151279171410691287B1B2B3B4B5A11A12A21A22A31A32每家公司最多可承建两家商店：人数≠工作数：B1B2B3B4B5B6A11A12A21A22A31A32B3不能由A1承办：50