ch3线性规划的灵敏度分析

1、 本章安排如下： 灵敏度分析是研究当一个线性规划问题中的系数发生变化时，函数最优解受影响的程度。 因此借助灵敏度分析，我们可以知道： （1）如果目标函数的系数发生了变化，对最优解所产生的影响 （2）如果改变约束条件右边的值，对最优解产生的影响 灵敏度分析是研究系数的改变对最优解的影响，所以必须首先计算出原线性规划的答案，也因此灵敏度分析又称为后最优分析 灵敏度分析对于一个经营者必须在动态环境中对系数进行不精确估计具有很重要的作用。 对于双变量的线性规划问题，当目标函数的系数或约束条件右边的值变化时，可用图解法进行灵敏度分析 以第二章的例1为例，我们分析目标系数在什么范围内变化时，目标函数的值不

2、变3.2.1 目标函数系数 第二章例1的可行域和目标函数可行域直线B（与成型约束条件重合）1S+2/3D=708目标函数线 10S+9D 直线A(与切割印染约束直线重合）7/10S+1D=630可行域目标函数线只要在区域范围内旋转，极点（3）依然是最优解直线B的斜率目标函数的斜率直线A的斜率直线B直线A目标函数直线A：（与切割印染约束直线重合） 7/10S+1D=630 其斜截式为： D- 7/10S+630直线B：（与成型约束直线重合）1S+2/3D=708 其斜截式为： D=-3/2 记 为标准袋的利润， 为高档袋的利润，则目标函数写作 其斜截式为：故 DCSCDCSCPDSDDSCPSC

3、CD10723DSCC直线B的斜率目标函数的斜率直线A的斜率计算标准袋利润的最优范围： 假设高档袋利润 ,代入公式，得到 解此不等式，我们得到标准袋利润的最优范围： 同理，假定标准袋利润不变，即可得出高档袋利润的最优范围： 注：画函数线的方法，只适用于单一目标函数系数改变的情况注：画函数线的方法，只适用于单一目标函数系数改变的情况 9DC10723DSCC107923SC5 .133 . 6SC29.1467. 6DC 以第二章的例1为例，假设它的第一个约束条件切割印染的右侧值从630变化到640，写作： 7/10S+1D640,如图所示： 7/10S+1D=640新的可行域最优解（S=527

4、.50D=270.75)）新的最优解 S=527.5, D=270.75新的目标函数值 10527.59270.757711.75利润的增量为 7711.75766843.75因此利润的增加率为 43.75/104.375即每增加一小时，利润增加4.375这就是对偶价格的定义：约束条件右侧每增加一个单位导致的最优解的增加量。约束条件右侧每增加一个单位导致的最优解的增加量。注：对偶价格只适用于只适用于约束条件右侧值变化比较小的情况对第二章的例1，使用Management Scientist进行敏感分析，结果如下 在取近似解之后，我们得到最优解S=540,D=252;目标函数值是7668。缩减费用

5、均为0（因为两个变量的值均为正数）缩减费用：如果使目标函数变量值为正，目标函数的系数应该提高的值 束缚性的约束条件（1，3），约束条件2、4各有120、18的松弛，这个模型中的松弛也称为未使用的生产能力。 对偶价格：约束条件1、3的对偶价格说明1、3右侧值每增加一个单位，目标函数的值就会分别增加4.375、6.936；约束条件2、4都有松弛，对偶价格为0，即使增加也不会提高目标函数的值。 第一个变量S的变化范围（6.30，13.50），即只要高档袋的利润在6.3013.50，产量S=540,D=252就仍然是最优解 第二个变量D的变化范围（6.67，14.29），即只要标准袋的利润在6.641

6、4.29，产量S=540,D=252就仍然是最优解 这部分是对偶价格的适用范围。只要约束条件的右侧值只要约束条件的右侧值在系统给出的上限与下限之间在系统给出的上限与下限之间，就可以通过对偶变量来计算增加约束条件右侧的值对模型最优解的值影响。 前面讲的灵敏度分析方面的信息是针对单系数变化的情况。对于多系数改变的问题，可用百分之百定理 定义两个词组： 可行增加：在单系数容许范围中，上限与当前值的差。 可行减少：在单系数容许范围中，当前值与下限的差。 可见第一个变量S的上限是13.49993，因此，可行增加是3.4999313.4999310，现在标准袋的利润增加到 11.50，增加了（从10增加到

