第三讲 线性规划的灵敏度分析与最优解的解释

1、物流管理系物流管理系 薛伟霞薛伟霞Par问题的数学描述nmax 10S+9DnS.t. S S，D0D06301107 DS6006521DS708321DS13541101DS切割与印染缝合成型检查与包装灵敏度分析灵敏度分析n研究当一个线性规划问题中的系数发生变化时，研究当一个线性规划问题中的系数发生变化时，其对目标函数最优解的影响程度。其对目标函数最优解的影响程度。n1 1如果目标函数的系数发生变化，对最优解会如果目标函数的系数发生变化，对最优解会产生什么影响？产生什么影响？n2 2如果改变约束条件右边的值，对最优解会产如果改变约束条件右边的值，对最优解会产生什么影响？生什么影响？主要内容

2、主要内容n灵敏度分析简介灵敏度分析简介n图解法灵敏度分析图解法灵敏度分析n灵敏度分析：计算机求解灵敏度分析：计算机求解n多于两个决策变量的情况多于两个决策变量的情况灵敏度分析简介（1）n问题问题如果我们要用如果我们要用LPLP模型去解决实际问题，模型中模型去解决实际问题，模型中的系数就不可能是一成不变的。这些系数的变化会对模的系数就不可能是一成不变的。这些系数的变化会对模型的最优解产生什么样的影响呢？型的最优解产生什么样的影响呢？6301107DS6006521DS708321DS13541101DS切割与印染缝合成型检查与包装max 10S+9DS.t.S，D08.5灵敏度分析简介（2）n问

3、题问题模型中的系数哪个更能左右最优解？模型中的系数哪个更能左右最优解？6301107DS6006521DS708321DS13541101DS切割与印染缝合成型检查与包装max 10S+9DS.t.S，D0(6.67-14.29)(8.9-9.25)灵敏度分析简介（3）n问题问题右端值变化对最优解有什么影响？右端值变化对最优解有什么影响？6301107DS6006521DS708321DS13541101DS切割与印染缝合成型检查与包装max 10S+9DS.t.S，D0利润利润图解法灵敏度分析n目标函数系数变化目标函数系数变化多系数同时改变多系数同时改变n右端项改变右端项改变目标函数系数n问

4、题问题目标函数系数变化会对目标函数系数变化会对ParPar公司的最优公司的最优产量产生什么样的影响。产量产生什么样的影响。n目标函数的最优范围目标函数的最优范围目标函数系数在什么范目标函数系数在什么范围内变化时，模型的最优解保持不变。围内变化时，模型的最优解保持不变。目标函数系数目标函数系数n第一步：目标函数直线斜率的范围第一步：目标函数直线斜率的范围n直线直线B B斜率斜率目标函数的斜率目标函数的斜率直线直线A A的斜率的斜率n第二步：目标函数系数的范围第二步：目标函数系数的范围nP=CSS+CDD10723目标函数的斜率5 .133 . 6SC29.1467. 6DC10723DSCC另一

5、例目标函数继续旋转23DSCC多系数同时改变10723DSCC假设标准袋的利润增加到假设标准袋的利润增加到1313美元，高档袋的利润减少到美元，高档袋的利润减少到8 8美元。美元。5 .133 . 6SC29.1467. 6DC新的目标函数的斜率：新的目标函数的斜率：625. 1813DSCC右端项n假设假设ParPar公司的切割印染部门又多出了公司的切割印染部门又多出了1010个小时的可工个小时的可工作时间。作时间。n新的约束条件：新的约束条件：6401107 DS运用图解法新的最优解新的最优解S=527.5S=527.5，D=270.75D=270.75。新的目标函数值新的目标函数值101

6、0527.5+9527.5+9270.75270.75=7711.75=7711.75美元，美元，利润增量利润增量7711.75-7711.75-7668.00=43.757668.00=43.75美元。美元。利润增加率利润增加率43.75/10=4.37543.75/10=4.375美元。美元。对偶价格n约束条件右端值每增加一个单位引起的最优解的增加量。约束条件右端值每增加一个单位引起的最优解的增加量。n对偶价格可以用来求出当某个约束条件右端值变化一个单位对偶价格可以用来求出当某个约束条件右端值变化一个单位时目标函数值将会有什么变化。时目标函数值将会有什么变化。n对偶价格只适用于约束条件的右

