运筹学整数规划指派问题.pptx

《运筹学整数规划指派问题.pptx》由会员分享，可在线阅读，更多相关《运筹学整数规划指派问题.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一 指派问题由由n项不同的工作或任务，需要项不同的工作或任务，需要n个人去完成（每人只个人去完成（每人只能完成一项工作）。由于每人的知识、能力、经验等能完成一项工作）。由于每人的知识、能力、经验等不同，故各人完成不同任务所需的时间（或其它资源）不同，故各人完成不同任务所需的时间（或其它资源）不同。不同。问应指派哪个人完成何项工作所消耗的总资源最少？问应指派哪个人完成何项工作所消耗的总资源最少？指派问题的数学模型指派问题的数学模型引进0-1变量表示安排第i个人完成第j项工作表示不安排第i个人完成第j项工作第1页/共34页决策变量矩阵可表示为：用 表示第i个人完成第j项工作所需的资源数，称之为效率

2、系数（或价值系数）。表示为第2页/共34页则指派问题的数学模型为或1注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。目前认为最简洁的方法匈牙利法。第3页/共34页例 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司 对新商店 的建造报价（万元）为 ，商业公司应当对5家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？第4页/共34页这是一个标准的指派问题。若设0-1变量当 承建 时当 不承建 时则问题的数学模型为或1第5页/共34页如何分派工作?第6页/共34页-4-6-7-6-7从而导出匈牙利解法的思想：第7页/共34页1955年,由库

