《运筹学》课程教学课件（PPT讲稿）对偶理论（Duality Theory）

Chapter2对偶理论 (Duality Theory) 本章主要内容： ·线性规划的对偶模型 。对偶性质 ·对偶问题的经济解释一影子价格 ·对偶单纯形法 优化后分析-灵敏度分析

Chapter2 对偶理论 ( Duality Theory ) 线性规划的对偶模型 对偶性质 对偶问题的经济解释－影子价格 对偶单纯形法 优化后分析- 灵敏度分析 本章主要内容：

线性规划的对偶模型 Page 2 1.对偶问题的现实来源 设某工厂生产两种产品甲和乙，生产中需4种设备按A,B, C,D顺序加工，每件产品加工所需的机时数、每件产品的利润值 及每种设备的可利用机时数列于下表： 产品数据表 设备 产品利润 A B D 产品 (元/件) 甲 2 1 4 0 2 乙 2 2 0 4 3 设备可利用机时数（时） 12 8 16 12 问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能 获得最大利润？

线性规划的对偶模型 Page 2 设某工厂生产两种产品甲和乙，生产中需4种设备按A，B， C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值 及每种设备的可利用机时数列于下表 ： 产品数据表 设备 产品 A B C D 产品利润 （元／件） 甲 2 1 4 0 2 乙 2 2 0 4 3 设备可利用机时数（时） 12 8 16 12 问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能 获得最大利润？ 1. 对偶问题的现实来源

线性规划的对偶模型 Page 3 解：设甲、乙型产品各生产x1及X2件，则数学模型为： max =2x +3x, 2x,+2x2≤12 x1+2x2≤8 s.t 4x1≤16 4x2≤12 七1，x2≥0 反过来问：若厂长决定不生产甲和乙型产品，决定出租机器 用于接受外加工，只收加工费，那么4种机器的机时如何定 价才是最佳决策？

线性规划的对偶模型 Page 3 解：设甲、乙型产品各生产x1及x2件，则数学模型为：             +  +  = + , 0 4 12 4 16 2 8 2 2 12 . max 2 3 1 2 2 1 1 2 1 2 1 2 x x x x x x x x s t z x x 反过来问：若厂长决定不生产甲和乙型产品，决定出租机器 用于接受外加工，只收加工费，那么４种机器的机时如何定 价才是最佳决策？

线性规划的对偶模型 Page 4 在市场竞争的时代，厂长的最佳决策显然应符合两条： (1)不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型 产品所获利润。由此原则，便构成了新规划的不等式约束条件。 (2)竞争性原则。即在上述不吃亏原则下，尽量降低机时总收 费，以便争取更多用户。 设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线 性规划数学模型为： mino=12y1+8y2+16y3+12y4 2y1+y2+4y3+0y.≥2 s.t2y1+2y2+0y3+4y4≥3 y1,y2,y3,y4≥0

线性规划的对偶模型 Page 4 在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型 产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收 费，以便争取更多用户。 设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线 性规划数学模型为：       + + +  + + +   = + + + , , , 0 2 2 0 4 3 2 4 0 2 . min 12 8 16 12 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 y y y y y y y y y y y y s t y y y y

线性规划的对偶模型 Page 5 把同种问题的两种提法所获得的数学模型用表2表示，将会发 现一个有趣的现象。 原问题与对偶问题对比表 A1) B(y2) C0y3) D(y4) 甲(c) 2 1 4 0 2 乙(x2) 2 2 0 4 3 12 8 16 12 min max

线性规划的对偶模型 Page 5 把同种问题的两种提法所获得的数学模型用表2表示，将会发 现一个有趣的现象。 原问题与对偶问题对比表 A（y1） B（y2） C（y3） D（y4） 甲（x1） 2 1 4 0 2 乙（x2） 2 2 0 4 3 12 8 16 12 minω max z

线性规划的对偶模型 Page 6 2.原问题与对偶问题的对应关系 max =2x +3x, 2x,+2x2≤12 mino=12y1+8y2+16y3+12y x1+2x2≤8 2y1+y2+4y3+0y4≥2 s.t 4x,≤16 s.t2y1+2y2+0y3+4y4≥3 4x2≤12 y1,y2,y3,y4≥0 x1,x2≥0 原问题 对偶问题 (对偶问题) (原问题)

线性规划的对偶模型 Page 6 2. 原问题与对偶问题的对应关系             +  +  = + , 0 4 12 4 16 2 8 2 2 12 . max 2 3 1 2 2 1 1 2 1 2 1 2 x x x x x x x x s t z x x       + + +  + + +   = + + + , , , 0 2 2 0 4 3 2 4 0 2 . min 12 8 16 12 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 y y y y y y y y y y y y s t y y y y 原问题 （对偶问题） 对偶问题 （原问题）

线性规划的对偶模型 Page7 (1)对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负；目标函数求极小值时，所有约束条件为≥号，变量非 负 P: maxz =CX D: min W=YTb AX≤b AY≥CT X≥0 Y≥0 已知P,写出D

线性规划的对偶模型 Page 7 （1）对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负;目标函数求极小值时，所有约束条件为≥号，变量非 负. X 0 AX b maxZ CX      P： =      = Y 0 A Y C T T D W Y b T : min 已知P，写出D

线性规划的对偶模型 Page 8 例2.1写出线性规划问题的对偶问题 max Z-2x-3x,+4x 2x1+3x2-5x3≥2 3x1+x2+7x3≤3 -x1+4x2+6x3≥5 x1,x2,x3≥0 解：首先将原问题变形为对称形式 max Z=2x-3x,+4.x3 -2x-3x2+5x3≤-2 3x1+x2+7x3≤3 x1-4x2-6x3≤-5 x1,x2,x3≥0

线性规划的对偶模型 Page 8 例2.1 写出线性规划问题的对偶问题         − + +  + +  + −  = − + , , 0 4 6 5 3 7 3 2 3 5 2 max 2 3 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x x Z x x x 解：首先将原问题变形为对称形式         − −  − + +  − − +  − = − + , , 0 4 6 5 3 7 3 2 3 5 2 max 2 3 4 1 2 3 1 2 3 1 2 3 2 3 1 2 3 x x x x x x x x x x x x Z x x x

线性规划的对偶模型 Page 9 对偶问题：minW=-2y1+3y2-5y3 -2y1+3y2+y3≥2 -3y1+y2-4y3≥-3 5y1+7y2-6y3≥4 y1,y2,y3≥0

线性规划的对偶模型 Page 9   + −  − + −  − − + +  = − + − , , 0 5 7 6 4 3 4 3 2 3 2 min 2 3 5 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y y y y 对偶问题： W y y y

线性规划的对偶模型 Page 10 (2)非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题。也可直接按教材表2-2中的对应关系写出非对 称形式的对偶问题

线性规划的对偶模型 Page 10 (2) 非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题。也可直接按教材表2-2中的对应关系写出非对 称形式的对偶问题