对偶灵敏度分析

设有线性规划0maxXbAXCXZ其中矩阵Am×n且r(A)=m,12(,,,)nCccc＝Tmbbbb),,,(21X≥0理解为X大于等于零的向量，即xj≥0(j=1,2…,n)。TnxxxX),,,(211.5.3计算公式1.5单纯形法SimplexMethod不妨假设A＝(P1,P2,…,Pn)中前m个列向量构成一个可行基，记为B=(P1,P2,…,Pm)。矩阵A中后n－m列构成的矩阵记为N＝(Pm+1,…,Pn),则A可以写成分块矩阵A=(B，N)。对于基B，基变量为XB=(x1,x2,…,xm)T,非基变量为XN=(xm+1,xm+2,…,xn)T。则X可表示成,同理将C写成分块矩阵C=(CB，CN)，NBXXXCB=(C1,C2,…,Cm),CN=(Cm+1Cm+2，…，cn),则AX=b可写成bNXBXXXNBNBNB)(，1.5单纯形法SimplexMethod因为r(B)=m(或|B|≠0)所以B-1存在，因此可有NNBNBNXBbBNXbBXNXbBX111)(令非基变量XN=0，XB=B-1b，由B是可行基的假设，则得到基本可行解X=(B－1b，0)T消去目标函数中的基变量，于是目标函数可写成NNBBNBNBXCXCXXCCZ),(1111()()BNNNBNBNCBbBNXCXCBbCCBNX1.5单纯形法SimplexMethod将B化为E(E为m阶单位矩阵),即求基本可行解。用B－1左乘表中第二行,得到CBCNXBXNbCBXBEB-1NB-1bλ＝Cj-Zj0CN-CBB－1NZ=CBB－1bCBCNXBXNbCBBNb1.5单纯形法SimplexMethod对于如下形式的线性规划问题：0maxXbAXCXZ引入松弛变量化为标准形如下：TmnnnsxxxX),,,(210,00maxsssXXbEXAXXCXZ1.5单纯形法SimplexMethod记则上述标准形式为,0,,CCEAAXXXs0maxXbXAXCZ由于对应的系数矩阵为单位阵，故容易确定初始基变量为，得到如下初始单纯形表:sXsXCX0XsCBXsAEbC001.5单纯形法SimplexMethodCX0XsbCBXBB-1AB-1B-1bλ＝Cj-ZjC-CBB-1A-CBB-1CBB-1b而对于一般的基B为的子矩阵，A1111111(),0BBBBBABABCCBACCBAECCBACB1.5单纯形法SimplexMethod1.6线性规划的对偶模型DualModelofLP【例1】某企业计划生产甲乙两种产品，生产单位产品所需设备A、B、C台时及产品的单位利润如下表：建立总收益最大的数学模型。产品资源甲乙资源限量设备A11300设备B21400设备C01250单件产品利润501001.6线性规划的对偶模型DualmodelofLP一、换个角度审视生产计划问题【解】设x1，x2分别为产品甲、乙的产量，则线性规划数学模型为：现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？1.6线性规划的对偶模型DualmodelofLP产品资源甲乙资源限量设备A11300设备B21400设备C01250利润(元/件)50100121212212max501003002400..250,0Zxxxxxxstxxx123yyy12xx这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。12312123123min300400250250.100,,0wyyyyystyyyyyy121212212max501003002400..250,0Zxxxxxxstxxx收益优化模型为生产利润的优化模型1.6线性规划的对偶模型DualmodelofLP二、对偶关系一般地，对于线性规划问题njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,...,2,10..............................................................max2211222221211121211122111Pmiycyayayacyayayacyayayatsybybybwinmmnnnmmmmmm,...,2,10..............................................................min2211222221121122111122111D称作互为对偶的线性规划问题，其中一个称为原问题，另一个称为它的对偶问题。用矩阵形式分别写为OXbAXtsXCzT.maxmin.TTwbYAYCstYO0minYCYAYbw1.6线性规划的对偶模型DualmodelofLPmax型min型式号Ⅰ右端Ⅰ…目标Ⅱ………………………式号Ⅱminw目标Ⅰ右端Ⅱ…maxzmnanc2c1cmb2ma1mamy2bna222a21a2y1bna112a11a1ynx2x1x从横行上看表示原线性规划问题（）1P从纵列上看表示对偶线性规划问题（)1D1.6线性规划的对偶模型DualmodelofLP1.7对偶性质Dualproperty0maxXbAXCXZ对偶问题是(记为DP)：0minYCYAYbw这里A是m×n矩阵,X是n×1列向量,Y是1×m行向量。【性质1】对称性:对偶问题的对偶是原问题。设原问题是(记为LP)：1.7对偶性质Dualproperty1对偶性质【性质2】弱对偶性:设X*、Y*分别为LP(max)与DP(min)的可行解，则bYCX**由（L）*AXb左乘得***YAXYb*Y0maxXbAXCXZ（L)0minYCYAYbw（D）证明思路：由（D）*YAC右乘，得*X***YAXCXbYCX**【性质3】最优准则定理:设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当CX*=Y*b.【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。1.7对偶性质Dualproperty**((max))((min))LPDPCXYb在用单纯形法求解LP问题（LP）的最优单纯形表中松弛变量的检验数的相反数就是其对偶问题（DP）的最优解CjCBCN0CBXBXBXNXSbCBEB-1NB-1B-1b0CN－CBB-1N≤0－CBB-1MaxZ=CB(B-1b)minW=(CBB-1)b*1.用单纯形法只要做LP或LD一个问题，即可同时得LP及LD的最优解。*2若LP目标函数无界（无最优解），则LD也无可行解。j0maxXbAXCXZ0minYCYAYbw1.7对偶性质Dualproperty【性质5】LP(max)的检验数的相反数对应于DP(min)的一组基本解。其中第j个决策变量的检验数的相反数对应于(DP)中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量的解。反之，(DP)的检验数对应于(LP)的一组基本解。jSyiSxiyjx12312123123min300400250250.100,,0wyyyyystyyyyyy121212212max501003002400..250,0Zxxxxxxstxxx收益优化模型为生产利润的优化模型2x1x4x25001001010-100-21101001505025000-500-50Z=27500迭代次数基变量cBx1x2x3x4x5b比值Bi/ai2501000000x3x4x5000111002101001001300400250300/1400/1250/1j-y4-y5-y1-y2-y3迭代变量基变量-300-400-25000-Mb1-M120-10150-2501110-10100M-502M-1500-M-25003Bc6y3y13yy-300-250120-10500-111-1500-500-50-25027500y1y2y3y4y5y650/2100/1-x3-x4-x5-x1-x212312123123min300400250250.100,,0wyyyyystyyyyyy121212212max501003002400..250,0Zxxxxxxstxxx收益优化模型为生产利润的优化模型j1、定义****ybwxCZTT由于****1122mmZbybyby是变化的，则假设mbbb,,,212、含义mmbZybZybZy**2**21**1,,,化量问题的目标函数值的变极大化单位时，变化可以理解成当资源)(1*Liyi影子价格（或边际价格）称为第i种资源的机会成本即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i)不变时，bi增加一个单位时目标值Z增加yi个单位。对偶问题的经济学解释：-------------------影子价格0,12416482..3221212121xxxxxxtsxxMaxZQ(4,2)x1x24x1=164x2=12x1+2x2=844083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=14CBXBx1x2x3x4x5b2X10X53X21001/40400-21/214011/2-1/802λj00-3/2-1/8014做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。原料A增加1单位,可多获利1.5元,原料B增加1单位,可多获利0.125元,原料C增加1单位,对利润无影响.***12331y=,y=,y=028******12312min81612max23wYbyyyZxx3、影子价格的作用（1）调节生产规模:例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时,表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模(2)影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，是企业内部根据资源对生产的贡献而作的估计，贡献越大价格越高，是资源效率的一种评价，与市场价格是不同的两个概念。同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样。例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的。而资源的市场价是已知的，是商品价值的货币表现。（3）告诉管理者增加何种资源对企业更有利（5）为新产品定价提供依据(4)了解生产要素对产出贡献的分解。通过影子价格分析每种资源获得多少产出。例如，企业获得100万元的利润，生产过程中产品的直接消耗的资源有材料甲、材料乙，这些资源各产生多少利润，由影子价格可以大致估计出来。1.8对偶单纯形法DualSimplexMethod1.8对偶单纯形法DualSim