改进单纯形法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单纯形法的矩阵描述,1,设线性规划问题可以用如下矩阵形式表示：,目标函数 max,z,=,CX,约束条件,AX,b,非负条件,X,0,2,将该线性规划问题的约束条件加入松弛变量后，得到标准型,：,m,ax z=CX+,0,X,s,AX+IX,s,=b,X，X,s,0,其中，,I,是,m,m,单位矩阵。,3,若以,X,s,为基变量，并标记成,X,B,，可将系数矩阵(,A,，I)分为 (,B,，,N,) 两块。,B,是基变量的系数矩阵，,N,是非基变量的系数矩阵。并同时将决策变量也分为两部分：,相应地可将目标函数系数,C,分为两部分：,C,B,和,C,N,，分别对应于基变量,X,B,和非基变量,X,N,，并且记作:,C,=（,C,B,C,N,）,4,若经过迭代运算后，可表示为：,相应有:,5,线性规划问题可表示为：,6,将（2-2）式移项及整理后得到：,7,令非基变量=0，由上式得到：,8,（1）非基变量的系数表示为：,9,（2）,规则表示为：,RHS值 表示选用0的分量,换入变量的系数向量,10,（3）单纯形表与矩阵表示的关系:,11,单纯形表中的数据:,12,小结,1）掌握矩阵的运算；,2）理解基矩阵的作用；,3）了解矩阵运算与单纯表的关系。,13,改进单纯形法,求解线性规划问题的关键是计算,B,-,1,。,以下介绍一种比较简便的计算,B,-,1,的方法。,14,设,m,n,系数矩阵为,A,，求其逆矩阵时，可先从第,1,列开始。,以,a,11,为主元素,进行变换：,15,然后构造含有（,1,）列，而其他列都是单位列的矩阵,可得到：,16,而后以第,2,列的 为主元素，进行变换,:,然后构造含有（2）列，而其他列都是单位列的矩阵:,可得到:,17,重复以上的步骤，直到获得:,可见，,E,n,E,2,E,1,=A,-1,。,用这方法可以求得单纯形法的基矩阵,B,的逆矩阵,B,-1,18,以例1为例进行计算。,19,第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量：,（2）计算非基变量的检验数，确定换入变量。,20,(3) 确定换出变量,表示选择,0,的元素,（4）基变换计算,将新的基 单位矩阵。计算：,21,（5）计算非基变量的系数矩阵,（6）计算RHS,22,第1步计算结束后的结果:,计算非基变量的检验数，确定换入变量：,23,确定换出变量：,由此得到新的基：,24,计算RHS,第2步计算结束后的结果：,25,第3步：计算非基变量（,x,3,x,5,）的检验数:,确定换出变量:,26,新的基:,计算B的逆矩阵：,27,计算非基变量的检验数:,得到最优解：,目标函数的最优值为：,28,