第3章(单纯形法的运用与改进)1

《第3章(单纯形法的运用与改进)1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3单纯形法的运用与改进初始可行基与人工变量法求上界变量的单纯形法单纯形法的讨论单纯形法的矩阵描述改进单纯形法矿业系统工程电子教案x2x1zo10/7/202113单纯形法的运用与改进3.1初始可行基与人工变量法辅助问题及人工变量两阶段法大Ｍ法多余约束的剔除极小化问题的直接求解10/7/202123单纯形法的运用与改进3.1.1辅助问题及人工变量(A)maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=

2、bmx1,x2,…,xn≥0(B)max=-xn+1-xn+2-…-xn+ms.t.a11x1+…+a1nxn+xn+1=b1a21x1+…+a2nxn+xn+2=b2……am1x1+…+amnxn+xn+m=bmx1~xn≥0,xn+1~xn+m≥0X0=(x10,x20,…,xn0)TY0=(x10,x20,…,xn0,0,…,0)T0=0X'=(x1',x2',…,xn')T'=0Y'=(x1',x2',…,xn',xn+1',…,xn+m')T10/7/202133单纯形法的运用与改进辅助问题的性质问题(B)是问题

3、(A)的辅助问题，(B)中的单位矩阵称为人工基，它对应的m个变量叫做人工变量(artificialvariables)。辅助问题(B)有两个特点：(i)约束方程为典式，表明有可行解；(ii)目标函数有上界，一定有最优解。(B)max=-xn+1-xn+2-…-xn+ms.t.a11x1+…+a1nxn+xn+1=b1a21x1+…+a2nxn+xn+2=b2……am1x1+…+amnxn+xn+m=bmx1~xn≥0,xn+1~xn+m≥0B0=(Pm+1,Pm+2,…,Pn)Y(0)=(0,…,0,b1,b2…,bm)T10

4、/7/202143单纯形法的运用与改进辅助问题的性质问题(B)是问题(A)的辅助问题，(B)中的单位矩阵称为人工基，它对应的m个变量叫做人工变量(artificialvariables)。辅助问题(B)有两个特点：(i)约束方程为典式，表明有可行解；(ii)目标函数有上界，一定有最优解。(B)max=-xn+1-xn+2-…-xn+ms.t.a11x1+…+a1nxn+xn+1=b1a21x1+…+a2nxn+xn+2=b2……am1x1+…+amnxn+xn+m=bmx1~xn≥0,xn+1~xn+m≥0B0=(Pm+1,P

5、m+2,…,Pn)Y(0)=(0,…,0,b1,b2…,bm)T10/7/202153单纯形法的运用与改进原理与应用定理3.1问题(A)有可行解的充要条件是：问题(B)的目标函数最优值等于零。推论3.1问题(B)的最优基的基变量组中不含人工变量，则这个最优基和相应的基最优解分别是问题(A)的可行基和基可行解。10/7/202163单纯形法的运用与改进原理与应用(续)结论3.1问题(B)的最优基的第l个基变量为人工变量，并且目标函数最优值等于零，而最优单纯形表中非人工变量在第l行的系数全为零，则表示问题(A)的第l个约束方程是多余

6、的，应予删除。标准形式线性规划问题的m个约束方程被假设为是相互独立的，上述结论中的情形在理论上不会出现，但在实际中经常碰到。10/7/202173单纯形法的运用与改进3.1.2两阶段法依据推论3.1，可将问题(A)的求解分为两阶段：阶段1从人工基开始，用单纯形法求解问题(B)，或是得到问题(A)的一个可行基和相应的基可行解，或是证实问题(A)沒有可行解；阶段2从阶段1得到的初始可行基出发，用单纯形法寻找问题(A)的最优解，或是查明问题(A)沒有最优解。10/7/202183单纯形法的运用与改进两阶段法算例例3.1用两阶段法求解问

7、题maxz=3x1-x2-x3s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1,x2,…,x5≥0得:maxz=3x1-x2-x3s.t.3x1+x4-2x5=12x2-x5=1-2x1+x3=1x1,x2,…,x5≥0解：max=-x6-x7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,…,x7≥010/7/202193单纯形法的运用与改进表3.1求可行解(阶段I)10/7/2021103单纯形法的运用与改进表3.2

8、求最优解(阶段II)10/7/2021113单纯形法的运用与改进3.1.3大Ｍ法大Ｍ法是将原问题及其辅助问题合并，集线性规划问题可行解和最优解的求证于一役。大Ｍ法也称罚函数法。10/7/2021123单纯形法的运用与改进大Ｍ法算例例3.1maxz=3x1-x2-