管理运筹学-03 线性规划的对偶理论.ppt

1.对偶问题的提出 2.对偶关系 3.对偶性质 4.对偶单纯形法 5.灵敏度分析 1. 对偶问题的提出 1.从数学角度提出对偶问题 (1) 正规化的线性规划数学模型 (2) 检验数与最优条件 (3) 对偶模型 2.从经济学角度提出对偶问题 (1) 例1 (2) 例1的数学模型 (3) 例1的对偶模型 正规化的线性规划数学模型 Max z = C X A X + E Xs = b X, Xs ? 0 检验数与最优条件 对偶模型 例1 例1的数学模型 Max z = 8x1 + 7x2 x1+ 2x2 ? 100 4x1+ 3x2 ? 200 5x1+ 6x2 ? 300 x1 ， x2 ? 0 例1的对偶模型 Min z = 100x1 + 200x2 + 300x3 x1+ 4x2 + 5x3 ? 8 2x1+ 3x2 + 6x3 ? 7 x1 ， x2 ? 0 2. 对偶关系 3. 对偶性质 1.对称性:对偶问题的对偶是原问题； 2.弱对偶性:CX ? Yb, X和Y是可行解； 3.无界性:原问题无界, 对偶问题无可行解； 4.最优性: CX = Yb, X和Y是最优解； 5.对偶性:原问题与对偶问题同时具有最优解且最优值相等； 6.互补松弛性； 7.对应性。 互补松弛性 对于线性规划的最优解，若某一约束条件的对偶变量值大于零，则该约束条件取严格等式；反之，若约束条件取严格不等式，则其对应的对偶变量一定为零。 对应性 1.原问题： Max z = CX AX +EXs = b，X，Xs ? 0 2.对偶问题： Min z = Yb YA - EYs = C，Y，Ys ? 0 3.对应关系 4.例2 4. 对偶单纯形法 1.对偶单纯形法的内涵 2.对偶单纯形法的优点和应用的 前提条件 3.对偶单纯形法的计算步骤 4.例3（例3-5） 对偶单纯形法的内涵 对偶单纯形法：在对偶可行基的基础上进行的单纯形法即为对偶单纯形法。 单纯形法是在原问题可行的基础上，通过迭代使对偶问题达到可行，从而得到最优解。根据对偶问题的对称性，可这样考虑，若原问题不可行而对偶问题可行，那么在保持对偶问题可行的基础上，逐步迭代使原问题达到可行，也可得到最优解。 对偶单纯形法的优点和 应用的前提条件 对偶单纯形法的优点是原问题的初始解不要求是可行解，可以从非可行解开始迭代，从而省去了引入人工变量的麻烦。 当然对偶单纯形法的应用也是有前提条件的，这一前提条件就是对偶问题的解是基可行解。 对偶单纯形法的计算步骤 1.根据对偶基可行解列初始单纯形表； 2.最优性检验：若原问题也为基可行解，则已得到最优解，过程结束；否则，进入第3步。 3.选择出基变量：Min{bi | bi ? 0} 4.选择入基变量：Min{?j /aij | aij? 0} 若所有的aij均大于零，则无可行解。 5.迭代运算，重复1~4步。 例2 Max z = 2x1 + x2 3x1+4x2+x3 =18 6x1+2x2 + x4 =24 x1+ x2 + x5 = 6 x1~4 ? 0 Min w =18y1+24y2+6y3 3y1+6y2+y3- y4 = 2 4y1+2y2+y3 - y5 = 1 y1~5 ? 0 例2的求解结果 例3（第35页例3-5） Min w = x1 + 4x2 + 3x4 x1+2x2 - x3+x4 ? 3 -2x1- x2 + 4x3+x4 ? 2 x1~4 ? 0 转换成标准形式： Min w =x1+4x2+3x4 x1+2x2- x3+x4 - x5 = 3 -2x1- x2+4x3+x4 - x6 = 2 x1~6 ? 0 例3的求解过程 例3的求解过程 例3的求解过程 5. 线性规划的灵敏度分析 1.灵敏度分析的内涵 2.灵敏度分析的处理方法 3.资源系数变化的灵敏度分析 4.价值系数变化的灵敏度分析 5.技术系数变化的灵敏度分析 6.增加新变量的灵敏度分析 7.增加新约束的灵敏度分析 灵敏度分析的内涵 灵敏度分析是对系统因环境变化显示出来的敏感程度的分析。在线性规划中讨论灵敏度分析，目的是描述一种能确定模型结构中元素变化对问题最优解影响的分析方法。 灵敏度分析主要回答两方面问题：因素有一定量变化时，最优解有什么变化；因素在什么范围内变化时，最优解保持不变。 灵敏度分析的处理方法 资源系数变化的灵敏度分析 1.基本原理 (B|E) ?