数据模型决策05网络优化（PPT64页).ppt

第5章 网络优化 所谓网络优化 简单地说 即对网络进行定性和定量分析 以便为实现某种优化目标而寻求最优方案 这方面的典型问题有 最小支撑树问题 最小费用流问题 最大流问题 最短路问题 中心问题 重心问题 运输问题 指派问题等等 树图结构 最小支撑树问题 光缆通信连接问题某公园决定铺设最先进的光纤网络 为它的主要景点之间提供高速通信 数据 声音和录像 为了利用光纤技术在景点之间高速通信的优势 不需要在每两个景点之间都用一条光缆把他们直接联系起来 问题 确定需要铺设那些光缆使得提供给每个景点之间的高速通信的成本最低 公园光缆通信问题的路径系统 图中虚线表示可供选择的边 最佳的解决办法 由于任意两个节点之间均可以通信 这个图必须是连通图 并且 这个图必须是无圈的 否则 从圈上任意去掉一条边 剩下的图仍然满足条件 并且成本更小 树 图的专有名词 图G定义为点和边的集合 记为G V E 其中 是点的集合 是边的集合 有向图区别于无向图的关键 在于它的边 此时也称弧 是有方向的 一个图连同定义在其边集上的实函数一起称为一个网络 我们把定义在边集上的实函数称为边的权数 该网络记为 V E W 对于图G V E 如果任意两个节点间都可以由一条或几条边连起来 则称该图为连通图 连通并且不含圈的无向图称为树 若树 中点的集合等于图 的点的集合 树 中边的集合是图 的边的集合的子集 称树 为图 的支撑树 在所有的支撑树中总成本最小的树称为最小支撑树 最小支撑树问题的算法 选择第一条边 选择成本最低的备选边 图中虚线 选择下一条边 在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边 重复第2个步骤 直到所有的节点都有一条边 可能会有多于一条边 与其相连 此时 就得到了最优解 最小支撑树 其中第2步的目的是为了保证每次生成的树都是连接当前子图的所有顶点的成本最小的树 算法的应用 首次连接 V C D W A B E F G 从V中的节点连向W中节点的备选边中选择成本最小的一条边 算法的应用 第二次连接 V B C D W A E F G 算法的应用 第三次连接 V A B C D W E F G 算法的应用 第四次连接 V A B C D F W E G 算法的应用 第五次连接 V A B C D E F W G 算法的应用 最后的连接 V A B C D E F G 最小费用流问题 这里的流是一个广泛的概念 例如在交通运输网络中有人流 车流 货物流 供水系统中有水流 金融系统中有现金流 通信系统中有信息流 等等 问题的提出 在一个关于流的网络中 每一个流量都有一定的费用 流所走的路线不一样 单位费用不一样 同样数量的流量 因为走的路线不一样 总的费用也不一样 从而我们希望确定在给定网络流量的基础上 让流沿着怎样的路线走 能使总的费用最小 无限配送公司问题 无限配送公司有两家工厂生产产品 这些产品需要运到两个仓库 工厂1生产80个单位 工厂2生产70个单位 仓库1需要60个单位 仓库2需要90个单位 工厂1和仓库1之间以及工厂2和仓库2之间各有一条铁路运输轨道 卡车司机总共可以从每家工厂运输50个单位到配送中心 然后可以从配送中心运输50个单位到每个仓库 任何运输到配送中心的产品必须随后运送到仓库 问题 确定一个运输方案 即每条路线运送多少单位的产品 使得运输成本达到最小 网络模型 净流量 流出 流入 最小费用流的专有名词 网络中的圆圈被称为节点 如果节点要求的净流量 流出减去流入 是一个确定的正数的话 这个点就是一个供应点 如果节点要求的净流量 流出减去流入 是一个确定的负数的话 这个点就是一个需求点 若节点要求的净流量恒为0 这个点称为转运点 我们把流出接点的量等于流入节点的量称为流量守恒 在网络里的箭头被称为弧 允许通过某一条弧的最大流量被称为该弧的容量 最小费用流问题的假定 至少有一个节点是供应点 至少有一个节点是需求点 所有剩下的节点都是转运点 通过弧的流只允许沿着箭头的方向流动 通过弧的最大流量取决于该弧的容量 网络中有足够的弧提供足够的容量 使得所有在供应点产生的流都能够到达需求点 在流的单位成本已知的前提下 通过每一条弧的流的成本与流量成正比 费用系数是确定的 最小费用流问题的目标是在给定需求的条件下 使通过网络供应的总成本最小 一个网络模型 净流量 流出 流入 数学模型 最佳的解决办法 最小费用流问题的数学建模 设一个有n个节点 m条弧的网络图 每一个节点i都对应于一个数bi 表示该节点要求的净流量 如果bi 0 节点i为供应节点 供应量为bi 如果bi 0 则为需求节点 需求量为 bi 如果bi 0 该节点为转运点 对于一个网络 如果有 称为供求平衡的网络 网络所有弧 i j G上的流量xij 一共n个分量 组成的向量X xij 称为网络的一个流 网络中求流量分配使总流量达到一定要求 而总费用最低 如果网络的一个流满足以下条件 则这样的流称为可行流 a 平衡条件 对网络中的任一节点i 在网络中从节点i通过弧 i j 流向关联的他节点j的流量xij之和减去与节点i关联的其他节点j通过弧 j i 流入i的流量xji之和与该节点要求的净流量平衡 即 b 容量限制条件 数学模型 网络的每一弧 i j 都有一个单位流量的费用系数cij与它对应 如果弧 i j 上的流量为xij 则该弧上这些流量引起的费用为cijxij 网络最小费用流问题就是找到使总费用最小的可行流 模型有可行解的必要条件是 该网络是供求平衡的网络 即 为什么 最小费用流问题的数学建模 2 另一类最小费用流问题是在预算费用C给定的情况下 求流量分配 使得从能够输送的总流量达到最大 仍用决策变量表示通过弧 i j 的流量 表示弧 i j 的费用系数 表示弧 i j 上的容量 则数学模型为 最大流问题 一 有关概念 例 下图是输油管道网 为起点 为终点 为中转站 弧上的数字表示该管道的最大输油能力 也称容量 记为 问应如何安排各管道输油量 才能使从到的总输油量最大 分别称为发点 收点 其余的点称为转运点 每一个弧上都给定一个容量的网络称为容量网络 记 的每一个弧上都给定一个实际流量的网络称为给定了网络一个流 b 容量限制条件 对每一弧上都有 a 平衡条件 转运点 流出量 流入量 0 发收点 发点流出量 收点流入量 网络总流量 若 称弧是饱和弧 使网络总流量达到最大的可行流称为最大流 如果网络的一个流满足以下条件 则这样的流称为可行流 最大流问题的数学建模 用决策变量表示通过弧 i j 的流量 表示弧 i j 的容量 则数学模型为 BMZ公司的最大流问题 BMZ公司是欧洲一家生产豪华汽车的制造商 虽然它生产的汽车在所有发达国家销量都不错 对它来讲 出口到美国尤其重要 BMZ汽车正在加利福尼亚变得特别受欢迎 因此保证洛杉矶中心良好的供应显得特别的重要 大部分汽车配件以及新车是在该公司位于德国的斯图加特的总厂生产的 BMZ公司需要制定一个计划 使得下个月从总厂运送到洛杉矶配送中心的配件流尽可能大 可以运送多少配件的限制条件就是该公司配送网络的容量 问题 通过每条运输路线可以运送多少货物 使得从总厂运送到洛杉矶配送中心的配件流最大 BMZ销售网 BMZ的一个网络模型 A C B F E G 70 80 70 60 40 50 30 50 40 D 数学模型 最短路问题 最短路问题是网络理论中应用最广泛的问题之一 许多优化问题都可以使用这个模型 如设备更新 管道的铺设 线路的安排 厂区的布局等 最短路问题的一般提法是 设为连通图 图中各边或弧有权 表示 间没有边或弧 为图中任意两点 求一条道路 使它是从到的所有路中总权最小的路 即 最小 最短路问题的假定 在网络中选择一条路 这条路始于某一节点 叫做始点 并且终于另一个节点 叫终点 连结两个节点的连线通常叫做边 允许任一方向的行进 也允许存在弧 只允许朝一个方向行进 与每条边相关的一个非负数称为该边的长度 注意 边和弧也可能代表其他类型的活动 目标是为了选择从始点到终点的最短路 总长度最小的路 一个最短路问题的应用 为了实现更加人性化的服务 公园管理层需要面向游客出一本旅游线路指南的小册子 在该小册子中要告诉旅客从公园入口 各个景点之间以及入口之间的最短线路 问题 首先考虑从公园入口到公园出口的最短线路 由于最小 所以医院应建在F 此时离医院最远的景点A距离为7 中心问题 中心医务室应建在哪个景点 可使离医务室最远的景点游客就诊时所走的路程最近 重心问题 已知各景点的员工人数分别为40 25 45 30 20 35 50 则会议中心应建在哪个景点 可使所有员工在参加会议时间所走的总路程最短 由于最小 所以会议中心应建在C 公园的重心 各个景点员工人数40 25 45 30 20 35 50 有向网络最短路问题的数学建模 设始点为1 终点为n 引入0 1决策变量 如果弧 i j 在从始点到终点的某条路径上 则 否则 则数学模型为 使总成本最小的最短路问题 萨拉刚刚高中毕业 在毕业典礼上 她父母给了她21000美圆的汽车基金帮助她购买并保养一辆使用了3年的二手车 以供她上大学 由于开车费用 维修费用随着汽车的老化而飞速上涨 萨拉可以一次或者几次折价将她的汽车置换为其他使用了3年的二手车 在四年大学毕业后 她父母将送给她一辆新车 到那时她肯定计划把旧车折价买出 问题 在接下来的3个暑期 萨拉什么时候应该折价买掉她的汽车 如果必要的话 可以使得她在大学四年的开车 买车 保养汽车的总费用最小 萨拉花费数据 问题 在接下来的3个暑期 萨拉什么时候应该折价买掉她的汽车 如果必要的话 可以使得她在大学四年的开车 买车 保养汽车的总费用最小 最短路网络 解 把这个问题化为最短路问题 节点 表示现在 入学 节点 分别表示第一年年末 第二年年末 第三年年末 第四年年末 从一个节点到另外一个节点的弧表示在第一个节点这个时间买车 然后在第二个节点的那个时间把车折价卖掉的活动 最短路网络 弧长 买车的价格 使用和保养的费用 折价买出的价值 这样该问题就变为 求从节点 到节点 的最短路问题 数学模型 最短路问题也可看成最小费用流问题的特例 当确定从任一节点i至另一节点j的最短路时 只要作以下假定 1 当网络中任意两个节点之间存在连接的弧时 弧上的费用系数等于该弧的长度 2 作为起点的节点i为供应节点且其净流出量为1 作为终点的节点j为需求节点且其净流出量为 1 所有其他节点的净流出量为零 3 总费用等于从节点i 起点 到节点j 终点 所经过的各条弧的长度之和 目标函数是总费用最小 也就是从节点i到节点j的路径最短 运输问题 运输问题的一般提法是 设某种物资有个产地 各产地的产量是 有个销地 各销地的销量是 假定从产地 到销地 运输单位物品的运价是 问 怎样调运这些物品才能使总运费最小 运输问题 例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量及各产地运往各销地的单位运费如表所示 如何调运 使总运费最少 单位运费 x11x12x13 x21x22x23 运输问题的假设 需求假设 每一个出发地 产地 都有一个固定的供应量 所有的供应量都必须配送到目的地 销地 与之相类似 每一个目的地都有一个固定的需求量 整个需求量都必须由出发地满足 成本假设 从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系 因此这个成本就等于配送的单位成本乘以所配送的数量 上例运输问题的线性模型 minz 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 推广为一般 平衡 运输问题的线性规划模型 Minz S t 定理 如果 平衡 运输问题有可行解 则 证 设运输问题有可行解 则应满足约束 从而有 运输问题的变形 总供应量 总需求量的情形供 求 LP模型中把约束 xij ai改为 xij ai即可供 求 LP模型中把约束 xij bj改为 xij bj即可目标函数最大化的情形 如目标是追求利润或收入时 只需将目标函数改为max即可某些路线的运输能力有一定限制的情形如从A2到B3受到运输能力限制 最多只能运送150时 只需在原LP模型上添加x23 150即可 运输问题的计算机求解 用线性规划程序求解 输出部分信息多 且变量和约束输入较麻烦 用运输问题程序求解 只需输入产地个数 销地个数 各产地的产量 各销地的销量 各产地到各销地的单位运价 前例输入后 得到的最优运输方案为 指派问题 有4个工人 要指派他们分别完成4项工作 每人做各项工作所消耗的时间如下表 要求1人只做1件事 如何指派使总成本最少 模型 用0 1变量表示 是非 决策 minz 14 35x11 14 41x12 14 27x13 14 40 x14 12 47x21 12 45x22 12 32x23 12 51x24 13 39x31 13 56x32 13 36x33 13 43x34 15 32x41 15 51x42 15 25x43 15 46x44s t x11 x12 x13 x14 1 A1只能干一件事 x21 x22 x23 x24 1 A2只能干一件事