运输问题模型与性质

第三章运输问题

——特殊的线性规划&

运输问题的模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广

产销不平衡的运输问题转运问题指派问题1可编辑ppt

3.1运输问题模型与性质一、运输问题的数学模型

1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？2可编辑ppt单位根据具体问题选择确定。

表3-1有关信息单位运价销或运距地产地

B1B2…Bn

产量

A1A2┆Am

c11c12…c1nc21c22…c2n………cm1cm2…cmn

a1a2┆am

销量

b1b2…bn

3可编辑ppt

2、运输问题的数学模型设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：

4可编辑ppt同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：

总运费为：

5可编辑ppt运输问题的数学模型（3-1）6可编辑ppt二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行7可编辑ppt

矩阵的元素均为1或0；

每一列只有两个元素为1，其余元素均为0；

列向量Pij=(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。

将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。8可编辑ppt2.运输问题的基变量总数是m+n-1写出增广矩阵9可编辑ppt前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此

的秩小于m+n；？因此的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1由的第二至m+n行和前n列及对应的列交叉处元素构成m+n-1阶方阵D非奇异；？证明系数矩阵A及其增广矩阵的秩都是m+n-1

10可编辑ppt11可编辑ppt可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。12可编辑ppt定义3.1

凡是能排成(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。3.m+n-1个变量构成基变量的充要条件是它们不构成闭回路。13可编辑pptX11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X34例3-1

设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起来的顶点变量。14可编辑ppt练习3-1请给出闭回路和在表中的表示法。X11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X3415可编辑ppt练习3-2下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什么？（a）（b）（c）（d）（e）

表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；为什么？

表中的每一行和每一列由折线相连的闭回路的顶点只有两个；为什么？16可编辑ppt有关闭回路的一些重要结果

定理3-1设是一个闭回路，则该闭回路中的变量所对应的系数列向量具有下面的关系：注意：列向量Pij=(0,…,0,1,0,…,0,1,0,…0)T中两个元素1分别处于第i行和第m+j行，直接计算即可得到结果。

17可编辑ppt

定理的证明可借助定理3-1和高等代数中“向量组中，若部分向量线性相关，则整个向量组就线性相关”的定理得到。定理3-2

若变量组中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。18可编辑ppt定理3-3

不包含任何闭回路的变量组中必有孤立点。所谓孤立点是指在所在行或列中出现于该变量组中的唯一变量。可用反证法证明结论成立。定理3-4

r个变量对应的系数列向量线性无关充要条件是该变量组不包含闭回路。19可编辑ppt必要性的证明可考虑用反证法结合定理