产销不平衡的运输问题

盐城师范学院运筹学期末论文题 目: 产销不平衡的运输问题 姓 名: 许凯波 二级学院: 数学科学学院 专 业: 数学与应用数学 班 级: 114 班 学 号: 11211434 成绩评定: 产销不平衡的运输问题在实际生产生活中，会经常碰到把某种东西从某地运到另一个地方，比如：把一批衣服从上海运到盐城，采用哪种运输方式更节约成本？这就是一个最简单运输问题。解决运输问题，找到其最优方案有很大使用价值或者说可以带来很大的经济利益。下面主要看一类运输问题：产销不平衡的运输问题。所谓产销不平衡的运输问题是指：某种物品有m个地点生产，n个地点需要，物品从不同的产地运往不同的需要地运费也不相同，其次该物品的总产量与总的需要量也不正好相等。如何分配才能既满足需要又使成本最少，即最优分配方案。解决该问题主要有以下几步：1. 初始方案的给定 最小元素法：最小元素法的基本思想是就近供应，即从单位运价表中最小的运价处开始确定供需关系，依次类推，一直到给出全部方案为止。下面将以具体的例子来进一步说明此方法。2.最优性检验与方案的调整位势法:首先将最小元素法确定的初始调运方案表有数字格的地方换上单位运价表中对应格的运价；然后在得到的新表格的右面和下面增加一行和一列，并填上一些数字，使表中各个数刚好等于他所在行和列的这些新填数字之和。通常用（=1，2，）和（=1,2，）来代表这些新填的数字。和分别称为第行和第列的位势。任一空格的检验数为： =如果表中出现有负的检验数时，对方案进行调整，用闭合回路法，下面将以具体例子作详细说明。例.已知运输问题的产销地的供需量与单位运价表如下图，求出最优解。 表1产地销地 B B B B 产量 A 8 4 1 2 7 A 6 9 4 7 25 A 5 3 4 3 26 销量 10 10 20 15解产地总产量为58，销地总销量为55,这是一个产大于销的运输问题。转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见表2，表3表2 产销平衡表产地销地 B B B B 库存 产量 A 7 A 25 A 26 销量 10 10 20 15 3 表3 单位运价表产地销地 B B B B 库存 A 8 4 1 2 0 A 6 9 4 7 0 A 5 3 4 3 0用最小元素法给出初始方案：在表3单位运价表中找出最小运价为1（库存列不算），即A首先供应B的需要。A生产的尽量满足B的需求，而A的产量为7，小于B的销量20，把A产的全给B，不够的由其他产地来供应，这样A就没有产品了，在产销平衡表中（A，B）的交叉格I填数字7得下表4，在单位运价表中划去A所在行的运价的下表5 表 4产地销地 B B B B 库存 产量 A 7 7 A 25 A 26 销量 10 10 20 15 3 表 5产地销地 B B B B 库存 A 8 4 1 2 A 6 9 4 7 A 5 3 4 3 再在表5中最小运价为3（有两个3，任选一个，假定选B列对应的3），让A生产的首先供应B，B需要10，而A生产了26，出去供应给B的还有剩余，可以供给其他地方。这样在表4中（A，B）的交叉格填10，得表6；再在表5中划去B所在列的运价得表7 表 6产地销地 B B B B 库存 产量 A 7 7 A 25 A 10 26 销量 10 10 20 15 3 表 7产地销地 B B B B 库存 A 8 4 1 2 A 6 9 4 7 A 5 3 4 3 这样一步一步进行下去，直到单位运价表上所有元素都划去为止，这时在产销平衡表上就得到一个调运方案，见表8 表 8产地销地 B B B B 库存 产量 A 7 7 A 9 13 3 25 A 1 10 15 26 销量 10 10 20 15 3 用位势法进行最优性检验产地销地 B B B B u A 1 u A 6 4 u A 5 3 3 u +u=6 , 令=1,解得=-1 +u=5 =-1 +u=3 =-1 +u=4 u=2 +u=1 u=5 +u=3 u=4 检验表产地销地 B B B B u A 3 1 1 1 u A 6 4 4 4 u A