运输问题

运输问题是一种特殊的线性规划问题，可以解决如类似把商品从一些产地运往另一些销售地使总运输成本最低的问题。由于其场景特殊性，找到比单纯型法更搞笑简便的算法，这便是研究运输问题的目的所在。下面是运输问题的思维导图

一、运输问题的数学模型

对于单一商品的调度运输问题，一般来说有以下定义：

商品有m个产地，A₁，A₂， ...， A_m，每个产地有a₁，a₂， ...， a_m的产量；有n个销售地B₁，B₂， ...， B_m，每个销售地有b₁，b₂， ...， b_m的销量；c_ij表示从A_i运往B_j的运输成本。

运输问题可以抽象成三个类型：

（1）产销平衡 ∑_i a_i = ∑_j b_j

（2）供过于求 ∑_i a_i > ∑_j b_j

（3）供小于求 ∑_i a_i < ∑_j b_j

以产销平衡为例，其模型为：

可以从该模型看出，模型包含m*n个决策变量，m+n个等式约束，m*n个非负约束。

写成（m+n）* （m*n）的系数矩阵

其系数向量的结构是

 即第i个和第（m+j）个分量是1，其余是0

运输问题的有如下特点：

1、所有结构约束条件都是等式约束

2、各地产量和等于各地销量和

3、解变量对应的约束方程组的系数列向量线性无关

4、解中的非零变量的个数不大于n+m-1个，因为m+n-1个约束条件是线性独立的

二、求解运输问题

表上作业法

（1）找到初始解（2）做最优判断（3）在运输表上改进得到新解（4）在判别、再改进

关于第一步，找到初始解，一般由三种方法可以做

西北角法

遵循“优先安排运价表上编号最小的产地和销地之间（即运价表的西北角位置）的运输业务”的规则

最小元素法

最小元素法的基本思想是就近供应，为了减少运费，优先考虑运价表中单位运价最小（或运距最短）的供销业务

沃格尔法

沃格尔法的基本思想是在运价表中分别计算出各行各列的最小单位运价和次小单位运价之差，并称这两个单位运价之差为该销售地或供应地的罚数，然后按照最小单位运价对罚数最大处安排运输。因为若罚数的值很大，说明不按最小运价组织运输就会造成很大的运费损失。