1、大连海事大学交通运输管理学院 2.4.1 对偶问题的提出 2.4.2 原问题与对偶问题 2.4.3 对偶问题的性质 2.4.4 对偶变量的经济含义 2.4.5 对偶单纯形法某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台时及 A、 B两种原材料的消耗，如表 1-1所示。每生产一件产品 可获利 2元，每生产一件产品 可获利 3元，问应如何安排计划使该工厂获利最多 ? -第 2章 对偶问题 -4-设 企业生产甲产品为 X1件， 乙产品为 X2件，则 2.资源最低售价模型资源最低售价模型(原问题 ) ( 对偶问题 )设第 i种资源价格为 yi,( i=1, 2, 3) 则有y1
2、y2y3y4一般表示式：原问题： max z = c1 X1 + c2 X2 + + cn Xns.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b2 am1 X1 + am2 X2 + + amn Xn bmxj 0， j=1,2, ,n 对偶问题： min w = b1 y1 + b2 y2 + + b m yms.t a11 y1 + a21 y2 + + a m1 ym c1 a12 y1 + a22 y2 + + a m2 ym c2 a1n y1 + a2n y2 + + a mn ym cn yi 0， (i
3、=1,2,m )典式模型对应对偶结构矩阵表示（ 1） max z = C X s.t AX b X 0min w = Y bs.t YA CY 0 对偶问题原问题（ 2）若模型为 max z = C X s.t AX b X 0 max z = C Xs.t - AX -b X 0变形min w = Y bs.t YA CY 0 Min w=Y (-b)st. Y (-A) CY 0令 Y=- Y 对偶问题对偶变量 Y（ 3） max z = C X s.t AX b X 0变形设 X= -X max = -CX st. -AX b X 0min w = Y bs.t YA CY 0则有min
4、 w = Y bs.t -YA - CY 0用矩阵形式表示：（ 1） max z = C X min w = Y bs.t AX b s.t YA CX 0 Y 0 （ 2） max z = C X min w = Y bs.t AX b s.t YA CX 0 Y 0 （ 3） max z = C X min w = Y bs.t AX b s.t YA CX 0 Y 0原问题 (对偶问题 ) 对偶问题 (原问题 )目标函数系数 约束右端项 约束右端项 目标函数系数约束条件系数列向量 A 约束条件系数行向量 AT变量个数 约束条件个数max min变量 x j : 约束方程 i :x j 0 x j 无约束 =x j 0 约束方程 : 变量 y i : y i 0 = y i 无约束 y i 0
