[工学]第4章线性规划的对偶原理.pptVIP

2003-6 线性规划的对偶原理 4 线性规划的对偶原理 线性规划的对偶问题 线性规划的对偶理论 对偶问题与单纯形法 对偶问题的经济解释 对偶单纯形法 对偶原理简介 对于每一个线性规划问题，都存在另一个线性规划问题与其密切相关，两者一个叫原始问题，另一个叫对偶问题。对偶原理深刻揭示了原始问题与对偶问题的形式和内在关系，为线性规划问题的求解和应用开辟了新的领域。 对偶原理自1947年提出以来有了很大发展，现已成为整个线性规划理论的重要组成部分。 4.1 线性规划的对偶问题 4.1.1 从经济意义上提出对偶问题 在例 1.1 中讨论了企业生产计划问题的模型及其解法，下面从另一角度来讨论这个问题。 假设该企业拟定不生产产品 P1 和 P2 ，而是将全部原料出售。这时企业的决策者就要考虑给各种原料如何定价的问题。 设 y1 , y2 , y3 分别为出售单位原料 M1 , M2 , M3 的盈利，便可得到另一个与生产计划问题相关的线性规划问题。为了区别，将这两者分别称为产品定产问题和原料定价问题。 产品定产问题和原料定价问题 max z=2x1+3x2 s.t. x1+2x2 ≤8 4x1 ≤16 4x2 ≤12 x1 , x2 ≥0 ? =8y1+16y2+12y3 y1+4y2 ≥2 2y1 +4y3 ≥3 y1 , y2 , y3 ≥0 定产问题的矩阵形式 定产问题 max z = CX s. t. AX ≤ b X ≥0 max z=2x1+3x2 s.t. x1+2x2 ≤8 4x1 ≤16 4x2 ≤12 x1 , x2 ≥0 定价问题的矩阵形式 定价问题 min ? =Yb s. t. YA≥C Y ≥0 min ? =8y1+16y2+12y3 s.t. y1+4y2 ≥2 2y1 +4y3≥3 y1 , y2 , y3 ≥0 相同的数据与不同的问题 max z = CX s. t. AX ≤ b X ≥0 max z=2x1+3x2 s.t. x1+2x2 ≤8 4x1 ≤16 4x2 ≤12 x1 , x2 ≥0 min ? =Yb s. t. YA≥C Y ≥0 min ? =8y1+16y2+12y3 s.t. y1+4y2 ≥2 2y1 +4y3≥3 y1 , y2 , y3 ≥0 4.1.2 从数学形式上定义对偶问题 假若把任一给定的线性规划问题叫做原始 (Primal) 问题，用它的数据按一定规则构成的另一个线性规划问题叫做对偶 (Dual) 问题。下面主要讨论如何由给定的原始问题得到对偶问题，并将指出这样一种操作是互逆的。 表4.3 问题的数据(表4.2) 原始问题的常规形式 max z=c1 x1 + c2 x2+…+cj xj+…+cn xn s. t. a11x1+a12x2+…+a1 jxj+…+a1nxn ≤ b1 a21x1+a22x2+…+a2 jxj+…+a2nxn ≤ b2 … … am1x1+am2x2+…+amjxj+…+amnxn≤ bm x1 , x2 , … , xj ,… , xn≥0 对偶问题的矩阵形式 min ? = ( y1 , y2 , … , ym ) ( b1 ,