《对偶和灵敏度分析》由会员分享，可在线阅读，更多相关《对偶和灵敏度分析（65页珍藏版）》请在金锄头文库上搜索。
1、例1：复习典型引例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位产品所消耗资源以及产生的利润如下表： 第二章：对对偶问题问题资源产品III资源限量设备128 台时 原材料A4016 kg 原材料B0412 kg 利润（元/件）23 对偶问题的提出 资源产品III资源限量 设备128 台时 原材料A4016 kg 原材料B0412 kg 利润（元/件）23 若企业不打算自己生产 而将资源出售（租），企 业应考虑如何定价。设 y1y2y3为3种资源的单 位售价，则有如下模型， 我们称其为原问题的对偶 模型。 Min W=8Y1+16Y2+12Y3Y1+4Y2 22Y1 +4Y33Y1Y2 Y
2、30 Max Z=2X1+3X2 Min W=8Y1+16Y2+12Y3X1+2X28 Y1+4Y2 24X1 16 互为对偶 2Y1 +4Y334X2 12 Y1Y2 Y30 X1X20 对对于LP问题问题 P： Max Z=CXAXbX0称以下问题问题 DP为为其对对偶问题问题 DP： Min W=bTYATYCY0一、对偶问题的提出任何一个求极大的线性规划问题都有一个求极小的线性 规划问题与之对应，反之亦然.把其中一个叫原问题，则另一个就叫做它的对偶问题， 这一对互相联系的两个问题就称为一对对偶问题。 原问题（P）对偶问题（D）二、原问题与对偶问题的对应关系( 一)对称型对偶问题其中 y
3、i 0 （i = 1,2,m）称为对偶变量。变量均具有非负约束，且约束条件：当目标函数求极大时 均取“”号，当目标函数求极小时均取“”号。max z = c1x1 + c2x2 + + cnxn s.t. a11x1 + a12x2 + + a1nxn b1a21x1 + a22x2 + + a2nxn b2(P) am1x1 + am2x2 + + amnxn bmxj 0 （j = 1,2,n）min w = b1 y1 + b2 y2 + +bm ym s.t. a11y1 + a21 y2 + + am1ym c1a12y1 + a22y2 + + am2 ym c2(D) a1ny1
4、 + a2ny2 + + amnym cnyi 0 （i = 1,2,m）(二)非对称型对偶问题分析：化为对称形式。maxx10, x20, x3无约束s.t. a11x1 + a12x2 + a13x3 b1z = c1x1 + c2x2 + c3x3 a31x1 + a32x2 + a33x3 b3a21x1 + a22x2 + a23x3 = b2令maxs.t.(二)非对称型对偶问题maxs.t.对偶变量mins.t.对偶问题：(二)非对称型对偶问题mins.t.令mins.t.mins.t.3个 =约束条件变 量(二)非对称型对偶问题mins.t.原问题对偶问题目标函数 max目标函
5、数 min目标函数的系数约束条件右端常数约束条件右端常数目标函数的系数3个 =3个 0 0无符号限制约束条件变 量3个 0 0无符号限制原问题（对偶问题）对偶问题（原问题）二、原问题与对偶问题的对应关系例2、写出下述线性规划问题的对偶问题解：设对偶变量为max s.t.mins.t.则对偶问题为例3、写出下述线性规划问题的对偶问题解：设对偶变量为min s.t.maxs.t.则对偶问题为练习、写出下述线性规划问题的对偶问题max s.t.min s.t.对偶问题的基本性质1.对称性2.弱对偶性3.无界性4.最优性7.原问题与对偶问题单纯形表间的性质5.互补松弛性6.强对偶性对偶问题的基本性质m
6、ax z=CXs.t. AX bX 0min w =bTYs.t. ATY CTY 0s.t.（P）s.t.（D）对偶问题1、对称性定理：对偶问题的对偶是原问题。对偶问题max z = CX s.t. AX bX 0max w = bTY s.t. ATY CT Y 0min w = bTY s.t. ATY CTY 0min z = CX s.t. AX bX 02、弱对偶性定理：设 和 分别是原问题（P） 和其对偶问题（D）的可行解，则恒有2、弱对偶性定理：设 和 分别是原问题（P） 和其对偶问题（D）的可行解，则恒有推论：原问题任一可行解的目标函数值是其对偶问题目标 函数值的下界；反之，
7、对偶问题任一可行解的目标函数值 是其原问题目标函数值的上界。3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解 ，则另一个问题无可行解。原问题有可行解但目标函数值无界对偶问题无可行解对偶问题有可行解但目标函数值无界原问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标 函数值的下界；反之，对偶问题任一可行解的目标函数值 是其原问题目标函数值的上界。3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解 ，则另一个问题无可行解。原问题有无界解对偶问题无可行解推论：原问题任一可行解的目标函数值是其对偶问题目标 函数值的下界；反之，对偶问题任一可行解的目标函数值 是其原问题
8、目标函数值的上界。可能是无可行解推论1：在互为对偶的两个问题中，若一个问题无可行解 ，则另一个问题或具有无界解或无可行解。3、无界性定理：在互为对偶的两个问题中，若一个问题具有无界解 ，则另一个问题无可行解。推论1：在互为对偶的两个问题中，若一个问题无可行解 ，则另一个问题或具有无界解或无可行解。推论2：在互为对偶的两个问题中，若一个问题有可行解 ，另一个问题无可行解，则可行的问题无界。无界解无可行解无可行解无界解对偶问题原问题例1、利用对偶理论证明问题无界（无最优解）解：设对偶变量为max s.t.min s.t.则对偶问题为由 知，第一个约束 可知对偶问题无条件不成立， 可行解。 易知(0
9、, 0, 0)T 是原问题的一 个可行解，故原问题可行。 由无界性定理可知，原问题 有无界解，即无最优解。对偶问题 不可行原问题无界或不可行无界 不可行练习、证明下列线性规划问题无最优解min s.t.max s.t.对偶问题原问题的一个可行解：对偶问题不可行：找矛盾4、最优性定理：设 和 分别是原问题（P） 和其对偶问题（D）的可行解，且有则 和 分别是原问题（P）和其对 偶问题（D）的最优解。5、互补松弛性定理：设 和 分别是原问题和其 对偶问题的最优解，若对偶变量 ，则原问题相应的约束条件若约束条件 ，则相应的对偶变量5、互补松弛性定理：设 和 分别是原问题和其 对偶问题的最优解，若对偶
10、变量 ，则原问题相应的约束条件若约束条件 ，则相应的对偶变量5、互补松弛性定理：设 和 分别是原问题和其 对偶问题的最优解，若对偶变量 ，则原问题相应的约束条件若约束条件 ，则相应的对偶变量若 ，则若 ，则若 ，则若 ，则例2、利用互补松弛定理求最优解max s.t.已知原问题的最优解是求对偶问题的最优解。解：设对偶变量为min s.t.则对偶问题为设对偶问题的最优解为因 由互补松弛性知解方程组得 故对偶问题的最优解为例3、利用互补松弛定理求最优解已知原问题的最优解是max s.t.求对偶问题的最优解。对偶变量为min s.t.则对偶问题为设对偶问题的最优解为将 代入原问题约束条件得解：由互补
11、松弛性知又故对偶问题的最优解为得例4、利用互补松弛定理求最优解已知其对偶问题的最优解是min s.t.求原问题的最优解。对偶问题为设原问题的最优解为解：min s.t.将 代入原问题约束条件得： (2)、(3)、(4)为严格不等式由互补松弛性知 又因由互补松弛性知得故原问题最优解为6、强对偶性（对偶定理）定理：若原问题有最优解，则其对偶问题也一定具有最优 解，且目标函数的最优值相等。s.t.用单纯形法求原问题的最优解：s.t.非基变量基变量XsXIA0C基变量 基变量 基可系数 行解0 Xs bXB XNB NCB CNXBI0CB CNB NXB XN单纯形法计算的矩阵描述非基变量基变量Xs
12、I0基变量 基变量 基可系数 行解0 Xs b基变量非基变量XB基变量 基变量 基可系数 行解CNCBB-1N B-1N B-1XN XsB-1bCB进行初等 行变换CBB-1 若CNCBB-1N 0CBB-1 0 最优解X*= B-1bB-1存在6、强对偶性（对偶定理）min w =bTYs.t. ATY CTY 0若CNCBB-1N 0CBB-1 0 最优解X*= B-1b令YT= CBB-1，则有CNYT N 0， Y 0因CBYTB = 0，故 CYT A 0，即AT Y CT ，说明Y是D的可行解max z=CXs.t. AX bX 0此时目标函数值 w =bTY=YTb= CBB-
13、1b 原问题的最优值z= CB-1b= CBB-1b由最优性定理知，Y是D的最优解。定理：若原问题有最优解，则其对偶问题也一定具有最优 解，且目标函数的最优值相等。6、强对偶性（对偶定理）推论：若一对对偶问题都有可行解，则它们都有最优解， 且目标函数的最优值必相等。定理：若原问题有最优解，则其对偶问题也一定具有最优 解，且目标函数的最优值相等。互为对偶的两个问题，只会出现以下三种关系： 都有最优解，且最优值相等 一个有无界解，另一个无可行解； 两个都无可行解。对偶问题的基本性质一个问题max另一问题min应用有最优解有最优解强对偶性无界解 （有可行解）无可行解 无界性 （证无最优解）无可行解无界解 （有可行解）已知最优解求最优解互补松弛性7、原问题与对偶问题单纯形表间的性质？XBI0CB CNB NXB XN非基变量基变量XsI0基变量 基变量 基可系数 行解0 Xs b基变量非基变量XB基变量 基变量 基可系数 行解CNCBB-1N B-1N B-1XN XsB-1bCBYT= CBB-1CBB-1 基 变 量基变量XB非基变量XC松弛变量XS基解B-1b检 验 数原问题非基变 量的检验数是 CN - CB B-1N原问题松弛变量 的检验数是Y= - CB B-
