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

《运筹学之对偶单纯形法.pptx》由会员分享，可在线阅读，更多相关《运筹学之对偶单纯形法.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一一.对偶单纯形法与单纯形法的区别：对偶单纯形法与单纯形法的区别：相同之处：相同之处：对偶单纯形法与单纯形法都是对单纯形表对偶单纯形法与单纯形法都是对单纯形表进行迭代计算。进行迭代计算。当当常数列常数列 ，而，而检验数行检验数行都都 时，单时，单纯形表是纯形表是最优表最优表。检验数检验数常数常数最最优优表表第1页/共32页一一.对偶单纯形法与单纯形法的区别：对偶单纯形法与单纯形法的区别：检验数检验数常数常数最最优优表表不同之处：不同之处：单纯形法单纯形法：在迭代过程中，始终保持：在迭代过程中，始终保持常数列常数列 ，而，而检验数行检验数行由有负检验数逐步变为全部由有负检验数逐步变为全部对偶单纯

2、形法对偶单纯形法：在迭代过程中，始终保持：在迭代过程中，始终保持检验数行检验数行 ，而而常数列常数列由有负分量逐步变为全部由有负分量逐步变为全部第2页/共32页二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：求解求解例例2-82-8标准形标准形式约束都式约束都 的问题。的问题。注：注：对偶单纯形法适用于目标函数系数都对偶单纯形法适用于目标函数系数都 ，不等，不等不是典不是典式，可式，可用两阶用两阶段法求段法求解，麻解，麻烦！烦！第3页/共32页否则不能用。否则不能用。二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-81.1.建立初始单纯形表建立初始单纯形表单单纯纯形形

3、表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量注：注：检验数行检验数行 ，因此可以用因此可以用对偶单纯形法对偶单纯形法求解，求解，4 1 3 0 0 00第4页/共32页二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量2.2.最优性检验：最优性检验：若当前若当前常数列常数列 ，则得则得到最优表。否则转下一步。到最优表。否则转下一步。第5页/共32页二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单

4、纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000有负分量有负分量3.3.确定出基变量：确定出基变量：将常数列中最负分量所在的将常数列中最负分量所在的行相应的基变量出基。行相应的基变量出基。为出基变量为出基变量第6页/共32页二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1-1-110-5-11401-341 3000所有元素都所有元素都 ，则原问题无可行解。停止计算。，则原问题无可行解。停止计算。4.4.确定进基变量：确定进基变量：为进基变量。为进基变量。在出基变量所在的行中，找出非基变在出

5、基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进得正比值中最小者相应的非基变量进基。基。若出基变量所在的行中，若出基变量所在的行中，第7页/共32页-1-1-1二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列10-5-11401-341 30005.5.换基运算：换基运算：11-151第8页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验

6、数检验数常数列常数列-105-11401-341 30005.5.换基运算：换基运算：-2031-8第9页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-841 30005.5.换基运算：换基运算：3021-5第10页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-5换基运算完成。得到新的单纯形表。换基运算完成。得到新的单纯形表。2.2.最优性检验：最优性检验：若当前若当前常数列常

7、数列 ，则得到最则得到最优表。否则转下一步。优表。否则转下一步。第11页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-53.3.确定出基变量：确定出基变量：将常数列中最负分量所在的将常数列中最负分量所在的行相应的出变量离基。行相应的出变量离基。为出基变量为出基变量第12页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-54.4.确定进基变量：确定进基变量：在出基变

8、量所在的行中，找出非基变在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进得正比值中最小者相应的非基变量进基。基。为进基变量。为进基变量。第13页/共32页111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-105-20311-830 210-55.5.换基运算：换基运算：1-3/2-1/2-1/24第14页/共32页1111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-8

9、2-8单单纯纯形形表表检验数检验数常数列常数列-1050-3/2-1/2-1/2430 210-55.5.换基运算：换基运算：013/25/23/2-17第15页/共32页1111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数列常数列-1050-3/2-1/2-1/240013/25/23/2-175.5.换基运算：换基运算：05/2-1/21/21换基运算完成。得到新的单纯形表。换基运算完成。得到新的单纯形表。第16页/共32页1111二二.对偶单纯形法的迭代步骤：对偶单纯形法的迭代步骤：例例2-82-8单单纯纯形形表表检验数检验数常数

10、列常数列-1050-3/2-1/2-1/240013/25/23/2-1705/2-1/21/212.2.最优性检验：最优性检验：若当前若当前常数列常数列 ，则得到最则得到最优表。优表。最最优优表表第17页/共32页第二章第二章 线性规划的对偶理论线性规划的对偶理论2.1 对偶线性规划对偶线性规划模型模型2.2 对偶问题的性质对偶问题的性质2.3 对偶单纯形法对偶单纯形法2.4 灵敏度分析与参数分析灵敏度分析与参数分析作业：作业：P69 6(1),(3)第18页/共32页标准形标准形作业作业1用对偶单纯形法求解：用对偶单纯形法求解：与与2.6(1)类似类似第19页/共32页单单纯纯形形表表一一

11、检验数检验数常数列常数列-1-2-310-5-2-2-101-600345000有负分量有负分量注：注：检验数行检验数行 ，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。求解。第20页/共32页单单纯纯形形表表一一检验数检验数常数列常数列-1-2-310-5-2-2-101-6345000单单纯纯形形表表二二检验数检验数常数列常数列0-1-310-211-101301-500-9单单纯纯形形表表三三检验数检验数常数列常数列01-1210-11001-11-111-2最最优优表表第21页/共32页标准形标准形作业作业2用对偶单纯形法求解：用对偶单纯形法求解：2.6(2)第22页/共32页单单

12、纯纯形形表表一一检验数检验数常数列常数列-1-110-4210120034000有负分量有负分量注：注：检验数行检验数行 ，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。求解。第23页/共32页单单纯纯形形表表一一检验数检验数常数列常数列-1-110-42101234000单单纯纯形形表表二二检验数检验数常数列常数列11-10单单纯纯形形表表三三检验数检验数常数列常数列最最优优表表40-121-60130-121011-201-2-160051-18第24页/共32页单单纯纯形形表表一一检验数检验数常数列常数列1011-201-2-160051-18确定进基变量：确定进基变量：在出基变量所

13、在的行中，找出非基变量列中的负系在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。值，所得正比值中最小者相应的非基变量进基。在出基变量所在的行中，若非基变量列中没有负系在出基变量所在的行中，若非基变量列中没有负系数，则原问题无解（因为这是矛盾方程）。数，则原问题无解（因为这是矛盾方程）。第25页/共32页标准形标准形作业作业3用对偶单纯形法求解：用对偶单纯形法求解：2.6(3)第26页/共32页单单纯纯形形表表一一检验数检验数常数列常数列2310024-1-2010-

14、1000240000-1-3-150010有负分量有负分量注：注：检验数行检验数行 ，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。求解。第27页/共32页检验数检验数常数列常数列表一表一2310024-1-2010-102400001/31500-1/3-2/3检验数检验数常数列常数列表二表二101019-1/300102/30004/3-20-1-3-15001最最优优表表第28页/共32页标准形标准形用对偶单纯形法求解：用对偶单纯形法求解：2.6(4)作业作业4第29页/共32页单单纯纯形形表表一一检验数检验数常数列常数列-2110-1-201002356000-1-3-13-2-3有负分量有负分量注：注：检验数行检验数行 ，因此可以用因此可以用对偶单纯形法对偶单纯形法求解。求解。第30页/共32页单单纯纯形形表表一一检验数检验数常数列常数列-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第31页/共32页