运筹学课件第三章运输问题

第三章运输问题

一、学习目的与要求

1、掌握表上作业法及其在产销平衡运输问题求解中的应用

2、掌握产销不平衡运输问题求解方法 二、课时 6学时

第一节 运输问题及其数学模型

一、运输问题的数学模型

单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？

表中x ij i j ij i j

如果运输问题的总产量等于其总销量，即有

∑∑===n

j j

m i i b

a 1

1

则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。

产销平衡运输问题的数学模型如下：

????

?

????≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1

111

1

ij m i j

ij n

j i

ij m i n j ij

ij x n

j b x m

i a x t s x c z

这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。

二、运输问题数学模型的特点

1、运输问题有有限最优解，即必有最优基本可行解

2、运输问题约束条件的系数矩阵A 的秩为(m+n-1)

该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j

对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1

(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。

此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和

第二节 用表上作业法求解运输问题

解题步骤

第1步：确定初始基本可行解。

第2步：最优性判别，若最优准则σij ≥0，则当前解最优，计算停止，否则转第3步。 第3步：取一个检验数最小的非基变量做进基变量。 第4步：调整当前基本可行解，转第2步

一、确定初始基本可行解（初始调运方案） 以实例介绍：

例 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售，各工厂的生产量、各销点的销售量（假定产位均为t ）以及各工厂到各销售点的单位运价（元/t ）于下表中，要求研究产品如何调

A 最小元素法

总运费（目标函数）：24611

==∑∑==i j ij ij

x c

z 这个解满足约束条件，其非零变量的个数为6（等于

m+n-1=3+4-1=6）。 B 西北角法

总运费（目标函数）：37211

==∑∑==i j ij ij

x c

z 这个解满足约束条件，其非零变量的个数为6（等于

m+n-1=3+4-1=6）。 C

总运费（目标函数）：24411

==∑∑==i j ij ij

x c

z

二、解的最优性检验 1、闭回路法

检验数表

由于024<σ，故知解不是最优解。 2、对偶变量法（也称位势法）

对产销平衡问题，若用n m v v v u u u ΛΛ,,,,,2121分别表示前m 个约束条件与后n 个约束条件的对偶变量，即有对偶变量

),,,,,(2121n m v v v u u u Y ΛΛ=

这时对偶问题的对偶规划写成

???

??

?

?==≤++='∑∑==的符号不限j i ij j i j

n

j j i m i i v u n

j m i c v u t s u b u a z ,,,2,1,,2,1..max 1

1

ΛΛ

由上一章知道，线性规划问题变量x j 的检验数可表示为

j j j B j j j j YP c P B C c z c -=-=-=-1σ

由此可写出运输问题某变量x ij 的检验数如下：

)(),,,,,,,(2121j i ij ij n m ij ij ij ij ij ij v u c P v v v u u u c YP c z c +-=-=-=-=ΛΛσ

现设我们已得到解到了运输问题的一个基可行解，其基变量是

1,,,21121-+=n m s x x x s j i j i j i s Λ

由于基变量的检验数等于零，故对这组基变量可写出方程组

??

???

?

?=+=+=+js s i s j is j i j i j i j i c

v u c v u c v u ,2

,221,1111

1112Λ 这个方程组有m+n-1个方程。

解以上方程组，可得解（上方程组解不唯一），此方程组解称为位势。 由上章知当每个0)(≥+-=j i ij ij v u c σ达到最优解。 例

??????????

?=+=+=+=+=+=+6

532

11

4432332

1241

31v u v u v u v u v u v u 令02=u 得方程组的解：9,4,10,1,3,2234131=-=====v u v u v v 计算检验数

由于σ24<0

三、解的改进（用闭回路法调整当前基可行解）

解的改进步骤：

（1）以x ij 为换入变量，找出运输表中的闭回路； （2）对顶点进行编号；

（3）确定换出变量：在闭回路上的所有偶数顶点中找出运输量量小的顶点，以该格中的变量为换出变量；

（4）以换出变量值为奇数顶点处的运输量增加值，得新的运输方案； （5）检验新的方案是否为最优，如否则重复以上步骤。

??????????

?=+=+=+=+=+=+6

592

114432342124131v u v u v u v u v u v u 令02=u 得方程组的解：2,8,3,2,9,2

==-====v v u u v v

四、表上作业法计算中的几个问题

1、某个基本可行解有几个非基变量的检验数为负

若运输问题的某个基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量均可使目标函数值得到改善，但通常取σij <0中最小者对应的变量为换入变量。 2、无穷多个最优解

当迭代到运输问题的最优解时，如果有某非基变量的检验数＝0，则说明该运输问题有无穷多最优解。（如上例，为得到另一个最优解，只需让σij ＝0的非基变量进基） 3、退化问题

当运输问题某部分产地的产量和与另一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。

在运输问题中，退化解是时常发生的，为了使表上作业法的迭代工作进行下去，退化解应在同时划去的一行或一列中的某个空格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。

b.在用闭回路法调整当前基本可行解时，调整量θ的取值应为θ＝min{x ij /( i,j )为闭回路上所有偶数号格点}。这时可能出现有两个（或以上）偶数号格点的xij 都相等且都为极小值，只能取其中一个为离基格，其余的仍作为基格，而在作运输量调整时，运输量与θ相等的那些偶数号格点的x ij 都将调整为0，因此得到的也是一个退化了的基可行解。

第三节运输问题的进一步讨论

一、产销不平衡的运输问题

1、如果总产量大于总销量，即

∑∑==>n

j j

m i i b

a 1

1

此时运输问题的数学模型为

????

?

????≥===≤=∑∑∑∑====0,...,2,1,...,2,1..min 1

111

ij m i j

ij n

j i

ij m i n

j ij

ij x n

j b x m

i a x t s x c z

为借助产销平衡时表上作业法求解，可增加一个假想销地B n+1，由于实际上它不存在，因而由产地A i （i =1,2,…,m ）调运到这个假想销地的物品数量x i,n+1（相当于松驰变量），实际上是就地存贮在A i 的物品数量。就地存贮的物品数量不经运输，故可令其运价c i,n+1=0（i =1,2,…,m ）。 若令假想销地的销量为b n+1，且

∑∑==+-=n

j j m i i n b a b 1

1

1

则模型变为

????

?

????≥+=====∑∑∑∑=+==+=01

,...,2,1,...,2,1min 1

1

111

1

ij m i j ij n j i

ij m i n j ij

ij x n j b x m

i a x x c z

运输表

2、总销量大于总产量

可假想增加一个产地A m+1，它的产量等于

∑∑==+-=m

i i n j j m a b a 1

1

1

由于这个产地并不存在，求出由它发往各销地的物品数量x m+1,j （j =1,2,…,n ），实际上各销地所需物品的欠缺额，显然有c m+1,j =0（j=1,2,…,n ）。 因此数学模型为

????

?

????≥==+===∑∑∑∑==+==0,...,2,11

,...,2,1min 1

1111

ij m i j ij n

j i

ij m i n

j ij

ij x n

j b x m i a x x c z

例 某市有三个造纸厂A 1,A 2,A 3,其纸产量分别为8，5，9个单位，有4个集中用户B 1,B 2,B 3,B 4,其需用量为4，3，5，6

解略:

Min z= 49

二、有转运的运输问题

假定某一产品有m 个产地A 1,A 2,…,A m 和n 个销地B 1,B 2,…,B n ，都可作为中间站使用，从而发送物品的地点和接收物品的地点都有m+n 个。这样一来，我们就得到一个扩大了的运输问题。令

a i ：表示第 i 个产地的产量（净供应量）；

b j ：表示第 j 个销地的销量（净需要量）；

x i j ：表示第 i 个发送地运到第 j 个接收地的物品数量； c i j ：表示第 i 个发送地运到第 j 个接收地的单位运价； c i ：表示第 i 个地点转运单位物品的费用。

若将产地与销地统一编号，并把产地排在前，销地排在后，则有

02121======+++m n m m m b b b a a a ΛΛ

假定为产销平衡问题，即有

Q b

a n

m j j

m i i ==∑∑+==1

1

运输表：

运价表：

例：如下图示出了一个运输系统，它包括两个产地、两个销地及一个中转站，各产地产量和各销地销量用相应节点处箭线旁的数字表示，节点连线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。

解：

销地产地

产地转运销地发送

量12345

产地1-4532M60 50(50)10(10)

25-12M490

50(50)(20)2020(20)

转运3

32-355

50

50(30)(20)

销地4

2M5-36

50

50(50)

5M456-550

50(50)

销量5050508070

第四节应用问题举例

由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多．所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型．下面介绍几个典型的例子．例1 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机．已知该厂各季度的生产能力及生产每台柴油机的成本如表所示．又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元．要求在完成合同的情况下，做出使该厂全年生产(包括储存、维护)费用最小的决策．

解: 由于每个季度生产出来的柴油机不一定当季交货，所以设x ij为第i季度生产的用于第j季度交货的柴油机数．

根据合同要求，必须满足：

??????

?=+++=++=+=20

25

1510

44342414332313221211x x x x x x x x x x 又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：

??????

?≤≤+≤++≤+++10

30

3525443433242322214131211x x x x x x x x x x 第i 季度生产的用于j 季度交货的每台柴油机的实际成本c ij 应该是该季度单位成本加上储存、维护等

费用．c ij 的具体数值见表

设用a i 表示该厂第i 季度的生产能力，b j 表示第j 季度的合同供应量，则问题可写成：

????

?

????≥=≤=∑∑∑∑====0min 41

4

1414

1

ij i j ij j i

ij i j ij

ij x b x a x x c z

因为当j

所以当j

此外，由于是产量大于销量的不平衡问题，∴加上一个假想的需求D ，就可以把问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，如下)

