《通信网络理论基础-网络优化问题的线性规划建模-2013-Yu》由会员分享，可在线阅读，更多相关《通信网络理论基础-网络优化问题的线性规划建模-2013-Yu（62页珍藏版）》请在金锄头文库上搜索。
1、通信网理论基础虞红芳 教授 博导Part 07: 网络优化问题的线性规划建模 线性规划建模12线线性规规划模型的基本概念 最大流问题问题 建模 3最小费费用流问题问题 建模 4多商品流问题问题 建模线性规划模型的基本概念线性规划模型的基本组成部分123建模：从一个简单的例子开始如何描述网络中的一个流线性规划模型的组成部分决策变量优化目标约束线性规划模型一般形式的线性规划模型决策变量约束优化目标一个简单的LP建模例子一个公司使用m种原料生产n种不同的产品。假设bi（i = 1, , m） 是第 i 种原料的可用数量。第 j ( j = 1, , n) 种产品需要第i种原料的 数量为aij 单位，
2、并且销售一个单位的第 j 种产品可以获利 cj 元。公 司生产管理部门需要决策每种产品的生产量以获得最大的利润。生产问题决策变量？xj : 每种变量产 品的生产量优化目标？总利润最大约束？课堂练习一个医院新成立了一个科室，该科室需要招收一批护士，这些新招收 的护士实行轮班制度，每个护士每周连续上5天班，休息两天。该科 室在一周的第i天需要护士di个，医院领导希望该科室降低成本，所 以要求在满足科室护理要求的情况下，尽量减少招收护士的数量。问题描述该问题的难点在于如何 确定决策变量如何对“流”进行建模？一个流用什么决策变量表示？xij: 这个流在链路(i, j) 上的流量一个流必须满足什么约束？
3、流量守恒约束，容量约束SEFBHGCDA怎么用数学模型表达流 的约束简单例子用约束标示出从节点1到节点2 的一个流，该流的大小为 d1x12x21x13 x31d3x32x13x312x32x23x23x21x12dx13 + x12 x31 x21 = dx31 + x32 x13 x23 = 0x23 + x21 x32 x12 = -d矩阵形式2013年春季 通信网络理论基础10 / 50假定：m维维矢量x = xijn维维矢量b = b(i)矩阵N是什么东西？维度？nm。取值？1或1或0。何时时Nij =1？顶顶点i是边边j的起点。何时时Nij = 1？顶顶点i是边边j的终终点。N :
4、 node-arc incidence matrix。流量守恒约束可写为：其中何时时Nij = 0？顶顶点i非边边j的终终点或起点。流模型的矩阵形式11 / 55图的关联矩阵N，关联矩阵的元素aij=1表示节点i是链路j的tail，元素 aij=-1表示节点i是链路j的head，otherwise aij = 0 所以，流量守恒约束可以写为：关联矩阵的第i行乘以流 向量x代表什么呢？节点i的出流量减去入流量矩阵N表述的是什么关系 ？节点和链路的关系所以这种建模方法也称作 Node-Link的建模方法其中Node-Link model2013年春季 通信网络理论基础12 / 50Node-Lin
5、k模型网络优化问题的一种建模方法。特点：约束定义在每个顶点(Node)上：流守恒约束变量定义在每条边(Link)上：流变量xij约束的系数矩阵描述的是Node与Link之间 的关系：关联矩阵N13 / 70线性规划建模12线线性规规划模型的基本概念 最大流问题问题 建模 3最小费费用流问题问题 建模 4多商品流问题问题 建模14 / 32最大流问题2013年春季给给定流网络络G，给给定节节点对对(s, t)，求从s到t 的一个流 ，使得流量值值最大(或者只要求得到最大流量值值)。决策变量：链路(i, j)上流过的流量优化目标：流的大小最大约束：流守恒约束和容量约束最大流问题2013年春季 通信
6、网络理论基础15 / 50变量是什么？ xij和v：m+1个。目标函数是线性的吗？约束是线性的吗？是是有多少个约束？ 每个顶顶点有一个流守恒 约约束（等式约约束）。每条边边有两个约约束（不 等式约约束）。n+2mMF-1线性规划建模12线线性规规划模型的基本概念 最大流问题问题 建模 3最小费费用流问题问题 建模 4多商品流问题问题 建模最小费用流问题建模最小费用流问题建模12最小费用流问题的特例建模这是个什么问题？2013年春季 通信网络理论基础18 / 50三个变变化：1)maxmin；2)v是给给定值值；3)目标标函数符号说说明: cij表示(i, j)上的单单位流代价。这是什么问题？最
7、小费费用流问题问题 ：在节节点s和t之间间“搬运”v个单单位的流， 要求费费用最小。MCF更一般的最小费用流问题2013年春季 通信网络理论基础19 / 50符号说说明: b(i)表示顶顶点i的“需求量”或者“供应应量”。需求量为负整数；供应量为正整数。b(i)0，则顶则顶 点i为为供应节应节 点； b(i)0，则顶则顶 点i为为需求节节点； b(i)=0，则顶则顶 点i为转为转 运节节点。MCF矩阵形式2013年春季 通信网络理论基础20 / 50假定：m维维矢量c = cijm维维矢量x = xijn维维矢量b = b(i)m维维矢量u = uij MCFN : node-arc inci
8、dence matrix。最小费用流的特例建模最短链路分离路径对问 题建模最小费用流的 特例建模单源最短路问题建模最大流问题建模单源最短路径问题建模单单源单单宿最短路问题问题给给定有向加权图权图 G(V, E)，给给定源点/起始点s和宿点/ 终终止点t，求从s出发发到t的权权重最小的路径。MCF：令b(s) = 1, b(t) = -1 b(i) = 0 (i s t)SPM：Shortest Path Model对边对边 上的容量有没有要求？必须须大于1。边边上容量有 意义吗义吗 ？上述约约束只限制了流入流出的差值为值为 1，会不会出现环现环 路？使得目标标函数最小的解一定不会出现环现环 路
9、。最短路问题模型分析该模型的最优解会出现多条等价路的情况吗？是的，从理论上讲，该模型的最优解可能 是多条等价最短路SPM 1cij, uijx=x12, x23, x14, x42, x43, x13 用MCF模型求解顶顶点1和3之间间的 最短路，下面3个解都是最佳的： x1=1,1,0,0,0,0，x2=0,1,1,1,0,0 x3=0.4, 0.7, 0.6, 0.3, 0.3, 0 12342, 11, 11, 12, 11, 18, 1好意思把x3称作“路”吗吗？怎么办?2013年春季 通信网络理论基础24 / 50解决方法：引入整数约束在单单源单单宿最短路问题问题 的MCF模型中，加
10、入以下约约束：或者整数线线性规规划问题问题 ，或者简简称整数规规划。 0-1规规划是整数规规划的特例。SPM 2建模技巧1：引入整数变量整数规划问题Project No. 4-12013年春季 通信网络理论基础25 / 50Project No.4-1 分别用线性规划模型SPM1和整数规划模型 SPM2建模单源单宿最短路问题。用Lingo软件 求解这两个模型，比较求解时间和求解的结果。 用Dijkstra算法求解同样的问题，比较求解时间 和结果。主要目的：熟悉基于流变变量的建模方法； 学习习并掌握Lingo软软件的使用方法； 验证验证 整数约约束的效果。这是啥问题？2013年春季 通信网络理论
11、基础26 / 50单单源多宿最短路问题问题 。一个重要的结论结论 ：单单源最短路问题问题 是MCF问题问题 的特例。边边上的容量u该该如何设设置？SPM-SSMD必须须大于n 1。难难道all-pair最短路问题问题 不是？边边上容量也有 意义吗义吗 ？SSMD：Single Source Multiple Destination课堂练习2013年春季 通信网络理论基础27 / 50带宽约带宽约 束下的最短路问题问题给给定加权图权图 G，每条边边上既有代价cij，也有带宽带宽 bij。给给定 源点s，宿点t，以及带宽带宽 需求B。求从s出发发到t的带宽带宽 大于 B的最小权权重路径。注意：要求
12、选选定的路径带宽带宽 大于B，等价于要求具有非零 流变变量xij的边边上带宽带宽 大于B。流变变量为为0的边边上呢？没有任何约约束。怎样样建模？最短链路分离路径对问题建模最短分离路径对问题对问题给给定加权图权图 G。给给定源点s和宿点d。求从s出发发到d的一对对路径（ 两条），要求这这两条路径“链链路分离”，且路径权权重之和最小。MCF:令b(s) = 2, b(t) = -2 b(i) = 0 (i s t)边边上的容量u该该如何设设置？必须须等于 1。边边上容量有意义吗义吗 ？SDPP-1 & 22013年春季 通信网络理论基础29 / 50SDPP：Shortest Disjoint P
13、ath Pair SDPP-1SDPP-21SDPP-32013年春季 通信网络理论基础30 / 50SDPP-3符号说说明：每条边边上增加了一个yij变变量；bx(s)=by(s)=1；bx(t)=by(t)= 1第三个约约束中，不等式右边边是 m维维的全1矢量。第三个约约束是什么意思？非零的x和y变变量各自构成一条路，并且不重叠。增加整数约约束Project No. 4-22013年春季 通信网络理论基础31 / 50Project No.4-2 用Lingo软件求解SDPP-1 3这3个模型。比较求 解时间和求解的结果。最大流：MCF建模2013年春季 通信网络理论基础32 / 50最短
14、路问题可以MCF来建模，最大流问题也可以。怎么可能？首先，MF问题问题 中supply和demand没有给给定；其次，MF问题问题 中根本没有cost的概念。建模思路：令b(i)=0, for all i V；st增加一条边边ts：cts = 1, uts = 1, 令cij=0, for all (i, j) A；求最小费费用流意味着什么？为为了尽量减小费费用，必须须在(t, s)上 安排尽可能多的流。为为了维维持流守恒，必须须在原网络络的s和t 之间间安排尽可能多的流。MF-2最小生成树：整数约束2013年春季 通信网络理论基础33 / 50MST：Minimum Spanning Tre
15、eMST-1xij表示边边(i,j)是否在生成树树上；E(S)表示一个边边的子集，这这些边边的端点均在集合S中。这这些约约束都是什么意思？xij还还是流变变量吗吗？MST-2：辅助变量2013年春季 通信网络理论基础34 / 50能不能想办办法描述该该生成树树的权权重？直接用流变变量乘以边边上权权重，再求和：不对对，流的代价 不等于树树的代价。流变变量非零的边边必在生成树树上：引入0-1变变量yij。要求yij在xij =0时时取0，在xij取非零值时值时 取1。M是个足够够大的整数。MST-2：模型2013年春季 通信网络理论基础35 / 50MST-2请请用心体会整数变变量的作用。课堂练习
16、2013年春季 通信网络理论基础36 / 50施泰纳纳(Steiner)树问题树问题给给定加权图权图 G，以及一个V的子集X，求一棵包含 了X中所有顶顶点的，最小权权重的树树。怎样样建模？线性规划建模12线线性规规划模型的基本概念 最大流问题问题 建模 3最小费费用流问题问题 建模 4多商品流问题问题 建模All-pair最短路：多商品流2013年春季 通信网络理论基础38 / 50为为什么不能用最小费费用流来建模？ 每个节节点需要发发出的流为为n1，需要收到的流也是n1 。若按照MCF建模，则则b(i)=0，无法保证证得到n1条路。 怎么办办？每个节节点发发出的流不相同：不同的商品。对对于第k种商品有，bk(k) = n1, bk(i)= 1(ik)。第k种商品在边边(i,j)上的流变变量为为xkij。APSP-1APSP：All-Pair Shortes
