线性规划模型-灵敏度分析

1、第三章 线性规划模型 引引 言言 实例实例加工奶制品的生产计划加工奶制品的生产计划 线性规划问题的数学模型线性规划问题的数学模型 求解线性规划问题的图解法求解线性规划问题的图解法 用用LingoLingo软件求解线性规划问题软件求解线性规划问题 线性规划问题的线性规划问题的灵灵敏度分析敏度分析 线性规划（线性规划（Linear Programming）是数学）是数学规划的一个重要分支规划的一个重要分支, , 历史比较悠久历史比较悠久, , 理论比理论比较成熟较成熟, , 方法较为完善。线性规划的思想最早方法较为完善。线性规划的思想最早可以追溯到可以追溯到19391939年年, , 当时的苏联数

2、学家、经济当时的苏联数学家、经济学家学家 L. V. KantorovichL. V. Kantorovich （康特罗维奇）在（康特罗维奇）在生产组织与计划中的数学方法生产组织与计划中的数学方法一书中提出一书中提出了类似线性规划的模型了类似线性规划的模型, , 以解决下料问题和运以解决下料问题和运输问题输问题, , 并给出了并给出了“解决乘数法解决乘数法”的求解方法。的求解方法。然而然而, , 他的工作长期未被人们知道。他的工作长期未被人们知道。引引 言言引引 言言 由于战争的需要由于战争的需要, , 美国的经济学家美国的经济学家T. C. T. C. KoopmansKoopmans (

3、(库普曼斯库普曼斯) ) 重新独立的研究运输问重新独立的研究运输问题题, , 并很快看到了线性规划在经济学中应用的并很快看到了线性规划在经济学中应用的意义意义. . 在这之后在这之后, , 线性规划也被人们广泛地用线性规划也被人们广泛地用于军事、经济等各方面。于军事、经济等各方面。 由于由于KantorovichKantorovich 和和 KoopmansKoopmans在这方面在这方面的突出贡献的突出贡献, ,他们一起得到他们一起得到19751975年诺贝尔经济年诺贝尔经济学奖。学奖。 为更好地理解线性规划所描述的问题，为更好地理解线性规划所描述的问题，我们先看一个例子。我们先看一个例子。

4、例例1 加工奶制品的生产计划加工奶制品的生产计划1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4千克千克A2 或或获利获利24元元/千克千克获利获利16元元/千克千克50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100千克千克A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大? ? 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/千克，应否改变生产计划？千克，应否改变生产计划？ 每天：每

5、天：1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4千克千克A2 或或获利获利24元元/千克千克获利获利16元元/千克千克x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100千克千克A1 50桶牛奶桶牛奶 每天每天model: ma

6、x=72*x1+64*x2; x1+x2=50; 12*x1+8*x2=480; 3*x1=100;end用用Lingo软件求解线性规划问题软件求解线性规划问题. 0, 0100348081250. .6472max211212121xxxxxxxtsxx模型模型LingoLingo语句语句模型开始模型开始目标函数求极大目标函数求极大约束条件约束条件（无非负限制）（无非负限制）模型结束模型结束Lingo软件包是由美国LINDO系统公司 研制开发的，是用于求解大型数学规划问题的软件包。求解20桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 LingoLingo软件的

7、计算结果软件的计算结果 Global optimal solution found at step: 2 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.0000000 X2 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.0000000 48.00000 3 0.0000000 2.000000 4 40.00000 0.0000000结果解释结果解释 Objective value: 3360.000V

8、ariable Value Reduced Cost X1 20.00000 0.0000000 X2 30.00000 0.0000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.0000000 48.00000 3 0.0000000 2.000000 4 40.00000 0.0000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） . 0, 0100348081250. .6472max211

9、212121xxxxxxxt sxx结果解释结果解释 在最优解下，在最优解下，“资源资源”增增加加1单位时，单位时，“效益效益”的的增量增量 原料增加原料增加1单位单位, 利润增长利润增长48 时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48, 应该买！应该买！ 聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？ 2元！元！Objective value: 3360.000Variable Value Reduced Cost X1 20.0

10、0000 0.0000000 X2 30.00000 0.0000000Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.0000000 48.00000 3 0.0000000 2.000000 4 40.00000 0.0000000Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.0

11、0000 8.000000 X2 64.00000 8.000000 16.00000Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000最优基不变时目标函数系数允许变化范围最优基不变时目标函数系数允许变化范围 灵敏度分析灵敏度分析 x1系数范围系数范围(64,96) x2系数范围系数范围(48,72) A1获利增加到获利增加

12、到 30元元/千克，应否改变生产计划千克，应否改变生产计划 x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内 不变！不变！(约束条件不变约束条件不变)结果解释结果解释 Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000Righth

13、and Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数系目标函数系数不变数不变)例例2 奶制品的生产销

14、售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4千克千克A2 或或获利获利24元元/千克千克获利获利16元元/千克千克0.8千克千克B12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克 制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶, 480小时小时 至多至多10

15、0公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？生产中通过切割、剪裁、冲压等生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小手段，将原材料加工成所需大小 钢管下料钢管下料原料下料问题原料下料问题按照工艺要求，确定下料方案，按照工艺要求，确定下料方案，使所用材料最省，或利润最大使所用材料最省，或利润最大问题问题1. 如何下料最节省如何下料最节省 ? 例例1 钢管下料钢管下料 问题问题2. 客户增加需求：客户增加需求：原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什

16、么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下

17、料 为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需

18、求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12, x5=15, 其余为其余为0；最优值：最优值：27。整数约束：整数约束： xi 为整数为整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以

19、总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15, x5=5, x7=5, 其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx152753xxxxi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米” 相比相比 钢管下料问题

20、钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和

21、米和8米长的钢管的数量米长的钢管的数量满足需求满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）321xxxMin约束约束条件条件整数约束：整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：原料钢管总根数下界： 2619158206105504特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：13+10+8=31 31