运输问题3Word文档格式.docx

运输问题3Word文档格式.docx

《运输问题3Word文档格式.docx》由会员分享，可在线阅读，更多相关《运输问题3Word文档格式.docx（14页珍藏版）》请在冰点文库上搜索。

也就是说，在数学模型中要增加约束条件xij=0，去掉这个约束条件使模型转化为运输问题的方法是：

将Ai到Bj的运价Cij修改为一个充分大的正数M，从而使得任意一个含有xij≠0的调运方案均不可能成为最优方案，这样在得到了相应的运输问题的最优调运方案时，约束条件xij=0自动地得到了满足。

例4.4供需双方在协商后签订了一个供货合同，合同规定供给方向六个地区（记为B1，B2，B1，B3，B5，B6）提供某种物资并负责物资的运输，同时规定B2和B4的物资只能有产地A1或A2调入。

各地的供给量，需求量以及运价有表4.18给出。

求满足合同要求的最优调运方案。

表4.18供需关系与运价表

销地\产地

B1

B2

B3

B4

B5

B6

供给量

A1

3

5

7

9

2

8

150

A2

1

6

4

180

A3

120

需求量

70

80

40

140

60

450

合同要求B2和B4的物资只能由A1和A2供给，形成了B2，B4对A3的封锁。

将C32和C34改为M（在应用计算机计算时M可取一个确定的数，如M=50），根据表4.19所示，应用表上作业法对这个问题可得最优调运方案，该方案由表4.20给出。

表4.19供需平衡表

销地

产地

ai

M

bj

表4.20最优调运方案表

10

运输能力限制

在制定物资调运方案时，管理人员应该考虑物资所经路段的运输能力。

设Ai到Bj的路段的运输能力为dij，如果Ai的供应量和Bj的需求量都大于dij，则从Ai到Bj的物资调运量至多为dij，也就是说，在物资调运时Ai到Bj的路段存在着运能力的限制。

此时相应的数学模型中应增加运输能力约束，即有xij<

=dij。

为将这种类型的问题转化为运输问题模型，我们可将Bj想象为两个销地Bj’和Bj’’，规定Bj’的需求量为dij，从而使得Ai到Bj’（实际上为Ai到Bj）路段不再有运输能力的限制，同时规定Bj’’的需求量为bj—dij，且Bj’’对Ai封锁，这样就不会有多于dij的物资经过Ai到Bj的路段。

例4.4某运输公司可承担某种物资的运输任务，有关数据由表4.21给出，其中cij表示单位物资从Ai到Bj的成本。

有关部门在A1到B3，A2到B1，A2到B4三个路段给出该公司的物资通过限量分别为15，15和10。

应如何指定物资调运方案，才能使运输的总成本最小。

表4.21供需关系与单位成本表

产地\销地

25

55

20

45

15

100

由于A2的供应量和B1的需求量都大于该路段的限制量，上述问题在A2到B1路段具有运输能力限制。

为建立该问题的运输问题模型，将B1视为二个销地B1’和B2’’，需求量分别为15和30，且B1’’对A2封锁。

同样处理另二个有运输能力限制的路段，A1到B3和A2到B4。

具体的模型见下面的表4.22。

表4.22供需平衡表

B1'

'

B3'

B4'

30

应用表上作业法求解，结果如表4.23所示。

将Bj’和Bj’’合并视为Bj，j=1，2，3，4，就得到可操作的调运方案，见表4.24。

表4.23

表4.24

有界需求

我们知道在物资调运中，如果总供应量小于总需求量，需要虚拟一个产地以达到形式上的供需平衡。

但如果仅仅考虑运输总费用最小这一经济目标，就可能使得一个或一些销地的需求全部由虚拟的产地供给，而实际上这些销地将得不到任何物资。

若这种物资是很重要的工业原料或者是日常生活中的必需品，上述情况的出现将会对这些销地的经济发展和人民生活需求带来重大的影响。

为避免出现这种情况，政府或有关部门应该给予干预，也就是说应从经济利益和社会利益等诸多方面统筹安排，以供物资在各个销地得到合理的分配。

