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

1、实用优化方法实用优化方法线性规划：单纯形法线性规划：单纯形法1.2线性规划线性规划：目标函数是线性的，约束条件是目标函数是线性的，约束条件是线性等式或不等式线性等式或不等式线性规划线性规划3线性规划的历史线性规划的历史渊源要追溯到渊源要追溯到Euler、Liebnitz、Lagrange等等George Dantzig, Von Neumann(Princeton)和和Leonid Kantorovich在在1940s创建了线性规划创建了线性规划1947年年, George Dantzig发明了单纯形法发明了单纯形法1979年，年，L. Khachain找到了求解线性规划的一种有效方法找到了求

2、解线性规划的一种有效方法(第一个多项式时第一个多项式时间算法间算法椭球内点法椭球内点法)1984年，年，Narendra Karmarkan发现了另一种求解线性规划的有效方法，已发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者证明是单纯形法的强有力的竞争者(投影内点法投影内点法)现在求解大规模、退化问题最有效的是现在求解大规模、退化问题最有效的是原对偶内点法原对偶内点法4567 问题：确定食品数量，满足营养需求，花费最小？问题：确定食品数量，满足营养需求，花费最小？ 变量：变量：n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位第

3、j 种食品所含第种食品所含第 i 种营养的数量种营养的数量食用第食用第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型：模型：例例1. 1. 食谱问题食谱问题8例例2. 运输问题运输问题产销平衡产销平衡/不平衡的运输问题不平衡的运输问题9例例3. 其它应用其它应用数据包络分析数据包络分析(data envelope analysis, DEA)网络流问题网络流问题(Network flow)博弈论博弈论(game theory)等等10线性规划的一般形式线性规划的一般形式11线性规划的标准形线性规划的标准形(分析、算法分析、算法)

4、标准形的特征：标准形的特征：极小化极小化、等式约束等式约束、变量非负变量非负向量表示：向量表示：12一般形式一般形式 标准形标准形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量；变量；自由变量自由变量13例例5. 5. 化成标准形化成标准形等价表示为等价表示为14定义：定义： 给定含有给定含有n个变量，个变量，m个方程的线性方程组个方程的线性方程组Ax=b，设，设B是由是由A 的列组成的任一非奇的列组成的任一非奇异异mm子阵，则如果置子阵，则如果置x的所有与的所有与B无关的无关的n-m个分量为零后，所得方程组的解是个分量为零后，所得方程组的解是Ax=b关关于基于基B的基本

5、解的基本解(basic solution) ，称，称x中与基中与基B对应的分量为基变量对应的分量为基变量(basic variables)退化基本解：退化基本解：基本解中如果有一个或多个基变量的值为零基本解中如果有一个或多个基变量的值为零基本解与基变量基本解与基变量其中其中满秩假定：满秩假定：m n矩阵矩阵A满足满足mn，且，且A的行向量线性无关的行向量线性无关 在满秩假定下，方程组在满秩假定下，方程组Ax=b总有解，且至少有一个基本总有解，且至少有一个基本 解解15基本可行解基本可行解定义定义 称称 的非负基本解是的非负基本解是标准形标准形的基本可行解的基本可行解( (basic feasi

6、ble solution)；约束系统约束系统 16线性规划的基本定理线性规划的基本定理i) 若标准型有可行解，则必有基本可行解；若标准型有可行解，则必有基本可行解；ii) 若标准型有最优解，则必有最优基本可行解。若标准型有最优解，则必有最优基本可行解。 考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn阶阶矩阵，则以下结论成立：矩阵，则以下结论成立：基本可行解的个数不超过基本可行解的个数不超过17与凸性的关系与凸性的关系线性规划的基本定理线性规划的基本定理( (标准形标准形) )基本可行解基本可行解线性方程组的基线性方程组的基本性质本性质代数理论代数理论(与与表述形式有关

7、表述形式有关)设计算法设计算法极点极点凸集理论凸集理论几何理论几何理论( (与表述形式与表述形式无关无关) )直观理解直观理解18凸性凸性( (凸集及性质凸集及性质) )几何解释：连接集合中任两点的线段仍含在该集合中几何解释：连接集合中任两点的线段仍含在该集合中性质性质 定义定义 是凸集是凸集(convex set)，如果对，如果对S中任意中任意 两两 点点 x , y 和和(0,1)中的任一数中的任一数 满足满足 19一些重要的凸集一些重要的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral convex set):推推广广平面上：多边形平面上：多边形注：任一线性

