第1章线性规划与单纯形法 第4节 单纯形法的计算步骤
第1章 线性规划与单纯形法 第4节 单纯形法的计算步骤
4.1单纯形表 ·为了便于理解计算关系，现设计一种计 算表，称为单纯形表，其功能与增广矩 阵相似 ·将(1-22)式与目标函数组成n+1个变量， m+1个方程的方程组
4.1 单纯形表 • 为了便于理解计算关系，现设计一种计 算表，称为单纯形表，其功能与增广矩 阵相似 • 将(1-22)式与目标函数组成n+1个变量， m+1个方程的方程组
线性规划的方程组 X1 +41m+1Xm+1+…+a1nXn=b1 X2 +2m+1Xm+1+…+a2nXn=b2 Xm+amm+Ixmamnxn =bm -Z+Cx+Cmxm+Cm+1xm+1++Cnxn =0
线性规划的方程组 0 11 11 11 2 112 2 2 1 111 1 1 ++++− =++ + =++ + =++ + + + = ++ ++ ++ ++ mmmm nn mmmm mnmn mm nn mm n n xcxcxcxcz bxaxax x bxaxa x bxaxa " " " % "
·为了便于迭代运算，可将上述方程组写成增 广矩阵形式 X2…XmXm+1 … Xn b 1,m+1 ain a2,m+1 02n b2 : 0 m,m+1 bm C2 Cm Cm+l Cn 0
•为了便于迭代运算，可将上述方程组写成增 广矩阵形式 ⎟⎟⎟⎟⎟⎟⎟⎠⎞ ⎜⎜⎜⎜⎜⎜⎜⎝⎛ − + + + + + 1 0 0000 0100 0010 2 1 21 1 1, 1,2 2 1,1 1 21 1 m mm n mm mn m n m n mm n b b b cccc c a a a a a a xxxxz bx # " " " " ## ## # " " " " "
·若将z看作不参与基变换的基变量，它与 1,x2,,X的系数构成个基 这时可采用行初等变换将c1,C2,,cn变换为 零，使其对应的系数矩阵为单位矩阵： X2 Xm Xm+l Xn b 0 a1,m+1 b 2,m+1 b : am,m+l bm 177 …Cn i=l
•若将z看作不参与基变换的基变量，它与 x 1,x 2,…,x m的系数构成一个基 这时可采用行初等变换将c 1,c 2,…,c m变换为 零，使其对应的系数矩阵为单位矩阵: ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − ∑ ∑ ∑ = = = + + + + + + m i ii m m i inin m i m mii mm mn m n m n m m n bc b b b acc acc a a a a a a xxxxz x b 1 2 1 1 1 1 1, 1, 1,2 2 1,1 1 21 1 0001 0000 0100 0010 # " " " " ### # # " " " " "