运筹学运输问题

回顾

运输问题的数学模型及其特点；运输问题解法—表上作业法；

（两个表格：产销平衡表，单位运价表）表上作业法中初始基可行解的确定方法：最小元素法；Vogel法（最大差额法）闭回路的建立与闭回路法求解检验数1、运输问题的数学模型2、最小元素法确定初始基可行解的步骤步骤一：确定第一个基变量

方法：（1）从单位运价表中，找出最小运价；（2）对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入产销平衡表中相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息<表示此产地不能再供应其他地方>；如果销量得到满足，则划去所在列的单位运价信息<表示此销售地不再有需求>。（注意产量和销量的变化）步骤二：确定第二个基变量

方法：在剩下的单位运价信息中，寻找最小值。按照上述方法进行操作。3、伏格尔方法（Vogel）确定初始基可行解

主旨：最大差额处，优先按最小运价进行调运。第一步：计算单位运价表中同行、同列的最小运费与次小运费之差，分别列在单位运价表的最右列和最下行（行差和列差）。

第二步：对行差和列差进行对比，找出最大差额。以与最大差额值同行（或同列）的最小运价为准，倾所在行的产量，最大限度地满足所在列的需求；一旦需求（或库存）被彻底满足（或库存调光），则随即划去该列（或行）的所有运价信息。（注意产量和销量的变化）第三步：重新计算同行同列的最小运费与次小运费之差，并对其它未被确定调拨值的行列，重复第二步的处理，直至构造出某初始调拨方案（初始解）。4、最优性检验的核心思想1、最优检验判断思路：确定初始基可行解后，调查非基变量取值变化对总运费的影响。2、实现方法：在确定的初始基可行解基础上，当非基变量有取值时，考虑总的运费的变化情况？（1）如果所有情况下总费用均增加，证明初始方案为最优；（2）一旦出现了总费用降低，代表给该非基变量安排运量可更优，说明最初方案需要优化。3、需要解决的问题：当非基变量取值时，为保证产销平衡表上的产销平衡，会引起已确定的基变量的连锁变化，导致相应的行或列基变量的波动。→需要靠闭回路法来确定基变量的变动情况。5、闭回路法的构造

（1）闭回路：调运方案中由一个空格（非基变量）和若干个有数字格（基变量）的水平和垂直连线所组成的回路。

（3）闭回路的构造方法：从选中的空格（非基变量）出发，沿水平或铅垂方向前进，确保只以途中的有数字格（基变量）为拐点实施转向，直到返回出发的空格（非基变量）。闭回路形式6、利用闭回路法计算非基变量检验数方法

1）参考产销平衡表，建立非基变量检验数表，用于填写各非基变量的检验数；

2）以确定的初始（或前一可行）调运方案表为准，寻找每个非基变量的闭回路；

3）在每个非基变量的闭回路上，计算当非基变量由“0”变为“+1”

时，基变量的取值变化规律（+1，还是-1）；

4）利用单位运价表中与闭回路相对应的运价信息，计算运费的变化情况（非基变量单位运价-∑处于奇数位置的基变量的单位运价+∑处于偶数位置的基变量的单位运价），即为非基变量检验数；

5）将非基变量检验数填入检验数表中相应位置。

销地产地B1B2B3B4产量A1非基变量1（3）非基变量2（11）4（3）3（10）7A23（1）非基变量3（9）1（2）非基变量4（8）4A3非基变量5

（7）6（4）非基变量6

（10）3（5）9销量3656利用闭回路法计算非基变量检验数方法A1B1非基变量：A1B1+1，A1B3-1，A2B3+1，A2B1-1.运费影响：3-3+2-1=1>0（即为此非基变量的检验数）。A2B2非基变量：A2B2+1，A2B3-1，A1B3+1，A1B4-1，A3B4+1，A3B2-1.运费影响：9-2+3-10+5-4=1>0。非基变量4：A2B4-1，A1B4+1,A1B3-1,A2B3+1。运费影响：8-10+3-2=-1<0。

