运筹学大学课件44对偶单纯形法文档.pptx

1、第四节第四节 对偶单纯形法对偶单纯形法n 对偶单纯形法的基本思路对偶单纯形法的基本思路n 对偶单纯形法的计算步骤对偶单纯形法的计算步骤对对偶偶偶偶单纯单纯形法的基本思路形法的基本思路形法的基本思路形法的基本思路单纯形法的基本思路：形法的基本思路：原原问题基可行解基可行解 最最优解判断解判断对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思路基本思路基本思路基本思路对偶偶单纯形法的形法的计算步算步骤n线性规划问题 不妨设 为对偶问题的初始可行基，则 。若 ，即表中原问题和对偶问题均为最优解，否则换基。换基方法：基方法：确定换

2、出基变量 对应变量 为换出基的变量确定换入基变量 为主元素，为换入基变量初始可行基例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：对偶问题的初始可行基例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：使对偶问题基变量可行,换入 换出换出换出例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：最优解最优解例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶

3、单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：n n对偶偶单纯形法的形法的优点：点：n不需要人工变量；不需要人工变量；n当变量多于约束时，用对偶单纯形法可减少当变量多于约束时，用对偶单纯形法可减少迭代次数；迭代次数；n在灵敏度分析中，有时需要用对偶单纯形法在灵敏度分析中，有时需要用对偶单纯形法处理简化。处理简化。n n对偶偶单纯形法缺点：形法缺点：n在初始单纯形表中对偶问题是基可行解，这在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。练习n用用对偶偶单纯形法求解形法求解线性性规划划问题：返回返回返回返回 对偶单纯形法对偶单纯形法