最优化方法线性规划单纯形法ppt课件.ppt

《最优化方法线性规划单纯形法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实用优化方法线性规划：单纯形法线性规划：目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划的历史渊源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,VonNeumann(Princeton)和LeonidKantorovich在1940’s创建了线性规划1947年,GeorgeDantzig发明了单纯形法1979年，L.Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法)1984年，NarendraKarmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法)现在求解大规模、

2、退化问题最有效的是原－对偶内点法◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；　　－第j种食品的单价－每单位第j种食品所含第i种营养的数量－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题例2.运输问题产销平衡/不平衡的运输问题例3.其它应用数据包络分析(dataenvelopeanalysis,DEA)网络流问题(Networkflow)博弈论(gametheory)等线性规划的一般形式线性规划的标准形(分析、算法)标准形的特征：极小化、等式约束、变量非负向量表示：一般形式　　　标准形转化称松弛(slack)/盈余(sur

3、plus)变量；自由变量例5.化成标准形等价表示为定义：给定含有n个变量，m个方程的线性方程组Ax=b，设B是由A的列组成的任一非奇异m×m子阵，则如果置x的所有与B无关的n-m个分量为零后，所得方程组的解是Ax=b关于基B的基本解(basicsolution)，称x中与基B对应的分量为基变量(basicvariables)退化基本解：基本解中如果有一个或多个基变量的值为零基本解与基变量其中满秩假定：m×n矩阵A满足m

4、ion)；约束系统线性规划的基本定理i)若标准型有可行解，则必有基本可行解；ii)若标准型有最优解，则必有最优基本可行解。考虑线性规划标准形，其中A是秩为m的m×n阶矩阵，则以下结论成立：基本可行解的个数不超过与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集合中性质定义是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足一些重要的凸集有限个闭半空间的交集多面集(polyhedralconvexset):

5、推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.极点与基本可行解的等价性定理推论：i)若K非空，则至少有一个极点.ii)若线性规划有最优解，则必有一个极点是最优解.iii)Ax=b对应的约束集K最多有有限个极点.考虑线性规划标准形，其中A是秩为m的m×n矩阵，令则x是K的极点，当且仅当x是线性规划的基本可行解.（线性规划基本定理的几何形式）例2.K有2个极点有3个基本解，2个可行K有3个极点有3个基本解，

6、均可行例1.例3.Subjectto5个极点－极点线性规划解的几何特征唯一解(顶点)！线性规划解的几何特征无界：没有有限最优解不可行：没有可行解无解可行集：多边形(二维)→多边集(高维空间)给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法有解：唯一解/多个解(整条边、面、甚至整个可行集)有顶点解顶点一条边无(下)界线性规划问题解的几种情况单纯形法简介适用形式：标准形(基本可行解=极点)理论基础：线性规划的基本定理！基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.初始化：如何找到一个BFS？判断准则：何时最优？

7、何时无界？迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？1.转轴(基本解→相邻基本解)满秩假定：A是行满秩的规范形(canonicalform)基变量基本解非基变量等价变形不妨设线性无关一般地：次序可以打乱！只要有m个单位列规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什么？◎替换问题假设在上述规范形中，想用转轴(pivot)◎当且仅当　　　　，可以替换◎替换后，新规范形的系数转轴公式－转轴元(pivo