2 最优化方法-线性规划-单纯形法[专业技术]

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

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

3、种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价 每单位第每单位第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量 食用第食用第 j 种食品的数量种食品的数量 为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型：模型： 例例1. 1. 食谱问题食谱问题 7高级教学 例例2. 运输问题运输问题 产销产销平衡平衡/不平衡不平衡的运输问题的运输问题 8高级教学 例例3. 其它应用其它应用 数据包络分析数据包络分析(data envelope analysis, DEA) 网络流问题网络流问题(Network flow) 博弈论博弈论(g

4、ame theory)等等 9高级教学 线性规划的一般形式线性规划的一般形式 10高级教学 线性规划的标准形线性规划的标准形(分析、算法分析、算法) 标准形的特征：标准形的特征：极小化极小化、等式约束等式约束、变量非负变量非负 向量表示：向量表示： 11高级教学 一般形式一般形式 标准形标准形 转化转化 称称 松弛松弛(slack)/盈余盈余(surplus)变量；变量； 自由自由变量变量12高级教学 例例5. 5. 化成标准形化成标准形 等价表示为等价表示为 13高级教学 定义：定义： 给定含有给定含有n个变量，个变量，m个方程的线性方程组个方程的线性方程组Ax=b， 设设B是由是由A 的列

5、组成的任一非奇异的列组成的任一非奇异mm子阵，则如果置子阵，则如果置x 的所有与的所有与B无关的无关的n-m个分量为零后，所得方程组的解是个分量为零后，所得方程组的解是 Ax=b关于基关于基B的的基本解基本解(basic solution) ，称，称x中与基中与基B对应对应 的分量为的分量为基变量基变量(basic variables) 退化基本解：退化基本解：基本解中如果有一个或多个基变量的值为零基本解中如果有一个或多个基变量的值为零 基本解与基变量基本解与基变量 其中其中 满秩假定：满秩假定： m n矩阵矩阵A满足满足mn，且，且A的行向量线性无关的行向量线性无关 在满秩假定下，方程组在满

6、秩假定下，方程组Ax=b总有解，且至少有一个基本总有解，且至少有一个基本 解解 14高级教学 基本可行解基本可行解 定义定义 称称 的非负基本解是的非负基本解是标准形标准形的的基基 本可行解本可行解( (basic feasible solution)； 约束系统约束系统 15高级教学 线性规划的基本定理线性规划的基本定理 i) 若标准型有可行解，则若标准型有可行解，则必有必有基本可行解；基本可行解； ii) 若标准型有最优解，则若标准型有最优解，则必有必有最优最优基本可行解。基本可行解。 考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn 阶阶 矩阵，则以下结论成立：矩

7、阵，则以下结论成立： 基本可行解的个数基本可行解的个数不超过不超过 16高级教学 与凸性的关系与凸性的关系 线性规划的基本定理线性规划的基本定理( (标准形标准形) ) 基本可行解基本可行解 线性方程组线性方程组 的基本性质的基本性质 代数理论代数理论 (与与表述形式有关表述形式有关) 设计算法设计算法 极点极点 凸集理论凸集理论 几何理论几何理论 ( (与表述形式与表述形式无关无关) ) 直观理解直观理解 17高级教学 凸性凸性( (凸集及性质凸集及性质) ) 几何解释几何解释：连接集合中任两点的线段仍含在该集合中：连接集合中任两点的线段仍含在该集合中 性质性质 定义定义 是凸集是凸集(co

8、nvex set)，如果对，如果对S中任意中任意 两两 点点 x , y 和和(0,1)中的任一数中的任一数 满足满足 18高级教学 一些重要的凸集一些重要的凸集 有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral convex set): 推推 广广 平面上：多边形平面上：多边形 注：注：任一线性规划的可行集是任一线性规划的可行集是多面集多面集！ 超平面超平面(hyperplane): 正正/ /负闭半空间：负闭半空间： 19高级教学 极点极点 几何上几何上：极点即不能位于连接该集合中其它两点：极点即不能位于连接该集合中其它两点 的开线段上的点的开线段上的点 定义定义

9、 称凸集称凸集C中的点中的点 x 是是C的极点，如果存在的极点，如果存在 C 中中 的点的点 y, z 和某和某 ，有，有 则必有则必有 y=z. 20高级教学 极点与基本可行解的等价性定理极点与基本可行解的等价性定理 推论：推论： i) 若若K非空，则至少有一个极点非空，则至少有一个极点. ii) 若线性规划有最优解，则必有一个极点是最优解若线性规划有最优解，则必有一个极点是最优解. iii) Ax=b对应的约束集对应的约束集K最多有有限个极点最多有有限个极点. 考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn 矩阵，令矩阵，令 则则x是是 K 的极点，的极点，当且仅

10、当当且仅当x是线性规划的基本可行解是线性规划的基本可行解. （线性规划基本定理的几何形式）（线性规划基本定理的几何形式） 21高级教学 例例2.2. K有有2个极点个极点 有有3个基本解，个基本解，2个个可行可行 K 有有3个极点个极点 有有3个基本解，个基本解，均可行均可行 例例1. 1. 22高级教学 例例3. 3. Subject to 5个极点个极点 极点极点 23高级教学 线性规划线性规划 解的解的 几何特征几何特征 唯一唯一 解解(顶点顶点)！ 24高级教学 线性规划解的线性规划解的几何特征几何特征 无界无界：没有有限最优解：没有有限最优解 不可行不可行：没有可行解：没有可行解 无

