第五章 运输问题(1).ppt

1、作业,3-7 4-1,管理运筹学,第五章 运输模型,问题：如何组织调运才能使总运费最少？,概述,运输模型是线性规划诸多模型中较早引起人们关注的一类特殊模型。 这类模型因为具有特殊的结构，所以可以采用比单纯形法更为简便的解法。 运输模型不仅适用于解决运输问题本身，还适用于其它相当多的应用问题（短缺资源分配、生产调度和转运问题等），因此受到了高度的关注并具有非常广泛的应用。,运输问题,在人们的实践中，经常出现各种运输活动： 这些运输活动一般都有若干个发货地点，简称产地； 有若干个收货地点，简称销地； 各产地有一定的可供货量，简称产量； 各销地有一定的需求量，简称销量； 如何组织调运，才能既满足各销

2、地的需求，又使总的运输费用（里程、时间）达到最低？这就是运输问题。,运输问题的类型,产销平衡的运输问题，简称平衡问题； 产销不平衡问题，简称不平衡问题： 产大于销的运输问题； 产小于销的运输问题。,例题,有A1A2A33座铁矿，每天要把生产的铁矿石运往B1B2B3B44个炼铁厂。各矿的产量、各厂的销量（百吨/天）以及各厂矿间的运价（百元/百吨），如下表所示。问如何组织调运才能使总运费最少？,运输模型的表达方式,文字表述（p118） 表格形式的一般运输模型（p119） 线性规划形式的一般运输模型，简称线性规划式运输模型（p119-120）,设xij为每天从Ai矿运往Bj厂的矿石数量，z为总运费，

3、则可得如下模型：,运输模型的特点,容易看出，运输模型具有两个特点： 它有m*n个变量，m+n个约束方程。 其系数矩阵具有特殊的结构。,表上作业法,产销平衡及运价表 表上作业法基本思想与单纯形法十分类似： 先找出一个初始基本可行解，称为初始方案； 然后按一定准则来检验这个方案是否最优； 如果不是，则按一定方法加以调整、改进，直到求出最优方案未知。 表上作业法3个基本步骤： 确定初始方案 进行最优解检验 调整、改进非最优方案,初始方案的确定,左上角法（西北角法或阶梯法） 最小元素法 最大差额法（又称Vogel概算法） Russell概算法,最小元素法,最小元素作业表中的最小运价 根据最小运价安排运

4、量 然后划去该运价所在的行或列 接下去继续这样做 直至求出初始方案为止。,1,1,1,3,1,3,1,3,1,3,0,1,3,0,1,3,0,2,1,3,0,2,2,1,3,0,2,2,1,3,0,2,2,2,1,3,0,2,2,2,最小元素法的几点说明,最小元素法3原则 每次只能划掉1行或1列 不留空格，如果是0也要填上 最后一个单元格一定要画圈 最小元素法确定的初始解满足的条件 最终画圆圈数字的个数为m+n-1 各行数字之和等于产量，各列数字之和等于销量 作业表中不存在以画圈数字问顶点的闭回路 最小元素法的优点和问题,32,最大差额法,计算每行、每列两个最小元素之差（取正值），将“行差”记

5、于表右侧，“列差”记于表下端； 在所有行差、列差中选一最大差额，若有几个同时最大，则可任选其一； 在最大差额所在行（列）中选一最小运价，若有几个同时最小，则可任选其一； 在步骤3中所确定最小运价格内，确定基变量数值并画圈，然后划去所在行或列，具体做法同最小元素法； 对剩余未划去的行列重复上述步骤，但当只剩下最后一行（列）时，不再计算行（列）差，直接按最小元素法分配运量，并划去相应的行或列。,1,1,1,1,1,2,1,2,1,2,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,2,1,2,1,2,2,1,2,1,2,2,1,2,1,2,2,2,1,2,1,2,2,2,关于最大差额法的说明,与最小元素法一样，最大差额法确定的方案也满足全部3个条件，因此也可以