运筹学 03 对偶理论及灵敏度分析

1、1.对偶理论 Dual Theory2.影子价格 Shadow price3.对偶单纯形法 Dual Simplex Method 4.灵敏度分析 Sensitivity Analysis5.参数线性规划Parameter LP 对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的对应关系对偶问题的基本性质影子价格对偶单纯形法例1：某厂利用现有资源(设备A、设备B、调试工序)生产两种产品(产品、产品)，有关数据如下表。问如何安排生产，使厂家利润最大？产品 产品 资源限量设备A0515设备B6224调试工序115单位利润21分析：设产品的产量为x1，产品的产量为x2；又设利润为z。则该问题

2、的线性规划数学模型为：max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20换一种思路：厂家的资源只出让而不自己生产，该如何解决？设备A出让单价为y1，设备B出让单价为y2，调试工序出让单价为y3。收购收购代价收购代价最小最小厂家出让所得应不低出让所得应不低于用同等数量的于用同等数量的资源自己生产的资源自己生产的利润。利润。厂家接受的条件：利润需要保证，即 6y2+y32 5y1+2y2+y31收购方接受的条件：收购成本最低，即 min w=15y1+24y2+5y3于是得到一个线性规划模型min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y

3、31 y1,y2,y30原问题max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20v 对偶问题v min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 y1,y2,y30互为对偶问题厂家收购-wy1y2y3y4y5y6y7bmin17.5003.5 M-3.51.5 M-1.5 -8.5y2-1.2510 -0.250.25 0.25-0.25 0.25y37.5010.5-0.5 -1.51.50.5-z x1x2x3x4x5bmax 1000 -0.25 -0.5 -8.5x30011.25 -7.57.5x11000.25 -0.

4、53.5x2010 -0.251.51.5尝试求解上述两个线性规划问题，你会发现 目标函数值一致 两个问题的解都出现在单纯形法表格中 其他规律结论 原问题与其对偶问题实质上一样 两个问题互为对方的另一种表达形式原问题对偶问题对称数学模型 vmax z=CXAXbX0vmin f=bTYATYCTY0目标函数取值max zmin f变量X=(x1,x2,xn)TY=(y1,y2,ym)T目标函数系数 C=(c1,cn)bT =(b1,bn)常数b=(b1,bn)TCT=(c1,cn)T约束条件系数 A=(aij)mnAT=(aij)nm变量 - 约束变量(n,0,0,任意)约束(n,=)约束 -

5、 变量约束(m,=)变量(m,0,0,任意)例2：将下述线性规划作为原问题，请转换为对偶问题max z=5x1+3x2+2x3+4x4 5x1+x2+x3+8x48 2x1+4x2+3x3+2x4=10 x10,x20,x3任意,x4任意解法1：将原问题写成对称形式的线性规划问题。得到max z=5x1+3x2+2(x3-x3)+4(x4-x4) 5x1+x2+(x3-x3)+8(x4-x4)8 2x1+4x2+3(x3-x3)+2(x4-x4)10 -2x1-4x2-3(x3-x3)-2(x4-x4)-10 x10,x20,x30,x30,x40,x40设对偶问题变量y1,y2,y20，直接

6、转换，得min f=8y1+10y2-10y2 5y1+2y2-2y25 y1+4y2-4y23 y1+3y2-3y22 -y1-3y2+3y2-2 8y1+2y2-2y24 -8y1-2y2+2y2-4 y1,y2,y20令y2=y2-y2(即y2取值任意)，合并第3、4个约束条件和第5、6个约束条件，得到原问题的对偶问题min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2y2=4 y10,y2任意解法2：也可以根据原问题与对偶问题的对应关系，直接得到对偶问题：min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2

7、y2=4 y10,y2任意对称性：对偶问题的对偶是原问题(对称定理)。证明： 设原问题为max z=CX,AXb,X0；则其对偶问题为min f=bTY,ATYCT,Y0。 把对偶问题看作原问题，得到线性规划模型为max f=-bTY,-ATY-CT,Y0。 将上述问题转换为对偶问题，得到min z=-(CT)TX,-(AT)TX-(bT)T,X0，即max z=CX,AXb,X0。 所以对偶问题的对偶即为原问题。弱对偶性：若X是原问题的可行解，Y是其对偶问题的可行解，则恒有CXbTY。证明： 因为X为原问题的可行解，故AXb，且X0；因为Y为对偶问题的可行解，故ATYCT，且Y0。 由上述可

