[管理学]第二章 对偶问题和灵敏度分析1+1.ppt

第二章 对偶问题和灵敏度分析1 1 对偶问题 2 对偶问题的基本性质 3 影子价格 4 对偶单纯形法 1 对偶问题 练习1写出下列线性规划问题的对偶问题 Max Z=60x1+30x2+20x3 s.t. 8x1+6x2+x3=48; 4x1+2x2+1.5x3=20; 2x1+1.5x2+0.5x3=8; x1,x2,x3=0. 练习1答案 Min w=48y1+20y2+8y3; s.t. 8y1+4y2+2y3=60; 6y1+2y2+1.5y3=30; y1+1.5y2+0.5y3=20; y1,y2,y3=0. 练习题2 Max z=2x1+x2 s.t. x1+x2=2; 2x1-x2=3; x1-x2=1; x1=0; x2 urs (unrestircted in sign) 练习题3 Min w=2y1+4y2+6y3 s.t. y1+2y2+y3=2; y1 -y3=1; y2+y3=1; 2y1+y2 =3; y1 urs, y2, y3=0. 用SOB方法来决定对偶问题约束形式（Sensible-Odd-Bizarre) 例1 例1答案 用SOB方法重做练习题2和3 练习题2 Max z=2x1+x2 s.t. x1+x2=2; 2x1-x2=3; x1-x2=1; x1=0; x2 urs 课后练习P68 2.1，2.2 2 对偶问题的基本性质 （5）互补基解性（complementary basic solution property）： 互补松弛性: 对于线性规划的最优解，若某一约束条件的对偶变量值大于零，则该约束条件取严格等式；反之，若约束条件取严格不等式，则其对应的对偶变量一定为零。 P48 例题2－4 练习题4 已知线性规划问题 Min w=2x1+3x2+5x3+2x4+3x5 s.t. x1+x2+2x3+x4+3x5=4; 2x1-x2+3x3+x4+x5=3; xj=0. 已知其对偶问题的最优解为y1=4/5,y2=3/5;z=5。试用对偶理论找出原问题的最优解。 练习题4的答案 X＝（1，0，0，0，1）T，w=5. 例3 考虑典型范例的P及D： 问题P与D的互补基解 由上表可观察两互补基解间的关系： 两互补基解的目标函数值相同（互补基解性质） 最优解发生在两互补基解均为可行解时（互补松驰性质） 除最优解外，一个可行的基解对应一個不可行的互补基解 除最优解外，一个次佳的基解对应一個超佳的互补基解 （7） 对应性（P49，性质2.6） 例4 从单纯形表的最优表中写出对偶问题的最优解 Max z = 2x1 + 3x2 x1+2x2+x3 = 8 4x1 + x4 =16 4x2 + x5 =12 x1~5 ? 0 例4 从单纯形表的最优表中写出对偶问题的最优解 Max z = 2x1 + 3x2 x1+2x2+x3 = 8 4x1 + x4 =16 4x2 + x5 =12 x1~5 ? 0 检验一下; 写出对偶问题并求解 检验一下 Min w =8y1+16y2+12y3 y1+4y2 - y4 = 2 2y1+ 4y3 - y5 = 3 y1~5 ? 0 规范形式： P49性质2.6： LP的检验数的相反数对应于DP的一组基本解； DP的检验数对应于LP的一组基本解（不用加负号） A Max Problem Optimal value of dual variable yi if Constraint i is a = constraint = －coefficient of si （松驰变量）in optimal row 0 (检验数所在行） Optimal value of dual variable yi if Constraint i is a = constraint = coefficient of ei （剩余变量）in optimal row 0 (检验数所在行） Optimal value of dual v