1、 线性规划的对偶理论及其敏感性分析hyl2对偶是一种普遍现象对偶是一种普遍现象两个黄鹂鸣翠柳两个黄鹂鸣翠柳,一行白露上青天。一行白露上青天。门泊东吴万里船。门泊东吴万里船。窗含西岭千秋雪窗含西岭千秋雪,3国庆黄金周的调侃 一行白鹭上青天，老子挤在最中间；借问酒家何处有，又被堵在收费口。犹抱琵琶半遮面，车上忘带方便面；天生我材必有用，五个小时就不动；寒雨连江夜入吴，高速路上看日出；两岸猿声啼不住，家里不住车里宿。路见不平一声吼，高速路上来遛狗；万里山河一片红，欢喜出门个个熊。4第一节 线性规划的对偶问题一、问题的提出一、问题的提出我们先来看一个例题我们先来看一个例题:56 例例1 某工厂在计划期
2、内安排甲、乙两种产品，已知生产单位产品所需设备某工厂在计划期内安排甲、乙两种产品，已知生产单位产品所需设备A、B、C台时和所获利润如台时和所获利润如下表所示：下表所示：甲乙资源限量设备A11300台时设备B 21400台时设备C01250台时利润（元）50100 问：工厂应分别生产甲、乙产品各多少，才能使工厂获利最多？问：工厂应分别生产甲、乙产品各多少，才能使工厂获利最多？7设：甲设：甲 x1，乙乙 x2该线性规划的模型为：该线性规划的模型为：现在我们从另一个角度来考虑这个问题现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备假如有另外一个工厂要求租用该厂的设备A、B、C
3、，那么，那么该厂的厂长应该如何来确定合理的租金呢？该厂的厂长应该如何来确定合理的租金呢？(LP1)0 x0,x250 x400 x2x300 x x100 x50 xmax Z2122121218设：设：y1-A 每台时的租金每台时的租金_ y2-B 每台时的租金每台时的租金 y3-C 每台时的租金每台时的租金则则 建立该线性规划的数学模型为：建立该线性规划的数学模型为：Min z=300y1+400y2+250y3 y1+2y2 50 y1+y2+y3 100 (LP2)y1,y2,y3 0LP1 与与LP2 是一对是一对对偶问题对偶问题9cj50 100 0 0 0 x1 x2 x3 x4
4、 x511 0 -1 0 0 -2 1 1cBixBi50 x10 x4bi50biaikyj=cj-zj100 x2050250 0 1 0 0 1 0 0 -50 0 -50 -27500cj-300 -400 -250 0 0 -M cBixBi-300 y1-250 y3bi50biaikyj=cj-zj50y1 y2 y3 y4 y5 y6 1 2 0 -1 0 10 -1 1 1 -1 -1 0 -50 0 -50 -250 -m+50 27500LP1最终单纯型表最终单纯型表LP2最终单纯型表最终单纯型表10求解问题求解问题 LP1得：得：X*=（x1,x2,x3,x4,x5)T
5、 =(50,250,0,50,0)T Max z=27500求解问题求解问题 LP2得：得：Y*=（y1,y2,y3,y4,y5,y6,)T =(50,0,50,0,0,0)TMin z=2750011二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式0,.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZ对称形式下线性规划原问题的一般形式为：对称形式下线性规划原问题的一般形式为：12 用用yi（i=1，2，.，m）代表第）代表第i种资源的种资源的估价，则其对偶问题的一般形式为：估
6、价，则其对偶问题的一般形式为：0,.2122112211112121112211mnmmnnn2mm222mmmmyyycyyycyyycyyyybybybminZaaaaaaaaats13用矩阵形式表示，对称形式的线性规划用矩阵形式表示，对称形式的线性规划问题的原问题为：问题的原问题为：YCYYmin wZ0A.X0XbAX.CXmaxtsts其对偶问题为：14原问题和对偶问题的关系可用下面表格的形式来表示：原问题和对偶问题的关系可用下面表格的形式来表示：原问题（求极大）c1 c2 cn x1 x2 xn右边原问题（求极小）b1 y1b2 y2bm ym a11 a12 a1n a21 a2
7、2 .a2n.am1 am2 .amnb1b2bm右边 c1 c2cm150 x0,x182x3x 122x4 x5x3xmax Z221212121例0y0,y0,y52y2y33yy 18y12y4ymin w3213231321其对偶问题：16三、非对称形式的原-对偶问题关系 例3、写出下述线性规划问题的对偶问题无约束333333333333300Zxxxbxaxaxabxaxaxabxaxaxaxcxcxc,max2122112222212111212111221117 0,0,0,0yyyyxcZmax0 x,0 x,0 x,xxx,xx33213333333322311322323
8、332222121223233322221211131333121211133332211 33233322xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxaxcxcxc对偶变量则上式可写为：其中令18 0y0y0y0ycyyyycyyyycyyyycyyyyybybybybmin w323333223231333332331333222113312223322,2121222122222121211112211aaaaaaaaaaaaaaaa其对偶问题为：19 0y,y0ycyyycyyycyyyy-y,y-yy333333133321132233222无约束由
9、此得令2122122221211111332211,min:,aaaaaaaaaybybybw20原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）无约束），（量变jjjxxxnj00.1xjjiijjiijjiijcyacyacyaj），个（件条束约n.1nijijijijijijbxabxabxai），个（件条束约m.1m变量无约束iiyyy00m)1,.,(iyiijjxczmaxiiybzmin21例例4 4、写对偶规划、写对偶规划minZ=4x1+2x2-3x3-x1+2x2 62x1 +3x3 9 x1+5x2-2x3=4x2,x3 022maxW=6y1+9
10、y2+4y3 -y1+2y2+y3=42y1 +5y3 2 3y2-2y3 -3y1 0,y2 0,y3自由自由23minZ=4x1+2x2-3x3 x1-2x2 -62x1 +3x3 9 x1+5x2-2x3=4x2,x3 0或将原问题变形为或将原问题变形为24maxW=-6y1+9y2+4y3 y1+2y2+y3=4-2y1 +5y3 2 3y2-2y3 -3y1 ,y2 0,y3自由自由对偶规划对偶规划25例例5 写出下面线性规划的对偶规划写出下面线性规划的对偶规划 min z=3x1+9x2+4x3 x1+2x2 +3x3=180 2x1-3x2 +x3 60 5x1+3x2 240
11、x1 0,x2 0 x3 无符号限制无符号限制26四、对偶问题的基本性质)n,.,2,1j(0 x)m,.,2,1i(bxa)P(xczmax jn1jijijn1jjj原问题：)m,.,2,1i(0y)n,.,2,1j(cya)D(ybmin wim1ijiijm1iji其对偶问题为：271、弱对偶性、弱对偶性n1jm1iiijjijybxcDPy,x）的可行解，则有：），（分别为（如果n1jm1iiijjm1im1im1iijn1jijijn1jijiin1jn1jm1iijn1jijjim1iijjjybxcyxay)xaybyxax)yaxc所以（因为证28弱对偶性的几个推论:原问题任
12、一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。解的目标函数值是其原问题目标函数值的上界。如原问题有可行解且其目标函数值无界（具有无界解），则其对偶问题无可行解；反之，对如原问题有可行解且其目标函数值无界（具有无界解），则其对偶问题无可行解；反之，对偶问题有可行解且其目标函数值无界，则其原问题无可行解（注意，本点性质的逆不成立）。偶问题有可行解且其目标函数值无界，则其原问题无可行解（注意，本点性质的逆不成立）。若原问题有可行解而其对偶问题无可行解，则
13、原问题目标函数值无界；反之，对偶问题有可若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。行解而其原问题无可行解，则对偶问题的目标函数值无界。29212minxxz0,02221212121xxxxxx无可行解 St例：例：302122maxyyw002211212121yyyyyy解有可行解，则必要无界而对偶问题：312、最优性、最优性的最优解则它们是）的可行解，且有：），（分别为（如果(D)(P),ybxcDPyxn1jm1iiijjij,3、强对偶性、强对偶性 若原问题及其对偶问题均具有可行解，则若原问题及
14、其对偶问题均具有可行解，则两者均有最优解，且它们最优解的目标函数两者均有最优解，且它们最优解的目标函数值相等。值相等。324 互补松弛性互补松弛性 在线性规划的最优解中，如果对应某一在线性规划的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严条件取严格等式；反之如果约束条件取严格不等式，则对应的对偶变量一定为零。格不等式，则对应的对偶变量一定为零。330y 0b-x a0b-x a0y 0y b-x am.1i2.220b-x a0y 2.220y b-x a2.212.21y bx c2.21y by x ax
15、 ciijn1jijijn1jijiiijn1jijijn1jijim1iiijn1jijn1jm1iiijjn1jm1iiim1iijn1jijjj 时，必有当时，必有由此当有，）式成立必须对所有，故（，因）（）式右端等式得应全为等式。由（）式中，故（又根据最优性）（由弱对偶性知证34证明同上，则如果有时，则如果有对偶问题同样有：0 x cy acy a0 x jjim1iijjim1iijj35求对偶问题的最优解。），（的最优解为例、已知线性规划,Tj321321321026X*1,2,3j0,x16x2x2x10 x2x xx4x3xmax Z3626w11Y1y1y42y2y32yy0
16、 x0 x0y0y1yy42y2y32yy1610212212），最优值，（，解得：变量等于零，即、二个约束的松弛，所以对偶问题的第一，因为解、对偶问题是*,min211212121121yyw37例：例：min =2x1+3x2+5x3+2x4+3x5 其对偶解其对偶解 y1=4/5 y2=3/5 Z=5 用对偶理论求用对偶理论求(P)的最优解的最优解x1+x2+2x3+x4+3x5 42x1-x2+3x3+x4+x5 3 xi 0 (i=1 5)(P)38解：解：(D)为为maxZ=4y1+3y2y1+2y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,
17、y2 039将将y1，y2 代入，知代入，知,为严格不等式为严格不等式 x2=x3=x4=0 x=(1,0,0,0,1)T Z=5由由y1，y20知原约束为等式知原约束为等式 x1+3x5=42x1+x5=340 综合以上对偶定理，互为对偶的两个线性规划问题的解之间的关系，只可能有三种情况：综合以上对偶定理，互为对偶的两个线性规划问题的解之间的关系，只可能有三种情况：（1)两个问题都存在最优解，且目标函数最优值相等；两个问题都存在最优解，且目标函数最优值相等；（2）两个问题都不存在可行解；）两个问题都不存在可行解；（3）一个问题无界，而另一个问题不存在可行解。）一个问题无界，而另一个问题不存在
18、可行解。41五、五、对偶问题的经济意义对偶问题的经济意义*m1iiin1jjj*wybxcz*Z*=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ym42Z=bi yi对对求求bi的偏导：的偏导：z*bi=yi*43yi*影子价格（影子价格（shadow price）。）。yi*的意义代表在资源最优利用条件的意义代表在资源最优利用条件下对单位第下对单位第i种资源的估价种资源的估价;bi 的单位改变的单位改变量所引起的目标函数值的改变量。量所引起的目标函数值的改变量。yi：反映：反映bi 的边际效益的边际效益(边际成本边际成本)44例例1中中y1=50,当机器台时数增加当机器台时数
19、增加1个单位时，工厂可增加利润个单位时，工厂可增加利润50个单位。个单位。45求解问题求解问题 LP1得：得：X*=（x1,x2,x3,x4,x5)T =(50,250,0,50,0)T Max z=27500求解问题求解问题 LP2得：得：Y*=（y1,y2,y3,y4,y5,y6,)T =(50,0,50,0,0,0)TMin z=2750046根据对偶问题的互补松驰性质中有根据对偶问题的互补松驰性质中有 生产过程中如果某种资源生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种在生产中
20、已消耗完毕。影子价格不为零时，表明该种在生产中已消耗完毕。，时，有当时，in1jjijiiin1jjijbxa0y0ybxa;47例例.某企业生产甲、乙两种产品，消耗的资源某企业生产甲、乙两种产品，消耗的资源等情况见下表所示，问应如何组织生产，使利等情况见下表所示，问应如何组织生产，使利润最大？润最大？甲 乙每天可用量资源单位成本AB2 31 225单位15小时5元/单位10元/小时产品售价（元）23 4048第一种模型第一种模型:),(*,*,max21212111116Y40z152555X015250203210 x54023ZTj434343对偶变量：，），（最优解：xxxxxxxxx
21、xxx49)1,1(*Y,40z55*X,0152253253ZmaxTj212121对偶变量：，），（最优解：xxxxxxx第二种模型第二种模型:50一般说对线性规划的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资一般说对线性规划的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。源的恰当估价，这种估价直接涉及资源的最有效利用。51第二节第二节 敏感性分析敏感性分析 什么是敏感性分析什么是敏感性分析 敏感性分析对管理者的重要性敏感性分析对管理者的重要性 继续研究伟恩德公司案例继续研究伟恩德公司案例 目标函数系数的敏感
22、性分析目标函数系数的敏感性分析 右端项的影子价格分析右端项的影子价格分析 同时改变右端项同时改变右端项52什么是敏感性分析什么是敏感性分析 数学模型只是实际问题的一个粗略的抽象数学模型只是实际问题的一个粗略的抽象最优解一般只是针对某一特定的数学模型最优解一般只是针对某一特定的数学模型管理者要对未来做各种假设，在这些假设下测试可能产生的结果，通过对各种结果深入分析管理者要对未来做各种假设，在这些假设下测试可能产生的结果，通过对各种结果深入分析来指导决策。来指导决策。通常，在取得最初版本模型的最优解之后，进行分析才能取得对问题深入的认识通常，在取得最初版本模型的最优解之后，进行分析才能取得对问题深
23、入的认识这种分析称为这种分析称为what-if分析分析 或敏感性分析（或敏感性分析（Sensitivity Analysis）53敏感性分析对管理者的重要性敏感性分析对管理者的重要性模型参数是粗略的估计值获取所需数据必须付出相当多的时间与心血有些因素只有在研究模型参数是粗略的估计值获取所需数据必须付出相当多的时间与心血有些因素只有在研究完成后才能精确测量完成后才能精确测量问题的条件发生了变化，即使不求解，也可表明模型参数的变化是否会改变最优解问题的条件发生了变化，即使不求解，也可表明模型参数的变化是否会改变最优解当模型特定的参数反映管理政策决策时，当模型特定的参数反映管理政策决策时，what-
24、if分析可以表明改变这些决策对结果的影分析可以表明改变这些决策对结果的影响，从而有效指导管理者作出最终的决策响，从而有效指导管理者作出最终的决策54继续研究伟恩德公司案例继续研究伟恩德公司案例伟恩德玻璃制品公司生产高质量的玻璃门窗，拥有伟恩德玻璃制品公司生产高质量的玻璃门窗，拥有3个工厂。由于收入下降，高层管理者决个工厂。由于收入下降，高层管理者决定修整公司的生产线。不盈利的产品将停止生产，将生产能力转移到有较大销售潜力的两个定修整公司的生产线。不盈利的产品将停止生产，将生产能力转移到有较大销售潜力的两个新产品：新产品：产品产品1：8英尺的铝框玻璃门英尺的铝框玻璃门 产品产品2：4X6英尺的双
25、把木框窗英尺的双把木框窗55工工 厂厂每个产品的生产时间每个产品的生产时间（小时）（小时）每周可用的生产时间（小时）每周可用的生产时间（小时）门门 窗窗123 00 23 241218单位利润（元）单位利润（元）300 500表1 伟恩德玻璃制品公司产品组合问题的数据56NoImage代数模型代数模型570,018231224500300max21212121xxxxxxxxz58结 论运筹学小组使用这个方法找到了最优解：Wyndor Glass 公司每周生产产品公司每周生产产品1和产品和产品2的数量分别是的数量分别是2批和批和6批，带来的总利润是批，带来的总利润是36000元。根元。根据这个
26、模型两种产品生产的其它组合都没有这种组合的盈利多。据这个模型两种产品生产的其它组合都没有这种组合的盈利多。59what-if 分析之前，最初伟恩德公司问题电子表格模型及最优解分析之前，最初伟恩德公司问题电子表格模型及最优解Excel60和管理层沟通后伟恩德公司需要进一步研究的问题（即：what-if分析）：1.1.如果在伟恩德公司的新产品中，有一个单位利润的估计值是不准确的，将会发生怎样的如果在伟恩德公司的新产品中，有一个单位利润的估计值是不准确的，将会发生怎样的情况？情况？2.2.如果在伟恩德公司的两种新产品的单位利润的估计都是不准确的，又将会怎样？如果在伟恩德公司的两种新产品的单位利润的估
27、计都是不准确的，又将会怎样？3.3.如果改变伟恩德公司一个工厂可用于生产新产品的时间，会对结果产生什么影响？如果改变伟恩德公司一个工厂可用于生产新产品的时间，会对结果产生什么影响？4.4.如果三个工厂每周可用于生产新产品的时间同时改变，又会对结果产生什么影响？如果三个工厂每周可用于生产新产品的时间同时改变，又会对结果产生什么影响？61目标函数系数的敏感性分析目标函数系数的敏感性分析只有一个目标函数的变动目标函数系数同时变动的影响62线性规划模型的许多参数，都只是对实际数据的大致估计，而不可能在研究的时候就获得精确的数值。What-if，更具体地说，灵敏度分析可以表现出每一个估计值需要精确到何种
28、程度，才能避免得出错误的最优解。6364 我们以下面的例题来看一下我们以下面的例题来看一下cj的变化是如何来影响最优解的的变化是如何来影响最优解的:例例1、某工厂在计划期内安排甲、乙两种产品，已知生产单位产品所需设备和某工厂在计划期内安排甲、乙两种产品，已知生产单位产品所需设备和A、B原材原材料消耗和所获利润如下表所示料消耗和所获利润如下表所示 只有一个目标函数的变动65甲乙资源限量设备11300台时原料A 21400千克原料B01250千克利润（元）50100 问：工厂应分别生产甲、乙产品各多少，才能使工厂获利最多？问：工厂应分别生产甲、乙产品各多少，才能使工厂获利最多？66设：甲设：甲 x
29、1，乙乙 x2该线性规划的模型为：该线性规划的模型为：max z=50 x1+100 x2 x1+x2 300 2x1+x2 400 (LP1)x2 250 x1 0,x2 0求解问题求解问题 LP1得：得：X*=（x1,x2,x3,x4,x5)T=(50,250,0,50,0)T Max z=2750067用图解的方法定出利润变化的范围用图解的方法定出利润变化的范围z直线直线E的方程为的方程为:E:x1+x2=300 x2=-x1+300F:x2=0 x1+250G:x2=-2x1+400目标函数目标函数:z=c1x1+c2x2 也可表示为也可表示为:x2=x1+c2-c1c2z100200
30、300100200300 x1x2直线直线G（原料（原料A的约束）的约束）直线直线E（设备约束）（设备约束）50 x1+100 x2=27500直线直线F68点仍然是最优解。之间变化时，元到的利润在不变时，单位产品即当解得：不变，则有假设当B1000100c100c00100c1100c0cc121122169点仍然是最优解。元时，利润只要大于等于的不变时，而单位产品即当解得：不变，则有假设的变化范围：计算B5050cc500c50150cc1221270问题问题1.1.如果在伟恩德公司的新产品中，有一个单位利润的估计值是不准确的，将会发生怎样如果在伟恩德公司的新产品中，有一个单位利润的估计值
31、是不准确的，将会发生怎样的情况？的情况？71门的单位利润PD=300降到PD=200，而最优解不变门的单位利润PD=300增加到D=500，而最优解不变门的单位利润从PD=300增加到PD=1000，最优解改变72在伟恩德的例子中系统改变门的单位利润得到数据表在伟恩德的例子中系统改变门的单位利润得到数据表 73最初伟恩德模型用最初伟恩德模型用Excel Solver产生的灵敏度分析的一部分，其中最后三栏表示了门窗单位利产生的灵敏度分析的一部分，其中最后三栏表示了门窗单位利润的最优域。润的最优域。运用灵敏度报告来寻找允许变化范围运用灵敏度报告来寻找允许变化范围74642 0 1 2 3 4DWP
32、D=0（利润（利润=0D+500W）（2,6）是）是0PD750的最优解的最优解PD=300（利润（利润=300D+500W）PD=750（利润（利润=750D+500W）75目标函数的两个系数的允许变化范围都很大，因此，尽管门窗的单位利润（300,500）可能仅仅是实际值的一个初略估计，我们也可以相信，这一估计值对最优解的正确性不会有太大的影响。在一些线性规划模型中，目标函数系数微小的变动都可能会影响最优解。这样的系数称为敏感参数。对敏感参数必须格外小心，尽量取得这些数据的精确值。76如何在不重新求解模型的条件下，确定如果目标函数的几个系数同时变化，可能造成对最优如何在不重新求解模型的条件下
33、，确定如果目标函数的几个系数同时变化，可能造成对最优解的影响解的影响如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？目标函数系数同时变动的影响77继续研究伟恩德公司案例继续研究伟恩德公司案例门，窗的单位利润分别被改PD=450,PW400，但是最优解不变78门，窗的单位利润分别被门，窗的单位利润分别被PD=600,PW300，从而最优解改变，从而最优解改变79伟恩德例子中系统改变门，窗单位利润得到的数据表伟恩德例子中系统改变门，窗单位利润得到的数据表 80百分之百法则百分之百法则目标
34、函数系数同时变动的百分之百法则目标函数系数同时变动的百分之百法则(The 100 percent rule for simultaneous changes in objective function coefficients)：如果目标函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。81改变）（可以确定最优解没有总和）（占允许增加量的百分比元元）（占允许增加量的百分比元元%66.66%33.33%300400500100400500:%33.
35、33%450300450100450300:WPPD82继续研究伟恩德公司案例继续研究伟恩德公司案例当门，窗的单位利润的估计值分别改为当门，窗的单位利润的估计值分别改为PD525，PW350，刚好处在百分百法则所允许的临界点上，刚好处在百分百法则所允许的临界点上，（，（D,W）（）（2，6）还是最优解，但同时，目标函数直线上在（）还是最优解，但同时，目标函数直线上在（2，6）（）（4，3）之间的所有点均）之间的所有点均为最优解为最优解 WD02462468Production rate for doorsProduction rate for windowsFeasible region10O
36、bjective function line now is Profit=$3150=525 D+350 W since PD=$525,PW=$350.Entire line segment is optimal(4,3)(2,6)883当门，窗的单位利润的估计值当门，窗的单位利润的估计值改为改为PD$150，PW$250，（最初解的一半）作图法可知（最初解的一半）作图法可知（D,W）（）（2，6）还是最优）还是最优解，尽管百分之百法则表示最解，尽管百分之百法则表示最优解有可能变动优解有可能变动 02462468(2,6)Feasible regionOptimal solutionProd
37、uction rate for doorsProduction rate for windowsProfit=$1800=150D+250 W8WD84可用于确定在保持最优解不变的条件下，目标函可用于确定在保持最优解不变的条件下，目标函 数系数的变动范围数系数的变动范围 百分百法则通过将允许的增加或减少值在各个系百分百法则通过将允许的增加或减少值在各个系 数之间分摊，从而可以直接显示出每个系数的允数之间分摊，从而可以直接显示出每个系数的允 许变动值许变动值 线性规划研究结束以后，如果将来条件变线性规划研究结束以后，如果将来条件变 化，致使目标函数中一部分或所有系数都发生变动，百化，致使目标函数
38、中一部分或所有系数都发生变动，百 分百法则可以直接表明最初最优解是否保持不变分百法则可以直接表明最初最优解是否保持不变 百分之百法则的作用百分之百法则的作用85右端项的影子价格分析右端项的影子价格分析分析函数约束右端值函数约束右端值变动的原因是不能得到模型的 参数的精确值，只能对其作大略的估计。因此要知 道万一这些估计不准确产生的后果 更主要的理由是因为这些常数往往不是由外界决定 的而是管理层的政策决策管理层的政策决策。在建模并求解后，管理 者想要知道如果改变这些决策是否会提高最终收益 影子价格分析就是为管理者提供这方面的信息影子价格分析就是为管理者提供这方面的信息 86假定前例中的假定前例中
39、的A设备台时数增加了设备台时数增加了10个台时个台时,共有共有310个台时，此时约束条件就变为个台时，此时约束条件就变为 310 xx2187100200300100200300 x1x2*50 x1+100 x2=27500BC*B/(60,250)为最优解为最优解MAX Z=28000元元其影子价格为其影子价格为:500/10=5088 如果原材料如果原材料A增加增加10千克千克,将会对最优解和最优值产将会对最优解和最优值产生影响什么生影响什么?100200300100200300 x1x250 x1+100 x2=27500最优解仍最优解仍然为然为B点点89利博公司问题利博公司问题最初的
40、利博公司例子的电子表格模型及其最优解最初的利博公司例子的电子表格模型及其最优解90利博公司，由利博公司，由Excel Solver产生的灵敏度报告中涉及函数约束的那一部分，其中的第四栏给出产生的灵敏度报告中涉及函数约束的那一部分，其中的第四栏给出了影子价格了影子价格 91给管理层的信息给管理层的信息影子价格分析提供了许多有价值的信息，因为该分析表明约束右端值每增加一个单位，最优的目标函数值会增加多少。如果影子价格是负的，那就表明约束右端值每减少一个单位，最优目标函数值会降低的量。如果影子价格等于零,则其最优目标函数值不变.但这些信息只有在约束右端值的数值变动不大的情况下才有效。现在我们讨论为保
41、持影子价格有效，约束右端值数值的变动范围。9293改变工厂改变工厂2每周可用于生产新产品工作时间生成的数据表每周可用于生产新产品工作时间生成的数据表 继续研究伟恩德公司案例继续研究伟恩德公司案例94工 厂工 厂 2 约 束 右 端 值 的 可 行 域约 束 右 端 值 的 可 行 域6RHS18的图形解释的图形解释 继续研究伟恩德公司案例继续研究伟恩德公司案例 024624682 W=6 Profit=300(4)+500(3)=$2,7002 W=18 Profit=300(0)+500(9)=$4,5002 W=12 Profit=300(2)+500(6)=$3,600(4,3)(2,6
42、)Feasibleregion for original problemLine BLine A(D=4)Line C(3 D+2 W=18)10(0,9)DWProduction rate for doorsProduction rate for windows9596管理层可以利用影子价格来评价改变工作时间的各种决策，但是要求这些决策改变的幅度不大，在影子价格的有效域内 97同时改变右端项同时改变右端项如果，多个约束右端值同时变动，那么管理层又如果，多个约束右端值同时变动，那么管理层又该如何来评估可能造成的影响呢？该如何来评估可能造成的影响呢？这种问题很常见！这种问题很常见！98同时改变几
43、个或所有函数约束的约束右端值同时改变几个或所有函数约束的约束右端值，如果这些变动的幅度不大，那么可以用影子价格预测变动产生的影响。如果所有的百分比之和不超过百分之一百，那么，影子价格还是有效的，如果所有的百分比之和超过百分之一百，那就无法确定影子价格是否有效 百分之百法则百分之百法则99修正的伟恩德问题，其中一个小时的工作时间从工厂修正的伟恩德问题，其中一个小时的工作时间从工厂3移到工厂移到工厂2，模型的求解。，模型的求解。伟恩德公司案例研究伟恩德公司案例研究100不断将工厂不断将工厂3的工作时间转移到工厂的工作时间转移到工厂2，从而生成数据表，从而生成数据表 继续研究伟恩德公司案例继续研究伟
44、恩德公司案例101按照百分之百法则，计算如下:%33.33%66.16%617181001718:%66.16%612131001312:32总和）（占允许增加量的百分比）（占允许增加量的百分比RHSRHS102因为变动百分比之和33.33%小于100%,所以用影子价格来预测这些变动的影响是有效的。上面求得的变动百分比之和为33.33%，表明即使将原先的变动扩大3倍，也不会使影子价格失效，即：影子价格依然有效）总和）（占允许增加量的百分比）（占允许增加量的百分比(%100%50%615181001518:%50%612151001512:32RHSRHS103案例研究案例研究 案例：案例：1.超级食品公司的广告混合问题 2.邦联航空公司作业作业:下一讲：下一讲：运输问题和指派问题104The End of Session 2
