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