运筹学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时，约束条件≥