运筹学课件第三章运输问题

精品文档

第三章运输问题

一、学习目的与要求

1、掌握表上作业法及其在产销平衡运输问题求解中的应用

2、掌握产销不平衡运输问题求解方法

二、课时 6学时

第一节 运输问题及其数学模型

一、运输问题的数学模型

单一品种运输问题的典型情况：设某种物品有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 产量 实用文档

精品文档

产地 c11 x11 c12 x12 c1n a1 x1n A1 c21 x21 c22 x22 c2n a2 x2n A2 … c11 x11 cm c12 x12 cm c1n … x1n cm 1 2 n Am am xm1 销量 b1 Xm2 b2 xmn bn … 表中xij为由产地Ai到销地Bj的物品数量，cij表示产地Ai到销地Bj的单位运价。

如果运输问题的总产量等于其总销量，即有

mn?a??bii?1j?1j

则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。

产销平衡运输问题的数学模型如下：

实用文档

精品文档

mn?1

minz???cijxij

i?1j?1

?n

??xij?ai

?1?jm?

s.t.??xij?bj

?i?1

?xij?0??

i?1,2,...,m

j?1,2,...,n

这就是运输问题的数学模型，它包含m×n个变量，(n十m)个约束方程．其系数矩阵的结构比较松散，且特殊。

二、运输问题数学模型的特点

1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A的秩为(m+n-1)

该系数矩陈中对应于变量xij的系数向量pij，其分量中除第i个和第m十j个为

实用文档