第03章 对偶单纯形法与灵敏度分析 运筹学.ppt

第3章线性规划问题的对偶与灵敏度分析 本章内容重点 线性规划的对偶问题的概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析 3.1.1 对偶问题的提出： 若第二章例2.1问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？  设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收取费用。 3.1 线性规划对偶问题 例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。 Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 3x2 ≤ 75 x1 , x2 ≥ 0 s.t. 3y1+2y2 ≥1500 （不少于甲产品的利润） 2y1+y2+3y3 ≥2500（不少于乙产品的利润） y1, y2 , y3 ≥ 0 3.1.2 对偶规划的形式 有对称形式和非对称形式。 对称形式的对偶规划之间具有下面的对应关系： (1) 若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即 “max，≤” 和 “min，≥” 相对应。 (2) 从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3) 从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4) 两个规划模型中的变量皆非负。 对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax ≤ b s.t. AT y ≥ c x ≥ 0 y ≥ 0 “Max ≤ ” “Min ≥” 原问题与对偶问题的对应关系 非对称形式的对偶规划:对非对称形式，可以按照下面的对应关系直接给出其对偶规划 (1) 将模型统一为“max，≤”或“min，≥” 的形式，对于其中的等式约束按下面(2)、(3)中的方法处理； (2) 若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； (3) 若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 下面对关系(2)作一说明。对于关系(3)可以给出类似的解释： 设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1 那么，它与下面两个不等式等价 原规划模型可以写成 转化为对称形式，直接写出对偶规划 这里，把y1看作是 y1 =y1’ - y1’’，于是y1没有非负限制。 例 写出下面线性规划的对偶规划模型 解 先将约束条件变形为“≤”形式 根据非对称形式的对应关系，直接写出对偶规划 3.1.3 线性规划对偶问题 推论2 若规划（P）有可行解，则（P）有最优解的充分必要条件是规划（D）有可行解。 推论3 若规划（D）有可行解，则（D）有最优解的充分必要条件是规划（P）有可行解。 定理 3.2 若原规划（P）有最优解，则对偶规划（D）也有最优解，反之亦然。并且两者的目标函数值相等 例 求解下面线性规划问题，并根据最优单纯形表中的检验数，给出其对偶问题的最优解。 解得最优单纯形表 最优解为(0, 25, 25)T，最优值为250。表中松弛变量的检验数分别为-0.5，-2，可以验证(0.5, 2)T为对偶规划的最优解。 可以用下面方法验证对偶最优性。原规划的对偶规划为 从本例的结论可以看到，对偶规划的最优解可以在原规划的最优解的检验数中得到，原规划最优解的检验数?的后m个分量（松弛变量对应的检验数）的负值，为对偶