8、规划的可行集是注：任一线性规划的可行集是多面集多面集！超平面超平面(hyperplane):正正/ /负闭半空间：负闭半空间：20极点极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义定义 称凸集称凸集C中的点中的点 x 是是C的极点，如果存在的极点，如果存在 C 中的点中的点 y, z 和某和某 ，有有则必有则必有 y=z.21极点与基本可行解的等价性定理极点与基本可行解的等价性定理推论：推论：i) 若若K非空，则至少有一个极点非空，则至少有一个极点.ii) 若线性规划有最优解，则必有一个极点是最优解若线性规划有最优解，则

9、必有一个极点是最优解.iii) Ax=b对应的约束集对应的约束集K最多有有限个极点最多有有限个极点.考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn矩阵，令矩阵，令则则x是是 K 的极点，当且仅当的极点，当且仅当x是线性规划的基本可行解是线性规划的基本可行解.（线性规划基本定理的几何形式）（线性规划基本定理的几何形式）22例例2. 2. K有有2个极点个极点有有3个基本解，个基本解，2个可行个可行K 有有3个极点个极点有有3个基本解，均可行个基本解，均可行例例1. 1. 23例例3. 3. Subject to5个极点个极点极点极点24线性规划解的线性规划解的几何特征几

10、何特征唯一唯一 解解(顶点顶点)！25线性规划解的线性规划解的几何特征几何特征无界无界：没有有限最优解：没有有限最优解不可行不可行：没有可行解：没有可行解无解无解可行集：多边形可行集：多边形( (二维二维) )多边集多边集( (高维空间高维空间) )给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证实上述几何特征，从理论上证实上述几何特征，并并寻求有效算法寻求有效算法有解：有解：唯一解唯一解/ /多个解多个解( (整条边、面、甚至整个可行集整条边、面、甚至整个可行集) ) 有顶点解有顶点解26顶点顶点一条边一条边无无(下下)界界27线性规划问题解的几种情况线性规划

11、问题解的几种情况28单纯形法简介单纯形法简介适用形式：标准形适用形式：标准形(基本可行解基本可行解=极点极点)理论基础：线性规划的理论基础：线性规划的基本定理基本定理！基本思想：从约束集的基本思想：从约束集的某个极点某个极点/BFS开始，依次移动到开始，依次移动到相邻极点相邻极点/BFS，直，直到找出最优解，或判断问题无界到找出最优解，或判断问题无界.初始化：如何找到一个初始化：如何找到一个BFS？判断准则：何时最优？何时无界？判断准则：何时最优？何时无界？迭代规则：如何从一个极点迭代规则：如何从一个极点/BFS迭代到相邻极点迭代到相邻极点/BFS？291.转轴转轴(基本解基本解相邻基本解相邻

12、基本解)满秩假定：满秩假定：A是行满秩的是行满秩的30规范形规范形(canonical form)基变量基变量基本解基本解非基变量非基变量等价变形等价变形不妨设不妨设 线性无关线性无关 一般地：一般地：次序可以打乱！次序可以打乱！只要有只要有m个单位列个单位列31规范形的转换问题规范形的转换问题 什么时候可以替换？什么时候可以替换？ 替换后替换后新规范形新规范形是什么？是什么？ 替换问题替换问题假设在上述规范形中，想用假设在上述规范形中，想用32转轴转轴(pivot) 当且仅当当且仅当 ，可以替换，可以替换 替换后，新规范形的系数替换后，新规范形的系数转轴公式转轴公式转轴元转轴元(pivot

13、element)33转轴例例1. 求下列方程组以求下列方程组以 为基变量的基本解为基变量的基本解34转轴转轴转轴转轴转轴转轴x=(0,0,0,4,2,1)352.BFS相邻相邻BFS(极点极点相邻极点相邻极点)问题：问题：确定出基变量，使转轴后新规范形对应确定出基变量，使转轴后新规范形对应BFS？设设x是是BFS, 且规范形如前，且且规范形如前，且假设假设 aq 进基进基因为因为令令可否选取合适的可否选取合适的 使得使得 是是BFS ？所以所以36确定离基变量确定离基变量至少有一个正元至少有一个正元37例例3. 考虑线性方程组考虑线性方程组a4进基进基转轴转轴B=(a1,a2,a3)X=(4,

14、3,1,0,0,0)x=(0,1,3,2,0,0)383. BFS目标值减小的相邻目标值减小的相邻BFS 将将Ax=b的任一解用非基变量表示；的任一解用非基变量表示；设设x是是BFS，且规范形如前，则有，且规范形如前，则有问题：问题：确定进基变量，转轴后使新确定进基变量，转轴后使新BFS的目标值变小？的目标值变小？用非基变量表示用非基变量表示. 选取进基变量的依据选取进基变量的依据 将将目标函数目标函数39相对相对/既约费用系数既约费用系数(relative/reduced cost coefficients)将将 Ax=b 的任一解的任一解 x 用非基变量表示为用非基变量表示为度量变量相对于

