用表上作业法求解运输问题

运输问题表上作业法改进思路研究论述运输问题的表上作业法是求解运输问题的重要方法，实质是一种单纯形法，其中，运输问题的基本性质对运输问题表上作业法的改进有着重要的意义。

但是，在实际的表上作业法运作中对运输问题的性质分析不够，经过有关人员的分析，提出了最小元素法给出的初始方案是解决运输问题的可行性操作，同时，也解决了运输问题的退化情况。

文章通过对运输问题表作业法现状的分析，对经典表上作业法的阐释，结合运输问题的性质，对运输问题表上作业法求解初始解方法以及调运检验方案的调整两个方面的改进思路进行研究。

标签：运输问题；表上作业法；改进思路随着我国经济的发展，物流业也得到了快速的发展，在我国经济活动中发挥了重要的作用。

物流业的发展对交通运输问题提出了更高的要求，在此情况下，运输问题中引用了一门现代学科中的运筹学。

运筹学是指利用数学的手段对所需要处理的问题进行规划和分析，最终实现对问题的最优化解决。

其中，应用到运输问题中的是运筹学中线性规划方面的表上作业法。

表上作业法是在一些线性规划问题采用图上作业难以直观规划的情况下，通过各元素的排列组成表格，并将表格作为一种初始方案，在此基础上利用闭合回路法、位势法获取检验数来对方案检验，最终获得最优化的解决办法。

1 运输问题性质、现状及表上作业法现状1.1 运输问题的性质运输问题中的运输表中行列、数列会随着相异变量的延伸而进行改变，变量序列之间形成了一种闭合路。

运输问题的系数矩阵及其增广矩阵的秩均为m+n-1。

其中，运输问题中的变量列向的充要条件不包括闭合路。

在对运输问题求解时，主要采用最小元素法的原理，通过对初始方案的确定来实现可行解。

1.2 运输问题研究现状随着交通运输事业的发展，物资配送问题的求解引起了有关人员的关注。

运输问题是一种特殊的线性规划形式，在上个世纪四十年代的时候，苏联数学家提出了一种线性的运输规划方法，是一种基于线性约束的基础上关于目标函数极大、极小值的数学理论，具有非常重要的现实意义。

第3节 运输问题的求解方法 ——表上作业法
产销平衡表与单位运价表
表上作业法
产销不平衡的运输问题的求解方法
一、产销平衡表与单位运价表
运输问题还可用产销平衡表与单位运价表 进行描述。 假设某种物资有m个生产地点Ai（i=1， 2，…，m），其产量（供应量）分别为ai（i=1， 2，…，m），有n个销地Bj（j=1，2，…，n）， 其销量（需求量）分别为bj（j=1，2，…，n）。 从Ai到Bj运输单位物资的运价（单价）为Cij。将 这些数据汇总可以得到产销平衡表和单位运价 表5.3.1。
P ,P ,P ,P ,P B ik lk ls us uj
而这些向量构成了闭回路见图
位势法
一种较为简便的求检验数的方法。
设 u1, , u2 ,, um ; v1 , v2 ,, vn 是对应运输问题的m+n 个约束条件的对偶变量。B是含有一个人工变量Xa的初始 基矩阵。 Xa在目标函数中的系数Ca ，由线性规划的对 偶理论可知
（1）确定初始调运方案，即找出初始 基可行解,在产销平衡表上给出 m+n-1个数 字格。
（2）求非基变量的检验数，即在表上计算 空格的检验数，判别是否达到最优解：是否存 在负的检验数？如果存在负的检验数，则初始 调运方案不是最优方案；如果所有检验数都非 负，则初始调运方案已经是最优方案了。如果 已经得到最优调运方案，则停止计算，否则转 入下一步。
考虑多余的物资在哪一个产地就地储存的问题。 xi ,n1 设 是产地Ai的储存量，于是有
n n 1 xij xi,n1 xij ai (i 1,2,, m) j 1 m j 1 xij b j ( j 1,2, n) m i 1 m n x i ,n 1 ai b j bn 1 i 1 j 1 i 1

把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季 度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度生 产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位 成本加上储存、维护等费用。可构造下列产销平衡问题：
运输问题的应用
Page 19
解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那 么应满足：
运输问题的应用
Page 17
3. 生产与储存问题
例3.5 某厂按合同规定须于当年每个季度末分别提供10、15、25、 20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台 柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台 每积压一个季度需储存、维护等费用0.15万元。试求在完成合同 的情况下，使该厂全年生产总费用为最小的决策方案。
3
11
3 5 10
1
9
2
8
7
4
10
5
表上作业法
B1 B2 B3 B4
A1
5
A2
×
A3
×
2
5
1
3
Page 9
7 1 1
表上作业法
B1 B2 B3 B4
A1
×
5
A2
3
×
A3
×
×
2
5
3
Page 10
7 7 1
表上作业法
Page 11
B1 B2 B3 B4
A1
×
×
5
2
1
A2
3
×
×
1
1
A3
×
6
×
3
1
5

第三章 运输问题主要内容 运输问题的模型、算法 讲授重点 运输问题的模型、算法 讲授方式讲授式、启发式第一节 运输问题及其数学模型一、运输问题的数学模型设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有n 个销地B l ,B 2,…,B n ,各销地的销量分别为b l ,b 2,…,b n 。

假定从产地A i (i ＝1,2,…,m)向销地B j (j ＝1,2,…,n)运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小?这是由多个产地供应多个销地的单品种物品运输问题。

为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。

设ij表示从A i 运往B j 的物品数量，ij表示从A i 运往B j 的单位物品的运价。

则对于平衡运输问题（∑∑===nj jm i i ba 11），其数学模型的一般形式可表示为：∑∑===n j mi ijij x c s 11min()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧==≥====∑∑==n j m i x n j b x m i a x ij j m i ij inj ij ,2,1;,2,10,,2,1,,2,111 (3.1)二、运输问题数学模型的特点对于平衡运输问题(∑∑===nj jm i iba 11)，可以证明其有如下两个特点： (1)矩阵A 的秩R(A)＝m+n-1。

(2)问题必有最优解，而且当ji b a ,皆为整数时，其最优解必为整数最优解。

第二节 表上作业法求解运输问题一、给出运输问题的初始可行解（初始调运方案） 1、最小元素法 解题步骤：⑴在运价表中找到最小运价c 1k ； ⑵将的A L 产品给B k ；①若a L>b k，则将a L改写为a L-b k，划掉b k，同时将运价表中K列的运价划掉；②若a L<b k，则将a L改写为b k-a L，划掉a L，同时将运价表中L列的运价划掉。