运筹学经典课件第7次(1).ppt

《运筹学经典课件第7次(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶单纯形法是求解对偶规划的一种方法×对偶单纯形法：利用对偶理论得到的一个求解线性规划问题的方法2.3对偶单纯形法在灵敏度分析中，有时用对偶单纯形法处理较简单。单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初始基本可行解用单纯形法求解关于可行基B的典则形式检验数原始单纯形法的基本思路：XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b初始单纯形表：原始单纯形法的迭代过程：对偶单纯形法的基本思路：XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b

2、作对偶单纯形表：基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

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

4、X3X2X1-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对偶单纯形法步骤：1、找出一个初始对偶可行解。把原问题写成该基的典则形式时，目标函数的系数均≤02、判断：（1）若B-1b≥0，则得到最优解结束（2）若B-1b≥0，则问题无可行解。3、换基迭代：（1）确定出基变量：（2）确定入基变量即找出一个基B，否则转下一步不是典则形式X1X2X3X4X5检210

5、00ZX1111005X4021105X50-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的典则形式为什么叫对偶单纯形法？设B为基对偶单纯形法的基本思路：关于基B的典则形式:XBXN常数项检验行0CN-CBB-1NZ-CBB-1bXBEB-1NB-1b

6、得对偶单纯形表：对偶单纯形表的另一形式：X常数项检验行XBX解检验行Z-CBB-1bXBB-1b设B为一个基对偶单纯形法的迭代过程：如何用？求解线性规划问题的方法与步骤：1、把原问题化为标准型2、找初始基，转第3步，转第4步3、把问题写成关于基B的典则形式，用单纯形法，对偶单纯形法，转第4步4、增加人工变量，用大M法或两阶段法求解对应B1的基本解：可用对偶单纯形法求解检验数全部≤0不可行对应B2的基本解用单纯形法求解可行对应B的基本解：存在检验数>0不可行单纯形法×对偶单纯形法？×大M法：两阶段法单纯形法单纯形

7、法练习：