第七章选址问题及隐枚举法

1、1第一节第一节 整数规划整数规划第二节第二节 0-1规划规划第三节第三节 指派问题指派问题第四节第四节 整数规划的应用整数规划的应用2 某道桥公司在同一时间内可参加某道桥公司在同一时间内可参加A A1 1、A A2 2、A A3 3、A A4 4四项工程的四项工程的投标。这些项目要求的工期相同。公司根据招标文件和本投标。这些项目要求的工期相同。公司根据招标文件和本公司的技术水平对每项工程进行了仔细的研究和计算，将公司的技术水平对每项工程进行了仔细的研究和计算，将各项工程的预期利润，主要工序的工程量及本企业的施工各项工程的预期利润，主要工序的工程量及本企业的施工能力见小表。问该公司对哪几种项目投

2、标可能获得的总利能力见小表。问该公司对哪几种项目投标可能获得的总利润最大？试建立这个问题的数学模型。润最大？试建立这个问题的数学模型。 工程项目工程项目预期利润（万元）预期利润（万元）土石方量（土石方量（m3）混凝土量（混凝土量（m3）其他材料（其他材料（m2）A1542002802500A282300880480A37.548003001500A4923009005200施工能力施工能力1200016009000第二节第二节 0-1规划规划3, 4 , 3 , 2 , 1 , , 0 , 1iAxii否则投资对项目4 , 3 , 2 , 11 090005200150048025001600

3、900300880280120003200480023004200 s.t.95 . 785max 4321432143214321ixxxxxxxxxxxxxxxxxzi，或设则建立的数学模型第二节第二节 0-1规划规划 建模建模456 每个变量都只取每个变量都只取0 0，1 1两个值，变量取值的两个值，变量取值的0-10-1组合组合是有限的。是有限的。 先列出各变量分别取先列出各变量分别取0 0或或1 1值的每一种组合，然后值的每一种组合，然后在满足约束条件的变量的在满足约束条件的变量的0-10-1组合中找出使目标函组合中找出使目标函数达到最优值的组合即是该数达到最优值的组合即是该0-10

4、-1规划的最优解。规划的最优解。 用这种方法求解变量个数为用这种方法求解变量个数为n n的的0-10-1规划，通常需规划，通常需检查检查2 2n n个组合。个组合。 计算量大，随变量数量的增加呈集合级数增长计算量大，随变量数量的增加呈集合级数增长 7 设计一种方法，只要检查变量取值的一部分就能得到原设计一种方法，只要检查变量取值的一部分就能得到原问题的最优解。问题的最优解。 这种方法称为这种方法称为隐枚举法隐枚举法。8321523maxxxxz 10,4 643 32 441 223123212312312或xxxxxxxxxxxxx9213max235zxxx 213213212321322

5、 (1)44 (2)3 (3)46 (4),01xxxxxxxxxxxxx或2132+355xxx过滤条件过滤条件 通过试探的方法找到一个可行解。通过试探的方法找到一个可行解。容易看出容易看出,(x1,x2,x3)=(0,0,1)是满足约束条件的可行解。是满足约束条件的可行解。相应的目标函数值为相应的目标函数值为S=5。 系数重排系数重排nmax型，目标函数中变量系数小型，目标函数中变量系数小-大大nmin型，相反型，相反n容易观察容易观察 增加过滤条件增加过滤条件(filtering constraint)10213max2+35zxxx 213213212321322 144 23 346

6、 4,01xxxxxxxxxxxxx或2132+355xxx（0 0） 约束条件重排序约束条件重排序解解约束条件约束条件是否满足条是否满足条件？件？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 系数、约束条件等重排序非必要系数、约束条件

7、等重排序非必要 更新过滤条件更新过滤条件 当遇到可行解的目标值大于过滤条件当遇到可行解的目标值大于过滤条件（0）当前的右端值时，应及时将（）当前的右端值时，应及时将（0）右端值换成大者。右端值换成大者。 一家移动通信公司准备在四个候选的位置中挑选几个一家移动通信公司准备在四个候选的位置中挑选几个来建造信号发射基站，以便覆盖一个城市中的四个地来建造信号发射基站，以便覆盖一个城市中的四个地区。这四个位置对于四个区的覆盖与修建费用如下表区。这四个位置对于四个区的覆盖与修建费用如下表所示（在一个位置所在列与一个地区所在行的交叉点所示（在一个位置所在列与一个地区所在行的交叉点处有数字处有数字“1 1”表

8、明在该位置建造信号发射基站时信表明在该位置建造信号发射基站时信号可以覆盖对应的地区）：号可以覆盖对应的地区）： 要求：构造一个线性规划模型，用规划求解工具确定要求：构造一个线性规划模型，用规划求解工具确定一种基站建设方案，使得既能将四个地区都覆盖一种基站建设方案，使得既能将四个地区都覆盖，又又使建站总费用达到极小。使建站总费用达到极小。13 求解结果：求解结果：1415 有有n n项任务，分配给项任务，分配给n n个人去完成，要求每个个人去完成，要求每个人完成其中一项任务，每项任务只交给其中一人完成其中一项任务，每项任务只交给其中一个人完成，已知每个人完成各项任务的成本个人完成，已知每个人完成

