1.7.使用Excel求解线性规划问题例:Case Chemicals生产两种溶剂CS-01和CS-02。
这些溶剂可以用来溶解某些有毒物质。
Case Chemicals的生产工厂有两个部门—混合(blending)和净化(purification)。
每个部门每周工作40个小时。
混合部门有5个全职(full-time)的工人和2个兼职(part-time)的工人,这两个兼职的工人每人每周工作15个小时。
这些工人操作7台机器来混合某些化学物质生产溶剂。
每1000加仑的CS-01需要2个小时去混合,同样数量的CS-02只需要1个小时去混合。
产品在混合部门混合后需要去净化部门净化。
净化部门有7台净化机器,并且雇了6个全职的工人和1个兼职的工人,兼职的工人每周工作10个小时。
60分钟可以净化1000加仑的CS-01或500加仑的CS-02。
Case Chemicals原材料供应充足,市场对CS-01的需求是供不应求,但是市场对CS-02的需求每周最多120,000加仑。
据估计,每加仑CS-01可以赚$0.30,每加仑的CS-02可以赚$0.50。
生产经理想要决定最优的生产计划,即应该生产每种溶剂各多少才能最大化利润?解:(1)决策变量x1=每周生产CS-01的数量(千加仑)x2=每周生产CS-02的数量(千加仑)(2)目标函数最大化每周生产CS-01和CS-02的利润Maximize 利润=CS-01利润+CS-02的利润 =300x1+500x2Max 300x1+500x2(3)约束条件混合部门的总工时的约束2x1+1x2<=5*40+2*15=230净化部门的总工时的约束x1+2x2<=6*40+1*10=250CS-02的销售数量的约束x2<=120变量的非负约束x1,x2>=0.数学模型Max 300x1+500x2St. 2x1+1x2<=230 blending1x1+2x2<=250 purificationX2<=120 CS-02x1,x2>=0 nonnegativeExcel规划求解Excel规划求解的选项可以用来解决线性规划问题。
可以设置决策变量为整数约束。
规划求解可以用来解决最多有200个变量,100个外在约束和400个简单约束(决策变量整数约束的上下边界)的问题。
安装线性规划加载项Excel 2003:菜单栏——工具——加载宏——规划求解调用规划求解,从主菜单中选择工具/规划求解。
Excel 2007:Office按钮——Excel选项——加载项——转到——加载宏——规划求解加载项在“数据”选项卡中出现带有“规划求解”按钮的“分析”组输入数据在Excel中输入问题数据,我们即可以输入原来的形式也可以输入标准的计算形式。
通常我们就输入原来的形式,让Excel自己把它变成标准形式。
因此,我们输入如下形式。
下图显示了输入这个问题后的屏幕,我们把变量1x称为x称为“CS-02”。
我们把三个约束也分别“CS-01”,变量2命名为BLENDHRS,PURIHRS和CS02LIM。
除了指约束外,这些名字也被Excel指为与这些约束相对应的剩余/松弛Slack/surplus 变量。
我们用单元格B2和C2来包含1x和2x的值。
约束中‘<=’的符号只是给我们自己看的,我们需要告诉规划求解(Solver)这些符号。
下面显示的是单元格所用的公式(formulae)。
注意在单元格D4中我们需要输入公式来计算目标函数(这个例子中,“=B4*B2+C4*C2”,其中*在Excel中指的是乘的意思),在D6到D8中输入公式来计算每个约束(如果你没有用过Excel,公式中的$符号,你可以不用管;它只是一个捷径)。
注意作为一个捷径,在单元格D6中我们也可以输入=SUMPRODUCT($B$2:$C$2,B6:C6),然后拷贝和粘贴这个公式到单元格D7和D8中。
当问题比较大的时候,这个会比较有用。
一旦我们设置好问题之后,我们可以从工具菜单中选择‘规划求解’(Solver),我们需要告诉规划求解参数对话框我们的问题。
这个例子中,单元格C4是目标单元格,需要最大化;这是我们输入目标函数的单元。
Excel会通过调整可变单元格B2和C2的值(我们的决策变量)来最大化目标。
(符号‘:’在$B$2:$C$2公式中,实际上指的是从B2到C2的单元格,这个例子中,只是单元格B2和C2,对于一个大点的问题,你可能输入$B$2:$F$2来告诉ExcelB2,C2,D2,E2和F2是决策变量。
)约束的输入是通过点击添加按钮,点击增加钮会弹出增加约束对话框,如下所示。
上面的第一个约束(又在下面的增加约束对话框中显示)是非负约束,这个例子中单元格B2和C2是正的(即CS-01>=0和CS-02>=0)。
在输入约束后,你可以用增加按钮增加一个约束。
如果你想改变约束,可以点击修改按钮,打开修改约束的对话框。
这个对话框和增加约束的对话框非常相似。
为了确保Excel产生我们期待的LP Solver的输出,我们需要点击选项按钮,选中采用线性模型和假定非负,假定非负也是另一种说1x,2x>=0的方式。
为了保证找到最优解,我们把允许误差设为0%。
一旦我们点击求解按钮,规划求解(Solver)会找到一个解(如果解存在),并显示下面的窗口,允许生成一定数量的报告;我们通常想要的是答案报告和灵敏度分析报告。
下面显示了Excel找到的最优解和答案报告(你可以看出Slacks 已经被加到答案报告中)。
如果你得到的报告和这个不同,你可能没选中“采用线性模型”。
最优解是生产70千加仑的CS-01和90千加仑的CS-02,这会给Case Chemicals带来每周$66000的利润。
1.8灵敏度分析引言一旦我们找到了最优解,我们经常想知道如果问题数据发生了变化,最优解会怎样改变。
换句话说,我们想知道最优值对模型中的某些值有多敏感。
例如,我们可能会问如果Case Chemicals模型中的某些值发生变化,会发生什么。
灵敏度分析主要是用来解决这样的问题。
术语上面的的式子中(1)目标函数中的300和500被称作成本(costs)(2)约束中的230,250和120被称作右边(right hand sides)计算机输出的灵敏度分析在问题求解后,Excel会产生一个灵敏度的表。
Case Chemicals 的灵敏度报告如下所示。
注意为了得到如下的内容,你必须告诉Excel“采用线性模型”。
Excel给出值的范围,用允许增加(如CS-01的700,也就是值的最大到300+700=1000)和减少(CS-01的50,也就是值最小到300-50=250)的数量来表示。
下面我们解释如何使用这个表。
成本灵敏度分析(Cost Sensitivity Analysis)我们考虑目标函数中成本系数的变化1.考虑最优解例如:对于Case Chemicals的问题,最优解是,目标函数值(利润)是660002.如果一个变量的成本发生变化,那么灵敏度分析会告诉我们原来的最优决定是否还是最优的。
例如:如果的成本$300增加到$400,解是否是最优的?也就是,是否我们还应该生产70千加仑的CS-01和90千加仑的CS-02?3.成本灵敏度分析的输出给出了新成本可以改变到的最小和最大值而不改变最优的决定。
例:对(CS-01),成本可以变到250-1000之间的任何值,而不改变最优解。
4.如果新的成本在范围内,那么原来的最优解保持最优。
如果不是,那么问题需要重新求解。
例:新的成本=400 值的范围 250-1000. 在范围内?是/(否)所以原来的解还是/(不是)最优的。
5.如果原来的解还是最优的,我们可以计算新的目标函数值。
新的目标函数值=旧的目标函数值+决策变量值*成本系数变化=旧的目标函数值+决策变量值*(新的成本系数-旧的成本系数)例:Case Chemicals新的总利润可以计算为旧的利润=$66,000决策变量的值:旧的成本系数:的旧的成本系数是300新的成本系数:新的成本是400新的目标函数值=旧的目标函数值+决策变量值*成本系数变化=66000+70*(400-300)=73000注意:这个分析只能用于一个变量的成本发生变化。
成本分析-数值例子例1. 市场的变化允许Case Chemicals在CS-01上的利润上增加了$200/每1000加仑。
生产计划该如何改变,Case Chemicals现在最大的利润是多少?例2. 由于市场的变化,CS-02的利润下降了$400/每1000加仑,现在Case Chemicals可以获得的最大利润是多少?第一步:识别问题的变化,x2的成本系数由500变为100.第二步:检查新的成本系数是否在范围内新的成本是100,范围是150-600,在范围内?否第三步:如果在范围内,计算新的成本答:最优生产计划改变了,需要重新求解。
例3. CS-01和CS-02的利润分别增加了10%和15%,Case Chemicals可以获得的最多的利润是多少?两个变化,不能回答。
例4. CS-01和CS-02的利润现在都加倍了,Case Chemicals是否应该改变他们生产CS-01和CS-02的量。
由于成本的比例没变,目标函数的轮廓看起来和原来一样,所以最优解没有改变。
成本灵敏度分析的图形解释改变一个成本对应着目标函数轮廓的改变。
下面显示了我们改变CS-01的利润(Cost on X1)1.原来的目标函数(Original Objective Function)原来CS-01的利润是$300,目标函数是Max 300X1+500X2图中显示了目标函数的轮廓。
注意当我们向右上方移动时目标函数是增加的。
原来的最优解是x1=70,x2=90, 最优的目标函数值为$300*70+$500*90=$660002.新的CS-01的利润为$500目标函数是Max 500X1+500X2图中显示了目标函数的轮廓。
注意当我们向右上方移动时目标函数是增加的。
原来的最优解仍然是最优的。
新的最优目标函数值为$500*70+$500*90=$80000检查:新的成本是否在Excel范围内?答:是/否(是,所以最优解没有变化)3.新的CS-01的成本$1000目标函数是Max 1000X1+500X2图中显示了目标函数的轮廓。
注意当我们向右上方移动时目标函数是增加的。
原来的最优解仍然是最优的。
新的最优目标函数值为$1000*70+$500*90=$115000评论:原来的最优解是众多最优解中的一个。
检查:新的成本在Excel的范围内吗?答:是,但只是刚刚是4.新的CS-01的成本$1500目标函数是Max 1000X1+500X2图中显示了目标函数的轮廓。