运筹学学习(自制笔记)第3章 运输问题.docx

第3章运输问题

3.1标准运输问题及模型

3.1.1标准运输问题：某种物资有m个产地Ai（i=1,2,…,m）,产量分别为ai，另有n个销地Bj（j=1,2,…,n），销量（需求量）分别为bj，现在需要把这种物资从各个产地运送到各个销地，已知从Ai到Bj的单位运价(或运距)为cij，假定产量总数等于销量总数，即

问就如何组织调运，才能使总运费（或总运输量）最省?

3.1.2标准运输问题的有关信息表

单位运价销地

或运距

产地

B1

B2

…

Bn

产量

A1

c11

c12

…

c1n

a1

A2

c21

c22

…

c2n

a2

…

…

…

…

…

…

Am

cm1

cm2

…

cmn

am

3.1.3标准运输问题的数学模型

设xij为从产地Ai运到销地Bj的物资数量（i=1,2,…,m；j=1,2,…,n），由于从Ai运出的物资总量等于Ai的产量，运到的物资

总量等于的销量，得模型如下：

s.t.

xij≥0

且有

即满足产销平衡条件，故此模型描述的是产销平衡运输问题。3.1.4标准运输问题的特点

⑴平衡条件下的运输问题必有最优解

此问题是一个有m×n个变量，m+n个等型约束条件的线性规划最小化问题，由于目标函数不可能为负，故有下界存在是问题的一组可行解，因此一定有最优解。

既是线性规划问题，无疑可用单纯形法求解，但其数学模型自身结构有其特殊性，可以利用更简便的表上作业法求解。

⑴标准运输问题约束方程组的系数矩阵

运输问题是一个具有m×n个变量，m+n个等型约束条件的线性规划问题，问题的约束方程组的系数矩阵A是一个只有0和1两个数值的稀疏矩阵，xij对应的列Pij只有第i行和第m+j行为1，其余各

行皆为0。

⑴标准运输问题的基变量总数为m+n-1。

可以证明系数矩阵A和增广矩阵A′的秩为m+n-1。

增广矩阵A′的前m行相加之和减后n行相加之和等于0，说明m+n个行向量线性相关，A′和A的秩都小于m+n；另外，可以在A′中找出一个行列式的值不为0的m+n-1阶方阵D(取第二行至第n行的前n列及xi1所在的列，其中i=2，3，…m,得到一个副对角线上为两单位矩阵，上方为零矩阵的矩阵，显然，此矩阵满秩)，所以,

A′和A的秩为m+n-1。

⑴m+n-1个变量构成基变量的充要条件是它们不构成回路。

运输模型中能排列成｛xi1j1,xi1j2,xi2j2,xi2j3,Lxisjs,xisj1｝的变量组称为一个闭回路，其中i1,i2,…is互不相同，j1,j2,…js也互不相同，出现在组中的变量称为回路的顶点。

由于xij所对应的列向量Pij仅有第i行和m+j行为1，其余各行皆为0,所以很容易得出

Pi1j1-Pi1j2+Pi2j2-Pi2j3+L+Pisjs-Pisj1=0

所以，若变量组xi1j1,xi2j2,xi3j3,Lxisjs中若有一部分构成回路，则变量组所对应的系数列向量组必线性相关。

若变量组中不含任何闭回路，则变量组中至少有一变量的行标或列标只出现一次，即变量组中必有孤立点。

若有孤立点xirjr则变量组所对应的所有列向量中只有Pirjr的ir

行或第m+jr行为1，其余各列向量的第ir行或第m+jr行皆为0，变量组所对应的系数列向量组必线性无关。

故得结论

变量组对应的系数列向量线性无关变量组不含任何回路又

m+n-1个变量对应的系数列向量线性无关此m+n-1个变量构成基变量所以，m+n-1个变量构成基变量的充要条件是它们不构成回路。

3.2运输问题的表上作业法

表上作业法也是一种迭代法，它的基本思想是：先设法找出一个初始方案，然后对方案进行检验、调整，直到得出最优方案。这和单纯形法的思想完全一致，但是具体的作法则更加简捷。

3.2.1初始方案的确定

将决策变量xij填入运输信息表的cij所在表格（可将cij填入右下角而将xij填入中央），得到所谓的“作业表”，下面的操作均在作业表中进行。

确定初始方案就是找出一个初始基可行解，即定出m+n-1个变量并赋予它们非负的值，除这m+n-1个变量外，其余变量的值皆为0，且这m+n-1个变量所对应的系数列向量线性