[管理学]IE10_OR12 CH3 运输问题4 and CH4 整数规划.ppt

第12讲目录 转运问题 补充证明 CH4整数规划 4 1整数规划问题的数学模型及解的特点 4 2分支定界法 4 30 1整数规划 4 4指派问题 4 5应用举例 转运问题 证明 例2 某公司有A1 A2 A3三个分厂生产某种物资 分别供应B1 B2 B3 B4四个地区的销售公司销售 假设质量相同 有关数据如下表 试求总费用为最少的调运方案 假设 1 每个分厂的物资不一定直接发运到销地 可以从其中几个产地集中一起运 2 运往各销地的物资可以先运给其中几个销地 再转运给其他销地 3 除产销地之外 还有几个中转站 在产地之间 销地之间或在产地与销地之间转运 运价如下表 解 把此转运问题转化为一般运输问题 1 把所有产地 销地 转运站都同时看作产地和销地 2 运输表中不可能方案的运费取作M 自身对自身的运费为0 3 Ai 产量为20 原产量 销量为20 Ti 产量 销量均为20 Bi 产量为20 销量为20 原销量 其中20为各点可能变化的最大流量 4 对于最优方案 其中xii为自身对自身的运量 实际上不进行运作 扩大的运输问题产销平衡与运价表 4 1整数规划问题的数学模型及解的特点 整数线性规划问题的一般形式 例1 某公司拟用集装箱托运甲 乙两种货物 这两种货物每件的体积 重量 可获利润以及托运所受限制如表所示 甲种货物至多托运4件 问两种货物各托运多少件 可使获得利润最大 解 设x1 x2分别为甲 乙两种货物托运的件数 建立模型目标函数 Maxz 2x1 3x2约束条件 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0为整数 整数线性规划问题的分类 全整数线性规划混合整数线性规划0 1整数线性规划 整数规划与其松弛问题 当放弃整数约束时得到的线性规划称为整数规划的松弛问题 整数规划的可行域是松弛问题的可行域 反之不成立 4 2分支定界法 混合整数规划的求解 分枝定界方法 分枝 当不符合整数要求时 构造两个约束条件 加入松弛问题分别形成两个子问题 分枝 定界 当子问题获得整数规划的一个可行解 则它的目标函数值就构成一个界限 例1 S 解S得 29 6 S2 对S分枝 构造约束 和 形成分枝问题S1和S2 得解B和C S1 1 3 2 X 2 5 4 S2 对S1分枝 构造约束 和 形成分枝问题S11和S12 得解D S12 S11无可行解 1 3 2 X 2 5 4 S2 对S12分枝 构造约束 和 形成分枝问题S121和S122 得解E和F S121 S122 例2用分枝定界法求解 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0整数用单纯形法可解得相应的松驰问题的最优解 6 5 21 10 Z 111 10为各分枝的上界 01234 4321 x1 x2 分枝 X1 1 x1 2 P1 P2 两个子问题 P1 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 整数用单纯形法可解得相应的 P1 的最优解 1 9 4 Z 43 4 P2 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 2 整数用单纯形法可解得相应的 P2 的最优解 2 1 2 Z 19 2 01234 4321 x1 x2 再对 P1 分枝 X1 1 P3 x2 2 P4 x2 3 P1 P2 P3 P4 P1 两个子问题 P3 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 x2 2整数用单纯形法可解得相应的 P3 的最优解 1 2 Z 10 P1 两个子问题 P4 MaxZ 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 1 x2 3整数用单纯形法可解得相应的 P4 的最优解 0 3 Z 9 X1 2 X2 2 X1 1 X2 3 P1 1 9 4 Z 43 4 P4 0 3 Z 9 P2 2 1 2 Z 19 2 P3 1 2 Z 10 P 6 5 21 10 Z 111 10 原问题的最优解 1 2 Z 10 4 30 1整数规划 1 0 1整数规划 变量只能取0或1的整数线性规划 2 0 1规划的应用 例1项目投资预算 模型 变量假设 模型 例2 一登山队员做登山准备 他需要携带的物品有 食品 氧气 冰镐 绳索 帐篷 照相机和通讯设备 每种物品的重要性系数和重量如下 假定登山队员可携带最大重量为25公斤 解 如果令xi 1表示登山队员携带物品i xi 0表示登山队员不携带物品i 则问题表示成0 1规划 MaxZ 20 x1 15x2 18x3 14x4 8x5 4x6 10 x7s t 5x1 5x2 2x3 6x4 12x5 2x6 4x7 25xi 1或xi 0i 1 2 7 背包问题 KnapsackProblem 一个旅行者 为了准备旅行的必须用品 要在背包内装一些最有用的东西 但有个限制 最多只能装b公斤的物品 而每件物品只能整个携带 这样旅行者给每件物品规定了一个 价值 以表示其有用的程度 如果共有n件物品 第j件物品aj公斤 其价值为cj 问题变成 在携带的物品总重量不超过b公斤条件下 携带哪些物品 可使总价值最大 解 如果令xj 1表示携带物品j xj 0表示不携带物品j 则问题表示成0 1规划 MaxZ cjxjs t ajxj bxj 0或1 例3工厂 销售点配置问题 工厂 销售点配置问题 问题描述 问题 为使经营成本最低 应开设那些工厂及销售点 工厂 销售点配置问题 模型参数 工厂 销售点配置问题 模型 解法概述因为可行方案数目有限 因此经过一一比较后 总能求出最好方案 例如 背包问题充其量有2n 1种方式 连线问题充其量有n 种方式 实际上这种