运筹学“运输问题”的教学方法探讨.doc

1、运筹学“运输问题”的教学方法探讨【摘要】 用运筹学的思想探讨运筹学课程的教学方法。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题，从而可以统筹安排这些教学内容，为提高教学效果，减少教学时间找出更优的教学方法。 【关键词】 运输问题; 转运问题; 运筹学; 教学方法运筹学是一门应用科学，它运用数学方法对经济和管理系统中的各种有限资源进行统筹安排，为决策者提供最优参考方案，以实现有效的科学管理。运筹学是管理类专业的专业基础课，对管理类人才培养有着重要的意义。该课程的特点是将数学知识、数学建模、经济管理与计算机应用四者融为一体，通过各类实际问题的案例，培养学生分析、解决实际

2、问题的能力。该课程本身有一定的难度，作为教师，应努力探索教育教学规律，认真把握课程的特点，以获得良好的教学效果。如何在现有的有限资源条件下(如学时、生源、师资)，将这门课上好，不也正是运筹学研究的内容吗?运筹学涉及内容较多，线性规划是最主要的一个分支，其理论最完善、方法最成熟，应用也最广泛，涉及的很多问题都是经典的问题，如运输问题、指派问题、最短路问题，最小费用流问题等。自己在运筹学教学过程中发现，这些问题有相同的共性，可以归结为同一个问题，从而可以统筹安排教学内容，为运筹学课程提高教学效果，减少教学时间找出更优的教学方法。1 运输问题和转运问题1.1 运输问题运输问题一般指货物可直接从产地运

3、往销地。下面以运费问题为例进行说明。记 si 为产地 Ai(i=1,2,n) 的产量，dj 为销地 Bj(j=1,2,m) 的销量，cij 为把货物从产地 Ai 运往销地 Bj 的单位运价。设 xij 为从产地 Ai 运到销地 Bj 的货物量，则运费最少的产销平衡问题的线性规划模型为1,4：目标函数 min z=ni=1 mj=1cijxij约束条件 mj=1xij=si ，(i=1,2,n) (1)ni=1xij=dj ，(j=1,2,m) (2)xij0 ,对所有的 i 和 j 。对于不同的实际问题，有时还需加一些约束条件。例如，当货物量的单位为“件” 、 “箱”时，还需加上 xij 为整

4、数的约束条件。对于产销不平衡问题一般用两种方法解决：第一种方法是建立一个假想(虚拟)的产地或销地，根据实际问题，将从产地运往销地的单位运价设为 0 或一个很大的数，再转化为产销平衡问题，这一方法比较复杂一些。另一种更简单的方法是，对产大于销问题，将(1)式中的等式变为 ，对销大于产问题，将(2)式中的等式变为 ，这种方法更直观，易于学生理解和掌握。1.2 转运问题转运问题是运输问题的一个扩充，当产地的货物不能直接运往销地时，需通过中转站。记产地为发点，销地为收点，中转站为中转点，cij 为把货物从点 i 运往点 j 的单位运价。设 xij 为从点 i 运往点 j 的货物量，则运费最少的产销平衡

5、转运问题的线性规划模型为1,4 ：目标函数 min z= 所有的弧 cijxij约束条件 ：对发点 i 有 所有的流出量 xij- 所有的流入量xij=si (3)对中转点有 所有的流出量 xij- 所有的流入量 xij=0 (4)对收点 j 有 所有的流出量 xij- 所有的流入量 xij=di (5)xij0 ，对所有的 i 和 j 。对于产销不平衡问题，可根据实际问题将(3)或(5)式中的等号改为不等号。2 可转化为运输问题的问题2.1 指派问题一般的指派问题为1,4：有 n 项任务，恰好有 n 个人可分别承担这些任务，由于各人特长不同，完成各项任务的效率等情况(如时间)也不同，现假设必

6、须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使完成 n 项任务的总效率最高。以完成任务的效率是时间为例，说明指派问题可转化为运输问题。将每个人看成产地，产量均为 1，si=1 ，即每个人生产出一个劳动力;将每项工作看成销地，销量为 1，dj=1 ，即每项工作需要一个劳动力来完成;将每个人完成各项任务的时间看成单位运价 cij ;设 xij=1 为指派第 i 个人完成第 j 项工作，设 xij=0 为不指派第 i 个人完成第 j 项工作，则上述指派问题可转化为产销平衡的运输问题。当任务项数多于人数时，可看成是销大于产的情况，当人数多于任务项数时，可看成是产大于销的情况，由此可

7、转化为产销不平衡的运输问题。2.2 特殊的背包问题一般的背包问为1：设背包携带物品的重量限制为 W ，N 种物品中第 i 种物品的重量为 wi ，价值为 ci ，总数量为 ni ，如何决定这 N 种物品中的每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。考虑 wi 都相等的特殊情况，即每种物品的重量都相等，不妨设为1。将第 i 种物品看成产地 Ai ，产量为 ni ;将背包看成唯一的一个销地，销量为 W ，将第 i 种物品的价值负数看成单位运价-ci ，设 xi 为携带的第 i 种物品的数量，则这种背包问题可转化为销大于产的的运输问题。3 可转化为转运问题的问题3.1 最短路问题一

