Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,对应(duyng)目标系数,原线性规划(xin xn u hu)可改写为：,约束条件,第一页，共13页。,第二页，共13页。,单纯形表的几个特征:,1、检验(jinyn)数:,非基底的检验(jinyn)数(等于对应的目标系数),cj zj=(CNCBB-1N),基变量的检验(jinyn)系数为零，即,cj zj=CBCBB-1 B=0,进一步，非基底变量可分解XN（XN1，Xs），其中 XN1 表示除去松弛(sn ch)变量以后的非基变量；Xs是松弛(sn ch)变量，其目标系数为零。,Xs非基底(j d)的检验数cj zj=(0CBB-1)=CBB-1,所有的检验数可用CCBB-1A与CBB-1表示,第三页，共13页。,2、规则(guz)的表达形式,第四页，共13页。,1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；,XB为基变量(binling)时，经基底转换后有XB,z的表达式:,2 改进(gijn)的单纯形算法,所有的检验数可用CCBB-1A与CBB-1表示,Xs非基底(j d)的检验数cj zj=(0CBB-1)=CBB-1,精品(jn pn)课件！,分块的系数矩阵(j zhn)可用下列表格形式表示：,精品(jn pn)课件！,所有的检验数可用CCBB-1A与CBB-1表示,3、单纯形表的矩阵表达形式,一般线性规划问题(wnt)具体对应如下：,3、单纯形表的矩阵表达形式,将目标和约束条件改写为：,z+CBXB+C NXN+0 Xs=0，N,s对应非基变量(binling),B XB+NXN+IXs=b,XB为基变量(binling)时，经基底转换后有XB,z的表达式:,XB+B-1 N1XN+B-1Xs=B-1b,z+(C N-CB B-1 N)XN1-CB B-1 Xs=-CB B-1 b,用矩阵表示为,第五页，共13页。,分块的系数矩阵(j zhn)可用下列表格形式表示：,一般线性规划问题(wnt)具体对应如下：,第六页，共13页。,最后(zuhu)表,初始(ch sh)表,第七页，共13页。,1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；,2）初始单纯形表中基变量Xs=b，迭代后的表中变为XB=B-1b；,3）初始单纯形表中的系数矩阵A，I=B，N，I，迭代后的表中约束(yush)系数矩阵为：,B-1A，B-1I=B-1B，B-1N，B-1I=I，B-1N，B-1I；,4）初始单纯形表中变量xj的系数向量为Pj，迭代后为Pj，则有Pj=B-1 Pj；,第八页，共13页。,2 改进(gijn)的单纯形算法,主要(zhyo)是计算 的差别,第九页，共13页。,第十页，共13页。,精品(jn pn)课件！,分块的系数矩阵(j zhn)可用下列表格形式表示：,cj zj=(CNCBB-1N),将目标和约束条件改写为：,分块的系数矩阵(j zhn)可用下列表格形式表示：,2 改进(gijn)的单纯形算法,精品(jn pn)课件！,3）初始单纯形表中的系数矩阵A，I=B，N，I，迭代后的表中约束(yush)系数矩阵为：,B-1A，B-1I=B-1B，B-1N，B-1I=I，B-1N，B-1I；,1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；,精品(jn pn)课件！,所有的检验数可用CCBB-1A与CBB-1表示,XB为基变量(binling)时，经基底转换后有XB,z的表达式:,3、单纯形表的矩阵表达形式,将目标和约束条件改写为：,用矩阵表示为,精品(jn pn)课件！,第十一页，共13页。,精品(jn pn)课件！,第十二页，共13页。,用改进的单纯形法求解下面的线性规划(xin xn u hu)问题,第十三页，共13页。,