当前位置:论文网 > 论文宝库 > 教育教学类 > 高等教育论文 > 正文

《运筹学》教学改革研究

来源:UC论文网2019-03-23 15:18

摘要:

  [摘要]Spreadsheet方法是近年来国内外大学流行的运筹学教学方法。本文以最小费用最大流问题为例介绍了在MicrosoftExcel背景下,利用Spreadsheet方法将运筹学最小费用最大流问题进行描述、展开、建模与求解的全过程。该方法使得运筹学的理论知识简明直观、易于被学生理解与掌握,不仅有利于提高学生运用运筹学方法构建数学模型的能力,还有利于培养学生解决具体问题的实践能力。  [关...

  [摘要]Spreadsheet方法是近年来国内外大学流行的运筹学教学方法。本文以最小费用最大流问题为例介绍了在MicrosoftExcel背景下,利用Spreadsheet方法将运筹学最小费用最大流问题进行描述、展开、建模与求解的全过程。该方法使得运筹学的理论知识简明直观、易于被学生理解与掌握,不仅有利于提高学生运用运筹学方法构建数学模型的能力,还有利于培养学生解决具体问题的实践能力。


  [关键词]spreadsheet方法;最小费用最大流;运筹学;教学改革


  引言


  “运筹学(OperationalResearch)”是众多高校经济管理类专业的一门重要专业基础课。它主要以定量分析的方法来研究管理问题,将工程思想和管理思想相结合,应用系统的、科学的、数学分析的方法,通过建模、检验和求解数学模型等手段,研究各种系统的优化途径和方案,为经济管理提供决策支持。


  目前运筹学教学普遍存在偏重数学理论与解题技巧的传授,而对如何从理论到实践。加强学生解决实际问题的能力培养还关注不够。此外,老师在讲授课程时采取单一讲授方法,教学手段仍是以手算为主,而较少使用计算机以及相应的工具软件。这些教学中所存在的问题造成了有的学生对运筹学复杂的理论产生畏惧心理而不敢实践,有的学生不善于运用相关软件进行建模求解,将精力用于大量繁琐的计算中,无法取得很好的实践效果。由于运筹学是一门应用性很强的课程,为了培养学生运用运筹学知识处理实际问题的能力,运筹学的教学必须从管理工程等专业的需要考虑,以培养学生能力为主线,精心组织教学内容,适当运用多媒体教学,利用计算机软件辅助计算,进一步提高教学质量。


  Spreadsheet教学方法,是在Excel背景下将所要解决的问题进行描述与展开,建立数学模型,并使用Excel的命令与功能进行运算与分析的方法。Spreadshet提供了一种描述问题、处理数据、建立模型与解题的有效工具,其教学重点不是数学公式的推导与计算,而是注重于介绍运筹学的基本概念及基本理论,侧重于如何对复杂的实际系统进行描述与建模的技术分析,并且用计算机求解,因而避免了繁琐的数学公式,使得运筹学的理论方法简明直观、易于被学生理解与掌握,也有助于学生在今后的管理实践中应用运筹学方法与技术。


  2最小费用最大流问题的示例


  本文以最小费用最大流问题为例来说明Spreadsheet方法在运筹学教学中的优越性。


  例某石油公司拥有一个管道网络,使用这个网络可以把石油从采地运送到一些销售点,这个网络的一部分如图1所示。由于输油管道的直径与长短不同,因此每段管道(vi,vj)有不同的容量cij,同时还有不同的单位流量的费用bij,其中cij的单位为万加仑/小时,bij的单位为百元/万加仑,每段管道(vi,vj)都有对应的(cji,bij)值已在图中标出。如果使用这个网络系统从采地v1向销地v7运送运送石油,怎样运送才能运送最多的石油并使总的运送费用最小?


  根据题意,我们知道该题要求在达到石油管道流量最大的同时,实现总运送费用最小。这就是典型的最小费用最大流问题。它的一般提法为:在一个给定的网络的每一条弧上,除了给出容量cij之外,还给出了每一弧上单位流量的费用bij,当实现最大流的网络流有多种方案时,总可以在多种方案中求得一个使总费用最小的方案。


  分析题意后,需要建立数学模型,我们用线性规划来求解此题,分两步走。第一步,先求出该网络图中的最大流量,其线性规划模型如下:


  o.b.maxF=12+f12


  s.tf12-f23-f25=0


  f14-f43-f46-f47=0


  f23-f43-f35-f36=0


  f25+f35-f57=0


  f36+f46-f67=0


  f57+f67+f47=f12+f14


  0≤fij≤cij(i=1,2…6;j=0,2…7)


  其中,fij表示弧(vi,vj)上的流量,F表示网络上总的流量。目标是使网络流量最大。约束条件中的前6个方程表示网络中的流量必须满足守恒条件:中间各结点(v2―v6)的净流量为0,即总流入量必须等于总流出量;而对于发点v1,只有流出量,收点v7只有流入量,必须有发点的总流出量等于收点的总流入量。最后一个约束条件则表示每一条弧上的流量fij都需满足流量可行条件,应大于等于零,并小于等于弧(vi,vj)的容量cij。


  第二步,在满足最大流量为F的前提下,求出一个最小费用解,其线性规划模型如下:


  o.b.minz=fij・bij


  s.t.f12+14=Ff12-f23-f25=0


  f14-f43-f46-f47=0


  f23+f43-f35-f36=0


  f25+f35-f57=0


  f36+f46-f67=0


  f57+f67-f47=f12+f14


  0≤fij≤cij(i=1,2…6;j=0,2…7)


  即目标是求流量的最小费用,约束条件在原模型基础上又增加了总流量必须等于最大流量F的约束,即f12+f14=F。


  下面介绍利用Spreadshet方法对最小费用最大流问题进行描述、展开、建模与求解的全过程。打开Excel后,出现工作表。该工作表用作描述问题与建立模型时,称为Spreadsheet。在Spreadshet上建模求解最小费用最大流问题的基本步骤如下:


  2.1首先在Spreadsheet中建立最大流模型,输入相应的公式和数据,可以与第一步中的线性规划模型相对应,如表1所示。单元格B15825称为可变单元格,用于存放模型求解的结果(也代表模型的决策变量),即网络实现最大流时各弧上的流量。B2单元格表示目标函数,需要在其中输入公式,模型求解后,即可以得到最大流量值F;在单元格B7B12中,也需要输入公式,分别表示各结点的净流量,它们应满足守恒条件。


  2.2最大流问题规划求解过程。打开Excel菜单栏中的“工具”菜单,在下拉菜单中选择“规划求解”选项,出现规划求解参数对话框,在对话框中输入相应的目标函数、决策变量与约束条件,如图2所示。


  单击对话框中的“选项”按钮,在出现的“规划求解选项”对话框中,选择“采用线性模型”和“假定非负”,选择“确定”。单击对话框中的“求解”按钮后,即可在可变单元格中得到各弧上的流量值,同时在目标函数单元格中得到了最大流量值,如表2所示。


  即如果使用该网络系统从产地vl向销地v7运送石油,每小时最多能运送10万加仑石油。


  2.3最小费用最大流问题描述与建模。根据上面的运行结果已经知道最大流为10万加仑/小时,各管道的流量分布为5、5、2、3、2、2、2、1、2、5、3万加仑/小时。但是达到最大流的流量分布是否只有这一种?这样的流量分布能否使总费用最小呢?为此,我们再次利用Spreadsheet建立相应的模型如下(与第二步的线性规划模型相对应):


  注意该表与表1的区别为B2单元格中输入的公式表示总运送费用,模型求解后,即可以得到最小费用值;增加了最大流量的约束条件:单元格B4中输入的公式表示网络中的总流量,它应等于最大流量值10。


  2.4最小费用最大流问题规划求解过程:打开Excel菜单栏中的“工具”菜单,在下拉菜单中选择“规划求解”选项,出现规划求解参数对话框,在对话框中输入相应的目标函数、决策变量与约束条件,如图3所示。注意此时设置目标单元格为最小值。


  单击对话框中的“选项”按钮,在出现的“规划求解选项”对话框中,选择“采用线性模型”和“假定非负”,选择“确定”。单击对话框中的“求解”按钮后,即可在可变单元格中得到各弧上的流量值,同时在目标函数单元格中得到了最小费用值,如表4所示。


  由此可见达到最大流的流量分布并不唯一,实现最小费用最大流时各管道流量分布应该是:4、6、1、3、2、2、3、1、2、5、3万加仑/小时,此时网络流量达到最大10万加仑/小时,同时实现了14500元的最小总运送费用,而如果按照第一种方案的流量分布,虽然也实现了最大流量,但总运送费用却高达15100元。


  3总结


  网络分析是应用十分广泛的运筹学分支,在生产实践和社会生活中有着重要意义。而最小费用最大流是其中比较有代表性的问题,也是一个不容易手算求解的问题。从上文最小费用最大流问题的示例可以看出,Spreadsheet方法以一种直观的方式进行问题描述与建模,与我们的分析思路以及线性规划模型相互对应,简便易懂,求解方便,因此,可以充分发挥该方法在运筹学教学中的积极作用。Spreadsheet教学方法可以使学生投入更多的精力在问题的描述与建模上,摆脱为求解问题而进行繁琐计算的苦恼,从而有助于学生对运筹学理论知识的理解,提高其构建数学模型的能力,同时还有利于培养学生动手解决具体问题的实践能力。

核心期刊推荐