第四章 运输问题

组合优化理论Combinatorial Optimization Theory第四章 运输问题

第四章

运输问题

运输问题(Transportation Problem,简记为TP)是一类常见而且极其特殊的线性规划问题.它最早是从

物资调运工作中提出来的，是物流优化管理的重要的内容之一 。 加速物资流转 降低流通费用

从理论上讲，运输问题也可用单纯形法来求解， 但是由于运输问题数学模型具有特殊的结构，存在一

种比单纯形法更简便的计算方法 —— 表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计

算时间与计算费用.但表上作业法的实质仍是单纯形法

§1 运输问题及其数学模型

§1 运输问题及其数学模型一、运输问题的数学模型 设某种物资共有 m 个产地 A1,A2,…,Am,各 产地的产量分别是a1,a2 ,…,am;有n 个销地 B1,

B2,…,Bn ,各销地的销量分别为b1,b2,…,bn .假定从产地Ai(i =1,2,…,m)向销地Bj(j =1, 2,…,n)运输单位物资的运价是cij,问怎样调运才能 使总运费最小？

ai 0, bj 0, cij 0 (i 1,2, , m; j 1,2, , n)

第四章

运输问题ij

j=1,2,…,n) 的运量.1、产销平衡问题min z cij xiji 1 j 1ij

