运筹学课件-对偶定理、影子价格

设原问题是（记为LP）：

对偶问题是（记为DP）：这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。【性质1】

对称性对偶问题的对偶是原问题。

【证】设原问题是2.1.3对偶定理它与下列线性规划问题是等价的：再写出它的对偶问题。它与下列线性规划问题是等价的即是原问题。

由表2－1知，它的对偶问题是【性质2】

弱对偶性

设X°、Y°分别为（LP）与（DP）的可行解，则

【证】因为X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,将不等式AX°≤b

两边左乘Y°得Y°AX°≤Y°b再将不等式Y°A≥C

两边右乘X°，故

CX°≤Y°AX≤Y°b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。得CX°≤Y°AX°由这个性质可得到下面几个结论：

（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3）若原问题可行且另一个问题不可行，则原问题具有无界解。

注意上述结论（2）及（3）的条件不能少。一个问题有可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。例如：无可行解，而对偶问题有可行解，由结论（3）知必有无界解。【性质3】最优准则定理设X°与Y°分别是（LP）与（DP）的可行解，则当X°、Y°是（LP）与（DP）的最优解当且仅当CX°=Y°b.【证】若X°、Y°为最优解，B为（LP）的最优基，则有Y°=CBB－1，并且当CX°=Y°b时，由性质1，对任意可行解有即Y°b是（DP）中任一可行解的目标值的下界，CX°是（LP）中任一可行解的目标值的上界，从而X°、Y°是最优解。【性质4】

还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【证】设（LP）有最优解X°，那么对于最优基B必有C－

CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0，这里Y°=CBB-1

，从而Y°是可行解，对目标函数有由性质3知Y°是最优解。由性质4还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。证明：由两者均有可行解，则根据弱对偶定理可知两者均有界，因此均有最优解。以下对于标准型的线性规划问题及其对偶问题证明在最优解时，原问题与对偶问题相等。的最优值相等。定理5(主对偶定理)

若(LP)和(DP)均可行，那么(LP)和(DP)均有最优解,且最优值相等。设B是其最优基，是与之对应的最优的基本可行解。令，则对应于基B的检验数满足：

因此成为对偶问题的一个可行解，且此时对应的目标函数值为：

注意到原问题的最优目标值为：恰好与对偶问题的目标函数值相等。【性质6】

（LP）的检验数的相反数对应于（DP）的一组基本解.

其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。【例2.1】线性规划（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；（4）用公式Y=CBB-1求对偶问题的最优解。【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2－2所示。表2－2XBx1x2x3x4x5b(1)x4x52*1-102410012→4λj6↑-2100

(2)x1x510-1/21/2*131/2-1/20113→λj01↑-5-30

(3)x1x21001460-11246λj00-11-2-2

最优解X=（4，6，0），最优值Z=6×4－2×6=12；

（2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性质6得到对偶问题的基本解（y1、y2、y3、y4、y5）

=（－λ4，－λ5，－λ1，－λ2，－λ3），即

表2－2（1）中λ=（6，－2，1，0，0），

则Y（1）=（0，0，-6，2，－1）表2－2（2）中λ=（0，1，－5，－3，0），

则Y（2）=（3，0，0，－1，5）表2－2（3）中λ=（0，0，－11，－2，－2），

则Y（3）=（2，2，0，0，11）（1）因为表2－2（3）为最优解，故

Y（3）=（2，2，0，0，11）为对偶问题最优解；（1）表2－2（3）中的最优基

B-1为表2－2（3）中x4，x5两列的系数，即CB=（6，－2），因而本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表2－3也许对您了解这些性质有帮助。表2－3一个问题max另一个问题min有最优解有最优解性质4无最优解无最优解无最优解性质4无界解（有可行解）无可行解性质2无可行解无界解（有可行解）应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以－1求得基本解性质6影子价格

——

是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。

若x*,y*

分别为（LP）和（DP）的最优解，

那么，cT

x*=bT

y*

。

根据f=bTy*=b1y1*+b2y2*+

+bmym*

可知

f/

bi

=

yi*

yi*

表示

bi

变化1个单位对目标f

产生的影响，称yi*

为bi的影子价格。

注意：若B

是最优基，

y*=(BT)-1

cB

为影子价格向量。2.1.4影子价格

影子价格的经济含义

(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。

（2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系

因此，可以将z*看作是bi,i=1,2，…,m的函数，对bi求偏导数可得到

这说明，如果右端常数增加一个单位，则目标函数值的增量将是

影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。

需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增