运筹学之对偶单纯形法.ppt

第二章第二章 线性规划的对偶理论线性规划的对偶理论2.1 对偶线性规划对偶线性规划模型模型2.2 对偶问题的性质对偶问题的性质2.3 对偶单纯形法对偶单纯形法2.4 灵敏度分析与参数分析灵敏度分析与参数分析一一. .对偶单纯形法与单纯形法的区别：对偶单纯形法与单纯形法的区别：相同之处：相同之处：对偶单纯形法与单纯形法都是对单纯形表对偶单纯形法与单纯形法都是对单纯形表进行迭代计算进行迭代计算当当常数列常数列 ，而，而检验数行检验数行都都 时，单时，单纯形表是纯形表是最优表最优表检验数检验数常数常数最最优优表表一一. .对偶单纯形法与单纯形法的区别：对偶单纯形法与单纯形法的区别：检验数检验数常数常数最最优优表表不同之处：不同之处：单纯形法单纯形法：在迭代过程中，始终保持：在迭代过程中，始终保持常数列常数列 ，而，而检验数行检验数行由有负检验数逐步变为全部由有负检验数逐步变为全部对偶单纯形法对偶单纯形法：在迭代过程中，始终保持：在迭代过程中，始终保持检验数行检验数行 ，，而而常数列常数列由有负分量逐步变为全部由有负分量逐步变为全部二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 求解求解例例2-82-8标准形标准形式约束都式约束都 的问题。

的问题注：注：对偶单纯形法适用于目标函数系数都对偶单纯形法适用于目标函数系数都 ，不等，不等不是典不是典式，可式，可用两阶用两阶段法求段法求解，麻解，麻烦！烦！否则不能用否则不能用二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-81.1.建立初始单纯形表建立初始单纯形表单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量注：注：检验数行检验数行 ，，因此可以用因此可以用对偶单纯形法对偶单纯形法求解，求解，4 1 3 0 0 00二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量2.2.最优性检验：最优性检验：若当前若当前常数列常数列 ，，则得则得到最优表否则转下一步到最优表否则转下一步二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量3.3.确定出基变量：确定出基变量：将常数列中最负分量所在的将常数列中最负分量所在的行相应的基变量出基。

行相应的基变量出基为出基变量为出基变量二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000所有元素都所有元素都 ，则原问题无可行解停止计算则原问题无可行解停止计算4.4.确定进基变量：确定进基变量：为进基变量为进基变量在出基变量所在的行中，找出非基变在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进得正比值中最小者相应的非基变量进基若出基变量所在的行中，若出基变量所在的行中，-1-1-1二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列10-5-11401-341 30005.5.换基运算：换基运算：11-151111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-11401-341 30005.5.换基运算：换基运算：-2031-8111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-841 30005.5.换基运算：换基运算：3021-5111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-5换基运算完成。

得到新的单纯形表换基运算完成得到新的单纯形表2.2.最优性检验：最优性检验：若当前若当前常数列常数列 ，，则得到最则得到最优表否则转下一步否则转下一步111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-53.3.确定出基变量：确定出基变量：将常数列中最负分量所在的将常数列中最负分量所在的行相应的出变量离基行相应的出变量离基为出基变量为出基变量111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-54.4.确定进基变量：确定进基变量：在出基变量所在的行中，找出非基变在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进得正比值中最小者相应的非基变量进基为进基变量为进基变量111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-55.5.换基运算：换基运算：1-3/2-1/2 -1/241111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1050-3/2-1/2-1/2430 210-55.5.换基运算：换基运算：013/25/23/2-171111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1050-3/2-1/2-1/240013/ 25/23/2-175.5.换基运算：换基运算：05/2-1/21/21换基运算完成。

得到新的单纯形表换基运算完成得到新的单纯形表1111二二. .对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤： 例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1050-3/2-1/2-1/240013/ 25/23/2-1705/2-1/21/212.2.最优性检验：最优性检验：若当前若当前常数列常数列 ，，则得到最则得到最优表最最优优表表第二章第二章 线性规划的对偶理论线性规划的对偶理论2.1 对偶线性规划对偶线性规划模型模型2.2 对偶问题的性质对偶问题的性质2.3 对偶单纯形法对偶单纯形法2.4 灵敏度分析与参数分析灵敏度分析与参数分析作业：作业：P69 6(1),(3) 标准形标准形作业作业1用对偶单纯形法求解：用对偶单纯形法求解：与与2.6(1)类似类似单单纯纯形形表表一一检验数检验数常数列常数列-1-2-310-5-2-2-101-600345000有负分量有负分量注：注：检验数行检验数行 ，，因此可以用因此可以用对偶单纯形法对偶单纯形法求解单单纯纯形形表表一一检验数检验数常数列常数列-1-2-310-5-2-2-101-6345000单单纯纯形形表表二二检验数检验数常数列常数列0-1-310-211-101301-500-9单单纯纯形形表表三三检验数检验数常数列常数列01-1210-11001-11-111-2最最优优表表标准形标准形作业作业2用对偶单纯形法求解：用对偶单纯形法求解：2.6(2)单单纯纯形形表表一一检验数检验数常数列常数列-1-110-4210120034000有负分量有负分量注：注：检验数行检验数行 ，，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。

求解单单纯纯形形表表一一检验数检验数常数列常数列-1-110-42101234000单单纯纯形形表表二二检验数检验数常数列常数列11-10单单纯纯形形表表三三检验数检验数常数列常数列最最优优表表40-121-60130-121011-201-2-160051-18单单纯纯形形表表一一检验数检验数常数列常数列1011-201-2-160051-18确定进基变量：确定进基变量： 在出基变量所在的行中，找出非基变量列中的负系在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基值，所得正比值中最小者相应的非基变量进基 在出基变量所在的行中，若非基变量列中没有负系在出基变量所在的行中，若非基变量列中没有负系数，则原问题无解（因为这是矛盾方程）数，则原问题无解（因为这是矛盾方程）标准形标准形作业作业3用对偶单纯形法求解：用对偶单纯形法求解：2.6(3)单单纯纯形形表表一一检验数检验数常数列常数列2310024-1-2010-1000240000-1-3-150010有负分量有负分量注：注：检验数行检验数行 ，，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。

求解检验数检验数常数列常数列表一表一2310024-1-2010-102400001/31500-1/3-2/3检验数检验数常数列常数列表二表二101019-1/300102/30004/3-20-1-3-15001最最优优表表标准形标准形用对偶单纯形法求解：用对偶单纯形法求解：2.6(4)作业作业4单单纯纯形形表表一一检验数检验数常数列常数列-2110-1-201002356000-1-3-13-2-3有负分量有负分量注：注：检验数行检验数行 ，，因此可以用因此可以用对偶单纯形法对偶单纯形法求解单单纯纯形形表表一一检验数检验数常数列常数列-2110-1-201002356000-1-3-13-2-3单单纯纯形形表表二二检验数检验数常数列常数列1-1/210-5/20-1/204490-311/2-3/2-1/23/2-5/2-5/2-1/2单单纯纯形形表表三三检验数检验数常数列常数列10-2/501-1/5-2/50005-19/51/51-11/58/51/5118/5。