其中的一个方法是对分配给一些销地的物资数量适当地加以限制，如限制销地Bj的物资数量在Lj和Uj之间，其中0<

=Lj<

=Uj。

称这种类型的问题为具有有界需求的物资调运（分配）问题，称Lj和Uj分别为销地Bj的最低需求量和最高需求量。

在物资分配时，Lj和Uj将起到协调作用，它们的取值应由政府或有关部门根据各地的实际情况给出，也可由各销地充分协商后确定。

但是Lj和Uj应满足如下条件：

即使得总供应量介于最低需求总量和最高需求总量之间。

因为从经济学的角度，如果总供应量与其中的任意一个量相等，将使物资分配成为一种简单的运输问题。

具有有界需求的物资调运（分配）问题含有约束条件

j=1,2,3……n.

为建立它的运输问题模型可采用以下方法。

将每个销地Bj视为二个销地Bj’和Bj’’，令Lj为Bj’的需求量，且Bj’对虚拟产地Am+1封锁以满足Bj的最低需求。

Bj’’的需求量为Uj—Lj，Bj’’的物资可由Am+1供给，即Am+1到Bj’’的运价为零。

由于从总体上物资是供不应求的，每个销地实际得到的物资量不会超过该地的最高需求量。

这样使得上述的约束条件隐含于运输问题模型之中。

例4.6某商业公司为下属四个商场（记为B1，B2，B3，B4）采购某种商品，由于资源紧张，采购部门仅能从产地A1，A2和A3处得到有限的订货量，不能充分满足各商场的实际需要。

管理部门决定对各商场实行限量供应。

根据下面的数据表（表4.25），制定一个分配方案，使得在满足个各商场的最低需求的条件下公司付出的总运输费用最少。

表4.25

订货量

16

13

22

17

50

14

19

23

Ｍ

最低需求量

无

最高需求量

首先补足数据表中缺失的数据，考虑到B3无最低需求要求，可以设定它的最低需求量满足L3=0。

这样四个销地的最低需求总量为L=110，由于总订货量S=160，在满足各商场的最低需求后，商品还多出50，可设想全部分配给B4，从而B4的最高需求量为U4=60。

现在四个商场的最高需求量为210，因此虚拟在产地A4处的订货量为a4=50。

根据前面的分析可得出该问题的运输问题模型，如表4.26所示。

表4.26

B2'

A4

210

模型中不含B2’’和B3’，这是由于U2-L2=0和L3=0，求得后可求得最优分配方案，如表4.27所示：

表4.27

而实际分配方案由表4.28给出。

表4.28

转运运输

在运输管理中，经常要处理物资的中转运输问题。

例如物资从产地运到销地必须使用不同的运输工具。

这样就需要首先将物资从产地运到某地（称为中转站），更换运输工具后再运往销地。

又如，由于运输能力的限制或价格因素（转运运价小于直接运价），需要将不同产地的物资首先集中到某个中转站，再由中转站发往销。

需要中转站的运输称为转运运输。

我们首先讨论一次转运问题。

一般提法是：

设有r个中转站T1，T2，…..Tr。

物资的运输过程是先从产地Ai运到某个中转站Tk，再到运往销地Bj。

已知Ai到Tk的运价为Cik,Tk到Bj的运价为Ckj，Ai的供给量为ai，通过Tk的最大运输能力为dk,Bj的需求量为bj。

不妨设

，

也就是说，供需是平衡的且所有的饿物资经转运后都达到销地。

现在要求得一个转运方案，使得运输的总费用最小。

为建立转运问题的线性规划模型，设决策变量为

xik：

从Ai到Tk的调运量。

i=1,2,3,…m,k=1,2,…r.

xkj:

从Tk到Bj的调运量。

j=1,2,3,…n,k=1,2,…r.

对每个变量均有非负要求。

目标函数为两个阶段费用之和达到最小，即

minZ=

约束条件分为以下几组，

供给约束：

n

运输能力约束：

中转站平衡：

k=1,2,3……..r,

需要约束：

j=1,2,3…….n.

有转运问题模型的结构，它也可转化为运输问题模型求解。