3、恩（W.W.Kuhn）根据匈牙利数学家狄考尼格（d.konig)关于矩阵中独立零元素的定理发明的。匈牙利法的基本原理：定理1 将效率矩阵的某一行（或某一列）的各个元素都减去同一个常数t(t可正可负），得到新的矩阵，则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同。但其最优值比原最优值减少t。解：设效率矩阵C为二匈牙利解法第8页/共34页记新指派问题的目标函数为 ，第9页/共34页注意到所以原式因此有推论推论 若将指派问题的效率矩阵每一行及每一列分别减去若将指派问题的效率矩阵每一行及每一列分别减去各各行各列的最小元素，则得到的新的指派问题与原指派问题有行各列的最小元素，则得到的新的指派问题

4、与原指派问题有相同的最优解。相同的最优解。注：当 cij=0 时，从第i行看，它表示第i人去干第j项工作效率（相对）最好，而从第j列来看，它表示第j项工作让第i人来干效率（相对）最高。第10页/共34页问题是：能否找到位于不同行、不同列的问题是：能否找到位于不同行、不同列的n个个0元素？元素？定义 在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例 已知则是一个独立零元素组，第11页/共34页分别称为独立零元素。也是一个独立零元素组。不是一个独立零元素组。第12页/共34页定理定理 效率矩阵效率矩阵C中独立零元素的最多个数等于能覆盖所中独立零

5、元素的最多个数等于能覆盖所有零元素的最少直线数。有零元素的最少直线数。本定理由匈牙利数学家狄考尼格证明的。例 已知矩阵第13页/共34页例 现有一个44的指派问题，其效率矩阵为：求解该指派问题。步骤1：变换系数矩阵，使得每行及每列至少产生一个零元素。第14页/共34页-2-4-9-7-4-2步骤步骤2：用圈：用圈0法确定法确定 中的独立中的独立0元素元素。若独立零元素个素有n个，则已得最优解。若 独立零元素的个数 n,则转入步骤3。其余全为0。第15页/共34页在在只有一个只有一个0元素的行元素的行（或列）加圈，表示此人只能做该事（或列）加圈，表示此人只能做该事（或此事只能由该人来做），每圈一

6、个（或此事只能由该人来做），每圈一个“0”，同时把，同时把位于位于同同列列同行的其他同行的其他零元素划去零元素划去。表示此时已不能再由他人来做。表示此时已不能再由他人来做（或此人已不能做其它事）。如此反复，直到矩阵中所有（或此人已不能做其它事）。如此反复，直到矩阵中所有零元素都被圈去或划去为至。零元素都被圈去或划去为至。在遇到所有行和列中，在遇到所有行和列中，零元素都不止一个零元素都不止一个时，可时，可任选任选其中其中一个加圈，然后划去一个加圈，然后划去同行、同列同行、同列其他未被标记的零元素。其他未被标记的零元素。例第16页/共34页步骤步骤3：若矩阵所有零元素都被标记的，但圈零的个数若矩阵

7、所有零元素都被标记的，但圈零的个数m nm n ，作最少直线覆盖当前零元素。作最少直线覆盖当前零元素。已知5家建筑公司承建5家商店系数矩阵-4-7-6-6-6-1-3变换系数矩阵第17页/共34页 确定独立零元素.作最少直线覆盖当前所有零元素。由于独立零元素个数4 5.对没有圈0的行打“”。在已打“”的行中，对零元素所在的列打“”。在已打“”的列中，对圈0元素所在的行打“”。第18页/共34页 重复和，直到再也找不到可以打“”的行或列为止 对没有打“”的行画一横线，对已打“”的列画一纵线，即得覆盖当前0元素的最少直线数目的集合。继续变换系数矩阵，以增加0元素。在未被直线覆盖的元素中找出一个最小

8、的元素。对未被直第19页/共34页线覆盖的元素所在的行（或列）中各元素都减去这一元素。这样，在未被直线覆盖的元素中势必会出现0元素，但同时却又使已覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素。返回。第20页/共34页-1-1+1 中已有5个独立0元素，故可确定指派问题的最优方案。其余全为0。第21页/共34页也就是说，最优指派方案是：让A1承建B3,A2承建B2,让A3承建B1,让A4承建B4,让A5承建B5.这样安排能使总的建造费用最少，总的建造费用为7+9+6+6+6=34（万元）。第22页/共34页三 非标准形式的指派问题处理方法：化成标准

9、形式，再按匈牙利方法求解。目标函数最大化指派问题例 有4名工人A1,A2,A3,A4分别操作4台机床B1,B2,B3,B4。每人操作每台机床的单位产量见下表。求产值最大的指派方案。机床工人B1 B2 B3 B4A1A2A3A410 9 8 7 3 4 5 6 2 1 1 2 4 3 5 6第23页/共34页 人数和事数不等的指派问题人少事多，添上虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。工作工人B1 B2 B3 B4 B5A1A2A3A410 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7第24页/共3

10、4页 人数和事数不等的指派问题人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取0。工作工人B1 B2 B3 B4A1A2A3A4A5107 5 131111 6 15410 9 11214 12 108 12 14 7第25页/共34页例 5家建筑公司承建5家商店的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司 A4和A5，而让技术力量较强的建筑公司A1，A2和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。3 一个人可以做几件事的指派问题第26页/共34页由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化

11、作相同的两家建筑公司（和这样，系数矩阵变为：上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，第27页/共34页引入一件虚事B6，使之成为标准指派问题的系数矩阵：再利用匈牙利法求解。第28页/共34页列变换圈0-1-1+1再变换打覆盖第29页/共34页圈0最优解 A1承建B1和B3,A2承建B2,A3承建B4和B5 总建筑费用为第30页/共34页最优解 总建筑费用为（万元）A1承建B1和B3,A2承建B2,A3承建B4和B5第31页/共34页例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：任务E必须完成，其它4项任务

12、可选3项完成。但甲不能做A项工作。试分别确定最优分配方案，使完成任务的总时间最少。任务任务人人A B C D E甲甲乙乙丙丙丁丁25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 4某事不能由某个人做 则可将相应的费用系数取作足够大的数M.第32页/共34页由于任务数大于人数，所以需要有一个虚拟的人，设为戊。任务任务人人A B C D E甲甲乙乙丙丙丁丁戊戊25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 0 0 0 0 M工作E必须完成甲不做AM第33页/共34页感谢您的观看！第34页/共34页