《运筹》教学课件对偶理论对偶问题（三）——对偶单纯形法.ppt

《《运筹》教学课件对偶理论对偶问题（三）——对偶单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3对偶单纯形法单纯形法与对偶单纯形法比较单纯形法的步骤对偶单纯形法的步骤如何用？基B的典则形式X1X2X3X4X5检-2-1000ZX3-3-1100-3X4-4-3010-6X5120013不可行检验行≤0分析：若X3或X4所在的行的aij均非负，则问题一定无可行解否则，做换基迭代X1X2X3X4X5检-2-1000ZX3-3-1100-3X4-4-3010-6X51200131、确定出基变量：设br=min{bi

2、bi<0}则取br所在行的基变量为出基变量即取X4为出基变量2、确定入基变量：原则：保持检验行系数≤0X1X2X3X4X5检X3X2X5X1X2X3X4X5检X3X

3、2X1-2/300-1/30Z+2-5/301-1/30-14/310-1/302-5/3002/31-1000-3/5-2/5Z+12/5001-1-100101/54/56/5100-2/5-3/53/5不是典则形式X1X2X3X4X5检21000ZX1111005X4021105X50-4-601-90-1-200Z-10X1X2X3X4X5检X1X4X2013/20-1/49/400-211/21/210-1/201/411/400-1/20-1/4Z-31/4注意：对偶单纯形法仅限于初始基B对应的典则形式中目标函数的系数（检验数）均≤0的情形。可用对偶单纯形法B的典则形式如

4、何用？求解线性规划问题的方法与步骤：1、把原问题化为标准型2、找初始基，转第3步，转第4步3、把问题写成关于基B的典则形式，用单纯形法，对偶单纯形法，转第4步4、增加人工变量，用大M法或两阶段法求解对应B1的基本解：可用对偶单纯形法求解检验数全部≤0不可行对应B2的基本解用单纯形法求解可行对应B的基本解：存在检验数>0不可行单纯形法对偶单纯形法？××用大M法求解或用两阶段法求解作业：