第二章运筹学.ppt

《第二章运筹学.ppt》由会员分享，可在线阅读，更多相关《第二章运筹学.ppt（30页珍藏版）》请在三一文库上搜索。

1、灵敏度分析的概念和内容 资源数量变化的分析 目标函数中价值系数变化的分析 影子价格的经济意义和应用,第二章 线性规划灵敏度分析,线性规划问题的系数有 aij、bi 、 cj，这些系数往往是估计值或预测值。,市场条件变化， cj 值就会变化；工艺条件和技术水平改变， aij 就变化； bi 是根据资源投入后的经济效果决定的一种选择，市场供应条件发生变化时，亦会改变。,灵敏度分析的概念,灵敏度分析的内容,再看线性规划模型：,已经求得最优解：x*1 = 2, x*2 = 6。此时总利润最大，最优目标值为：z* = 3600（元）,灵敏度分析的内容,现在要考虑发生下面的变化时，最优解是否会改变？对总利

2、润又会产生怎样的影响？,如果门的单位利润由原来的300元提升到500元 如果门和窗的单位利润都发生变化 如果车间 2 的可用工时增加 1 个小时 如果同时改变多个车间的可用工时 如果车间 2 更新生产工艺，缩短制造时间 工厂考虑增加一种新产品 如果又要求增加用电限制,目标函数中价值系数 cj 的变化分析,先考虑只有一个系数 cj 改变：门的单位利润由原来的 300 元提升到 500 元，最优解如何变化呢？,改变参数,最优解未变,总利润增加,(500 300) 2 = 400,最优解变了,再改变参数,那么，保持最优解不变的价值系数允许变化范围？,可行域,最优解(2,6),看图解法,此时有无穷组解

3、,此时有无穷组解,最优解不变,资源数量变化的分析,考虑只有一个右段值 bi 改变：2车间可用工时由原来的12小时增加到13小时，最优解如何变化呢？,修改了参数,总利润增加了 3750 3600 = 150(元),最优解也变了,可行域,最优解(2,6),（利润）,（利润）,（利润）,右端值变化，也改变了可行域。在一定范围内，车间的约束右端值增加 1，交点（最优点）上移，利润增长。,最优解不变,LINGO,Options,General Solver,Dual Computations,下拉菜单中选择：Prices & Range,激活灵敏度计算,（计算对偶值和灵敏度）,OK,在 LINGO 的求

4、解报告中，除了前面提到的迭代次数，最优解和目标函数值外，还有松弛系数（Slack or surplus）、递减费用（Reduced Cost）和对偶价格（Dual Price）三栏。,Lingo 的对偶价格,“Reduced Cost” （递减成本）表示当变量有微小变动时, 目标函数的变化率。即当变量 xj 增加一个单位时，目标函数减少的量（max型问题）。 它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。在最大化问题中，“改进”指增加，最小化问题中指减少。,“Slack or Surplus”（松弛系数）表示对应约束行在最优解下还剩下多少资源。（第一行是目标函

5、数行）,“DUAL PRICE”（对偶价格，即影子价格）输出结果中对应于每一个约束有一个对偶价格。 表示对应约束中不等式右端项若增加 1 个单位，目标值将增加的数量（max型问题）。如：车间2：1213，总利润变化量 = 影子价格 = 150 元； 车间3：1817，总利润变化量 = - 影子价格 = - 100 元,LINGO,Range,Lingo 的灵敏度分析,输出报告,目标函数中 x1 变量原来的费用系数为300，允许增加（Allowable Increase）=450、允许减少（Allowable Decrease）=300，说明当它在 0, 750 范围变化时，最优基保持不变，可以

6、类似解释 x2变量。由于此时约束没有变化（只是目标函数中某个费用系数发生变化），所以最优基保持不变的意思也就是最优解不变（当然，由于目标函数中费用系数发生了变化，所以最优值会变化）。 第 2 行约束中右端项（Right Hand Side，简写为RHS）原来为 4，当它在 2，范围变化时，最优基保持不变。第3、4 行可以类似解释。不过由于此时约束发生变化，最优基即使不变，最优解、最优值也会发生变化。,多个费用系数同时变动分析,例如，门的单位利润涨到 450元，窗的利润降到 400元，是否会导致最优解发生变化呢？,model: max=450*x1+400*x2; x1=4; 2*x2=12;

7、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.000000 X2 6.000000 0.000000,最优解没有发生变化，总利润 由于产品单位利润的变化相应改变 (450 - 300)2 + (400 500) 6 = -300,百分之百法则,如果目标函数系数同时变动，计算出每一系数变动量的百分比，然后将各系数的变动百分比相加，如果所得的和不超过100%，则最优解不会改变；反之，

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

