对偶理论敏感分析.ppt

1 线性规划 Linear Programming（LP） 第二章 线性规划的对偶理论与灵敏度分析 2 线性规划 Linear Programming（LP） 线性规划对偶理论 3 线性规划 Linear Programming（LP） 线性规划的对偶理论 对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？ 4 线性规划 Linear Programming（LP） 引例——俩家具制造商间的对话： 唉!我想租您的木工和油漆工一 用。咋样？价格嘛……好说， 肯定不会让您兄弟吃亏讪。 王老板做家具赚了 大钱，可惜我老李有 高科技产品，却苦于没有 足够的木工和油漆工 咋办？只有租咯。 Hi：王老板，听说 近来家具生意好惨了， 也帮帮兄弟我哦! 家具生意还真赚钱，但 是现在的生意这么好， 不如干脆把我的木工和油漆 工租给他，又能 收租金又可做生意。 价格嘛……好商量， 好商量。只是…... 王 老 板 李 老 板 5 线性规划 Linear Programming（LP） 王老板的家具生产模型： x1 、 x2是桌、椅生产量。 Z是家具销售总收入（总利润）。 max z = 50x1 + 30x2 s.t. 4x1+3x2 ≤ 120（木工） 2x1+ x2 ≤ 50 （油漆工） x1，x2 ≥ 0 原始线性规划问题，记为（P） 王老板的资源出租模型： y1、 y2单位木、漆工出租价格。 W是资源出租租金总收入。 min w =120y1 + 50y2 s.t. 4y1+2y2 ≥ 50 3y1+ y2 ≥ 30 y1，y2 ≥ 0 对偶线性规划问题，记为（D） 6 线性规划 Linear Programming（LP） 王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。 7 线性规划 Linear Programming（LP） 例1 第一章例1煤电油，其线性规划问题为 ——将其称为原始问题，记为P （P） max z = 7X1 + 12X2 s.t. 9X1+ 4X2 ≤ 360 4X1 + 5X2 ≤ 200 3X1 + 10X2 ≤ 300 X1 ， X2 ≥ 0 8 线性规划 Linear Programming（LP） 下面我们从另一角度提出一个新的问题。这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。 （D） min w = 360y1 + 200y2 + 300y3 s.t. 9y1+4y2 + 3y3 ≥ 7 4y1 + 5y2 + 10y3 ≥ 12 y1， y2， y3 ≥ 0 这个问题我们将其称为原始问题的对偶问题，记为D 9 线性规划 Linear Programming（LP） （P） max z = CX s.t. AX ≤ b X≥ 0 （D） min w = Yb s.t. YA ≥ C Y ≥ 0 特点： （1）P为max型，D为min型 （2）P的变量个数=D的约束个数 （3）P的约束个数=D的变量个数 （4）P的目标函数系数=D的资源约束向量 （5）P的资源约束向量=D的目标函数系数 （6）P技术系数矩阵=D技术系数矩阵转置 这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系。 10 线性规划 Linear Programming（LP） 对称形式下对偶问题的一般形式： 原问题 对偶问题 A b C 目标函数 约束条件 决策变量 技术系数矩阵 约束条件的右端项向量 目标函数中的价格系数向量 max Z = CX AX ≤ b X ≥ 0 其技术系数矩阵的转置 目标函数中的价格系数向量 约束条件的右端项向量