线性规划对偶理论(含影子价格)_21136（PPT47页).ppt

线性规划的对偶理论,对偶的定义对偶问题的性质对偶的经济解释,SUES,了解-单纯形的矩阵描述,XS为松弛变量,单纯性法计算时，总选取单位矩阵I为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB在初始单纯性表中的系数矩阵为B。则该步的单纯性表中由XB系数组成的矩阵为单位矩阵I，对应XS的系数矩阵在新表中应为B-1,Y=CBB-1称为单纯形乘子（对偶变量）,对偶原理,对偶问题概念：任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的导出,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出卖工时和材料?,出卖资源获利应不少于生产产品的获利;约束价格应该尽量低，这样，才能有竞争力;目标价格应该是非负的,用y1和y2分别表示工时和材料的出售价格,总利润最小minW=3y1+9y2保证A产品利润y1+y22保证B产品利润y1+4y23保证C产品利润y1+7y23售价非负y10y20,对偶问题的定义,对称形式的对偶问题,对偶的定义,原始问题minf(x)=CTXs.t.AXbX0,对偶问题maxz(y)=bTys.t.ATyCy0,min,b,A,CT,C,AT,bT,max,m,n,m,n,对偶问题的特点（1）目标函数在一个问题中是求最大值在另一问题中则为求最小值（2）一个问题中目标函数的系数是另一个问题中约束条件的右端项（3）一个问题中的约束条件个数等于另一个问题中的变量数（4）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵,一般线性规划问题的对偶问题,对偶问题对应表,例写出如下LP问题的对偶问题,对偶问题,对偶问题的性质,1、对偶的对偶就是原始问题,2、对偶问题的性质,（1）弱对偶性（可行解的目标函数值之间的关系）设X、Y分别是原始问题和对偶问题的可行解cjxjbiyi,（3）最优性,（2）无界性,如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。,无界性在一对对偶问题，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,已知,试用对偶理论证明原问题无界。,解：=（0.0.0）是原问题的一个可行解，而对偶问题的第一个约束条件不能成立（因为y1,y20)。因此，对偶问题不可行，可知，原问题无界。,（4）强对偶性（最优解的目标函数之间的关系）,如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等,在线性规划问题的最优解中，,如果对应某一约束条件的对偶变量值为非零，,则该约束条件取严格等式；,反之如果约束条件取严格不等式，,3、互补松弛性,则其对应的对偶变量一定为零。,即,解：先写出它的对偶问题,练习已知线性规划问题,影子价格对偶的经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润,产品产量,总利润,资源限量,单位产品消耗的资源,剩余的资源,消耗的资源,2、对偶问题,资源限量,资源价格,总利润,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（ShadowPrice）,原始和对偶问题都取得最优解时，最大利润maxz=miny,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1w2wm,4、产品的机会成本,机会成本表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,THEEND,对偶单纯形法,对偶单纯形法的原理对偶单纯形法的应用步骤对偶单纯形法举例对偶单纯形法的应用条件对偶单纯形法的优点和缺点,对偶单纯形法原理,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。单纯形法是在原问题可行的基础上，通过迭代使对偶问题达到可行，从而得到最优解。根据对偶问题的对称性，若原问题不可行而对偶问题可行，那么在保持对偶问题可行的基础上，逐步迭代使原问题达到可行，也可得到最优解。,对于标准线性规划问题：,可行基B若B对应的基本解是可行解最优基B若B对应的基本解是最优解对偶可行基B若CBB-1是对偶问题可行解即C-CBB-1A0或检验数0,对偶单纯形法应用条件,应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。,对偶单纯形法步骤,找一个基（可以不是可行的），建立初始对偶单纯形表，检验数全部非负；若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量；为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非负的。主元变换,例题:用对偶单纯形法求解,解:将上述模型转化为,列初始单纯形表，取b中比较小的行对应的变量为换出基变量。,所以，X*=（2.2.2.0.0.0）Z*=72，原问题Z*=72其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72,对偶单纯形法的优点和缺点,优点：初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，不需要加入人工变量。当变量多于约束条件，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。,缺点：对于大多数的线性规划问题，很难找到一个初始可行基，因而这个