运筹学课件第三章运输问题第三章运输问题一、学习目的与要求1、掌握表上作业法及其在产销平衡运输问题求解中的应用2、掌握产销不平衡运输问题求解方法二、课时 6学时第一节运输问题及其数学模型一、运输问题的数学模型单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。
假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？表中x ij i j ij i j如果运输问题的总产量等于其总销量，即有∑∑===nj jm i i ba 11则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。
产销平衡运输问题的数学模型如下：≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 11111ij m i jij nj iij m i n j ijij x nj b x mi a x t s x c z这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。
二、运输问题数学模型的特点1、运输问题有有限最优解，即必有最优基本可行解2、运输问题约束条件的系数矩阵A 的秩为(m+n-1)该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j对产销平衡的运输问题具有以下特点：(1)约束条件系数矩阵的元素等于0或1(2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。
此外，对于产销平衡问题，还有以下特点(3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和第二节用表上作业法求解运输问题解题步骤第1步：确定初始基本可行解。
