第二章运筹学.ppt

《第二章运筹学.ppt》由会员分享，可在线阅读，更多相关《第二章运筹学.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、灵敏度分析的概念和内容灵敏度分析的概念和内容资源数量变化的分析资源数量变化的分析目标函数中价值系数变化的分析目标函数中价值系数变化的分析影子价格的经济意义和应用影子价格的经济意义和应用第二章第二章 线性规划灵敏度分析线性规划灵敏度分析 线性规划问题的系数有线性规划问题的系数有 aij、bi、cj，这些系数往往是估这些系数往往是估计值或预测值。计值或预测值。市场条件变化，市场条件变化，cj 值就会变化；工艺条件和技术水平改变，值就会变化；工艺条件和技术水平改变，aij 就变化；就变化；bi 是根据资源投入后的经济效果决定的一种选择，是根据资源投入后的经济效果决定的一种选择，市场供应条件发生变化时

2、，亦会改变。市场供应条件发生变化时，亦会改变。灵敏度分析的概念灵敏度分析的概念当线性规划问题的系数有一个或几个发生变化时，已求得的当线性规划问题的系数有一个或几个发生变化时，已求得的最优解会有什么变化；最优解会有什么变化；这些系数在什么范围内变化时，线性规划问题的最优解不会这些系数在什么范围内变化时，线性规划问题的最优解不会变化。变化。提出问题提出问题:灵敏度分析的内容灵敏度分析的内容再看线性规划模型：再看线性规划模型：Max Z=300 x1+500 x2 x1 4 2 x2 12 3x1+2x2 18 x1,x2 0s.t.（车间（车间1）（车间（车间2）（车间（车间3）（非负）（非负）已

3、经求得最优解：已经求得最优解：x*1=2,x*2=6。此时总利润最大，最优。此时总利润最大，最优目标值为：目标值为：z*=3600（元）（元）灵敏度分析的内容灵敏度分析的内容 现在要考虑发生下面的变化时，最优解是否会现在要考虑发生下面的变化时，最优解是否会改变？对总利润又会产生怎样的影响？改变？对总利润又会产生怎样的影响？1.如果门的单位利润由原来的如果门的单位利润由原来的300元提升到元提升到500元元2.如果门和窗的单位利润都发生变化如果门和窗的单位利润都发生变化3.如果车间如果车间 2 的可用工时增加的可用工时增加 1 个小时个小时4.如果同时改变多个车间的可用工时如果同时改变多个车间的

4、可用工时5.如果车间如果车间 2 更新生产工艺，缩短制造时间更新生产工艺，缩短制造时间6.工厂考虑增加一种新产品工厂考虑增加一种新产品7.如果又要求增加用电限制如果又要求增加用电限制目标函数中价值系数目标函数中价值系数 cj 的变化分析的变化分析先考虑只有一个系数先考虑只有一个系数 cj 改变：改变：门的单位利润由原来的门的单位利润由原来的 300 300 元提升到元提升到 500 500 元，最优解如何变化呢？元，最优解如何变化呢？改变参数改变参数最优解未变最优解未变总利润增加总利润增加(500 300)2=400最优解变了最优解变了再改变参数再改变参数那么，保持最优解不变的价值系数允许变化

5、范围？那么，保持最优解不变的价值系数允许变化范围？可行域可行域最优解最优解(2,6)看图解法看图解法此时有无穷组解此时有无穷组解此时有无穷组解此时有无穷组解最优解不变最优解不变资源数量变化的分析资源数量变化的分析考虑只有一个右段值考虑只有一个右段值 bi 改变：改变：2 2车间可用工时由原来的车间可用工时由原来的1212小小时增加到时增加到1313小时，最优解如何变化呢？小时，最优解如何变化呢？修改了参数修改了参数总利润增加了总利润增加了 3750 3600=150(元元)最优解也变了最优解也变了可行域可行域最优解最优解(2,6)（利润）（利润）（利润）（利润）（利润）（利润）右端值变化，也改

6、变了可行域。在一定范围内，车间的右端值变化，也改变了可行域。在一定范围内，车间的约束右端值增加约束右端值增加 1，交点（最优点）上移，利润增长。，交点（最优点）上移，利润增长。最优解不变最优解不变LINGOOptionsGeneral SolverDual Computations下拉菜单中选择：下拉菜单中选择：Prices&Range 激活灵敏度计算激活灵敏度计算（计算对偶值和灵敏度）（计算对偶值和灵敏度）OK 在在 LINGO 的求解报告中，除了前面提到的迭代次数，的求解报告中，除了前面提到的迭代次数，最优解和目标函数值外，还有松弛系数（最优解和目标函数值外，还有松弛系数（Slack or

