对偶理论与影子价格

1、对偶理论与影子价格第1页，共35页，2022年，5月20日，1点57分，星期三2对偶问题的提出第2页，共35页，2022年，5月20日，1点57分，星期三例1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？ 产品甲产品乙设备能力设备A3265设备B2140设备C0375利润15002500 现在从另一个角度来讨论该问题： 如果工厂考虑不安排生产，而准备把所有设备出租（或用于外协加工），工厂收取租金（或加工费）。试问：设备 A、B、C 每工时各如何

2、收费（租金或加工费）才最有竞争力？ 工厂为了获得最大利润，在为设备定价时，应保证生产某产品的设备工时所收取的费用不低于生产该产品的利润；同时，为了提高竞争力，应该使定价尽可能低。目标函数设x1，x2分别为生产甲乙两种产品的件数约束条件 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收费。目标函数约束条件第3页，共35页，2022年，5月20日，1点57分，星期三4 解： 可以建立如下的线性规划模型： 目标函数 约束条件 化为标准型，利用单纯形法进行求解。 最优解X=(5, 25, 0, 5, 0)， 最优值（利润）为70000。 第4页，共35页，2022年，5月20日，1点57分

3、，星期三5 解： 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收费。可以建立以下线性规划模型： 化为标准型，利用单纯形法进行求解。 最优解Y=(500, 0, 500, 0, 0) 最优值（收费）为70000。 第5页，共35页，2022年，5月20日，1点57分，星期三6原问题对偶问题第6页，共35页，2022年，5月20日，1点57分，星期三7原问题对偶问题目标函数 Max Min约束条件系数矩阵AAT资源常数b c目标系数cb2个变量2个约束 3个约束 3个变量解 检验数检验数解可以看到，这两个问题关系密切，用同样的原始数据：第7页，共35页，2022年，5月20日，1点5

4、7分，星期三 线性规划有一个有趣的特性，就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题，并且这一对线性规划问题的解之间还存在着密切的关系。线性规划的这个特性称为对偶性。 对这两个线性规划问题，一般称前者为原问题，后者是前者的对偶问题8第8页，共35页，2022年，5月20日，1点57分，星期三对偶问题的形式9 如果线性规划问题的变量均具有非负约束，其约束条件当目标函数求极大值时均取“”，当目标函数求极小值时均取“”，则称具有对称形式。对称形式下原问题和对偶问题的形式：（LP）“Max”s.t.（DP）“Min”s.t.第9页，共35页，2022年，5月20日，1点

5、57分，星期三一对对称形式的对偶规划之间具有下面的对应关系： 1.若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。 2.从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量 3.从数据b、C的位置看：在两个规划模型中，b和C的位置对换 4.两个规划模型中的变量皆非负10第10页，共35页，2022年，5月20日，1点57分，星期三11Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2y

6、mam1am2amnbmyi 0c1c2cn第11页，共35页，2022年，5月20日，1点57分，星期三 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系进行处理并给出其对偶规划： 1. 将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面的方法处理； 2. 若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； 3. 若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 也可以直接给出其对偶规划。12第12页，共35页，2022年，5月20日，1点57分

7、，星期三例2：写出下面线性规划的对偶规划模13第13页，共35页，2022年，5月20日，1点57分，星期三解：先化为对称形式（Max） “”的约束两端同乘以“1” “=”的约束等价转换为“”和“”的两个约束，再变换 变量0，用变量替换，如 变量无非负限制，用变量替换，如 14第14页，共35页，2022年，5月20日，1点57分，星期三写出对偶问题：15第15页，共35页，2022年，5月20日，1点57分，星期三变量替换，令16第16页，共35页，2022年，5月20日，1点57分，星期三把对偶问题和原问题进行比较 17 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1

8、 + 3 x2 5 x3 2原问题 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 没有非负限制 Min f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1对偶问题 3 y1 y2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3无非负限制第17页，共35页，2022年，5月20日，1点57分，星期三 由此得到非对称形式的线性规划原问题和对偶问题的对应关系（对称形式也适用）18原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项目标函数中的系数C目标函数中的系数约束条

9、件右端项目标函数Max z = cj xjMin z = bi yi变量n个 xj 0(0，无限制)约束条件n个aij yj(，=)cj约束条件m个aij xj(，=)bi变量m个 yi0(0，无限制)第18页，共35页，2022年，5月20日，1点57分，星期三对偶问题的基本性质 对偶问题的基本性质对对称形式和非对称形式都是同样适用的，但为了方便，在说明或证明时以对称形式为例（非对称形式可以化为对称形式） 对称形式下原(Primal)问题和对偶(Dual)问题如下： (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “M

10、ax - ” “Min- ”19第19页，共35页，2022年，5月20日，1点57分，星期三1对称性。即对偶问题的对偶是原问题。20第20页，共35页，2022年，5月20日，1点57分，星期三 2.（弱对偶定理）若X，Y分别为（P) 和（D）的可行解，那么CX YTb。证明：由变量的非负性限制，可以得到21第21页，共35页，2022年，5月20日，1点57分，星期三弱对偶定理的推论： 1.（P）任一可行解的目标函数值是其对偶问题目标函数值的下界；（D）任一可行解的目标函数值是其原问题目标函数值的上界。 2. 若（P）可行，那么（P）无有限最优解的充分必要条件是（D）无可行解。 3. 若（

