C7单纯形法矩阵描述改进单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,线性规划与目标规划,第二章 对偶理论与灵敏度分析,Duality Theory and Sensitivity Analysis,第二章 对偶理论与灵敏度分析,Duality Theory and Sensitivity Analysis,内容摘要：,单纯形法的矩阵描述,改进的单纯形法,2.1,单纯形法的矩阵描述,令：,2.1,单纯形法的矩阵描述,基变量,非基变量,RHS,I,0,-,4,-,4,2,12,4,-,-3/4,0,0,0,2,-9,1/4,0,0,1,0,3,3,0,1,0,0,4,16,0,-1/2,0,1,0,1,2,0,1/4,0,-2,0,0,-13,1/4,0,0,1,0,3,3,2,1,-4,0,0,8,0,-1/2,0,1,0,1,2,2,3,0,0,0,3,2,0,1,0,0,4,0,12,0,0,1,0,0,4,16,0,0,0,1,2,1,8,0,0,0,0,3,2,0,-1/8,-3/2,0,0,-14,0,-1/8,1/2,1,0,2,3,1,1/2,-2,0,0,4,0,0,1/4,0,0,1,4,2,内容摘要：,单纯形法的矩阵描述,改进的单纯形法,一、改进单纯形法的计算步骤,在利用单纯形法进行迭代运算时，单纯形表中有一部分数据是不用计算的，也就是在利用单纯形表求解时会有很多不必要的计算。如果利用计算机求解，会占用大量的存储单元从而影响计算效率，改进单纯形法会克服上述的不足。,(1),X,B,X,N,=,B,-1,b,0,然后计算单纯形乘子,Y=C,B,B,-1,(2),计算非基变量,X,N,的检验数,N,=C,N,-C,B,B,-1,N,(3),根据,max(,j,|,j,0)=,j,*,所,对应的非基变量,x,j*,为换入变量，计算,B,-1,P,j,*,若,B,-1,P,j,*,0,，,则无解，停止，否则进入下一步,（,4,）根据,规则求出,，,i*,对应的变量 为换出变量。于是得到新的基变量和基矩阵,（,5,）计算新矩阵的逆矩阵,B,1,1,求出,B,1,1,b,和,C,B,1,B,1,1,重复（,2,）到（,5,）步,改进单纯形法的具体步骤为：,关键问题,新基逆矩阵 的求法,。设 阶 单位阵表示为,为入基变量，,为出基变量，则有 。其中,第,i*,行,2.2,改进单纯形法,步骤,结 束,Y,N,Y,N,无界解,2.2,改进单纯形法,例子,解：,确定初始基,入基,出基,新基,入基,出基,新基,入基,出基,新基,最优解,为：,小结,改进的单纯形法在哪里进行了改进？其核心部分是什么？,单纯形法的矩阵描述及改进的单纯形法为对偶理论的基础,作业：,P73 2.1,（,2,）,