运筹学 运输问题

运筹学运输问题第一页，共三十七页，2022年，8月28日

从m个发点向n个收点发送某种货物.发点的发量为，收点的收量为。由运往单位货物的运费为，问如何调配，才能使运费最省？问题的提出第二页，共三十七页，2022年，8月28日表1产销平衡表

上述数据可以汇总于表格中,如下:表2单位运价表

第三页，共三十七页，2022年，8月28日运输问题的数学模型

设xij代表为从第i个产地调运给第j个销地的物资的数量.在产销平衡的条件下，即使总的运费支出最小，可以表为以下数学形式：第四页，共三十七页，2022年，8月28日m行n行

运输问题的数学模型,包含m×n个变量,m+n个约束条件,系数矩阵如下:第五页，共三十七页，2022年，8月28日2.5.2表上作业法第六页，共三十七页，2022年，8月28日表上作业法的基本思路：确定初始调运方案最优性检验改进方案

第七页，共三十七页，2022年，8月28日1确定初始调运方案运输问题确定初始基可行解，就是求出运输问题的初始调运方案.确定初始基可行解的方法有最小元素法和伏格尔法。第八页，共三十七页，2022年，8月28日

【例2-1】某公司经销甲产品,下设3个加工厂A1、A2、A3，产品分别运往销售点B1、B2、B3、B4，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示：（运输问题供需平衡表和运价表如下），求总运费最少的调运方案。

销地产地B1B2B3B4发量（T）A13113107A219284A3741059收量（T）3656表3-3第九页，共三十七页，2022年，8月28日1.最小元素法314

633Z=4×3+3×10+3×1+1×2+6×4+3×5=86该方案总运费：（思想：就近供应）不能同时划去行和列保证填有运量的格子为m+n-1表3-4第十页，共三十七页，2022年，8月28日2.Vogel法①2513①

011表3-6[]6②213②

0123③212③

01

[][]3④12④

76

[]521表3-5Z=85第十一页，共三十七页，2022年，8月28日1若有两个以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填数字，不能划掉。3计算行差，列差时，已经划去的列或者行不再考虑。4用伏格尔法所求的初始解是基可行解，所以基变量个数为m+n-1个。第十二页，共三十七页，2022年，8月28日

销产B1B2B3产量A151

812A224114A33

674销量91011例题用伏格尔法求初始调运方案第十三页，共三十七页，2022年，8月28日

销产B1B2B3产量A1210

12A231114A34

4销量91011初始调运方案第十四页，共三十七页，2022年，8月28日2.2最优解的判别判别办法是计算空格(非基变量的检验数),因为运输问题的目标函数是实现最小化,所以当所有空格处的检验数大于等于零时,为最优解.

下面分别介绍两种计算检验数的方法:闭回路法(2)位势法第十五页，共三十七页，2022年，8月28日①闭回路法闭回路：从空格出发画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。

销产B1B2B3B4供量A1

5

27A23

14A3

6

39销量

3656表3-7第十六页，共三十七页，2022年，8月28日

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1

销地产地

6

3

3

4

3

1计算最小元素法得到的初始基可行解的检验数

(+1)

(-1)

(+1)

(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1调整后总运费增加：空格处检验数为1表3-8第十七页，共三十七页，2022年，8月28日

5

10

4

7A3

8

2

9

1A2

10

3

11

3A1B4B3B2B1

销地产地

6

3

3

4

3

1

(+1)

(-1)

(+1)

(-1)7-5+10-3+2-1=10调整后总运费增加：空格处检验数为10

(-1)

(+1)表3-9第十八页，共三十七页，2022年，8月28日检验数表110121-12因为存在小于零的检验数,所以最小元素法给出的方案不是最优方案.表3-10第十九页，共三十七页，2022年，8月28日位势法

求检验数的步骤:

1在表中下面和右面增加一行和一列,列中添入ui,行中添入vj,令u1=0,按照,根据表中已有的数字确定所有的ui及

vj;

2

计算所有空格处的检验数.

第二十页，共三十七页，2022年，8月28日

0

1

1

28-3

7检验数表121-1101224=-1＜0，当前方案不是最优方案。最优方案判别准则表3-12第二十一页，共三十七页，2022年，8月28日2.3闭回路调整法改进方案xpq为换入变量从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。表3-13第二十二页，共三十七页，2022年，8月28日找到最小调整量以后,按照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。

销产B1B2B3B4供量A1

5

27A23

14A3

6

39销量

3656再用闭回路法或者位势法求检验数，得到下表:表3-14第二十三页，共三十七页，2022年，8月28日

销产B1B2B3B4供量A102

7A22

14A39

129销量

3656这时所有的检验数都非负，表中的解就是最优解.表3-15第二十四页，共三十七页，2022年，8月28日

销产B1B2B3B4供量A137

6

45A224

322A34

38

53销量

3322例求该运输问题的最优解第二十五页，共三十七页，2022年，8月28日2.3表上作业法计算中的问题1.退化:

用表上作业法求解运输问题当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。有以下两种情况：

(1)当确定初始解的各供需关系时，若在(i,j)格填入某数字后，出现Ai处的余量等于Bj处的需量。这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格。不能同时划去行和列。第二十六页，共三十七页，2022年，8月28日(2)在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，这时应取调整量θ=0。第二十七页，共三十七页，2022年，8月28日

销产B1B2B3B4供量A11067124A21610599A35410104销量5246第二十八页，共三十七页，2022年，8月28日2.5.3产销不平衡的运输问题及其求解方法第二十九页，共三十七页，2022年，8月28日当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为，在单位运输表上令从该假象产地至各销地的运价为0当销小于产时，可以在产销平衡表中增加一个假想的销地（库存）j=m+1，，在单位运输表上令从产地至该假象销地的运价为0

第三十页，共三十七页，2022年，8月28日

销产B1B2B3B4供量A1211

347A2103

595A37

81

27销量

2346例：设有三个产地生产某种物资，其产量分别为7吨，5吨，7吨，四个销地需要该种物资，销量分别为2吨，3吨，4吨，6吨，又知各产销地之间的单位运价，试决定总运费最少的调运方案。产大于销第三十一页，共三十七页，2022年，8月28日例2：设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。已知各化肥厂年产量，各地区年需要量及从各化肥厂到各地区单位化肥的运价如表3-25所示。试决定使总的运费最节省的化肥调拨方案。表3-25运价：万元/万

t第三十二页，共三十七页，2022年，8月28日解这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为210吨。为了求得平衡，在产销平衡表