7、侧值变化比较小的情况。对偶价格只适用于约束条件的右侧值变化比较小的情况。n任何非束缚性约束条件的对偶价格都是任何非束缚性约束条件的对偶价格都是0 0。n负的对偶价格告诉我们，如果使右端值增加，目标函数值不负的对偶价格告诉我们，如果使右端值增加，目标函数值不会增加，反而会减少。在最小化问题中，目标函数结果变得会增加，反而会减少。在最小化问题中，目标函数结果变得更坏意味着总成本的增加。更坏意味着总成本的增加。n影子价格影子价格每增加一个单位的约束条件右端值最优解的变每增加一个单位的约束条件右端值最优解的变化量。一般来说，对于最大化问题，影子价格和对偶价格相化量。一般来说，对于最大化问题，影子价格和

8、对偶价格相同；对于最小化问题，影子价格是对偶价格的相反数。同；对于最小化问题，影子价格是对偶价格的相反数。主要内容主要内容n灵敏度分析简介灵敏度分析简介n图解法灵敏度分析图解法灵敏度分析n灵敏度分析：计算机求解灵敏度分析：计算机求解n多于两个决策变量的情况多于两个决策变量的情况灵敏度分析：计算机求解n使用管理科学家软件求解使用管理科学家软件求解ParPar公司的线性规划问公司的线性规划问题。题。目标函数最优解最优解减少的成本减少的成本目标函数的每个系数应提高多少，目标函数的变量值才能是正数松弛/剩余变量对偶价格目标系数范围右端值范围对偶价格适用范围的限制条件多系数同时变化100%法则n假设，假

9、设，ParPar公司的会计部门发现原来高档袋和标准袋的利公司的会计部门发现原来高档袋和标准袋的利润计算润计算分别为分别为1010美元和美元和9 9美元有误，正确的利润分别美元有误，正确的利润分别应该是应该是11.5011.50美元和美元和8.258.25美元。美元。n允许增加量允许增加量对于目标函数的系数，在不超过最优范对于目标函数的系数，在不超过最优范围的情况下，系数可能增加的最大量；围的情况下，系数可能增加的最大量；n允许减少量允许减少量在不低于最优范围下限的情况下，系数在不低于最优范围下限的情况下，系数可能减少的最大量。可能减少的最大量。目标函数系数的100%法则n对所有变化的目标函数系

10、数，计算其占允许增加量和允许减少量对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到的百分比之和。如果和没有达到100%100%，最优解就不会改变。，最优解就不会改变。目标函数系数目标函数系数S S的上限是的上限是13.499 13.499 9393，允许增加量：，允许增加量：上限上限- -目前值目前值=13.49993-10=3.49993=13.49993-10=3.49993。标准袋。标准袋的利润增加到的利润增加到11.5011.50美元，增加美元，增加了（从了（从1010美元到美元到11.5011.50美元）美元）1.501.50美元。占总允许增加量的

11、美元。占总允许增加量的（1.50/3.499 931.50/3.499 93）100%=42.86%100%=42.86%。D D的下限是的下限是6.66676.6667，允许减少量：，允许减少量：目前值目前值- -下限下限=9-6.6667 =9-6.6667 =2.33330=2.33330。高档袋的利润减少了。高档袋的利润减少了0.750.75（从（从9 9美元到美元到8.258.25美元）美美元）美元，占允许减少量的元，占允许减少量的（0.75/2.333 300.75/2.333 30）100%=32.14%100%=32.14%。可行增加（可行增加（42.86%42.86%）和可行

12、减少（）和可行减少（32.14%32.14%）百分率变化的和）百分率变化的和是是75.00%75.00%。约束条件右端值的100%法则n对所有变化的右端值，计算其占允许增加量和允许减少对所有变化的右端值，计算其占允许增加量和允许减少量的百分比之和。如果没有达到量的百分比之和。如果没有达到100%100%，对偶价格就不会，对偶价格就不会改变。改变。n例：假设切割与印染部门能够获得额外的例：假设切割与印染部门能够获得额外的2020小时时间，小时时间，同时成型部门能够获得额外的同时成型部门能够获得额外的100100小时时间。对偶价格小时时间。对偶价格是否适用？是否适用？计算机输出的解释 M&