8、得CX=XTCTXTATY=YTAXYTb=bTY。原问题原问题对偶问题对偶问题CX*=bTY*CXbTY从弱对偶性可得到以下重要结论： (1)极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 (2)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 (3)若原问题可行，但其目标函数值无界，则对偶问题无可行解。 (4)若对偶问题可行，但其目标函数值无界，则原问题无可行解。 (5)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 (6)对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。最优性：若X是原问

9、题的可行解，Y是其对偶问题的可行解，且有CX=bTY，则X是原问题的最优解，Y是其对偶问题的最优解。证明： 根据弱对偶性及已知条件，对于对偶问题任意可行解Y*都有bTY*CX=bTY，故Y为对偶问题的最优解。 根据弱对偶性及已知条件，对于原问题的任意可行解X*都有CX*bTY=CX，故X为原问题的最优解。强对偶性：若原问题及其对偶问题都有可行解，则两者都有最优解，且最优解的目标函数值相等(对偶定理)。证明：根据弱对偶性可知，由于原问题与对偶问题都有可行解，故原问题目标函数有上界且对偶问题目标函数有下界，所以两者都有最优解。同时，原问题的影子价格即为对偶问题的一个可行解，这个可行解的目标函数即为

10、原问题的目标函数值，且为最优。互补松弛性：在线性规划问题的最优解中，有以下结论成立：(1)若yi0，则aijxj=bi；(2)若aijxjbi，则yi=0。证明：由弱对偶性可知，CXYTAXYTb。且由CX=YTb=YTAX，得到YT(AX-b)=0。这就说明了Y的第i个分量和AX-b的第i个分量若其中一个不为零，另外一个必定为零。结论得证。影子价格的定义影子价格的经济意义当线性规划原问题求得最优解X*时，其对偶问题也得到最优解Y*，且有z*=CX*=bTY*=f*式中b是线性规划问题约束条件的右端项，表示各种资源的拥有量；对偶变量Y*的意义代表在资源最优利用条件下对单位资源的估价。这种估价不

11、是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)(1)资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。(2)影子价格是一种边际价格。在z*=bTY*中对b求导数，得到dz*/dbT=Y*，这说明Y*的值相当于在资源得到最优利用的生产条件下，b每增加一个单位时目标函数z的增量。(3)资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当资源的市场价格低于影子价格时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这

12、种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。(4)在对偶问题的互补松弛性质中有：当ai1xi1+ai2xi2+ainxin0时，ai1xi1+ai2xi2+ainxin=bi，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。(5)从影子价格的含义上再来考察单纯形表的计算。检验数j=cj-CBB-1Pj=cj-aijyi，式中cj代表第j种产品的产值，aijyi是生产该种产品所消耗各种资源的影子价格的总和，即产品的隐含成本。当产品产值大于隐含

13、成本，表明生产该项产品有利，可在计划中安排；否则，用这些资源来生产别的产品更为有利(准确地说，出售更有利)，就不在生产计划中安排。这就是检验数的经济意义。(6)一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。对偶单纯形法的基本思路对偶单纯形法的计算步骤对偶单纯形法的应用举例当一个线性规划的约束条件中包含“”约束时，为了获得初始可行基，必须用大M法，略嫌麻烦。若减去一个剩余变量，认定为基变量，则成为系数为-1的基变量，其基本解不可行。但是，若基本解满足最优性检验，也就是说其对偶问题所对应的解可行，那么通过迭代，

14、可以使得原问题的解逐渐变得可行，也就得到了原问题的最优解。这就是对偶单纯形法的原理。优点是不需要添加人工变量。对偶问题的可行解对偶问题最优解判断最优解判断最优解判断j=cj-zj0原问题基可行解原问题基可行解xB=B-1b0第一步：给出一组满足最优检验的基本解第二步：若当前解可行，则得最优解第三步：确定出基变量。选择负数基本解中最小值所对应的变量作为出基变量。即当 minbi|bi0=br时第r行对应变量为出基变量第四步：确定入基变量。若第r行都大于等于0则无可行解，停止计算；否则计算=minj/arj|arj0,j0clminj/alj|alj0brmin-bi/ir|ir0时，aijj/y

15、i 当yi0时，aijj/yi(5)增加新的变量 略(6)增加新的约束条件 略例5：某家电厂家利用现有资源生产两种产品，有关数据如下表。产品 产品 资源限量设备A(台时)0515设备B(台时)6224调试工序(小时)115单位利润(元/台)21试问 问题1：如何安排生产，使厂家获利最多？ 问题2：当c1=1.5时，最优生产计划有何变化？ 问题3：当c2=2时，最优生产计划有何变化？ 问题4：求原最优解不变时c2的范围。 问题5：b1和b2分别如何改变，原计划不变？ 问题6：为保持最优解不变，a11=0的变化范围。 问题7：增加一个变量，最优解的改变。 问题8：增加一个约束条件，最优解的变化。解

