3-4运筹学课件

《运筹学》1/36第三章线性规划对偶理论及其应用§3.1线性规划的对偶问题§3.3对偶单纯形法§3.4影子价格和灵敏度分析§3.2对偶规划的基本性质《运筹学》2/36§3.4影子价格和灵敏度分析原问题是利润最大化的生产计划问题021212211222222121111212111222211mnnnnmmnnmnmmnnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxatsxcxcxcz...................................max单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）《运筹学》3/36对偶问题0212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmm资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=miny《运筹学》4/36定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。0s.t.(D)0s.t.YCYAXbAXPYbWCXZ)(minmax一、影子价格的概念《运筹学》5/36设：B是问题P的最优基，由前表可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+...+y*Ibi+...+y*mbm当bi变为bi+1时(其它条件不变），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CBB-1N－CNCBB-1《运筹学》6/36目标函数最优值变为：Z′*=y*1b1+y*2b2+...+y*I（bi+1）+...+y*mbm所以△Z*=Z′*－Z*=y*i),...,,(*miybZii21也可以写成：即y*i表示Z*对bi的变化率。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。《运筹学》7/36考虑具有三种资源的优化问题：302010由图示可知最优点为B（35，10），最优值为215。例14影子价格的图解法03452802190345Z2121212121xxxxxxxxxx,)()()(maxx18060402020406080③②①100Bx2《运筹学》8/362010由图示可知最优点为B(35,10),最优值为215。故资源A的影子价格为0。03452802191345Z2121212121xxxxxxxxxx,)()()(max假设资源A增加1个单位，其它条件不变：8060402020406080x1③②①100Bx2《运筹学》9/36302010由图示可知最优点为B（36，9），最优值为216。故资源B的影子价格为1。8060402020406080x1③②①100Bx203452812190345Z2121212121xxxxxxxxxx,)()()(max假设资源B增加1个单位，其它条件不变：《运筹学》10/362010由图示可知最优点为B(34，12），最优值为218，故C的影子价格为3。8060402020406080x1③②①100Bx203462802190345Z2121212121xxxxxxxxxx,)()()(max假设资源C增加1个单位，其它条件不变：《运筹学》11/36若第i种资源的单位市场价格为mi，当yimi时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；如果yimi，则企业有偿转让这种资源，可获单位纯利mi－yi。影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0《运筹学》12/36w1w2wm产品的机会成本机会成本：表示减少一件产品所节省的资源可以增加的利润。mmjiij2j21j1wawawawa增加单位资源可以增加的利润减少一件产品可以节省的资源02122112222221211112121112211njmnmnjmjmmnnjjnnjjnnjjxxxxbxaxaxaxabxaxaxaxabxaxaxaxatsxcxcxcxcz.....................................................max《运筹学》13/36机会成本利润差额成本0212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmm产品的差额成本差额成本=机会成本-利润jjTjmjmjjjmcaWcawawaww)...(2211《运筹学》14/36互补松弛关系的经济解释0x0w0w0x0wx0w0x0x0w0xwjjmjmjjmjiininiini在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产《运筹学》15/36灵敏度分析灵敏度分析的任务是解决以下两类问题一、当系数A、b、C中的某个发生变化时,目前的最优基是否仍最优（即目前的最优生产方案是否要变化）?(称为模型参数的灵敏度分析)二、增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）?(称为模型结构的灵敏度分析)《运筹学》16/36灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、C中的某一个或几个发生变化时，考察是否影响以下两式的成立：0011CABCbBB《运筹学》17/36一、对于参数b的灵敏度分析从矩阵形式的单纯形表中可以看出，b的变化只影响最优解的变化和最优值的变化。bXXBB-1bB-1AZCBB-1bCBB-1A-C因此，当时，最优基不变（即生产产品的品种不变，但数量及最优值会变化）。0bB10bB1是一个不等式组，从中可以解得b的变化范围若B-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。《运筹学》18/36例15对于如下生产计划问题，为使最优方案不变，试讨论第二个约束条件中b2的变化范围。0,)工时(2623)材料(2432.t.s34maxZ21212121xxxxxxxx约束约束C4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z3600-1/5-6/5解：最优单纯形表为：《运筹学》19/36从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性B-1b≥0,因此，为使最优解不变，只需变化以后的B-1b≥0即可。0535485257224535252532221bbbbB////05354805257222bb由解得：36162b《运筹学》20/36若b2变化超出上述范围，则需用对偶单纯形法进行求解。如b2=6，则612624535252531////bB12612431bBCBC4300CBXBbx1x2x3x434x2x112-6013/5-2/510-2/53/5Z1200-1/5-6/5用上述数字替换最优单纯形表中相应位置的数字得：《运筹学》21/36C4300CBXBbx1x2x3x430x2x33153/2101/2-5/201-3/2Z9-1/200-3/2用对偶单纯形法迭代，求出的最优单纯形表如下：得到新的最优解为：x1=0,x2=3;maxz=9《运筹学》22/36二、对价值系数Cj变化的分析（1）当CN（非基变量的目标函数系数）中某个Cj发生变化时，只影响到非基变量xj的检验数jjjBjjjCPBCCC)()(1由于所以,当0j即当jjC时,最优解不变反之,当时,最优解改变,需要用单纯形法重新进行迭代,以求得新的最优解.0j《运筹学》23/36例16对于下列线性规划模型,为使最优解不变，讨论非基变量x3的目标函数系数c3的变化范围。026223243223421321321321xxxxxxxxtsxxxZ,)()(..max工时约束材料约束用单纯形法求得其最优表为：cj43200CBXBbx1x2x3x4x534x2x14601-1/53/5-2/5104/5-2/53/5Z3600-3/5-1/5-6/5《运筹学》24/36解：因为x3为非基变量，其目标函数系数c3的变化只会影响到x3的检验数，因此为使最优解不变，只需03即，05/1333c若c3=3,则523代入最优单纯形表中相应位置：继续迭代求出新的最优解。C43300CBXBbx1x2x3x4x534x2x14601-1/53/5-2/5104/5-2/53/5Z36002/5-1/5-6/55133/c故时最优解不变。《运筹学》25/36例12在例10中，设基变量x1的系数c1变化为，在最优性不变的条件下，试确定的范围。11cc（2）当CB(即基变量的目标函数系数)中某个Cj发生变化时则会影响到所有变量的检验数σ=C－CBB-1A解不等式组01ABCCB解：5/35/2015/25/310430034111ccABCCB111153565251340034cccc就可得到Cj的变化范围。1c《运筹学》26/360565351520011cc54221211.cc即595100,511ABCCcB则若将上述数字替换单纯形表中相应位置的数字得：C5300CBXBbx1x2x3x435x2x146013/5-2/510-2/53/5Z42001/5-9/5056530515211cc时最优性不变。《运筹学》27/36用单纯形法迭代得最优解表如下：C5300CBXBbx1x2x3x405x3x120/326/305/31-2/312/301/3Z130/30-1/30-5/3j三、技术系数aij变化的分析第一种情况（当jJN）：即aij为非基变量xj的技术系数时，它的变化只影响xj的系数列B-1Pj和检验数，为使最优方案不变，只需0j《运筹学》28/36026223243223421321321321xxxxxxxxtsxxxZ,)()(..max工时约束材料约束C43200CBXBbx1x2x3x4x534x2x14601-1/53/5-2/5104/5-2/53/5Z3600-3/5-1/5-6/5例17