第二章线性规划的对偶理论 本章主要内容： ·对偶问题的提出 原问题与对偶问题 ◆对偶问题的基本性质 ◆对偶的经济解释 —影子价格 对偶单纯形法 灵敏度分析 2014-12-15
2014-12-15 1 第二章 线性规划的对偶理论 对偶问题的提出 原问题与对偶问题 对偶问题的基本性质 对偶的经济解释——影子价格 对偶单纯形法 灵敏度分析 本章主要内容：
§1对偶问题的提出 第一章例2)常山机器厂生产1、Ⅱ两种产品。这两种 产品都要分别在A、B、C三种不同设备上加工。按工 艺资料规定，单件产品在不同设备上加工所需要的台 时和利润如下表所示，企业决策者应如何安排生产计 划，使企业总的利润最大？ 设备 A B 利润（元） 产品 I 2 4 0 2 Ⅱ 2 0 5 3 有效台时 12 16 15 2014-12-15 2
2014-12-15 2 §1 对偶问题的提出 [第一章例2] 常山机器厂生产I、Ⅱ两种产品。这两种 产品都要分别在A、B、C三种不同设备上加工。按工 艺资料规定，单件产品在不同设备上加工所需要的台 时和利润如下表所示，企业决策者应如何安排生产计 划，使企业总的利润最大？ 设 备 产 品 A B C 利润（元） I 2 4 0 2 Ⅱ 2 0 5 3 有 效 台 时 12 16 15
§1对偶问题的提出 解：设X、分别为、川两种产品的产量，则数学模型为： max Z=2x+3x2 2x1+2x2≤12 4x1 ≤16 (1) S.t. 5x2≤15 x1≥0，X2≥0 反过来问：现假定有另一四海机器厂，为扩大生产想租借常 山机器厂拥有的3种设备资源，问常山厂分别以每小时什么 样的价格才愿意出租自己的设备？ 2014-12-15 3
2014-12-15 3 §1 对偶问题的提出 解：设x 1、x 2分别为I、Ⅱ两种产品的产量，则数学模型为： max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0 s.t. 2x1 + 2x2 ≤ 12 4x1 ≤ 16 5x2 ≤ 15 反过来问：现假定有另一四海机器厂，为扩大生产想租借常 山机器厂拥有的3种设备资源，问常山厂分别以每小时什么 样的价格才愿意出租自己的设备？ （1）
§1对偶问题的提出 解：设A、B、C3种设备每小时出租的价格分别为y小、y2、 3,则新的线性规划数学模型为： min0=12y,+16y2+15y3 2y+42+0y3≥2 (2) s.t2y+0y2+5y3≥3 、y1,y2,y3≥0 任何一个线性规划问题都存在一个伴生的线性规划问题， 我们称之为“对偶”。 2014-12-15
2014-12-15 4 §1 对偶问题的提出 解：设A、B、C 3种设备每小时出租的价格分别为y1、y2、 y3，则新的线性规划数学模型为： , , 0 2 0 5 3 2 4 0 2 . . min 12 16 15 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y st y y y （2） 任何一个线性规划问题都存在一个伴生的线性规划问题， 我们称之为“对偶”
§2原问题与对偶问题 把同种问题的两种提法所获得的数学模型写在一块，将会 发现一个有趣的现象。 max Z=2x+3x2 min0=12y+16y2+15y3 2X1+2x2≤12 2y+4y2+0y≥2 4x1 ≤16 (1) (2) s.t. st2y+0y2+5y3≥3 5x2≤15 y,y2,为3≥0 X1≥0，X2≥0 原问题 对偶问题 (对偶问题) (原问题) 称(2)为（1)的对偶，也称（1)为(2) 的对偶。 2014-12-15 5
2014-12-15 5 §2 原问题与对偶问题 称（2）为（1）的对偶，也称（1）为（2）的对偶。 , , 0 2 0 5 3 2 4 0 2 . . min 12 16 15 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y st max Z = 2x1 + 3x2 y y y x1 ≥ 0 , x2 ≥ 0 s.t. 2x1 + 2x2 ≤ 12 4x1 ≤ 16 5x2 ≤ 15 （1） （2） 把同种问题的两种提法所获得的数学模型写在一块，将会 发现一个有趣的现象。 原问题 （对偶问题） 对偶问题 （原问题）
§2原问题与对偶问题 (1)对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负；目标函数求极小值时，所有约束条件为≥号，变量非 负. P: maxZ =CX D minw=b'Y AX≤b ATY≥CI X≥0 Y≥0 (2)非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题。 2014-12-15 6
2014-12-15 6 §2 原问题与对偶问题 （1）对称形式 特点：目标函数求极大值时，所有约束条件为≤号，变 量非负；目标函数求极小值时，所有约束条件为≥号，变量非 负. X 0 AX b maxZ CX P： Y 0 A Y C : min T T D W b Y T (2) 非对称型对偶问题 若给出的线性规划不是对称形式，可以先化成对称形式 再写对偶问题
§2原问题与对偶问题 [例1】写出线性规划问题的对偶问题 min0=12y+16y2+15y3 2y+42+03≥2 s.t2y+0y2+5y3≥3 y1,y2,y3≥0 解：首先将原问题变形为对称形式 对偶问题 maxo=-12y1-16y2-15y3 minz=-2x-3x2 -21-4y2 ≤-2 -2x1-2x2≥-12 s.t.-2y -4x1 ≥-16 -5y3≤-3 S.t. -5x2≥-15 y1,y2,y3≥0 2014-12-15 x1,x2≥0
2014-12-15 7 §2 原问题与对偶问题 , , 0 2 0 5 3 2 4 0 2 . . min 12 16 15 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y st y y y [例1] 写出线性规划问题的对偶问题 解：首先将原问题变形为对称形式 , , 0 2 5 3 2 4y 2 . . max 12 16 15 1 2 3 1 3 1 2 1 2 3 ' y y y y y y st y y y 对偶问题 , 0 5 15 4 16 2 2 12 . . min ' 2 3 1 2 2 1 1 2 1 2 x x x x x x st z x x
§2原问题与对偶问题 [例2]写出下述线性规划的对偶问题 minz=7x+4x2-3x3 -4x1+2x2-6x3≤24 -3x1-6x2-7x3≥15 s.t. 5x2+3x3=30 x≤0，x2无约束，x3≥0 解：(1)令×1'=-X1,X2=2'-X2”, 等式约束化为：5X2+3X3≥30和5X2+3X3≤30，有 minz=-7x+4x2'-4x2"-3x3 -4x,'-2x2'+2x2"+6x3≥-24 3x1'-6x2'+6x2”-7x3≥15 5x2'-5x2"+3x3≥30 -5x2'+5x2"-3x3≥-30 2014-12-15 x',x2',x2",x3≥0 8
2014-12-15 8 §2 原问题与对偶问题 0, , 0 5 3 30 3 6 7 15 4 2 6 24 . . min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x st z x x x 无约束 [例2] 写出下述线性规划的对偶问题 解：（1）令x1′= - x1，x2 = x2 ′- x2 ″ ， 等式约束化为: 5X2+3X3≥30 和 5X2 +3X3≤30，有 ', ', '', 0 5 ' 5 '' 3 30 5 '-5 '' 3 30 3 ' 6 ' 6 '' 7 15 4 ' 2 ' 2 '' 6 24 . . min 7 ' 4 ' 4 '' 3 1 2 2 3 2 2 3 2 2 3 1 2 2 3 1 2 2 3 1 2 2 3 x x x x x x x x x x x x x x x x x x st z x x x x
§2原问题与对偶问题 (2)令上式四个约束条件对应的对偶变量分别为y1,y2,Y3,y4,则其 对偶问题为： maxo=-24y+15y2+30y3-30y4 -4y+3y2≤-7 -2y-6y2+5y3-5y4≤4 s.t2y1+6y2-5y3+5y4≤-4 6y-7y2+3y3-3y4≤-3 y2:34≥0 (3)令y1'=-y1,y⅓'=y3-y4,中间两个约束条件合成等式约束，有 maxo-24y'+15y2+30y3 minz=7x+4x2-3x3 -4y'-3y2≥7 4x1+2x2-6x3≤24 2y’6y2+5y3'=4 s.t. 3x-6x2-7x3≥15 - 6y1'-7y2+3y3'≤-3 S.t. 5x2+3x3=30 y'≤0，y2≥0，y3'无约束 x1≤0，x2无约束，x3≥0 2014-12-15
2014-12-15 9 §2 原问题与对偶问题 0 6 7 3 3 3 2 6 5 5 4 2 6 5 5 4 4 3y 7 . . max 24 15 30 30 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 1 2 3 4 y y y y y y y y y y y y y y y y y st y y y y ， ， ， （2）令上式四个约束条件对应的对偶变量分别为y1，y2，y3，y4，则其 对偶问题为： （3）令y1′= - y1，y3 ′= y3 – y4 ，中间两个约束条件合成等式约束，有 ' 0， 0， '无约束 6 ' 7 3 ' 3 2 ' 6 5 ' 4 4 ' 3y 7 . . max 24 ' 15 30 ' 1 2 3 1 2 3 1 2 3 1 2 1 2 3 y y y y y y y y y y s t y y y 0, , 0 5 3 30 3 6 7 15 4 2 6 24 . . min 7 4 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x st z x x x 无约束
§2原问题与对偶问题 也可直接按教材表22中的对应关系写出非对称形式的对偶问题。 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数max 目标函数min m个 约束条件 m个 ≤ ≥0 銮 ≥ ≤0 = 无约束 n个 n个 塞 ≥0 ≥ ≤0 ≤ 约束条件 无约束 =
2014-12-15 10 §2 原问题与对偶问题 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数 max 目标函数 min 约 束 条 件 m个 m个 变 量 ≤ ≥0 ≥ ≤0 = 无约束 变 量 n个 n个 约 束 条 件 ≥0 ≥ ≤0 ≤ 无约束 = 也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题