经用表上作业法求解，可得多个最优方案，表3—32中列出最优方案之一．即第1季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台．用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货Ⅳ季度生产10台，于当季交货．按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元．

例2 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务．已知(1)各条航线的起点、终点城市及每天航班数．(2)假定各条航线使用相同型号的船只，又已知各城市间的航程天数．(3)又知每条船只每次装卸货的时间各需1天。问该航运公司至少应配备多少条船，才能满足所有航线的运输需求?

每天航班数表

各城市之间的航程天数

解：该公司所需配备船只分两部分：(1)载货航程需要的周转船只数。例如航线l，在港口E装货1天，E —D航程l 7天，在D卸货1天，总计19天．每天3航班，故该航线周转船只需57条．各条航线周转所需船只数见表．以上累计共需周转船只数

91条．

(2)各港口间调度所需船只数．有些港口每天到达船数多于需要船数．例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B．各港口每天余缺船只数的计算见表．为使配备船只数最少，应做到周转的空船数为最少．因此建立以下运输问题，其产销平衡表见表．

单位运价表应为相应各港口之间的船只航程天数，见表

用表上作业法求出空船的最优调度方案见表

另一最优解为x CA=1,x CE=1,x DB=1,x DE=1,x FE=1

按这两个方案掉运船只，解得Z=40，说明各港口之间调度所需船只至少为40艘。

