单纯形法的矩阵描述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,（第二版）,刁在筠等 编,高等教育出版社,第,2,章 对偶理论和灵敏度分析,第,1,节,单纯形法的矩阵描述,第,2,章 对偶理论和灵敏度分析,第,1,节,单纯形法的矩阵描述,第,2,节 改进单纯形法,第,3,节 对偶问题的提出,第,4,节 线性规划的对偶理论,第,5,节 对偶问题的经济解释,影子价格,第,6,节 对偶单纯形法,第,7,节 灵敏度分析,第,8,节*参数线性规划,第,1,节,单纯形法的矩阵描述,设线性规划问题,:,目标函数,max z=CX;,约束条件,A,Xb;,非负,条件,X0,给这线性规划问题的约约束条件加入松弛变量以后，得到标准型：,m,ax z=CX+0X,s,;,A,X+,IX,s,=b;X,，,X,s,0,这里,I,是,mm,单位矩阵。,若以,X,s,为基变量，并标记成,X,B,这是将系数矩阵（,A,，,I,）,分为（,B,，,N,）,两块。,B,是基,变量的系数矩阵，,N,是非基变量的系数矩阵。,决策变量分为：,将目标函数的系数,C,分为,C,B,，,C,N,分别对应于基变量,X,B,和非基变量,X,N,。,并且记作,C=,（,C,B,C,N,）。,若经过迭代运算后，可表示为：,相应有,线性规划问题可表示为：,将（,2-2,）式移项及整理后：,令非基变量,=,0,；由上式得到：,（,1,）非,基,变量的系数表示为：,（,2,）,规则表示为：,RHS,值 表示选用,0,的分量,换入变量的系数向量,（,3,）单纯形表与矩阵表示的关系,矩阵关系式：,单纯形表中的数据,基变量,非,基,变量,等式右边,系数矩阵,检验数,小结,1,）掌握矩阵的运算；,2,）理解基矩阵的作用；,3,）了解矩阵运算与单纯表的关系。,