第四章 运输问题

组合优化理论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分组构 …… 此处隐藏：2326字，全部文档内容请下载后查看。喜欢就下载吧 ……