13、D公司的最小化问题 min 2A+3B min 2A+3B s.t. s.t. 1A 125 1A 125 产品产品A A的需求量的需求量 1A + 1B 350 1A + 1B 350 总产量总产量 2A + 1B 600 2A + 1B 600 生产时间生产时间 A A，B 0B 0时间约束总产量约束关于对偶价格的解释n小于等于型约束条件的对偶价格总是大于或等于小于等于型约束条件的对偶价格总是大于或等于0 0的，因为的，因为增加其右端值不会使目标函数变得更坏。增加其右端值不会使目标函数变得更坏。n大于等于型约束条件的对偶价格总是小于或等于大于等于型约束条件的对偶价格总是小于或等于0 0的，

14、因为的，因为增加其右端值不会对最优解有所改进。增加其右端值不会对最优解有所改进。n当约束条件的右端值表示某种资源的可利用量时（沉没成当约束条件的右端值表示某种资源的可利用量时（沉没成本），对偶价格通常可以解释为公司对额外支付一单位这种本），对偶价格通常可以解释为公司对额外支付一单位这种资源所愿意提供的金额。资源所愿意提供的金额。n管理者经常会遇到是否有必要引进新技术的问题，而一般新管理者经常会遇到是否有必要引进新技术的问题，而一般新技术的开发或购买都是为了节约资源。在这种情况下，对偶技术的开发或购买都是为了节约资源。在这种情况下，对偶价格可能对问题的解决有所帮助，它可以帮助我们了解节约价格可能

15、对问题的解决有所帮助，它可以帮助我们了解节约这些资源会为我们带来多大的利益，进而决定这项新技术的这些资源会为我们带来多大的利益，进而决定这项新技术的价值。价值。多于两个决策变量的情况nParPar公司原来问题的模型公司原来问题的模型6301107DS6006521DS708321DS13541101DS切割与印染缝合成型检查与包装max 10S+9DS.t.S，D0Par公司管理决策上的改变n假设管理层希望生产一种轻便的、可以被球手随身携带假设管理层希望生产一种轻便的、可以被球手随身携带的球袋模型。设计部门计算得出，每个轻型袋需要的球袋模型。设计部门计算得出，每个轻型袋需要0.80.8小小时进

16、行切割印染，时进行切割印染，1 1小时缝合，小时缝合，1 1小时成型，小时成型，0.250.25小时检小时检验和包装。因为这种设计是独一无二的，管理层认为在验和包装。因为这种设计是独一无二的，管理层认为在当前销售期内每个轻便袋的利润可达当前销售期内每个轻便袋的利润可达12.8512.85美元。美元。n令令L L为轻便袋的产量为轻便袋的产量修正的Par公司问题6308.01107LDS60016521LDS7081321LDS13525.041101LDS切割与印染缝合成型检查与包装max 10S+9D+12.85LS.t.S，D，L0多重最优解的情况n假设我们使假设我们使D D的系数正好增加的

17、系数正好增加1.150031.15003美元。美元。增加新的约束条件n假设管理者在审核了上述的解决方案后发现，他们会放假设管理者在审核了上述的解决方案后发现，他们会放弃所有不生产高级袋的方案，并要求高级袋的产量至少弃所有不生产高级袋的方案，并要求高级袋的产量至少要达到标准袋产量的要达到标准袋产量的30%30%。nD0.3SD0.3S 或者或者 -0.3S+D 0-0.3S+D 0 课外练习n牧草农场位于肯塔基州列克星敦。农场正在实验一种新牧草农场位于肯塔基州列克星敦。农场正在实验一种新的赛马食品。赛马食品有以下三种，由普通饲料，富含的赛马食品。赛马食品有以下三种，由普通饲料，富含维生素的燕麦饲

18、料和一种新的含维生素和矿物质的食品维生素的燕麦饲料和一种新的含维生素和矿物质的食品添加剂饲料。这些高营养食品的各组成要素的成本如表添加剂饲料。这些高营养食品的各组成要素的成本如表3-13-1所示。我们可以看到，每磅普通饲料中含所示。我们可以看到，每磅普通饲料中含0.80.8单位单位A A，1 1单位单位B B和和0.10.1单位单位C C，一匹马一天的最少进食，一匹马一天的最少进食3 3单位单位A A，6 6单位单位B B，4 4单位单位C C。为了保持马的体型，总摄入量不可以。为了保持马的体型，总摄入量不可以超过超过6 6磅。农场希望找到一种饲料组合，可以满足马一磅。农场希望找到一种饲料组合，可以满足马一天的营养需要，又可以使总成本最低。天的营养需要，又可以使总成本最低。课外练习表表3-13-1牧草农场饲料的营养值和成本值牧草农场饲料的营养值和