对偶问题(运筹学)教程.ppt

大连海事大学交通运输管理学院;2.4.1 对偶问题的提出 2.4.2 原问题与对偶问题 2.4.3 对偶问题的性质 2.4.4 对偶变量的经济含义 2.4.5 对偶单纯形法; 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多? ;--第2章 对偶问题--;一般表示式： 原问题： max z = c1 X1 + c2 X2 + ┈ + cn Xn s.t　　 a11 X1 + a12 X2 + ┈ + a1n Xn ? b1 a21 X1 + a22 X2 + ┈ + a2n Xn ? b2 　　　······················· am1 X1 + am2 X2 + ┈ + amn Xn ? bm xj ? 0，j=1,2,┈,n 对偶问题： min w = b1 y1 + b2 y2 + ┈ + bm ym 　　 s.t　 a11 y1 + a21 y2 + ┈ + am1 ym ? c1 a12 y1 + a22 y2 + ┈ + am2 ym ? c2 　　　························· a1n y1 + a2n y2 + ┈ + amn ym ? cn yi ? 0，(i=1,2,···,m ) ;典式模型对应对偶结构矩阵表示;（2）若模型为 max z = C X s.t AX ? b X ? 0 ;（3）max z = C X s.t AX ? b X ? 0;用矩阵形式表示： （1） max z = C X min w = Y b s.t AX ? b ======== s.t YA ? C X ? 0 Y ? 0 （2） max z = C X min w = Y b s.t AX ? b ======== s.t YA ? C X ? 0 Y ? 0 （3）max z = C X min w = Y b s.t AX ? b ======== s.t YA ? C X ? 0 Y ? 0; 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项