【教案】运筹学课件第二章线性规划的对偶理论与灵敏度分析教案.pdf

第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求1、掌握对偶理论及其性质2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法二、课时6 学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格 )；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量 (人工变量带来很多麻烦，两阶段法则增加一倍的计算量)例：某家具厂木器车间生产木门与木窗；两种产品加工木门收入为56 元/扇，加工木窗收入为30元/扇生产一扇木门需要木工4 小时，油漆工2 小时；生产一扇木窗需要木工3 小时，油漆工1 小时；该车间每日可用木工总共时为120 小时，油漆工总工时为50 小时。

问： (1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单他想利用该木器车间的木工与油漆工来加工完成他的订单他就要考虑付给该车间每个工时的价格他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少解(1)：设该车间每日安排生产木门x1 扇，木窗x2 扇，则数学模型为0502120343056max21212121xxxxxxxz精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 28 页 - - - - - - - - -X*=(15,20) Z*=1440 元解(2)：设 y1为付给木工每个工时的价格，y2为付给油工每个工时的价格0303562450120min21212121yyyyyyywY*=(2,24) W*=1440 元将上述问题1 与问题 2 称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同二、LP 和 DP 的联系与区别(1)一个极大化，一个极小化(2)LP 的价值系数行向量(DP 右端项 ) (3)LP 的系数矩阵 (DP 系数矩阵 ) (4)LP 的右端项 (DP 的价值系数 ) (5)LP 的约束个数 DP 的变量个数(6)LP 的变量个数 DP 的约束个数原问题与对偶问题的关系1对称形式下对偶问题的一般形式定义： 满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；(2)其约束条件当目标函数求极大时取“ ” 号，当目标函数求极小时取“ ” 号； (3)右端项 b 可取负值。

), 1(0max:221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczLPjmnmnmmnnnnnn), 1(0min:221122222112112211112211miycyayayacyayayacyayayaybybybwDPinmmnnnmmmmmm对称形式下原问题及对偶问题的矩阵形式0max:XbAXCXzLP0min:YCYAbYwDP对称性定理：对偶问题的对偶是原问题精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 28 页 - - - - - - - - -证明：在DP 中，令 W = -W 则有0maxYCYAbYW其对偶问题为：0minXbAXCXZ令 Z=-Z，则有0maxXbAXCXZ所以，对偶问题的对偶是原问题例：写出LP 的对偶问题02,1121214222max:21212121xxxxxxxxxxzLP0,224222m i n:321321321321yyyyyyyyyyyywDP2. 非对称形式的原对偶问题关系并非所有的LP 问题都有对称形式，故讨论一般情况下LP 问题如何写出其对偶问题例写出下述线性规划的对偶问题无约束321321321321321004163253234maxxxxxxxxxxxxxxxxz解：先化为对称形式，因为目标函数求极大，所以约束条件变为“”，决策变量 0 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 28 页 - - - - - - - - -4 4 1 6632 5532 334max33213321332133213321xxxxxxxxxxxxxxxxxxxxz令对应上述4 个约束条件的对偶变量分别为 , , ,3321yyyy则有0 , , ,3 653 654 31 32 442min332133213321332133213321yyyyyyyyyyyyyyyyyyyyyyyyw令 , 33322yyyyy，将上边3，4 两个约束条件合并，得无约束321321321321321003654313242minyyyyyyyyyyyyyyyw经过以上分析，可以总结出原规划与对偶规划相关数据间的联系。

对偶关系相互对照表原问题 (LP) 对偶问题 (DP) 目标函数形式max 目标函数形式min 变量N 个变量变量 0 变量 0 无正负限制约束n 个约束约束约束约束约束M 个约束约束约束约束变量m 个变量变量 0 变量 0 无正负限制精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 28 页 - - - - - - - - -约束方程右端项目标函数价值系数目标函数价值系数约束方程右端项例写出下列线性规划的对偶问题无约束32132132132132100121213225minxxxxxxxxxxxxxxxz结果无约束32132132132132100322252maxyyyyyyyyyyyyyyyw练习写出下列线性规划的对偶问题无约束321313213213210034313242maxxxxxxxxxxxxxxxz练习结果无约束321321213213210041323234minyyyyyyyyyyyyyyw精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 28 页 - - - - - - - - -第二节对偶问题的基本性质 (对偶定理 ) 一、单纯形法的矩阵描述对于对称形式的线性规划问题，其标准形式为0maxXbAXCXz0,0m a xssXXbIXAXCXzXS为松弛变量 ,XS=(xn+1,xn+2, ,xn+m), I 为 mm 单位矩阵),(),(NBNBCCCXXXNBAbNXBXbXXNBNBNB),(列出初始单纯形表项目非基变量基变量XBXNXSCBXBb B N I cj-zjCBCN0 设若干步迭代后，基变量为XB, XB在初始单纯形表中的系数矩阵为B，而 A 中去掉 B 的若干列组成矩阵 N，则迭代后的单纯形表为：项目基变量非基变量XBXNXSCBXBB-1b I B-1N B-1cj-zj0 CN-CB B-1N -CB B-1从表中看出：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1(2)初始单纯形表中的基变量XS=b，迭代后为XB=B-1b (3)初始单纯形表中约束系数矩阵A,I=B,N,I，迭代后的表中为B-1A, B-1I= B-1B, B-1N, B-1I I, 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 28 页 - - - - - - - - -B-1N, B-1 (4)若初始矩阵中变量xj的系数列向量为Pj，迭代后为Pj ，则 Pj = B-1Pj(5)当 B 为最优基时，应有)2(0)1 (011BCNBCCBBN又因为 XB的检验数可写为)3(001BBCCICCBBBB将(1)和 (3)合并，则有0011BCABCCBBCBB-1称为单纯形因子，令CBB-1Y 则有0YCYA检验数行的相反数，恰好是对偶问题的可行解。

将 YCBB-1代入对偶问题的目标函数值，ZbBCYbWB1所以当原问题为最优解是，对偶问题为可行解，且两者目标函数值相同，根据下节的对偶问题的基本性质，将看到这时对偶问题的解也为最优解二、对偶问题的基本性质对于下面标准形式的原，对偶问题，有以下定理：0max:XbAXCXzLP0m i n:YCYAbYwDP定理 1(弱对偶定理 )：如果 X(0) 是原问题的可行解，Y(0) 是对偶问题的可行解，则恒有C X(0) b Y(0) 证明： X(0) 是原问题的可行解，所以 A X(0) b (1) Y(0) 是对偶问题的可行解，所以A Y(0) C (2) C X(0) A Y(0) X(0) b Y(0) A X(0)Y(0) 即 C X(0) Y(0) b (1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 28 页 - - - - - - - - -(2)如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界则其原问题无可行解。

3)如原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界定理 2(最优准则定理)：如果 X(0) 是原问题的可行解，Y(0) 是对偶问题的可行解，则当 C X(0) Y(0) b 时，X(0) ， Y(0) 分别为各自问题的最优解证明：设X 是 LP 的任一个可行解，则有C X Y(0) b C X(0) 所以X(0) 是最大化问题的最优解Y(0) 是最小化问题的最优解定理 3(最优解存在定理)： 若 LP 和 DP 同时存在可行解， 则它们必都存在最优解,且它们的目标函数值相等证明同上定理 4(无界解定理 )：若原问题 (对偶问题 )为无界解，则其对偶问题(原问题 )无可行解证明： (反证法 )设原问题目标函数为极大值，无上界对偶问题的可行解为Y(0) 则 C X Y(0) b 根据定理1，原问题存在最优解，与假设矛盾，假设不成立定理5(强对偶性定理)：如果原问题和对偶问题中有一个有最优解，则另一个问题也必存在最优解，且两个问题的最优解的目标函数值相等证明：设LP 存在最优解，将其化为标准型，则有00max:aaaaXXbIXAXXCCXzLPXa 为松弛变量， Ca 为其价值系数(Ca=0)，设原问题的最优解为X(0) ，基为 B，则有*)0(aXXX01jBjjPBCC即0),()(1IABCCCBa精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 8 页，共 28 页 - - - - - - - - -0001111BCCABCIBCCABCCBBBaB令 CBB-1 Y(0) 则有0)0()0(YCAY所以 Y(0) 是对偶问题的一个可行解引入定理2，W(0)=Y(0) b CBB-1b=CBXB 也是对偶问题的最优解原问题与对偶问题的解之间只有以下3 种可能的关系两个问题都有可行解，从而都有最优解一个为无界，另一个必无可行解两个都无可行解定理 6(互补松弛性定理)：性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。

也即若0?iy,则有injjijbxa1?,即0。