7、11.50）1.50。实际增加占可行增加的比例：（1.50/3.49993）10042.86；同理，D的下限6.66670，可行减少2.333309-6.66670。按百分率的观点，高档袋的利润减少了0.75，占可行减少的（ 0.75 / 2.33330 ）10032.14 对于所有变化的目标函数的系数，求其占可行增加和可行减少的百分率的绝对值的和，如果和没有超过100，则最优解不变 对于所有变化的约束条件的右侧的值，求这些值占可行增加和可行减少的百分率的绝对值的和，如果和没有超过100，则对偶价格不变先引入两个名词： 相关成本：一个由决策变量资源的变化而影响的资源成本 沉没成本：不考虑决策变

8、量的资源数量而必须被支付的资源成本 相关成本都必须在目标函数的系数中反映出来，沉没成本不受目标函数的系数影响资源成本是沉没的 对偶价格是你想为额外增加一个单位资源而乐意付出的最大量资源成本是相关的对偶价格是你想为一个单位资源在正常的成本上乐意再增加的最大额外数量。3.4.1 对第二章的例1进行修改 假设该公司准备增加生产一种小型袋，每个小型袋需要0.8小时进行切割印染，1小时缝合，1小时成型，0.25检验和包装，每个小型袋的利润可达12.85增加决策变量：小型袋的数量为L，模型修改如下 最大化： 10S+9D+12.85L12.85L 约束条件 0.75S+ 1D+ 0.8L630 0.5S+

9、0.83333D+ 1L600 1S+ 0.66667D+ 1L708 0.1S+ 0.25D +0.25L135 S,D,L0D的缩减费用是1.15003也就是说：高档袋的费用增加1.15003后，D在最优解时的值就不会是0了缩减费用：使得变量为正数时，相应的目标函数系数的增加量表示将高档袋的产量由原来的30提高1个单位，总利润将减少1.38在现有20的基础上每增加1单位产量，目标函数的值增加0.89。同时这种只适用于约束值不超过156这节我们举一个三变量的最小化问题： 牧草农场正在试验一种新的赛马食品。赛马食品有以下三种，有普通饲料、富含维生素的燕麦饲料和一种新的含维生素和矿物质的食品添加

10、剂饲料。这些高营养食品的各组成要素的营养值和成本值如图所示 一匹马一天的最小进食量3单位A，6单位B，4单位C。为了保持马的体型，总摄入量不可以超过6磅。农场希望找到一种饲料组合，可以满足马的一天营养，又可以使总成本最低饲料成分饲料成分普通饲料普通饲料高营养燕麦高营养燕麦饲料添加剂饲料添加剂A成分0.80.20.0B成分1.01.53.0C成分0.10.62.0每磅成本美元0.250.503.00定义三个决策变量： S普通饲料的量 E 高营养燕麦的量 A饲料添加剂的量成本最小的目标函数： 最小化：0.25S+0.50E+3A 约束条件 0.8S+ 0.2E 3 A成分 1.0S+ 1.5E+3

11、.0A6 B成分 0.1S+ 0.6E+2.0A4 C成分 S+ E+ A6 总量 S,E,A0对偶价格为负，说明相应的增加会对目标函数产生消极影响，对于最小化问题，消极意味着成本增加最优解所对应的目标函数系数的变化范围对偶价格的适用范围电子通信公司生产双向便携式无线电话机，公司开发了一种新的产品，通信范围覆盖25英里，适合企业和个人使用。新产品的分销渠道是； 1.航海器材经销店。 2.商用器材经销店。 3.全国范围的连锁零售商店 4.直接邮购 因为分销和促销的价格不同，产品的利润也因销售渠道而异。此外广告成本也因渠道的不通有所差异，分销渠道分销渠道单位销售利润单位销售利润单位广告成本单位广告

12、成本单位销售时间单位销售时间航海分销店90102商业分销店8483全国连锁店7093直接邮购6015无公司的广告预算是5000美元，每个分销点的最大销售时间是1800。管理层决定现阶段大约制造600件产品。还有一点，全国连锁零售商店要求最少有150件产品在这个渠道内销售。 目标：销售利润最大。（合理分配各渠道的销售量、销售时间以及广告预算）定义四个决策变量： M通过航海器材分销店销售的产品的数量 B通过商用器材分销店销售的产品的数量 R通过全国范围的连锁零售商店销售的产品数量 D通过直接邮购销售的产品数量目标：利润最大化 90M+84B+70R+60D 约束条件(广告预算、销售总时间、生产能力、连锁零售店的限制) 10M+ 8B+ 9R+15D5000 2M+ 3B+ 3R 1800 M+ B+ R+ D=600 R 150 M,B,R,D 0对问题进行求解部分的结果：最大利润时各个分销点的销售数量只有当直接邮购的利润增加45美元时，才可以使用这种渠道每增加1美元预算，会增加利润3美元零售店销售数量每减少一个，利润会增加17美元公司的产量增加一个单位，利润增加60美元有关问题的灵敏度分析结果：只要系数在这个范围内变化，现在