线性规划_单纯形法

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

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

2、纯形法的强有力的竞争者(投影内点法)现在求解大规模、退化问题最有效的是原－对偶内点法◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；　　－第j种食品的单价－每单位第j种食品所含第i种营养的数量－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题例2.运输问题产销平衡/不平衡的运输问题例3.目标值带绝对值的问题假设：事实：转化为：例4.其它应用数据包络分析(dataenvelopeanalysis,DEA)网络流问题(Networkflow)博弈论(gametheory)等线性规划的一般形式线性规划的标准形

3、(分析、算法)*****标准形的特征：极小化、等式约束、变量非负向量表示：一般形式　　　标准形转化称松弛(slack)/盈余(surplus)变量例5.化成标准形等价表示为定义设B是A的m个线性无关列组成的矩阵.置所有与B无关列对应的变量为零，称所得方程组的解是Ax=b的基本解(basicsolution)称B是基(basis)；称与B对应的变量为基变量(basicvariables)基本解与基变量(*****)其中满秩假定：m

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

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

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

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