对偶单纯形法运筹学专业知识讲座.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,文档来源于网络，文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,对偶单纯形法的优点：,1、不需要人工变量；,2、当变量多于约束时，用对偶单纯形法可减少迭代次数；,3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。,B 可逆,原始单纯形法的基本思路：,关于可行基B的典则形式,检验数,X,B,X,N,常数项,检验行,0 C,N,-C,B,B,-1,N,Z-C,B,B,-1,b,X,B,E B,-1,N,B,-1,b,初始单纯形表：,原始单纯形法的迭代过程：,对偶单纯形法的基本思路：,X,B,X,N,常数项,检验行,0 C,N,-C,B,B,-1,N,Z-C,B,B,-1,b,X,B,E B,-1,N,B,-1,b,作对偶单纯形表,：,基B的典则形式,X,1,X,2,X,3,X,4,X,5,检,-2,-1,0,0,0,Z,X,3,-3,-1,1,0,0,-3,X,4,-4,-3,0,1,0,-6,X,5,1,2,0,0,1,3,不可行,检验行,0,分析：,若X,3,或X,4,所在的行的a,ij,均非负，,则问题一定无可行解,否则，做换基迭代,X,1,X,2,X,3,X,4,X,5,检,-2,-1,0,0,0,Z,X,3,-3,-1,1,0,0,-3,X,4,-4,-3,0,1,0,-6,X,5,1,2,0,0,1,3,1、确定出基变量：,设b,r,=minb,i,|b,i,0,不可行,单纯形法,对偶单纯形法？,大M法：,两阶段法,单纯形法,单纯形法,作业：,