其方法是将每个中转站Tk既看成产地也看成销地，从而形成一个有m+r个产地（按A1，A2，…，Am，T1，T2，…，Tr排序），有r+n个销地（T1，T2，…，Tr，B1，B2，…Bn排序）的运输问题。

由于物资不能由Ai直接到达Bj，故Bj对Ai封锁。

同样，不同的中转站之间也互相封锁。

Tk（这里需要三指标变量以区分变量表示的是从产地到中转站，还是从中转站到销地。

两指标变量不能做到这点。

）的供给量和需求量均为dk，从而总供给量为

，总需求量为

，以实现供需平衡。

在转运问题的运输问题模型中，我们实际上已将运输能力化为等式约束，即在该不等式中增加一个松弛变量Xi+kk,它的实际意义为物资从Tk到Tk的调运量。

当Xi+kk>

0时，即从各产地往到Tk的物资总量小于dk时，虚拟这个调运量Xi+kk以达到供需平衡。

因此Tk到Tk的运价为零。

该运输问题的最优方案将处于封锁状态下是调运量为零，从而自动满足转运问题的所有约束条件。

例4.7将某种物资从A1，A2，A3运往B1，B2，B3，B4，B5五个销地，物资必须经过T1，T2，T3，T4中的任意一个中转站转运，有关数据有表4.29和4.30给出。

求这个转运问题的运输问题模型。

表4.29

中转站＼产地

T1

T2

T3

T4

12

11

90

中转站的运输能力

340\240

表4.30

销地＼

中转站

销地需求量

该转运问题可转化为具体七个产地和九个销地的运输问题，数学模型可由表4.31表示，

表4.31转运问题供需平衡表

580

应用表上作业法可得最优调运方案，如表4.32所示。

表4.32

由上表不难得出转运方案，如图4.2所示。

实际运输过程中物资可能需要多次中转，这种类型的转运问题的线性规划比较复杂，但将它转化为运输问题模型时，与一次转运问题具有相同的形式。

处理时只需适当掌握好禁运与封锁原则，即当物资不能从一个产地或中转站直接到达另一个中转站或销地时，就应当对这两地实行禁运与封锁。

例如，在某个运输过程中，物资从产地A2经汽车运往火车站T1或T2，经铁路运输到达港口T3或T4，最后海运到销地B3。

此时A2应对T3，T4禁运，B3应对A2，T1和T2封锁。

由于运输问题的目标函数的优化方向为极小，在最优转运方案中不会出现物资的逆向流动。

例如一个方案中既含有物资从T2到T1的调运（设调运量为20），又有物资从T2到T1的调运（设调运量为10），则该问题一定不是最优方案，因为只要将T1到T2的调运量改为10，T1到T1的虚调运量也为10，则总费用必然要减少。

根据实际情况，某些产地或销地也可作为中转站，此时在运输问题模型中应以产地的原有供给量与运输能力之和作为模型中的供给量，并以运输能力作为它的需求量，同时，销地的原有需求量与运输能力之和作为模型中的需求量，以运输能力作为它的供给量。

这样仍然保持原有的供需平衡。

当转运问题中无运输能力约束时，可以以总供给量作为每个中转站的运输能力限制。

例4.8某种物资在三个产地A1，A2和A3的供给量分别是9，4和7，四个销地B1，B2，B3，B4的需求量分别是6，6，5，3。

物资从产地到销地需转运，连接各地的交通图如图4.3所示

图中连线上方的数字表示两地的运价。

给出这个转运问题的运输问题模型。

由图4.3可知A2，A3和B4均可作为中转站，这样共有8个中转站，转运问题的运输问题模型中共有9个产地和11个销地。

由于各地均没有运输能力约束，因此以a=20作为每个中转站的运输能力限制。

由图中各地间的关系可确定两地间是否需要禁运与封锁，如此可得下面的模型，如表4.33所示。

表4.33

T5

24

27

一般来讲，多过程的转运问题都可以用一个图表示（如图4.3），称这个图为网络。

因此，多过程转运问题也可归结为网络分析中的“最小费用最大流”问题。