11、D）可行，那么（D）无有限最优解的充分必要条件是（P）无可行解。 4. 若（P）、（D）可行，那么（P）、（D）都有最优解。22第22页，共35页，2022年，5月20日，1点57分，星期三 3.（最优性准则定理）若X，Y分别为(P)，(D)的可行解，且CTX=YTb，则X，Y分别为(P)和(D)的最优解。 证明：设 X 为(P)的可行解，由弱对偶定理可得 CTX YTb = CTX因此 X 为(P) 的最优解。设 Y 为(D)的可行解，由弱对偶定理可得 YTb CTX = YTb因此 Y 为(D) 的最优解。23第23页，共35页，2022年，5月20日，1点57分，星期三 4.（主对偶定理

12、）若(P)和(D)均可行，那么(P)和(D)均有最优解，且最优值相等。证明：若(P)和(D)均可行，则由弱对偶定理的推论知 (P)和(D)均有最优解。 设(P)的最优基为B，令YT= CBB-1，由=C - CBB-1A 0，对于松弛变量部分，目标函数系数为0，系数矩阵为单位阵，检验数为= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 为(D)的可行解。 目标YTb = CBB-1b = CX（原问题最优值），由最优性准则定理知 Y 为 (D) 的最优解注：(P) 松弛变量的检验数的绝对值是(D)的基可行解推论：(P)有最优解的充分必要条件是(D)有最优解24第24页，共35页

13、，2022年，5月20日，1点57分，星期三对称形式下原问题和对偶问题的标准形式如下 5.（互补松弛定理）若X 和Y 分别是 (P)和(D)的最优解（对称形式的标准型下），则有即约束取等式或对应的变量为025第25页，共35页，2022年，5月20日，1点57分，星期三证明：由弱对偶定理（CXYTb）得由主对偶定理可知最优值相等，上述不等式取“=”，26第26页，共35页，2022年，5月20日，1点57分，星期三对偶问题基本性质的应用： 利用单纯形法，求得对偶问题最优解 X=(1, 0, 0, 2, 0)T，最优值 z* = 9。 由互补松弛定理，得 x1 y3 = 0， x2 y4 = 0

14、，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1个约束得到y2 = 9，代入其余约束得 y4 = 4， y5 = 64。 对于变量数量少、约束多的问题，可以利用基本性质简化求解27例4： Min f = 5 y1 + y2 s.t. 3 y1 + y2 9 y1 + y2 5 y1 + 8 y2 8 y1，y2 0 Max z = 9 x1 + 5 x2 + 8 x3 s.t. 3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 第27页，共35页，2022年，5月20日，1点57分，星期三影子

15、价格 影子价格 (Shadow Price) 的概念： 若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第28页，共35页，2022年，5月20日，1点57分，星期三影子价格的经济含义及应用： 资源的市场价格是已知的，且相对比较稳定

16、，而影子价格有赖于资源的利用情况，是未知数，随着企业生产任务、产品结构等情况的变化而发生变化。 影子价格是一种边际价格，说明在资源得到最优利用的条件下，增加单位资源量可以增加的收益。 影子价格是对现有资源实现最大效益时的一种估价，实际上是一种机会成本。企业可以根据现有资源的影子价格，考虑经营策略：如果影子价格高于市场价格，可考虑买进设备，以扩大生产能力，否则不宜买进；若某设备的租费高于影子价格，可考虑出租该设备，否则不宜出租29第29页，共35页，2022年，5月20日，1点57分，星期三 由互补松弛定理，可知如果某种资源未得到充分利用时（松弛变量不为0），则其影子价格为0（对应变量为0）；当

17、资源的影子价格不为0，表明该资源在生产中已耗费完毕。 从影子价格的含义上来考察检验数j = cj - aij yi， 其中 cj 表示产品的价值，aij yi是生产该产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。当产品的价值大于隐含成本时，表明生产该产品有利；否则就不安排生产。这就是检验数的经济含义。 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手，以较少的局部努力，获得较大的整体效益。30第30页，共35页，2022年，5月20日，1点57分，星期三 一般来说，对线性规划问题的求解是确定资源的最优分配

18、方案，而对于对偶问题的求解则是确定对资源的恰当估价。这种估价涉及到资源的最有效利用，如在一个大公司内部，可借助资源的影子价格确定内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。 需要指出的是，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格说明增加单位资源量可以增加的收益，是指资源在一定范围内增加时的情况，当某种资源的增加超过了一定的范围，总利润的增加量就不是按照影子价格给出的数值线性地增加。这将在灵敏度分析中讨论31第31页，共35页，2022年，5月20日，1点57分，星期三影子价格的应用举例： 例5：某外贸公司准备购进两种产

19、品A1，A2。购进产品A1每件需要10元，占用5平方米的空间，卖出1件可获纯利润3元；购进产品A2每件需要15元，占用3平方米的空间，卖出1件可获纯利润4元。公司现有资金1400元，有430平方米的仓库空间存放产品。根据这些条件可以建立求最大利润的线性规划模型： Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15 x2 1400 5 x1 + 3 x2 430 x1, x2 032第32页，共35页，2022年，5月20日，1点57分，星期三求解后得到最优单纯形表如下所示 ： 因此，最优方案是分别购进两种产品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第33页，共35页，2022年，5月20日，1点57分，星