《管理运筹学》02-5对偶原理.ppt

* Cj ? -4 -12 -18 0 0 当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为 x1=0，x2=3/2，x3=1，max z，=-36， 即min z=36 第3节 对偶与灵敏度分析 对偶单纯形法 * 练习 min z = 3x1+2x2 s.t. 2x1+3x2 ≤ 18 x1 - x2 ≥ 2 x1+3x2 ≥ 10 x1, x2 ≥ 0 解 max z′= -3x1 -2x2 s.t. 2x1+3x2+x3 = 18 x1 -x2 –x4 = 2 x1+3x2 –x5 = 10 x1, x2, x3, x4, x5 ≥ 0 –x1+ x2 +x4 = –2 –x1–3x2 +x5 = –10 第3节 对偶与灵敏度分析 对偶单纯形法 X*= (4,2)T z* = 16 * 第3章 对偶原理  第 3 节 Dual Principle DP 对偶与灵敏度分析 第3节 对偶与灵敏度分析 * 一、 线性规划的对偶关系 二、 线性规划的对偶性质 三、灵敏度分析 四、对偶关系的经济解释 第3节 对偶与灵敏度分析 * 线性规划的对偶关系 对偶问题 y1 y2 y3 由于原拟用于生产每件甲产品的1个A工时和3个c工时能创造3百元 利润，所以出租上述数量的各资源的盈利起码应不低于3百元。 2y1+y2+4y3 ≥ 2 ① 2y1+2y2 +4y4 ≥ 3 ② Min w =12y1+8y2+16y3+12y4 21 4 0 2 20 4 128 16 12 A B C D 车间 产品 甲 乙 单耗（工时/件） 加工能力 （工时/天） 利润 2 3 s.t. 2x1 + 2x2 ≤12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1 ， x2 ≥ 0 max z = 2x1 + 3x2 y1， y2， y3 ， y4 ≥ 0 ③ ω y3 第3节 对偶与灵敏度分析 * 原问题 对偶问题 线性规划的对偶关系 第3节 对偶与灵敏度分析 * 线性规划的对偶关系 min w = 8y1 + 12y2 + 36y3 y1 + 3y3 ≥ 3 2y2 + 4y3 ≥ 5 y1 , y2, y3 ≥ 0 s.t. Y*= (0,1/2,1)T w*= 42 max z = 3 x1 + 5x2 x1 ≤ 8 2x2 ≤ 12 3 x1 + 4x2 ≤ 36 x1 ， x2 ≥ 0 s.t. X*= (4,6)T z* = 42 第3节 对偶与灵敏度分析 * 线性规划的对偶关系 对偶结构用矩阵表示为： max z = CX AX≤b X≥0 s.t. (原问题): (对偶问题): min w = Yb YA≥C Y≥0 s.t. 记向量和矩阵为： 第3节 对偶与灵敏度分析 * 其他形式的对偶问题 若模型中原问题约束条件的符号与标准形式相反 变 形 对偶变量Y’ 令Y=Y’ 第3节 对偶与灵敏度分析 * 其他形式的对偶问题 若模型中原问题变量的符号与标准形式相反 设X= -X’ 对偶问题 对偶变量Y’ 第3节 对偶与灵敏度分析 * 对偶问题典式 第3节 对偶与灵敏度分析 其他形