指派问题(经典运筹学).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.4 0-1整数规划,一、决策问题与0-1变量,1,0,做第i件事,不做第i件事,n件事中必须,做k件并只做k件事,n件事中,最多做k件事,n件事中,至少做k件事,做第i件事的充要条件是做第j件事,做第i件事的充要条件是不做第j件事,只在做了第i件事前提下才考虑是否做第j件事,该公司只有600万资金可用于投资，由于技术上的,原因，投资受到以下约束：,1、在项目1、2和3中必须有一项被选中,2、项目3和4只能选中一项,3、项目5被选中的前提是项目1被选中;如何,在 满足上述条件下选择一个最好的投资,方 案，使投资收益最大,例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：,项目,投资额,（万元）,投资收益,（万元）,1,210,150,2,300,210,3,100,60,4,130,80,5,260,180,1,0,投资第i个项目,不投资第i个项目,Z表示投资效益,投资项目模型：,例2（布点问题）某城市共有6个区，每个区都可以建消防站市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。

据实地测定，各区之间消防车行驶的时间见右表地区,1,2,3,4,5,6,1,0,10,16,28,27,20,2,10,0,24,32,17,10,3,16,24,0,12,27,21,4,28,32,12,0,15,25,5,27,17,27,15,0,14,6,20,10,21,25,14,0,请为该市制定一个,最节省的计划,在第i个地区建站,Z表示全区消防站总数,不在第i个地区建站,i=1,2,6,布点问题模型：,最优解,x,2,=1,x,4,=1,最优值,Z=2,二、,过滤隐枚举法,（适合于变量个数较少的0-1规划）,（x,1,x,2,x,3,),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）,0,Z0,枚举法：,检验可行解：,32次运算,-2,5,Z5,3,1,8,3,6,运算次数：21,计算目标,函数值：8次,三、指派问题与匈牙利法,设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作c,ij,表示第i个人做第j件事的费用,求总费用最低的指派方案。

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

工作,人,收费用,1 2 3 4,1,2,3,4,3 5 4 5,6 7 6 8,8 9 8 10,10 10 9 11,费用矩阵,对应一个5个人5个工作的指派问题,第2个人做第4个工作的费用,5,第4个人做第2个工作的费用,0,定理：在费用矩阵C=（c,ij,）的任一行（列）中,减去一个常数或加上一个常数不改变本,问题的最优解n个人n个工作的指派问题1,-b,3、,匈牙利法,n个人n个工作的指派问题2,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,-b,-b,i=1,2,n,j=1,2,n,i=1,2,n,j=1,2,n,任务,：,对C的行和列减去某个常数，,将C化的尽可能简单，,简单到可一眼看出该问题的最优解,-b,3.4 0-1整数规划,三、指派问题与匈牙利法,费用,1 2 j n,1,2,i,n,指派问题模型：,i=1,2,n,j=1,2,n,第i个人做第j 人件事,Z表示总费用,i=1,2,n;j=1,2,n,第i个人不做第j 人件事,1、指派问题的,数学模型,设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作c,ij,表示第i个人做第j件事的费用,求总费用最低的指派方案。

2、费用矩阵,设有n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作c,ij,表示第i个人做第j件事的费用,求总费用最低的指派方案费用,1 2 j n,1,2,i,n,c,ij,表示第i个人做第j件事的费用,费用矩阵,定理：在费用矩阵C=（c,ij,）的任一行（列）中,减去一个常数或加上一个常数不改变本,问题的最优解b,3、,匈牙利法,指派问题的最优解：,若C中有n 个位于不同行不同列的零元素，,则令这些零元素对应的变量取1，其余变量,取零，既得指派问题的最优解,i=1,2,3,4,j=1,2,3,4,可行解,最优解,匈牙利法的基本思路：,对费用矩阵C的行和列减去某个常数，将C化成,有n 个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解,例：有一份说明书要分别译成英、日、德、俄四种文字，现交给甲、乙丙、丁四个人去完成，每人完成一种由于个人的专长不同，翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？,工作,人,时间,英 日 德 俄,甲,乙,丙,丁,2 15 13 4,10 4 14 15,9 14 16 13,7 8 11 9,-2,-4,-9,-7,最优方案：,甲翻译俄文,，乙翻译日文,丙翻译英文,，丁翻译德文,总费用：28小时,-4,-2,-2,-4,-9,-7,-4,-2,最优解的取法：,从含0元素最少的行或列开始，圈出一个0元素，用 表示，然后划去该所在的行和列中的其余0元素，用表示，依次类推，若能得到n个，则得最优解X,0,例：求费用矩阵为右表的,指派问题的最优解,工作,人,费用,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,得4个，且不存在没打的0,修改方法！,对n阶费用矩阵C，若C有n 个位于不同行不同列的,零元素，即可得最优解X,0。

