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

第三章线性规划模型引言

实例—加工奶制品的生产计划线性规划问题的数学模型求解线性规划问题的图解法

用Lingo软件求解线性规划问题

线性规划问题的灵敏度分析线性规划（LinearProgramming）是数学规划的一个重要分支,历史比较悠久,理论比较成熟,方法较为完善。线性规划的思想最早可以追溯到1939年,当时的苏联数学家、经济学家L.V.Kantorovich（康特罗维奇）在《生产组织与计划中的数学方法》一书中提出了类似线性规划的模型,以解决下料问题和运输问题,并给出了“解决乘数法”的求解方法。然而,他的工作长期未被人们知道。引言引言由于战争的需要,美国的经济学家T.C.Koopmans(库普曼斯)重新独立的研究运输问题,并很快看到了线性规划在经济学中应用的意义.在这之后,线性规划也被人们广泛地用于军事、经济等各方面。由于Kantorovich和Koopmans在这方面的突出贡献,他们一起得到1975年诺贝尔经济学奖。为更好地理解线性规划所描述的问题，我们先看一个例子。例1加工奶制品的生产计划1桶牛奶

3千克A1

12小时

8小时

4千克A2

或获利24元/千克获利16元/千克50桶牛奶时间480小时至多加工100千克A1

制订生产计划，使每天获利最大?

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/千克，应否改变生产计划？每天：1桶牛奶3千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/千克x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100千克A1

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

Globaloptimalsolutionfoundatstep:2

Objectivevalue:3360.000

VariableValueReducedCost

X120.000000.0000000

X230.000000.0000000RowSlackorSurplusDualPrice13360.0001.00000020.000000048.0000030.00000002.000000440.000000.0000000结果解释

Objectivevalue:3360.000VariableValueReducedCostX120.000000.0000000X230.000000.0000000

RowSlackorSurplusDualPrice13360.0001.000000

20.000000048.00000

30.00000002.000000

440.000000.0000000原料无剩余时间无剩余加工能力剩余40三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释

在最优解下，“资源”增加1单位时，“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！Objectivevalue:3360.000VariableValueReducedCostX120.000000.0000000X230.000000.0000000RowSlackorSurplusDualPrice13360.0001.000000

20.000000048.00000

30.00000002.000000

440.000000.0000000Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000最优基不变时目标函数系数允许变化范围灵敏度分析

x1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53

35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数系数不变)例2奶制品的生产销售计划

在例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小时至多100公斤A1

B1，B2的获利经常有10%的波动，对计划有无影响？生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小钢管下料原料下料问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大问题1.如何下料最节省?例1钢管下料问题2.客户增加需求：原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？5米10根按照客户需要在一根原料钢管上安排切割的一种组合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根钢管下料为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少模式

4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量

目标1（总余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解：x2=12,x5=15,其余为0；最优值：27。整数约束：xi为整数当余料没有用处时，通常以总根数最少为目标目标2（总根数）钢管下料问题1约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。xi为整数按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米虽余料增加8米，但减少了2根与目标1的结果“共切割27根，余料27米”相比钢管下料问题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米和8米长的钢管的数量满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数增加约束，缩小可行域，便于求解原料钢管总根数下界：

特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=31模式排列顺序可任定

钢管下料问题2需求：4米50根，5米10根，6米20根，8米15根每根原料钢管长19米LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.00000