对偶单纯形法(经典运筹学)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,完整版课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,完整版课件,*,对偶单纯形法是求解对偶规划的一种方法,对偶单纯形法,：利用对偶理论得到的一个,求解线性规划问题的方法,2.3 对偶单纯形法,1,完整版课件,对偶单纯形法是求解对偶规划的一种方法对偶单纯形法：利用对偶,单纯形法（原始单纯形法）的,两个条件,：,1、问题为标准型,2、有初始基本可行解,用单纯形法求解,2,完整版课件,单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初,对偶单纯形法的优点：,1、不需要人工变量；,2、当变量多于约束时，用对偶单纯形法可减少迭代次数；,3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。,3,完整版课件,对偶单纯形法的优点：1、不需要人工变量；2、当变量多于约束时,B 可逆,原始单纯形法的基本思路：,4,完整版课件,B 可逆原始单纯形法的基本思路：4完整版课件,关于可行基B的典则形式,检验数,5,完整版课件,关于可行基B的典则形式检验数5完整版课件,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,初始单纯形表：,原始单纯形法的迭代过程：,6,完整版课件,XB XN常数项检验行0 CN- CBB,对偶单纯形法的基本思路：,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,作对偶单纯形表,：,7,完整版课件,对偶单纯形法的基本思路：XB XN常数项检验行0,基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,均非负，,则问题一定无可行解,否则，做换基迭代,8,完整版课件,基B的典则形式X1X2X3X4X5检-2 -1000ZX3-,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,不可行,单纯形法,对偶单纯形法？,21,完整版课件,对应B的基本解：存在检验数0不可行单纯形法对偶单纯形法？,大M法：,两阶段法,单纯形法,单纯形法,22,完整版课件,大M法：两阶段法单纯形法单纯形法22完整版课件,作业：,23,完整版课件,作业：23完整版课件,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,