综合以上两方面的要求，在不考虑维修、储备等情况下，该公司至少配备131条船，才能满足4条航线正常运输的需要。

如有侵权请联系告知删除，感谢你们的配合！

第七章 运筹学 运输问题案例

第七章运输问题 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表：

# 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少 ^ 解：得运价表（产大于销的运输模型）如下： | 得生产安排的方案：

第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 如下表表示： 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表： （万元/吨）

浅谈运筹学中的运输问题.doc11

浅谈运筹学中的运输问题 摘 要：运筹学自二战以来开始打来那个应用在除战争以外的许多领域，尤其在企业管理中表现的尤为突出。运筹学的思想贯穿了企业管理的始终，在企业战略管理、生产计划、市场营销、运输问题、库存管理、人事管理、财务会计等各个方面都具有重要的作用，对企业管理的发展产生重要影响。这里我们主要对运输问题几种方法做一个简单的介绍。 关键词：最下元素法；沃格尔法（V ogel ） 首先我们先来介绍运输问题的数学模型：设有m 个产地（记作A 1，A 2，A 3,…,Am ），生产某种物资，其产量分别为a 1,a 2，…，am ；有n 个销地（记作B 1，B 2，…，Bn ），其需要量分别为b 1,b 2，…，bn ；且产销平衡，即 。从第i 个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设xij (i =1,2,…，m ；j =1,2,…,n )为第i 个产地到第j 个销地的运量，则数学模型为： n j m i x n j b x m i a x ij j m i ij n j i ij ,,1;,,1, 0,,1,,11 1 ==≥====∑∑== ∑∑ ===n j ij ij m i x c z 1 1 min （！）最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij 对应的变量xij 优先赋值 {} j i ij b a x ,min = 然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。 下面举一个例子：求表3－7给出的运输问题的初始基本可行解。

