对偶理论与影子价格ppt课件

1、管管 理理 运运 筹筹 学学第六节对偶实际与影子价钱第六节对偶实际与影子价钱 对偶问题的提出对偶问题的提出 对偶问题的方式对偶问题的方式 对偶问题的根本性质对偶问题的根本性质 影子价钱影子价钱管管 理理 运运 筹筹 学学对偶问题的提出对偶问题的提出管管 理理 运运 筹筹 学学例例1 1：某工厂拥有：某工厂拥有A A、B B、C C三种类型三种类型的设备，消费甲、乙两种产品。每的设备，消费甲、乙两种产品。每件产品在消费中需求占用的设备机件产品在消费中需求占用的设备机时数，每件产品可以获得的利润以时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所及三种设备可利用的时数如下表所示：问题：工

2、厂应如何安排消费可示：问题：工厂应如何安排消费可获得最大的总利润？获得最大的总利润？ 产品甲产品甲产品乙产品乙设备才干设备才干设备设备A3265设备设备B2140设备设备C0375利润利润15002500 如今从另一个角度来讨论该问题：如今从另一个角度来讨论该问题： 假设工厂思索不安排消费，而预假设工厂思索不安排消费，而预备把一切设备出租或用于外协加备把一切设备出租或用于外协加工，工厂收取租金或加工费。工，工厂收取租金或加工费。试问：设备试问：设备 A A、B B、C C 每工时各如何每工时各如何收费租金或加工费才最有竞争力？收费租金或加工费才最有竞争力？ 工厂为了获得最大利润，在为设工厂为了

3、获得最大利润，在为设备定价时，应保证消费某产品的设备备定价时，应保证消费某产品的设备工时所收取的费用不低于消费该产品工时所收取的费用不低于消费该产品的利润；同时，为了提高竞争力，应的利润；同时，为了提高竞争力，应该使定价尽能够低。该使定价尽能够低。目的函数目的函数设设x1x1，x2x2分别为消费甲乙两种产品的件数分别为消费甲乙两种产品的件数12max15002500zxx121221232652403750,0 xxxxxxx约束条件约束条件 设设 y1 y1 ，y2 y2 ，y3 y3 分别为每工时设分别为每工时设备备 A A、B B、C C 的收费。的收费。123min654075fyyy

4、121231233215002325000,0,0yyyyyyyy（不少于甲产品的利润）（不少于乙产品的利润）目的函数目的函数约束条件约束条件管管 理理 运运 筹筹 学学 解： 可以建立如下的线性规划模型： 目的函数 约束条件 化为规范型，利用单纯形法进展求解。 最优解X=(5, 25, 0, 5, 0)， 最优值利润为70000。 12max15002500zxx121221232652403750,0 xxxxxxx管管 理理 运运 筹筹 学学 解： 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收费。可以建立以下线性规划模型： 化为规范型，利用单纯形法进展求解。 最优解Y=(

5、500, 0, 500, 0, 0) 最优值收费为70000。 123min654075fyyy121231233215002325000,0,0yyyyyyyy管管 理理 运运 筹筹 学学12max15002500zxx121221232652403750,0 xxxxxxx123min654075fyyy121231233215002325000,0,0yyyyyyyy原问题原问题对偶问题对偶问题管管 理理 运运 筹筹 学学原问题原问题对偶问题对偶问题目的函数目的函数 Max Min约束条件约束条件系数矩阵系数矩阵AAT资源常数资源常数b c目的系数目的系数cb2个变量个变量2个约束个约束

6、 3个约束个约束 3个变量个变量解解 检验数检验数检验数检验数解解可以看到，这两个问题关系亲密，用同样的原始数据：管管 理理 运运 筹筹 学学 线性规划有一个有趣的特性，就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题，并且这一对线性规划问题的解之间还存在着亲密的关系。线性规划的这个特性称为对偶性。 对这两个线性规划问题，普通称前者为原问题，后者是前者的对偶问题管管 理理 运运 筹筹 学学对偶问题的方式 假设线性规划问题的变量均具有非负约束，其约束条件当目的函数求极大值时均取“，当目的函数求极小值时均取“，那么称具有对称方式。对称方式下原问题和对偶问题的方式：LPL

