【运筹学】-运输问题(一)(运输问题模型)

西北角法：在单位运价表中，每次从西北角位置选择元素，不考虑单位运价
最小元素法：在单位运价表中，每次选择运价最小的元素
伏格尔法：每次重新计算未被划去的行列的最小元素和次小元素的差额，选择最大差额对应列的最小元素对应的行列

例题

求解方法

步骤一：求初始基本可行解

西北角法求解

（1）确定西北角

（2）标识基变量：确定最大运输量（可接受量） b_j 和可提供量 a_i


（3）确定西北角

（4）标识基变量：确定最大运输量（可接受量） b_j 和可提供量 a_i


（5）确定西北角

（6）标识基变量：确定最大运输量（可接受量） b_j 和可提供量 a_i

（7）确定西北角

（8）确定运输表

（9）确定西北角

（10）确定运输表

（11）确定西北角

（12）确定运输表

到此，找到了6个基变量，而我们需要的基变量也正是m+n-1=3+4-1=6个，说明我们找到了初始可行解

初始方案：
根据运输方案表中的运输量分配，对照单位运价表中的运价，即可有：总运费=单位运价 * 运输量

运费 Z = 3*3+11*4+9*2+2*2+10*3+5*6 = 135

但是，由于这样的方法没有考虑单位运价，所以得到的解很可能不是最优解（总运费最小的解）

最小元素法求解

（1）确定基变量：寻找最小元素

（2）确定运输表

（3）确定最小元素
最小元素为2，对应产地A2到销地B3，接下来确定运输方案表中产地A2到销地B3的运输量

（4）确定运输表

（5）确定最小元素

（6）确定运输表

（7）确定最小元素

（8）确定运输表

（9）确定最小元素

（10）确定运输表

（11）确定最小元素

（12）确定运输表

到此，找到了6个基变量，而我们需要的基变量也正是m+n-1=3+4-1=6个，说明我们找到了初始可行解

初始方案：
根据运输方案表中的运输量分配，对照单位运价表中的运价，即可有：总运费=单位运价 * 运输量

运费 Z = 1*3+4*6+3*4+2*1+10*3+5*3 = 86

不过，最小元素法也存在问题：可能一开始寻找的元素是最小的，但是到后来找到的元素就很大，导致总体费用并不是最小

伏格尔法求解

（a1）计算未被划去的行列的最小元素和次小元素的差额

（a2）选择差额最大，确定基变量

（a3）确定运输表

（b1）计算未被划去的行列的最小元素和次小元素的差额

（b2）选择差额最大，确定基变量（b3）确定运输表

（c1）计算未被划去的行列的最小元素和次小元素的差额

（c2）选择差额最大，确定基变量（c3）确定运输表

（d1）计算未被划去的行列的最小元素和次小元素的差额

（d2）选择差额最大，确定基变量

（d3）确定运输表

（e1）计算未被划去的行列的最小元素和次小元素的差额

（e2）选择差额最大，确定基变量（e3）确定运输表

（f1）计算未被划去的行列的最小元素和次小元素的差额

（f2）选择差额最大，确定基变量（f3）确定运输表

到此，找到了6个基变量，而我们需要的基变量也正是m+n-1=3+4-1=6个，说明我们找到了初始可行解

初始方案：
根据运输方案表中的运输量分配，对照单位运价表中的运价，即可有：总运费=单位运价 * 运输量

运费 Z = 1*3+4*6+3*5+10*2+8*1+5*3 = 85

三种方法结果比较

步骤二：求检验数，并判断

闭回路法：每求一个检验数，就需要构建一个闭回路
位势法：对偶原理。λ_ij = c_ij - u_i - v_j

闭回路法

下图中运输方案表时有最小元素法得到的（伏格尔法得到的是最优的，不需要再优化？？）

求检验数

计算所有非基变量的检验数，得到最终表格如下：

判断检验数

对于最小化问题，（非基变量）检验数全部 ≥0 时，现行解为最优解。
上图结果中，检验数表中检验数不全 ≥0，所以还不是最优解

位势法

此时，c_ij、u_i、v_j都是已知的了，即可得出检验数 λ_ij


（）内为非基变量的检验数，同闭回路法得到的一致

步骤三：调整运量

采用闭回路法

步骤：
① 选择不满足条件的检验数中最小的检验数对应的非基变量作为换入变量
② 从该非基变量处为起始点，寻找一条闭回路，选择闭回路上运量最小的基变量作为换出变量
③ 调整运量。调整的大小为出基变量的大小

调整后，得到一组新的基本可行解。表格如下：

对这组新的基本可行解，再次计算检验数：

满足检验数全部≥0，对于最小化问题，现行解为最优解，即当前运输方案表中的运输方案为最优方案

运费 Z = 1*3+4*6+3*5+10*2+8*1+5*3 = 85

最小运费和伏格尔法计算结果相同（可见伏格尔法得出的方案为最优方案）