通信网络理论基础-网络优化问题的线性规划建模-2013-Yu.pptVIP

The solution of LP is right there! Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * 首先介绍清楚线性规划模型的基本组成部分，然后使用一个简单的例子来进一步阐述线性规划模型，最后引出如何用线性规划约束来描述网络中的一个流 * * * * * * * 请学生回忆xij的系数取值只能是1或-1；何时取值为1？ * * * Xij的含义：边(i,j)上的流大小。 * * * 为啥叫做“更一般”？因为该问题中不限定只有一个源和一个宿。 * 请学生回忆xij的系数取值只能是1或-1；何时取值为1？ * 结论的含义：能够求解mcf问题的算法都可以用来求解最短路问题。而我们将要发展的针对网络流问题的网络单纯形法就是这样的一个算法。 问题的另一个方面是：通用解法往往不如专门设计的算法效率高；不同对通用算法的了解有利于求解各种扩展问题。例如：label-correcting算法比label-setting算法更为通用，所以效率较低，但求解约束路由问题时，可以通过改进label-correcting算法来实现；但label-setting算法就不行了。 All-pair问题实际上是多商品流的一种描述。多商品流问题的建模方法我们将在后面讨论。 边上容量在最短路问题中没有意义。这也是为什么在part05中我们从未讨论过容量的原因。不设置容量，流变量也不会超过1（单源单宿问题）或者超过n-1（单源多宿问题）。 * 注意讲解： 1）xij*bij=B可以保证第一点。但不能保证第二点。 2）xij*bij=B-(1-xij)B可以同时保证第一点和第二点。但是xij此时必须是0-1变量。 * 直接给模型，回忆b(s)=1,b(t)=-1对应于SP-SSSD模型。变成2和-2就成了SDPP了。 * 为了更明确的描述出两条分离路径，我们还可以使用两个变量x和y分别代表一条路。同时，引入两个向量bx和by，并且bx(s) = by(s) = 1, bx(t) = by(t) = -1, , bx(i) = by(i) = 0 (i≠s≠t) X和y各自定义一条路。第三个约束要求不重叠。但是加起来小于等于1能保证不重叠吗？换句话说，需要整数约束吗？自己对比研究SDPP-3和4。 * 约束1要求最后的解中，只能包含n-1条边。n-1条边构成的子图若不成环，则是原图生成树。 约束2要求任选原图中的顶点子集，它们在可行解中都不成环。 所以二者合在一起定义了生成树。 注意：这里xij已经没有流变量的含义了。因为不再要求它满足流守恒。 * 描述该生成树的权重，就可以在目标函数中要求它最小化。岂不就是最小生成树的模型了么？ 需要给出一个具体的实例来说明：流代价不等于树的代价。该实例中，生成树上必须包含孩子多于1个的节点。 * 原点任选。注意：最小生成树模型中，一般假定针对无向图。若树必须是有向的，那么原点的选择就有关系了。 显然，xij仍然是流变量；而yij已经不是流变量了。 * 参考MST-2的建模思路： 1）引入辅助变量yij，表示xij非零的边在树上。 2）只有X中的点才有流量需求，b值为-1。 3）目标函数是最小化yij*cij之和。 * * 要点：每个“源”发出的流都必须是“独立的”流。 和最小等价于每个路径权重最小么？是的。因为没有容量约束。 * APSP模型中，目标可以拆成每种商品一个函数；约束也可以完全分开。因此：可以拆成K个相互独立的子问题。 引入容量约束后，这些子问题不再独立。 为什么是最佳路由问题？该模型的物理意义：每个节点对之间都只有一个单位的流量需求，请问怎样安排它们之间的路径和流量安排，使得总体的代价最小。 * 更一般的最佳路由问题的描述：1）每个节点对之间的需求不必是1，hk：给定的值；2）不必所有节点对之间都有需求。 边上代价的含义：单位流量的代价。 给出模型后，说明一点：这显然已经不能用我们已经学过的算法来求解了。所以求解线性规划的统一方法很重要。 * 1 链路利用率的概念。 2〉变量z是所有链路利用率的上界：最大链路利用率 3〉优化目标是：最大链路利用率最小化。 4〉这就是负载平衡的一种表达。 * 边上代价的含义与最佳路由有所区别：OR-1问题中，单位流量代价；容量设计问题中，配置单位容量所需的成本。 * Project No. 4-2 2013年春季 通信网络理论基础 * / 50 Project No.4-2 用Lingo软件求解SDPP-1 ~ 3这3个模型。比较求解时间和求解的结果。 Evaluation o