管理运筹学讲义第7讲运输问题.pptx

1
中山大学南方学院工商管理系
王甜源
第7讲 运输问题
2
运输问题及其数学模型
表上作业法
产销不平衡的运输问题
目 录
3
在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。
在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。
4
但是由于在运输问题的数学模型中，约束方程的系数矩阵具有特殊的结构。因此，存在一种比单纯形法更为简便的方法——表上作业法。
　　表上作业法通过定制的运输表确定最优调运方案，但其本质仍然是单纯形法，其主要步骤是：首先需要确定一个初始调运方案（初始基本可行解），然后检验现行调运方案（现行基本可行解）是否最优，若非最优，则需对现行调运方案（现行基本可行解）进行改进等几个阶段。只是表上作业法对单纯形法作了适当的修改，从而提高了计算的效率。
5
运输问题的一般提法是：某种物质（粮食、棉花、煤炭等）有m个产地 ，其产量是 ；有n个销地 ,其销量（或需求量）是 。
现在需要把这种物质从m个产地运送到n个销地。若从 运到
的单位运价为 。
又限定产销平衡，即 ，
问应如何制定调运方案可使总费用最小？
运输问题及其数学模型
6
上述已知条件可用下面的表格来表示。
销量
产量
销地
产地
7
如果用 代表从第ｉ产地运往第ｊ销地的物质单位数量
（i=1，2 m；j＝1，2 n），Ｚ为总运费，那么求解上述使总运费最小的运输问题。可以用下列数学模型描述：
从每一个产地运往各个销地的物
质数量之和等于该产地的产量
从各个产地运往每一个销地的物质数量之和等于该销地的销量
使总运费达到最小
运输量非负
8
运输问题的线性规划模型具有
特殊的结构，其约束方程组的系数
矩阵A具有如下形式：
m×n个决策变量，m＋n个约束条件。经证明：产销平衡的运输问题的非零变量 为m+n-1个。具体证明如下：
A =
1 1 1
1 1 1
1 1 1
1 1 1
m行
n行
1 1 1
1 1 1
9
A =
1 1 1
1 1 1
1 1 1
1 1 1
m行
n行
1 1 1
1 1 1
该矩阵的元素全部为0或1。每一列只有2个元素为1，其余为0。
若用 表示决策变量 的系数列向量，则在 中第i个和第
m＋j 个元素为1，其余为0。我们也可以用两个单位向量之和来
表示。 即：
其中 和 分别为第i个元素和第m＋j个元素为1的单位向量。
10
通过对运输问题的数学模型约束矩阵Ａ的特殊结构作进一步分析，还可以发现矩阵Ａ的秩为m＋n－1，即Ｒ(Ａ)＝m+n-1。
这是因为系数矩阵A的前m个行向量之和减去后n个行向量之
和恰好为零向量。即矩阵Ａ的m＋n个行向量线性相关。因此
Ｒ(Ａ)<m＋n。再将矩阵A的第2,3,…m+n行与
所对应的列的交叉处的元素构成一个m＋n－1阶子式。
1 1 1
1 1