第四节对偶问题的经济学解释——影子价格一、对偶最优解的经济解释：资源的影子价格标准化1、yi的数学含义在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN?CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?设B是｛maxz=CX｜AX≤b，X≥0｝的最优基，由强对偶定理可知z=CBB-1b=Yb=w对z求偏导数，得由上式可知，变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。cj23000qiCBXBbx1x2x3x4x52x104101/400x5040-21/213x2120-1/801/2sj000-3/2-1/8第2章中例1的影价格及其经济解释标准化第2章中例1的影价格及其经济解释。由表2-5可知cj23000θCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1=1.5，y2=0.125，y3=0。第2章中例1的影价格及其经济解释。这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由①移至①′，相应的最优解由(4，2)变为(4，2.5)，目标函数z=2×4+3×2.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由②移至②′，相应的最优解从(4，2)变为(4.25，1.875)，目标函数z=２×4.25+3×1.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由③移至③′，这时的最优解不变。第2章中例1的影价格及其经济解释。清华大学出版社yi的值代表对第i种资源的估价——影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。Q(4,2.5)Z=15.5Q(4.25,1.875)Z=14.125Q(4,2)Q(4,2)Z=14x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。4x1=1644x2=123x1+2x2=8Z=1408x142、yi的经济学含义(1)对偶问题的最优解——买主的最低出价。(2)原问题资源的影子价格——当该资源增加1单位时引起的总收入的增量——卖主的内控价格。(3)代表在资源最优利用条件下对单位第i种资源的估价，这种估价不是资源的市场价格，而是根据资源在最优生产配置中作出的贡献而作的估价，为区别起见，称为影子价格（shadowprice)。资源影子价格≠资源市场价格资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。即：市场价格由市场确定；影子价格由生产企业确定。(4)影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。(5)影子价格是一种边际价格。(6)资源的影子价格实际上又是一种机会成本。在完全市场经济条件下,当：资源的市场价格<影子价格，应买进这种资源资源的市场价格>影子价格，应卖出这种资源随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。3、影子价格在企业管理中的作用(1)告诉管理者增加何种资源对企业更有利；(2)告诉管理者花多大代价购买进资源或卖出资源是合适的；(3)为新产品定价提供依据。四、互补松弛定理的经济解释这表明在利润最大化的生产计划中，如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕，反映了资源的稀缺性。由此总结：(1)影子价格大于0的资源没有剩余；(2)有剩余的资源影子价格等于0；典型示例分析：X＝(4,2,0,0,4)T对偶Y＝(3/2,1/8,0,0,0)T第五节对偶单纯形法一、基本思想由单纯形法的原理可知：在用单纯形法求解LP问题时，PP没有得到最优解之前，每迭代一步得到一个基可行解，此时DP得到的是一个基解；而当PP得到最优解时，DP才得到一个基可行解。根据强对偶定理，DP得到的这个基可行解一定是DP的最优解。根据对偶问题的对称性，也可始终保持DP为基可行解，PP从基解开始迭代，当PP得到基可行解时，表明PP和DP都得到最优解。为了始终保持DP为基可行解，对于最大化的PP问题，其检验数必须保持非正；对于最小化的PP问题，其检验数必须保持非负。由于PP可以从基解开始迭代，因此PP约束条件的右端常数项可以为非正。若b中存在负数（非正）时，尽管可以使用人工变量法进行求解，但会使问题变得复杂，因此可以使用对偶单纯形法进行求解。二、步骤(以最大化为例):建初始表N选出换出和换入变量进行运算Y结束用对偶单纯形法求解下列LP问题解：原问题变形为例11-1-2-3000b0-4-11-1100081120100-20-110010-1-2-3000-1-2-3000b-141-11-100040211100-20-1100140-3-2-100-1-2-3000b-16100-10-100003112-2201-100-11000-5-10-3注意：对偶单纯形法不可理解成是求解对偶问题的单纯形法，而是根据对偶理论，允许原问题从初始非可行基开始迭代求解原问题的单纯形法。三、几个问题的讨论第7节?灵敏度分析以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。第7节?灵敏度分析显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按下表中的几种情况进行处理。7.1资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB′=B-1(b+Δb)这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。7.1资源数量变化的分析新的最优解的值可允许变化范围用以下方法确定。7.1资源数量变化的分析新的最优解的值可允许变化范围用以下方法确定。7.1资源数量变化的分析例如求第1章例1中第二个约束条件b2的变化范围。解：可以利用第1章例1的最终计算表中的数据：7.1资源数量变化的分析可计算Δb2：由上式，可得Δb2≥?4/0.25=?16，Δb2≥?4/0.5=?8，b2≤2/0.125=16。所以Δb2的变化范围是［?8，16］；显然原b2=16，加它的变化范围后，b2的变化范围是［8，32］。7.1资源数量变化的分析例7从表2-5得知第2章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品Ⅰ，Ⅱ。求这时该厂生产产品Ⅰ，Ⅱ的最优方案。解：先计算B-1Δb,将结果反映到最终表1-5中，得表2-10。7.1资源数量变化的分析由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。即该厂最优生产方案应改为生产4件产品Ⅰ，生产3件产品Ⅱ，获利z=4×2+3×3=17(元)从表2.11看出x3=2，即设备还有2小时未被利用。7.2标函数中价值系数cj的变化分析可以分别就cj是对应的非基变量和基变量两种情况来讨论。(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是σj=cj?CBB-1Pj或当cj变化Δcj后，要保证最终表中这个检验数仍小于或等于零，即σj’=cj?CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必须小于或等于YPj?cj，才可以满足原最优解条件。这就可以确定Δcj的范围了。7.2标函数中价值系数cj的变化分析可以分别就cj是对应的非基变量和基变量两种情况来讨论。(2)若cr是基变量xr的系数。因cr∈CB，当cr变化Δcr时，就引起CB的变化，这时(CB+ΔCB)B-1A=CBB-1A+(0，…，Δcr，…，0)B-1A=CBB-1A+Δcr(αr1,αr2,…，αrn)可见，当cr变化Δcr后，最终表中的检验数是σj′=cj?CBB-1A?Δcrrj，j=1,2,…，n若要求原最优解不变，即必须满足σj′≤0。于是得到7.2标函数中价值系数cj的变化分析Δcr可变化的范围是清华大学出版社7.2标函数中价值系数cj的变化分析例8试以第1章例1的最终表表1-5为例。设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。解：这时表1-5最终计算表便成为表2-12所示。7.2标函数中价值系数cj的变化分析若保持原最优解，从表2-12的检验数行可见应有由此可得Δc2≥?3和Δc2≤1。Δc2的变化范围为?3≤Δc2≤1即x2的价值系数c2可以在［0，4］之间变化，而不影响原最优解。7.3技术系数αij的变化例9分析在原计划中是否应该安排一种新产品。以第1章例1为例。设该厂除了生产产品Ⅰ，Ⅱ外，现有一种新产品III。已知生产产品III，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。问该厂是否应生产该产品和生产多少?解：分析该问题的步骤是：(1)设生产产品III为x3′台，其技术系数向量P3′=(2,6,3)T，然后计算最终表中对应x3′的检验数σ3′=c3′?CBＢ-1Ｐ3′=5?(1.5,0.125,0)(2,6,3)T=1.25＞0说明安排生产产品III是有利的。7.3技术系数αij的变化由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。7.3技术系数αij的变化(3)将x3′作为换入变量，x5作为换出变量，进行迭代，求出最优解。计算结果见表3-13(b)，这时得最优解：x1=1,x2=1.5，x3′=2。总的利润为16.5元。比原计划增加了2.5元。7.3技术系数αij的变化例10分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?解：把改进工艺结构的产品Ⅰ看作产品Ⅰ′，设x1′为其产量。于是在原计算的最终表中以x1′代替x1，计算对应x1′的列向量。同时计算出x1′的检验数为c1′?CBB-1P1′=4?(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1′的列向量位置，得表3-14。7.3技术系数αij的变化可见x1′为换入变量，x1为换出变量，经过迭代。得到表3-157.3技术系数αij的变化表3-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品Ⅰ′，3.2单位；生产产品Ⅱ，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。7.3技术系数αij的变化例11假设例10的产品Ⅰ′的技术系数向量变为P1′=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案?解：方法与例10相同，以x1′代替x1，并计算列向量x1′的检验数为c1′?CBB-1P1′=4?（1.5,0.125,0)(4,5,2)T=?2.625。将这些数字填入最终表2-15的x1列的位置，得到表3-16。7.3技术系数αij的变化将表2-16的x1′变换为基变量，替换x1，得表3-17。7.3技术系数αij的变化从表3-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表3-17中x2所在行，用方程表示时为0x1′+x2+0.5x3?0.4x4+0x5=?2.4引入人工变量x6后，便为?x2?0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表3-17，得到表3-18。7.3技术系数αij的变化这时可按单纯形法求解。x4为换入变量，x6为换出变量。经基变换运算后，得到表3-19的上表。在表3-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表3-19的下表。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品Ⅰ′，0.667单位；产品Ⅱ，2.667单位，可得最大利润10.67元。7.3技术系数αij的变化第8节参数线性规划灵敏度分析主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。参数线性规划研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：第8节参数线性规划(1)对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解；(2)用灵敏度分析法，将参变量t直接反映到最终表中；(3)当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若在b列首先出现某负值时，则以它对应的变量为换出变量；于是用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代一步；(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。8.1参数c的变化例12试分析以下参数线性规划问题。当参数t≥0时的最优解变化。解：将此模型化为标准型清华大学出版社8.1参数c的变化令t=0，用单纯形法求解的结果，见表2-20。将c的变化直接反映到最终表2-20中，得表2-21。计算t的变化范围清华大学出版社8.1参数c的变化当t值变化，在σ4≤0，即0≤t≤9/7时，为最优解(2,6,2,0,0)T；当t值增大，t≥(3/2)/(7/6)=9/7时，在检验数行首先出现σ4≥0；表示还可以继续改进。t=9/7为第一临界点。当t＞9/7时，σ4＞0，这时x4作为换入变量。用单纯形法迭代一步，得表2-22。清华大学出版社8.1参数c的变化当t继续增大t≥(5/2)/(1/2)=5时，在检验数行首先出现σ5≥0，在σ5≤0，即9/7≤t≤5时，得最优解(4,3,0,6,0)T。t=5为第二临界点。当t＞5时，σ5＞0，这时x5作为换入变量，用单纯形法迭代一步，得表2-23。t继续增大时，在检验数行恒有σ2，σ3＜0，故当t≥5时，最优解为(4，0，0，12，6)T。清华大学出版社8.2参数b的变化分析例13分析以下线性规划问题，当t≥0时，其最优解的变化范围。解将上述模型化为标准型清华大学出版社8.2参数b的变化分析令t=0，用单纯形法迭代两次，求解的结果，见表2-24。将此计算结果反映到最终表2-24，得表2-25。清华大学出版社8.2参数b的变化分析在表2-25中进行分析，当t增大至t≥2时，则b≤0；即0≤t≤2时，最优解为(2?t,4,0,0)T。当t＞2时，则b1＜0；故将x1作为换出变量，用对偶单纯形法迭代一步，得表2-26从表2-26可见，当t＞6时，问题无可行解；当2≤t≤6时，问题的最优解为(0，6?t，0，?6+3t)T。原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 表中的解仍为最优解 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单纯形法继续迭代求最优解 非可行解 非可行解 引进人工变量，编制新的单纯形表，求最优解
在最终表中求得的经过变化后的b列的所有元素，
要求i+irΔbr≥0，i=1,2,…,m。由此可得
irΔbr≥-i，i=1,2，…，m
当ir＞0时，Δbr≥-i/ir；
当ir＜0时，Δbr≤-i/ir；于是得到
cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 2 x1 4 1 0 1 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 -z -14 0 0 -3/2 -1/8 0
cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2
0
3 x1
x5
x2 4+0
4-8
2+2 1
0
0 0
0
1 0
[-2]
0.5 0.25
0.5
–0.125 0
1
0 cj-zj 0 0 -1.5 -0.125 0
cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2
0
3 x1
x3
x2 4
2
3 1
0
0 0
0
1 0
1
0 0.25
-0.25
0 0
-0.5
0.25 cj-zj 0 0 0 -0.5 -0.75
cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2
0
3+Δc2 x1
x5
x2 4
4
2 1
0
0 0
0
1 0
-2
0.5 0.25
0.5
–0.125 0
1
0 cj-zj 0 0 -1.5-Δc2/2 Δc2/8-1/8 0
(2)计算产品Ⅲ在最终表中对应x3′的列向量
并将(1)，(2)中的计算结果填入最终计算表2-5，得表3-13(a)。
cj→ 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x5’ 2
0
3 x1
x5
x2 4
4
2 1
0
0 0
0
1 0
2
0.5 0.25
0.5
–0.125 0
1
0 1.5
[2]
0.25 cj-zj 0 0 -1.5 -0.125 0 1.25
cj→ 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x5’ 2
0
3 x1
x3’
x2 1
2
1.5 1
0
0 0
0
1 1.5
-1
0.75 -0.125
0.25
–0.1875 -0.75
0.5
-0.125 0
1
0 cj-zj 0 0 -0.25 -0.4375 -0.625 0
cj→ 4 3 0 0 0 CB XB b x1’ x2 x3 x4 x5 2
0
3 x1
x5
x2 4
4
2 1.25
0.5
0.375 0
0
1 0
-2
0.5 0.25
0.5
–0.125 0
1
0 cj-zj 0.375 0 -1.5 -0.125 0
cj→ 4 3 0 0 0 CB XB b x1’ x2 x3 x4 x5 4
0
3 x1’
x5
x2 3.2
2.4
0.8 1
0
0 0
0
1 0
-2
0.5 0.2
0.4
–0.2 0
1
0 cj-zj 0 0 -1.5 -0.2 0
cj→ 4 3 0 0 0 CB XB b x1’ x2 x3 x4 x5 2
0
3 x1
x5
x2 4
4
2 1.25
-3.5
1.375 0
0
1 0
-2
0.5 0.25
0.5
–0.125 0
1
0 cj-zj -2.625 0 -1.5 -0.125 0
cj→ 2 3 0 0 0 CB XB b x1’ x2 x3 x4 x5 4
0
3 x1’
x5
x2 3.2
15.2
-2.4 1
0
0 0
0
1 0
-2
0.5 0.2
1.2
–0.4 0
1
0 cj-zj 0 0 -1.5 0.4 0
cj→ 4 3 0 0 0 -M CB XB b x1’ x2 x3 x4 x5 X6 4
0
-M x1’
x5
x6 3.2
15.2
2.4 1
0
0 0
0
1 0
-2
0.5 0.2
1.2
–0.4 0
1
0 0
0
1 cj-zj 0 3-M -0.5M -0.8+0.4M 0 0
cj→ 4 3 0 0 0 -M CB XB b x1’ x2 x3 x4 x5 X6 4
0
0 x1’
x5
x4 2
8
6 1
0
0 0.5
[3]
1 0.25
-0.5
-1.25 0
0
1 0
1
0 0.5
-3
2.5 cj-zj 0 1 -1 0 -M+2 4
3
0 x1’
x2
x4 0.667
12.667
12.667 1
0
0 0
0
1 0
-2
0.5 0
0
1 -0.33
0.33
0.83 0
-1
0 cj-zj 0 3-M -0.5M 0 -0.33 -M+3
cj→ 3 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0
5
3 x3
x2
x1 2
6
2 0
0
1 0
1
0 1
0
0 1/3
1/2
–1/3 -1/3
0
1/3 cj-zj 0 0 0 -3/2 -1
cj→ 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0
5-t
3+2t x3
x2
x1 2
6
2 0
0
1 0
1
0 1
0
0 1/3
1/2
–1/3 -1/3
0
1/3 cj-zj 0 0 0 -(3/2)+(7/6)t -1-(2/3)t
cj→ 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0
5-t
3+2t x4
x2
x1 6
3
4 0
0
1 0
1
0 3
-3/2
1 1
0
0 -1
1/2
0 cj-zj 0 0 (9/2)-(7/2)t 0 -(5/2)+(1/2)t
cj→ 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0
0
3+2t x4
x5
x1 12
6
4 0
0
1 2
2
0 0
-3
1 1
0
0 0
1
0 cj-zj 0 5-t -3-2t 0 0
cj→ 1 3 0 0 CB XB b x1 x2 x3 x4 1
3 x1
x2 2
4 1
0 0
1 2/3
1/3 -1/3
1/3 cj-zj 0 0 -5/3 -2/3
cj→ 1 3 0 0 CB XB b x1 x2 x3 x4 1
3 x1
x2 2-t
4 1
0 0
1 2/3
1/3 -1/3
1/3 cj-zj 0 0 -5/3 -2/3
然后计算
cj→ 1 3 0 0 CB XB b x1 x2 x3 x4 0
3 x1
x2 -6+3t
6-t -3
1 0
1 -2
1 1
0 cj-zj -2 0 -3 0
|
|