8、般的最短路问题为1：对一个赋权的有向图，找到一条从一个指定的起点到另一个指定的终点的路，使这条路上所有弧的权数的总和最小。将起点看成唯一的一个产地(发点)，产量为 1;将终点看成唯一的一个销地(收点)，销量为 1;将其余点看成中转点，任两点的权看成单位运价，并设 xij=1 为最短路经过弧(i ，j )， xij=0 为最短路不经过弧(i ，j )，则最短路问题可转化为产销平衡的转运问题。在实际应用中遇到更多的是无向图的最短路问题。这时需将无向图添加方向变为有向图。由于最短路不可能由起点出发再回到起点，到了终点也不会再转向其它点，而其它情况的各种可能性都有，所以可用如下方法为无向图添加方向：与

9、起点相连的弧，方向由起点指向另一点;与终点相连的弧，方向由另一点指向终点;与起点、终点无关的弧，给出双向的方向(图 1)。弧(i ，j )和弧(i ，j )权相同。图 1 无向图(左)添加方向成为有向图(右)，其中 1 为起点，5 为终点3.2 最大流问题一般的最大流问题为1 ：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。记发点为 v1 ，收点为 vn ，fij 为弧(vi,vj) 上的容量，M=rk=2f1k ，各条弧上的单位运价为 c1k=-1 ，k=2,3,r ，其余cij=0 。设 xij 为弧(vi,vj) 上的流量，则

10、上述最大流问题可转化为只有一个产地(发点)，产量为 M，只有一个销点(收点)，销量为rk=2x1k 的产大于销的转运问题：目标函数 min z= 所有的弧 cijxij=-rk=2x1k 约束条件 ：对发点 1 有 rk=2x1kM (6)对中转点有 所有的流出量 xij- 所有的流入量 xij=0对收点 n 有 所有的流入量 xin=rk=2x1k0xijfij ，对所有的 i 和 j 。其实(6)式是多余的，由 0xijfij 可以得到，这里仅为了说明该问题可转化为转运问题。3.3 最小费用流问题一般的最小费用流问题为4：给了一个带收发点的网络，对每一条弧除给出了容量外，还给出了这条弧的单

11、位流量的费用，要求一个可行流，并使得总运送费最小。若可行流是最大流时，则为最小费用最大流问题。最小费用最大流问题分两步解，第一步，先求出最大流 F;第二步，在最大流 F 的所有解中，找出一个最小费用的解。关于第一步求最大流问题，已在前面讨论过。第二步求最小费用问题，将发点看成唯一的产地，产量为 F(或可行流)，将收点看成唯一的销地，销量为 F(或可行流)，每条弧的单位流量的费用看成单位运价，由此可转化为产销平衡的转运问题。4 讨论在教学中，将看似不同的问题归纳转化为同一问题，非常重要。首先，这涉及到教学内容的结构问题，原来看似不同的问题可能在教材的不同章节，转化为同一问题后可并入同一章节。第二

12、，对提高教学效果有一定的帮助。对老师而言，可减少教学时间，原先要花较多时间讲解不同的问题，现在只需讲解一个问题，然后作为同一问题举一反三，不仅可将原问题讲授得更清楚，也解决了新问题。对学生而言，原先要记多种问题的解法，现在只需记一种解法就可以了，减轻了学习负担。第三，更重要的是，启发学生对问题有更深入的理解，抓住事物的本质，而不是停留在表面，这对培养学生抽象思维、综合归纳能力是大有裨益的。当然，要做到这一点，对老师的要求显然更高，必须要花更多的时间和精力研究问题，吃透教材，理解精髓，融会贯通，非一般的应付教学所能解决的。最后，在用计算机求解方面，可用同一程序处理这些类似的问题。因此，将看似不同

13、的问题归纳转化为同一问题，可以统筹安排教学内容，在现有的教学条件下，能帮助我们提高教学效果，减少教学时间。这正是运筹学的精髓，对各种有限资源进行统筹安排，找出最优方案。所以本文与其说是教学体会，还不如说是运筹学方法的运用，用运筹学方法探讨运筹学的教学问题，为运筹学教学找到一种更好的方法。【参考文献】1 韩伯棠.管理运筹学.第 2 版.北京：高等教育出版社,2005.2 罗荣桂，原海英.运筹学教学改革与探索.理工高教研究，2005，24(3)：4950.3 黄宇林.从运筹学教学谈人才培养模式与实践.中国教育导刊，2005，(2)：7677.4 朱道立，徐庆，叶耀华.运筹学.北京：高等教育出版社,2006.5 董振宁，刘洪伟.管理类专业运筹学教学存在的问题及对策.中山大学学报论丛,2006，26(1)：235.6 张辉.运筹学教学方法探讨.中国石油大学胜利学院学报.2008 ，22(1)：8586.