使用Excel求解线性规划问题

1、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个 小时去混合。产品在混合部门混合后需要去净化部门净化。净

2、化部门有7台净化机器，并且雇了 6个全职的工人和1个兼职的工 人，兼职的工人每周工作10个小时。60分钟可以净化1000加仑 的CS-01或500加仑的CS-02。Case Chemicals原材料供应充足， 市场对CS-01的需求是供不应求，但是市场对CS-02的需求每周 最多120,000加仑。据估计，每加仑CS-01可以赚$0.30，每加仑 的C S-02可以赚$0.50。生产经理想要决定最优的生产计划，即 应该生产每种溶剂各多少才能最大化利润？解：(1)决策变量x1=每周生产CS-01的数量(千加仑)x2=每周生产CS-02的数量(千加仑)目标函数最大化每周生产CS-01和CS-02的

3、利润Maximize 利润二CS-01 利润+CS-02的利润=300 x1+500 x2Max 300 x1+500 x2(3)约束条件混合部门的总工时的约束2x1+1x2=5*40+2*15=230 净化部门的总工时的约束 x1+2x2=6*40+1*10=250CS-02的销售数量的约束 x2=0.数学模型Max 300 x1+500 x2St. 2x1+1x2=230 1x1+2x2=250 X2=0blending purification CS-02 nonnegativeExcel规划求解Excel规划求解的选项可以用来解决线性规划问题。可以设置决 策变量为整数约束。规划求解可以

4、用来解决最多有200个变量， 100个外在约束和400个简单约束（决策变量整数约束的上下边 界）的问题。安装线性规划加载项Excel 2003:菜单栏工具加载宏规划求解调用规划求解，从主菜单中选择工具/规划求解。转到Excel 2007: Office按钮Excel选项加载项加载宏一一规划求解加载项在“数据”选项卡中出现带有“规划求解”按钮的“分析”组输入数据在Exce l中输入问题数据，我们即可以输入原来的形式也可以输 入标准的计算形式。通常我们就输入原来的形式，让Exce 1自己 把它变成标准形式。因此，我们输入如下形式。maximize300 xi + 500 x2subject to2

5、xi + x： 0,下图显示了输入这个问题后的屏幕，我们把变量X 1称为“CS-01 ”，变量X 2称为“ CS-02 ”。我们把三个约束也分别 命名为BLENDHRS,PURIHRS和CS02LIM。除了指约束外，这些名字 也被Excel指为与这些约束相对应的剩余/松弛Slack/surplus 变量E。我们用单元格B2和C2来包含X 1和工2的值。约束中=0和CS-02=0）。在输入约束后，你可以用增加按 钮增加一个约束。如果你想改变约束，可以点击修改按钮，打开修改约束的对话 框。这个对话框和增加约束的对话框非常相似。为了确保Excel产生我们期待的LP Solver的输出，我们需要点 击

6、选项按钮，选中采用线性模型和假定非负，假定非负也是另 一种说x 1 , x 2 =0的方式。为了保证找到最优解，我们把允许 误差设为0%。一旦我们点击求解按钮，规划求解（Solver）会找到一个解（如 果解存在），并显示下面的窗口，允许生成一定数量的报告； 我们通常想要的是答案报告和灵敏度分析报告。下面显示了 Exce l找到的最优解和答案报告（你可以看出Slacks 已经被加到答案报告中）。如果你得到的报告和这个不同，你可能没选中“采用线性模型”。Origlnxil Vulu0Final Value6601X1Original Vrtlue00Finul Value7090faiger Ce