7、 surplus）、）、递减费用（递减费用（Reduced Cost）和对偶价格（）和对偶价格（Dual Price）三栏。）三栏。Lingo 的对偶价格的对偶价格“Reduced Cost”（递减成本递减成本）表示当变量有微小变动时）表示当变量有微小变动时,目标函数的变化率。即当变量目标函数的变化率。即当变量 xj 增加一个单位时，目标函增加一个单位时，目标函数减少的量（数减少的量（max型问题）。型问题）。它的绝对值表示目标函数中决策变量的系数必须改进它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。在最大化问题中，多少，才能得到该决策变量的正数解。在最大化问

8、题中，“改进改进”指增加，最小化问题中指减少。指增加，最小化问题中指减少。“Slack or Surplus”（松弛系数松弛系数）表示对应约束行在最优解下还）表示对应约束行在最优解下还剩下多少资源。（第一行是目标函数行）剩下多少资源。（第一行是目标函数行）“DUAL PRICE”（对偶价格，即（对偶价格，即影子价格影子价格）输出结果中对应）输出结果中对应于每一个约束有一个对偶价格。于每一个约束有一个对偶价格。表示对应约束中不等式右端表示对应约束中不等式右端项若增加项若增加 1 个单位，目标值将增加的数量（个单位，目标值将增加的数量（max型问题）。型问题）。如：车间如：车间2：1213，总利润

9、变化量，总利润变化量=影子价格影子价格=150 元；元；车间车间3：1817，总利润变化量，总利润变化量=-影子价格影子价格=-100 元元LINGORangeLingo 的灵敏度分析的灵敏度分析输出输出报告报告 目标函数中目标函数中 x1 变量原来的费用系数为变量原来的费用系数为300，允许增加，允许增加（Allowable Increase）=450、允许减少（、允许减少（Allowable Decrease）=300，说明当它在，说明当它在 0,750 范围变化时，最优基保范围变化时，最优基保持不变，可以类似解释持不变，可以类似解释 x2变量。由于此时约束没有变化（只变量。由于此时约束没

10、有变化（只是目标函数中某个费用系数发生变化），所以最优基保持不是目标函数中某个费用系数发生变化），所以最优基保持不变的意思也就是最优解不变（当然，由于目标函数中费用系变的意思也就是最优解不变（当然，由于目标函数中费用系数发生了变化，所以最优值会变化）。数发生了变化，所以最优值会变化）。第第 2 行约束中右端项（行约束中右端项（Right Hand Side，简写为，简写为RHS）原来为原来为 4，当它在，当它在 2，范围变化时，最优基保持不变。第范围变化时，最优基保持不变。第3、4 行可以类似解释。不过由于此时约束发生变化，最优基即使行可以类似解释。不过由于此时约束发生变化，最优基即使不变，最

11、优解、最优值也会发生变化。不变，最优解、最优值也会发生变化。多个费用系数同时变动分析多个费用系数同时变动分析例如，门的单位利润涨到例如，门的单位利润涨到 450元，窗的利润降到元，窗的利润降到 400元，是否元，是否会导致最优解发生变化呢？会导致最优解发生变化呢？model:max=450*x1+400*x2;x1=4;2*x2=12;3*x1+2*x2=18;end Global optimal solution found at iteration:2 Objective value:3300.000 Variable Value Reduced Cost X1 2.000000 0.00

12、0000 X2 6.000000 0.000000 最优解没有发生变化，总利润最优解没有发生变化，总利润由于产品单位利润的变化相应改变由于产品单位利润的变化相应改变 (450-300)2+(400 500)6=-300百分之百法则百分之百法则如果目标函数系数同时变动，计算出每一系数变动量的百分比，如果目标函数系数同时变动，计算出每一系数变动量的百分比，然后将各系数的变动百分比相加，如果所得的和不超过然后将各系数的变动百分比相加，如果所得的和不超过100%，则最优解不会改变；反之，则不能确定。，则最优解不会改变；反之，则不能确定。前面的例子。前面的例子。c1:300450 占允许增加量的百分比占

13、允许增加量的百分比=c2:500400 占允许增加量的百分比占允许增加量的百分比=总和总和=66.67%100%，故最优解，故最优解(2,6)没有改变。没有改变。如果如果c1:300525，c2:500350，总和，总和=100%100%，最优解也未变。，最优解也未变。多个资源系数同时变动分析多个资源系数同时变动分析例如，将例如，将 1 个小时的用工时间从个小时的用工时间从3车间移到车间移到2车间，对总利润车间，对总利润产生什么影响？产生什么影响？model:max=300*x1+500*x2;x1=4;2*x2=13;3*x1+2*x2=17;end Global optimal solut