11、解无解 可行集：可行集：多边形多边形( (二维二维) )多边集多边集( (高维空间高维空间) ) 给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证，从理论上证 实上述几何特征，并实上述几何特征，并寻求有效算法寻求有效算法 有解：有解：唯一解唯一解/ /多个解多个解( (整条边、面、甚至整条边、面、甚至 整个可行集整个可行集) ) 有顶点解有顶点解 25高级教学 顶点顶点 一条边一条边 无无(下下)界界 26高级教学 线性规划问题解的几种情况线性规划问题解的几种情况 27高级教学 单纯形法简介单纯形法简介 适用形式：适用形式：标准形标准形(基本可行解基本可行解=极

12、点极点) 理论基础：理论基础：线性规划的线性规划的基本定理基本定理！ 基本思想：基本思想：从约束集的从约束集的某个极点某个极点/BFS开始，开始， 依次移动到依次移动到相邻极点相邻极点/BFS，直到找出最优，直到找出最优 解，或判断问题无界解，或判断问题无界. 初始化：初始化：如何找到一个如何找到一个BFS？ 判断准则：判断准则：何时最优？何时无界？何时最优？何时无界？ 迭代规则：迭代规则：如何从一个极点如何从一个极点/BFS迭代到相迭代到相 邻极点邻极点/BFS？ 28高级教学 1.转轴转轴(基本解基本解相邻相邻基本解基本解) 满秩假定：满秩假定： A是行满秩的是行满秩的 29高级教学 规范

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

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

15、线性方程组 a4进基进基 转轴转轴 B=(a1,a2,a3) X=(4,3,1,0,0,0) x=(0,1,3,2,0,0) 37高级教学 3. BFS目标值减小的相邻目标值减小的相邻BFS 将将Ax=b的任一解的任一解用非基变量用非基变量表示；表示； 设设x是是BFS，且规范形如前，则有，且规范形如前，则有 问题：问题：确定进基变量，转轴后使确定进基变量，转轴后使新新BFS的目标值的目标值变小变小？ 用非基变量表示用非基变量表示. 选取进基变量的依据选取进基变量的依据 将将目标函数目标函数 38高级教学 相对相对/既约费用系数既约费用系数(relative/reduced cost coef

16、ficients) 将将 Ax=b 的任一解的任一解 x 用非基变量表示为用非基变量表示为 度量变量相对于给定基的费用度量变量相对于给定基的费用 39高级教学 确定进基变量确定进基变量 最优性定理最优性定理 定理定理(BFS的提高的提高) 相对费用系数的相对费用系数的经济解释经济解释！(合成价格、相对价格合成价格、相对价格) 给定目标值为给定目标值为z0的的非退化非退化基本可行解，且假定存基本可行解，且假定存 在在 j 使得使得 rj 0，无无可行解！可行解！ z*= 0，有有可行解！可行解！ 基变量中基变量中无无人工变量人工变量x 是是BFS，B 是对应的基是对应的基 基变量中基变量中有有人

17、工变量人工变量驱赶人工变量出基驱赶人工变量出基 假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前单纯形表 第第 i 行的前行的前n个数据是个数据是 第第 i 个约束冗余；个约束冗余； 删除单纯形表的第删除单纯形表的第 i 行数据行数据 以以任一非零元任一非零元为转轴元转轴为转轴元转轴 得辅助问题的一个新最优得辅助问题的一个新最优BFS，且基变量中少，且基变量中少1个人工变量！个人工变量！ 56高级教学 例例1. 给出下面系统的一个基本可行解，或者说明其无解给出下面系统的一个基本可行解，或者说明其无解 引入引入人工人工变量变量 目标目标： 辅助问题的辅助问题的 初始

18、表格初始表格！ BFS 57高级教学 第一张第一张 单纯形表单纯形表 第二张第二张 单纯形表单纯形表 注意基变量整列包括末行z在内除了基变量 其他元素都是0 58高级教学 辅助问题的辅助问题的最优值是最优值是0 0. . 原问题的原问题的BFS： 59高级教学 两阶段法两阶段法可求任一可求任一线性规划问题线性规划问题 第第I阶段：启动单纯形法阶段：启动单纯形法 构造、求解辅助问题构造、求解辅助问题 判断原问题判断原问题不可行、或可行不可行、或可行 可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形 第第II阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题 从上述从上述BFS出

19、发，求解所给问题出发，求解所给问题 原问题原问题无界无界或者或者有解有解 60高级教学 例例2. 利用两阶段法求解下面的问题利用两阶段法求解下面的问题 辅助问题辅助问题第第I阶段：阶段： 先构造辅助向量z=x4+x5 61高级教学 辅助问题的辅助问题的最后一张单纯形表最后一张单纯形表 原问题的原问题的初始初始表格：表格： 得到辅助问题的最后一张单纯 形表后，去掉辅助变量，将原 始问题的z带入表格，启动单纯 形法 62高级教学 原问题的原问题的最优解最优解： 63高级教学 6. 修正单纯形法修正单纯形法(Revised simplex method) 重要事实：重要事实： 通常仅有少数列发生转轴

20、通常仅有少数列发生转轴(2m-3m) 核心问题：核心问题： 如何更新如何更新当前基的逆当前基的逆新基的逆新基的逆 理论上的表现理论上的表现表格实现表格实现 仅需原始数据仅需原始数据(c, A, b)和基和基 B 的逆矩阵的逆矩阵 64高级教学 7. 单纯形法的矩阵形式单纯形法的矩阵形式 给定基给定基 B 及对应及对应BFS (xB, 0), 其中其中xB=B-1b 用用非基非基变量表示变量表示目标函数目标函数： 用用非基非基变量表示变量表示基基变量：变量： 相对相对费用向量费用向量 65高级教学 初始表格单纯形表初始表格单纯形表 初始表格初始表格 通常不是单纯形表！通常不是单纯形表！ 与基矩阵与基矩阵 B 对应的对应的单纯形表单纯形表66高级教学 修正单纯形法的计算步骤修正单纯形法的计算步