1、第三章 运输问题北京物资学院信息学院2017年 4月北京物资学院运筹学教学课件本章主要内容第一节 运输问题的数学模型及其特征第二节 运输问题的求解 表上作业法第三节 产销不平衡的运输问题及应用第一节 运输问题的数学模型及其特征1. 运输问题的定义2. 运输问题的数学模型3. 运输问题的特征1. 运输问题的定义例 1： 某集团新购进一批钢材，分别存储在三个仓库，现在要将这批钢材运到分布在各地的四个工厂。各仓库的库存量、各工厂的需求量以及从各仓库往各个工厂每运送一吨钢材所需的费用见下表，问如何调运才能使总运费降到最低？工厂B1工厂B2工厂B3工厂B4库存量仓库 A1 2 9 10 7 9仓库 A2
2、 1 3 4 2 5仓库 A3 8 4 2 5 7需求量 3 8 4 6运输问题： 有 m个供应点向 n个需求点供应某种物资，这 m个供应点 A1、 A2、 .A m的供应量分别为 a1、 a2、 .a m； n个需求点 B1、 B2、 .B n的需求量分别为 b1、 b2、 .b n； 已知从任一供应点 Ai向任一需求点 Bj运输一个单位物资的费用为cij。 问采取什么样的物资调运方案才能使总运费最省？B1 B2 Bn 供应量A1 c11 c12 c1n a1A2 c21 c22 c2n a2 Am cm1 cm2 cmn am需求量 b1 b2 bn2. 运输问题的数学模型运输问题的约束方
3、程组系数矩阵及特征1. 矩阵 A是一个 m+n行 mn列的矩阵，它的秩为 m+n-1。2. 运输问题应该有 m+n-1个基变量。3. 系数矩阵非常稀疏。4. xij的系数列向量为：m行n行3. 运输问题的特征特征 1： 运输问题一定有可行解；特征 2： 运输问题一定有最优解；特征 3： 运输问题每一组基对应 m+n-1个基变量；特征 4： 运输问题的 m+n-1个基变量构成的变量组不含闭回路 ；特征 5： 任意一个非基变量和 m+n-1个基变量组成的变量组中必定存在一条并且只存在唯一一条闭回路； 特征 6： 如果运输问题中的供应量和需求量都是整数，则任一基解中各变量的取值也都是整数。 闭回路定义：凡是能够排列成下列序列的一组变量的集合就称为运输问题的一个闭回路。并称集合中每一个变量为此闭回路的一个 顶点 ；称连接相邻两个变量（顶点）以及连接最后一个顶点和第一个顶点的线段为此闭回路的 边 。或B1 B2 B3 B4 B5A1A2A3A4 X45X41X31 X33X13 X15
