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

01变量：变量：在整数规划问题中，有一类特殊的整数规在整数规划问题中，有一类特殊的整数规划，不仅要求解为整数，而且要求只能取得划，不仅要求解为整数，而且要求只能取得0和和1两个整数值，这类整数规划称之为两个整数值，这类整数规划称之为01型型整数规划，该类解称为整数规划，该类解称为01变量。变量。第三节第三节01型整数规划型整数规划一 指派问题由由n项不同的工作或任务，需要项不同的工作或任务，需要n个人去完成（每人只个人去完成（每人只能完成一项工作）。由于每人的知识、能力、经验等能完成一项工作）。由于每人的知识、能力、经验等不同，故各人完成不同任务所需的时间（或其它资源）不同，故各人完成不同任务所需的时间（或其它资源）不同。不同。问应指派哪个人完成何项工作所消耗的总资源最少？问应指派哪个人完成何项工作所消耗的总资源最少？指派问题的数学模型指派问题的数学模型引进0-1变量表示安排第i个人完成第j项工作表示不安排第i个人完成第j项工作决策变量矩阵可表示为：用 表示第i个人完成第j项工作所需的资源数，称之为效率系数（或价值系数）。表示为则指派问题的数学模型为或1注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。目前认为最简洁的方法匈牙利法。例 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司 对新商店 的建造报价（万元）为 ，商业公司应当对5家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？这是一个标准的指派问题。若设0-1变量当 承建 时当 不承建 时则问题的数学模型为或1如何分派工作?-4-6-7-6-7从而导出匈牙利解法的思想：1955年,由库恩（W.W.Kuhn）根据匈牙利数学家狄考尼格（d.konig)关于矩阵中独立零元素的定理发明的。匈牙利法的基本原理：定理1 将效率矩阵的某一行（或某一列）的各个元素都减去同一个常数t(t可正可负），得到新的矩阵，则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同。但其最优值比原最优值减少t。解：设效率矩阵C为二匈牙利解法记新指派问题的目标函数为 ，注意到所以原式因此有推论推论 若将指派问题的效率矩阵每一行及每一列分别减去若将指派问题的效率矩阵每一行及每一列分别减去各各行各列的最小元素，则得到的新的指派问题与原指派问题有行各列的最小元素，则得到的新的指派问题与原指派问题有相同的最优解。相同的最优解。注：当 cij=0 时，从第i行看，它表示第i人去干第j项工作效率（相对）最好，而从第j列来看，它表示第j项工作让第i人来干效率（相对）最高。问题是：能否找到位于不同行、不同列的问题是：能否找到位于不同行、不同列的n个个0元素？元素？定义 在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例 已知则是一个独立零元素组，分别称为独立零元素。也是一个独立零元素组。不是一个独立零元素组。定理定理 效率矩阵效率矩阵C中独立零元素的最多个数等于能覆盖所中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。有零元素的最少直线数。本定理由匈牙利数学家狄考尼格证明的。例 已知矩阵例 现有一个44的指派问题，其效率矩阵为：求解该指派问题。步骤1：变换系数矩阵，使得每行及每列至少产生一个零元素。-2-4-9-7-4-2步骤步骤2：用圈：用圈0法确定法确定 中的独立中的独立0元素元素。若独立零元素个素有n个，则已得最优解。若 独立零元素的个数 n,则转入步骤3。其余全为0。在在只有一个只有一个0元素的行元素的行（或列）加圈，表示此人只能做该事（或列）加圈，表示此人只能做该事（或此事只能由该人来做），每圈一个（或此事只能由该人来做），每圈一个“0”，同时把，同时把位于位于同同列列同行的其他同行的其他零元素划去零元素划去。表示此时已不能再由他人来做。表示此时已不能再由他人来做（或此人已不能做其它事）。如此反复，直到矩阵中所有（或此人已不能做其它事）。如此反复，直到矩阵中所有零元素都被圈去或划去为至。零元素都被圈去或划去为至。在遇到所有行和列中，在遇到所有行和列中，零元素都不止一个零元素都不止一个时，可时，可任选任选其中其中一个加圈，然后划去一个加圈，然后划去同行、同列同行、同列其他未被标记的零元素。其他未被标记的零元素。例步骤步骤3：若矩阵所有零元素都被标记的，但圈零的个数若矩阵所有零元素都被标记的，但圈零的个数m nm n ，作最少直线覆盖当前零元素。作最少直线覆盖当前零元素。已知5家建筑公司承建5家商店系数矩阵-4-7-6-6-6-1-3变换系数矩阵 确定独立零元素.作最少直线覆盖当前所有零元素。由于独立零元素个数4 5.对没有圈0的行打“”。在已打“”的行中，对零元素所在的列打“”。在已打“”的列中，对圈0元素所在的行打“”。重复和，直到再也找不到可以打“”的行或列为止 对没有打“”的行画一横线，对已打“”的列画一纵线，即得覆盖当前0元素的最少直线数目的集合。继续变换系数矩阵，以增加0元素。在未被直线覆盖的元素中找出一个最小的元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一元素。这样，在未被直线覆盖的元素中势必会出现0元素，但同时却又使已覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素。返回。-1-1+1 中已有5个独立0元素，故可确定指派问题的最优方案。其余全为0。也就是说，最优指派方案是：让A1承建B3,A2承建B2,让A3承建B1,让A4承建B4,让A5承建B5.这样安排能使总的建造费用最少，总的建造费用为7+9+6+6+6=34（万元）。三 非标准形式的指派问题处理方法：化成标准形式，再按匈牙利方法求解。目标函数最大化指派问题例 有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 人数和事数不等的指派问题人少事多，添上虚拟的“人”。这些虚拟的“人”做各事的费用系数可取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 人数和事数不等的指派问题人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取0。工作工人B1 B2 B3 B4A1A2A3A4A5107 5 131111 6 15410 9 11214 12 108 12 14 7例 5家建筑公司承建5家商店的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司 A4和A5，而让技术力量较强的建筑公司A1，A2和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。3 一个人可以做几件事的指派问题由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（和这样，系数矩阵变为：上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚事B6，使之成为标准指派问题的系数矩阵：再利用匈牙利法求解。列变换圈0-1-1+1再变换打覆盖圈0最优解 A1承建B1和B3,A2承建B2,A3承建B4和B5 总建筑费用为最优解 总建筑费用为（万元）A1承建B1和B3,A2承建B2,A3承建B4和B5例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。试分别确定最优分配方案，使完成任务的总时间最少。任务任务人人ABCDE甲甲乙乙丙丙丁丁25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 4某事不能由某个人做 则可将相应的费用系数取作足够大的数M.由于任务数大于人数，所以需要有一个虚拟的人，设为戊。任务任务人人ABCDE甲甲乙乙丙丙丁丁戊戊25293142373938262033342728403224423623450 0 0 0 M工作E必须完成甲不做AM