销地产地B1B2B3B4A112A21-1A31012非基变量检验数表非基变量A2B4的检验数小于0，表明在A2B4处安排运量可以带来更低的运费→如何调整?7、问题

对于每一个非基变量，需要重复寻找闭回路，并计算“非基变量+1”时对总运费的影响→繁琐。

当出现检验数<0，证明原初始方案或改进方案还不是最优→如何进行基变量的调入调出？采用位势法一次全部计算出所有检验数给检验数<0的非基变量赋值，越大越好。但要考虑产销平衡问题。8、运输问题的校验方法2

—位势法利用行位势和列位势两类数据，将检验数与单位运价联系起来检验数方程λij=

cij

–

ui

–

vjui

，

vj

行位势列位势单位运价m个产地，n个销地时，则需要确定m个行位势，n个列位势一般令基变量的λ

ij=0，故确定ui与vj可借助基变量的位势方程组来确定ui

+

vj=

cij（基变量对应的单位运价）它总共含有m+n–1个方程，确定m+n个未知数，一般可以令某一个位势为0或1或者任何数，通过上述关系即可确定所有的位势。A、位势法求检验数的步骤第一步：根据最小元素法或Vogel法确定的初始运量表做一表格，将基变量（或运量）数据替换成与之对应的单位运价；（或对单位运价表进行修改，只保留与基变量对应的运价信息）第二步：在右侧增加一列，下侧增加一行，用于填写位势数据。右侧表示行位势ui（i=1，2...m），下侧表示列位势vj（j=1，2...n）；第三步：对于基变量对应的单位运价处，ui+vj=cij。随便确定任一个位势，即可求解全部行和列位势；第四步：在非基变量对应的空格处，计算检验数λij=cij-（ui+vj）。并将检验数填入检验数表中；第五步：判断检验数λij是否大于0，如是，则表示较优。如不是，则需要调整基变量。第六步：基变量的调整采用闭回路法进行。

销地产地B1B2B3B4A143A231A363

销地产地B1B2B3B4A1310A212A345初始调运表基变量的单位运价表

销地产地B1B2B3B4A1311310A21928A374105+步骤一：建立基变量的单位运价表单位运价表B、例子P88步骤二：确定行位势与列位势取值

销地产地B1B2B3B4A1310A212A345基变量的单位运价表uiu1u2u3vjv1v2v3v41）对于基变量处，cij=ui+vj；2）任意确定一个位势即可。0103-12-59步骤三：根据行位势与列位势取值计算非基变量检验数

销地产地B1B2B3B4A1310A212A345uivj0103-12-591）对于非基变量处，检验数为cij-（ui+vj

）；2）结合非基变量对应的单位运价，即可计算出所有非基变量的检验数。

销地产地B1B2B3B4A1311310A21928A3741051211012-1收点发点B1v1B2v2B3v3B4v4发量A1u1x119

18x131

109A2u2x2111x226

8

1810A3u3x3114

12

2x34166收量4975Σa=Σb行位势ui与列位势vj的确定方法初始调运表79211509251411例2

利用已确定好的ui与vj值，再结合cij值计算非基变量的检验数λij=cij

–(ui

+

vj)总共

(m–1)(

n–1)个收点发点B19B24B31B411发量A10x119

18x131

109A22x2111x226

8

1810A35x3114

12

2x34166收量4975Σa=Σb用行列位势ui与vj确定非基变量的检验数初始调运表792115

14-1

55

3-4确定非基变量检验数后，如果非基变量检验数<0，则其应该进入基变量组。1）如果出现多个非基变量检验数＜0，选择哪个作为换入基变量；2）如何确定换出基变量？收点发点B19B24B3-1B411发量A10x119

18x131

109A22x2111x226

8

1810A35x3114

12

2x34166收量4975Σa=Σb非基变量x33的检验数为-4

且最小构造闭回路792115

14-1

55