设 xij 表示产地 Ai 运往销地 Bj (i=1,2,…,m ; 运输表 Note : c 在左下角

即产地

a bi 1 i j 1销地

m

n

j

xij 在右上角

m

n

B1x11 c11

B2x12 c12 21

… …

Bnx1n c1n

产量 a1

s.t.

xj 1

n

ai bj

A1

i 1, 2, , mij

A2ミ Am

x21c21 c22

x22

…… …

x2nc2n

a2ミ am

xi 1

m

ミxm1 cm1

ミxm2 cm2

ミxmn cmn

j 1, 2, , n 销量

b1

b2

bn

xij 0 i 1, 2, , m; j 1, 2, , n

§1 运输问题及其数学模型

2、产销不平衡问题当

a bi 1 i j 1

m

n

j

当

a bi 1 i j 1

m

n

j

min z cij xiji 1 j 1ij

m

n

min z cij xiji 1 j 1ij

m

n

s.t.

xj 1

n

ai bj

s.t.

xj 1

n

ai bj

i 1, 2, , mij

i 1, 2, , mij

xi 1

m

xi 1

m

j 1, 2, , n

j 1, 2, , n

xij 0 i 1, 2, , m; j 1, 2, , n xij 0 i 1, 2, , m; j 1, 2, , n

第四章

运输问题

讨论产销平衡问题

二、运输问题数学模型的特点定理 1 平衡运输问题必有可行解，也必有最优解.证明

定理 2 平衡运输问题的约束方程系数矩阵 A 和增广矩 阵 A 的秩相等，且等于 m+n-1 . 即 R( A) R( A) m n 1定理2 说明： 定理 3 平衡运输问题的约束方程系数矩阵 A 的所有 基可行解包含 m+n-1个基变量. 各阶子式只取 0,1 或 -1 三个值. note

定理 4 如果平衡运输问题中的所有产量 ai 和销量 bj 都是整数，那么，它的任一基可行解都是整数解.

证明

Go on

定理 1 的证明 Proof : 则取n

设xij ij

a bi 1 i j 1

m

n

j

d

ai b jn

又

x j 1 j 1

d ai b j

(i 1, 2, , m; j 1, 2, , n)

显然有 xij 0 ,

ai d d bj

bj 1m i 1 i

n

j

ai (i 1, 2, , m) b j ( j 1, 2, , n)

x i 1 ij i 1

m

m

ai b j d

a d

所以 xij 0 ,是问题的一个可行解. 又因为 cij 0 (i 1, 2, , m; j 1, 2, , n) ,对于任一可行 解有目标函数值 z 0 ,对于求极小化问题，目标函数

值有下界，则必有最优解.

§1 运输问题及其数学模型 Note : 平衡运输问题有 条件，规模很大。x11 11 AA 11 x12 x1n x21 x22 x2n xm1 11 11 11 11 11 11 11 11 11 11 11 11 xm 2 xmn

Go back

m n 个变量， m n

R( A) m n 1

个约束

11 11

a1 a 2 11 am b1 b2 11 b n

m

n

定理 4 的证明 Proof : 设 x 是 Ax = b 的任一基可行解，其基变量为

xi1 j1 , xi2 j2 , , xim n 1 jm n 1xit jt det Bt det B

B 为对应的基矩阵，则

(t 1, 2, , m n 1)

其中 Bt 是用 b 中对应的 m+n-1元素替换 B 的第t 列

元素得到的矩阵.显然，由定理 3 及 ai 、 bj都是整数知，det Bt 是个xi j 整数， det B= 1 ,因此，t t

(t 1, 2, , m n 1)

都是整数. b a1 a2 am

b1 b2 bn

T

第四章

运输问题

闭回路的几何特征： 定义 1 凡是能排列成 xi1 j1 , xi1 j2 , xi2 j2 , xi2 j3 , , xis js , xis j1 1、每一个顶点格子都是 90°转角点； (其中 i1 , i2 , , is 互不相同，j1 , j2 , , js 互不相同) 2、每一行(或列)若有闭回路的顶点，则有两个 形式的变量集合，称为一个闭回路，其中诸变量称为 顶点； 这个闭回路的顶点 . 3、每两个顶点格子的连线都是水平的或垂直的； , x31 4、闭回路中顶点的个数必为偶数 如： 变量集合 x11, x12 , x22 , x24 , x34.变量集合

x11 , x14 , x44 , x45 , x35 , x32 , x22 , x21

B1

B2x12x22 x32 x42

B3x13x23 x33 x43

B4x14x24 x34 x44

B5x15x25 x35 x45

A1A2 A3

x11x21 x31 x41

A4

§1 运输问题及其数学模型

闭回路的代数性质：性质 1

xi1 j1 , xi1 j2 , xi2 j2 , xi2 j3 , , xis js , xis j1

构成闭回路的变量组对应的列向量组证明

pi1 j1 , pi1 j2 , pi2 j2 , pi2 j3 , , pis js , pis j1 必线性相关.性质 2 若变量组 xi1 j1 , xi2 j2 , , xir jr分组构成闭回路，则该变量组对应的列向量组

(*) 中有一个部

pi1 j1 , pi2 j2 , , pir jr量组一定

不包含闭回路.

是线性相关的.

推论 1 若变量组对应的列向量组线性无关，则该变Go on

性质 1 的证明 Proof : 由直接计算可知

pi1 j1 pi1 j2 pi2 j2 pi2 j3 pis js pis j1 0x11 x12 x1n x21 x 故该向量组线性相关 .22 x2n xm1 xm2 xmn 1 1 1 1 1 1 1 1 1 A 1 1 1 1 1 1 1 1 1

第四章定义 2

运输问题在变量组 xi1 j1 , xi2 j2 , , xir jr孤立点不会是 没有孤立点 ( *) 中，若有某 闭回路上的点

一个变量 xij 是它所在的行(第 i 行)或列(第 j 列) 中出现于(*)中的唯一变量，则称该变量 xij 是该变量 组的一个孤立点. 闭回路的特征 性质 3 定理 5 必有孤立点.

x11, x14 , x44 , x45 , x35 , x32 , x22 , x21 反证

若一变量组中不包含任何闭回路，则该变量组 变量组 (*) 对应的列向量组线性无关的充要证明

条件是该变量组中不包含任何闭回路.

定理 5 的证明

k: 0,从而( 1)变成 k2 pi2 j2 kr pir jr 0 (2) Proof 设变量组( *)对应的列向量 用反证法 1 组线性无关，但该变量组包含一个以其中某些变量为顶 但 xi2 j2 , xi3 j3 , xir jr 仍不包含闭回路，其中还有孤立点,点的闭回路， 则由性质 k 2= 知，这些变量对应的列向量必 与前面类似分析可证 2 0. 同理得 k3 = k4 =…= kr = 0 线性相关，与假设矛盾. 这就证明了向量组(*)线性无关.

设有一组数 k1 , k2 , , kr

使得

k1 pi1 j1 k2 pi2 j2 kr pir jr 0 (1) 一变量如何？可知其中必有孤立点， 不妨设 xi j 为孤立点，1 1

在第 j1列上的唯

由于变量组(*)中不包含任何闭回路，由性质 3

()在第 *) 对应的列向量组线性无关的充要 又不妨设 i1行上唯一的变量，这时由pij i j 是(* 定理 5 x 变量组1 1

条件是该变量组中不包含任何闭回路 的特征，( 1)的左端第i1个分量和为k. 1,而右端为0,

§1 运输问题及其数学模型 推论 2 平衡运输问题中的一组 m + n - 1 个变量 xi1 j1 , xi2 j2 , , xis js (s m n 1) 能构成基变量的充要条件是它不包含任何闭回路. 该推论给出了运输问题的基可行解中基变量的一 个基本特征：基变量组不含闭回路. 这就是基可行解 在表上的一个表现，利用它来判断 m + n – 1 个变量 是否构成基变量组，就看它是否包含闭回路. 这种方法简便易行，它比直接判断这些变量对应 的列向量是否线性无关要简便得多. 利用基变量的这个特征，将可以导出求平衡运输 问题的初始基可行解的一些简便方法.

§2 运输问题的表上作业法

§2 运输问题的表上作业法表上作业法(又称运输单纯形

法)是根据单纯形

法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法. 主要步骤： 1、求一个初始调运方案(初始基可行解); 2、判别当前方案是否为最优，若是则迭代停止，否则 转下一步； 3、改进当前方案，得到新的方案(新的基可行解), 再返回 2 。