对偶理论与影子价格

对偶理论与影子价格第一页，共三十五页，2022年，8月28日2对偶问题的提出第二页，共三十五页，2022年，8月28日例1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？

产品甲产品乙设备能力设备A3265设备B2140设备C0375利润15002500现在从另一个角度来讨论该问题：

如果工厂考虑不安排生产，而准备把所有设备出租（或用于外协加工），工厂收取租金（或加工费）。试问：设备A、B、C每工时各如何收费（租金或加工费）才最有竞争力？工厂为了获得最大利润，在为设备定价时，应保证生产某产品的设备工时所收取的费用不低于生产该产品的利润；同时，为了提高竞争力，应该使定价尽可能低。目标函数

设x1，x2分别为生产甲乙两种产品的件数约束条件

设y1，y2，y3分别为每工时设备A、B、C的收费。目标函数

约束条件第三页，共三十五页，2022年，8月28日4

解：可以建立如下的线性规划模型：

目标函数

约束条件

化为标准型，利用单纯形法进行求解。最优解X=(5,25,0,5,0)，最优值（利润）为70000。

第四页，共三十五页，2022年，8月28日5

解：设y1，y2，y3分别为每工时设备A、B、C的收费。可以建立以下线性规划模型：

化为标准型，利用单纯形法进行求解。最优解Y=(500,0,500,0,0)最优值（收费）为70000。

第五页，共三十五页，2022年，8月28日6原问题对偶问题第六页，共三十五页，2022年，8月28日7原问题对偶问题目标函数

Max

Min

约束条件 ≤ ≥系数矩阵A AT资源常数 b c目标系数 cb2个变量 2个约束

3个约束

3个变量解 检验数检验数解可以看到，这两个问题关系密切，用同样的原始数据：第七页，共三十五页，2022年，8月28日线性规划有一个有趣的特性，就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题，并且这一对线性规划问题的解之间还存在着密切的关系。线性规划的这个特性称为对偶性。

对这两个线性规划问题，一般称前者为原问题，后者是前者的对偶问题

8第八页，共三十五页，2022年，8月28日对偶问题的形式9如果线性规划问题的变量均具有非负约束，其约束条件当目标函数求极大值时均取“≤”，当目标函数求极小值时均取“≥”，则称具有对称形式。对称形式下原问题和对偶问题的形式：（LP）“Max——≤”s.t.（DP）“Min——≥”s.t.第九页，共三十五页，2022年，8月28日

一对对称形式的对偶规划之间具有下面的对应关系：

1.若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。

2.从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量

3.从数据b、C的位置看：在两个规划模型中，b和C的位置对换

4.两个规划模型中的变量皆非负

10第十页，共三十五页，2022年，8月28日11MaxzMinfx1x2…xnxi≥0y1a11a12…a1n≤b1y2a21a22…a2n≤b2……………≤…ymam1am2…amn≤bmyi≥0c1c2…cn≥≥≥≥第十一页，共三十五页，2022年，8月28日一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。

对于非对称形式的规划，可以按照下面的对应关系进行处理并给出其对偶规划：

1.将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面的方法处理；

2.若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；

3.若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。

也可以直接给出其对偶规划。

12第十二页，共三十五页，2022年，8月28日例2：写出下面线性规划的对偶规划模

13第十三页，共三十五页，2022年，8月28日解：先化为对称形式（Max—≤）

“≥”的约束两端同乘以“–1”

“=”的约束等价转换为“≤”和“≥”的两个约束，再变换

变量≤0，用变量替换，如

变量无非负限制，用变量替换，如

14第十四页，共三十五页，2022年，8月28日写出对偶问题：

15第十五页，共三十五页，2022年，8月28日变量替换，令

16第十六页，共三十五页，2022年，8月28日把对偶问题和原问题进行比较17Maxz=x1+4x2+3x3s.t.2x1+3x2–5x3≤

2原问题3x1–x2+6x3≥1

x1+x2+x3=4x1≥

