§1单纯形法的基本思路和原理 2.出基变量的确定 在确定了x为入基变量之后,我们要在原来的3个基变量s1,s2,s3中确 定一个出基变量,也就是确定哪一个基变量变成非基变量呢? 如果把s3作为出基变量,则新的基变量为x2,s1,S2,因为非基变量x1=s3=0, 我们也可以从下式: x2+s1=300, X2+s2=400, X2=250, 求出基本解:x1=0,x2=250,s1=50,s2=150,s3=0。因为此解满足非负 条件,是基本可行解,故s3可以确定为出基变量 能否在求出基本解以前来确定出基变量呢? 以下就来看在找出了初始基本可行解和确定了入基变量之后,怎么样的 基变量可以确定为出基变量呢?或者说出基变量要具有什么条件呢? 管理蓦
管 理 运 筹 学 11 §1 单纯形法的基本思路和原理 2. 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确 定一个出基变量，也就是确定哪一个基变量变成非基变量呢？ 如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3 =0， x2 +s1 =300， x2+s2 =400， x2 =250， 求出基本解：x1 =0，x2 =250，s1 =50，s2 =150，s3 =0。 条件，是基本可行解，故s3可以确定为出基变量。 能否在求出基本解以前来确定出基变量呢？ 以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的 基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？
§1单纯形法的基本思路和原理 我们把确定出基变量的方法概括如下:把已确定的入基变量在各约束方 程中的正的系数除其所在约束方程中的常数项的值,把其中最小比值所 在的约東方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变 换中可以确保新得到的b值都大于等于零 在本例题中约束方程为 x1+x2+S1=300 2x1+x2+S2=400 x2+S3=250 在第二步中已经知道x2为入基变量,我们把各约束方程中x2的为正的系数除 对应的常量,得 b50=300,a12 b,400 400 b3250 250 12 C 32 管理蓦 12
管 理 运 筹 学 12 §1 单纯形法的基本思路和原理 我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方 程中的正的系数除其所在约束方程中的常数项的值，把其中最小比值所 在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变 换中可以确保新得到的bj值都大于等于零。 在本例题中约束方程为 在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除 对应的常量，得 1 2 1 1 2 2 2 3 300, 2 400, 250. x x s x x s x s + + = + + = + = 1 2 3 12 22 32 300 400 250 300, 400, 250. 1 1 1 b b b a a a = = = = = =
§1单纯形法的基本思路和原理 其中的值最小,所以可以知道在原基变量中系数向量为e3=(0,0.1) 的基变量s3为出基变量,这样可知x2,s1,S2为基变量,x1,s3为非基变量。 令非基变量为零,得 300 X2=250 求解得到新的基本可行解ⅹ=0,x2=250.=50,s2=150 这时目标函数值为 50X1+100X2=50×0+100×250=25000。 显然比初始基本可行解x1=0x2=0,s1=300s3-250时的目标函数值为0要好 得多 下面我们再进行检验其最优性,如果不是最优解还要继续进行基变 换,直至找到最优解,或者能够判断出线性规划无最优解为止 运筹 13
管 理 运 筹 学 13 §1 单纯形法的基本思路和原理 其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 这时目标函数值为 50x1+100x2=50×0+100×250=25000。 显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好 得多。 下面我们再进行检验其最优性，如果不是最优解还要继续进行基变 换，直至找到最优解，或者能够判断出线性规划无最优解为止。 3 32 b a 3 (0,0,1) T e =
§2单纯形法的表格形式 在讲解单纯形法的表格形式之前,先从一般数学模型里推导出检验 数O;的表达式。 可行基为m阶单位矩阵的线性规划模型如下(假设其系数矩阵的前m 列是单位矩阵) max 2=Cx, +C2x2 t'+Cnx 1.m+1m+1 x +a 2.m+1m+1 +a x= b m,m+1m+1+.+am,x=b m 2 以下用x(=12…,m)表示基变量,用x(j=m+1,m+2,…,m) 表示非基变量。 运莓
管 理 运 筹 学 14 §2 单纯形法的表格形式 在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验 数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m 列是单位矩阵）： 以下用 表示基变量，用 表示非基变量。 j ( ) 1 1 2 2 1 1, 1 1 1, 1 2 2, 1 1 2, 2 , 1 1 , max . , , , 0. 1,2, , n n m m n n m m n n m m m m m n n m j z c x c x c x x a x a x b x a x a x b x a x a x b x j n + + + + + + = + + + + + + = + + + = + + + = = x i m i ( =1,2, , ) x j m m n j ( = + + 1, 2, , )
§2单纯形法的表格形式 把第诠个约束方程移项,就可以用非基变量来表示基变量x, i,m+1m+1 i,m+2m+2 1.2.….m 把以上的表达式带入目标函数,就有 cx+C2x2+…+cx=∑cx+∑ j=m+1 +∑(c1-=)=0+∑ =m+1 j=m+1 其中 ∑c ∑can=ca1+ca2y+…+Cnam=(c1 2 m i=1 )p 运筹 15
管 理 运 筹 学 15 §2 单纯形法的表格形式 把第i个约束方程移项，就可以用非基变量来表示基变量xi， 把以上的表达式带入目标函数，就有 其中： ( ) , 1 1 , 2 2 , 1 . 1,2, , i i i m m i m m i n n n i ij j j m x b a x a x a x b a x i m + + + + = + = − − − − = − = ( ) 1 1 2 2 1 1 0 0 1 1 m n n n i i j j i j m n n j j j j j j m j m z c x c x c x c x c x z c z x z x = = + = + = + = + + + = + = + − = + 0 1 , ; m i i j j j i z c b c z = = = − ( ) ( ) 1 2 1 1 2 2 1 2 1 1 2 , , , , , , j m j j i ij j j m mj m i mj m j a a z c a c a c a c a c c c a c c c p = = = + + + = =