16、：(1)设x1表示产品的产量，x2表示产品的产量，z为厂家利润，则得到线性规划模型 max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最优解x=(3.5,1.5)T 最优值z=8.5(2)c1=1.5时，得到线性规划模型 max z=1.5x1+x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最优解x=(3.5,1.5)T 最优值z=6.75结论：最优解不变，最优值减少(3)c2=2时，得到线性规划模型 max z=2x1+2x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最优解x=(3.5,

17、1.5)T 最优值z=10结论：最优解不变，最优值增加(4)c2的变化范围原问题的最终单纯形表中alj和j见表，计算j/alj也在下表中结论：-1/3c21，或2/3c22Itemx1x2x3x4x5j000 -0.25 -0.5a2j010 -0.25 1.5j/a2j-0-1-1/3(5)略(6)略(7)略(8)略1.将参数的改变计算反映到最终单纯形表上；2.检查原问题是否仍为可行解；3.检查对偶问题是否仍为可行解；4.按下表所列情况得出结论和决定继续计算的步骤。某厂计划生产甲、乙、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表：单位产品 甲 乙 丙 可使用资源量劳动力1/

18、3 1/3 1/31材料1/3 4/3 7/33利润(元)231(1)确定最优的生产方案；(2)当c3增大至多少时，丙产品安排生产；(3)增加3个劳动力，最优解是否改变？(4)劳动力在哪个范围内变化，对利润值的改变有利；(5)增加新的产品丁，需1个劳动力，1个单位原料，利润3元。确定最优的生产方案。(6)添加新约束：x1+2x2+x310，最优解是否改变？概念模型步骤举例 目标函数的系数含有参数的线性规划问题 约束条件右端的常数项含有参数的线性规划问题当参数cj或bi沿某一方向连续变动时，目标函数值z将随cj或bi的变动而呈线性变动，z是这个变动参数的线性函数，因而称为参数线性规划。(1)目标

19、函数的系数含有参数的LP模型设C：价值不变向量；C*：资源变动向量；：参数，则有模型max z()=(C+C*)X AX=b X0(2)约束条件右端的常数项含有参数的LP模型设b：资源不变向量；b*：资源变动向量；：参数，则有模型max z=CX AX=b+b* X0(1)令=0求解得最终单纯形表(2)将C*或b*项反映到最终单纯形表中去(3)值增大或减小，观察原问题或对偶问题 确定现有解(基)允许的的变动范围 当的变动超出这个范围时，用单纯形法或对偶单纯形法求新的解(4)重复第(3)步，直到值继续增大或减小时，表中的解(基)不再出现变化时为止例6：目标函数的系数含有参数的线性规划问题。分析值

20、变化时，下述参数线性规划问题最优解的变化。max z()=(2+)x1+(1+2)x2 5x115 6x1+2x224 x1+x25 x1,x20解：(1)先令=0求得最优 解，见下表。BV -z x1x2x3x4x5b121000 x350100153x462010244x51100155101-0.400-6x1100.2003-x402-1.21063x501-0.20122100-0.20-1 -8x1100.2003x400-0.81-22x201-0.2012(2)然后将反映在最终单纯形表中，见下表BV -zx1x2x3x4x5b12+1+20000 x350100153x4620

21、10244x51100155101+2-0.4-0.200-6-3x1100.2003-x402-1.21063x501-0.20122100-0.2+0.20-1-2-8-7x1100.2003x400-0.81-22x201-0.2012(3)为保持原问题解不变，则-0.2+0.20，且-1-20，即-1/21。解不变，值变z=8+7(4)增加，即1。继续。解变，值变z=5+10BV -zx1x2x3x4x5b100-0.2+0.20-1-2-8-7x1100.200315x400-0.81-22-x201-0.2012-11-000-1-2-5-10 x35010015x44001-21

22、4x2110015(5)减少，即-2-1/2。继续。解变，值变z=6+3。见下表。(6)减少，即-2。初始单纯形表即达最优z=0BV -zx1x2x3x4x5b12+1+20000 x350100153x462010244x51100155101+2-0.4-0.200-6-3x1100.2003x402-1.2106x501-0.2012xz(0,5,15,14,0)T5+101,)(3,2,0,2,0)T8+7-0.5,1(3,0,0,6,2)T6+3-2,-0.5(0,0,15,24,5)T0(-,-2-2-1/2-1124.51525z()0例7：目标函数的右端的常数项含有参数的线性规划问题。分析值变化时，下述参数线性规划问题最优解的变化。max z()=2x1+x2 x1+x210+2 2x1+4x224- 3x1+x218+ x1,x20(1)