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

《对偶单纯形法(经典运筹学)课件》由会员分享，可在线阅读，更多相关《对偶单纯形法(经典运筹学)课件（24页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,完整版课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,,完整版课件,*,对偶单纯形法是求解对偶规划的一种方法,×,对偶单纯形法,：利用对偶理论得到的一个,求解线性规划问题的方法,2.3 对偶单纯形法,,1,完整版课件,对偶单纯形法是求解对偶规划的一种方法×对偶单纯形法：利用对偶,单纯形法（原始单纯形法）的,两个条件,：,1、问题为标准型,2、有初始基本可行解,用单纯形法求解,,2,完整版课件,单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初,,对偶单纯形

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,初始单纯形表

3、：,原始单纯形法的迭代过程：,,,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,

4、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,=min{b,i,| b,i,<0},则取b,r,所在行的基变量,为出基变量,即取X,4,为出基变量,2、确定入基变量：,原则：,保持检验行系数≤0,,,X,1,X

5、,2,X,3,X,4,X,5,,,检,,,,,,,,X,3,,,,,,,,X,2,,,,,,,,X,5,,,,,,,,,,X,1,X,2,X,3,X,4,X,5,,,检,,,,,,,,X,3,,,,,,,,X,2,,,,,,,,X,1,,,,,,,,-2/3 0 0 -1/3 0 Z+2,-5/3 0 1 -1/3 0 -1,4/3 1 0 -1/3 0 2,-5/3 0 0 2/3 1 -1,0 0

6、 0 -3/5 -2/5 Z+12/5,0 0 1 -1 -1 0,0 1 0 1/5 4/5 6/5,,1 0 0 -2/5 -3/5 3/5,,9,完整版课件,X1X2X3X4X5检-2 -1000ZX3-3-1100-,,10,完整版课件,10完整版课件,对偶单纯形法步骤,：,1、找出一个初始对偶可行解。,把原问题写成该基的典则形式时，,目标函数的系数均≤0,2、判断：,（1）若B,-1,b≥

7、0，则得到最优解,结束,（2）若B,-1,b≥0，,则问题无可行解。,3、换基迭代：,（1）确定出基变量：,（2）确定入基变量,即找出一个基B，,否则转下一步,,11,完整版课件,对偶单纯形法步骤：1、找出一个初始对偶可行解。把原问题写成该,不是典则形式,,X,1,X,2,X,3,X,4,X,5,,检,2,1,0,0,0,Z,X,1,1,1,1,0,0,5,X,4,0,2,1,1,0,5,X,5,0,-4,-6,0,1,-9,0,-1,-2,0,0,Z-10,,,X,1,X,2,X,3,X,4,X,5,,检,,,,,,,X,1,,,,,,,X,4,,,,,,,X,2,,,,,,,0,1,3/2

8、,0,-1/4,9/4,0,0,-2,1,1/2,1/2,1,0,-1/2,0,1/4,11/4,0,0,-1/2,0,-1/4,Z-31/4,,12,完整版课件,不是典则形式X1X2X3X4X5检21000ZX111100,注意,：对偶单纯形法仅限于初始基B对应,的典则形式中目标函数的系数（检,验数）均≤0的情形。,可用对偶单纯形法,B的典则形式,,13,完整版课件,注意：对偶单纯形法仅限于初始基B对应可用对偶单纯形法B的典则,为什么叫对偶单纯形法？,,14,完整版课件,为什么叫对偶单纯形法？14完整版课件,,X,解,检验行,,Z- C,B,B,-1,b,X,B,,B,-1,b,设B为可行基

9、,,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,,原始单纯形法的基本思路：,,15,完整版课件,X解检验行Z- CBB-1bXBB-1b设B,,,X,解,检验行,,Z- C,B,B,-1,b,X,B,,B,-1,b,设B为可行基,,,,,原始单纯形法的迭代过程,：,,16,完整版课件,X解检验行Z- CBB-1bXBB-1b设B,对偶单纯形法的基本思路,：,,17,完整版课件,对偶单纯形法的基本思路：17完整版课件,如何用？,,18,完整版课件,如何用？18完整版课件,求解线性规划问

10、题的,方法与步骤,：,1、 把原问题化为标准型,2、找初始基,，转第3步,，转第4步,3、把问题写成关于基B的典则形式,，用单纯形法,，对偶单纯形法,，转第4步,4、增加人工变量，用大M法或两阶段法求解,,19,完整版课件,求解线性规划问题的方法与步骤：1、 把原问题化为标准型2、找,,,对应B,1,的基本解：,可用对偶单纯形法求解,检验数全部≤0,不,可行,对应B,2,的基本解,用单纯形法求解,可行,,20,完整版课件,对应B1的基本解：可用对偶单纯形法求解检验数全部≤0不可行对,,,对应B的基本解：,存在检验数>0,不可行,单纯形法,×,对偶单纯形法？,×,,21,完整版课件,对应B的基本解：存在检验数>0不可行单纯形法×对偶单纯形法？,大M法：,两阶段法,单纯形法,单纯形法,,22,完整版课件,大M法：两阶段法单纯形法单纯形法22完整版课件,作业：,,23,完整版课件,作业：23完整版课件,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,