运筹学OR 教师:周志英 ·信息管理系 电话:663372 办公室:62-317 ·考查:平时30%+期末考试70% ·教材∷黄桐城上海人民 出版社2004清华大学出版社
运 筹 学OR • 教师：周志英 • 信息管理系 • 电话：663372 • 办公室：62-317 • 考查:平时30%+期末考试70% • 教材:黄桐城 上海人民 出版社 2004 清华大学出版社
第三章对偶线性规划 口对偶的定义 口对偶问题的性质 口原始对偶关系 ■目标函数值之间的关系 ■最优解之间的互补松弛关系 最优解的Kuhn- Tucker条件 口对偶可行基对偶单纯形法 口对偶的经济解释
第三章 对偶线性规划 p对偶的定义 p对偶问题的性质 p原始对偶关系 n目标函数值之间的关系 n最优解之间的互补松弛关系 n最优解的Kuhn-Tucker条件 p对偶可行基对偶单纯形法 p对偶的经济解释 DUAL
对偶问题的提出 产品甲产品乙资源总量 设备台时 8台时 原料A 4 原料B 0 2043 16kg 12k g 利润(元件)2 ·假定该厂决策者不考虑自己生产产品,而是将资源 出租和出售,问决策者应如何给每种资源定价? 考虑两个因素(1)每种资源所收回的费用应不低于 自己生产时可获得的利润 (2)定价不能太高,要使对方能接受
对偶问题的提出 • 假定该厂决策者不考虑自己生产产品，而是将资源 出租和出售，问决策者应如何给每种资源定价？ 产品甲 产品乙 资源总量 设备台时 1 2 8台时 原料A 4 0 16kg 原料B 0 4 12kg 利润（元/件） 2 3 考虑两个因素（1）每种资源所收回的费用应不低于 自己生产时可获得的利润 （2）定价不能太高，要使对方能接受
解:设y1,y2,y3分别表示三种资源的单价 生产产品甲:y1+4y22 产品乙:2y1+4y323 且y1,y2,y320 总收入W=8y1+16y2+12y3 ·从工厂决策者而言,w越大越好,但为使对方容 易接受,在保证上述统计下,应使对方总支出尽 可能少。 minw=8y1+16y, +12y3max z=2X1+3X y1+4y2≥2 st.x1+2x≤8 2y1+4y323 4x1≤16 y1,y2,y320 4x2≤12 x1x2≥0
• 解：设y1，y2，y3分别表示三种资源的单价 • 生产产品甲：y1+4y2≥2 • 产品乙：2y1+4y3≥3 • 且y1，y2，y3 ≥0 • 总收入w=8y1+16y2+12y3 • 从工厂决策者而言，w越大越好，但为使对方容 易接受，在保证上述统计下，应使对方总支出尽 可能少。 • ∴ minw=8y1+16y2+12y3 • y1+4y2≥2 2 y1+4y3≥3 • y1，y2，y3 ≥0 max z=2x1+3x2 s.t. x1+2x2≤8 4x1 ≤16 4x2≤12 x1, x2≥0
对偶的定义 原始问题 对偶问题 max zCX min w=yb st.AX≤b St.YA≥C X>0 Y>0 max min A b n AT 对称:(1)变量20,b无限制 (2)当max时,约束条件≤ 当min时,约束条件≥
对偶的定义 原始问题 max z=CX s.t. AX ≤ b X ≥0 对偶问题 min w=Yb s.t. YA ≥ C Y ≥0 ≤ max A b C AT CT b ≥ min m n m n 对称：（1）变量≥0, b无限制 （ 2）当max时，约束条件≤ 当min时，约束条件≥
对称的原始问题和对偶问题 原问题为 max z=6X1+9x2 原问题是极大化问题 st.x1+2X2≤2 原问题的约束全为≤ 2X13X2≤3 原问题有2个变量,3个约束 x1+2x2≤-1 原问题的变量全部为非负 x1x2≥0 对偶问题为 对偶问题是极小化问题 min w=2y1+ 3y2-y3 对偶问题的约束全为≥ st.y1+2y2+y326 对偶问题有3个变量,2个约束 2y1-3y2+2y3≥9 对偶问题的变量全部为非负 yi y2r y320 原问题变量的个数(2)等于对偶问题约束条件的个数(2) 原问题约束条件的个数(3)等于对偶问题变量的个数(3)
对称的原始问题和对偶问题 对偶问题为 min w=2y1+3y2-y3 s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0 原问题为 max z=6x1+9x2 s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0 原问题是极大化问题 原问题的约束全为≤ 原问题有2个变量，3个约束 原问题的变量全部为非负 对偶问题是极小化问题 对偶问题的约束全为≥ 对偶问题有3个变量，2个约束 对偶问题的变量全部为非负 原问题变量的个数(2)等于对偶问题约束条件的个数(2) 原问题约束条件的个数(3)等于对偶问题变量的个数(3)
根据定义写出对偶问题的练习 max z=2x,+x, sx st.x13X2+2x35X4≤6 4x1+x2-5X3+2X4≤9 x1+2X2+x4≤12 yyy 123 x1rX2nx34≥0 原问题有4个变量,3个约束,对偶问题应该有3个变量,4 个约束。根据定义,对偶问题为: min w=6y1+9y2+12y3 st.y1+42-y322 3y1+y2+2y321 y15y22-3 xxxx 5y1+2y2+y320 234 y1y2y320
根据定义写出对偶问题的练习 max z=2x1+x2-3x3 s.t. x1-3x2+2x3- 5x4 ≤ 6 4x1+x2- 5x3+2x4 ≤ 9 -x1+2x2 +x4 ≤ 12 x1, x2, x3, x4 ≥0 原问题有4个变量，3个约束，对偶问题应该有3个变量，4 个约束。根据定义，对偶问题为： y1 y2 y3 min w=6y1+9y2+12y3 s.t. y1+4y2- y3 ≥2 -3y1+ y2+2y3 ≥ 1 2y1-5y2 ≥ -3 -5y1+2y2+ y3 ≥ 0 y1, y2, y3 ≥0 x1 x2 x3 x4
对偶问题的对偶 maxw=-8y4-16y2-12y mnw=8y1+16y2+12y3写成原问st.y4yzs2 题的形式 y1+4y2≥2 y14y3≤-3 y1+4y323 yyzy3≥0 y1,y2,y3≥0 根据定义写出对偶问题 max z=2X1+ 3X2 st.x1+X2≤8 min z=-2X1-3X2 4x1≤16 st.-x1-X≥-8 变形 4x≤12 -4x12-16 x1X20 -4x2≥-12 X1X2≥0 结论:对偶问题的对偶就是原始问题。两个问题中的任 个都可以作为原始问题。另一个就是它的对偶问题
对偶问题的对偶 minw=8y1+16y2+12y3 y1+4y2 ≥2 y1+ 4y3≥3 y1，y2，y3 ≥0 max w’=-8y1 -16y2 -12y3 s.t. -y1 -4y2 ≤ -2 -y1 - 4y3 ≤ -3 y1, y2,y3 ≥0 min z’=-2x1-3x2 s.t. –x1-x2 ≥ -8 -4x1 ≥ -16 -4x2 ≥ -12 x1, x2, ≥0 max z=2x1+3x2 s.t. x1+x2 ≤ 8 4x1 ≤ 16 4x2 ≤12 x1, x2≥0 结论：对偶问题的对偶就是原始问题。两个问题中的任一 个都可以作为原始问题。另一个就是它的对偶问题。 写成原问 题的形式 根据定义写出对偶问题 变形
其他形式的对偶一极大化问题有“2"约束 max z=2X+3x2-X3 max z=2X1+ 3x2-X3 2xy-Xx≤-6 st.x1+2x2+x326 st 2x1-3X2+2X2s9 2X1-3X2+2X39 X1 X, x220 x1x2,x3≥0 min w=6y1+9y2 min w=-6y1+9y2 s.t. y1+2y222 Y1=-y'1y150 s.t. -y1+2y222 2y1-3y223 2y1-3y23 y1+2y2-1 y1+2y22-1 y1≤0,y2≥0 yry2≥0 如果极大化原始问题中一个约束是“≥"约束,则对偶问 题中相应的变量≤0
其他形式的对偶—极大化问题有“≥ ”约束 max z=2x1+3x2-x3 s.t. x1+2x2+x3 ≥ 6 2x1-3x2+2x3≤9 x1, x2, x3≥0 max z=2x1+3x2-x3 s.t. -x1-2x2-x3≤-6 2x1-3x2+2x3≤9 x1, x2, x3≥0 min w=-6y1 ’+9y2 s.t. -y’ 1+2y2 ≥ 2 -2y’ 1 -3y2 ≥ 3 -y’ 1+2y2 ≥ -1 y’ 1, y2≥0 min w=6y1+9y2 s.t. y1+2y2 ≥ 2 2y1- 3y2 ≥ 3 y1+2y2 ≥ -1 y1≤0, y2≥0 y1=-y’ 1, y1≤0 如果极大化原始问题中一个约束是“≥”约束，则对偶问 题中相应的变量≤0
其他形式的对偶一原始问题有“=“约束 min z=2X,1+3x2X3min z=2X1+3X2-X3 min z=2X1+3X2-X3 st.x1+2x2+x3=6 st.x1+2X2+x2≥6 st.x1+2x2+x226 x1+2x2+x3≤6 2X1-3X2+2X3≥9 x12x2x32-6 2x13X2+2x2≥9 2x1-3x2+2X3≥9 x1X,x2≥0 x1X2x320 Xx,x20 y1=y1y1∠:Free max y=6 1+9y2 maxw=6(v1 -)+9y2 maxw=6y1'-6y1+9y2 st.y1+2y2≤2 st.(y1y1)+2y2≤2 st.y1-y1+2y2≤2 2y1-3y2≤3 2(y1y1)-3y2≤3 2y1-2y13y2≤3 W1+2y2≤-1 (y1y"1)+2y2≤-1 y1y1+2y2≤-1 yi: Free y220 y'ly1y220 y'ly1y220 如果原始问题中一个约束是等号约束,则对偶问题中相应的变 量没有符号限制
min z=2x1+3x2-x3 s.t. x1+2x2+x3=6 2x1-3x2+2x3≥9 x1, x2, x3≥0 min z=2x1+3x2-x3 s.t. x1+2x2+x3≥6 x1+2x2+x3≤6 2x1-3x2+2x3≥9 x1, x2, x3≥0 min z=2x1+3x2-x3 s.t. x1+2x2+x3≥6 -x1- 2x2- x3≥-6 2x1-3x2+2x3≥9 x1, x2, x3≥0 maxw=6y1 ’-6y1 ’’+9y2 s.t. y’ 1-y’’ 1+2y2≤2 2y’ 1-2y’’ 1-3y2≤3 y’ 1-y’’ 1+2y2≤-1 y’ 1, y’’ 1, y2≥0 max w=6(y1 ’-y1 ’’)+9y2 s.t. (y’ 1-y’’ 1)+2y2≤2 2(y’ 1-y’’ 1)-3y2≤3 (y’ 1-y’’ 1)+2y2≤-1 y’ 1, y’’ 1, y2≥0 max y=6y1+9y2 s.t. y1+2y2≤2 2y1- 3y2≤3 w1+2y2≤-1 y1:Free y2≥0 y1=y’ 1-y’’ 1 , y1:Free 如果原始问题中一个约束是等号约束，则对偶问题中相应的变 量没有符号限制 其他形式的对偶—原始问题有“=”约束