运筹学之对偶单纯形法

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

2、目标函数系数都 ，不等,不是典式，可用两阶段法求解，麻烦！,否则不能用。,二.对偶单纯形法的迭代步骤：,例2-8,1.建立初始单纯形表,-1,-1,-1,1,0,-5,-1,1,4,0,1,-3,4,1,3,0,0,0,有负分量,注：检验数行 ，因此可以用对偶单纯形法求解，,4 1 3 0 0,0,0,二.对偶单纯形法的迭代步骤：,例2-8,-1,-1,-1,1,0,-5,-1,1,4,0,1,-3,4,1,3,0,0,0,有负分量,2.最优性检验：,若当前常数列 ，则得到最优表。否则转下一步。,二.对偶单纯形法的迭代步骤：,例2-8,-1,-1,-1,1,0,-5,-1,1,4,0,1,-3

3、,4,1,3,0,0,0,有负分量,3.确定出基变量：,将常数列中最负分量所在的行相应的基变量出基。,为出基变量,二.对偶单纯形法的迭代步骤：,例2-8,-1,-1,-1,1,0,-5,-1,1,4,0,1,-3,4,1,3,0,0,0,所有元素都 ，则原问题无可行解。停止计算。,4.确定进基变量：,为进基变量。,在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。,若出基变量所在的行中，,-1,-1,-1,二.对偶单纯形法的迭代步骤：,例2-8,1,0,-5,-1,1,4,0,1,-3,4,1,3,0,0,0,5

4、.换基运算：,1,1,-1,5,1,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,-1,1,4,0,1,-3,4,1,3,0,0,0,5.换基运算：,-2,0,3,1,-8,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,-2,0,3,1,1,-8,4,1,3,0,0,0,5.换基运算：,3,0,2,1,-5,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,-2,0,3,1,1,-8,3,0,2,1,0,-5,换基运算完成。得到新的单纯形表。,2.最优性检验：,若当前常数列 ，则得到最优表。否则转下一步。,1,1,1,二.对偶单纯形法的迭

5、代步骤：,例2-8,-1,0,5,-2,0,3,1,1,-8,3,0,2,1,0,-5,3.确定出基变量：,将常数列中最负分量所在的行相应的出变量离基。,为出基变量,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,-2,0,3,1,1,-8,3,0,2,1,0,-5,4.确定进基变量：,在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。,为进基变量。,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,-2,0,3,1,1,-8,3,0,2,1,0,-5,5.换基运算：,1,-3/

6、2,-1/2,-1/2,4,1,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,0,-3/2,-1/2,-1/2,4,3,0,2,1,0,-5,5.换基运算：,0,13/2,5/2,3/2,-17,1,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,0,-3/2,-1/2,-1/2,4,0,0,13/ 2,5/2,3/2,-17,5.换基运算：,0,5/2,-1/2,1/2,1,换基运算完成。得到新的单纯形表。,1,1,1,1,二.对偶单纯形法的迭代步骤：,例2-8,-1,0,5,0,-3/2,-1/2,-1/2,4,0,0,13/ 2,5/2,3/2,-1

7、7,0,5/2,-1/2,1/2,1,2.最优性检验：,若当前常数列 ，则得到最优表。,最优表,第二章 线性规划的对偶理论,2.1 对偶线性规划模型,2.2 对偶问题的性质,2.3 对偶单纯形法,2.4 灵敏度分析与参数分析,作业：P69 6(1),(3),标准形,作业1,用对偶单纯形法求解：,与2.6(1)类似,-1,-2,-3,1,0,-5,-2,-2,-1,0,1,-6,0,0,3,4,5,0,0,0,有负分量,注：检验数行 ，因此可以用对偶单纯形法求解。,-1,-2,-3,1,0,-5,-2,-2,-1,0,1,-6,3,4,5,0,0,0,0,-1,-3,1,0,-2,1,1,-1,

8、0,1,3,0,1,-5,0,0,-9,0,1,-1,2,1,0,-1,1,0,0,1,-11,-1,1,1,-2,最优表,标准形,作业2,用对偶单纯形法求解：,2.6(2),-1,-1,1,0,-4,2,1,0,1,2,0,0,3,4,0,0,0,有负分量,注：检验数行 ，因此可以用对偶单纯形法求解。,-1,-1,1,0,-4,2,1,0,1,2,3,4,0,0,0,1,1,-1,0,最优表,4,0,-1,2,1,-6,0,1,3,0,-12,1,0,1,1,-2,0,1,-2,-1,6,0,0,5,1,-18,1,0,1,1,-2,0,1,-2,-1,6,0,0,5,1,-18,确定进基变量：,在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。,在出基变量所在的行中，若非基变量列中没有负系数