通信网络理论基础-线性规划地求解方法-2003-Final-WX.ppt

《通信网络理论基础-线性规划地求解方法-2003-Final-WX.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、通信网理论基础王雄博士副教授Part07:线性规划的求解方法GeorgeBernardDantzig(1914-2005)线性规划的求解方法12线性规划解的基本概念线性规划解的几何性质及几何解法3线性规划的代数解法4单纯型算法5网络单纯型法与最短路问题线性规划的一般形式决策变量约束优化目标A矩阵行的数目多呢？还是列的数目多呢？一些解的基本概念如果一个解x满足，则称该解x为线性规划问题的一个可行解可行域由所有可行解组成的集合被称为可行域，记为P可行解最优解如果一个可行解x*满足（x为可行域P中的任意可行解），则x*被称为该线性规划问题的最优解例子x3012y01243可行域x

2、³0y³0x+2y³2y£4x£3Subjectto:Minimize-x-y最优解SolutionHalfspace&HyperplaneHalfspace集合被称为HalfSpaceHyperplane集合被称为HyperPlaneHalfspaceaHyperplanePolyhedra&可行域线性规划的可行域为，即由一组Halfspace的交集组成Polyhedra集合被定义为一个PolyHedra，其中A为一个m×n的矩阵，b为一个m维的向量。可见线性规划的可行域就是一个Polyhedra凸集&Polyhedra凸集一个集合S为凸集的充分必要条件为对于任意的和任意

3、的,有,则集合S为凸集Polyhedra为凸集吗？是的，怎么证明？极点假设P为一个Polyhedra，x为P中的一个点，如果不存在点y，z∈P和λ∈[0,1]，使得x=λy+(1-λ)z,则x为P的一个极点极点在代数意义上PolyhedraP={x

4、Ax≥b}的一个极点x0意味者什么呢？是不是意味着Ax≥b表示的m个不等式中至少有n个不等式在x0处取等于号呢？即，x0是大于的等于n个以上Hyperplane的交点线性规划的求解方法12线性规划解的基本概念线性规划解的几何性质及几何解法3线性规划的代数解法4单纯型算法5网络单纯型法与最短路问题线性规划图形解法：示例1x3012

5、y01243FeasibleRegionx³0y³0x+2y³2y£4x£3Subjectto:Maximum-x-yOptimalSolutionFeasibleRegionx³0y³0-2x+2y£4x£3Subjectto:Minimizex-yMultipleOptimalSolutions!41x312y02031/3x+y£4线性规划图形解法：示例2FeasibleRegionx³0y³0x+y³20x³5-2x+5y£150Subjectto:Minimizex+1/3yOptimalSolutionx301020y010204003040线性规划图形解法：示

6、例3FeasibleRegionx³0y³0x+y³20x³5-2x+5y£150Subjectto:Minimize-x-1/3yx301020y010204003040线性规划图形解法：示例4该问题无最优解，是一个Unbound的问题从上面的4个例子中我们能发现什么规律呢？yxy0xy如果存在最优解，则先线性规划的最优解在极点处达到可行域虽然存在极点，但是规划没有最优解x三维的情况2009年春季图算法及其在通信网络中的应用17/55课堂练习用图解法求下列线性规划问题的解一个重要的定理假设线性规划问题为：如果该线性规划问题存在极点，那么该线性规划问题的最优解要么为-∞，要

7、么其中至少有一个极点必然为最优解最优解的存在性定理怎么证明？我们仅从物理意义上来进行证明，严格的数据证明请见本课程推荐的参考书从线性规划的图形解法中我们可以到，线性规划问题的最优解一定是在可行域的边界达到。那么边界有两种情况：一种是一个有限的边界，一个是无限的边界（最优解无穷小）线性规划问题的几何求解方法假如线性规划问题存在最优解，那么一个线性规划问题可以采用以下的方法来进行求解根据约束，画出可行域将所有极点带入优化目标，选择使得优化目标值最小的点即为最优解找出可行域的所有极点但是该方法是不完备的，因为该方法只有在线性规划问题存在最优解的情况下才能使用因为该方法缺少了对是否

8、存在最优解的判断（无界）怎么办呢？我姑且假设线性规划问题是有最优解的，然后从代数解法中寻找判断的方法线性规划的求解方法12线性规划解的基本概念线性规划解的几何性质及几何解法34单纯型算法5网络单纯型法与最短路问题线性规划解的代数解法从几何解法中发掘代数解法的灵感从前面的几何解法中，我们可以看出如果线性规划问题存在在最优解，那么线性规划问题可行域中至少有一个极点是最优解找最优解找可行域的极点从代数的角度我们应该怎么来求解呢找到极点在代数上的对应关系极点在代数上意味这什么？线性规划约束AX≥b的m个不等式中至少有n个取