工程优化第章文档ppt第一页，共四十二页根据以上讨论得到如下的结论：根据以上讨论得到如下的结论： 结论结论结论结论1 1：线性规划的可行域是凸集线性规划的可行域是凸集,它它可以是有界的可以是有界的,也可以是无界的也可以是无界的区域区域;仅有有限个顶点仅有有限个顶点 结论结论结论结论2 2：线性规划的每一个基线性规划的每一个基本本可行解对应于可行域的一个顶点可行解对应于可行域的一个顶点.若线性规划问题有最优解若线性规划问题有最优解,必定可在某顶点取到必定可在某顶点取到 结论结论结论结论3 3：如果一个线性规划存在多个最优解如果一个线性规划存在多个最优解,那么至少有两个相邻那么至少有两个相邻的顶点处是线性规划的最优解的顶点处是线性规划的最优解 结论结论结论结论4 4：如果有一个顶点处可行解的目标值比其它相邻顶点如果有一个顶点处可行解的目标值比其它相邻顶点的可行解的目标值小的话，那么它就是最优解的可行解的目标值小的话，那么它就是最优解 线性规划的基本性质线性规划的基本性质线性规划的基本性质线性规划的基本性质第二页，共四十二页 可行域的顶点个数是有限的可行域的顶点个数是有限的( (不超过不超过 Cnm 个个) )，采用，采用“枚举法枚举法”找出所有基找出所有基本本可行解，然后一一比较它们的目标函数值的大小，最可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。
终可以找到最优解 但当但当 m、n 的数目相当大时，这种办法实际上是行不通的的数目相当大时，这种办法实际上是行不通的因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解进并最终求出最优解 线性规划的基本性质线性规划的基本性质线性规划的基本性质线性规划的基本性质第三页，共四十二页1947年年, 美国学者美国学者George Dantzig(丹齐格丹齐格) 提出了求解线性规划的单提出了求解线性规划的单纯形法纯形法, 为线性规划的推广奠定了基础为线性规划的推广奠定了基础从可行域的从可行域的一个顶点一个顶点一个顶点一个顶点(基本可行解基本可行解)开始开始, 转移到另一个顶点转移到另一个顶点转移到另一个顶点转移到另一个顶点 (另一个基本可行解另一个基本可行解); 转移的条件是转移的条件是使目标函数值得到改善使目标函数值得到改善使目标函数值得到改善使目标函数值得到改善(逐步变优逐步变优) 当目标函数达到最优值时当目标函数达到最优值时, 问题也就得到了最优解问题也就得到了最优解基本思想基本思想基本思想基本思想单纯形法单纯形法第四页，共四十二页。
对于标准线性规划问题对于标准线性规划问题(简写为简写为 LP):A = ( aij)m n , rank(A)= m 单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理将将A 分解成分解成B,N,使使B为基矩阵为基矩阵, N为非基矩阵为非基矩阵 设设求基本解求基本解求基本解求基本解基本可行解基本可行解基本可行解基本可行解令令令令x xN N=0=0是基本解是基本解若若第五页，共四十二页相应的目标函数值为相应的目标函数值为记记 现在分析如何从一个基本可行解现在分析如何从一个基本可行解x(0)出发，求一个改进的基本可行解出发，求一个改进的基本可行解x(1) 单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理假设已知一个基本可行解假设已知一个基本可行解x(0) 若初始基本可行解若初始基本可行解x(0)不是最优解，找一个新的基本可行解不是最优解，找一个新的基本可行解任意可行解任意可行解xx ?形式形式并保证是基本可行解并保证是基本可行解x(1) 找改进的基本可行解：找改进的基本可行解：第六页，共四十二页设设x是任意可行解，是任意可行解，目标函数目标函数 f 在点在点x 处的值为处的值为单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理记记 是非基变量的是非基变量的指标集指标集相应于矩阵相应于矩阵A的分解的分解A=B,N, B B称为基矩阵称为基矩阵称为基矩阵称为基矩阵x 可写为可写为第七页，共四十二页。
对任意一个可行解对任意一个可行解 处的目标函数值为处的目标函数值为单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理其中其中 是非基变量的下标集，以及是非基变量的下标集，以及 x xk k就从非基变量变成了基变量就从非基变量变成了基变量就从非基变量变成了基变量就从非基变量变成了基变量式式(1)中，如果中，如果 则则 ，x(0)是最优解；是最优解； 如果如果 则令则令 xk由由0变变 为正数时，为正数时，f 就在变小；就在变小；( (x xk k 是进基变量是进基变量是进基变量是进基变量) )第八页，共四十二页对任意一个可行解对任意一个可行解 处的目标函数值为处的目标函数值为单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理x xk k 就从非基变量变成了基变量就从非基变量变成了基变量就从非基变量变成了基变量就从非基变量变成了基变量( (x xk k 是进基变量是进基变量是进基变量是进基变量) )根据（根据（1）,当当 取值相同时，取值相同时， 越大，目标函数下降越多，因此越大，目标函数下降越多，因此选择选择 (进基变量进基变量) 式式(1)中，中，如果有多个如果有多个 则记则记 令令 xk由由0变为正数时，变为正数时，f 在变小；在变小；第九页，共四十二页。
1. 1. 确定进基变量确定进基变量确定进基变量确定进基变量 x xk k 假设假设 记记 和和 是是m维列向量，维列向量， ，把把 按分量写出，即按分量写出，即单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理取取 此时方程组的解变为此时方程组的解变为 对应的对应的对应的对应的x xk k 就是就是就是就是进基变量进基变量进基变量进基变量 当当 由零变为正数后，函数值变小由零变为正数后，函数值变小 第十页，共四十二页新得到的点是新得到的点是 因为基变量个数总是为因为基变量个数总是为 m , 所以一个进基之后还必须有一个离基所以一个进基之后还必须有一个离基下面我们来考虑如何选择离基变量下面我们来考虑如何选择离基变量 单纯形法的基本原理单纯形法的基本原理在新得到的点，目标函数值是在新得到的点，目标函数值是基基变变量量原则：保证新得到的点是基本可行解原则：保证新得到的点是基本可行解原则：保证新得到的点是基本可行解原则：保证新得到的点是基本可行解第十一页，共四十二页原则：保证新得到的点是原则：保证新得到的点是原则：保证新得到的点是原则：保证新得到的点是基本可行解基本可行解基本可行解基本可行解当当 时，时， 取任何正值时，总成立取任何正值时，总成立对某个对某个i, 当当 时，时， 取任何正值时，总成立取任何正值时，总成立2. 2. 确定离基变量确定离基变量确定离基变量确定离基变量 单纯形法的基本原理单纯形法的基本原理而当而当 时，为了保证时，为了保证 取取因此，为使因此，为使 ，应令，应令 取值取值 后，原来的基变量后，原来的基变量 就是离基变量，于是得到新的基本可行解就是离基变量，于是得到新的基本可行解 当当当当 x xk k 趋于正无穷时，目趋于正无穷时，目趋于正无穷时，目趋于正无穷时，目标函数值趋于负无穷，因标函数值趋于负无穷，因标函数值趋于负无穷，因标函数值趋于负无穷，因此解无界此解无界此解无界此解无界第十二页，共四十二页。
重复以上过程，可以进一步改进基本可行解，直到所有的重复以上过程，可以进一步改进基本可行解，直到所有的 时为止 单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理基变量基变量基变量基变量非基变量非基变量非基变量非基变量初始的基初始的基本可行解本可行解改进的基改进的基本可行解本可行解目标函数值减小目标函数值减小目标函数值减小目标函数值减小了了了了进基变量进基变量进基变量进基变量的确定的确定的确定的确定离基变量离基变量离基变量离基变量的确定的确定的确定的确定 f f0 0 是最优值是最优值是最优值是最优值, ,当前的基本可当前的基本可当前的基本可当前的基本可行解是最优解行解是最优解行解是最优解行解是最优解第十三页，共四十二页最优解判别定理最优解判别定理最优解判别定理最优解判别定理 称称 为判别数或检验数为判别数或检验数单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理单纯形法的基本原理所有的所有的 就可以作为最优解的一个判别条件就可以作为最优解的一个判别条件 若在极大化问题中若在极大化问题中, 对于某个基本可行解对于某个基本可行解, 所有所有 则这个基本可行解是最优解。
则这个基本可行解是最优解 若在极小化问题中若在极小化问题中, 对于某个基本可行解对于某个基本可行解, 所有所有 则这个基本可行解是最优解则这个基本可行解是最优解第十四页，共四十二页步骤步骤步骤步骤1 1：找出初始可行基找出初始可行基B，由，由 ，求得，求得 ， 令令 ，确定初始基本可行解计算目标函数值，确定初始基本可行解计算目标函数值 步骤步骤步骤步骤2 2： 对于所有非基变量，计算对于所有非基变量，计算 判别数判别数 , 令令 若若 ，则对于所有非基变量，则对于所有非基变量 ， 对基变量的判别数总是零，对基变量的判别数总是零， 停止计算，当前的基本可行解是最优解否则，进行下停止计算，当前的基本可行解是最优解否则，进行下 一步单纯形法的算法步骤单纯形法的算法步骤单纯形法的算法步骤单纯形法的算法步骤称为单纯形乘子称为单纯形乘子由由 ，得到，得到 .第十五页，共四十二页步骤步骤步骤步骤3 3：由由 ,得到得到 ,若若 ，即，即 的每一的每一 个分量均非正数，则停止计算，问题不存在有限最优解个分量均非正数，则停止计算，问题不存在有限最优解 否则，进行转步骤否则，进行转步骤4步骤步骤步骤步骤4 4：确定下标确定下标 r 为离基变量，为离基变量， 为进基变量。
用为进基变量用 替换替换 ，得到，得到 新的基矩阵新的基矩阵B, 返回步骤返回步骤1注：对于极大化问题，可以给出类似的步骤，只是确定进基和离基变注：对于极大化问题，可以给出类似的步骤，只是确定进基和离基变量的准则不同对于极大化问题，应令量的准则不同对于极大化问题，应令单纯形法的算法步骤单纯形法的算法步骤第十六页，共四十二页以极小化问题为例以极小化问题为例每次迭代必出现下列三种情形之一每次迭代必出现下列三种情形之一(1) .这时当前的基本可行解就是最优解这时当前的基本可行解就是最优解2) . 这种情形下，我们知道这种情形下，我们知道 取任何正数，总能取任何正数，总能得到可行解所以当得到可行解所以当 无限增大时，目标函数趋于负无穷，因此解无限增大时，目标函数趋于负无穷，因此解无界3) ， 不小于零这时求出新的基本可行解，经迭代使目不小于零这时求出新的基本可行解，经迭代使目标函数下降标函数下降单纯形法的收敛性单纯形法的收敛性单纯形法的收敛性单纯形法的收敛性第十七页，共四十二页 如果迭代过程中各个基本可行解都是非退化的，即基变量的取值都是如果迭代过程中各个基本可行解都是非退化的，即基变量的取值都是正的，则各次迭代得到的基本可行解互不相同。
正的，则各次迭代得到的基本可行解互不相同 由于基本可行解的个数有限，因此经有限次迭代一定可以达到由于基本可行解的个数有限，因此经有限次迭代一定可以达到最优解收敛性定理：收敛性定理：收敛性定理：收敛性定理：对于非退化问题，单纯形方法经有限次迭代或对于非退化问题，单纯形方法经有限次迭代或 达到最优基本可行解，或得出无界的结论达到最优基本可行解，或得出无界的结论 注：对于退化情形，可能出现循环迭代，我们在后面将要证明，注：对于退化情形。