7、ll (Max)C：llNumeWS I Max 7ALLJEAdjustable CellsCdlName$B$2 CS-01SC$2 CS412(MistrainisCellNameCell ValueFormulaStatusSlackSDS6BLENDHRS VALUE2S0WS(y =SFS6Bmdina0SD$7PURIHRS VALUE250$D$7=$F$7Binding0SDSSCS02LIM VALUE90$D$8=0Not Binding90Excels Answer Report最优解是生产70千加仑的CS-01和90千加仑的CS-02,这会给Case Chemical

8、s带来每周$66000的利润。1.8灵敏度分析引言一旦我们找到了最优解，我们经常想知道如果问题数据发生了 变化，最优解会怎样改变。换句话说，我们想知道最优值对模 型中的某些值有多敏感。例如，我们可能会问如果Case Chemicals模型中的某些值发生变化，会发生什么。inaxiinizcsubject to(profit) (blending) (punfication) (sales limit)300 xj - 500 x22x，i - xs 230,X】一2x2 250, 0.灵敏度分析主要是用来解决这样的问题。术语上面的的式子中（1）目标函数中的300和500被称作成本（costs）

9、（2）约束中的230，250和120被称作右边（right hand sides）计算机输出的灵敏度分析在问题求解后，Excel会产生一个灵敏度的表。Case Chemicals的灵敏度报告如下所示。注意为了得到如下的 内容，你必须告诉Excel “采用线性模型”。Excel给出值的范 围，用允许增加（如CS-01的700 ,也就是值的最大到 300+700=1000 ）和减少（CS-01的50 ,也就是值最小到 300-50=250 ）的数量来表示。ChanCellsMnnlReducedObj ectiveAllowableAllowableCellNameValueCostCoeffic

10、ient(ncreaseCS-0170030070050心2CS-02900500100350CotistiintsFinalShadowConstraintAlhwnbleAllowableCellNameValuePriceRE. SideIncreaseDeciTaseSOS6BL ENDHRS VALUE23033.3333333323027090SDS7PIJRIHRS VALUE250233333333325045135SDSSCS02LIM VALUE900120IL-3030Case Chemiciih - ExcN Sensitivity Analysis ruble卜而我们

11、解释如何使用这个表。成本灵敏度分析（Cost Sensitivity Analysis ）我们考虑目标函数中成本系数的变化maximizesubject to(pmRt) (blending) (purification) (sales limit)300 400 Xi - 500 x2 2xi x档 230.xi + 2x2 250, x2 0.考虑最优解最优解是： = 0. ：=90,例如：对于Case Chemicals的问题，目标函数值（利润）是66000如果一个变量的成本发生变化，那么灵敏度分析会告诉我们 原来的最优决定是否还是最优的。例如：如果E的成本$300增加到$400，解2

12、=。，、*虬是否是 最优的？也就是，是否我们还应该生产70千加仑的CS-01和90 千加仑的CS-02?成本灵敏度分析的输出给出了新成本可以改变到的最小和 最大值而不改变最优的决定。例：对七（CS-01），成本可以变到250-1000之间的任何值，而 不改变最优解。如果新的成本在范围内，那么原来的最优解保持最优。如果 不是，那么问题需要重新求解。例：新的成本=400值的范围250-1000.在范围内？是/（否） 所以原来的解。，十=9。还是/（不是）最优的。如果原来的解还是最优的，我们可以计算新的目标函数值。 新的目标函数值二旧的目标函数值+决策变量值*成本系数变化 二旧的目标函数值+决策变量

13、值*（新的成本系数-旧的成本系数） 例：Case Chemicals新的总利润可以计算为旧的利润=$66,000决策变量的值：X.=。旧的成本系数：为的旧的成本系数是300新的成本系数：S新的成本是400新的目标函数值二旧的目标函数值+决策变量值*成本系数变化=66000+70* (400-300)=73000注意：这个分析只能用于一个变量的成本发生变化。成本分析-数值例子例1.市场的变化允许Case Chemicals在CS-01上的利润上增加 了 $200/每1000加仑。生产计划该如何改变，Case Chemicals现在最大的利润是多少？例2.由于市场的变化，CS-02的利润下降了$4

14、00/每1000加仑， 现在Case Chemicals可以获得的最大利润是多少？第一步：识别问题的变化，x2的成本系数由500变为100.第二步：检查新的成本系数是否在范围内 新的成本是100，范围是150-600，在范围内？否 第三步：如果在范围内，计算新的成本 答:最优生产计划改变了，需要重新求解。例3. CS-01和CS-02的利润分别增加了 10%和15%，CaseChemicals可以获得的最多的利润是多少?两个变化，不能回答。例4. CS-01和CS-02的利润现在都加倍了，Case Chemicals是否 应该改变他们生产CS-01和CS-02的量。由于成本的比例没变，目标函数

15、的轮廓看起来和原来一样，所 以最优解没有改变。成本灵敏度分析的图形解释 改变一个成本对应着目标函数轮廓的改变。下面显示了我们改 变CS-01 的利润(Cost on X1)原来的目标函数(Original Objective Function)原来CS-01的利润是$300,目标函数是Max 300X1+500X2图中显示了目标函数的轮廓。注意当我们向右上方移动时目标 函数是增加的。原来的最优解是x1=70,x2=90,最优的目标函数值为$300*70+$500*90=$66000云二二_新的CS-01的利润为$500目标函数是Max 500X1+500X2图中显示了目标函数的轮廓。注意当我们

16、向右上方移动时目标 函数是增加的。原来的最优解仍然是最优的。新的最优目标函数值为$500*70+$500*90=$80000检查：新的成本是否在Exce l范围内？答：是/否（是，所以最优解没有变化）original optlnial solution100新的CS-01的成本$1000目标函数是Max 1000X1+500X2图中显示了目标函数的轮廓。注意当我们向右上方移动时目标 函数是增加的。原来的最优解仍然是最优的。新的最优目标函数值为$1000*70+$500*90=$115000评论：原来的最优解是众多最优解中的一个。检查：新的成本在Exce l的范围内吗？答：是，但只是刚刚是100

17、-ongnnl apt mal soiiition1004.新的CS-01的成本$1500目标函数是Max 1000X1+500X2图中显示了目标函数的轮廓。注意当我们向右上方移动时目标 函数是增加的。原来的最优解不再是最优的。新的目标函数值是未知的。检查：新的成本在Exce l的范围内吗？答：不是。影子价格（Shadow Prices）和约束右边灵敏度分析（constraint right hand side sensitivity）我们考虑一些约束右边的变化maximizesubject to300 xi + 500 x2 2xi + X? 230, X】+ 2x2 250, X2 120

18、, X, x2 0.(profit)(blending) (pun ficatton) ( sales limit)考虑一些最优解和相关的目标函数值例：对于Case Chemicals的问题，最优解是.y： = 0. .：=90， 目 标函数值（利润）是66000。如果一个约束的右边发生变化（不是太大），那么右边的灵 敏度分析会告诉我们一旦我们改变我们的决策变量来最好 的利用变化，我们的目标函数变化了多少。例：假设净化部门的工时从250增加到了 280。如果Case Chemicals现在改变了生产计划来最好的利用这个变化，他们总 的利润增加了多少？首先检查改变的右边值是否在允许的范围内（即变

19、化不是太 大的时候）。计算机的输出给出了这个范围。例：CellNameFinalValueShadow PriceConstraint Allowable AllowableR.H. SideIncreaseDecrease$D$6BLEN0HRS VALUE23033.3333333323027090$DS7PU RIH RS VALUE250233-333333325045135$D$8CS02I IM VALUE9001201F+3030对于第二个约束（Purihrs）,允许的范围是115-295。新的值280 在这个范围内。每个约束有一个影子价格（shadow price）。影子价格给

20、出 了某个约束的右边值增加（或减少）一个单位（并在允许的范 围内）而导致的目标函数值增加（或减少）的量。例：对约束2 （Purihrs），影子价格是233.33如果新的右边在允许变化的范围内，那么目标函数的变化由 下面的式子给出，目标函数的变化=影子价格*（新的右边值-旧的右边值）。新的目标函数是：新的目标函数二原来的目标函数值+目标函数 值的变化。例：变化的利润是：233.33*（280-250）=$233.33*30=$7000.00因此，新的利润是$66000+7000=$73000.住意：（1）Shadow Prices只给出了目标函数值的变化；要找到新的 决策变量的值需要对问题用新的

21、右边变量值重新求解。（2）如果同时改变两个约束，我们需要用100%Rule。（3）如果新的右边超出了允许范围，我们需要做参数分析或 重新求解才能得出目标函数的变化。右边灵敏度分析-数值例子例1：如果混合部门有一个兼职的工人现在变成了全职，另一个兼职的工人辞职了，Case Chemicals新的利润是多少？ 第一步：识别问题中的变化约束Blending 由2x1+x2=230变为2x1+x2=230+40-15-15=240第二步：检查变化是否在允许的范围内C hanging CellsFinalReducedObjectiveAllowableAllowableCellNameVahieCosiCoefficient(ncreiiseDecreaseSBS2 CS-0170030070050SCS2 CS-02900500100:iimeValuePriceR.II. SideIncreaseDe caseSD6BLENDHRS VALUE2303X3333333323027090SDS7PURIHRS VALUE250233333333325045135SDS8CS02LIM VALUE900120IE十 3030C：ise Cliemicak sensitivity zmalysis table新的右边增加了 10,允许的范围