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

1、线性规划的对偶实际 对偶的定义 对偶问题的性质 对偶的经济解释SUES.XBXNXSbXBBNIbCCBCN00了解-单纯形的矩阵描画XS为松弛变量.XBXNXSbXBIB1N B1B1bN0CNCBB1NCBB1CBB1b单纯性法计算时，总选取单位矩阵 I 为初始基，对应基变量为XS, 设迭代假设干步后，基变量变为XB, XB 在初始单纯性表中的系数矩阵为 B。那么该步的单纯性表中由 XB 系数组成的矩阵为单位矩阵 I ，对应XS 的系数矩阵在新表中应为B-1 Y=CBB-1 称为单纯形乘子对偶变量.对偶原理对偶问题概念：任何一个线性规划问题都有一个与之相对应的线性规划问题，假设前者称为原始

2、问题，后者就称为“对偶问题。对偶问题是对原问题从另一角度进展的描画其最优解与原问题的最优解有着亲密的联络，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶实际就是研讨线性规划及其对偶问题的实际，是线性规划实际的重要内容之一。 .问题的导出ABC拥有量工 时1113材 料1479单件利润233.ABC拥有量工 时1113材 料1479单件利润233假设有客户提出要求，购买工厂所拥有的工时和资料，为客户加工别的产品，由客户支付工时费和资料费。那么工厂给工时和资料制定的最低价钱应是多少，才值得出卖工时和资料 ?.ABC拥有量工 时1113材 料1479单件利润233出卖资源

3、获利应不少于消费产品的获利; 约束价钱应该尽量低，这样，才干有竞争力; 目的价钱应该是非负的 .ABC拥有量工 时1113材 料1479单件利润233用y1和y2分别表示工时和资料的出卖价钱总利润最小 min W=3y1+9y2保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20.ABC拥有量工 时1113材 料1479单件利润233.对偶问题的定义对称方式的对偶问题.对偶的定义原始问题min f(x)=CTXs.t.AXbX 0对偶问题max z(y)=bTys.t. ATyCy 0minbACTCATbTmaxmnmn.对偶

4、问题的特点1目的函数在一个问题中是求最大值在另一问题中那么为求最小值2一个问题中目的函数的系数是另一个问题中约束条件的右端项3一个问题中的约束条件个数等于另一个问题中的变量数4原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵. 普通线性规划问题的对偶问题.对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数min目标函数max约束条件： m个第i个约束类型为“”第i个约束类型为“”第i个约束类型为“” 变量数： m个第i个变量0第i个变量0第i个变量是自由变量 变量数：n个第j个变量 0第j个变量 0第j个变量是自由变量 约束条件：n个第j个约束类型为“”第j个约束类型为“”第j

5、个约束类型为“” .例写出如下LP问题的对偶问题对偶问题.对偶问题的性质1、对偶的对偶就是原始问题max z=-CTXs.t. -AX-bX 0min y=-bTWs.t. -ATW-CW 0max y=bTWs.t. ATWCW 0min z=CTXs.t. AXb X 0对偶的定义对偶的定义.2、对偶问题的性质1弱对偶性可行解的目的函数值之间的关系 设X、Y分别是原始问题和对偶问题的可行解 cjxjbiyi.3最优性2无界性假设原问题对偶问题具有无界解，那么其对偶问题原问题无可行解。. 无界性在一对对偶问题，假设其中一个问题可行但目的函数无界，那么另一个问题不可行；反之不成立。这也是对偶问

6、题的无界性。关于无界性有如下结论：问题无界无可行解无可行解无可行解问题无界对偶问题原问题无界如：原无可行解对.知试用对偶实际证明原问题无界。 解： =0.0.0是 原问题的一个可行解，而 对偶问题 的第一个约束条件不能成立由于y1 , y2 0)。因此，对偶问题不可行，可知，原问题无界。.4强对偶性最优解的目的函数之间的关系假设原问题有最优解，那么其对偶问题也一定有最优解，且两者的目的函数值相等.在线性规划问题的最优解中，假设对应某一约束条件的对偶变量值为非零，那么该约束条件取严厉等式；反之假设约束条件取严厉不等式，3、互补松弛性那么其对应的对偶变量一定为零。即.解：先写出它的对偶问题.练习知

7、线性规划问题.影子价钱对偶的经济解释1、原始问题是利润最大化的消费方案问题单位产品的利润产品产量总利润资源限量单位产品耗费的资源剩余的资源耗费的资源.2、对偶问题资源限量资源价钱总利润对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价钱Shadow Price原始和对偶问题都获得最优解时，最大利润 max z=min y.3、资源影子价钱的性质影子价钱越大，阐明这种资源越是相对紧缺影子价钱越小，阐明这种资源相对不紧缺假设最优消费方案下某种资源有剩余，这种资源的影子价钱一定等于0.w1w2wm4、产品的时机本钱时机本钱表示减少一件产品所节省的资源可以添加的利润添加单

8、位资源可以添加的利润减少一件产品可以节省的资源.THE END.对偶单纯形法对偶单纯形法的原理对偶单纯形法的运用步骤对偶单纯形法举例对偶单纯形法的运用条件对偶单纯形法的优点和缺陷.对偶单纯形法原理对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶实际求解原问题的解的方法。单纯形法是在原问题可行的根底上，经过迭代使对偶问题到达可行，从而得到最优解。根据对偶问题的对称性，假设原问题不可行而对偶问题可行，那么在坚持对偶问题可行的根底上，逐渐迭代使原问题到达可行，也可得到最优解。.对于规范线性规划问题：可行基B 假设B对应的根本解是可行解最优基B 假设B对应的根本解是最优解对偶可行基B 假设CBB-

9、1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 .最优基B可行基B 对偶可行基B单纯形法可行基B 坚持可行性 对偶可行基B对偶单纯形法可行基B 坚持对偶可行性 对偶可行基B.对偶单纯形法运用条件运用前提： 有一个基，其对应的基满足: 单纯形表的检验数行全部非正对偶可行； 变量取值可有负数非可行解。.对偶单纯形法步骤找一个基可以不是可行的，建立初始对偶单纯形表，检验数全部非负；假设b列元素非负，那么曾经是最优基。反之，那么取相应行的基变量为出基变量；为保证能对基的可行性有所改良，那么未来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。主元变换.例题:用对偶单纯形

10、法求解.解:将上述模型转化为.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-15000列初始单纯形表，取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-3

11、.cj-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/14.cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z 72000-1/3-3-7/3. 所以， X*=2 . 2 . 2 . 0 . 0 . 0 Z* =72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72.对偶单纯形法的优点和缺陷优点： 初始解可以是非可行解，当检验数都为负数时，就可以进展基的变换，不需求参与人工变量。 当变量多于约束条件，用对偶单纯形法计算可以减少计算任务量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。 在灵敏度分析中，有时需求运用对偶单纯形法，这样可以使问题处置简化。.缺陷：对于大多数的线性规划问题，很难找到一个初始可行基，因此这个方法在求解线性规划问题时很少单独运用。.单纯形法是在根本可行解中寻觅满足