运输问题求解表上作业法

运输问题求解表上作业法

一、初始基本可行解的确定根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到m+n

–1个不构成闭回路的基变量。一般的方法步骤如下：

(1)在运输问题求解作业数据表中任选一个单元格xij，令

xij

=min{ai,bj

}2

即从Ai

向Bj

运最大量(使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足),填入xij

的相应位置；

(2)从ai

或bj

中分别减去xij

的值，即调整Ai

的拥有量及Bj

的需求量；3(3)若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；

(4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，转(4)。4上述计算过程可用流程图描述如下取未划去的单元格xij

,令xij

=min{ai,bj

}ai’=ai-xijbj’=bj-xijai’=0?划去第i行划去第j列是否

bj’=0否所有行列是否均被划去是找到初始基本可行解图3-2求运输问题的初始基本可行解过程5

按照上述方法所产生的一组变量的取值将满足下面条件：

(1)所得的变量均为非负，且变量总数恰好为m+n

–1个；

(2)所有的约束条件均得到满足；

(3)所得的变量不构成闭回路。6

因此，根据定理3.1及其推论，所得的解一定是运输问题的基本可行解。

在上面的方法中，xij

的选取方法并没有给予限制，若采取不同的规则来选取xij

，则得到不同的方法，较常用的方法有西北角法、最小元素法和Vogel法。71、西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。82、最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。93、Vogel法：从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤。

10

应用西北角法、最小元素法和Vogel法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。11表11213141516

最优性检验就是检查所得到的方案是不是最优方案。检查的方法----计算检验数由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。

二、基本可行解的最优性检验171、闭回路法以最小元素法给出的初始基本可行解方案为例，考察初始方案的一个非基变量x24。根据初始方案，产地A2的产品是不运往销地B4的。如果现在改变初始方案，把A2的产品运送1个单位给B4

，那么为了保持产销平衡，就必须使x14

或x34

减少1个单位；而如果x14

减少1个单位，第1行的运输量就必须增加1个单位，例如x13

增加1个单位，那么为了保持产销平衡，就必须使x23

减少1个单位。18

这个过程就是寻找一个以非基变量x24

为起始顶点的闭回路——{x24

，x14

，x13

，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。上述调整使总的运输费用发生的变化为8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。19

可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基变量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。表4-10中用虚线画出以非基变量x22

为起始顶点的闭回路。20表4-10以非基变量x22

为起始顶点的闭回路销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A321

可以计算出以非基变量x22

为起始顶点的闭回路调整使总的运输费用发生的变化为

9–2+3–10+5–4＝1

即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。22

这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。23

如果规定作为起始顶点的非基变量为第1个顶点，闭回路的其他顶点依次为第2个顶点、第3个顶点……，那么就有

ij=(闭回路上的奇数次顶点单位运费之和)-(闭回路上的偶数次顶点单位运费之和)

其中ij为非基变量的下角指标。24

按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图4-11所示。

销地产地B1B2B3B4产量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539销量365620(产销平衡)表4-11初始基本可行解及检验数25

显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。26

2.位势法位势：设对应基变量xij

的m+n-1个ij

，存在ui,vj

满足

ui+vj=cij

，i=1,2…,m;j=1,2…,n.

称这些ui,vj

为该基本可行解对应的位势。27

由于有m+n

个变量（ui,vj

），

m+n-1个方程（基变量个数），故有一个自由变量，位势不唯一。

利用位势求检验数：

ij=cij-ui-vj

i=1,…,m;j=1,…,n28前例，位势法求检验数：step1从任意基变量对应的cij

开始,任取

ui

或vj

，然后利用公式

cij=ui+vj

依次找出m+n

个ui,vj

从c14=10开始step2计算非基变量的检验数

ij=cij-ui-vj

；填入圆圈内29302.运输问题求解

—表上作业法

闭回路法和位势法得到的表是一样的。由于检验数不都非负，故这个基本可行解不是最优解。需要找新的基本可行解，使运费不高于当前的基本可行解。31

当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程。2.运输问题求解

—表上作业法

三、求新的基本可行解32

（1）选负检验数中最小者rk，那么xrk

为主元，作为进基变量（P55页图中x24）;

（2）以xrk

为起点找一条闭回路，除xrk

外其余顶点必须为基变量格（P55页图中的回路）;2.运输问题求解

—表上作业法

在运输问题的表上作业法中，换基的过程是如下进行：33

（3）为闭回路的每一个顶点标号，xrk

为1，沿一个方向（顺时针或逆时针）依次给各顶点标号；（4）求=Min{xijxij对应闭回路上的偶数标号格}=xpq那么确定xpq为出基变量，为调整量；2.运输问题求解

—表上作业法

34

（5）对闭回路的各奇标号顶点调整为：xij+，对各偶标号顶点调整为：xij-，特别

xpq-=0，xpq变为非基变量。重复(2)、(3)步，直到所有检验数均非负，得到最优解。2.运输问题求解

—表上作业法

35362.表上作业法

ij

≥0，得到最优解x13=5,x14=2,x21=3,x24=1,

x32=6,x34=3,其余xij=0;

最优值：

f*=3×5+10×2+1×3+8×1+4×6+5×3=8537

四、产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型

m

nMinf=cijxij

（4-1）

i=1j=1

n

s.t.xij

si

i=1,2,…,m

（4-2）

j=1

mxij

(=,)dj

j=1,2,…,n(4-3）

i=1xij0(i=1,2,…,m;j=1,2,…,n)（4-4）2.运输问题求解

—表上作业法

38

我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题。

1.产量大于销量的情况

m

n

考虑si>dj的运输问题，得到的数学模

i=1

j=1型为2.运输问题求解

—表上作业法

392.运输问题求解

—表上作业法

mn

Minf=cijxij

i=1j=1

n

s.t.xij

si

i=1,2,…,m

j=1

m

xij

=dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)40

只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1i=1,2,…,m即可，变为：

n

xij+xin+1=si

i=1,2,…mj=1然后，需设一个销地Bn+1,它的销量为：

mn

bn+1=si-dj

i=1j=1

2.运输问题求解

—表上作业法

41

这里，松弛变量xin+1

可以视为从产地Ai

运往销地B

n+1

的运输量，由于实际并不运送，它们的运费为cin+1=0i=1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。2.运输问题求解

—表上作业法

42

例4.2:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？2.运输问题求解

—表上作业法

43

解：增加一个虚设的销地运输费用为02.运输问题求解

—表上作业法

442.销量大于产量的情况

mn

考虑si<dj的运输问题，得到的数学模型为

i=1

j=12.运输问题求解

—表上作业法

mn

Minf=cijxij

i=1j=1

n

s.t.xij

=si

i=1,2,…,m

j=1