解： 在x 12、x 22、x 33、x 34中任选一个变量作为基变量，例如选x 12 初始基本可行解可用下列矩阵表示 ??????????634610 表3－8中，标有符号 的变量恰好是3+4－1=6个且不包含闭回路， {} 323123141312,,,,,x x x x x x 是一组基变量，其余标有符号×的变量是非基变量， （2）运费差额法（V ogel ）:最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案， 20101258515 10??????=?C 2010125815510? ?????=?C 15 15 15 15 前一种按最小元素法求得，总运费是Z 1=10×8+5×2+15×1=105，后一种方案考虑到C 11与C 21之间的差额是8－2=6，如果不先调运x 21，到后来就有可能x 11≠0，这样会使总运费增加较大，从而先调运x 21，再是x 22，其次是x 12这时总运费Z 2=10×5+15×2+5×1=85

运筹学(胡运权版)第三章运输问题课后习题答案

P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A 1， A 2，A 3的生产量、各销售点B 1，B 2，B 3，B 4的销售量（假定单位为t ）以及各工厂到销售点的单位运价（元/t ）示于下表中，问如何调运才能使总运费最小？ 表 解：一、该运输问题的数学模型为： 可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6. 34 33323124232221 3141 141312116115893102114124min x x x x x x x x x x x x x c z i j ij ij +++++++++++== ∑∑ ==??? ??????????==≥=++=++=++=++=+++=+++=+++4,3,2,1;3,2,1,0141214822 1016342414332313322212312111343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij 111213142122232431323334x x x x x x x x x x x x 712111111111111111111111111??? ? ? ? ? ? ? ? ? ???

二、给出运输问题的初始可行解（初始调运方案） 1. 最小元素法 思想：优先满足运价（或运距）最小的供销业务。

其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6). 总运费为（目标函数值） ,1013=x ,821=x ,223=x ,1432=x ,834=x ,614=x ∑∑===314 1 i j ij ij x c Z

第七章 运筹学 运输问题案例

第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表： 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维

护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：得运价表（产大于销的运输模型）如下： 第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 7.3 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表：

运筹学课件第三章运输问题

第三章运输问题 一、学习目的与要求 1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时 第一节 运输问题及其数学模型 一、运输问题的数学模型 单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？ 表中x ij i j ij i j 如果运输问题的总产量等于其总销量，即有 ∑∑===n j j m i i b a 1 1 则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 产销平衡运输问题的数学模型如下：