3-4奇点①③奇点②偶点偶点④基变量非基变量721721720如何调整基变量？初始基变量2初始基变量3初始基变量1检验数＜0的非基变量一般应在闭回路上进行调整。8、基变量的调整方法—

用闭回路法调整进基和出基变量（产销平衡时的运输问题）基变量的调整方法1）选择负检验数中绝对值最大的空格（非基变量），将其作为换入基变量；2）从该空格出发，构造一个闭回路，且此闭回路唯一；3）在闭回路上进行运量调整，使选定的空格处的运量尽可能的增加：将闭回路上最小基变量的取值调整给该空格，使该非基变量变为基变量（换入基变量）。原最小基变量变为非基变量，在新的调运方案中抹去（换出基变量）；4）闭回路上的其他基变量进行相应的调整，保证产销的平衡，得到新的调运方案；5）继续采用位势法进行检验，观察检验数是否全大于零。如出现负数，按照1）—4）的方法进行基变量的调整，直到所有检验数为正。

销地产地B1B2B3B4A143A231A363基变量的调整举例1

销地产地B1B2B3B4A1310A212A3451211012-1检验数初始调运方案

销地产地B1B2B3B4A143A231A363基变量的调整方法

寻找以检验数为负数的非基变量为起点的闭回路；对基变量进行调整，将非基变量变成基变量：将闭回路中，最小的基变量调运量调整给该非基变量，调整量为min｛1,3,4｝=1。从而使被调整的基变量变成非基变量；在闭回路上，对其他基变量进行调整，保证产销平衡。获得新的调运方案。1025

销地产地B1B2B3B4A143A231A363

销地产地B1B2B3B4A152A231A363初始调运方案（初始基可行解）调整后的调运方案（优化后的基可行解）运费：86运费：85

销地产地B1B2B3B4A152A231A363

销地产地B1B2B3B4A102A221A3912检验数表最优调运方案收点发点B19B24B31B411发量A10x119

18x131

109A22x2111x226

8

1810A35x3114

12

2x34166收量4975Σa=Σb偶点基变量x31的取值1

最小：θ=1偶点减θ，奇点加θ79211514-1

5

5

3-4奇点①③奇点②偶点偶点④06318、运输问题表上作业法的步骤9、产销不平衡的问题

核心方法：将产销不平衡转换为产销平衡的情形，然后由表上作业法进行求解。（1）对于“产>销”情形：产量盈余，可虚拟一个销售地（库存），让多余的产量均运抵此销售地，则其销售量=“产-销”，同时令该虚拟的销售地的单位运价为0；（虚拟的销地）（2）对于“销>产”，可虚拟一个产地，让其产量=“销-产”，同时令该虚拟的产地的单位运价为0.例1产大于销销地产地B1

B2

B3产量

A1

A2

A3

592

317628

151817销量181216Σ50≠Σ46解法：虚设一销地，令其销量为产销量之差。

b4=∑ai-∑bj=4

该列单位运价为0，即可化为产销平衡问题销地产地B1

B2

B3B4产量

A1

A2

A3

5920

31706280

151817销量1812164Σ50=Σ50例2产小于销

销产B1B2B3aiA141210A234312bj81052223解法：虚设一销地，令其销量为产销量之差

b4=∑bj

-∑ai=1

令该列运价为0，如此可化为产销平衡问题。

销产B1B2B3aiA141210A234312A30001bj8105232310、运输问题的应用短缺资源的分配问题

需求产地ⅠⅡⅢⅣ产量A1613221750B1413191560C192023－50最低需求3070010最高507030不限

需求产地ⅠⅡⅢⅣ产量A1613221750B1413191560C192023－50最低需求3070010最高需求507030不限必须满足最高和最低之间差额，不一定全额满足。问题分析1、产销量问题。产量160，最低需求110，最高需求无限，但根据现有情况，最高总需求为210（因为Ⅳ销地最多可获得60），属于产销不平衡问题；2、如何转换成产销平衡问题？增加假想产地。3、将需求量化成两部分，一部分满足最低需求，一部分满足差额。