线性规划对偶理论(含影子价格)-2.11.3.6

1、 对偶的定义 对偶问题的性质 对偶的经济解释SUES1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析 (1) 资源数量 bi 发生变化的分析 (2) 目标函数中价值系数 cj 发生变化的分析对偶问题概念：对偶问题概念：任何一个线性规划问题都有一个与之相对应任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者的线性规划问题，如果前者称为原始问题，后者就称为就称为“对偶对偶”问题。问题。对偶问题是对原问题从另一角度进行的描述对偶问题是对

2、原问题从另一角度进行的描述其最优解与原问题的最优解有着密切的联系，在其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。理论，是线性规划理论的重要内容之一。 ABC拥有量工 时1113材 料1479单件利润233321332maxxxxZ0, 0, 09743. .321321321xxxxxxxxxtsABC拥有量工 时1113材 料1479单件利润233假

3、设有客户提出要求，购买工厂所拥有的假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得和材料制订的最低价格应是多少，才值得出卖工时和材料出卖工时和材料 ?ABC拥有量工 时1113材 料1479单件利润233出卖资源获利应不少于生产产品的获利出卖资源获利应不少于生产产品的获利; 约束约束价格应该尽量低，这样，才能有竞争力价格应该尽量低，这样，才能有竞争力; 目标目标价格应该是非负的价格应该是非负的 ABC拥有量工 时1113材 料1

4、479单件利润233用用y1和和y2分别表示工时和材料的出售价格分别表示工时和材料的出售价格总利润最小总利润最小 min W=3y1+9y2保证保证A产品利润产品利润 y1+y22 保证保证B产品利润产品利润 y1+4y23 保证保证C产品利润产品利润 y1+7y23 售价非负售价非负 y10 y20ABC拥有量工 时1113材 料1479单件利润2332193minyyW0, 037342. .21212121yyyyyyyyts321332maxxxxZ0, 0, 09743. .321321321xxxxxxxxxts1 122minnnZc xc xc x111112121222221

5、212. .,0nnmmmnnmnxbaaaaaaxbstaaaxbx xx1122maxmmWb yb yb y111121112222221212. .,0mmnnmnmnmycaaaaaaycstaaaycy yy对称形式的对偶问题原始问题原始问题min f(x)=CTXs.t.AXbX 0对偶问题对偶问题max z(y)=bTys.t. ATyCy 0minbACTCATbTmaxmnmn对偶问题的特点对偶问题的特点l（1）目标函数在一个问题中是求最大值在）目标函数在一个问题中是求最大值在另一问题中则为求最小值另一问题中则为求最小值l（2）一个问题中目标函数的系数是另一个）一个问题中目

6、标函数的系数是另一个问题中约束条件的右端项问题中约束条件的右端项l（3）一个问题中的约束条件个数等于另一）一个问题中的约束条件个数等于另一个问题中的变量数个问题中的变量数l（4）原问题的约束系数矩阵与对偶问题的）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵约束系数矩阵互为转置矩阵 一 般线性规划问题的对偶问题1 122minnnfc xc xc xnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa1), 0(0),(),(),(22112222212111212111或符号不限1122maxmmzb yb yb y11121211121222221122,)1(

7、 , )( , )( , )0(0mmmmnnmnmnjima ya ya yca ya yayca ya yaycy 符号不限 或对偶问题对应表对偶问题对应表原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数min目标函数目标函数max约束条件：约束条件： m个个第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“” 变量数：变量数： m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 变量数：变量数：n个个第第j个变量个变量 0第第j个变量个变量 0第第j个变量是自由变量

8、个变量是自由变量 约束条件：约束条件：n个个第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“” 例写出如下LP问题的对偶问题123min23fxxx123123123123,3264235390,xxxxxxxxxxxx符号不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符号不限对偶问题对偶问题的性质1、对偶的对偶就是原始问题、对偶的对偶就是原始问题max z=-CTXs.t. -AX-bX 0min y=-bTWs.t. -ATW-CW 0max y=bTWs.t. ATWCW

9、0min z=CTXs.t. AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义2、对偶问题的性质（1）弱对偶性（可行解的目标函数值之间的关系）弱对偶性（可行解的目标函数值之间的关系） 设设X、Y分别是原始问题和对偶问题的可行解分别是原始问题和对偶问题的可行解 cjxjbiyiminTfC X. .0TA YCstYmaxTzb YTTTTTC XA YXY AXY bb Y. .0AXbstX11 (1,2, ) (1,2,) (1,2, ) (1,2,)jinmjjiijijixjny imc xb yxjny im 如果是原问题的可行解是其对偶问题的可行解且有则是原问题的最优解是其对

10、偶问题的最优解（3）最优性）最优性（2）无界性）无界性如果原问题（对偶问题）具有无界解，如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。则其对偶问题（原问题）无可行解。 无界性在一对对偶问无界性在一对对偶问题，若其中一个问题可行题，若其中一个问题可行但目标函数无界，则另一但目标函数无界，则另一个问题不可行；反之不成个问题不可行；反之不成立。这也是对偶问题的无立。这也是对偶问题的无界性。界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可行解无可行解无可行解无可行解问题无界问题无界对偶问题对偶问题原问题原问题 0,024 2max2121212

11、1xxxxxxxxZ无界无界如：如：（原）（原） 0,012 24min21212121yyyyyyyyW无可无可行解行解（对）（对）已知已知12123123123 : max22 21,0Zxxxxxxxxx x x 原1212121212: min221 2 0,0Wyyyyyyyyy y对试用对偶理论证明原问题无界。试用对偶理论证明原问题无界。 解：解： =（0.0.0）是）是 原问题的一个可行解，而原问题的一个可行解，而 对偶对偶问题问题 的第一个约束条件不能成立（因为的第一个约束条件不能成立（因为y1 , y2 0)。因。因此，对偶问题不可行，可知，原问题无界。此，对偶问题不可行，可

