运筹学整数规划指派问题

1运筹学整数规划指派问题一指派问题由n项不同的工作或任务，需要n个人去完成（每人只能完成一项工作）。由于每人的知识、能力、经验等不同，故各人完成不同任务所需的时间（或其它资源）不同。问应指派哪个人完成何项工作所消耗的总资源最少？指派问题的数学模型引进0-1变量表示安排第i个人完成第j项工作表示不安排第i个人完成第j项工作第1页/共34页决策变量矩阵可表示为：用表示第i个人完成第j项工作所需的资源数，称之为效率系数（或价值系数）。表示为第2页/共34页则指派问题的数学模型为或1注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。目前认为最简洁的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 —匈牙利法。第3页/共34页例某商业公司 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造报价（万元）为，商业公司应当对5家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？第4页/共34页这是一个 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的指派问题。若设0-1变量当承建时当不承建时则问题的数学模型为或1第5页/共34页如何分派工作?第6页/共34页-4-6-7-6-7从而导出匈牙利解法的思想：第7页/共34页1955年,由库恩（）根据匈牙利数学家狄·考尼格（d.konig)关于矩阵中独立零元素的定理发明的。匈牙利法的基本原理：定理1将效率矩阵的某一行（或某一列）的各个元素都减去同一个常数t(t可正可负），得到新的矩阵，则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同。但其最优值比原最优值减少t。解：设效率矩阵C为二匈牙利解法第8页/共34页记新指派问题的目标函数为，第9页/共34页注意到所以原式因此有推论若将指派问题的效率矩阵每一行及每一列分别减去各行各列的最小元素，则得到的新的指派问题与原指派问题有相同的最优解。注：当cij=0时，从第i行看，它表示第i人去干第j项工作效率（相对）最好，而从第j列来看，它表示第j项工作让第i人来干效率（相对）最高。第10页/共34页问题是：能否找到位于不同行、不同列的n个0元素？定义在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例已知则是一个独立零元素组，第11页/共34页分别称为独立零元素。也是一个独立零元素组。不是一个独立零元素组。第12页/共34页定理效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。本定理由匈牙利数学家狄·考尼格证明的。例已知矩阵第13页/共34页例现有一个4×4的指派问题，其效率矩阵为：求解该指派问题。步骤1：变换系数矩阵，使得每行及每列至少产生一个零元素。第14页/共34页-2-4-9-7-4-2步骤2：用圈0法确定中的独立0元素。若独立零元素个素有n个，则已得最优解。若独立零元素的个数<n,则转入步骤3。其余全为0。第15页/共34页在只有一个0元素的行（或列）加圈，表示此人只能做该事（或此事只能由该人来做），每圈一个“0”，同时把位于同列同行的其他零元素划去。表示此时已不能再由他人来做（或此人已不能做其它事）。如此反复，直到矩阵中所有零元素都被圈去或划去为至。在遇到所有行和列中，零元素都不止一个时，可任选其中一个加圈，然后划去同行、同列其他未被标记的零元素。例第16页/共34页步骤3：若矩阵所有零元素都被标记的，但圈零的个数m<n，作最少直线覆盖当前零元素。已知5家建筑公司承建5家商店系数矩阵-4-7-6-6-6-1-3⒈变换系数矩阵第17页/共34页⒉确定独立零元素.⒊作最少直线覆盖当前所有零元素。由于独立零元素个数4<5.⑴对没有圈0的行打“✓”。⑵在已打“✓”的行中，对零元素所在的列打“✓”。✓✓⑶在已打“✓”的列中，对圈0元素所在的行打“✓”。✓第18页/共34页✓✓✓⑷重复⑵和⑶，直到再也找不到可以打“✓”的行或列为止⑸对没有打“✓”的行画一横线，对已打“✓”的列画一纵线，即得覆盖当前0元素的最少直线数目的集合。✓✓✓⒋继续变换系数矩阵，以增加0元素。在未被直线覆盖的元素中找出一个最小的元素。对未被直第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页三非标准形式的指派问题处理方法：化成标准形式，再按匈牙利方法求解。⒈目标函数最大化指派问题例有4名工人A1,A2,A3,A4分别操作4台机床B1,B2,B3,B4。每人操作每台机床的单位产量见下表。求产值最大的指派方案。机床工人B1B2B3B4A1A2A3A410987345621124356第23页/共34页⒉人数和事数不等的指派问题人少事多，添上虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。工作工人B1B2B3B4B5A1A2A3A410114287111014125691214131511107第24页/共34页⒉人数和事数不等的指派问题人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取0。工作工人B1B2B3B4A1A2A3A4A575131161510911141210812147第25页/共34页例5家建筑公司承建5家商店的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，而让技术力量较强的建筑公司A1，A2和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。3一个人可以做几件事的指派问题第26页/共34页由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（和这样，系数矩阵变为：上面的系数矩阵有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项任务可选3项完成。但甲不能做A项工作。试分别确定最优分配方案，使完成任务的总时间最少。任务人ABCDE甲乙丙丁252931423738262033342728403224423623454某事不能由某个人做则可将相应的费用系数取作足够大的数M.第32页/共34页由于任务数大于人数，所以需要有一个虚拟的人，设为戊。任务人ABCDE甲乙丙丁戊25293142373938262033342728403224423623450000M工作E必须完成甲不做AM第33页/共34页