运筹学 (第三版) 第1章 线性规划 与单纯形 法 《运筹学》教材编写组编 第4节 单纯型法 的计算步 骤 钱颂迪制作 清华大学出版社
运筹学 （第三版） 《运筹学》教材编写组 编 清华大学出版社 第1章 线性规划 与单纯形 法 第4节 单纯型法 的计算步 骤 钱颂迪 制作
第1章线性规划与单纯形法 第4节单纯型法的计算步骤
第1章 线性规划与单纯形法 第4节 单纯型法的计算步骤
第4节单纯型法的计算步骤 根据以上讨论的结果,将求解线性规划 问题的单纯形法的计算步骤归纳如下 如利用单纯型表,求解线性规划问题
第4节 单纯型法的计算步骤 • 根据以上讨论的结果，将求解线性规划 问题的单纯形法的计算步骤归纳如下 • 如利用单纯型表，求解线性规划问题
41单纯型表 为了便于理解计算关系,现设计一种计 算表,称为单纯形表,其功能与增广矩 阵相似,下面来建立这种计算表。 将(1-22)式与目标函数组成n+1个变量, m+1个方程的方程组
4.1 单纯型表 • 为了便于理解计算关系，现设计一种计 算表，称为单纯形表，其功能与增广矩 阵相似，下面来建立这种计算表。 • 将(1-22)式与目标函数组成n+1个变量， m+1个方程的方程组
线性规划的方程组 X 1m+1m+1 +…+a1xn=b nn 2m+1m+1+.+a -b 1°n X+a mm+1.m+1 +…+anxn=b z+C1x1+…+Cmxm+cm+1xm+1+…+Cnxn=0
线性规划的方程组 0 1 1 1 1 1 1 2 2 1 1 2 2 1 1 1 1 1 1 − + + + + + + = + + + = + + + = + + + = + + + + + + + + m m m m n n m m m m m n n m m m n n m m n n z c x c x c x c x x a x a x b x a x a x b x a x a x b
为了便于迭代运算,可将上述方程组写成增广 矩阵形式 -z r1 x m+1 010 1.m+1 In 001 0000 m,m1+1…a mn m+1
为了便于迭代运算，可将上述方程组写成增广 矩阵形式 − + + + + + 1 0 0 0 0 0 0 0 1 0 0 1 0 0 2 1 1 2 1 , 1 2, 1 2 1, 1 1 1 2 1 m m m n m m m n m n m n m m n b b b c c c c c a a a a a a z x x x x x b
若将z看作不参与基变换的基变量,它与 x1,x2,…,xn的系数构成一个基,这时可采用行初 等变换将c1,c2,…,Cn变换为零,使其对应的系数 矩阵为单位矩阵。得到 n 001 0 m+ 000 mn ∑qnmn…->an∑9 i=1
若将z看作不参与基变换的基变量，它与 x1 ,x2 ,…,xm的系数构成一个基，这时可采用行初 等变换将c1 ,c2 ,…,cm变换为零，使其对应的系数 矩阵为单位矩阵。得到 − − − − = = = + + + + + + m i i i m m i n i i n m i m i i m m m m n m n m n m m n c b b b b c c a c c a a a a a a a z x x x x x b 1 2 1 1 1 1 , 1 , 1 2, 1 2 1, 1 1 1 2 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
可根据上述增广矩阵设计计算表, 表12 B B m+1 m+1 n 2.m+1 2 m,m+1 mn C; 6 ;0 m+1 c:a
可根据上述增广矩阵设计计算表， 表1-2。 = = + + = + + + + + − − − − − − − − − − − − → − m i n i i n m i m i i m m i i i m m m m m m n m m n m n B B m m n i j m m n z c b c c a c c a c x b a a c x b a a c x b a a C X b x x x x c c c c c 1 1 1 , 1 1 , 1 2 2 2 2, 1 2 2 1 1 1 1, 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0
表1-2的说明 XB列中填入基变量,这里是x1,x CB列中填入基变量的价值系数,这里是 ,Cn;它们是与基变量相对应的 b列中填入约束方程组右端的常数; c行中填入基变量的价值系数c1,C2,…Cn θ;列的数字是在确定换入变量后,按θ规则 计算后填入; 最后一行称为检验数行,对应各非基变量x的 检验数是 ∑ j=1,2
表1-2的说明 • XB列中填入基变量，这里是x1，x2 ,…，xm； • CB 列 中 填 入 基 变 量 的 价 值 系 数 ， 这 里 是 c1 ,c2 ,…,cm；它们是与基变量相对应的； • b列中填入约束方程组右端的常数； • cj行中填入基变量的价值系数c1 ,c2 ,…,cn； • θi列的数字是在确定换入变量后，按θ规则 计算后填入； • 最后一行称为检验数行，对应各非基变量xj的 检验数是 = − = m i c j ci ai j j n 1 , 1,2,
4.2计算步骤 表1-2称为初始单纯形表,每迭代一步构造一个新单纯 形表 ·计算步骤: (1)按数学模型确定初始可行基和初始基可行解,建立 初始单纯形表。 )计算各非基变量x的检验数,=∑q 检查检验数,若所有检验数 G≤0,j=12,…n 则已得到最优解,可停止计算。否则转入下一步
4.2 计算步骤 • 表1-2称为初始单纯形表，每迭代一步构造一个新单纯 形表。 • 计算步骤： • (1) 按数学模型确定初始可行基和初始基可行解，建立 初始单纯形表。 • (2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 • 则已得到最优解，可停止计算。否则转入下一步。 = = − m i j j i ij c c a 1 , j 0, j =1,2, n