整数规划运筹学交大工商管理讲义PPT课件.ppt

第四章整数规划 IntegerProgramming IP 整数规划 IntegerProgramming 主要是指整数线性规划 一个线性规划问题 如果要求部分决策变量为整数 则构成一个整数规划问题 所有变量都要求为整数的称为纯整数规划 PureIntegerProgramming 或称全整数规划 AllintegerProgramming 仅有一部分变量要求为整数的称为混合整数规划 MixedIntegerProgramming 有的变量限制其取值只能为0或1 这类特殊的整数规划称为0 1规划 0 1IntegerProgramming 整数规划的有关概念 一 整数规划问题例4 1某工厂生产甲 乙两种设备 已知生产这两种设备需要消耗材料A 材料B 有关数据如下 问这两种设备各生产多少使工厂利润最大 第一节整数规划问题及其数学模型 解 设生产甲 乙这两种设备的数量分别为x1 x2 由于是设备台数 则其变量都要求为整数 建立模型如下 Maxz 3x1 2x22x1 3x2 14x1 0 5x2 4 5x1 x2 0 且为整数 要求该模型的解 不考虑整数约束条件 用单纯形法对相应线性规划求解 其最优解为 x1 3 25x2 2 5maxz 14 75 凑整得到的 4 2 不在可行域范围内 3 2 点尽管在可行域内 但没有使目标达到极大化 4 1 使目标函数达到最大 即z 14 二 整数规划数学模型的一般形式 由上述例子可得出整数规划数学模型的一般形式 Maxz CXAX bX 0 且为整数或部分为整数若称该整数规划问题为原问题 则线性规划问题 Maxz CXAX bX 0为原问题对应的松驰问题 LPRelaxation 显然 原问题与松弛问题有如下关系 松弛问题可行域包含原问题可行域 若两者都有最优解 则松弛问题最优解大于原问题最优解 若松弛问题最优解为整数解 则该最优解就是原问题最优解 整数规划常用的解法有分枝定界法和割平面法 它们适用于解纯整数规划问题和混合整数规划问题 一 分枝定界法基本思想二 割平面法基本思想三 整数规划的计算机解法计算机求解举例 第二节整数规划的解法 第三节0 1整数规划 一 0 1整数规划模型0 1整数规划在实际中应用较多 因为实际问题中经常碰到大量的决策问题 要求回答 是 否 或 有 无 问题 这类问题可以借助整数规划中的0 1整数变量 使许多复杂的 困难的问题相对变得简单 0 1变量一般可表示为 0 1整数规划的数学模型可表示为 第三节0 1整数规划 二 0 1整数规划求解0 1整数规划的求解方法有穷举法 隐枚举法和分枝定界法 隐枚举法求解举例 解 1 先用试探的方法找出一个初始可行解 如x1 x2 0 x3 1 满足约束条件 选其作为初始可行解 目标函数z0 2 2 附加过滤条件以目标函数作为过滤约束 4x1 3x2 2x3 2原模型变为 3 求解求解过程如表4 6所示 一 相互排斥的计划 Mutuallyexclusiveplanning 例4 6某公司拟在市东 西 南三区中建立门市部 有例7个点Ai i 1 2 7 可供选择 要求满足以下条件 1 在东区 在A1 A2 A3三个点中至多选两个 2 在西区 A4 A5两个点中至少选一个 3 在南区 A6 A7两个点为互斥点 4 选A2点必选A5点 若Ai点投资为bi万元 每年可获利润为ci万元 投资总额为B万元 试建立利润最大化的0 1规划模型 第四节0 1整数规划应用 Applications 解 设决策变量为 建立0 1规划模型如下 例4 7某产品有A1和A2两种型号 需要经过B1 B2 B3三道工序 单位工时和利润 各工序每周工时限制见表所示 问工厂如何安排生产 才能使总利润最大 B3工序有两种加工方式B31和B32 产品为整数 二 互排斥的约束条件 Mutuallyexclusiveconstraints 解 设A1 A2产品的生产数量分别为x1 x2件 在不考虑B31和B32相互排斥的情况下 问题的数学模型为 工序B3只能从两种加工方式中选择一种 那么约束条件 1 和 2 就成为相互排斥的约束条件 为了统一在一个问题中 引入0 1变量 则数学模型为 一般地 在建立数学模型时 若需从p个约束条件中选择q个约束条件 则可以引入p个0 1变量 那么约束条件组 例4 8某公司制造小 中 大三种尺寸的容器 所需资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如下表所示 不考虑固定费用 小 中 大号容器每售出一个其利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人 月 机器有100台 月 另外若生产 不管每种容器生产多少 都需要支付一笔固定费用 小号为100万元 中号为150万元 大号为200万元 问如何制定生产计划使获得的利润对大 三 固定成本问题 Fixedcostproblem 解 设x1 x2 x3分别为小号容器 中号容器 大号容器的生产数量 不考虑固定费用 则问题的数学模型为 若考虑固定费用就必须引入0 1变量 则该问题的数学模型为 例4 9某城市消防队布点问题 该城市共有6个区 每个区都可以建消防站 市政府希望设置的消防站最少 但必须满足在城市任何地区发生火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间见表4 9 请帮助该市制定一个布点最少的计划 四 布点问题 LocationProblem 表4 9消防车在各区间行驶时间表单位 min 本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内 如地区1 由表4 9可知 在地区1及地区2内设消防站都能达到此要求 即x1 x2 1因此本问题的数学模型为 minz x1 x2 x3 x4 x5 x6x1 x2 1x1 x2 x6 1x3 x4 1x3 x4 x5 1x4 x5 x6 1x2 x5 x6 1xi 1或0 i 1 6 解 引入0 1变量xi作决策变量 令 资金预算 Capitalbudgetingproblem 冰冷电冰箱公司正在考虑4种投资方案 有关数据如下表 问题 选择投资项目使总现值最大 五 其他案例 引入4个0 1变量 P 1 工厂扩建通过 P 0 则不选工厂扩建 W 1 仓库扩建通过 P 0 则不选仓库扩建 M 1 机器更新通过 P 0 则不选机器更新 R 1 新产品研究通过 P 0 则不选新产品研究 则问题的0 1规划数学模型为 MaxZ 90P 40W 10M 37R15P 10W 10M 15R 4020P 15W 10R 5020P 20W 10R 4015P 5W 4M 10R 50P W M R 0 1 固定成本 Fixedcostproblem 生产三种产品需要用三种原料 生产这些产品需要配置成本 若不需要 则无配置成本 有关数据如下表 问题 各产品应生产多少总利润最大 设 F 添加剂生产量 S 溶剂生产量 C 清洁剂生产量 引入3个0 1变量 若生产添加剂 SF 1 否则SF 0 若生产溶剂 SS 1 否则SS 0 若生产清洁剂 SC 1 否则SC 0 则问题的0 1规划数学模型为 MaxZ 40F 30S 50C 200SF 50SS 400SC0 4F 0 5S 0 6C 200 2S 0 1C 50 6F 0 3S 0 3C 21F 50SF 0S 25SS 0C 40SC 0F S C 0 SF SS SC 0 1 分销系统设计 Distributionsystemdesignproblem 马丁贝克公司在圣路易斯经营一家生产量为30000件产品的工厂 产品被运输到位于波士顿 亚特兰大和休斯敦的地区分销中心 由于预期将有需求增长 公司计划在底特律 托来多 丹佛和堪萨斯中一个或多个城市建立新工厂以增加生产力 有关数据如下表 问题 各选择哪个或哪些工厂使总成本最小 在不考虑固定成本和生产地选择的情况下 此问题是一个运输问题 若用xij表示从产地i到分销中心j的运量 则其数学模型为 Minf 5x11 2x12 3x13 4x21 3x22 4x23 4x52 3x53x11 x12 x13 10 x21 x22 x23 20 x31 x32 x33 30 x41 x42 x43 40 x51 x52 x53 30 x11 x21 x31 x41 x51 30 x12 x22 x32 x42 x52 20 x13 x23 x33 x43 x53 20 xij 0 所有i j 若考虑固定成本和生产地的选择需要引入0 1变量 若在底特律建立工厂 y1 1 否则y1 0 若在托来多建立工厂 y2 1 否则y2 0 若在丹佛建立工厂 y3 1 否则y3 0 若在堪萨斯建立工厂 y4 1 否则y4 0 若用xij表示从产地i到分销中心j的运量 则其数学模型为 minf 5x11 2x12 3x13 4x52 3x53 175y1 300y2 375y3 500y4x11 x12 x13 10y1 0 x21 x22 x23 20y2 0 x31 x32 x33 30y3 0 x41 x42 x43 40y4 0 x51 x52 x53 30 x11 x21 x31 x41 x51 30 x12 x22 x32 x42 x52 20 x13 x23 x33 x43 x53 20 xij 0 所有i j y1 y2 y3 y4 0 1 银行选址 Locationproblem 俄亥俄州信托投资公司的远期计划正在考虑在俄亥俄州东北部20个郡的地区开展业务 该投资公司目前在这20个郡还没有主营业处 根据该州法律 如果一个银行在任一个郡建立主营业处 即可在该郡及所有毗邻郡建设分行 该计划的第一步是 投资公司需要确定为了在这20个郡完全营业一共要建立的主营业处的最小数目 若在第i郡建立主营业处 则xi 1 否则xi 0这样 目标函数为 minz x1 x2 x20每个郡要满足一个约束条件 该郡或与该郡相毗邻的郡中至少有一个需要建立主营业处 例如第10个郡有 x3 x9 x8 x11x10 x12 x13 1因此 该问题的数学模型为 minz x1 x2 x20 x1 x2 x12 x16 1 第1个郡 x1 x2 x3 x12 x16 1 第2个郡 x2 x3 x4 x9 x10 x12 x13 1 第3个郡 x11 x14 x19 x20 1 第20个郡 xi 0 1I 1 2 20 产品设计和市场份额的优化 Productdesignandmarketshareoptimizationproblem 决策变量 xij 1 表示赛伦pizza在属性j上选择i 否则xij 0yk 1 顾客i选择赛伦pizza 否则yk 0这样 目标函数为 选择赛伦pizza的顾客数最大 即maxz y1 y2 y3 y4 y5 y6 y7 y8约束条件 1 若果顾客i选择赛伦 则他认为赛伦的效用比他目前中意的品牌的效用还要大 例如第1个顾客 目前中意的pizza是安东尼奥 效用为52 因此 11x11 2x21 6x12 7x22 3x13 17x23 26x14 27x24 8x34 1 52y1 2 赛伦在每中属性中只能选择一种 即x11 x21 1x12 x22 1x13 x23 1x14 x24 x34 1 因此 该问题的数学模型为 maxz y1 y2 y3 y4 y5 y6 y7 y811x11 2x21 6x12 7x22 3x13 17x23 26x14 27x24 8x34 1 52y111x11 7x21 15x12 17x22 16x13 26x23 14x14 1x24 10 x34 1 58y27x11 5x21 8x12 14x22 16x13 7x23 29x14 16x24 19x34 1 56y313x11 20 x21 20 x12 17x22 17x13 14x23 25x14 29x24 10 x34 1 83y42x11 8x21 6x12 11x22 30 x13 20 x23 15x14 5x24 12x34 1 58y512x11 17x21 11x12 9x22 2x13 30 x23 22x14 12x24 20 x34 1 70y69x11 19x21 12x12 16x22 16x13 25x23 30 x14 23x24 19x34 1 79y75x11 9x21 4x12 14x22 23x13 16x23 16x14 30 x24 3x34 1 59y8x11 x21 1x12 x22 1x13 x23 1x14 x24 x34 1xij yk 0 1对于所有i j k求解结果 x11 x22 x23 x14 1 y1 y2 y3 y6 y7 1 五 指派问题 Assignmentproblem 指派问题是一种特殊的整数规划问题 在实践中经常会遇到一种问题 某单位有m项任务要m个人去完成 每人只完成一项工作 在分配过程中要充分考虑各人的知识 能力 经验等 应如何分配才能使工作效率最高或消耗的资源最少 这类问题就属于指派问题 引入0 1变量xij 案例 福尔市场营销调查指派问题福尔市场营销调查公司有3个新客户需要进行市场调查 目前正好有3个人没有其他工作 由于他们的对不同市场的经验和能力不同 估计他们完成不同任务所需时间如下表 公司面临的问题是如何给每个客户指派一