运输问题数学建模

本章主要内容:

§3.1 运输问题及其数学建模

§3.2 表上作业法§3.3 产销不平衡的运输问题

§3.4 应用举例

教学要求： 1.掌握运输问题的数学模型、系数矩阵特殊形 式 2.掌握用西北角法、最小元素法求初始基可行 解 3.掌握回路、位势法求解过程和表上作业法求 解运输问题过程

一、 运输问题及其数学模型问题的提出: 在经济建设中，经常碰到物资调拨中的运输问题。 例如 煤、钢材、粮食、木材等物资，在全国都有若干 生产基地，分别将这些物资调到各消费基地去，应如 何制定调运方案，使总的运输费用最少？

1、运输问题的一般提法运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为 量 的运价为Cij。 这就是由多个产地供应多个销地的单品种物资运输问a i ( i 1,2 , , m )

;销地Bj的销

b j ( j 1 , 2 , , n )。从第i个产地向第j个销地运输每单位物资

题。问如何调运这些物资才能使总运费达到最小。

单位运价表销地 产地 A1 A2 ┇ Am 销量

B1 c11 c21 ┇ cm1 b1

B2 … Bn c12 … c1n c22 … c2n ┇ ┇ ┇

产量 a1 a2 ┇ am

cm2 … cmn b2 … bn

分两种情况来讨论：(1) a i i 1 m

bj 1

n

j

。即运输问题的总产量等于其总

销量，这样的运输问题称为产销平衡的运输问题。 (2) m

ai

i 1

bj 1

n

j

。即运输问题的总产量不等于总

销量，这样的运输问题称为产销不平衡的运输问题。

2、运输问题的数学模型若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下， 要求得总运费最小的调运方案，数学模型为：min z

ci 1 j 1

m

n

ij

x ij ( 3 1)

其中，ai和bj满足：

m x ij b j j 1 , 2 , , n i 1 n s . t . x ij a i i 1 , 2 , , m j 1 x 0 ij m nai j i 1 j 1

b 称为产销平衡条件。

将约束方程式展开可得 x1 1 x1 n x 21 x 2 n xm1 xmn x 21 xm1 x1 1 x1 2 x 22 xm 2 x1 n x2n xmn a1 a2 am b1 b2 bn

约束方程式中共mn个变量，m+n个约束。

上述模型是一个线性规划问题。但是其结构很特殊， 特点如下： 1.变量多(mn个),但结构简单。x 11 x 12 x 1 n x 21 x 22 x 2 n x m 1 x m 2 x mn 1 技术系数矩阵 A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 m 行 n行

该系数矩阵中每列只有两个元素为1,其余的都为

零。

2.m+n个约束中有一个是多余的(因为其间含有一个平衡关系 式 ) ai

b

j

所以R(A)=m+n-1,即解的mn个变量中基变量为m+n-1个。

二、 表上作业法运输问题仍然是线性规划问题，可以用线性规划 法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯形表太大；

2.若把技术系数矩阵A中的0迭代成非0,会使问题 更加复杂。以上两个原因使得我们不得不利用运输问题的 特点设计出它的特殊解法——表上作业法。

二、表上作业法(续)表上作业法，实质上还是单纯形法。其步骤如下： 1.确定一个初始可行调运方案。可以通过最小元素法、 西北角法、Vogel 法来完成； 2.检验当前可行方案是否最优，常用的方法有闭回路法 和位势法，用这两种方法计算出检验数，从而判别方 案是否最优； 3.方案调整，从当前方案出发寻找更好方案，常采用闭 回路法。

例3.1

某公司从三个产地A1、A2、A3 将物品运往四个

销地B1、B2、B3、B4,各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表3-4所示销地 产地 A1 A2 A3 销量 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 20(产销平 衡)

问应如何调运，可使得总运输费最小?

1、确定初始方案

即初始基本可行解的确定，与一般线性规划 问题不同，产销平衡运输问题总是存在可行解。 确定初始基本可行解的方法很多，一般希望方 法是既简便，又尽可能接近最优解。下面介绍两种 方法：最小元素法，西北角法、 Vogel 法

(1)最小元素法最小元素法的基本思想是优先满足单位运价最小的 供销业务。 首先找出运价最小的，并以最大限度满足其供销量 为原则确定供销业务。同样的方法反复进行直到确定了所 有的供销业务，得到一个完整的调运方案即初始基本可行

解为止。

方案表 销

运价表

产A1 A2 A3 需求

B1

B2

B3

B4

产量7 4

B13 1 7

B211 9

B3 32 2 10

B410 8 5

4 3 63 6 5

3

1 36

9 20

4