7、Pmax zCX0AX bX“Max“Maxs.t.s.t.minTzY bDPDP0TTAY CY“Min“Mins.t.s.t.管管 理理 运运 筹筹 学学一对对称方式的对偶规划之间具有下面的对应关系： 1.假设一个模型为目的求“极大，约束为“小于等于的不等式，那么它的对偶模型为目的求“极小，约束是“大于等于的不等式。即“max，和“min，相对应。 2.从约束系数矩阵看：一个模型中为，那么另一个模型中为AT。一个模型是m个约束，n个变量，那么它的对偶模型为n个约束，m个变量 3.从数据b、C的位置看：在两个规划模型中，b和C的位置对换 4.两个规划模型中的变量皆非负管管 理理 运运 筹筹

8、 学学Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2ymam1am2amnbmyi 0c1c2cn管管 理理 运运 筹筹 学学 普通称不具有对称方式的一对线性规划为非对称方式的对偶规划。 对于非对称方式的规划，可以按照下面的对应关系进展处置并给出其对偶规划： 1. 将模型一致为“max，或“min， 的方式，对于其中的等式约束按下面的方法处置； 2. 假设原规划的某个约束条件为等式约束，那么在对偶规划中与此约束对应的那个变量取值没有非负限制； 3. 假设原规划的某个变量的值没有非负限制，那么在对偶问题中与此变量对应的那个约束为等式。 也可以直接给出

9、其对偶规划。管管 理理 运运 筹筹 学学例2：写出下面线性规划的对偶规划模123123123123123max43235236140,0,zxxxxxxxxxxxxxxx没有非负限制. .s t管管 理理 运运 筹筹 学学解：先化为对称方式Max “的约束两端同乘以“1 “=的约束等价转换为“和“的两个约束，再变换 变量0，用变量交换，如 变量无非负限制，用变量交换，如 22=-xx333xxx123312331233123312331233max43323552366144,0zxxxxxxxxxxxxxxxxxxxxx x x x 管管 理理 运运 筹筹 学学写出对偶问题：12331233

10、123 33 3123 33 312 23 33 3123 33min24423134563563,0fyyyyyyyyyyyyyyyyyyyyy yyy 管管 理理 运运 筹筹 学学变量交换，令123123123123123min24231345630,0,yyyyyyyyyyyyyyy无非负限制22333,yyyyy 管管 理理 运运 筹筹 学学把对偶问题和原问题进展比较 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2原问题原问题 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 没有非负限制没有

11、非负限制 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无非负无非负限制限制管管 理理 运运 筹筹 学学 由此得到非对称方式的线性规划原问题和对偶问题的对应关系对称方式也适用原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项目的函数中的系数C目的函数中的系数约束条件右端项目的函数Max z = cj xjMin z = bi yi变量n个 xj 0(0，无限制)约束条件n个aij yj(，=)cj约束条件m个aij x

12、j(，=)bi变量m个 yi0(0，无限制)管管 理理 运运 筹筹 学学对偶问题的根本性质 对偶问题的根本性质对对称方式和非对称方式都是同样适用的，但为了方便，在阐明或证明时以对称方式为例非对称方式可以化为对称方式 对称方式下原(Primal)问题和对偶(Dual)问题如下： (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “Max - “Min- 管管 理理 运运 筹筹 学学 1对称性。即对偶问题的对偶是原问题。管管 理理 运运 筹筹 学学 2.弱对偶定理假设X，Y分别为P) 和D的可行解，那么CX YTb。证明：由变

13、量的非负性限制，可以得到 minjijijnjjmiiijnjjjyxaxyaxc11111)(miiinjjjybxc11 minjijijmiinjjijmiiiyxayxayb11111)(管管 理理 运运 筹筹 学学弱对偶定理的推论： 1.P任一可行解的目的函数值是其对偶问标题的函数值的下界；D任一可行解的目的函数值是其原问标题的函数值的上界。 2. 假设P可行，那么P无有限最优解的充分必要条件是D无可行解。 3. 假设D可行，那么D无有限最优解的充分必要条件是P无可行解。 4. 假设P、D可行，那么P、D都有最优解。管管 理理 运运 筹筹 学学 3.最优性准那么定理假设X，Y分别为(

14、P)，(D)的可行解，且CTX=YTb，那么X，Y分别为(P)和(D)的最优解。 证明：设 X 为(P)的可行解，由弱对偶定理可得 CTX YTb = CTX因此 X 为(P) 的最优解。设 Y 为(D)的可行解，由弱对偶定理可得 YTb CTX = YTb因此 Y 为(D) 的最优解。管管 理理 运运 筹筹 学学 4.主对偶定理假设(P)和(D)均可行，那么(P)和(D)均有最优解，且最优值相等。证明：假设(P)和(D)均可行，那么由弱对偶定理的推论知 (P)和(D)均有最优解。 设(P)的最优基为B，令YT= CBB-1，由=C - CBB-1A 0，对于松弛变量部分，目的函数系数为0，系

15、数矩阵为单位阵，检验数为= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 为(D)的可行解。 目的YTb = CBB-1b = CX原问题最优值，由最优性准那么定理知 Y 为 (D) 的最优解注：(P) 松弛变量的检验数的绝对值是(D)的基可行解推论：(P)有最优解的充分必要条件是(D)有最优解管管 理理 运运 筹筹 学学对称方式下原问题和对偶问题的规范方式如下 5.互补松弛定理假设X 和Y 分别是 (P)和(D)的最优解对称方式的规范型下，那么有即约束取等式或对应的变量为0), 2 , 1( 0), 1(11mnjxmibxxaxczMaxjiinnjjijnjjj), 2