0，x2≤0，x3没有非负限制Minf=2y1+y2

+4y3s.t.2y1+3y2

+y3

≥

1对偶问题3y1–y2

+y3≤4–5y1+6y2+y3=3y1≥0

，y2

≤

0，y3无非负限制第十七页，共三十五页，2022年，8月28日

由此得到非对称形式的线性规划原问题和对偶问题的对应关系（对称形式也适用）

18原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项目标函数中的系数C目标函数中的系数约束条件右端项目标函数Maxz=ΣcjxjMinz=Σbiyi变量n个

xj≥0(≤0，无限制)约束条件n个Σaijyj≥(≤，=)cj约束条件m个Σaijxj≤(≥，=)bi变量m个

yi≥0(≤0，无限制)第十八页，共三十五页，2022年，8月28日对偶问题的基本性质对偶问题的基本性质对对称形式和非对称形式都是同样适用的，但为了方便，在说明或证明时以对称形式为例（非对称形式可以化为对称形式）对称形式下原(Primal)问题和对偶(Dual)问题如下：

(P)Maxz=CX(D)Minf=YTbs.t.AX≤bs.t.ATY≥CTX≥0Y≥0“Max--≤”“Min--≥”19第十九页，共三十五页，2022年，8月28日1．对称性。即对偶问题的对偶是原问题。20第二十页，共三十五页，2022年，8月28日

2.（弱对偶定理）若X，Y分别为（P)和（D）的可行解，那么CX≤YTb。

证明：由变量的非负性限制，可以得到

21第二十一页，共三十五页，2022年，8月28日弱对偶定理的推论：

1.（P）任一可行解的目标函数值是其对偶问题目标函数值的下界；（D）任一可行解的目标函数值是其原问题目标函数值的上界。

2.若（P）可行，那么（P）无有限最优解的充分必要条件是（D）无可行解。

3.若（D）可行，那么（D）无有限最优解的充分必要条件是（P）无可行解。

4.若（P）、（D）可行，那么（P）、（D）都有最优解。

22第二十二页，共三十五页，2022年，8月28日

3.（最优性准则定理）若X’，Y’分别为(P)，(D)的可行解，且CTX’=Y’Tb，则X’，Y’分别为(P)和(D)的最优解。

证明：设X为(P)的可行解，由弱对偶定理可得

CTX≤Y’Tb=CTX’

因此X’为(P)的最优解。

设Y为(D)的可行解，由弱对偶定理可得

YTb≥CTX’=Y’Tb

因此Y’为(D)的最优解。

23第二十三页，共三十五页，2022年，8月28日

4.（主对偶定理）若(P)和(D)均可行，那么(P)和(D)均有最优解，且最优值相等。

证明：若(P)和(D)均可行，则由弱对偶定理的推论知(P)和(D)均有最优解。

设(P)的最优基为B，令YT=CBB-1，由σ=C-CBB-1A≤0，对于松弛变量部分，目标函数系数为0，系数矩阵为单位阵，检验数为σ=-CBB-1≤0，故Y≥0，且YTA≥C，ATY≥CT，因此Y为(D)的可行解。

目标YTb=CBB-1b=CX（原问题最优值），由最优性准则定理知Y为(D)的最优解

注：(P)松弛变量的检验数的绝对值是(D)的基可行解

推论：(P)有最优解的充分必要条件是(D)有最优解

24第二十四页，共三十五页，2022年，8月28日对称形式下原问题和对偶问题的标准形式如下5.（互补松弛定理）若X和Y分别是(P)和(D)的最优解（对称形式的标准型下），则有即约束取等式或对应的变量为025第二十五页，共三十五页，2022年，8月28日证明：由弱对偶定理（CX≤YTb）得由主对偶定理可知最优值相等，上述不等式取“=”，26第二十六页，共三十五页，2022年，8月28日对偶问题基本性质的应用：利用单纯形法，求得对偶问题最优解X=(1,0,0,2,0)T，最优值z*=9。由互补松弛定理，得x1y3=0，x2y4=0，x3y5=0，x4y1=0，x5y2=0，因此有y1=0，y3=0，代入第1个约束得到y2=9，代入其余约束得y4=4，y5=64。对于变量数量少、约束多的问题，可以利用基本性质简化求解27例4：Minf=5y1+y2s.t.3y1+y2≥9

