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的利润
1
Maximize 利润=CS-01利润+CS-02的利润 =300x1+500x2
Max 300x1+500x2
(3)约束条件
混合部门的总工时的约束
2x1+1x2<=5*40+2*15=230
净化部门的总工时的约束
x1+2x2<=6*40+1*10=250
CS-02的销售数量的约束
x2<=120
变量的非负约束
x1，x2>=0.
数学模型
2
Max 300x1+500x2
St. 2x1+1x2<=230 blending
1x1+2x2<=250 purification
X2<=120 CS-02
x1,x2>=0 nonnegative
Excel规划求解
Excel规划求解的选项可以用来解决线性规划问题。可以设置决策变量为整数约束。规划求解可以用来解决最多有200个变量，100个外在约束和400个简单约束（决策变量整数约束的上下边界）的问题。
安装线性规划加载项
Excel 2003：菜单栏——工具——加载宏——规划求解
3
调用规划求解，从主菜单中选择工具/规划求解。
Excel 2007：Office按钮——Excel选项——加载项——转到——加载宏——规划求解加载项
4
在“数据”选项卡中出现带有“规划求解”按钮的“分析”组
输入数据
在Excel中输入问题数据，我们即可以输入原来的形式也可以输入标准的计算形式。通常我们就输入原来的形式，让Excel自己把它变成标准形式。因此，我们输入如下形式。
5
下图显示了输入这个问题后的屏幕，我们把变量
x1称为“CS-01”x，变量2称为
“CS-02”。我们把三个约束也分别命名为BLENDHRS,PURIHRS和CS02LIM。除了指约束外，这些名字也被Excel指为与这些约束相对应的剩余/松弛Slack/surplus变量
。
我们用单元格B2和C2来包含
x1和x2的值。约束中‘<=’的符号只是给我们自己
6
看的，我们需要告诉规划求解（Solver）这些符号。下面显示的是单元格所用的公式(formulae)。注意在单元格D4中我们需要输入公式来计算目标函数（这个例子中，“=B4*B2+C4*C2”,其中*在Excel中指的是乘的意思），在D6到D8中输入公式来计算每个约束（如果你没有用过Excel，公式中的$符号，你可以不用管；它只是一个捷径）。注意作为一个捷径，在单元格D6中我们也可以输入=SUMPRODUCT($B$2:$C$2,B6:C6)，然后拷贝和粘贴这个公式到单元格D7和D8中。当问题比较大的时候，这个会比较有用。
一旦我们设置好问题之后，我们可以从工具菜单中选择‘规划求解’（Solver）,我们需要告诉规划求解参数对话框我们的问题。
7
这个例子中，单元格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）。在输入约束后，你可以用增加按钮增加一个约束。
8
如果你想改变约束，可以点击修改按钮，打开修改约束的对话框。这个对话框和增加约束的对话框非常相似。
为了确保Excel产生我们期待的LP Solver的输出，我们需要点击选项按钮，选中采用线性模型和假定非负，假定非负也是另一种说我们把允许误差设为0%。
x1,x2>=0的方式。为了保证找到最优解，
9
一旦我们点击求解按钮，规划求解（Solver）会找到一个解（如果解存在），并显示下面的窗口，允许生成一定数量的报告；我们通常想要的是答案报告和灵敏度分析报告。
10
下面显示了Excel找到的最优解和答案报告（你可以看出Slacks已经被加到答案报告中）。如果你得到的报告和这个不同，你可能没选中“采用线性模型”。
11
最优解是生产70千加仑的CS-01和90千加仑的CS-02,这会给Case Chemicals带来每周$66000的利润。
1.8灵敏度分析
引言
一旦我们找到了最优解，我们经常想知道如果问题数据发生了变化，最优解会怎样改变。换句话说，我们想知道最优值对模型中的某些值有多敏感。例如，我们可能会问如果Case Chemicals模型中的某些值发生变化，会发生什么。
灵敏度分析主要是用来解决这样的问题。
术语
上面的的式子中
（1）目标函数中的300和500被称作成本（costs）
12
（2）约束中的230，250和120被称作右边（right hand sides）
计算机输出的灵敏度分析
在问题求解后，Excel会产生一个灵敏度的表。
Case Chemicals 的灵敏度报告如下所示。注意为了得到如下的内容，你必须告诉Excel“采用线性模型”。Excel给出值的范围，用允许增加（如CS-01的700，也就是值的最大到300+700=1000）和减少（CS-01的50，也就是值最小到300-50=250）的数量来表示。
13
下面我们解释如何使用这个表。
14
成本灵敏度分析（Cost Sensitivity Analysis）
我们考虑目标函数中成本系数的变化
1. 考虑最优解
例如：对于Case Chemicals的问题，最优解是是66000
，目标函数值（利润）
2. 如果一个变量的成本发生变化，那么灵敏度分析会告诉我们原来的最优决定是否还是最优的。
例如：如果的成本$300增加到$400,解是否是最优的？也就是，
是否我们还应该生产70千加仑的CS-01和90千加仑的CS-02?
3. 成本灵敏度分析的输出给出了新成本可以改变到的最小和最大值而不改变最优的决定。
15
例：对（CS-01）,成本可以变到250-1000之间的任何值，而不改变最优解。
4. 如果新的成本在范围内，那么原来的最优解保持最优。如果不是，那么问题需要重新求解。
例：新的成本=400 值的范围 250-1000. 在范围内？是/（否）所以原来的解还是/(不是)最优的。
5. 如果原来的解还是最优的，我们可以计算新的目标函数值。
新的目标函数值=旧的目标函数值+决策变量值*成本系数变化
=旧的目标函数值+决策变量值*（新的成本系数-旧的成本系数）例：Case Chemicals新的总利润可以计算为
旧的利润=$66,000
决策变量的值：
旧的成本系数：的旧的成本系数是300
16
新的成本系数：新的成本是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，在范围内？否
17
第三步：如果在范围内，计算新的成本
答:最优生产计划改变了，需要重新求解。
例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
18
图中显示了目标函数的轮廓。注意当我们向右上方移动时目标函数是增加的。
原来的最优解是x1=70,x2=90, 最优的目标函数值为$300*70+$500*90=$66000
2.
新的CS-01的利润为$500
目标函数是Max 500X1+500X2
图中显示了目标函数的轮廓。注意当我们向右上方移动时目标函数是增加的。
原来的最优解仍然是最优的。新的最优目标函数值为$500*70+$500*90=$80000
检查：新的成本是否在Excel范围内？
答：是/否(是，所以最优解没有变化)
19
3. 新的CS-01的成本$1000
目标函数是Max 1000X1+500X2
图中显示了目标函数的轮廓。注意当我们向右上方移动时目标函数是增加的。
原来的最优解仍然是最优的。新的最优目标函数值为$1000*70+$500*90=$115000
评论：原来的最优解是众多最优解中的一个。
检查：新的成本在Excel的范围内吗？答：是，但只是刚刚是
20
4.
新的CS-01的成本$1500
目标函数是Max 1000X1+500X2
图中显示了目标函数的轮廓。注意当我们向右上方移动时目标函数是增加的。
原来的最优解不再是最优的。
新的目标函数值是未知的。
检查：新的成本在Excel的范围内吗？答：不是。
21
影子价格（Shadow Prices）和约束右边灵敏度分析(constraint right hand side sensitivity)
我们考虑一些约束右边的变化
1. 考虑一些最优解和相关的目标函数值
例：对于Case Chemicals的问题，最优解是是66000。
，目标函数值（利润）
2. 如果一个约束的右边发生变化（不是太大），那么右边的灵敏度分析会告诉我们一旦我们改变我们的决策变量来最好的利用变化，我们的目标函数变化了多少。
例：假设净化部门的工时从250增加到了280。如果Case Chemicals现在改变了生产计划来最好的利用这个变化，他们总的利润增加了多少？
3. 首先检查改变的右边值是否在允许的范围内（即变化不是太大的时候）。计算机的输出给出了这个范围。
22
例：
对于第二个约束（Purihrs）,允许的范围是115-295。新的值280在这个范围内。
4. 每个约束有一个影子价格（shadow price）。影子价格给出了某个约束的右边值增加(或减少)一个单位（并在允许的范围内）而导致的目标函数值增加（或减少）的量。
例：对约束2（Purihrs）,影子价格是233.33…
5. 如果新的右边在允许变化的范围内，那么目标函数的变化由下面的式子给出，
目标函数的变化=影子价格*（新的右边值-旧的右边值）。
新的目标函数是：新的目标函数=原来的目标函数值+目标函数值的变化。
例：变化的利润是：
233.33*(280-250)=$233.33*30=$7000.00
因此，新的利润是
23
$66000+7000=$73000.
注意：
（1）Shadow Prices只给出了目标函数值的变化；要找到新的决策变量的值需要对问题用新的右边变量值重新求解。
（2）如果同时改变两个约束，我们需要用100%Rule。
（3）如果新的右边超出了允许范围，我们需要做参数分析或重新求解才能得出目标函数的变化。
右边灵敏度分析-数值例子
例1：如果混合部门有一个兼职的工人现在变成了全职，另一个兼职的工人辞职了，Case Chemicals新的利润是多少？
第一步：识别问题中的变化
约束Blending 由2x1+x2<=230变为2x1+x2<=230+40-15-15=240
第二步：检查变化是否在允许的范围内
24
新的右边增加了10，允许的范围是：减少90，增加270。在范围内。
第三步：计算新的利润。
影子价格=33.3333
目标函数的变化=影子价格*（新的右边的值-旧的右边值）
=33.33*10=333.33
新的目标函数值=原来的目标函数值+目标函数值的变化=66000+333.33=66333.33.
例2：净化部门的罢工导致了20%的工时减少。如果Case Chemicals调整生产来很好的处理罢工，罢工会影响多少利润？
25
例3.一个竞争对手公司从混合部门挖走了3个全职的工人，这会影响多少利润？
例4.在混合部门，工人们可期待的最多的加班费（$/小时）是多少？
例5. 如果混合部门的一个兼职的工人调到了净化部门，利润会发生怎样的变化？
影子价格的图形解释
原来的Case Chemicals问题中包含约束
X1+2x2<=250 (PuriHrs)
图形中约束‘PuriHrs’用粗线表示。
26
如果由于某种原因250小时的工时约束发生了改变,会发生什么？
例如，考虑净化部门的工时从250增加到了280，这使约束朝着远离原点的方向移动。
约束改变，Case Chemicals能够改变生产来增加利润。（这种情况，Case Chemicals生产的CS-01少了，CS-02多了。）
每个额外的净化工时值多少钱呢？
从灵敏度表中看出，这个约束的影子价格是$233.33.因此，每次我们增加单位右边值，目标函数的值就会增加$233.33。
练习:
27
1.如果我们减少右边的值从250到249，目标函数的值会发生怎样的变化？
2.如果我们一直增加净化部门的工时，目标值会发生什么变化？
3.如果我们净化部门的工时从295到296，增加的1个小时的工时是否能带来$233.33的利润？
答：不能。
影子价格在一定的范围内工作。
28