9、ptimal solution 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%，那么，影子价格依然有效；否则，就无法确定。,前面的例子。 b2: 1213 占允许增加量的百分比 =,b3: 1817 占允

10、许增加量的百分比 =,总和 = 33.33% 100%，故影子价格 没有改变。,若,b2: 1215 ， b3: 1815 ，总和 = 100% 100%，仍未变。,在影子价格有效的范围里，总利润的变化量可以直接用影子价格来计算。,影子价格,资源的影子价格实际上是一种机会成本。在纯市场经济条件下 市场价格 影子价格， 卖出该资源 影子价格随之改变，逐渐趋向市场价格。,影子价格 = 0，该资源未充分利用 影子价格 0，该资源已消耗殆尽。,产品的隐含成本 = 单位资源消耗量影子价格 产品产值 隐含成本， 生产该产品有利 产品产值 隐含成本，生产该产品不利，应该转产,影子价格的应用。 某文教用品厂利

11、用白坯纸生产稿纸、日记本和练习本。该厂有工人100人，每天白坯纸的供应量为30000千克。每个工人每天可单独生产稿纸30捆或日记本30打或练习本30箱。三种产品消耗白坯纸：每捆稿纸需10/3千克，每打日记本需40/3千克，每箱练习本需80/3千克。分别盈利为1元、2元和3元。试讨论在现有条件下，使该厂盈利最大的方案？ 如白坯纸供应量不变，而工人数量不足时，可从市场上招收临时工，临时工费用为每人每天15元，该厂是否招临时工及招多少人为宜？,解：设决策变量为该厂每天生产量： 稿纸 x1 捆，日记本 x2 打，练习本 x3 箱。,数学模型为,总利润最大 每天白坯纸供应约束 工人数 非负,Global

12、 optimal solution found at iteration: 2 Objective value: 5000.000 Variable Value Reduced Cost 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.00000,model: max=x1+2*x2+3*x3; (x1+4*x2+8*x3)*10/3=3000

13、0; (x1+x2+x3)/30=100; end,Lingo 程序和计算结果,求解结果：每天生产稿纸1000捆，日记本2000打，练习本0箱最大利润 5000元 灵敏度报告：第二个约束的影子价格为 20 元，大于临时工每天费用 15 元，所以每招一名临时工，工厂多盈利 5 元，允许增量 200 人,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 1.000000 0

14、.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. 某工厂利用原材料甲、乙、丙生产产品 A，B，C。问： （1）怎样安排生产，才能使利润最大？ （2）若增加1公斤原材料甲，总利润增加多少？ （3）设原材料乙的

15、市场价格为1.2元/公斤，若要转卖原材料乙，工厂应至少叫价多少？为什么？ （4）单位产品利润分别在什么范围内变化时，原生产计划不变？ （5）由于市场变化，产品B、C的单位利润变为2、4元，这时应如何调整生产计划？,2. 某工厂计划生产、三种产品 ，各需要在A, B, C设备上加工：,（1）如何充分发挥设备能力，使工厂盈利最大？ （2）为了增加产量，可借用其它工厂的设备B，若每月可借60台，租金1.8万元，问是否合算？ （3）若有新产品，需用设备 A 12台，B 5台，C 10台时，单位产品盈利2.1千元，新产品，需用设备 A 4台，B 4台，C 12台时，单位产品盈利1.87千元。投产这两种新

16、产品是否合算？ （4）改进工艺后生产每件产品，需9台设备A，12台设备B，4台设备C，单位产品盈利4.5千元，问对原计划有何影响？,3. 某公司目前生产、两种产品的产量分别为每天30个和120个。问： （1）假设产品销路不成问题，请确定最优产品组合（产量）？ （2）在最优产品组合中，哪些车间还有剩余产能，剩余多少？ （3）四个车间能力的影子价格各为多少？ （4）当产品单位利润不变，产品的单位利润在什么范围内变化时，最优解不变不变？当单位利润不变，的变化范围呢？ （5）当产品单位利润从500元降为450元，产品的单位利润增加到430元，原来的最优产品组合是否保持，或如何改变？,4. 前进电器厂生产A、B、C三种产品。问： （1）在资源限量及市场容量允许的条件下，如何安排生产，才能使利润最多？ （2）说明三种产品的市场容量的影子价格以及材料、台时的影子价格的含义，并对其进行灵敏度分析。如要开拓市场应当首先开拓哪种产品的市场？如要增加资源，则应在多大程度上增加机器台时数和材料数量？,