选址问题及隐枚举法

1第八章整数规划第一节整数规划第二节0-1规划第三节指派问题第四节整数规划的应用2某道桥公司在同一时间内可参加A1、A2、A3、A4四项工程的投标。这些工程要求的工期相同。公司根据招标文件和本公司的技术水平对每项工程进行了仔细的研究和计算，将各项工程的预期利润，主要工序的工程量及本企业的施工能力见小表。问该公司对哪几种工程投标可能获得的总利润最大？试建立这个问题的数学模型。工程项目预期利润（万元）土石方量（m3）混凝土量（m3）其他材料（m2）A1542002802500A282300880480A37.548003001500A4923009005200施工能力1200016009000第二节0-1规划p70例3-113设那么建立的数学模型第二节0-1规划建模456每个变量都只取0，1两个值，变量取值的0-1组合是有限的。先列出各变量分别取0或1值的每一种组合，然后在满足约束条件的变量的0-1组合中找出使目标函数到达最优值的组合即是该0-1规划的最优解。用这种方法求解变量个数为n的0-1规划，通常需检查2n个组合。计算量大，随变量数量的增加呈集合级数增长第二节0-1规划0-1规划求解方法——穷举法7设计一种方法，只要检查变量取值的一局部就能得到原问题的最优解。这种方法称为隐枚举法。第二节0-1规划8第二节0-1规划例3-14(p71)9过滤条件第二节0-1规划通过试探的方法找到一个可行解。容易看出,(x1,x2,x3)=(0,0,1)是满足约束条件的可行解。相应的目标函数值为S=5。系数重排max型，目标函数中变量系数小-->大min型，相反容易观察增加过滤条件(filteringconstraint)10〔0〕第二节0-1规划约束条件重排序解约束条件是否满足条件？z值（0）（1）（2）（3）（4）（0，0，0）0（0，0，1）5-11015（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）802118（1，1，0）1（1，1，1）6用全部枚举的方法，3个变量共有8种组合原先4个约束方程，需要32次计算增加过滤条件后，可减少计算次数不符合过滤条件的，就不需要继续计算其余的约束方程了0-1型整数规划的解法：隐枚举法12第二节0-1规划系数、约束条件等重排序非必要更新过滤条件当遇到可行解的目标值大于过滤条件〔0〕当前的右端值时，应及时将〔0〕右端值换成大者。一家移动通信公司准备在四个候选的位置中挑选几个来建造信号发射基站，以便覆盖一个城市中的四个地区。这四个位置对于四个区的覆盖与修建费用如下表所示〔在一个位置所在列与一个地区所在行的交叉点处有数字“1〞说明在该位置建造信号发射基站时信号可以覆盖对应的地区〕：要求：构造一个线性规划模型，用规划求解工具确定一种基站建设方案，使得既能将四个地区都覆盖，又使建站总费用到达极小。13求解结果：1415第三节指派问题有n项任务，分配给n个人去完成，要求每个人完成其中一项任务，每项任务只交给其中一个人完成，每个人完成各项任务的本钱〔或效率〕，求使总本钱最少的分配方案。任务分配问题；指派问题；资源分配问题〔AssignmentProblem,AP〕16有四个熟练工人，他们都是多面手，有四项任务要他们完成。假设规定每人必须完成且只完成一项任务，而每人完成每项任务的工时消耗如表，问如何分配任务使完成四项任务的总工时消耗最少？第三节指派问题例117第三节指派问题xij

为第i个工人分配去做第j

项任务；aij

为第i

个工人为完成第j

项任务时的工时消耗；{aij}mm

称为效率矩阵18

目的地车辆编号D1D2D3D4D5D6146665559202822481256225913282239502786446314547545856544644331606322434243364设某运输队有6辆卡车，需分派驶往6个不同的目的地，由于各辆卡车的性能、消耗和效率不同，因而驶往各目的地的运输本钱也不同，如下表所示。试求能使总本钱最低的车辆分派方案。效率矩阵第三节指派问题例219第三节指派问题20第三节指派问题AP不但是整数规划，而且是01规划；AP有2m个约束条件，但有且只有m个非零解，是自然高度退化的。21第三节指派问题根据定理1变换效率矩阵，使矩阵中有足够多的零。假设矩阵中存在m个不同行不同列的零，就找到了最优解假设覆盖变换后的效率矩阵零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零匈牙利算法AP求解根本思路AP求解算法22

有5辆公交车可以在5条公交线路上行驶。不同车辆在不同的路线上发生的年平均交通事故数如下表所示。这5辆公交车如何分配，才能使全年的总事故数最少？匈牙利法的解题步骤

线路编号车辆R1R2R3R4R5D173328D2108697D392706D460835D553427第三节指派问题例求解〔匈牙利法〕23使费用矩阵出现0元素332886972706083553427110620312706083531205初始效率矩阵第三节指派问题第一步：变换效率矩阵，使每行每列至少有一个零(不能出现负值)行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之2110512030627053083401204行变换列变换24第三节指派问题第二步：找出所以位于不同行，不同列的零元素，即独立零元素；并用最少条数的直线覆盖全部零元素；21105120306270530834012042110512030627053083401204如果是MM矩阵，而又要使最优解分配在0元素位置上，划线数量应为M。本例还没有到达最优解。25在未划线的元素中找出最小元素未划线的各元素减去这个最小元素两直线交叉划线的各元素加上这个最小元素其余元素不变2100423040626043073301113第三节指派问题第三步：再变换矩阵来增多独立零元素个数；26第一辆车在3号线路第二辆车在5号线路第三辆车在4号线路第四辆车在2号线路第五辆车在1号线路第三节指派问题第四步：得到一个新矩阵，转到第二步，重复前述步骤，再检验。21004230406260430733011132728找到原效率矩阵最大元素m，以m减去原效率矩阵各元素值，那么新矩阵的最小化AP与原问题有同解第三节指派问题最大化AP人数和事数不等的AP一人可作几件事的AP某事一定不能由某人做的AP将相应的费用系数取足够大的数M将此人虚化成多个人，费用系数相同。增加虚拟的人或事，其本钱系数均为029某出租汽车公司有5辆出