9、各项任务的成本（或效率），求使总成本最少的分配方案。（或效率），求使总成本最少的分配方案。 任务分配问题；指派问题；资源分配问题任务分配问题；指派问题；资源分配问题（Assignment Problem, AP）16有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表，问如何分配任务使完成四项任务的总工时耗费最少？任务任务 工时工时ABCD人员人员人员人员甲甲109781乙乙58771丙丙54651丁丁23451任务任务111117xij 为第 i 个工人分配去做第 j 项任务；aij 为第 i 个工人为完成第 j 项任务时

10、的工时消耗；aijmm 称为效率矩阵mjijijixij, 2 , 1,01项任务项任务个工人未分配去做第个工人未分配去做第当第当第项任务项任务个工人分配去做第个工人分配去做第当第当第1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx18 目的地目的地车辆编号车辆编号D D1 1D D2 2D D3 3D D4 4D D5 5D D6 61 14646666655555959202028282 22424818125256262252591913 32828222239395050272786864 4464631314545474

11、7545458585 56565444464644343313160606 6323224243434242433336464设某运输队有6辆卡车，需分派驶往6个不同的目的地，由于各辆卡车的性能、消耗和效率不同，因而驶往各目的地的运输成本也不同，如下表所示。试求能使总成本最低的车辆分派方案。 效率矩阵19否则目的地号车辆驶往第若分派第 , 1 , 0jixij6 , 2 , 1,ji666564636261565554535251464544434241363534333231262524232221161514131211643324342432 603143644465 585447453

12、146 8627503962228 912562258124 282059556646min xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz6 , 2 , 1, 1, 06 , 2 , 1 , 16 , 2 , 1 , 1 s.t.6161jixjxixijiijjij或20AP不但是整数规划，而且是不但是整数规划，而且是0 1规划；规划；AP有有2m个约束条件，但有且只个约束条件，但有且只有有m个非零解，是自然个非零解，是自然高度退化高度退化的。的。1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx21

13、根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零匈牙利算法匈牙利算法22 有有5 5辆公交车可以在辆公交车可以在5 5条公交线路上行驶。不同车条公交线路上行驶。不同车辆在不同的路线上发生的年平均交通事故数如下辆在不同的路线上发生的年平均交通事故数如下表所示。这表所示。这5 5辆公交车如何分配，才能使全年的总辆公交车如何分配，才能使全年的总事故数最少？事故数最少？匈牙利法的解题步骤匈牙利法的解题步骤 线路编号线路编号车辆车辆R1R2R3R4R5D17

14、3328D2108697D392706D460835D55342723使费用矩阵出现使费用矩阵出现0元素元素 3 3 2 8 8 6 9 7 2 7 0 6 0 8 3 55 3 4 2 7 1 1 0 6 2 0 3 1 2 7 0 6 0 8 3 53 1 2 0 5初始效率矩阵初始效率矩阵第一步：变换效率矩阵，使每行每列至少有一个零(不能出现负值) 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4行变换行变换列变换列变换24第二步第二步：找出所以位于不同

15、行，不同列的零元素，：找出所以位于不同行，不同列的零元素，即独立零元素；并用最少条数的直线覆盖全部零元即独立零元素；并用最少条数的直线覆盖全部零元素；素；2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 42 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4如果是MM矩阵，而又要使最优解分配在0元素位置上，划线数量应为M。本例还没有达到最优解。25在未划线的元素中找出在未划线的元素中找出最小元素最小元素未划线的各元素减去这个最小元素未划线的各元素减去这个最小元素两直线交叉划线的各元素加上这个最小元素两直线交叉划线的各元

16、素加上这个最小元素其余元素不变其余元素不变2 1 0 0 42 3 0 4 06 2 6 0 43 0 7 3 30 1 1 1 3第三步第三步：再变换矩阵来增多独立零元素个数；：再变换矩阵来增多独立零元素个数；26第一辆车在第一辆车在3 3号线路号线路 第二辆车在第二辆车在5 5号线路号线路第三辆车在第三辆车在4 4号线路号线路 第四辆车在第四辆车在2 2号线路号线路第五辆车在第五辆车在1 1号线路号线路第四步第四步：得到一个新矩阵，转到第二步，重复前述步：得到一个新矩阵，转到第二步，重复前述步骤，再检验。骤，再检验。2 1 0 0 42 3 0 4 06 2 6 0 43 0 7 3 30 1 1 1 32728 找到原效率矩阵最大元素找到原效率矩阵最大元素m，以，以m减去原效率矩阵减去原效率矩阵各元素值，则新矩阵的最小化各元素值，则新矩阵的最小化AP与原问题有同