§2单纯形法的表格形式 上面假设x1x2,xm是基变量,即第行约束方程的基变量正好是x,而 经过迭代后,基将发生变化,计算z的式子也会发生变化。如果迭代后的 第行约束方程中的基变量为xg,与xB相应的目标函数系数为cB,系数列 向量为p/(=12,…n)则 B13 )P=(cB)p 其中,(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依 次组成的有序行向量。 单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、 迭代某步骤都用表格的方式来计算求岀,其表格的形式有些像增广矩阵, 而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来 求解第二章的例1 max50X1+100x2+0·s1+0s2+0 +x,+s1=300, 2x1+x2+s=400, X2+s2=250, ⅹ1,ⅹ2,s1,S2,s3≌0.把上面的数据填入如下的单纯形表格 运筹
管 理 运 筹 学 16 §2 单纯形法的表格形式 上面假设x1 ,x2 ,…xm是基变量，即第i行约束方程的基变量正好是xi，而 经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的 第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列 向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依 次组成的有序行向量。 单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、 迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵， 而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来 求解第二章的例1。 max 50x1+100x2+0·s1+0·s2+0·s3 . x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1 , x2 , s1 , s2 , s3≥0. 把上面的数据填入如下的单纯形表格 p j n j ( =1,2, , ) z c c p c p j B Bm j B j = = ( 1 , , , ) ( )
§2单纯形法的表格形式 迭代基变 比值 次数量 50100 B/ap S1 300 300/1 000 001000 s000100 400 400/1 S3 200 250 250/1 z=0 50 100 按照线性规划模型在表中填入相对应的值,如上表所示 在上表中有一个m*m的单位矩阵,对应的基变量为s1,S2,s3; 在z行中填入第列与c列中对应的元素相乘相加所得的值,如 0*1+0*1+0*1=0,所在z行中的第2位数填入 在G=C-行中填入c-z所得的值,如σ1=50-0=50; ·z表示把初始基本可行解代入目标函数求得的目标函数值,即b列*cp列; 初始基本可行解为s=3002=400,s3=250,x1=0,x2=0 由于250/1最小,因此确定s3为出基变量 在列的交汇处为主元,这里是a21,在表中画圈以示区别入基变量所 由于σ2>01>0,因此确定x为入基变量。出基变量所在 管理蓦
管 理 运 筹 学 17 §2 单纯形法的表格形式 • 按照线性规划模型在表中填入相对应的值，如上表所示； • 在上表中有一个m*m的单位矩阵，对应的基变量为s1 ,s2 ,s3； • 在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如 z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0； • 在 行中填入cj -zj所得的值，如 ； • z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列； • 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0; • 由于250/1最小，因此确定s3为出基变量； • 由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所 在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。 j j j = − c z 迭代 次数 基变 量 cB x1 x2 s1 s2 s3 b 比值 Bi 50 100 0 0 0 /ai2 0 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 300 400 250 300/1 400/1 250/1 zj 0 0 0 0 0 50 100 0 0 0 z=0 j j j = − c z 1 = − = 50 0 50 2 1 0