通信网络理论基础虞红芳 博士 教授 博导Part 09: 对偶与整数规划对对偶与整数规规划2013年春季 通信网络理论基础2 / 701234对偶理论对偶问题示例对偶单纯形算法简介整数规划的求解方法5小结拉格朗日乘子法2013年春季 通信网络理论基础3 / 70如何求解该问题？拉格朗日乘子法的思想：松弛原问题的约束，得到一个无约束问题；引入惩罚因子p，对违背约束的解进行惩罚；只要选择合适的p，无约束问题的解与原问题一致。LP标标准型的对对偶(1/2)2013年春季 通信网络理论基础4 / 70松弛掉等式约束可得：惩罚因子的 个数为m。LP标标准型的对对偶(2/2)2013年春季 通信网络理论基础5 / 70LP标准型的对偶(dual)问题。关于对对偶的第一个印象2013年春季 通信网络理论基础6 / 70对于LP问题，可以按照拉格朗日乘子法求解其“估值”。求解合适的Lagrange乘子（惩罚因子）等价于求解一个 LP问题：原问题（主问题）的对偶问题。Well，至少对标准型，是这样。更一般的LP问题还是这样吗？我们用一个例子来说明。对于更一般的LP问题，其对偶问题是什么样子？例子：一般的LP(1/4)2013年春季 通信网络理论基础7 / 70除了符号约束之外，每个 约束都引入一个惩罚因子， 并松弛到目标函数中。在该松弛问题中，为了体现“惩罚”的含义，必有：例子：一般的LP(2/4)2013年春季 通信网络理论基础8 / 70为了保证最小化Lagrange函数有意义，必有：每个主变量都对应一个“对偶约束”。例子：一般的LP(3/4)2013年春季 通信网络理论基础9 / 70由于对偶约束与对应的主变量“同符号”，其最小值为0。例子：一般的LP(4/4)2013年春季 通信网络理论基础10 / 70主问题对偶问题总结上述推导，可得：关于对对偶的第二个印象2013年春季 通信网络理论基础11 / 70主问题问题minimizemaximize对对偶问问 题题 约约束变变量变变量约约束任给一个LP问题，都可按照上述规则写出其对偶问题。真正需要记住的是“惩罚”以及拉格朗日函数的概念， 而不是这些规则。另一个例子(1/4)2013年春季 通信网络理论基础12 / 70应用“惩罚”的概念推导下面最大化问题的对偶问题。另一个例子(2/4)2013年春季 通信网络理论基础13 / 70应用“惩罚”的概念推导下面最大化问题的对偶问题。对偶约束和主变量 符号相反。另一个例子(3/4)2013年春季 通信网络理论基础14 / 70对偶约束与对应的主变量“符号相反”，其最大值为0。另一个例子(4/4)2013年春季 通信网络理论基础15 / 70主问题对偶问题总结上述推导，可得：有人看出这个例子与上一个例子的关系了吗？该例中，主问题是上例中的对偶问题。该例中，对偶问题是上例中的主问题。关于对对偶的第三个印象2013年春季 通信网络理论基础16 / 70对偶问题的对偶，是主问题。主问题与对偶问题是一一对应的。主问题可以推出其对偶问题。对偶问题也可以推出其对应的主问题。对偶问题可以看作是主问题的最佳估值问题，那么， 这种估值准确吗？让我们来讨论对偶理论中最深刻的结论：对偶定理。弱对对偶定理2013年春季 通信网络理论基础17 / 70定理：weak duality theorem主问题对偶问题推导对偶问题的过程中，我们知道：对拉格朗日函数求最小值(松弛问题)得到的一定是主问题 目标函数值的下界；对偶问题的目标函数就是松弛问题的目标函数。故有：两个推论论2013年春季 通信网络理论基础18 / 70推论1：Let x and p be feasible solutions to the primal and the dual, respectively, and suppose that pb=cx. Then, x and p are optimal solutions to the primal and the dual, respectively.推论2：强对对偶定理(1/2)2013年春季 通信网络理论基础19 / 70假定用单纯形法求解主问题，得到最佳解x和最佳基B，则：主问题对偶问题p为对偶可行解。由弱对偶定理的推论2可知，p是对偶最佳解。Reduced Cost，还记得吗？强对对偶定理(2/2)2013年春季 通信网络理论基础20 / 70If a linear programming problem has an optimal solution, so does its dual, and the respective optimal costs are equal.定理：strong duality theorem主问题对偶问题若标准型主问题存在最佳解，则单纯形法一定可以求出。求出了主最佳解，则对偶最佳解也被求出了。因此，有：任一LP问题都可以转化为标准型。关于对对偶的第四个印象2013年春季 通信网络理论基础21 / 70主问题与对偶问题不仅一一对应， 而且在下述意义下是等价的：二者的最佳目标值是一致的：估值是精确的。求解主问题的同时，对偶问题的解也被求出了。那么，两个问题的解的取值有什么关系吗？一个重要的结论：互补松弛定理。互补补松弛定理(1/2)2013年春季 通信网络理论基础22 / 70定理：complementary slackness证明：互补补松弛定理(2/2)2013年春季 通信网络理论基础23 / 70证明：弱对偶定理， 记得吗？充要条件得证。关于对对偶的第五个印象2013年春季 通信网络理论基础24 / 70主问题与对偶问题不仅求解过程是一致的（求解前者 的同时也求解了后者），而且求出的解具有密切关系：若主最佳解非零，则对应的对偶约束必取等号。若对偶最佳解非零，则对应的主约束必取等号。对对偶与整数规规划2013年春季 通信网络理论基础25 / 701234对偶理论对偶问题示例对偶单纯形算法简介整数规划的求解方法5小结最短路的对对偶(1/2)2013年春季 通信网络理论基础26 / 70最短路的对对偶(2/2)2013年春季 通信网络理论基础27 / 70绳绳球模型2013年春季 通信网络理论基础28 / 70怎样理解最大化距离标记？绳球模型。 想象随意放在桌上的一堆 绳和球。球顶点；绳边。绳的长度=边的权重。一手拿s，一手拿i，拉伸到 不能再拉为止。最优条件：RC非负。Bellman-Ford算法2013年春季 通信网络理论基础29 / 70Ring a bell？Yes, its Bellman-Ford algorithm!事实上，上述方程成为Bellman方程。绳球模型：先将s上的绳子拉直，然后将s邻接点的绳子 拉直；一直进行下去，直至所有点i到s的绳子都被拉直。对对偶的用途：设计设计 新算法2013年春季 通信网络理论基础30 / 70主问题与对偶问题是等价的。因此求解对偶问题的算法 同样可以求解主问题。Bellman-Ford算法求解的其实不是最短路，而是 距离标记（对偶变量）。最大流的对对偶(1/3)2013年春季 通信网络理论基础31 / 70需要两套对偶变量：p对应流守恒；q对应容量约束。最大流的对对偶(2/3)2013年春季 通信网络理论基础32 / 70对偶目标必须等于0必须小于等于0最大流的对对偶(3/3)2013年春季 通信网络理论基础33 / 70设置对偶变量取值如下：是对偶可行解吗？是的。对偶目标函数的含义？ 割容量。由强对偶定理可知，若最大流存在最佳解，则最小割问题 也存在最佳解。而且最大流等于最小割。对对偶的用途：发现发现 新关系2013年春季 通信网络理论基础34 / 70将问题建模为LP模型，进行对偶变换，往往可以发现 新的物理意义，在不同的物理概念之间建立新的联系。最大流与最小割之间的关系就是这样建立的。最佳路由的对对偶(1/4)2013年春季 通信网络理论基础35 / 70需要2套对偶变量：p（流守恒约束）和q（容量约束）。最佳路由的对对偶(2/4)2013年春季 通信网络理论基础36 / 70最佳路由的对对偶(3/4)2013年春季 通信网络理论基础37 / 70对偶目标由于z为自由变量， 该项系数必须等于0.该项系数必须大于等于0.最佳路由的对对偶(4/4)2013年春季 通信网络理论基础38 / 70最佳路由=最短路！2013年春季 通信网络理论基础39 / 70sabt只考虑特定的需求k。其流变量取值大于0的边构成一些路径。如右图所示。只看其中的一条路径（例如sabt）。其他路径呢（例如sbt）？最佳解在最短路上！权权重设设置2013年春季 通信网络理论基础40 / 70我们知道，Internet的路由协议是基于最短路的。控制路由的唯一方法是设置不同的权重。最佳路由问题的对偶提供了全新的Insight：怎样的权重设置才是最佳的？根据优化目标建模OR问题。求解OR问题得到的对偶变量取值，就是最佳权重。需要注意的是：即使得到了最佳权重，沿着最短路 安排流量也不完全等价于原最佳解（因为没有分流 比例信息），应该看作是对原最佳解的近似。对对偶的用途：Insight2013年春季 通信网络理论基础41 / 70最佳路由问题与最短路问题表面上看有很大不同，但 上述结论表明，它们具有深层次的联系。对偶为我们 提供了得到这种“Insight”的一种可能的手段。对对偶与整数规规划2013年春季 通信网络理论基础42 / 701234对偶理论对偶问题示例对偶单纯形算法简介整数规划的求解方法5小结基本思路2013年春季 通信网络理论基础43 / 70对偶问题也是一个LP问题，也可用单纯形算法求解。用单纯形法求解对偶问题，相当于保持主问题解的 最佳性，追求主问题解的可行性。主问题对偶问题注意以下两个事实：单纯形法的思路是：保持解的可行性，追求解的最佳性。对偶可行实际上意味着RC大于等于0：主问题最佳条件。换换基方法2013年春季 通信网络理论基础44 / 70假定已经得到了一个基本解及其基矩阵。由于是基本解，因此等式约束是肯定满足的。不可行 意味着必有某些基变量的取值小于0。对偶单纯形法的换基方法是：选择进基变量时，要保证RC大于等于0 。注意对比主单纯形法。例1(1/2)2013年春季 通信网络理论基础45 / 701234考虑一个MCF问题的实例。基矩阵如图红线所示； 流量需求矢量b和边代价矢量c如图所示。其它点到节点4的最短路。该问题求的是什么？流变量取值是多少？RC是多少？显然，这是一个不可行解， 但满足最优条件。可以用 对偶单纯形法求解。例1(2/2)2013年春季 通信网络理论基础46 / 701234对偶单纯形法说， 先确定出基变量。看谁能保持RC非负。谁入基？已知当前基本解为：换基后，x=？已是可行解， 搞定！对对偶单纯单纯 形法的应应用2013年春季 通信网络理论基础47 / 70对偶单纯形法要求初始解对偶可行（主最佳）。因此同样 需要一个类似大M法那样的确定初始解的方法。跟直接用单纯形法求解主问题有何区别？若从头开始求解，那确实没有区别。应用场景：求解多个关系密切的LP问题。只是增加了 不等式约束只是右端矢量b 发生了变化这些场景的共同特点：第一个问题的最佳解可能不是第 二个问题的可行解，但却满足第二个问题的最佳条件。因此，可以在第一个问题最佳解的基础上，应用对偶单 纯形法“继续求解”第二个问题。而不必重新开始。场场景1：bb2013年春季 通信网络理论基础48 / 70首先，矩阵A没有变化。原问题的基矩阵仍是新问题的基矩阵。原问题的最佳基在新问题中一定能保证对偶可行。该解不仅满足最优条件，而且是可行的。该解就是新问题的最佳解。该解不可行，但满足最优条件（对偶可行）。从该解出发，应用对偶单纯形法进行换基操作， 直至到达某个可行解为止。场场景1的第一个例子2013年春季 通信网络理论基础49 / 701234节点1到其它点的最短路。