第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 # " " " " ### # # " " " " "
单纯形表 表1-2 Ci→ C Cm Cm+l 。泰 Cn 0 XB b x1 Xm Xm+l 七n C x1 b 1 。。。 0 1,m+1 n 81 C2 … b2 0 0 2,m+1 Q2n 82 .: .… Cm Xm 0 1 Am,m+I m -7 cb 0…0ca-2e i=l …6
单纯形表 表1-2 ∑ ∑ ∑ = = + + = + + + + + −− − − → m i n ini m i m mii m i ii m m m mm mn m m n m n B B m m n i j m m n bcz acc acc bxc a a bxc a a bxc a a XC b x xx x c c cc c 1 1 1 1, 1 1, 22 2 1,2 2 2 11 1 1 1, 1 1 1 1 1 1 00 10 00 01 " " " " ##### # ## " " " " " " " θ θ θ θ
表1-2的说明 ·X列中填入基变量，这里是x1’X2,,X ·C列中填入基变量的价值系数，这里是 C1,C2,,Cm:它们是与基变量相对应的： ·b列中填入约束方程组右端的常数； ·c行中填入基变量的价值系数c1,c2,,Cn 0:列的数字是在确定换入变量后，按0规 则计算后填入； 最后一行称为检验数行，对应各非基变量x; 的检验数是 c-∑ca,j=1,2,…,n i=l
∑= − = m i j iji jacc n 1 ",,2,1, • X B列中填入基变量，这里是x 1，x 2,…，x m ； • C B列中填入基变量的价值系数，这里是 c 1,c 2,…,c m；它们是与基变量相对应的； • b列中填入约束方程组右端的常数； • c j行中填入基变量的价值系数c 1,c 2,…,c n ； • θ i列的数字是在确定换入变量后，按θ规 则计算后填入； • 最后一行称为检验数行，对应各非基变量x j 的检验数是 表1-2的说明
4.2计算步骤 ·表1-2称为初始单纯形表，每迭代一步构造一个新 单纯形表。 ·计算步骤： (1)按数学模型确定初始可行基和初始基可行解， 建立初始单纯形表 (2)计算各非基变量x的检验数，¤，=C-∑c4 检查检验数，若所有检验数 i=1 oj≤0，j=1,2,…n 则已得到最优解，可停止计算。否则转入下一步
4.2 计算步骤 • 表1-2称为初始单纯形表，每迭代一步构造一个新 单纯形表。 • 计算步骤： (1) 按数学模型确定初始可行基和初始基可行解， 建立初始单纯形表 (2) 计算各非基变量x j的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。 ∑= = − m i j j i aij c c 1 σ σ j ≤ 0 , j = 1 , 2 , " n
计算步骤-确定换入/出变量 (3)在0；>0，jm+1,,n中， 若有某个ok 对应x的系数列向量P≤0，则此问题是 无界，停止计算。 否则，转入下一步。 (4)根据max(o,>0)=ok,确定x为换入 变量，按0规则计算 x为换出变量 X的第1元
计算步骤-确定换入/出变量 (3) 在σ j＞0,j=m+1, …,n中，若有某个σ k 对应 x k的系数列向量P k≤0，则此问题是 无界，停止计算。 否则，转入下一步。 (4) 根据max(σ j＞0)=σ k，确定 x k为换入 变量，按θ规则计算 lk l ik ik i a b a a b =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ θ = min > 0 x l为换出变量 X B的第 l 元
计算步骤-旋转运算 (5)以4为主元素进行迭代（即用高斯消去法 或称为旋转运算)，把x,所对应的列向量 k 0 Qzk 0 Pk二 变换→ k 1 《第行 k 0 将X列中的x,换为x, 得到新的单纯形表 (6)重复(2)~(5)，直到终止
(5) 以 alk为主元素进行迭代(即用高斯消去法 或称为旋转运算)，把 x k所对应的列向量 将X B列中的 x l换为 x k，得到新的单纯形表 (6)重复(2)～(5)，直到终止 行第 变换 l a a a a P mk lk k k k ← ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⇒ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 1 0 0 2 1 # # # # 计算步骤-旋转运算