交通运筹学教学课件作者张文会第4章节运输与指派问题课件

《交通运筹学教学课件作者张文会第4章节运输与指派问题课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章运输与指派问题1主要内容第一节运输问题的数学模型第二节运输单纯形法第三节指派问题2第一节运输问题的数学模型【例5.1】现从两个产地A1，A2将物品运往B1，B2，B3三个地区。各产地的产量、各需求地（销地）的需求量及产地到需求地的运价如表5-1所示，问如何安排运输计划使总的运输费用最小。3解设为个产地运往第个需求地的运量，这样得到运输问题的数学模型为：（1）目标函数为总的运费最小，即：（2）各产地的供给量与运出量应平衡，即：（3）各需求地的供给量与需求量应平衡，即：（4）运量应大于或等于零，即：4使总运输费用最小的运输问题的数学模型为：5【定理5.1

2、】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。【定理5.2】若变量组包含有闭回路则变量对应的列向量线性相关。6第二节运输单纯形法5.2.1确定初始基本可行解最小元素法，西北角法，元素差额法5.2.2求检验数闭合回路法、位势法5.2.3调整运量闭合回路法7最大值问题：（1）所有非基变量的检验数时最优。在求初始运输方案时可采用最大元素法或西北角法。（2）将极大化问题转化为极小化问题产销不平衡问题：在实际问题中常常会遇到总产量和总销量不相等的情况，即产销不平衡，这时就需要把产销不平衡问题化成产销平衡问题。8一、最小元素法这种方法的基本思想是

3、就近优先供应，即对单位运价表中最小运价对应的变量优先赋值，然后对次小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基本可行解。9【例】某建筑公司拟从三个管桩厂购买管桩，供4个工地使用。已知各管桩厂可供应管桩的数量（百根），各工地需要的数量（百根）及从各管桩厂到各工地的运输单价（千元/百根）如表所示，试用最小元素法求解该运输问题。、、10二、元素差额法（Vogel近似法）最小元素法的缺点是：可能开始时节省一处的费用，但随后在其他处要多花几倍的运费。元素差额法对最小元素法进行了改进。如果不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额

4、越大，说明不能按最小运费调运时，运费增加就越多，因此对差额最大处就应当采用最小运费调运。11三、左上角法（西北角法）左上角法的基本思想是优先产销平衡表的左上角（西北角）的供应关系。即对单位运价表中左上角处的运价对应的变量优先赋值当行或列分配完毕后，再对表中余下部分的左上角赋值，依次下去，直到右下角的元素分配完毕。【例】试用西北角法求解上题的初始基本可行解。12最优性判别判断初始运输方案是否为最优方案，仍然是用检验数来判别。因运输问题的目标函数都是求最小值，所以当所有检验数时，运输方案最优，否则，再改进当前的运输方案。下面介绍求检验数的两种方法：闭回路法和位

5、势法。13一、闭回路法这种方法求非基变量检验数的步骤为：（1）在基本可行解矩阵中，以该非基变量为起点，以基变量为其他顶点，找一条闭回路；（2）由起点开始，分别在顶点上交替标上代数符号；（3）用代数符号乘以相应的运价，代数和即为检验数。【例】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价，右边的元素为产量，下方的元素为销量。14二、位势法闭回路法计算各个空格检验数时需要找出对应的闭回路，这使得在运输问题比较大时计算量很大。下面介绍较为简便的方法—位势法。【例】用位势法求上题给出的初始基本可行解的检验数。15调整运量当某个检验数小于零时，需要

6、调整运量从而改进运输方案，改进方法为闭回路法，其步骤为：（1）确定进基变量。（2）确定出基变量。（3）调整运量，在进基变量的闭回路中将标有负号的最小运量作为调整运量，正号格加上这个运量负号格减去这个运量。16【例】求下列运输问题的最小运输费用的最优解17最大值问题当运输问题的目标函数求最大值时，有两种求解方法。（1）所有非基变量的检验数时最优。在求初始运输方案时可采用最大元素法或西北角法。（2）将极大化问题转化为极小化问题。18不平衡运输问题在实际问题中常常会遇到总产量和总销量不相等的情况，即产销不平衡，这时就需要把产销不平衡问题化成产销平衡问题。（1）产

7、大于销时（2）销大于产时19【例】设有和两个化肥厂供应三个地区。假定等量的化肥在这些地区使用效果相同。各地化肥年产量，各地区的需求量及从化肥厂到各地区运送单位化肥的运价如表所示。试求出总的运费最节省的化肥调拨方案。20指派问题在生活中经常遇到这样的问题，某单位需要完成n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，完成每项任务的效率也就不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高的问题，这类问题成为指派问题或分派问题（AssignmentProblem）。在工程项目管理、资源利用和劳动力分配等实际工作中，指派问题比较常见

8、。例如在工程运输中n个工程公司对n个工程项目的投标问题，公共交通客