对偶单纯形法运筹学教育课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,对偶单纯形法运筹学PPT讲座,单纯形法（原始单纯形法）的,两个条件,：,1、问题为标准型,2、有初始基本可行解,用单纯形法求解,对偶单纯形法的优点：,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法：,两阶段法,单纯形法,单纯形法,作业：,