运筹学第三章运输问题引入l我们已经讨论了线性规划的一般形式以及求解的方法l但是在实际工作中，常常碰到很多线性规划问题，由于它们的约束条件变量的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的方法求解，从而可大量节约计算的时间和费用运输问题l一、运输问题的实例和数学模型l1、运输问题的实例l人们在从事生产活动中，不可避免地要进行物资调运工作如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小这样的问题称为运输问题l例3-1 现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）产粮地到需求地的运价（元/吨）如表3－1所示，问如何安排一个运输计划，使总的运输费用最少地区 产粮区B1B2B3B4产量A1326310A253828A341295 需要量578323运价表（元/T）表5-1产地销地A110A28A35B43B38B27B15354 2 3 1 6 8 232 9l例3-1【解】l设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需 求地的运量，这样得到下列运输问题的数学模型：l（1）使总的运输费用最小，则目标函数为：（4）运量应大于或等于零（非 负要求），即 （2）各产地粮的供应 量与运出量要平衡:（3）供给各需求地的 供给量与需求量的平衡 :请大家试着写出约束条件的系数矩阵运输问题l一、运输问题的实例和数学模型l例3-2 某食品公司经销的主要产品之一是糖果。
它下面设有三个加工厂，每天的糖果生产量分别为：A1-7t，A2-4t，A3-9t该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B1-3t，B2-6t，B3-5t，B4-6t已知从每个加工厂到各销售门市部每吨糖果的运价如表3-2所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少？运输问题l一、运输问题的实例和数学模型l例3-2门市部 加工厂B1B2B3B4供给量A13113107A219284A3741059销售量365620表3-2l练习：请大家自行列出例3-2描述的运输问题的线性规划模型约束条件的系数矩阵为：确定行数=？列数=？l通过实例概括问题：l性规划中我们研究的运输问题是：有某种物资需要调运，这种物资的计量单位可以是重量、包装单位或其他l已知有lm个地点可以供应该种物资（以后统称产地，用i=1，…,m表示）；这m个产地的可供量（称为产量）为a1，a2,…，am（通写为ai）；l有n个地点需要该种物资（以后统称销地，用j=1，…，n表示）；这n个销地的需要量（通称为销量）分别为b1，b2，…，bn（通写为bj）；l从第i个产地到第j个销地的单位物资运价为cij。
l怎样调运这些物品才能使总运费最小？l上面这些数据通常用产销平衡表5-3和单位运价表5-4来表示表3-3 产销平衡表销地 产地12…n产量1a12a2……mam销量b1b2…bn平衡?表3-4 单位运价表销地 产地12…n1c11c12…c1n2c21c22…c2n……………mcm1cm2…cmnl一、运输问题的实例和数学模型l2、运输问题的数学模型l如果用xij代表从第i个产地调运给第j个销地的物资 的单位数量，那么在产销平衡的条件下，使总的运费 支出最小，可以表示为数学形式：这就是运输问题的数学模 型，包含： m×n个变量 m+n个约束条件 约束条件的系数矩阵A有 m+n行m×n列所有销地的某物资的运输量之和=该物资在某产地的供给量（产量）某销地的所有物资的运输量之和=该物资在某销地的需求量（销售量）l一、运输问题的实例和数学模型l2、运输问题的数学模型l建立了运输问题的数学模型，我们发现运输问题的数学模型仍然是线性规划模型，但是与我们以前所学习的模型相比，又有它独有的一些特点l自己总结一下l那么如何来求解运输问题呢？l我们的思路与一般的线性规划问题的求解思路是一样的即：l寻找基及基解→判断是否最优→否→则继续寻找下一个基及基本解→重复直到最优解找到或确定无最优解。
l一、运输问题的实例和数学模型l2、运输问题的数学模型l从单纯形法中，我们了解到：寻找初始基及基本解，要从约束条件的系数矩阵出发，确定系数矩阵的秩，并在系数矩阵中确定满秩的单位子矩阵，从而确定初始基本解l运输问题也是线性规划问题，我们根据以往的经验来看看它的系数矩阵、系数矩阵的秩等有什么特点这就是运输问题的数学模 型，包含： m×n个变量 m+n个约束条件 约束条件的系数矩阵A有 m+n行m×n列:1 1 … 11 1 … 1 …1 1 … 1 1 1 … 11 1 … 1 …1 1 … 1 m行n行l运输问题模型的系数矩阵有m+n行、m×n列，那么系数矩阵的秩=？l因为m+n
证】因为产销平衡，即 ，将前m个约束方程两边相 加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约 束方程是相关的，系数矩阵【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变 量数为m+n-1所有的运输量之和=所有产地的供给量之和所有的运输量之和=所有销地的需求量之和中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式m 行n 行故r(A)=m+n－1,所以运输问题有m+n－1个基变量为了在mn个变量中找出m+n－1个变量作为一组基变量 ，就是要在A中找出m+n-1个线性无关的列向量m 行n-1 行l一、运输问题的实例和数学模型l为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量l在系数矩阵中如何表示列向量？l怎样才能在A中找出m+n-1个线性无关的列向量作为基呢？运输问题l一、运输问题的实例和数学模型l在系数矩阵中如何表示列向量？l运输问题约束系数矩阵中，变量xij对应的系数列向量可以表示为：• ei和em+j分别为第i个和第（m+j）个分量为1的单位向量。
mnl例如：3行4行l怎样才能在A中找出m+n-1个线性无关的列向量作为基呢？l我们将通过实例介绍寻找基的方法l二、表上作业法------运输问题的求解l上一节已经分析了，对于产销平衡问题，我们关心的量均可以表示在产销平衡表中因此可以建立基于产销平衡表的求解运输问题的方法—表上作业法运输问题l二、表上作业法------运输问题的求解l求解运输问题的思想和单纯形法完全类似，即首先确定一个初始基本可行解，然后根据最优性判别准则来检查这个基本可行解是不是最优的如果是则计算结束；如果不是，则进行换基，直至求出最优解为止l例3-2 用表上作业法求解l计算之前，首先列出这个问题的产销平衡表和单位运价表，如表3-5 和表3-6销地 产地B1B2B3B4产量A17 A24 A39 销量3656表3-5 产销平衡表l例3-2 用表上作业法求解l计算之前，首先列出这个问题的产销平衡表和单位运价表，如表3-5 和表3-6门市部 加工厂B1B2B3B4A1311310A21928A374105表3-6 单位运价表l也可以将产销平衡表和运价表合二为一销地产地产 量 311310 71928 474105 9销 量365620二、表上作业法-运输问题的求解l2.1 初始方案的给定l1、最小元素法 2、Vogel法 3、左上角法l2.2 最优性检验l1、闭回路法 2、位势法l2.3 调整调运方案l确定换入基的变量和换出基的变量二、表上作业法-运输问题的求解l2.1 初始方案的给定l方法很多，一般来说，方法要简单可行，并能给出较好的方案，减少迭代的次数。
l1、最小元素法 l2、Vogel法（元素差额法）l3、左上角法二、表上作业法-运输问题的求解l2.1 初始方案的给定l方法很多，一般来说，方法要简单可行，并能给出较好的方案，减少迭代的次数l1、最小元素法l基本思想：就近供应，即从单位运价表中最小的运价处开始确定供销关系，以此类推，一直到给出全部方案为止l以例3-2说明最小元素法的步骤：门市部 加工厂B1B2B3B4供给量A13113107A219284A3741059销售量365620例3-2 运输问题的产销平衡表/运价表销地 产地B1B2B3B4产量A1437 A2314A3639销量3656表3-7调运方案以上为例3-2 运输问题的初始基本解确定初始基中的基变量和初始基本解(以矩阵的方式写)销地 产地B1B2B3B4产量A1437 A2314A3639销量3656表3-7调运方案的说明称为有数字的格，对应运输问题 解中的基变量取值空格，对应解中的非基变量l练习：请大家在下表中用最小元素法确定调运方案销地产地产 量 311310 71928 474105 9销 量365620l因运输问题中基变量数一般为（m+n-1）个，所以 调运方案中有数字的格也为（m+n-1）个。
用最小 元素法给出初始方案时，一般调运方案表中每填 一个数后，划去该元素所在表中的一行或一列 但往往出现下述情况：l当选定最小元素后，发现该元素所在行的产地产 量等于所在列的销地的销量，这时在产销平衡表 上填写一个数，运价表上就要同时划去一行和一 列为了使调运方案中的有数字格仍为（m+n-1） 个，需要在同时划去的该行或该列的任一空格位 置补填一个0门市部 加工厂B1B2B3B4A131145 A27738 A312106销地 产地B1B2B3B4产量A17 A24A39销量3656 为了使有数字的格不减少，可以在空格（A1，B2）、 （A2，B2）、 （A3，B3）、 （A3，B4）中任选一格填写一个“0”同样，这个填写0的格被当作有数字的格看待0 00 00 00 03 36 64 41 16 6二、表上作业法-运输问题的求解l2.1 初始方案的给定l1、最小元素法：l用最小元素法给定初始方案只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远，有时为了节省某一处的运费，可能会导致其他处运费很大销地 产地B1B2B3B4产量A17 A24 A39 销量3656例3-2初始调运方案单位运 价B1B2B3B4A1311310 A21928 A3741053 36 64 41 13 33 3l2.1 初始方案的给定l2、Vogel法（元素差额法）l元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。
前一种按最小元素法求得，总运费是 Z1=10×8+5×2+15×1=105 后一种方案考虑到C11与C21之间的差额是8－2=6，先调运x21， 再是x22，其次是x12这时总运费 Z2=10×5+15×2+5×1=85