《线性规划的对偶理论与灵敏度分析[内容充实]》由会员分享，可在线阅读，更多相关《线性规划的对偶理论与灵敏度分析[内容充实]（23页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划的对偶理论与灵敏度分析主要内容对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划讲授重点对偶基本性质、对偶单纯形方法、灵敏度分析讲授方式讲授式、启发式本章知识结构图第一节 线性规划的对偶问 题 一、对偶问题的提出 首先通过实际例子看对偶问题的经济意义。 例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP1) max z2xl+x2 现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自
2、己组织生产活动时获取的盈利。设分别用y1、y2、和y3代表单位时间(h)设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和1小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电，盈利1元。由此y1，y2，y3的取值应满足 6y2+y32 5y1+2y2+y31 (2.1) 又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有 min z15y1+24y2+5y3 (2.2)显然yi0(il，2，3)，再综合(2.1)，(2.2)式有。(LP 2) min 15y1+24y2+5y3 上述LP1和LP2是两个线性规划问题，通常称前者为原问题
3、，后者是前者的对偶问题。 二、对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。对称形式下线性规划原问题的一般形式为：max z=c1x1+c2x2+cnxn (2.3)用yi（i=1，m）代表第i种资源的估价，则其对偶问题的一般形式为: min w=b1y1+b2y2+bmym (2.4)用矩阵形式表示，对称形式的线形规划问题的原问题为：max z=CX (2.5) 其对偶问题为： min w=Yb 将上述对称形式下线性规划的原问题与对偶问题进行比较，可以列出如表2-1所
4、示的对应关系。 表 21原 问 题对偶问题A约束系数矩阵其约束系数矩阵的转置B约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数max z=CXmin =约束条件AXb决策变量X0Y0上述对偶问题中令= ，可改写为 max =-Yb 如将其作为原问题，并按表2-1所列对应关系写出它的对偶问题则有 再令则上式可改写为： 可见对偶问题的对偶即原问题。三、非对称形式的原-对偶问题关系因为并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。考虑下面的例子。例2 写出下述线性规划问题的对偶问题思路是先将其转换成对称形式，再
5、按表2-1的对应关系来写。下面将对称或不对称线性规划原问题同对偶问题的对应关系，统一归纳为表2-2所示形式。 表2-2原问题（对偶变量）对偶问题（原问题）A约束系数矩阵约束条件系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量c目标函数中的价格系数向量约束条件右端项向量目标函数约束条件原问题（对偶变量）对偶问题（原问题）约束条件第二节 对偶问题的基本性质本节的讨论先假定原问题及对偶问题为对称形式线性规划问题，即原问题为： (2.9) 其对偶问题为： (2.10) 然后说明对偶问题的基本性质在非对称形式时也适用。 为本节讨论及后面讲述的需要，这里先介绍有关单纯形法计算的矩阵描述。 一、单
6、纯形法计算的矩阵描述 对称形式线性规划问题(2.9)的矩阵表达式加上松弛变量后为： (2.11)上式中Xs为松弛变量，Xs=( xn+1,xn+2,，xn+m)，I为mm单位矩阵。单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。将B在初始单纯形表中单独列出，而A中去掉后的若干列后剩下的列组成矩阵N，这样(2.11)的初始单纯形表可列成如表2-3的形式。 表 2-3非基变量基 变 量XB XNXs0 Xs bB NIcj-zjCB CN0当迭代若干步，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭
7、代是对约束增广矩阵进行的行的初等变换，对应Xs的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有表2-4形式。 表 2-4基 变 量非基变量XBXN XsCB XB B-1bIB-1N B-1cj-zj0CN-CB-1N -CBB-1从表2-3和表2-4看出，当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为，则有：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为； (2)初始单纯形表中基变量b,，迭代后的表中b,，(3)初始单纯形表中约束系数矩阵为A，IB，N，I，迭代后的表中约束系数矩阵为A，IB，N，II，N，。(4)若初始矩阵中变量 的系数向量为 迭代后为
8、 ，则有 （2.13）（5）当B为最优解时，在表2-4中应有 （2.14） (2.15) 因 的检验数可写为 (2.16) 故(2.14)(2.16) 式可重写为 (2.17) (2.18)称为单纯乘子，若令 则(2.17)、(2.18)式可改写为 (2.19) 看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有 (2.20)由(2.20)式看出，当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。根据下一节讲述的对偶问题的基本性质，将看到这时对偶问题的解也为最优解。下面通过例子说明两个问题的变量及解之间的对应关系，见例3。例3
9、本章例1中列出了两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：用单纯形法和两阶段法求得两个问题的最终单纯形表分别见表2-5和表2-6。表2-5原问题变量松弛变量15/20015/4-15/27/21001/4-1/23/2010-1/43/20001/41/2对偶问题的剩余变量对偶问题变量表 2-6对偶问题变量对偶问题剩余变量1/4-5/410-1/41/41/215/2011/2-3/215/2007/23/2原问题松弛变量原问题变量从表2-5和表2-6，可以清楚看出两个问题变量之间的对应关系。此处分析解的对应关系，并指出：只需求解其中一个问题，从最优解的单纯形表中能得到另一个
10、问题的最优解。 二、对偶问题的基本性质 1.弱对偶性。如果是原问题的可行解，是其对偶问题的可行解，则恒有 证明：由目标和约束不等式易得。由弱对偶性，可得出以下推论： (1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 (2)如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解(注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然)。 (3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问
11、题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。 2.最优性。如果是原问题的可行解, 是其对偶问题的可行解，且有 则是原问题的最优解，是对偶问题的最优解。3.强对偶性(或称对偶定理)。若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。 证 由于两者均有可行解，根据弱对偶性的推论(1)，对原问题的目标函数值具有上界，对偶问题的目标函数值具有下界；因此两者均具有最优解。又由本节的公式(2.19)和(2.20)知，当原问题为最优解时，其对偶问题的解为可行解，且有，由最优性知，这时两者的解均为最优解。 4.互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即 若 ， 则有， 即 若 ，即，则有 因此一定有 证 由弱对偶性知
