09工程优化 第5章-2

nullnull极点：设S是凸集， , 不存在 S 中的另外两个点 和 ， 及 ，使 , 则称x是凸集S的 极点，或称顶点。定理：设 ，其秩为m, 且 , ,则 x为凸集 的一个顶点的充要条件是 x 为 的一个基本可行解。 线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 的基本性质null推论1：若线性规划的可行域 R = { x |Ax = b , x  0 } 是非空 的，则它至少有一个顶点。 推论2: 若线性规划存在有限的最优解，则至少存在一个 R 的顶点是有限最优解。 推论3: 线性规划的可行域R有有限多个顶点。 线性规划的基本性质定理 (线性规划问题的基本定理) (1) 若线性规划问题存在可行解,则一定存在基本可行解; (2) 若线性规划问题存在最优解,则一定存在最优的基本可行解。基本可行解 R的顶点基本可行解 R的顶点基本可行解最多 个线性规划问题若有最优解,必定在某顶点取到null根据以上讨论得到如下的结论： 结论1：线性规划的可行域是凸集,它可以是有界的,也可以是无界的区域;仅有有限个顶点。 结论2：线性规划的每一个基本可行解对应于可行域的一个顶点.若线性规划问题有最优解,必定可在某顶点取到。 结论3：如果一个线性规划存在多个最优解,那么至少有两个相邻的顶点处是线性规划的最优解。 结论4：如果有一个顶点处可行解的目标值比其它相邻顶点的可行解的目标值小的话，那么它就是最优解。 线性规划的基本性质null 可行域的顶点个数是有限的(不超过 Cnm 个)，采用“枚举法”找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。 但当 m、n 的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。 线性规划的基本性质null1947年, 美国学者George Dantzig(丹齐格) 提出了求解线性规划的单纯形法, 为线性规划的推广奠定了基础。 从可行域的一个顶点(基本可行解)开始, 转移到另一个顶点 (另一个基本可行解); 转移的条件是使目标函数值得到改善(逐步变优) 当目标函数达到最优值时, 问题也就得到了最优解。基本思想单纯形法null对于标准线性规划问题(简写为 LP):A = ( aij)mn , rank(A)= m 单纯形法的基本原理将A 分解成[B,N],使B为基矩阵, N为非基矩阵 设求基本解基本可行解令xN=0是基本解。若null相应的目标函数值为记 现在分析如何从一个基本可行解x(0)出发，求一个改进的基本可行解x(1) 。单纯形法的基本原理假设已知一个基本可行解x(0) 若初始基本可行解x(0)不是最优解，找一个新的基本可行解。任意可行解xx ?形式并保证是基本可行解x(1) 找改进的基本可行解：null设x是任意可行解，目标函数 f 在点x 处的值为单纯形法的基本原理记 是非基变量的指标集相应于矩阵A的分解A=[B,N], B称为基矩阵x 可写为null对任意一个可行解 处的目标函数值为单纯形法的基本原理其中 是非基变量的下标集，以及 xk就从非基变量变成了基变量式(1)中，如果 则 ，x(0)是最优解； 如果 则令 xk由0变 为正数时，f 就在变小；(xk 是进基变量)null对任意一个可行解 处的目标函数值为单纯形法的基本原理xk 就从非基变量变成了基变量(xk 是进基变量)根据（1）,当 取值相同时， 越大，目标函数下降越多，因此选择 (进基变量)。 式(1)中，如果有多个 则记 令 xk由0变为正数时，f 在变小；null1. 确定进基变量 xk 假设 记 和 是m维列向量， ， 把 按分量写出，即单纯形法的基本原理取 此时方程组的解变为 对应的xk 就是进基变量 当 由零变为正数后，函数值变小 null新得到的点是 因为基变量个数总是为 m , 所以一个进基之后还必须有一个离基。下面我们来考虑如何选择离基变量。 单纯形法的基本原理在新得到的点，目标函数值是基变量原则：保证新得到的点是基本可行解null原则：保证新得到的点是基本可行解当 时， 取任何正值时，总成立 对某个i, 当 时， 取任何正值时，总成立2. 确定离基变量 单纯形法的基本原理而当 时，为了保证 取因此，为使 ，应令 取值 后，原来的基变量 就是离基变量，于是得到新的基本可行解 当 xk 趋于正无穷时，目标函数值趋于负无穷，因此解无界null重复以上过程，可以进一步改进基本可行解，直到所有的 时为止。 单纯形法的基本原理基变量基变量非基变量非基变量初始的基本可行解改进的基本可行解目标函数值减小 了进基变量的确定离基变量的确定 f0 是最优值,当前的基本可行解是最优解null最优解判别定理 称 为判别数或检验数。单纯形法的基本原理所有的 就可以作为最优解的一个判别条件 若在极大化问题中, 对于某个基本可行解, 所有 则这个基本可行解是最优解。 若在极小化问题中, 对于某个基本可行解, 所有 则这个基本可行解是最优解。null步骤1：找出初始可行基B，由 ，求得 ， 令 ，确定初始基本可行解。计算目标函数值 。 步骤2： 对于所有非基变量，计算 判别数 , 令 若 ，则对于所有非基变量 ， 对基变量的判别数总是零， 停止计算，当前的基本可行解是最优解。否则，进行下 一步。单纯形法的算法步骤称为单纯形乘子由 ，得到 .null步骤3：由 ,得到 ,若 ，即 的每一 个分量均非正数，则停止计算，问题不存在有限最优解。 否则，进行转步骤4。步骤4：确定下标 r 为离基变量， 为进基变量。用 替换 ，得到 新的基矩阵B, 返回步骤1。注：对于极大化问题，可以给出类似的步骤，只是确定进基和离基变量的准则不同。对于极大化问题，应令单纯形法的算法步骤null以极小化问题为例每次迭代必出现下列三种情形之一(1) .这时当前的基本可行解就是最优解。(2) . 这种情形下，我们知道 取任何正数，总能得到可行解。所以当 无限增大时，目标函数趋于负无穷，因此解无界。(3) ， 不小于零。这时求出新的基本可行解，经迭代使目标函数下降。单纯形法的收敛性null 如果迭代过程中各个基本可行解都是非退化的，即基变量的取值都是正的，则各次迭代得到的基本可行解互不相同。 由于基本可行解的个数有限，因此经有限次迭代一定可以达到最优解。收敛性定理：对于非退化问题，单纯形方法经有限次迭代或 达到最优基本可行解，或得出无界的结论。 注：对于退化情形，可能出现循环迭代，我们在后面将要证明，如果最优解存在，只要采取一定的措施，也能做到有限步收敛。单纯形法的收敛性null使用表格形式的单纯形方法记 ，则标准形式等价于1. 构造单纯形表标准形式的线性规划标准形式继续等价于null把约束方程的系数置于表中，就得到了所谓的单纯形表1列cBTB-1 bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行-cBT B-1N +cNT01目标函数值负的判别数基变量的值使用表格形式的单纯形方法1. 构造单纯形表A中存在m阶的单位矩阵xBf为了出现判别数，最后1行乘以-1负的目标值判别数nullzk -ckymkyrky1k …… zj -cj…zm+1 –cm+1 0… 0… 0……ymj…ymm+1 1… 0… 0 …… … ……yrj…yrm+1 0… 1… 0 …… … ……y1j…y1m+1 0… 0… 1初始单纯形表……………………………………………………使用表格形式的单纯形方法1. 构造单纯形表 xk是进基变量 ， 是离基变量；主元把 xk 所对应的列向量 pk 变成 所对应的列向量，即是单位向量。把xk 和 的位置对换，nullzk -ckymkyrky1k …… zj -cj…zm+1 –cm+1 0… 0… 0……ymj…ymm+1 1… 0… 0 …… … ……yrj…yrm+1 0… 1… 0 …… … ……y1j…y1m+1 0… 0… 1……………………………………………………使用表格形式的单纯形方法2. 高斯主元消去法主元将yrk 变为1，yik ( i ≠ r)以及zk –ck都变为0把 pk 变成 对应的单位向量？null对应的新的目标函数值即为：使用表格形式的单纯形方法2. 高斯主元消去法以yrk 为主元素进行Gauss消元: 将第 r 行每个元素除以 yrk :将第 r 行每个元素乘以 – yik / yrk 加到第 i 行 (i = 1, ··· , m , i ≠ r)将第 r 行每个元素乘以 – (zk –ck) / yrk 加到检验数行 null经过Gauss消元后，针对于新基 B1 的基本可行解为：使用表格形式的单纯形方法2. 高斯主元消去法null步骤3：在所有j > 0, j∈RN 中，若有一个j 对应的系数列向量 yj  0，则此问题没有有限最优解，停止计算，否则转步 骤4；使用表格形式的单纯形方法3.单纯形表的单纯形法的算法步骤步骤1：找出初始可行基，确定初始基本可行解 ，建立初始单 纯形表；步骤2：检查对应于非基变量的检验数 j = zj -cj, j∈RN , 若所有 j  0 , j∈RN , 则已得到最优解, 停止计算; 否则转步骤3步骤4：根据 max {j |j > 0, j∈RN } = k ,确定 xk 为进基变量。null确定 xr 为离基变量(即为新基的非基变量), 转步骤6；步骤5：再根据步骤6：以 yrk 为主元素进行Gauss消元，转步骤2。使用表格形式的单纯形方法3.单纯形表的单纯形法的算法步骤null例1. 利用单纯形算法求解 如下的线性规划问题。解： 1. 写出线性规划的标准型使用表格形式的单纯形方法3.单纯形表的算例A中存在4阶单位矩阵选取 作为基变量，得到一个基本可行解null 2. max{1, 2}=3= 2, 所以x2 为进基变量. 3. p2的坐标有正分量存在，因为3与x6 那一行相对应，所以x6 为离基变量；故x2对应列与x6对应行的相交处的4为主元素；xB x1 x2 x3 x4 x5 x6 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1x3 x4 x5 x612 8 16 12 2 3c -2 -3 0 0 0 0 6 4 -- 30 0 0 0 cB0 0 0 0null4. 以“4”为主元素Gauss消去，进行行初等变换xB x1 x2 x3 x4 x5 x6 x3 x4 x5 x2c -2 -3 0 0 0 0 cB0 0 0 -3 0 1 0 0 -1/2 6 2 0 0 0 0 -3/4 3 2 4 --0 1 0 0 0 1/4 3 4 0 0 0 1 0 161 0 0 1 0 -1/2 2这行除以4xB x1 x2 x3 x4 x5 x6 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1x3 x4 x5 x612 8 16 12 2 3c -2 -3 0 0 0 0 6 4 -- 30 0 0 0 cB0 0 0 0这行不变第4行的-1/2加到这行第4行的-1/2加到这行第4行的-3/4加到检验数行null 5. max{1}=2= 1, 所以x1 为进基变量. 6. p1的坐标有正分量存在，因为2与x4 那一行相对应，所以x4 为离基变量；故x1对应列与x4对应行的相交处的1为主元素；null7. 以“1”为主元素Gauss消元，进行行初等变换xB x1 x2 x3 x4 x5 x6 x3 x1 x5 x2c -2 -3 0 0 0 0 cB0 -2 0 -30 0 1 -2 0 1/2 2 0 0 0 -2 0 1/4 4 -- 4 120 1 0 0 0 1/4 3 0 0 0 -4 1 2 81 0 0 1 0 -1/2 2第2行的-4倍加到该行xB x1 x2 x3 x4 x5 x6 c -2 -3 0 0 0 0 cB0 0 0 -3第2行的-2倍加到该行第4行的-2加到检验数行x3 x4 x5 x2 0 1 0 0 -1/2 6 2 0 0 0 0 -3/4 0 1 0 0 0 1/4 3 4 0 0 0 1 0 16 1 0 0 1 0 -1/2 23 2 4 --这行不变这行不变退化现象： 有两个或更多的相同时，在相同对应的变量中选择下标最大的那个基变量为离基变量null因为4与x3 ， x5那一行相对应，所以x5 为离基变量;故x6对应列与x5对应行的相交处的2为主元素； 9. p6的坐标有正分量存在， 8. max{6}=1/4= 6, 所以x6 为进基变量.nullxB x1 x2 x3 x4 x5 x6 x3 x1 x5 x2c -2 -3 0 0 0 0 cB0 -2 0 -30 0 1 -2 0 1/2 2 0 0 0 -2 0 1/4 4 -- 4 120 1 0 0 0 1/4 3 0 0 0 -4 1 2 81 0 0 1 0 -1/2 2注： 这时出现了退化问题。即有两个或更多的相同时，在相同对应的变量中选择下标最大的那个基变量为换出变量； 同时如果出现有两个或更多的检验数σ相同时，在相同σ 对应的变量中选择下标最小的那个基变量为进基变量，这样会避免出现“死循环”的现象。null10. 以“2”为主元素Gauss消元，进行行初等变换xB x1 x2 x3 x4 x5 x6 x3 x1 x6 x2c -2 -3 0 0 0 0 cB0 -2 0 -30 0 1 -1 -1/4 0 0 0 0 0 -3/2 -1/8 0 0 1 0 1/2 -1/8 0 2 0 0 0 -2 1/2 1 41 0 0 0 1/4 0 4该行除以2xB x1 x2 x3 x4 x5 x6 c -2 -3 0 0 0 0 cB0 -2 0 -3第3行的-1/4倍加到该行第3行的-1/8加到检验数行x3 x1 x5 x20 0 1 -2 0 1/2 2 0 0 0 -2 0 1/4 0 1 0 0 0 1/4 3 0 0 0 -4 1 2 8 1 0 0 1 0 -1/2 24 -- 4 12第3行的1/4加到该行第3行的-1/8加到该行所有检验数都小于等于0，当前的基本可行解是最优解nullxB x1 x2 x3 x4 x5 x6 x3 x1 x6 x2c -2 -3 0 0 0 0 cB0 -2 0 -30 0 1 -1 -1/4 0 0 0 0 0 -3/2 -1/8 0 0 1 0 1/2 -1/8 0 2 0 0 0 -2 1/2 1 41 0 0 0 1/4 0 4所有检验数都小于等于0，当前的基本可行解 x=(4,2,0,0,0,4)T是最优解原问题的最优解是x=(4,2)T，最优值是f=2*4+3*2=14null例2. 利用单纯形算法求解如下的线性规划问题。解： 1. 化为标准型得到：A中存在3阶单位矩阵选取 作为基变量，得到一个基本可行解null 2. max{2}=2= 2, 所以x2 为进基变量. 3. p2的坐标有正分量存在，因为2与x6 那一行相对应，所以x6 为离基变量；故x2对应列与x6对应行的相交处的2为主元素；建立单纯形表xB x1 x2 x3 x4 x5 x6 x4 x5 x6c 1 -2 1 0 0 0 cB0 0 0 1 1 -2 1 0 0 10-1 2 -1-1 2 -4 0 0 1 4 2 -1 4 0 1 0 810 -- 20 0 0 null4. 以“2”为主元素进行Gauss消去，即进行行初等变换xB x1 x2 x3 x4 x5 x6 x4 x5 x6c 1 -2 1 0 0 0 cB0 0 0 1 1 -2 1 0 0 10-1 2 -1-1 2 -4 0 0 1 4 2 -1 4 0 1 0 810 -- 20 0 0 xB x1 x2 x3 x4 x5 x6 x4 x5 x2c 1 -2 1 0 0 0 cB 0 0 -23/2 0 0 1 0 -1/2 8 0 0 3 0 0 -1-1/2 1 -2 0 0 1/2 23/2 0 2 0 1 1/2 10-- 5 --这行除以2第3行的1/2加到该行第3行的-1/2加到该行第3行的-1倍加到检验数行null 5. max{3}=3= 3, 所以x3 为进基变量. 6. p3的坐标有正分量存在，因为5与x5 那一行相对应，所以x5 为离基变量；故x3对应列与x5对应行的相交处的2为主元素；null7. 以“2”为主元素进行Gauss消去，即进行行初等变换xB x1 x2 x3 x4 x5 x6 x4 x5 x2c 1 -2 1 0 0 0 cB 0 0 -2xB x1 x2 x3 x4 x5 x6 x4 x3 x2c 1 -2 1 0 0 0 cB 0 1 -23/2 0 0 1 0 -1/2 8-9/4 0 0 0 -3/2 -7/4 1 1 0 0 1 1 123/4 0 1 0 1 1/4 5第2行加到该行这行除以2这行不变第2行的-3/2倍加到检验数行3/2 0 0 1 0 -1/2 83/2 0 2 0 1 1/2 10-1/2 1 -2 0 0 1/2 2-- 5 -- 0 0 3 0 0 -1所有检验数都小于等于0，当前的基本可行解是最优解nullxB x1 x2 x3 x4 x5 x6 x4 x3 x2c 1 -2 1 0 0 0 cB 0 1 -23/2 0 0 1 0 -1/2 8-9/4 0 0 0 -3/2 -7/4 1 1 0 0 1 1 123/4 0 1 0 1 1/4 5检验数全部小于等于0，于是得到最优解： x = (0,12,5,8)T 目标函数的最小值为： f = -19null例3. 利用单纯形算法求解如下的线性规划问题。解： x6 ，x7 ， x 5对应的是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。min x6+ x7 s.t. x1 +x2 - x3 + x6 = 2 x1 - x2 - x4 + x7 = 1 x1 + x5 = 3 xj ≥0 , j=1,2,……,7nullxB x1 x2 x3 x4 x5 x6 x7 1 1 -1 0 0 1 0 1 -1 0 -1 0 0 1 1 0 0 0 1 0 0x6 x7 x5 2 1 3 2 0 -1 -1 0 0 00 2 -1 1 0 1 -1 1 -1 0 -1 0 0 1 0 1 0 1 1 0 -1x6 x1 x5 1 1 2 0 2 -1 1 0 0 -2cB1 1 0 2 1 3 1/2 -- 21 0 0x2 x1 x50 1 -1/2 1/2 0 1/2 -1/2 1 0 -1/2 -1/2 0 1/2 1/2 0 0 1/2 1/2 1 -1/2 -1/2 1/2 3/2 3/2 0 0 0 0 0 -1 -10 0 0min x6+ x7 s.t. x1 +x2 - x3 + x6 = 2 x1 - x2 - x4 + x7 = 1 x1 + x5 = 3 xj ≥0 , j=1,2,……,7c 0 0 0 0 0 1 1 null所有判别数 zj-cj≤0 ，因此达到最优解null作业：用单纯形法解下列问题：1.2.3.4.