基础运筹学教程（第三版）- 第一章-4 单纯形法.ppt

*Cj→-1-1-1-1-1-1-1-1θiCBXBbx1x2x3x4x5x6x7x8-1x15011/21/21/20000--1x5100/302/31/301[2/3]1/3050-1x875/20-1/81/85/801/23/4175-z725/601/24-1/241/801/61/120-1x15011/21/21/20000100-1x650011/203/211/20--1x825/20-5/8-1/8[5/8]-3/401/2120-z225/20-1/8-1/81/8-1/4000-1x1401[1]3/503/50-2/5-4/5-1x650011/203/211/20-1x4200-1-1/51-6/504/58/5-z11000-1/100-1/100-1/10-1/5得X*=(40,0,0,20,0,50,0,0)T，z*=-110。所得结果给出的最优下料方案为：40根按第1种截法，20根按第4种截法，50根按第6种截法，所用圆钢根数110根。********************第一章线性规划*五.单纯形法(SM)原理设有线性规划问题：§1-3单纯形法可展开为下式：*不失一般性，讨论系数矩阵A中含有m阶单位阵的情形，也即n个系数列向量中，含有m个线性无关的单位列向量。假定：m阶单位阵位于系数矩阵的前m列，则有：*用简洁的形式表示为：由再令则目标函数可变形为：＝*其中：为基变量，为非基变量，为检验数，其中的基变量对应单位列向量，故其检验数恒为零。即：由于单纯形法是一种迭代计算法，求解结果又存在多种情况，所以必须先要对初始解的确定与解的判别作出分析，然后再考虑解的改进。*2.基可行解为最优解的判别定理定理1：若σj≤0(j=m+1,m+2,…,n)，则基可行解X(0)=(b1,b2,…,bm,0,…,0)T为最优解。证：因xj≥0(j=m+1,m+2,…,n)，如果σj≤0，则：又因为在X(0)中，xm+1=xm+2=…=xn=0，故z(X(0))=z0，即X(0)为最优解。1.初始基可行解的确定令非基变量xj=0(j=m+1,m+2,…,n)，则基变量xi=bi(i=1,2,…,m)，于是得初始基可行解：X(0)=(b1,b2,…,bm,0,…,0)T。*3.无界解判别定理定理2：若存在一检验数σm+k0，而ai,m+k≤0(i=1,2,…,m)，则线性规划为无界解（或称为无最优解）证：由于构造新的可行解：*令：则：因故：由X(1)的作法可知，对任意λ0，X(1)都是可行解，于是，对于：当λ→+∞时，因σm+k0，故z→+∞，因此线性规划为无界解（或称为无最优解）。*4.基可行解的改进若判别定理1与定理2皆不满足，则通过下述迭代步骤，可获LP最优解。(1)选入基变量为使目标函数值有较大幅度的增加，由前面引例讨论可知，可选择最大正检验数对应的非基变量为入基变量，即：所对应的非基变量xk为入基变量，将其由0增加至某一正值时，目标函数值必随之增加，该原则称为最大正检验数法则（最大σ法则）。*(2)定出基变量入基变量xk由于受到约束方程组的限制而不能任意增大，必需定出合理的上界值。因为所以有：当aik0时，有由此，xk的合理上界值θ应取为：，且*该原则称为ark称为主元，其所在行(列)称为主行(列)。记第r个约束方程中基变量的下标为h，则xh为出基变量。于是，所定出的新基变