管理运筹学讲义 第3章 运输问题

第3章 运输问题学习要点 Sub title 1.掌握运输问题的数学模型、系数矩阵特殊形式 2.掌握用西北角法、最小元素法求初始基可行解 3.掌握位势法求解、牢固掌握三合一表格求解运输 问题过程

1

石家庄经济学院

管理科学与工程学院

第3章 运输问题

本章主要内容§3.1 运输问题及其数学模型 §3.2 表上作业法 §3.3 产销不平衡的运输问题 §3.4 应用举例

2

石家庄经济学院

管理科学与工程学院

§3.1 运输问题及其数学模型问题的提出一般的运输问题就是要解决把某种产品从

若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地 之间的运输单价的前提下，如何确定一个使得 总的运输费用最小的方案。回本章目录

3

石家庄经济学院

管理科学与工程学院

例 3.1

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

运往四个销地 B1 、 B2 、 B3 、 B4 ,各产地的产量、各 销地的销量和各产地运往各销地每件物品的运费 如下表所示销地 产地 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 (产销平衡)

问应如何调运，可使得总运输费最小?石家庄经济学院 管理科学与工程学院

解： 这是一个产销平衡的运输问题，设 xij 为从产 地Ai运往销地Bj的运输量(i = 1,2,3; j = 1,2,

3, 4)该运输问题的线性规划模型如下： Min f = 3x11+ 11x12+ 3x13+ 10x14+ x21+ 9x22 + 2x23+ 8x24+ 7x31+ 4x32+ 10x33+ 5x34

5

石家庄经济学院

管理科学与工程学院

s.t.

x11+ x12 + x13 + x14 = 7x21 + x22+ x23 + x24 = 4

x31 + x32+ x33 + x34 = 9x11 + x21 + x31 = 3

x12 + x22 + x32 = 6x13 + x23 + x33 = 5

x14 + x24 + x34 = 6xij ≥ 0 ( i = 1、2、3;j = 1、2、36 石家庄经济学院 管理科学与工程学院

其系数矩阵为 ： 1 0 0 A 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1

共有 m+n 行，分别表示产地和销地；有 mn 列分别表示各变量；每列只有两个 1,其余为 0 。7 石家庄经济学院 管理科学与工程学院

运输问题的一般提法是：设某种物资有m个产地和n个 ,2, , m) ; 销地。产地Ai的产量为 ai (i 1 销地Bj的销量为 b j ( j 1,2, , n) 。从第i个产地向 第j个销地运输每单位物资的运价为Cij,这就是由多个 产地供应多个销地的单品种物资运输问题。问如何调 运这些物资才能使总运费达到最小。

8

石家庄经济学院

管理科学与工程学院

表3-1 产销平衡表销地 产地 A1 A2 ┇ Am 销量 B1 x11 x21 ┇ xm1 b1 B2 Bn x12 x1n x22 x2n ┇ ┇ ┇ 产量 a1 a2 ┇ am

x

m2 xmn b2 bn

9

石家庄经济学院

管理科学与工程学院

表3-2 单位运价表销地 产地 A1 A2 ┇ Am 销量 B1 c11 c21 ┇ cm1 b1 B2 Bn c12 c1n c22 c2n ┇ ┇ ┇ 产量 a1 a2 ┇ am

cm2 cmn b2 bn

10

石家庄经济学院

管理科学与工程学院

表中的 xij (i 1,2 , m; j 1,2, , n) 表示由产地Ai 向销地Bj运输物资的数量(即运量)。在产销平衡表 3-1中，去掉最后一行和最后一列余下的部分，称为 一个调运方案，或简称为一个方案。或者将上述两个 表格合在一起，称为运输表(表3-3)。

11

石家庄经济学院

管理科学与工程学院

表3-3 运输表销地 产地

B1 x11 x21

A1 A2

c11

B2 x12 x22

c12c22

… … …

Bn x1n x2n

产量

c1n

c21cm1

a1 a2

c2 ncmn

Am销量

xm1b1

xm2b2

cm 2

… …

xmnbn

am

12

石家庄经济学院

管理科学与工程学院

下面分两种情况来讨论：(1) ai b j 。即运输问题的总产量等于其总i 1 j 1 m n

销量，这样的运输问题称为产销平衡的运输问题。 m n (2) a b 。即运输问题的总产量不等于总 i ji 1 j 1

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

我们重点讨论产销平衡的运输问题及其求解方法。 然后在此基础上讨论产销不平衡的运输问题应该 如何转化为产销平衡的运输问题。

13

石家庄经济学院

管理科学与工程学院

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

min z cij xiji 1 j 1

m

n

14

n xij ai i 1,2, , m j 1 m s.t. xij b j j 1,2, , n i 1 xij 0 石家庄经济学院

(3 1)

管理科学与工程学院

其中，ai和bj满足：

ai b ji 1 j 1

m

n

(3-2)

称为产销平衡条件。

15

石家庄经济学院

管理科学与工程学院

将(3-1)的结构约束加以整理，可知其系 数矩阵的结构比较松散，且特殊x11 x12 x1n x21 x22 x2 n xm1 xm 2 xmn u1 1 1 1 u2 1 1 1 um v1 1 1 v2 1 1 vn 1 1 16 石家庄经济学院

1 1 1 1 1 1

m行 n行

管理科学与工程学院