否则，对C进行调整2,+2,-2,最优指派方案：甲做B工作,，乙做C工作,丙做A工作,，丁做D工作,戊做E工作,？,？,当C没有n 个位于不同行不同列的零元素时，对C进行调整第一步：做能复盖所有0元素的,最小直线集合,：,1）对没有的行打号,2）对打号的行上所有0元,素的列打号,3）再对打号的列上所有的,行打号,4）重复以上步骤直到得不出新的,打号为止,5）对没有打号的行画横线，所有,打号的列画纵线，所得到的直线,既是复盖所有0元素的最小直线集合,具体步骤：,第二步：在没有被直线复盖的元素中找出最,小元素，让打号的列加上这个元,素，打号的行减去这个元素,第三步：对所得到的矩阵画，若能得到n个，,则得最优解，否则重复以上步骤，直至得,到n个2,-2,-2,例：求费用矩阵为下表的,指派问题的最优解,工作,人,费用,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工作,=32,匈牙利法的具体步骤：,第一步,：变换指派问题的费用矩阵，使其在各行,各列都出现0元素：,方法：首先每行元素减去该行的最小元素，,然后每列减去该列的最小元素,第二步,：进行试指派（画）,方法：从含0元素最少的行或列开始，圈出一个0,元素，用 表示，然后划去该所在的行,和列中的其余0元素，用表示，依次类推。

若矩阵中的的个数等于n，则得最优解,若矩阵中的的个数n,工作,人,费用,1 2 j n,1,2,i,m,n+1 n+2 m,用匈牙利法求解,例：现有4份工作，6个人应聘，由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案工作,人,时间,1 2 3 4,1,2,3,4,5,6,5 6,0,0,0,0,0,0,0,0,0,0,0,0,12 7 9 7,7 17 12 14,15 14 6 6,4 10 7 10,6 5 5 8,4 5 7 6,分派方案：,第3个人第4项工作,第4个人第1项工作,第5个人第3项工作,第6个人第2项工作,第1、2个人没工作,总时间=,6+4+5+5=20,工作,人,费用,1 2 j n,1,2,i,m,m+1,m+2,n,(b)mn,用匈牙利法求解,(3),一个人可做几件事,的指派问题,设n个人中的第k个人可同时做t件事：,把第k个人视为t个人，,这t个人做同一件事的费用系数都一样,问题化为人数为n-1+t个人的指派问题,（4）,某人一定不能做某事,的指派问题,如在minZ问题中，第k个人一定不能做第t件事：,如在maxZ问题中，第k个人一定不能做第t件事，,例：某商业公司计划开办五家新商店。

为了尽早建成营业，商业公司决定由3家建筑公司分别承建已知第A,i,(i=1,2,3)个建筑公司对第Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，每家建筑公司最多只能承建两个商店，且由于某种原因，第B,3,家商店不能由第A,1,个建筑公司承办，求使总费用最少的指派方案,商店,建筑公司,报价,B,1,B,2,B,3,B,4,B,5,A,1,A,2,A,3,4 8 7 15 12,7 9 17 14 10,6 9 12 8 7,B,1,B,2,B,3,B,4,B,5,A,11,A,12,A,21,A,22,A,31,A,32,每家公司最多可,承建两家商店：,人数工作数：,B,1,B,2,B,3,B,4,B,5,B,6,A,11,A,12,A,21,A,22,A,31,A,32,B,3,不能由A,1,承办：,50,50,B,1,B,2,B,3,B,4,B,5,B,6,A,11,A,12,A,21,A,22,A,31,A,32,由A,1,承建B,1,、B,2,指派方案：,，由A,2,承建B,5,由A,3,承建B,3,、B,4,总费用=42,作业：,6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使,总收益最大,的指派方案。

工作,人,收益,1 2 3 4,1,2,3,4,5,6,3 5 4 5,6 7 6 8,8 9 8 10,10 10 9 11,12 11 10 12,13 12 11 13,分派方案：,第3个人第2项工作,第4个人第3项工作,第5个人第1项工作,第6个人第4项工作,第1、2个人没工作,第一步,：变换费用矩阵，使其在各行各列都出现0元素：,方法：每行减去该。