运筹学实验3用Excel求解线性规划模型
实验三、用Excel求解线性规划模型
线性规划问题用手工求解工作量很大,而且没有较高的数学基础很难理解其计算过程和方法,但是借助Excel“规划求解”工具,就能轻而易举地求得结果。Excel最多可解200个变量、600个约束条件的问题。下面我们以一实例介绍利用Excel规划求解工具怎样快速解决具体的经济决策问题。
一、实验目的
1、 掌握如何建立线性规划模型。
2、 掌握用Excel求解线性规划模型的方法。
3、 掌握如何借助于Excel对线性规划模型进行灵敏度分析,以判断各种可能的变
化对最优方案产生的影响。
4、 读懂Excel求解线性规划问题输出的运算结果报告和敏感性报告。
二、 实验内容
1、 [工具][规划求解]命令
规划求解加载宏是Excel的一个可选安装模块,在安装Excel时,只有在选择“完全/定制安装”时才可选择装入这个模块。在安装完成进入Excel后还要用[工具][加载宏]命令选中“规划求解”,以后在[工具]菜单下就增加了一条[规划求解]命令。
使用[规划求解]命令的一般步骤为:
第一步:在选取[工具][规划求解]命令后,弹出图1所示“规划求解参数”对话框,其中各选项说明如表1。
图1“规划求解参数”对话框
图2
图3
第二步:完成图1所示的一切填入项目后,单击“选项”按钮,在弹出的“规划求解选项”对话框中若是线性模型则选取“采用线性规模”选项按钮,再单击“确定”按钮回到图1
。
图4
第三步:在图1中单击“求解”按钮,经计算完成后弹出“规划求解结果”对话框(图5)。
图5
第四步:在图5中单击“确定”按钮,则只将优化计算结果显示在表格设置中的可变单元格(决策变量)和目标单元格(目标函数)内。
在图5的“报告”框中有3个选项,每个选项对应着一个报告,各报告以单一工作表记载,它们不仅能给出优化结果,甚至还给出更重要信息,例如影子价格等。
2、 产品生产品种结构优化问题 数学模型 示例:一家制药厂生产两种产品:药品Ⅰ和药品Ⅱ。每个产品要用到一种相同的原料A,并要经过一道相同的工序,在机器B上包装 。因为这两种产品可以使用同样的机器,所以它们可以轮换使用设备,从而使其生产设施得到较充分的利用。
问该制药厂应该如何安排生产计划才能使企业的利润最大。
我们知道,如果分别设药品Ⅰ和药品Ⅱ的生产数量为x1和x2,那么该问题的线性规划模型如下:
maxZ=50x1+100x2
⎧2x1+x2≤400(原料A)⎪
⎪x1+x2≤300(机器B)⎪
s.t.⎨x2≤250(原料C)
⎪x≥0(药品I的最低产量)⎪1⎪⎩x2≥0(药品II的最低产量)
表格设置与公式说明
根据本问题的规模和条件,拟设置如表1中A1︰E8所示形式:
⑴区域B3︰C6和E3︰E5为原始数据区,输入如表1中所示的原始数据。
表4
⑵在单元格B8内输入数学模型中目标函数的计算公式,并求最大值。 ⑶单元格B7︰C7分别作为药品Ⅰ和药品Ⅱ的产量(即决策变量x1、x2),即可变单元格。其初始值设为0,求解过程中计算机会自动输入各组试验值。
⑷区域D3︰D5内的各单元格依次输入三个约束条件对应式的左侧部分。
操作步骤
第一步:选择[工具][规划求解]命令,弹出图1所示对话框。根据本问题的性质,在“设置目标单元格”文本框内填入$B$8,在“等于”选项后选取“最大值”,在“可变单元格”文本框内填入$B$7︰$C$7。
第二步:单击“添加”按钮,弹出图2所示对话框。该步骤的任务是要把前面数学模型中的全部约束条件一个一个地填入图1所示的“约束”列表框内。图2所示就是填入三个资源约束条件的情形:在左边“单元格引用位置”文本框内填入$D$3︰$D$5(可直接录入、或用鼠标拖入)、单击中间向下小箭头并选取符号“
第三步:重复第二步,录入$B$7︰$C$7>=0,即两决策变量的值必须大于0,最后如图1所示。
第四步:在图1中单击“选项”按钮,弹出图4对话框。因本例题属于线性规划问题,选取“采用线性模型”按钮,再单击“确定”按钮,回到图1。
第五步:在图1中选取“求解”按钮或击回车键,Excel进入规划求解运行过程,屏幕左下角状态条上逐次显示运行过程报告。一旦计算结束,弹出图5的对话框。在图5内可以有四种选择:
⑴若单击“确定”按钮或击回车键,则显示如表2的结果。可变单元格$B$7︰$C$7内显示最优生产计划,即药品Ⅰ生产50件和药品Ⅱ生产100件,可获得最大利润27500元;单元格$D$3︰$D$5分别给出了各种资源的用量,只有原料A有50千克的剩余。
表
5
⑵若选择“运算结果报告”,Excel显示“运算结果报告”,其中表示求解本问题中已经连续第几次选择该选项,我们这里给出的是“运算结果报告1”(如表6),即在同一文件内首次选择该选项。表6比较全面地报告了优化结果信息,包括目标单元格的位置、名称、初值和终值,可变单元格的位置、名称、初值和终值,约束单元格位置、名称、单元格内计算结果、单元格相应约束式、运算结果达到的状态(型数值为0表示到达限制值、否则未到达限制值)。
⑶若选择“敏感性报告”,Excel显示“敏感性报告”(如表7)。敏感性报告表的限制式中“阴影价格”(经济学中称影子价格、Shadow Price)是一个有特别意义的经济指标。
表6
Microsoft Excel 9.0 运算结果报告 工作表 [习题一.xls]Sheet2 报告的建立: 2006-8-24 19:22:29 单元格 $B$8 单元格 $B$7 $C$7 约束 单元格 $D$3 $D$4 $D$5 $B$7 $C$7
原料A 机器B 原料C
决策变量 产品1 决策变量 产品2
名字
决策变量 产品1 决策变量 产品2
名字
名字
目标函数
初值
0 0
公式
初值
终值
目标单元格 (最大值)
终值
50 250
状态
27500
型数值
50 0 0 50 250
可变单元格
单元格值
350 $D$3=0 250 $C$7>=0
未到限制值 未到限制值
影子价格的经济学意义是,使在最优利用下的紧缺资源增加1个单位,将为企业创造的利润。
用影子价格与各紧缺资源的市场价格相比较,可以为企业是否购买紧缺资源扩大生产提供决策依据。有剩余的资源影子价格为0。
表7
Microsoft Excel 9.0 敏感性报告 工作表 [习题一.xls]Sheet2 报告的建立: 2006-8-25 11:01:22
单元格 $B$7 $C$7 约束
单元格 $D$3 $D$4 $D$5
原料A 机器B 原料C
名字
决策变量 产品1 决策变量 产品2
名字
值 成本 50 250
终 阴影 350 300 250
0 50 50 0 0 约束
400 300 250
可变单元格
系数
50 100
允许的 增量 1E+30 25 50
允许的 增量
50 1E+30
允许的 减量
50 50 50
允许的 减量
50 50
终 递减 目标式
值 价格 限制值
⑷若选择“极限值报告”,Excel显示“极限值报告”(如表8)。除了给出最优决策对应最优目标值信息外,还显示各决策变量的上、下限值及其对应目标式结果。
表8 Microsoft Excel 9.0 极限值报告 工作表 [习题一.xls]Sheet2 报告的建立: 2006-8-25 11:02:45 单元格 单元格
变量 名字
目标式 名字
值 27500 值 50 250
下限 极限
0 0 目标式 结果 25000
上限 极限
50
目标式 结果
27500
$B$8 最大利润
$B$7 决策变量 产品1 $C$7 决策变量 产品2
2500 249.9999999 27499.99999
3、读懂Excel求解线性规划问题输出的运算结果报告和敏感性报告
利用Excel求解线性规划问题系统将提供三个计算结果报告,即运算结果报告、敏感性报告、极限值报告。这三个报告中的前两个报告非常重要,下面我们将结合教材第二章线性规划的对偶理论与灵敏度分析的内容讲述如何看Excel求解线性规划问题输出的运算结果报告和敏感性报告。
⑴读懂运算结果报告
运算结果报告比较容易看懂,可变单元格$B$7和$C$7分别表示两个决策变量,即药品Ⅰ和药品Ⅱ的产量,在计算时,由于我们最初赋予x1=0,x2=0,所以单元格$B$7和$C$7的初值为0,求得最优解后,$B$7和$C$7的值分别为50和250,即x1=50,x2=250,表示使目标函数值最大的计划是生产50个单位的药品Ⅰ和250个单位的药品Ⅱ。目标单元格$B$8表示目标函数maxz=50x1+100x2,由于我们最初赋予x1=0,x2=0,所以目标函数的初值为0,求得最优解后,目标函数的值为27500,即,如果生产50个单位的药品Ⅰ和250个单位的药品Ⅱ能使企业利润达到最大值27500元。
x1+x2在单元格$D$3、$D$4、$D$5我们分别输入了三个约束条件的左边项,即2x1+x2,
和x2,随后在使用[工具][规划求解]时,在[规划求解参数]窗口,我们输入了
$D$3≤$E$3,$D$4≤$E$4,$D$5≤$E$5,而$E$3=400、$E$4=300、$E$5=250,从而完成
了约束条件的输入。当求得最优解x1=50,x2=250后,将x1=50,x2=250代入约束方程得:
未达到限制值,型数值为50;$D$3=2x1+x2=350≤$E$3,$D$4=x1+x2=300=$E$4,达到限制值,型数值为0;$D$5=x2=250=$E$5,达到限制值,型数值为0。
⑵读懂敏感性报告可变单元格$B$7、$C$7分别表示两个决策变量x1 和x2,在求得最优解后x1=50,x2=250,即敏感性报告中所显示的$B$7、$C$7的终值分别为50和250。x1 在目标函数中的系数为50,允许的增量为50,允许的减量为50,意思是当x1 在目标函数中的系数在50的基础上再增加50或减少50,该线性规划问题的最优解不变,即在其他条件不变的情况下,当0≤c1≤100时,x1=50,x2=250仍然是线性规划问题的最优解。同理,x2在目标函数中的系数为100,允许的增量为1E+30,允许的减量为50,意思是当x2 在目标函数中的系数在100的基础上再增加1E+30或减少50,该线性规划问题的最优解不变,即在其他条件不变的情况下,当c2≥50时,x1=50,x2=250仍然是线性规划问题的最优解。当求得最优解后,单元格$D$3、$D$4、$D$5的值分别为350,300和250,即50
个单位的药品Ⅰ和250个单位的药品Ⅱ,消耗了原料A350千克、机器B300小时,原料C250千克。由于企业拥有的原料A、机器B,原料C的数量分别是:400千克300小时和250千克,所以生产50个单位的药品Ⅰ和250个单位的药品Ⅱ消耗掉了企业的拥有的全部机器B设备时数和原料C,但原料A还有50千克的剩余。
三种资源的阴影价格分别为0、50、50,即该线性规划问题的对偶问题的最优解为
y1=0,y2=50,y3=50意思是:保持其他生产条件不变,每增加1个单位的原料A使目标
函数增加的数量为0,每增加1个小时的设备B使目标函数增加的数量为50,每增加1个单位的原料C使目标函数增加的数量为50。
约束限制值分别为400、300和250,即企业拥有的原料A、机器B,原料C的数量分别是:400千克300小时和250千克。原料A的允许的增量为1E+30,允许的减量为50,意思是原料A在现有数量的基础上再增加1E+30或减少50,原料A的影子价格不变,即在其他条件不变的情况下,当b1 ≥350时,y1=0。同理可得:当250≤b2 ≥325时,y2=50;当200≤b2 ≥300时,y3=50。课外练习
1、利用Excel试算教材后面的习题,然后与手工计算的结果进行对比。
2、练习利用线性规划模型制订总体计划。例:红西红柿公司是一家园艺工具生产商,公司主要是将购进的原材料制造成多用途的园艺工具。由于生产线需要的工具和场地是有限定的,红西红柿公司的生产能力主要由劳动力人数决定。该公司的产品需求季节性很强,需求最旺的时间在春季。该公司决定利用总体计划来克服需求季节性变动的障碍,同时实现利润最大化。公司的选择是,在淡季建立库存,当旺季到来时增加工人,签订转包合同,交积压订单登记入册,以后再将产品送达顾客。为了知道如何利用总体计划中的这些选择,“红西红柿”供应链的副总裁从预测下6个月的需求着手工作,如表9所示。
该公司以40美元的单价销售其工具。公司在1月的库存为1000个工具,在1月初有80名
员工。每个月每条生产线有20个工作日,每个工人每小时收入4美元。每个工人每天工作8小时,其余时间休息。如前所述,生产线的生产能力主要取决于工人工作总时数。所以,机器的生产能力并不限制生产线的生产能力。根据劳动法规定,工人每月加班不能超过10小时。各种成本如表10所示。
目前,红西红柿公司在转包合同、库存缺货或积压上没有什么限制。所有库存缺货被积累起来,由下一个月生产出来的产品来满足。库存成本在当月库存结清时才计入。供应链管理者的目标是,制定出一个最合理的总体计划,它将使库存量在6月底至少为500个单位,即6月底没有库存缺货,而是至少有500个单位的库存量。问企业应该如何制定总体计划才能使总成本最小。
表10“红西红柿”工具公司的成本
3、捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积如表1所示。仓库租借费用随合同期而定,期限越长,折扣越大,具体数据见表2。租借仓库的合同每月初都可办理,每份合同具体规定租用面积和期限。因此该厂可根据需要,在任何一个月初办理租借合同。每次办理时可签订一份合同,也可签订若干份租用面积和租借四、 实验要求
1、 2、 3、 4、 1、 2、 3、
课前预习,写出实验提纲;
能建立常见的线性规划模型,并用Excel进行运算。
能看懂Excel输出的结果报告,了解结果的经济学含义,以将计算结果用于指导企业经营实践。
根据实验目的和实验内容写出实验报告。 单元格引用地址 单元格公式显示
SUMPRODUCT函数的使用。
五、 指示指导