管理运筹学-第五章-整数规划.pptVIP

非标准形式指派问题的处理 1、最大化指派问题：目标函数求max 最大元素：m将原系数矩阵C转换为B 最大化指派问题例题 有5个工人，要指派去做5项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得分最大？ J1 J2 J3 J4 J5 S1 S2 S3 S4 S5 15 5 1 7 12 5 11 0 12 9 3 13 13 0 8 0 8 5 3 9 12 10 6 8 12 工人 工作 √-3 √ +3 √-1 2、人数≠事数 人数事数：添加虚拟“人”，c = 0 人数事数：添加虚拟“事”， c = 0 3、一个人可以做几件事 将一人化为相同的多个人来接受指派，这多个人做同一件事的费用相同 4、某事不能由某人来做 将相应的费用系数取无穷大M 一个人做多件事 例5.12 某大型工程共由5个项目A、B、C、D、E组成，现有三个公司甲、乙、丙分别来投标，各自给出的报价如下表所示。这里甲乙丙三家公司实力均比较雄厚，可以同时进行两个项目的施工，请给出最优施工分配方案。 A B C D E 甲 15 17 9 12 18 乙 14 18 10 11 16 丙 12 19 12 13 15 一人做两事 人多事少 第五章 整数规划 5.1 整数规划实例及一般模型 5.2 分支定界法 5.3 0-1整数规划 5.4 指派问题 5.1 整数规划实例 例5.1 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示。 货物 每件体积/立方英尺 每件重量/百千克 每件利润/百元 甲 195 4 2 乙 273 40 3 托运限制 1365 140 甲种货物至多托运4件，问两种货物各托运多少件， 可使获得利润最大？ 解 设x1、x2分别为甲、乙两种货物托运的件数，建立模型 5.1 整数规划实例 例5.2 某服务部门各时段（每2小时为一时段）需要的服务员人数如下表。按规定，服务员连续工作8个小时（4个时段），问如何安排服务员，使服务员总数最少。 时段 1 2 3 4 5 6 7 8 服务员最少所需人数 10 8 9 11 13 8 5 3 例5.3 某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂，已知在A2地建厂的固定成本为175千元，在A3地建厂的固定成本为300千元，在A4地建厂的固定成本为375千元，在A5地建厂的固定成本为500千元，另外，在A1的产量，A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价（每千箱运费）如下表5-3所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小？ 如果A2和A3两地必须有且只有一个建厂，怎么办？ 1、整数规划数学模型的一般形式 整数规划问题的松弛问题 xj部分或全部取整数 整数规划的类型 纯整数规划：变量全部是整数 混合整数规划：变量部分整数，部分非整数 0-1型整数规划：变量= 0或1 * 整数规划对应松弛问题最优解为： x1=2.44, x2=3.26,目标函数值为14.66。 整数规划的最优解为：x1=4, x2=2,目标函数值为14。 1 2 3 4 1 2 3 2x1+3x2 =14.66 x1 x2 2x1+3x2 =14 2x1+3x2 =6 整数规划解的特点（与松弛问题的关系） 1、整数规划的可行解集合是其松弛问题可行解集合的子集 ；整数规划最优解的目标函数值不会优于松弛问题最优解的目标函数值。 2、整数规划的最优解不一定是对松弛问题最优解变量的简单取整。 5.2 分支定界法 分支：若松弛问题最优解中存在变量xi=bi′不满足整数约束，记[bi′]为不超过bi′的最大整数，则构造两个新 的约束xi≤ [bi′] ，和xi≥ [bi′]+1。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它们的分支。 定界：在分支的过程中，若某个后继问题恰好获得了整数规划的一个可行解，则这一可行解的目标函数值可看成一个“界限”，作为处理其他分支的依据。 例5.4 求解如下整数规划： 首先求解其松弛规划： 最优解为X=(3.25,2.5)’，z=14.75 因为x1=3.25，所以将其分为x1=3和x1=4两个分支 因为x2=8/3，所以将其分为x2=2和x2=3两个分支 所以X*=(4,1)，Z*=14 5.3 0-1ILP 例5.5 广州某食品公司计划在市区的东、西、南、北四区建立销售门市部，目前有10个位置可供选择，考虑到各地区居民的消费水平及居民居住密集