14、ion found at iteration:2 Objective value:3650.000 Variable Value Reduced Cost X1 1.333333 0.000000 X2 6.500000 0.000000总利润增加总利润增加 3650-3600=50 元，元，而目标系数未变，所以最优解肯定而目标系数未变，所以最优解肯定发生变化，发生变化，百分之百法则百分之百法则如果约束右端值同时变动，计算出每一变动占允许变动量的的如果约束右端值同时变动，计算出每一变动占允许变动量的的百分比，如果所有的百分比之和不超过百分比，如果所有的百分比之和不超过100%，那么，影子价，那

15、么，影子价格依然有效；否则，就无法确定。格依然有效；否则，就无法确定。前面的例子。前面的例子。b2:1213 占允许增加量的百分比占允许增加量的百分比=b3:1817 占允许增加量的百分比占允许增加量的百分比=总和总和=33.33%100%，故影子价格，故影子价格 没有改变。没有改变。若若 b2:1215，b3:1815，总和，总和=100%100%，仍未变。，仍未变。在影子价格有效的范围里，总利润的变在影子价格有效的范围里，总利润的变化量可以直接用影子价格来计算。化量可以直接用影子价格来计算。影子价格影子价格资源的影子价格实际上是一种机会成本。在纯市场经济条件下资源的影子价格实际上是一种机会

16、成本。在纯市场经济条件下市场价格市场价格 影子价格，影子价格，卖出该资源卖出该资源影子价格随之改变，逐渐趋向市场价格。影子价格随之改变，逐渐趋向市场价格。影子价格影子价格=0，该资源未充分利用，该资源未充分利用影子价格影子价格 0，该资源已消耗殆尽。，该资源已消耗殆尽。产品的隐含成本产品的隐含成本=单位资源消耗量单位资源消耗量影子价格影子价格产品产值产品产值 隐含成本，隐含成本，生产该产品有利生产该产品有利产品产值产品产值 隐含成本，生产该产品不利，应该转产隐含成本，生产该产品不利，应该转产影子价格的应用影子价格的应用。某文教用品厂利用白坯纸生产稿纸、日记本和练习本。某文教用品厂利用白坯纸生产

17、稿纸、日记本和练习本。该厂有工人该厂有工人100人，每天白坯纸的供应量为人，每天白坯纸的供应量为30000千克。每个千克。每个工人每天可单独生产稿纸工人每天可单独生产稿纸30捆或日记本捆或日记本30打或练习本打或练习本30箱。箱。三种产品消耗白坯纸：每捆稿纸需三种产品消耗白坯纸：每捆稿纸需10/3千克，每打日记本需千克，每打日记本需40/3千克，每箱练习本需千克，每箱练习本需80/3千克。分别盈利为千克。分别盈利为1元、元、2元和元和3元。试讨论在现有条件下，使该厂盈利最大的方案？元。试讨论在现有条件下，使该厂盈利最大的方案？如白坯纸供应量不变，而工人数量不足时，可从市场上招收如白坯纸供应量不

18、变，而工人数量不足时，可从市场上招收临时工，临时工费用为每人每天临时工，临时工费用为每人每天15元，该厂是否招临时工及元，该厂是否招临时工及招多少人为宜？招多少人为宜？解：设决策变量为该厂每天生产量：解：设决策变量为该厂每天生产量：稿纸稿纸 x1 捆，日记本捆，日记本 x2 打，练习本打，练习本 x3 箱。箱。数学模型为数学模型为总利润最大总利润最大每天白坯纸每天白坯纸供应约束供应约束工人数工人数非负非负 Global optimal solution found at iteration:2 Objective value:5000.000 Variable Value Reduced Co

19、st X1 1000.000 0.000000 X2 2000.000 0.000000 X3 0.000000 0.3333333 Row Slack or Surplus Dual Price 1 5000.000 1.000000 2 0.000000 0.1000000 3 0.000000 20.00000model:model:max=x1+2*x2+3*x3;max=x1+2*x2+3*x3;(x1+4*x2+8*x3)*10/3=30000;(x1+4*x2+8*x3)*10/3=30000;(x1+x2+x3)/30=100;(x1+x2+x3)/30=100;endendL

20、ingo 程序和计算结果程序和计算结果求解结果：每天生产稿纸求解结果：每天生产稿纸1000捆，日记本捆，日记本2000打，练习本打，练习本0箱箱最大利润最大利润 5000元元灵敏度报告：第二个约束的影子价格为灵敏度报告：第二个约束的影子价格为 20 元，大于临时工每元，大于临时工每天费用天费用 15 元，所以每招一名临时工，工厂多盈利元，所以每招一名临时工，工厂多盈利 5 元，允许元，允许增量增量 200 人人Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowab

21、le Variable Coefficient Increase Decrease X1 1.000000 0.2500000 0.5000000 X2 2.000000 2.000000 0.1428571 X3 3.000000 0.3333333 INFINITY Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 30000.00 10000.00 20000.00 3 100.0000 200.0000 25.00000练习二练习二 1.某工厂利用原材料甲、乙、丙生产产品某工厂利用

22、原材料甲、乙、丙生产产品 A，B，C。问。问：（1）怎样安排生产，才能使利润最大？）怎样安排生产，才能使利润最大？（2）若增加）若增加1公斤原材料甲，总利润增加多少？公斤原材料甲，总利润增加多少？（3）设原材料乙的市场价格为）设原材料乙的市场价格为1.2元元/公斤，若要转卖原材料乙，公斤，若要转卖原材料乙，工厂应至少叫价多少？为什么？工厂应至少叫价多少？为什么？（4）单位产品利润分别在什么范围内变化时，原生产计划不变？）单位产品利润分别在什么范围内变化时，原生产计划不变？（5）由于市场变化，产品）由于市场变化，产品B、C的单位利润变为的单位利润变为2、4元，这时应元，这时应如何调整生产计划？如

23、何调整生产计划？ABC每月可供原材料每月可供原材料甲甲211200（公斤）（公斤）乙乙123500（公斤）（公斤）丙丙221600（公斤）（公斤）单位利润（元）单位利润（元）413 2.某工厂计划生产某工厂计划生产、三种产品三种产品，各需要在，各需要在A,B,C设设备上加工备上加工：（1）如何充分发挥设备能力，使工厂盈利最大？）如何充分发挥设备能力，使工厂盈利最大？（2）为了增加产量，可借用其它工厂的设备）为了增加产量，可借用其它工厂的设备B，若每月可借，若每月可借60台，租金台，租金1.8万元，问是否合算？万元，问是否合算？（3）若有新产品）若有新产品，需用设备，需用设备 A 12台，台，B

24、 5台，台，C 10台时，单台时，单位产品盈利位产品盈利2.1千元，新产品千元，新产品，需用设备，需用设备 A 4台，台，B 4台，台，C 12台时，单位产品盈利台时，单位产品盈利1.87千元。投产这两种新产品是否合算？千元。投产这两种新产品是否合算？（4）改进工艺后生产每件产品）改进工艺后生产每件产品，需，需9台设备台设备A，12台设备台设备B，4台设备台设备C，单位产品盈利，单位产品盈利4.5千元，问对原计划有何影响？千元，问对原计划有何影响？设备有效台时（月）设备有效台时（月）A8210300B1058400C21310420单位利润（千元）单位利润（千元）322.9 3.某公司目前生产

25、某公司目前生产、两种产品的产量分别为每天两种产品的产量分别为每天30个和个和120个。问个。问：（1）假设产品销路不成问题，请确定最优产品组合（产量）？）假设产品销路不成问题，请确定最优产品组合（产量）？（2）在最优产品组合中，哪些车间还有剩余产能，剩余多少？）在最优产品组合中，哪些车间还有剩余产能，剩余多少？（3）四个车间能力的影子价格各为多少？）四个车间能力的影子价格各为多少？（4）当产品）当产品单位利润不变，产品单位利润不变，产品的单位利润在什么范围内变的单位利润在什么范围内变化时，最优解不变不变？当化时，最优解不变不变？当单位利润不变，单位利润不变，的变化范围呢？的变化范围呢？（5）当

26、产品）当产品单位利润从单位利润从500元降为元降为450元，产品元，产品的单位利润增的单位利润增加到加到430元，原来的最优产品组合是否保持，或如何改变？元，原来的最优产品组合是否保持，或如何改变？车间车间设备有效台时（月）设备有效台时（月）12030020354032244041.21.5300单位利润（元）单位利润（元）500400 4.前进电器厂生产前进电器厂生产A、B、C三种产品。问三种产品。问：（1）在资源限量及市场容量允许的条件下，如何安排生产，才）在资源限量及市场容量允许的条件下，如何安排生产，才能使利润最多？能使利润最多？（2）说明三种产品的市场容量的影子价格以及材料、台时的影）说明三种产品的市场容量的影子价格以及材料、台时的影子价格的含义，并对其进行灵敏度分析。如要开拓市场应当首子价格的含义，并对其进行灵敏度分析。如要开拓市场应当首先开拓哪种产品的市场？如要增加资源，则应在多大程度上增先开拓哪种产品的市场？如要增加资源，则应在多大程度上增加机器台时数和材料数量？加机器台时数和材料数量？产品产品材料消耗材料消耗（kg/件）件）台时消耗台时消耗（时（时/件）件）产品利润产品利润（元（元/件）件）市场容量（件）市场容量（件）A1.0210200B1.51.212250C4.0114100资源限制资源限制20001000