16、, 1( 0), 1(11mniynjcyyaybfMinijjmmiiijmiii), 1;, 1( 0, 0njmixyyxinijmj管管 理理 运运 筹筹 学学证明：由弱对偶定理CXYTb得由主对偶定理可知最优值相等，上述不等式取“=， miiiminjijijnjjjybyxaxc1111 miiinmiinjjijiminjijijmiiiyxyxabyxayb111111)(00, 0,yxyxiinij得由 njjjmnjjjmiiijnjjjminjijijxyxcyaxcyxa111111)(00, 0,yxyxjmjij得由管管 理理 运运 筹筹 学学对偶问题根本性质的运

17、用： 利用单纯形法，求得对偶问题最优解 X=(1, 0, 0, 2, 0)T，最优值 z* = 9。 由互补松弛定理，得 x1 y3 = 0， x2 y4 = 0，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1个约束得到y2 = 9，代入其他约束得 y4 = 4， y5 = 64。 对于变量数量少、约束多的问题，可以利用根本性质简化求解例例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.

18、3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 管管 理理 运运 筹筹 学学影子价钱 影子价钱 (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-1管管 理

19、理 运运 筹筹 学学影子价钱的经济含义及运用： 资源的市场价钱是知的，且相对比较稳定，而影子价钱有赖于资源的利用情况，是未知数，随着企业消费义务、产品构造等情况的变化而发生变化。 影子价钱是一种边沿价钱，阐明在资源得到最优利用的条件下，添加单位资源量可以添加的收益。 影子价钱是对现有资源实现最大效益时的一种估价，实践上是一种时机本钱。企业可以根据现有资源的影子价钱，思索运营战略：假设影子价钱高于市场价钱，可思索买进设备，以扩展消费才干，否那么不宜买进；假设某设备的租费高于影子价钱，可思索出租该设备，否那么不宜出租管管 理理 运运 筹筹 学学 由互补松弛定理，可知假设某种资源未得到充分利用时松弛

20、变量不为0，那么其影子价钱为0对应变量为0；当资源的影子价钱不为0，阐明该资源在消费中已耗费终了。 从影子价钱的含义上来调查检验数j = cj - aij yi， 其中 cj 表示产品的价值，aij yi是消费该产品所耗费的各项资源的影子价钱的总和，即产品的隐含本钱。当产品的价值大于隐含本钱时，阐明消费该产品有利；否那么就不安排消费。这就是检验数的经济含义。 影子价钱反映了不同的部分或个体的增量可以获得不同的整体经济效益。假设为了扩展消费才干，思索添加设备，就应该从影子价钱高的设备入手，以较少的部分努力，获得较大的整体效益。管管 理理 运运 筹筹 学学 普通来说，对线性规划问题的求解是确定资源

21、的最优分配方案，而对于对偶问题的求解那么是确定对资源的恰当估价。这种估价涉及到资源的最有效利用，如在一个大公司内部，可借助资源的影子价钱确定内部结算价钱，以便控制有限资源的运用和考核下属企业运营的好坏。 需求指出的是，影子价钱不是固定不变的，当约束条件、产品利润等发生变化时，有能够使影子价钱发生变化。另外，影子价钱阐明添加单位资源量可以添加的收益，是指资源在一定范围内添加时的情况，当某种资源的添加超越了一定的范围，总利润的添加量就不是按照影子价钱给出的数值线性地添加。这将在灵敏度分析中讨论管管 理理 运运 筹筹 学学影子价钱的运用举例： 例5：某外贸公司预备购进两种产品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 0 管管 理理 运运 筹筹 学学求解后得到最优单纯形表如下所示 ： 因此，最优方案是分别购进两种产品50件和60件，公司的最大利润为390元。 同时，从表中也可以看到，资金的影子价钱为11/45，