15、给定基的费用度量变量相对于给定基的费用40确定进基变量确定进基变量最优性定理最优性定理定理定理(BFS的提高的提高)相对费用系数的经济解释！相对费用系数的经济解释！(合成价格、相对价格合成价格、相对价格) 给定目标值为给定目标值为z0的非退化基本可行解，且假定存在的非退化基本可行解，且假定存在 j 使得使得 rj 0，无可行解！无可行解！ z*= 0，有可行解！有可行解！ 基变量中无人工变量基变量中无人工变量x 是是BFS，B 是对应的基是对应的基 基变量中有人工变量基变量中有人工变量驱赶人工变量出基驱赶人工变量出基假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前

16、单纯形表第第 i 行的前行的前n个数据是个数据是第第 i 个约束冗余；个约束冗余；删除单纯形表的第删除单纯形表的第 i 行数据行数据以任一非零元为转轴元转轴以任一非零元为转轴元转轴得辅助问题的一个新最优得辅助问题的一个新最优BFS，且基变量中少，且基变量中少1个人工变量！个人工变量！57例例1. 给出下面系统的一个基本可行解，或者说明其无解给出下面系统的一个基本可行解，或者说明其无解引入人工变量引入人工变量目标：目标：辅助问题的初辅助问题的初始表格！始表格！BFS58第一张第一张单纯形表单纯形表第二张第二张单纯形表单纯形表注意基变量整列包括末行z在内除了基变量其他元素都是059辅助问题的最优值

17、是辅助问题的最优值是0. 0. 原问题的原问题的BFS：60两阶段法可求任一线性规划问题两阶段法可求任一线性规划问题 第第I阶段：启动单纯形法阶段：启动单纯形法 构造、求解辅助问题构造、求解辅助问题 判断原问题不可行、或可行判断原问题不可行、或可行 可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形 第第II阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题 从上述从上述BFS出发，求解所给问题出发，求解所给问题 原问题无界或者有解原问题无界或者有解61例例2. 利用两阶段法求解下面的问题利用两阶段法求解下面的问题辅助问题辅助问题第第I阶段：阶段：先构造辅助向量z=x4+x56

18、2辅助问题的最后一张单纯形表辅助问题的最后一张单纯形表原问题的初始表格：原问题的初始表格：得到辅助问题的最后一张单纯形表后，去掉辅助变量，将原始问题的z带入表格，启动单纯形法63原问题的最优解：原问题的最优解：646. 修正单纯形法修正单纯形法(Revised simplex method) 重要事实：重要事实： 通常仅有少数列发生转轴通常仅有少数列发生转轴(2m-3m) 核心问题：核心问题：如何更新当前基的逆如何更新当前基的逆新基的逆新基的逆理论上的表现理论上的表现表格实现表格实现 仅需原始数据仅需原始数据(c, A, b)和基和基 B 的逆矩阵的逆矩阵657. 单纯形法的矩阵形式单纯形法的矩阵形式给定基给定基 B 及对应及对应BFS (xB, 0), 其中其中xB=B-1b用非基变量表示目标函数：用非基变量表示目标函数：用非基变量表示基变量：用非基变量表示基变量：相对费用向量相对费用向量66初始表格单纯形表初始表格单纯形表初始表格初始表格通常不是单纯形表！通常不是单纯形表！与基矩阵与基矩阵 B