???? ? ????≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1 111 1 ij m i j ij n j i ij m i n j ij ij x n j b x m i a x t s x c z 这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。 二、运输问题数学模型的特点 1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A 的秩为(m+n-1) 该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j 对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1 (2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。 此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和

运筹学模型在运输问题中的应用

《数值分析》课程设计非线性方程求根公式的集成与菜单调用 院（系）名称信息工程学院 专业班级12普本信计 学号1201110054 学生姓名孟浩 指导教师孔繁民 2015年6月16日

课程设计任务书 2014—2015学年第二学期 专业班级：12 普本信计学号：1201110054 姓名：孟浩 课程设计名称：运筹学 设计题目：运筹学模型在运输问题中的应用 完成期限：自2015年 5 月24 日至2015 年05 月30 日共 1 周一、设计目的 运筹帷幄之中，决胜千里之外。运筹学是多种学科的综合性学科，是最早形成的一门软科学。他把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上，以便为那些掌握系统的人们提供最佳的解决问题的办法。他用科学的方法研究与某一系统的最优管理有关问题。因此运筹学是一门有重要应用价值的学科，特别在现代科学管理中是处处离不开运筹学。为了更好的理解运筹学，我们运用运筹学知识建立数学模型来解决运输问题中的应用的问题。 二、设计要求 1、运用LINGO等工具。 2、运筹学模型在运输问题中的应用。 3、按照格式要求写出3000字文档。 三、参考文献 [1]谢金星薛毅，优化建模与LINDO/LINGO软件[M]，北京：清华大学出版社. [2]吴祈宗，运筹学[M] ，北京：机械工业出版社. [3]朱德通，最优化模型与实验/应用数学系列丛书[M] ，上海：同济大学出版社 [4]谷歌地图 https://www.wendangku.net/doc/a55348524.html,/maps?q=%E4%BB%CB%AE+%BB%AF%B7%CA&ie=gbk. 工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字 指导教师（签字）：教研室主任（签字）： 批准日期：年月日

运筹学在运输问题中的应用

运筹学在运输问题中的应用 关键字：运筹学运输 引言：运输是土木工程中经常遇到的问题，在工程造价中占较大的比例。如何使运输费用达到最小化，这就需要在施工前优化施工组织设计，将运筹学、网络技术等理论的设计方法应用到施工中，使得成本费用最经济。下面我们借鉴运筹学中的理论来解决运输问题。 一、运输路线最短问题。 根据运筹学中最短路径算法，寻找最短路线，就是从最后一段开始，用由后向前逐步递推的方法求卅各点到终点的最短路线，最终求得南起点到终点的最短路线。 某工程需要从点Sl运送500吨的建筑材料一个工地S1O。 首先．将图l的路线问题看成四个阶段的问题．南S1到S2，S3，S4为第一阶段；南S2，S3，S4到S5，S6，S7为第二阶段；南S5，S6，S7到S8。S9为第i阶段；南S8，S9到SIO为第四阶段。下面引进几个符号：

D(Sk,Sm)为Sk到Sm的距离，f(Sk)Sk到终点的最短距离。 (1)在第四阶段。 目前状态可以是S8或S9，可选择的下一状态是S1O，所以有 (2)在第i阶段。 目前状态可以是S5或S6或S7，可以选择的下一状态为S8或S9．所以有 (3)在第二阶段。 目前状态可以是S2或S3或S4，可以选择的下一状态为S5或S6或S7，所以有 (4)在第一阶段。 目前状态只有S1，可以选择的下一状态为S2或S3或S4．所以有 通过最短路径算法计算。可知从Sl(出发点)到S1O(终点)的最短运输路程为1080千米(权数路径距离)，所走的最优路线采用“顺序追踪法”来确定，最优运输路径：S1一S3一S6—S8—S10。 二、自卸车排队问题

在工程中经常遇到材料的运输和施工之间的关系，例如铺路的碎石、沥青的运输和路面的铺设之间的关系。如果运输工作进行得太快，而施工进程跟不上，就会有太多的原料来不及施工，导致运输设备和人员的闲置。相反，如果运输进度赶不上施工，就会出现施工设备和人员的闲置。 下面以高速公路高速公路沥青路面机械化施工系统为例子进行说明。高速公路沥青路面机械化施工系统，是指以沥青混合料拌和站、自卸汽车、沥青混凝土摊铺机、初压压路机、复压压路机、终压压路机等6种主体机械组成的沥青路面铺筑机群施工系统。沥青混凝土混合料作为纽带，将这6种机械共同联系在一起。准确、协调地工作，形成在“拌和一运料一摊铺一初压一复压一终压”过程中机械间的“相互影响、相互联系、相互制约”规律，即沥青路面施工系统机群工作规律。” 要研究沥青路面施工系统机群工作规律，首先应研究、分析机群施工系统的概率规律性及机械排队数量的目的，为研究拌和站、自卸汽车、摊铺机、初压压路机、复压压路机、终压压路机的运行工作情况作准备，为该系统资源优化配置(即机械的性能与数量优化组合)提供理论依据。其中重点是研究机械排队队长分布和机械排队数量。 1、系统流程分析 系统理想的工作情况是：当沥青混合料拌和站刚拌合好l车料时，就有l辆汽车到达拌和站处并装料；当摊铺机需要进料时，就有1辆汽车到达摊铺机处并立即卸料；沥青混凝土经摊铺机摊铺后，压路机立即分别予以压实。 拌和子系统是指由拌和站与运料汽车形成的系统。汽车总数是有限的。如只有M辆汽车，每辆汽车来到系统中接受服务后仍回到原来的总体，还会再来。由于拌和站的空间比较大，运输汽车是有限的，不会出现有运输车不能进入的情况，所以问题可以归结为单服务台等待制模型M/M/1/∞。这类问题的主要特征是系统空问是无限的，允许永远排队。 设：M为运料汽车总数量；L为平均队长；λn为拌和站处汽车平均到达率；μn为拌和站服务率，即单位时间内装车数量；W为平均逗留时间；Wq为平均等待时间。则系统状态流图见图1。