12、知，原问题无界。_X（4）强对偶性（最优解的目标函数之间的关系）强对偶性（最优解的目标函数之间的关系）如果原问题有最优解，则其对偶问题也一定有如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等最优解，且两者的目标函数值相等在线性规划问题的最优解中，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；则该约束条件取严格等式；反之如果约束条件取严格不等式，反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。则其对应的对偶变量一定为零。即即1100niijjijnijjiijya xba xby如

13、果，则如果，则123123123123min 23. .33122,0 xxxstxxxxxxx xx例2给定线性规划问题121 11(,),7 7Tyy y已知对偶问题的最优解为试用互补松弛性质求原问题的最优解.1212121212max2. .322331,0yys tyyyyyyyy12312,0,y yxy y将最优解的值代入约束条件，得第3个约束为严格不等式，由互补松弛性得又由于的值均大于零，因此原问题的两个约束条件应取等式，故有12312331232xxxxxx解：先写出它的对偶问题12123min4,5/7,( ,)(4/7,5/7,0)23/7TTxxxx xxf求解后得到/7

14、故原问题的最优解为l练习已知线性规划问题123451234512345min 23523. .2342330,1,2,5jxxxxxstxxxxxxxxxxxj(1,0,0,0,1)Tx 已知原问题的最优解为试用互补松弛性质找出对偶问题的最优解.影子价格对偶的经济解释1、原始问题是利润最大化的生产计划问题0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润单位产品的利润产品产量产品产量总利润总利润资源限量资源限量单位产品消耗的资源单位

15、产品消耗的资源剩余的资源剩余的资源消耗的资源消耗的资源2、对偶问题112211121211112122222211221212min. .0mmmmmmmmnnmnmm nnmmmm nzbwb wb wsta wa wa wwca wa wa wwca wa wa wwcwwwwww 资源限量资源限量资源价格资源价格总利润总利润对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的影子价格（种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min

16、 y3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooi1122iimmzbwb wbwb wmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润mmjiij2j2

17、1j1wawawawa增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211l对偶单纯形法的原理l对偶单纯形法的应用步骤l对偶单纯形法举例l对偶单纯形法的应用条件l对偶单纯形法的优点和缺点l对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。l单纯形法是在原问题可行的基础上，通过迭是在原问题可行的基础上，通过迭代使代使对偶

18、问题达到可行，从而得到最优解。达到可行，从而得到最优解。根据对偶问题的对称性，若根据对偶问题的对称性，若原问题不可行而不可行而对偶问题可行，那么在保持对偶问题可行的可行，那么在保持对偶问题可行的基础上，逐步迭代使基础上，逐步迭代使原问题达到可行，也可达到可行，也可得到最优解。得到最优解。对于标准线性规划问题：可行基B 若B对应的基本解是可行解最优基B 若B对应的基本解是最优解对偶可行基B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 min fCX. .Tst A YC0. .XbAXtsmax zbY最优基B可行基B 对偶可行基B单纯形法可行基B 保持可行性 对偶可行基

19、B对偶单纯形法可行基B 保持对偶可行性 对偶可行基B应用前提： 有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。l找一个基（可以不是可行的），建立初始对偶单纯形表，检验数全部非负；l若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；l为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。l主元变换 )3.2.1(01451232102215129min321321321321jxxxxxxxxxxxxxZj 例题例题:用对偶单纯形法求解用对偶单纯形法求解解:将上述模型转化

20、为 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxZ cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(-9/-1.-12/-1. -15/-5)cj-Z 0-9-12-15000i列初始单纯形表，取b中比较小的行对应的变量为换出基变量。cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5 (-30/-9.-45/-14 .-15/-1)-Z 42-6-9000-3icj-9-12 -15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9. -33/-1)-15x315/71/140101/14-3/14-Z 501/7-3/14000-45/14-33/14c