运筹学_5单纯形表+向量形式(考虑放在第3课)

运筹学OperationalResearchLec.5单纯形表、矩阵表达形式Chang’anUniversityZHUTongAutumn2012inXi’[e-mail]目录单纯形表的使用方法单纯形方法的矩阵表达复习：单纯形法的基本步骤第零步：标准形式第一步：基可行解，检查是否终止计算第二步：进基变量第三步：离基变量第四步：旋转操作/枢轴变换/高斯－若当行变换第五步：新的基可行解，检查是否终止计算向下一基可行解出发复习：单纯形表基变量原始价值系数基变量全部变量原始价值系数CjbCBXB基变量系数非基变量系数C1C2……Cmx1x2……xm100010……001ai，jb1b2……bm检验行Cj-∑Ciaij∑Cibii=1mi=1mi=1m矩阵表达形式0Xbs.tAXCXZmax其中，字母含义C为n维行向量[1×n]，X为n维列向量[n×1]b为m维列向量[m×1]，A为m行n列矩阵[m×n]nixbxaxaxabxaxaxabxaxaxatsxcxcxcZimnmnmmnnnnnn1,0..max221122222121112121112211矩阵表达形式向量形式maxz=CXs.t.AX=bX≥0B为基，因此，X分为基变量和非基变量：XB和XNA分为基和非基变量之前的系数：B和NC分为：CB和CNC为n维行向量[1×n]X为n维列向量[n×1]b为m维列向量[m×1]A为m行n列矩阵[m×n]矩阵表达形式向量形式maxz=CXs.t.AX=bX≥0新形式maxz=(CB,CN)(XB,XN)’s.t.(B,N)(XB,XN)’=b见书19页推导原始问题maxz＝3x1＋4x2s.t.x1＋x2≤6x1＋2x2≤82x2≤6x1，x2≥0以下讲单纯形表的应用，同时讲其代数和几何意义原始问题的图示3x2x1486maxz＝3x1＋4x2是斜率为-3/4的直线簇x1，x2≥02x2≤6x1＋2x2≤8x1＋x2≤66标准形式（0）已经化为标准形式，产生3个松弛变量注意：松弛变量表示点与约束直线之间的线性冗余（a1x1＋a2x2），非距离冗余是这个点沿某轴到达某条线的距离的加权和；从截距角度看更好理解例如，第2个方程，如x4＝6，说明x1轴上截距差6，x2轴上截距差3。maxz＝3x1＋4x2s.t.x1＋x2＋x3＝6x1＋2x2＋x4＝82x2＋x5＝6x1，x2，x3，x4，x5≥0初始基本可行解（1）54321,,,,100200102100111PPPPPAP3、P4、P5构成一个基；x3，x4，x5为基变量；初始基本可行解（1）用非基变量表示目标和基变量单位阵以便计算目标值与解maxz＝0＋3x1＋4x2s.t.x3＝6－x1－x2x4＝8－x1－2x2x5＝6－2x2x1，x2，x3，x4，x5≥0基解为（0，0，6，8，6），可行，是一个基本可行解此时，目标值为0初始基本可行解（1）3x2x1486maxz＝3x1＋4x2是斜率为-3/4的直线簇x1，x2≥02x2≤6x1＋2x2≤8x1＋x2≤66单纯形表基变量原始价值系数基变量全部变量原始价值系数CjbCBXB基变量系数非基变量系数C1C2……Cmx1x2……xm100010……001ai，jb1b2……bm检验行Cj-∑Ciaij∑Cibii=1mi=1mi=1m单纯形表示例maxz＝3x1＋4x2s.t.x1＋x2＋x3＝6x1＋2x2＋x4＝82x2＋x5＝6x1，x2，x3，x4，x5≥0基变量原始价值系数基变量34000bCBXB变量系数000x3x4x5111001201002001686检验行340000进基变量（2）z＝0＋3x1＋4x2选择x2，比x1增加的速度更快，因此选择x2进maxz＝0＋3x1＋4x2s.t.x3＝6－x1－x2x4＝8－x1－2x2x5＝6－2x2x1，x2，x3，x4，x5≥0进基变量（2）（2）进基变量＋（3）离基变量进基变量由0变为非0，x1仍未0，代表在x2轴上离基变量（冗余）变为0，把其他变为0后，x2最小的一个3x2x1486x1，x2≥02x2≤6x1＋2x2≤8x1＋x2≤66离基变量（3）X1＝0如x3＝0，则x2＝6如x4＝0，则x2＝4如x5＝0，则x2＝3选择最小的一个，或者选符合约束条件的一个maxz＝0＋3x1＋4x2s.t.x3＝6－x1－x2x4＝8－x1－2x2x5＝6－2x2x1，x2，x3，x4，x5≥0离基变量（3）（2）进基变量＋（3）离基变量进基变量由0变为非0，x1仍未0，代表在x2轴上离基变量（冗余）变为0，把其他变为0后，x2最小的一个3x2x1486x1，x2≥02x2≤6x1＋2x2≤8x1＋x2≤66单纯形表进基离基根据max（Ϭj0）＝Ϭk确定xk进基Θ＝min（bi/aik|aik0）＝bl/alk确定xl为离基变量单纯形表进基离基查看检验数基变量原始价值系数基变量Cj34000bCBXB变量系数000x3x4x511100120100[2]001686检验行34000043,x2进基Min{6/1,8/2,6/2}=3因此，x5离基旋转运算（4）X2进基，x5离基，基变量x2，x3，x4用非基变量表示基变量单位阵、目标值maxz＝3x1＋4x2s.t.x1＋x2＋x3＝6x1＋2x2＋x4＝82x2＋x5＝6x1，x2，x3，x4，x5≥0maxz＝12＋3x1－2x5s.t.x1＋（3－½x5）＋x3＝6x1＋（6－x5）＋x4＝8x2＋½x5＝3x1，x2，x3，x4，x5≥0单纯形表旋转运算旋转运算可以表示为矩阵运算单纯形表旋转运算查看检验数基变量原始价值系数基变量Cj34000bCBXB变量系数000x3x4x511100120100[2]001686检验行基变量原始价值系数基变量Cj34000bCBXB变量系数004x3x4x21010-1/21001-101001/2323检验行3000-212枢轴变换的本质：选择在某个方程中，将基变量放左端，用非基变量表示新的基本可行解，终止条件（5）解为（0,3,3,2,0），目标值为12maxz＝12＋3x1－2x5s.t.x1＋（3－½x5）＋x3＝6x1＋（6－x5）＋x4＝8x2＋½x5＝3x1，x2，x3，x4，x5≥0新的基本可行解，终止条件（5）maxz＝12＋3x1－2x5X1的系数为3，x1≥0，说明z还有增加的可能向下一目标出发直到求出最优解书上例1-12复习今天的学习内容单纯形方法的矩阵表达单纯形表的使用方法