y1+y2≥5

y1+8y2≥

8y1，y2≥

0Maxz=9x1+5x2

+8x3s.t.3x1+x2

+x3≤

5

x1+x2

+8x3≤

1x1，x2，x3≥0

第二十七页，共三十五页，2022年，8月28日影子价格影子价格(ShadowPrice)的概念：若X*，Y*分别为（P）和（D）的最优解，则

z=CX*=Y*Tb=f根据z=b1y1*+b2y2*+∙∙∙+bmym*可知z/bi

=

yi*

其中bi表示第i种资源的拥有量，yi*表示bi

变化1个单位对目标z产生的影响，也是在资源最优利用条件下对该资源的估价，称为该资源的影子价格例如，在例1中yi*是对设备租金的估价注意：若B是最优基，y*T=CBB-128第二十八页，共三十五页，2022年，8月28日影子价格的经济含义及应用：

资源的市场价格是已知的，且相对比较稳定，而影子价格有赖于资源的利用情况，是未知数，随着企业生产任务、产品结构等情况的变化而发生变化。

影子价格是一种边际价格，说明在资源得到最优利用的条件下，增加单位资源量可以增加的收益。

影子价格是对现有资源实现最大效益时的一种估价，实际上是一种机会成本。企业可以根据现有资源的影子价格，考虑经营策略：如果影子价格高于市场价格，可考虑买进设备，以扩大生产能力，否则不宜买进；若某设备的租费高于影子价格，可考虑出租该设备，否则不宜出租

29第二十九页，共三十五页，2022年，8月28日由互补松弛定理，可知如果某种资源未得到充分利用时（松弛变量不为0），则其影子价格为0（对应变量为0）；当资源的影子价格不为0，表明该资源在生产中已耗费完毕。

从影子价格的含义上来考察检验数j=cj-∑aijyi，其中cj

表示产品的价值，∑aijyi是生产该产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。当产品的价值大于隐含成本时，表明生产该产品有利；否则就不安排生产。这就是检验数的经济含义。

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

30第三十页，共三十五页，2022年，8月28日一般来说，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价。这种估价涉及到资源的最有效利用，如在一个大公司内部，可借助资源的影子价格确定内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。

需要指出的是，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格说明增加单位资源量可以增加的收益，是指资源在一定范围内增加时的情况，当某种资源的增加超过了一定的范围，总利润的增加量就不是按照影子价格给出的数值线性地增加。这将在灵敏度分析中讨论

31第三十一页，共三十五页，2022年，8月28日影子价格的应用举例：

例5：某外贸公司准备购进两种产品A1，A2。购进产品A1每件需要10元，占用5平方米的空间，卖出1件可获纯利润3元；购进产品A2每件需要15元，占用3平方米的空间，卖出1件可获纯利润4元。公司现有资金1400元，有430平方米的仓库空间存放产品。根据这些条件可以建立求最大利润的线性规划模型：

Maxz=3x1+4x2

s.t.10x1+15x2≤1400

5x1+3x2≤430

x1,x2≥0

32第三十二页，共三十五页，2022年，8月28日求解后得到最优单纯形表如下所示：因此，最优方案是分别购进两种产品50件和60件，公司的最大利润为390元。同时，从表中也可以看到，资金的影子价格为11/45，即增加1元用于购买产品，可以多获利润11/45元；仓库的影子价格为1/9，即增加1平方米的仓库空间，可以多获利润1/9元。33CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9第三十三页，共三十五页，2022年，8月28日假设公司现在另有一笔资金585元，准备用于投资。当然，这笔资金用于购买产品或者增加仓库空间都可以使公司获得更多的利润。问题是应该如何合理安排投资，使公司能够