运输问题的数学模型.ppt

运输问题的数学模型§3.1运输问题及其数学模型§3.2表上作业法§3.3产销不平衡的运输问题§3.4应用举例1．掌握运输问题的数学模型、系数矩阵特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握回路、位势法求解过程和表上作业法求解运输问题过程一、运输问题及其数学模型在经济建设中，经常碰到物资调拨中的运输问题。例如煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：

二、表上作业法例1给定下列运输问题.（一）确定初始基可行解运输问题的初始方案的确定主要有三种方法：该问题的运价表：.练习题２.最小元素法最小元素法的基本思想是——就近供应；即从运价表中最小的运价开始确定供销关系.若有几个最小运价，则任取其一。练习题３.伏格尔法一产地的产品如若不能按最小运费就近供应，就考虑按次小运费供应，这里存在一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，应当采用最小运费调运。练习题（二）判断当前方案是否为最优用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。（1）闭回路法在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。小结运输问题模型是一种特殊的线性规划，由于其约束条件特别简单，因此它有更简单的解法——表上作业法。本章教学重点内容有：1.运输问题的数学模型及其特点；2.确定初始调运方案的最小元素法；3.检验数的意义、计算方法和格式。表上作业法类似于单纯形法，表上作业法的步骤：第一步，确定一个初始可行调运方案。常用的方法有最小元素法、西北角法等。第二步，判别当前可行方案是否最优。常用方法有二种，一种是闭回路法，另一种称为位势法。通过这二种方法，计算出检验数，从而判别方案是否最优。第三步，方案调整。即从当前方案出发去寻找另一个更好的调运方案。5/2/052724104398126/4483/0bj7A3A29A1aiB4B3B2B1最小元素法计算33004/07/3200寻找运价中最小的：令销地B3的销量4全由产地A3供给，所以x13=0。将x33＝4填到调运方案表中第3行第3列上。画去运输数据表中第3列，A3的产量剩余为7-4=3.得到新的产销平衡运输表405/2/052724104398126/44/083/0bj7/3A3A29A1aiB4B3B2B1最小元素法计算43008/57/3/020040寻找运价中最小的：令产地A3的产量3全供给销地B2，所以x34=0，将x32=3填到调运方案表中第3行第2列上。画去运输数据表中第3行，B2的销量剩余为8-3=5.得到新的产销平衡运输表.305/2/052724104398126/44/083/0bj7/3A3A29A1aiB4B3B2B1最小元素法计算53008/57/3/02004030现在只有一个产地两个销地，故令x12=5,x14=4为基变量，将其分别填到调运方案表中第1行第2列与第1行第4列上。得到产销平衡运输问题的一个初始方案.45552724104398126483bj7A3A29A1aiB4B3B2B13243得到产销平衡运输问题的一个初始方案.45评注此调运方案的运费是3×1+5×9+3×4+4×2+2×2+4×7=100比用西北角法初始方案好些。1、某公司生产某种产品有三个产地A1、A2、A3，要把产品运送到四个销售点B1、B2、B3、B4去销售。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。问应如何调运，可使得