东北财经大学：《运筹学》课程教学资源（教案讲义）第二篇 线性规划 第三章 对偶理论

第三章对偶理论 §1对偶问题的提出 回顾对第一章§1例3营养问题 食物 各种营养的最 营养成分 n 低要求 bi 单价 的分析,得到如下形式的线性规划问题 AX≥b > 现在从另一个角度提出问题: 设有一个制造商,要生产m种不同的药丸来代替上述n种不同的食物,试问每种药丸 的价格如何确定,才能获利最大 仍可利用上面的表格,设第i种药丸的价格是w;,并记W=(w1,…,m)为了达到畅 销的目的,药丸的价格当然不宜超过与之相当的食物的价格,即应有WA≤C,于是问题变 成 MA≤C (DW≥0 I max wb 据此我们得到如下定义 1°、称(L)和(D所规定的线性规划问题是互为对偶问题。若其一叫原问题,则另一叫对 偶问题,也称它们构成一组对称的对偶规划 20、对于标准形的线性规划问题 AX= b (LX≥b CX 考虑 MA≤C (L)和(D)叫作一组非对称的对偶规划 以下证明,对称对偶规划与非对称对偶规划是可以互相推出的 由对称情形推出非对称情形

91 第三章 对偶理论 §1 对偶问题的提出 回顾对第一章§1 例 3 营养问题 食物 营养成分 x1 x2 xn 1 2 n 各种营养的最 低要求 w1 1 w2 2 ┇ wm m a11 a12 … a1n a21 a22 … a2n … … am1 am2 … amn b1 b2 ┇ bm 单价 C1 C2 … Cn 的分析，得到如下形式的线性规划问题：        CX X AX b L min ( ) 0 现在从另一个角度提出问题： 设有一个制造商，要生产 m 种不同的药丸来代替上述 n 种不同的食物，试问每种药丸 的价格如何确定，才能获利最大。 仍可利用上面的表格，设第 i 种药丸的价格是 wi ，并记 ( , , ) W = w1  wm 为了达到畅 销的目的，药丸的价格当然不宜超过与之相当的食物的价格，即应有 WA  C ，于是问题变 成        Wb W WA C D max ( ) 0 据此我们得到如下定义： 1 0、称(L)和(D)所规定的线性规划问题是互为对偶问题。若其一叫原问题，则另一叫对 偶问题，也称它们构成一组对称的对偶规划。 2 0、对于标准形的线性规划问题       =  CX X b AX b L min ( ) 考虑      Wb WA C D max ( ) (L) 和 (D) 叫作一组非对称的对偶规划。 以下证明，对称对偶规划与非对称对偶规划是可以互相推出的。 由对称情形推出非对称情形

AX≤b 因AX=b AX≥b 故(L’)可变成 X≥0 min CX 此为(L)型按定义其对偶规划应为 (W1, C H,W2)20 max(WI, W2 W-W)A≤C (W1,W2)≥0 max(W1-W2)b 令W”=1-2,则W已无非负限制,从而上式变成 WA≤C max w b 这便是(D)的形式,说明(L)的对偶规划确为(D)。 反之,设(L)的对偶是(D),可证(L)的对偶是(D) 对(L)引入剩余变量y=(y,…,yn)≥0,将其化成标准形式: X≥0,y≥0 X min( C,0 从而其对偶问题具形式:

92 因      =  AX b AX b AX b 故 (L) 可变成:                   −          − CX X b b X A A min 0 此为(L)型,按定义其对偶规划应为                  −          − b b W W W W C A A W W max( , ) ( , ) 0 ( , ) 1 2 1 2 1 2 即      −  −  W W b W W W W A C max( ) ( , ) 0 ( ) 1 2 1 2 1 2 令 1 2 * W = w − w ，则 * W 已无非负限制，从而上式变成      W b W A C * * max 这便是 (D) 的形式，说明 (L) 的对偶规划确为 (D) 。 反之，设 (L) 的对偶是 (D) ，可证(L)的对偶是(D)。 对(L)引入剩余变量 ( , , ) 0, = 1  T m Y y  y 将其化成标准形式：                    =        − Y X C X Y b Y X A I min( ,0) 0, 0 ( , ) 从而其对偶问题具形式：

W(A,-D)≤(C,0) max wb 此即 W≥0 max Wb 它恰为D) 除此之外,还有将两种情形结合起来的混合型对偶规划,例如设 A A12 A21A2 其中A为mxn阶矩阵i=12。m+m2=mm1+n2=n,x,X2分别为n,n2维向量 若原问题为 A,X1+A,、X2≥b Ax+Ax2=b X≥0,X2无限制 min(C X+C x) 则它的对偶规划为 A2+W22=C2 1≥0,W2无限制 max(wb+wb) 综上,我们可以总结出构成一般对偶规划的规则如下: (i)把原问题的约束条件统一成≥及=(或≤及=),目标函数改写成求极小(或极大)。 (i)原问题的一个行约束对应一个变量w;,若行约束是不等式,则v1≥0,否则v无符 号限制。 (ⅲi)原问题每个变量x,对应一个行约束:若x,≥0, 则对应∑wn≤c(或∑wa≥c)若x无限制,则对应∑wan=c1(c,是原问 题目标函数x,的系数)。 (ⅳv)原目标函数CX若为求极小(极大),则对应目标函数Wb求极大(极小)(这里 b是原问题约束中的常数项列) 例1原问题

93    −  Wb W A I C max ( , ) ( ,0) 此即        Wb W WA C max 0 它恰为(D)。 除此之外，还有将两种情形结合起来的混合型对偶规划，例如设         =         = 2 1 21 22 11 12 , x x X A A A A A 其中 Aij 为 mi  n j 阶矩阵 i,j=1,2。m1 + m2 = m,n1 + n2 = n， 1 2 X , X 分别为 1 2 n ,n 维向量。 若原问题为        +  + = +  min( ) 0, 1 1 2 2 1 2 2 2 22 1 21 2 1 12 1 11 C X C X X X A X A X b A X A X b 无限制 则它的对偶规划为        +  + = +  max( ) 0, 1 1 2 2 1 2 2 22 2 12 1 1 21 2 11 1 W b W b W W W A W A C W A W A C 无限制 综上，我们可以总结出构成一般对偶规划的规则如下： （ⅰ）把原问题的约束条件统一成  及=（或  及=），目标函数改写成求极小（或极大）。 （ⅱ）原问题的一个行约束对应一个变量 wi ，若行约束是不等式，则 wi  0 ，否则 wi 无符 号限制。 （ⅲ）原问题每个变量 j x 对应一个行约束：若 x j  0 ， 则对应 ij j m i i w a  c =1 （或 ij j m i i w a  c =1 ），若 j x 无限制，则对应 ij j m i i w a = c =1 （ j c 是原问 题目标函数 j x 的系数）。 （ⅳ）原目标函数 CX 若为求极小（极大），则对应目标函数 Wb 求极大（极小）（这里 b 是原问题约束中的常数项列）。 例 1 原问题

6x1-3x2 x4 28x1-17x,+4x3+2x4≤-3 x1≥0, 0 无限制 mn5x1-6x2+7x3+4x4 把不等式统一成≥,再列成下表: 4=fmin x1≥0,x,≥0,x2,x4无限制 据此可直接写出对偶规划 1+6,+283≤5 2w1-32+17v3≤-6 7 W1无限制,w2,w3≥0 max-7w1+14w2+3 §2对偶定理 对于原问题和它的对偶问题的关系有以下几个定理,它们在理论和应用中都是很重要 定理1(L)和(D),(L)和(D)同时有最优解的充要条件是同时有可行解 证明只需证充分性,设(L)和(D)分别有可行解X和W°,既有 AX0≥b,X°≥0,W°A≤C,W0≥0。于是对(L)的任一可行解X,有 CX≥W0AX≥W"b 即CX在可行解集合有下界W%b,从而在基可行解的集合上有下界,由于基可行解是有限 的故必于某点X·达到其下界,再根据X的典式。其检验数λ,或者全小于等于0,或者经 过若干次迭代后,变得小于等于0,但目标函数值仍为CX”,从而由单纯法的理论,知X 即为最优解,这便证明了(L)有最优解 同样对D的任一可行解集W,有

94          − + +   − − + +  − − + −  + − − = − 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 min 5 6 7 4 0, 0, , 28 17 4 2 3 6 3 7 14 2 7 x x x x x x x x x x x x x x x x x x x x 无限制 把不等式统一成  ，再列成下表： x1 x2 x3 x4 w1 w2 w3 1 2 -1 -1=-7 6 -3 1 -7  14 28 17 -4 -2  3 5 -6 7 4 = f min 1 2 3 4 x  0, x  0, x , x 无限制 据此可直接写出对偶规划：            − + +  − − − = − + − = − +  − + +  1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 max 7 14 3 , , 0 7 2 4 4 7 2 3 17 6 6 28 5 w w w w w w w w w w w w w w w w w w 无限制 §2 对偶定理 对于原问题和它的对偶问题的关系有以下几个定理，它们在理论和应用中都是很重要 的。 定理 1 （L）和（D）， (L) 和 (D) 同时有最优解的充要条件是同时有可行解。 证 明 只 需 证 充 分 性 ， 设 （ L ）和（ D ） 分 别 有 可 行 解 0 0 X 和W ，既有 , 0; , 0 0 0 0 0 AX  b X  W A  C W  。于是对（L）的任一可行解 X，有 CX W AX W b 0 0   即 CX 在可行解集合有下界 W b 0 ，从而在基可行解的集合上有下界，由于基可行解是有限 的故必于某点 * X 达到其下界，再根据 * X 的典式。其检验数  j 或者全小于等于 0，或者经 过若干次迭代后，变得小于等于 0，但目标函数值仍为  CX ，从而由单纯法的理论，知  X 即为最优解，这便证明了（L）有最优解。 同样对 D 的任一可行解集 W，有

Wb≤WAX0≤CX0 故Wb在可行解集合有上界CX°,从而类似可证(D)有最优解。 推论若X0和W0分别是(L)和(D)的可行解,且CX0=W°b,则它们分别是(L) 和(D)的最优解 同理可证结论对(L)和(D)成立 CF≥W0AX=W%b Wb=WAX0≤CX0 定理2设(L)和(D)(或(L)和(D))中一个有最优解,则另一个也一定有最优解, 且目标函数值相同。 证明设(L)有最优解,引入剩余变量Y则(L)可化为标准形式 (A,-1 X≥0,y≥0 X min( C,o) 运用单纯形法可求得最优解X°,X0是基可行解,对应于某一基B,据最优判别准则有 CB-(A-1)≤(C0) 令W0=CB-,上式可变成 WA≤C W0≥0 故W0是(D)的可行解,又因 Wb=CB-b=C XD=C 故由定理1的推论知W是(D)的最优解,且 min CX=w b= max wb 反之,设(D)有最优解,将(D)化成标准形式:

95 0 0 Wb  WAX  CX 故 Wb 在可行解集合有上界 0 CX ，从而类似可证（D）有最优解。 推论 若 0 X 和 0 W 分别是（L）和（D）的可行解，且 CX W b 0 0 = ，则它们分别是（L） 和（D）的最优解。 同理可证结论对 (L) 和 (D) 成立： 0 0 0 0 Wb WAX CX CX W AX W b =   = 定理 2 设（L）和（D）（或 (L) 和 (D) ）中一个有最优解，则另一个也一定有最优解， 且目标函数值相同。 证明 设（L）有最优解，引入剩余变量 Y 则（L）可化为标准形式：                    =        − Y X C X Y b Y X A I min( ,0) 0, 0 ( , ) 运用单纯形法可求得最优解 0 X ， 0 X 是基可行解，对应于某一基 B，据最优判别准则有 ( , ) ( ,0) 1 CB B A −I  C − 令 0 −1 W = CB B ，上式可变成 0 0 0   W W A C 故 0 W 是（D）的可行解，又因 0 1 0 0 W b = CB B b = CB XB = CX − 故由定理 1 的推论知 0 W 是（D）的最优解,且 min CX W b max Wb 0 = = 反之，设（D）有最优解，将（D）化成标准形式：

W≥0,y7≥0 min(-b, 0) 仿上可类似证明(L)有最优解。 从证明中易见。以上结论对(L)和(D)亦成立。 综上,互为对偶规划的解之间的联系,不外乎以下三种情况 两个规划都有最优解 20两个规划都没有可行解 3°一个规划有可行解,但目标函数在可行解集上无界,而另一个规划无可行解 此外由定理2的证明知,若B是(L)的最优基,则单纯形乘子x=CBB便是(D)的 最优解,于是从原问题(L)的最终单纯形表中可以直接得到对偶问题(D)的解。实际上 假如在原始阵A中有一个mxm阶的单位阵1,则在最后的表中,矩阵B出现在开始时为单 位阵I的地方,同时B-下面m个检验数为CBB--C1,这样从最后一行中对应的这些元 素与C,的对应分量相加,就获得了对偶问题的最优解W=CB-1。 定理3松紧定理 (i)、考虑非对称的对偶规划(L′)和(D’),设X和W0分别是它们的可行解, 则它们分别是(L′)和(D′)的最优解的充要条件是 (CWA)ⅹ0=0 证明由定理1和2知,可行解X0和W0为最优解的充要条件是 (Cw0A)x0=0 因Ⅹ≥0,C-WA≥0,故(1)式等价于

96         −   =         T T T T T T T T T Y W b W Y C Y W A I min( ,0) 0, 0 ( , ) 仿上可类似证明(L)有最优解。 从证明中易见。以上结论对（L ' ）和（D ' ）亦成立。 综上，互为对偶规划的解之间的联系，不外乎以下三种情况： 1 0 两个规划都有最优解。 2 0 两个规划都没有可行解。 3 0 一个规划有可行解，但目标函数在可行解集上无界，而另一个规划无可行解。 此外由定理 2 的证明知，若 B 是（L）的最优基，则单纯形乘子 −1  = CB B 便是（D）的 最优解，于是从原问题（L）的最终单纯形表中可以直接得到对偶问题（D）的解。实际上， 假如在原始阵 A 中有一个 m  m 阶的单位阵 I,则在最后的表中，矩阵 B −1 出现在开始时为单 位阵 I 的地方，同时 B −1 下面 m 个检验数为 C B B − CI −1 ,这样从最后一行中对应的这些元 素与 C I 的对应分量相加，就获得了对偶问题的最优解 W=C −1 B B 。 定理 3 松紧定理 （ⅰ）、考虑非对称的对偶规划（L′）和（D′）,设 X 0 和 W 0 分别是它们的可行解， 则它们分别是（L′）和（D′）的最优解的充要条件是 （C-W 0 A）X 0 =0 (1) 证明 由定理 1 和 2 知，可行解 X 0 和 W 0 为最优解的充要条件是 CX 0 = W 0 b= W 0 A X 0 即 （C-W 0 A）X 0 =0 因 X 0  0，C- W 0 A  0,故（1）式等价于

(C,-W°p,)X0=0 P 由此可得结论: 1°、若(L′)有最优解X,使得对指标满足x>0(称为j对(L)是松的) 则对(D′)的一切最优解w,必有WP,=C,(称为j对(D′)是紧的) 2、若(D)有最优解W°,使对指标j,满足W°P,<C,(称j对(D′)是松的 则对(L′)的一切最优解X,必有x=0(称j对(L′)是紧的)。 (ⅱ)、考虑对称对偶规划(D)和(L),设X和W°分别是(D)和(L)的可行解 则它们同时也是最优解的充要条件为 (C-WA)X0=0 证明将对称形式(L)、(D)转化为非对称形式(L)和(D′) (A0 (L′)X≥0,y≥0 ∫W(4-D)≤(C0) max wb nin( c 由以上(i)的结论知, F0/和W0分别为(L)和(D)的最优解的充要条件 是 IC,0)-w(A- (C-WA,w D 由此得 (C-W AX=0 0=Wo(AX0-b)=0 故定理得证

97 （C j W p j 0 − ）X 0 j =0,j=1、……、n 由此可得结论： 1 0 、若（L′）有最优解 X 0 ,使得对指标 j,满足 X 0 j >0 （称为 j 对（L′）是松的）, 则对（D′）的一切最优解 w，必有 WP j =C j (称为 j 对（D′）是紧的)。 2 0 、若（D′）有最优解 W 0 ，使对指标 j，满足 W 0 P j  C j (称 j 对（D′）是松的)， 则对（L′）的一切最优解 X，必有 X j =0（称 j 对（L′）是紧的）。 （ⅱ）、考虑对称对偶规划（D）和（L）,设 X 0 和 W 0 分别是（D）和（L）的可行解， 则它们同时也是最优解的充要条件为     − = − = ( ) 0 ( ) 0 0 0 0 0 W AX b C W A X (2) 证明 将对称形式（L）、（D）转化为非对称形式（L′）和（D′） （L′）                    =        − Y X C X Y b Y X A I min( ,0) 0, 0 ( ) 0 （D′）    −  Wb W A I C max ( , ) ( ,0) 由以上（ⅰ）的结论知，         0 0 Y X 和 0 W 分别为（L′）和（D′）的最优解的充要条件 是 [( ,0) ( , )] 0 0 0 0 =         − − Y X C W A I 即 ( , ) 0 0 0 0 0 =         − Y X C W A W I 由此得 ( ) 0 0 0 C −W A X = ( ) 0 0 0 0 0 W Y = W AX − b = 故定理得证

若记A=(P,…,P)=:(a表示A的标号为i的行向量,则对称松紧关系(2) 可表为 、若x>0,则WP=C,(=1,2,…,m) 2若WP0,则a1x=b(=1,…,m) 49若a,X0>b,则v9=0 以上的对偶定理对于混合型的对偶规划同样成立 对偶理论应用很广,如 (一)、已知对偶问题的最优解,求原问题的最优解。反之一样。 (二)、检验最优解性质的某些假说,例如在最优解处,原始的约束条件是否都是严 格的不等式 对偶定理及松紧定理有明显的经济解释。它指出,对于资源利用问题(D),利用资源生 产产品与转让(出售)资源这两种作法在理论上具有同等效益(cx°=bv°)。其次,当 °p(c时,表明按最优生产方案w进行操作时,第i种资源消耗不尽,尚有剩余,因此, 再增加这种资源不会增加目标函数值,从这个意义上讲,该资源的价值x1=0。再有,当 a1x>b1时,表明生产产品i要消耗的资源的价值高于该产品的价格,明智之举是不生产 它,这也就是v=0 §3关于影子价格的讨论 先给出影子价格的定义,考虑资源最优利用问题的线性规划模型: A, I)I b AX≤b x≥0→X≥0,Y≥0 max CX mn(-C, 0 设下表是该问题的最优单纯形表(4): , x y y

98 若记           = = m n a a A P  P  1 1 ( , , ) ( i a 表示 A 的标号为 i 的行向量)，则对称松紧关系（2） 可表为： 0 1 、若 0 0 x j  ，则 W Pj = Cj 0 ( j = 1,2,  ,n) 0 2 若 W Pj  Cj 0 ，则 0 0 x j = 0 3 若 0 0 wi  ，则 ( 1, , ) 0 ai X = bi i =  m 0 4 若 ai X  bi 0 ，则 0 0 wi = 以上的对偶定理对于混合型的对偶规划同样成立。 对偶理论应用很广，如 （一）、已知对偶问题的最优解，求原问题的最优解。反之一样。 （二）、检验最优解性质的某些假说，例如在最优解处，原始的约束条件是否都是严 格的不等式。 对偶定理及松紧定理有明显的经济解释。它指出，对于资源利用问题（D）,利用资源生 产产品与转让（出售）资源这两种作法在理论上具有同等效益（ 0 0 c x b w T T = ）。其次，当 i i w p〈c 0 时，表明按最优生产方案 0 w 进行操作时，第 i 种资源消耗不尽，尚有剩余，因此， 再增加这种资源不会增加目标函数值，从这个意义上讲，该资源的价值 0 0 xi = 。再有，当 i bi a x  0 时，表明生产产品 i 要消耗的资源的价值高于该产品的价格，明智之举是不生产 它，这也就是 wi 0 = 0。 §3 关于影子价格的讨论 先给出影子价格的定义，考虑资源最优利用问题的线性规划模型：                  −   =                Y X C X Y b Y X A I CX X AX b min( ,0) 0, 0 ( , ) max 0 (3) 设下表是该问题的最优单纯形表（4）： 1 x 2 x … n x 1 y 2 y … m y

B-b (CRB A-C) CB 则根据对偶定理W°=CBB-1=(w,v2,…,v),便是对偶问题的最优解。并且有 F(b)=maxf=b,w1+b,w2+.+bw (5) aF(b) ab 由上式可以看出第1种资源增加一个单位时,最大产值f将增加w资源的这种价值v 称为边际价值,亦称为资源的影子价格可见线性规划问题(3)中,资源的影子价格就是其 对偶问题的最优解。它们是最优单纯形表(4)中,后m个检验数的相反数 影子价格在经济上有着重要的意义。供不应求的资源称为短线资源。这时其影子价格 大于O,反之亦然供大于求的资源称为长线资源。其影子价格等于0,反之亦然。因此可据 影子价格来判断某种资源是长线还是短线资源。 影子价格可指导资源管理部门对稀缺资源实行择优分配,资源的影子价格与资源的进 价之差越大,获利越多,资源利用效果也就越好;反之当影子价格低于资源进价时,分配(如 贷款)则是不可取的。此时,从经济上考虑,非但不宜购入反而应卖出,可见即使是短线资 源也不是不加分析地一律购入的 影子价格还用于价格预测,甲厂的产品是乙厂的资源,则在单一情形,产品的价格应 在成本与影子价格之间,否则价格将处于诸厂影子价格中的最大值与最小值之间,这体现出 经济结构的优劣对竞争力的具大影响。 研究结果表明,影子价格是相应资源量b的减函数,对于线性问题(3),这个諴函 数是分段阶梯函数。在每段内它等于常数,即对偶最优解的相应分量,这时对偶最优解ν是 唯一的,而且(5),(6)成立。但在两台阶的衔接处,函数必有间断,说明在此处对偶最优 解不唯一,这时的相应资源量称为临界值,用b表示,那么当资源量取临界值时,如何认识 和确定它的影子价格呢? 事实上,假定当bb时为vP),则由函数的递减性和阶梯 性,必有w>w(3,这时对临界值,若取v=1则目标值f将增加v{2),若取vb=-1则将 减少w,故增与减的值不等,这正是它与通常情形区别之所在。再看目标函数f,它实际 上是资源量b的连续分段线性函数,该函数在临界处虽说连续,且左右导数均存在 0ff=2却不相等,这就是说对临界值b(6)不成立。这时宜补充定义如下

99 B A −1 −1 B B b −1 ( ) 1 − CB B A−C − −1 −CB B -max f (4) 则根据对偶定理 ( , , , ) 0 0 2 0 1 0 1 W = CB B = w w  wm − ，便是对偶问题的最优解。并且有 0 0 2 2 0 max 1 1 ( ) b w b w bm wm F b = f = + ++ (5) w i m b F b i i , 1, , ( ) = 0 =    (6) 由上式可以看出，第 i 种资源增加一个单位时，最大产值 f 将增加 w 0 i .资源的这种价值 w 0 i ， 称为边际价值，亦称为资源的影子价格.可见线性规划问题（3）中，资源的影子价格就是其 对偶问题的最优解。它们是最优单纯形表（4）中，后 m 个检验数的相反数。 影子价格在经济上有着重要的意义。供不应求的资源称为短线资源。这时其影子价格 大于 O，反之亦然.供大于求的资源称为长线资源。其影子价格等于 0，反之亦然。因此可据 影子价格来判断某种资源是长线还是短线资源。 影子价格可指导资源管理部门对稀缺资源实行择优分配，资源的影子价格与资源的进 价之差越大，获利越多，资源利用效果也就越好；反之当影子价格低于资源进价时，分配（如 贷款）则是不可取的。此时，从经济上考虑，非但不宜购入反而应卖出，可见即使是短线资 源也不是不加分析地一律购入的。 影子价格还用于价格预测，甲厂的产品是乙厂的资源，则在单一情形，产品的价格应 在成本与影子价格之间，否则价格将处于诸厂影子价格中的最大值与最小值之间，这体现出 经济结构的优劣对竞争力的具大影响。 研究结果表明，影子价格 0 wi 是相应资源量 i b 的减函数，对于线性问题（3），这个减函 数是分段阶梯函数。在每段内它等于常数，即对偶最优解的相应分量，这时对偶最优解 0 w 是 唯一的，而且（5），（6）成立。但在两台阶的衔接处，函数必有间断，说明在此处对偶最优 解不唯一，这时的相应资源量称为临界值，用 i b ˆ 表示，那么当资源量取临界值时，如何认识 和确定它的影子价格呢？ 事实上，假定当 bi bi ˆ  时，影子价格为 (1) wi ，bi bi ˆ  时为 (2) wi ，则由函数的递减性和阶梯 性，必有 (1) (2) wi  wi ，这时对临界值 i b ˆ ，若取 bi =1 则目标值 f 将增加 (2) wi ，若取 bi = −1 则将 减少 (1) wi ，故增与减的值不等，这正是它与通常情形区别之所在。再看目标函数 f，它实际 上是资源量 i b 的连续分段线性函数，该函数在临界处虽说连续，且左右导数均存在 (1) i i w b f =   − ， (2) i i w b f =   + 却不相等，这就是说对临界值 i b ˆ （6）不成立。这时宜补充定义如下

(7) b.=6.. vb >0 Ol 其中,b为资源b的临界值。 表面看,(7)在b处似有两个影子价格,但是一联系具体问题,不是考虑资源增加就是 减少,两者必具其一也仅具其一,因而影子价格仍是唯一的。 进一步,如何判断资源量是否为临界值呢。上述分析表明,这等价于对偶问题的解是 否唯 容易证明,如果问题(3)的最优解x是非退化的,即所有基变量均为正,则对偶问题 最优解唯一,故只有当ξ是退化的,即有θ基变量时,对偶问题才可能有多个最优解。在此 基础上,可以给出对偶问题有非唯一解的充要条件(详见[24])。最后可得下面的结果 定理9设资源优化利用问题(3)有k≥2个对偶最优解 对于任意i,1≤i≤m令 fwl; 则当v>w时,第i种资源的投入量恰为临界值,此时资源增加时的影子价格为 af =n,减时的影子价格为互=m而当w+=时第i种资源的投入量不取临界值, 其影子价格仍为QJ=m=v。 证明略。 例1 2x1+ 2x1+2x≤12 x+2x2≤8 st4x1≤16 2x,≤4 可以求得它有4个对偶最优解

100            =     =        = + − , 0 ˆ , 0 ˆ , (0) i i i i i i i i i i i i b b b b f b b b b f b b b f w  (7) 其中， i b ˆ 为资源 i b 的临界值。 表面看，（7）在 i b ˆ 处似有两个影子价格，但是一联系具体问题，不是考虑资源增加就是 减少，两者必具其一也仅具其一，因而影子价格仍是唯一的。 进一步，如何判断资源量是否为临界值呢。上述分析表明，这等价于对偶问题的解是 否唯一。 容易证明，如果问题（3）的最优解 x 是非退化的，即所有基变量均为正，则对偶问题 最优解唯一，故只有当 x 是退化的，即有 0 基变量时，对偶问题才可能有多个最优解。在此 基础上，可以给出对偶问题有非唯一解的充要条件（详见[24]）。最后可得下面的结果。 定理 9 设资源优化利用问题（3）有 k  2 个对偶最优解: w w w j k j m j j ( , , ), 1,2, , ( ) ( ) 1 ( ) =  =  对于任意 i，1  i  m 令 min { } ( ) 1 j i j k wi w   + = max{ } ( ) 1 j i j k wi w   − = 则当 − + wi  wi 时，第 i 种资源的投入量恰为临界值，此时资源增加时的影子价格为 + + =   i i w b f ，减时的影子价格为 − − =   i i w b f ;而当 w + − i = wi 时第 i 种资源的投入量不取临界值， 其影子价格仍为 + − = =   i i i w w b f 。 证明略。 例 1             +  +  = + , 0 2 4 4 16 2 8 2 2 12 . . max 2 3 1 2 2 1 1 2 1 2 1 2 x x x x x x x x st f x x 可以求得它有 4 个对偶最优解: