运筹学第2章2：线性规划的对偶理论及其应用

©管理与人文学院忻展红1999，42.4灵敏度分析灵敏度分析又称为后优化分析22.4线性规划的灵敏度分析•线性规划是静态模型•参数发生变化，原问题的最优解还是不是最优•哪些参数容易发生变化–C,b,A•每个参数发生多大的变化不会破坏最优解•灵敏度越小，解的稳定性越好32.4.1边际值(影子价)qi•以(max,)为例•边际值(影子价)qi是指在最优解的基础上，当第i个约束行的右端项bi减少一个单位时，目标函数的变化量miijimiiji1Bj1Bjininii1Bin1Bini1Biimkkk1B1BaqaBCPBCzzzqBCPBCzBCbxfqbBCbBCxf111)(,)(,)()()()(式机会成本的另外表达形剩余变量人工变量松弛变量因此机会成本左导数4例2.4.2x1x2x3x4x5x6x7CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-15关于影子价的一些说明•影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关•松弛变量增加一个单位等于资源减少一个单位•剩余变量增加一个单位等于资源增加一个单位•资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为0•影子价为0，资源并不一定有剩余•应用，邮电产品的影子价格0YXYAIYCΔΔΔ)(Δmax162.4.2价值系数cj的灵敏度分析•cj变动可能由于市场价格的波动，或生产成本的变动•cj的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj允许的变动范围cj•cj的变化会引起检验数的变化，有两种情况–非基变量对应的价值系数变化，不影响其它检验数–基变量对应的价值系数变化，影响所有非基变量检验数1、非基变量对应的价值系数的灵敏度分析)(0)(jjjjjjzcczcc故有要保持7例2.4.2x1x2x3x4x5x6x7CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-175.5,75.225.4,25.3,331131ccccxx所以为非基变量82、基变量对应的价值系数的灵敏度分析•由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数•只有一个基变量的cj发生变化，变化量为cj•令cj在CB中的第k行，研究非基变量xj机会成本的变化0min0max,'kjkjjjjjkjkjjjjaazccaazc有验数仍满足最优条件为保证所有非基变量检9设x4的价值系数增加c4，对应k=2，•有一边为空集如何处理•为什么akj=0不出现在任何一边的集合中•与对偶单纯型法找入变量的公式一样x1x2x3x4x5x6x7CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-1102.4.3右端项bi的灵敏度分析•设XB=B1b是最优解，则有XB=B1b0•b的变化不会影响检验数•b的变化量b可能导致原最优解变为非可行解112.4.3右端项bi的灵敏度分析12以b2为例,x6是对应的初始基变量，所以有132.4.4技术系数aij的灵敏度分析•技术系数aij变化的影响比较复杂–对应基变量的aij，且资源bi已全部用完–对应基变量的aij，但资源bi未用完–对应非基变量的aij，且资源bi全用完或未用完1、对应基变量的aij，且资源bi已全部用完aij=02、对应基变量的aij，但资源bi未用完aijxn+i/xj–上述两个公式不充分，为什么？–B–1发生变化，从而引起非基变量检验数cj–zj的变化3、对应非基变量的aij–只影响对应非基变量xj的检验数cj–zj–若aij0，不会破坏最优解–若aij0，必须保证cj–zj01415x1,x3为非基变量，q1=0,q2=0.25,q3=1,故有x2,x4为基变量，x5=100,b1有剩余，故有x1x2x3x4x5x6x7CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-1162.4.5新增决策变量的分析•例2.4.2中，若新增产品x8，问是否生产？–已知c8=9,a18=5,a28=4,a38=3–计算x8的检验数可知生产是否有利结论：生产x8有利。将B–1P8加入最优单纯型表中，以x8为入变量进行迭代172.4.6新增约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代–为什么可以利用对偶单纯型法例2.4.2第2步18x1x2x3x4x5x6x7x8CBXBb153400000x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100x8650123300010x51001/40-13/4011/4-104x420020-2(1)01-105x2100-3/4111/400-3/4100x84505/20-5/2301.5-210x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100x8-150-7/207/200-1.51119x1x2x3x4x5x6x7x8CBXBb153400000x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100x8-150-7/207/200(-1.5)1113004.2555.75400.2510cj-zj-3.250-2.7500-0.25-100x575-0.330-2.67010-0.830.174x4100-0.3300.33100-0.330.675x21751110000.5-0.50x61002.330-2.33001-0.67-0.6712753.6756.334001.170.17cj-zj-2.670-3.33000-1.17-0.17注意：最优解的目标函数减少了25个单位202.4.7灵敏度分析举例例2.4.3某工厂生产三种产品A,B,C，有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110个，求收益最大的生产方案。21例2.4.3解：设xj为已选定各种组合方案的组数(j=1,2,…,5)，x6为A产品的剩余变量，x7，x8分别为工人工时和机器工时的松弛变量。22例2.4.3•最优解的B–1是什么•产品A的影子价为多少•第II组方案的生产费用提高2元，是否要调整生产组别•若工人加班费为1元/小时，是否要采取加班措施•若通过租借机器增加工时，租费的上限应为多少•A产品的订购合同是否有利•若要选用第IV组方案，该组的生产费用应降低多少•若工人加班费为0.3元/小时，最多允许加班时间多少•若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)•若第III组方案使机器工时减少0.5小时，能否被选入232.5参数线性规划•2.4节中aij,bi,cj只有一个发生变化，多个同时发生变化则很难解析•但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析2.5.1参数cj的变化分析i第i种资源的单位费用变化量，i不限ii变化对cj的影响率24例2.4.2资源b1单价变化量1，价格影响率j=a1j25例2.4.2资源b1单价变化量1与c5262.5.2参数bi的变化分析•例2.4.2中，将b1,b2,b3理解为三个车间的周工时资源。假设从第2向1车间调动工人个，每个工人的周工时为40小时，问调动多少工人不会破坏最优产品组合