第四章 运输问题.ppt

第四章运输问题
组合优化理论
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,问怎样调运才能
使总运费最小?
一、运输问题的数学模型
第四章运输问题
销地
产地
B1
B2
…
Bn
产量
A1
c11
c21
…
c1n
a1
A2
c21
c22
…
c2n
a2
ミ
ミ
ミ
ミ
ミ
Am
cm1
cm2
…
cmn
am
销量
b1
b2
…
bn
运输表
1、产销平衡问题
即
设 xij 表示产地 Ai 运往销地 Bj (i=1,2,…,m;
j=1,2,…,n) 的运量.
销地
产地
B1
B2
…
Bn
产量
A1
x11
c11
x12
c12
…
x1n
c1n
a1
A2
x21
c21
x22
c22
…
x2n
c2n
a2
ミ
ミ
ミ
ミ
ミ
Am
xm1
cm1
xm2
cm2
…
xmn
cmn
am
销量
b1
b2
…
bn
Note : cij 在左下角
xij 在右上角
§1 运输问题及其数学模型
2、产销不平衡问题
当
当
第四章运输问题
二、运输问题数学模型的特点
讨论产销平衡问题
定理 1 平衡运输问题必有可行解,也必有最优解.
证明
定理 2 平衡运输问题的约束方程系数矩阵 A 和增广矩
阵的秩相等,且等于 m+n-1 . 即
定理2 说明:
基可行解包含m+n-1个基变量.
定理 3 平衡运输问题的约束方程系数矩阵 A 的所有
各阶子式只取 0,1 或-1 三个值.
定理 4 如果平衡运输问题中的所有产量 ai 和销量 bj
都是整数,那么,它的任一基可行解都是整数解.
证明
note
Go on
定理 1 的证明
Proof :
则取
显然有,
又
所以,是问题的一个可行解.
又因为,对于任一可行
解有目标函数值,对于求极小化问题,目标函数
值有下界,则必有最优解.
§1 运输问题及其数学模型
Note :
平衡运输问题有个变量, 个约束
条件,规模很大。
Go back
定理 4 的证明
Proof :
设 x 是 Ax = b 的任一基可行解,
B 为对应的基矩阵,则
其中 Bt 是用 b 中对应的 m+n-1元素替换 B 的第t 列
元素得到的矩阵.
显然,由定理 3 及 ai 、 bj都是整数知,det Bt 是个
整数, det B= ,因此,
都是整数.
其基变量为
第四章运输问题
定义 1
凡是能排列成
(其中互不相同, 互不相同)
形式的变量集合,称为一个闭回路,其中诸变量称为
这个闭回路的顶点.
B1
B2
B3
B4
B5
A1
x11
x12
x13
x14
x15
A2
x21
x22
x23
x24
x25
A3
x31
x32
x33
x34
x35
A4
x41
x42
x43
x44
x45
如:
变量集合
变量集合
2、每一行(或列)若有闭回路的顶点,则有两个
顶点;
3、每两个顶点格子的连线都是水平的或垂直的;
4、闭回路中顶点的个数必为偶数.
闭回路的几何特征:
1、每一个顶点格子都是 90°转角点;