运筹学运输问题的教学方法探讨论文
【摘要】 用运筹学的思想探讨运筹学课程的教学方法。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题，从而可以统筹安排这些教学内容，为提高教学效果，减少教学时间找出更优的教学方法。
【关键词】 运输问题; 转运问题; 运筹学; 教学方法
运筹学是一门应用科学，它运用数学方法对经济和管理系统中的各种有限资源进行统筹安排，为决策者提供最优参考方案，以实现有效的科学管理。运筹学是管理类专业的专业基础课，对管理类人才培养有着重要的意义。该课程的特点是将数学知识、数学建模、经济管理与计算机应用四者融为一体，通过各类实际问题的案例，培养学生分析、解决实际问题的能力。该课程本身有一定的难度，作为教师，应努力探索教育教学规律，认真把握课程的特点，以获得良好的教学效果。如何在现有的有限资源条件下(如学时、生源、师资)，将这门课上好，不也正是运筹学研究的内容吗?
运筹学涉及内容较多，线性规划是最主要的一个分支，其理论最完善、方法最成熟，应用也最广泛，涉及的很多问题都是经典的问题，如运输问题、指派问题、最短路问题，最小费用流问题等。自己在运筹学教学过程中发现，这些问题有相同的共性，可以归结为同一个问题，从而可以统筹安排教学内容，为运筹学课程提高教学效果，减少教学时间找出更优的教学方法。
1 运输问题和转运问题
1.1 运输问题
运输问题一般指货物可直接从产地运往销地。下面以运费问题为例进行说明。
记si 为产地Ai(i=1,2,…,n) 的产量，dj 为销地Bj(j=1,2,…,m) 的销量，cij 为把货物从产地Ai 运往销地Bj 的单位运价。设xij 为从产地Ai 运到销地Bj 的货物量，则运费最少的产销平衡问题的线性规划模型为[1,4]：
目标函数 min z=秐i=1 秏j=1cijxij
约束条件 秏j=1xij=si ，(i=1,2,…n) (1)
秐i=1xij=dj ，(j=1,2,…m) (2)
xij≥0 ,对所有的i 和j 。
对于不同的实际问题，有时还需加一些约束条件。例如，当货物量的单位为“件”、“箱”时，还需加上xij 为整数的约束条件。
对于产销不平衡问题一般用两种方法解决：
第一种方法是建立一个假想(虚拟)的产地或销地，根据实际问题，将从产地运往销地的单位运价设为0或一个很大的数，再转化为产销平衡问题，这一方法比较复杂一些。另一种更简单的方法是，对产大于销问题，将(1)式中的等式变为≤ ，对销大于产问题，将(2)式中的等式变为≤ ，这种方法更直观，易于学生理解和掌握。
1.2 转运问题
转运问题是运输问题的一个扩充，当产地的货物不能直接运往销地时，需通过中转站。
记产地为发点，销地为收点，中转站为中转点，cij 为把货物从点i 运往点j 的单位运价。设xij 为从点 i运往点j 的货物量，则运费最少的产销平衡转运问题的线性规划模型为[1,4] ：
目标函数 min z=端有的弧cijxij
约束条件 ：对发点i 有 端有的流出量xij-端有的流入量xij=si (3)
对中转点有 端有的流出量xij-端有的流入量xij=0 (4)
对收点j 有 端有的.流出量xij-端有的流入量xij=di (5)
xij≥0 ，对所有的i 和j 。
对于产销不平衡问题，可根据实际问题将(3)或(5)式中的等号改为不等号。
2 可转化为运输问题的问题
2.1 指派问题
一般的指派问题为[1,4]：有n 项任务，恰好有n 个人可分别承担这些任务，由于各人特长不同，完成各项任务的效率等情况(如时间)也不同，现假设必须指派每个人去完成一项任务，怎样把n 项任务指派给n 个人，使完成n 项任务的总效率最高。
以完成任务的效率是时间为例，说明指派问题可转化为运输问题。
将每个人看成产地，产量均为1，si=1 ，即每个人生产出一个劳动力;将每项工作看成销地，销量为1，dj=1 ，即每项工作需要一个劳动力来完成;将每个人完成各项任务的时间看成单位运价cij ;设xij=1 为指派第 i个人完成第j 项工作，设xij=0 为不指派第i 个人完成第j 项工作，则上述指派问题可转化为产销平衡的运输问题。
当任务项数多于人数时，可看成是销大于产的情况，当人数多于任务项数时，可看成是产大于销的情况，由此可转化为产销不平衡的运输问题。
2.2 特殊的背包问题
一般的背包问为[1]：设背包携带物品的重量限制为W ，N 种物品中第i 种物品的重量为wi ，价值为ci ，总数量为ni ，如何决定这N 种物品中的每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。
考虑wi 都相等的特殊情况，即每种物品的重量都相等，不妨设为1。将第i 种物品看成产地Ai ，产量为ni ;将背包看成唯一的一个销地，销量为W ，将第i 种物品的价值负数看成单位运价-ci ，设xi 为携带的第i 种物品的数量，则这种背包问题可转化为销大于产的的运输问题。
3 可转化为转运问题的问题
3.1 最短路问题
一般的最短路问题为[1]：对一个赋权的有向图，找到一条从一个指定的起点到另一个指定的终点的路，使这条路上所有弧的权数的总和最小。
将起点看成唯一的一个产地(发点)，产量为1;将终点看成唯一的一个销地(收点)，销量为1;将其余点看成中转点，任两点的权看成单位运价，并设xij==1 为最短路经过弧(i ，j )， xij=0为最短路不经过弧(i ，j )，则最短路问题可转化为产销平衡的转运问题。
在实际应用中遇到更多的是无向图的最短路问题。这时需将无向图添加方向变为有向图。由于最短路不可能由起点出发再回到起点，到了终点也不会再转向其它点，而其它情况的各种可能性都有，所以可用如下方法为无向图添加方向：与起点相连的弧，方向由起点指向另一点;与终点相连的弧，方向由另一点指向终点;与起点、终点无关的弧，给出双向的方向(图1)。弧(i ，j )和弧(i ，j )权相同。图1 无向图(左)添加方向成为有向图(右)，其中1为起点，5为终点
3.2 最大流问题
一般的最大流问题为[1] ：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。
记发点为v1 ，收点为vn ，fij 为弧(vi,vj) 上的容量，M=秗k=2f1k ，各条弧上的单位运价为c1k=-1 ，k=2,3,…,r ，其余cij=0 。设xij 为弧(vi,vj) 上的流量，则上述最大流问题可转化为只有一个产地(发点)，产量为M，只有一个销点(收点)，销量为秗k=2x1k 的产大于销的转运问题：
目标函数 min z=端有的弧cijxij=-秗k=2x1k 约束条件 ：对发点1 有 秗k=2x1k≤M (6)
对中转点有 端有的流出量xij-端有的流入量xij=0
对收点n 有 端有的流入量xin=秗k=2x1k
0≤xij≤fij ，对所有的 i和j 。
其实(6)式是多余的，由 0≤xij≤fij可以得到，这里仅为了说明该问题可转化为转运问题。
3.3 最小费用流问题
一般的最小费用流问题为[4]：给了一个带收发点的网络，对每一条弧除给出了容量外，还给出了这条弧的单位流量的费用，要求一个可行流，并使得总运送费最小。
若可行流是最大流时，则为最小费用最大流问题。
最小费用最大流问题分两步解，第一步，先求出最大流F;第二步，在最大流F的所有解中，找出一个最小费用的解。
关于第一步求最大流问题，已在前面讨论过。第二步求最小费用问题，将发点看成唯一的产地，产量为F(或可行流)，将收点看成唯一的销地，销量为F(或可行流)，每条弧的单位流量的费用看成单位运价，由此可转化为产销平衡的转运问题。
4 讨论
在教学中，将看似不同的问题归纳转化为同一问题，非常重要。首先，这涉及到教学内容的结构问题，原来看似不同的问题可能在教材的不同章节，转化为同一问题后可并入同一章节。第二，对提高教学效果有一定的帮助。对老师而言，可减少教学时间，原先要花较多时间讲解不同的问题，现在只需讲解一个问题，然后作为同一问题举一反三，不仅可将原问题讲授得更清楚，也解决了新问题。对学生而言，原先要记多种问题的解法，现在只需记一种解法就可以了，减轻了学习负担。第三，更重要的是，启发学生对问题有更深入的理解，抓住事物的本质，而不是停留在表面，这对培养学生抽象思维、综合归纳能力是大有裨益的。当然，要做到这一点，对老师的要求显然更高，必须要花更多的时间和精力研究问题，吃透教材，理解精髓，融会贯通，非一般的应付教学所能解决的。最后，在用计算机求解方面，可用同一程序处理这些类似的问题。
因此，将看似不同的问题归纳转化为同一问题，可以统筹安排教学内容，在现有的教学条件下，能帮助我们提高教学效果，减少教学时间。这正是运筹学的精髓，对各种有限资源进行统筹安排，找出最优方案。所以本文与其说是教学体会，还不如说是运筹学方法的运用，用运筹学方法探讨运筹学的教学问题，为运筹学教学找到一种更好的方法。
【参考文献】
1 韩伯棠.管理运筹学.第2版.北京：高等教育出版社,2005.
2 罗荣桂，原海英.运筹学教学改革与探索.理工高教研究，2005，24(3)：49～50.
3 黄宇林.从运筹学教学谈人才培养模式与实践.中国教育导刊，2005，(2)：76～77.
4 朱道立，徐庆，叶耀华.运筹学.北京：高等教育出版社,2006.
5 董振宁，刘洪伟.管理类专业运筹学教学存在的问题及对策.中山大学学报论丛,2006，26(1)：2～35.
6 张辉.运筹学教学方法探讨.中国石油大学胜利学院学报.2008 ，22(1)：85～86.
【运筹学运输问题的教学方法探讨论文】相关文章：