第三章运输问题

第三章运输问题3.1运输问题的模型3.2运输问题的表上作业法3.3产销不平衡的运输问题3.4运输问题的应用3.5运输问题的计算机求解例1某食品公司有三个生产面包的分厂A1、A2、A3

，有四个销售公司B1、B2、B3，B4，由于供需双方两两间的相对位置不同因而单位运价不同，有关数据如下表：

B1B2B3

B4产量

A13113107

A219284A37410

5

9

销量3656

问应如何安排运输才能使总运费为最小？3.1运输问题的模型设表示从产地Ai调运到Bj的运输量（i=1,2,3;j=1,2,3)B1B2B3B4

产量A1x11x12x13x147

A2x21x22x23x244

A3x31x32x33x349销量3646分析：这是一个产销平衡的运输问题。一个运输方案可列表如下：f=3x11+11x12+3x13+10x14

+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34

B1B2B3B4产量A13113107

A219284

A3741059销量3646该运输问题的线性规划模型为：x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9

x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6

Xij

³0(i=1,2;j=1,2,3)Min运输问题的一般提法是：

某种物资有m个产地iA，产量分别为),...,2,1(miai=，有n个销

地jB，销量（需求量）分别为),...,2,1(njbj=,已知iA到jB的单位运

价为),...,2,1;,...,2,1(nnmicij==，又假设产销是平衡的，即：

åå===njjmiiba11，问应如何安排运输可使总运费最小？

假定ijx表示由iA到jB的运输量，则平衡条件下的运输问题可写出

如下的线性规划模型：

ijminjijxczåå===11min

s.t.),...,2,1(1miaxinjij==å=

),...,2,1(1njbxjmiij==å=

0³ijx3.2

运输问题的表上作业法

表上作业法的解题步骤：

先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。

确定初始方案（初始基本可行解）判定是否最优？

改进调整（换基迭代）结束否是例1某食品公司有三个生产面包的分厂A1、A2、A3

，有四个销售公司B1、B2、B3，B4，由于供需双方两两间的相对位置不同因而单位运价不同，有关数据如下表：

B1B2B3B4产量

A13113107

A219284A3741059

销量3656问应如何安排运输才能使总运费为最小？方法1：最小元素法基本思路是“就近供应”，即对单位运价最小的变量分配运输量。B1B2B3B4产量A17A24A39销量3656总运输费用=86第一步:确定初始方案（初始基本可行解）3B1B2B3B4A1311310

A21928

A3741051463315432方法2：Vogel法B1B2B3B4产量A17A24A39销量3656总运输费用=853B1B2B3B4A1311310

A21928

A374105156320112513012213012127612第二步:求检验数，判别最优性方法1：闭回路法

在调运方案表中，从一个空格出发沿水平或垂直方向前进，遇到一个有数字的格子时，就转向90度继续前进，这样经过若干次拐弯后，必然回到原来出发的那个空格，于是就形成了一条由水平线段和垂直线段组成的封闭折线即闭回路。在理论上可以证明：过每一个空格一定可以做唯一的一条闭回路。B1B2B3B4产量A1()437A2314A3639销量3656一般地，就把过空格的闭回路中第奇数次拐角点上的运费总和减第偶数次拐角点上的运费总和之差称作空格的检验数，记为

B1B2B3B4产量A1437A2314A3639销量

36563

11310179421085+1-1-1+1检验数的经济含义：对闭回路中的运量做单位调整后，总运费的增减量

B1B2B3B4产量A1437A2314A3639销量

36563

11310192874105+1-1-1+1+1-1检验数：最优方案的判别标准：如果所有空格的检验数均已非负，则相应的调运方案已是最优方案；否则若某空格中仍有负数，则需要对方案进行调整。本例中，初始运输方案的检验数中，

λ24=-1因此，该运输方案不是最优方案。方法2：位势法步1：将运输方案中的调运量换成其单位运价；B1B2B3B4产量A1437A2314A3639销量3656B1B2B3B4产量A13107A2124A3459销量3656表2表1：运输方案1步2在表2中增加一行Vj

，增加一列Ui,使Vj和Ui满足：

Ui+Vj=Cij

表3

B1B2B3B4产量A13107A2124A3459销量3656B1B2B3B4产量UiA131070A2124-1A3459-5销量3656Vj29310步3依据求出的Vj和Ui值，计算所有空格位置的检验数。λij=Cij

－（Ui+Vj）表4

B1B2B3B4产量UiA131070A2124-1A3459-5销量

3656Vj29310λ11=C11－U1－V1=1λ12=C12－U1－V2=2λ22=C22－U2－V2=1λ24=C24－U2－V4=-1λ31=C31－U3－V1=10λ33=C33－U3－V3=12B1B2B3B4A1311310

A21928

A374105第三步，调整运输方案

调整方法：闭回路调整法

在小于零的负检验数中，找出绝对值最大的检验数；然后确定该检验数的闭回路，并对其运量做最大可能的调整。B1B2B3B4产量A14

37A2314A3639销量3656表1：运输方案1B1B2B3B4产量A1527A2314A3639销量3656表5：新的运输方案+1-1-1+1对表5给出的运输方案，再用位势法进行检验：

表5：新的运输方案B1B2B3B4产量A1527A2314A3639销量3656λ11=C11－U1－V1=0λ12=C12－U1－V2=2λ22=C22－U2－V2=2λ23=C23－U2－V3=1λ31=C31－U3－V1=9λ33=C33－U3－V3=12由上述检验数可知，所有检验数都大于或等于“0”，因此，表5所示的解是最优运输方案。

B1B2B3B4产量A1527A2314A3639销量3656总运费=85进一步讨论：寻找多个最优方案

由于X11的检验数λ11=0，可知该运输问题有多个最优解。B1B2B3B4产量A1527A2314A3639销量3656B1B2B3B4产量A1257A2134A3639销量3656B1B2B3B4A111310

A21928

A3741052总运费=85

实际问题中产销往往不一定是平衡的。但无论是总产量大于总销量，

还是总销量大于总产量都可以用表上作业法求解。基本思路是：当产量

大于销量（或销量大于产量）时，应虚设一个销地或库存（产地或亏空），

使其销量（产量）为总产与销量的差额，单位运价为零,并在表上增一列

（行），即可化为平衡问题。

3.3产销不平衡的运输问题

例2设有一个运输问题如下表:B1B2B3B4产量A1211347A2103595A378127销量2346试确定一个最优调运方案。分析：这是一个产销不平衡的运输问题（总产量大于总销量）方法：虚设一个销地（库存）B5B1B2B3B4产量A1211347A2103595A378127销量2346B1B2B3B4B5产量A12113407A21035905A3781207销量23464解：应用表上作业法，最后得到的最优调运方案是：

1B

2B

3B

4B

B5

产量

1A

2A

3A

2

3

2

3

2

4

3

7

5

7

销量

2

3

4

6

4

最小运费Z=35

例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为0例4、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为03.4运输问题的应用例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。

例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。解：设xij为第i季度生产的第

j季度交货的柴油机数目，那末应满足：

交货：x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第

j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地

1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；

2）上年末库存103台，只有仓储费和运输费，把它列为的0行；

3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；

4）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。产销平衡与运价表：例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产450台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛转运问题：

在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。解：设xij

为从i到j的运输量，可得到有下列特点的线性规划模型：

目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量

对转运站（中转点）：输入量-输出量=0

对销地（收点）j：输入量-输出量=销量例8．（续）目标函数：

Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

约束条件：

s.t.x13+x14≤600(广州分厂供应量限制）

x23+x24+x28≤450(大连分厂供应量限制）

-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）

-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）

x35+x45=200（南京的销量）

x