运筹学--第三章 运输问题.ppt

1、运筹学,第三章,运输问题,引入,我们已经讨论了线性规划的一般形式以及求解的方法。 但是在实际工作中，常常碰到很多线性规划问题，由于它们的约束条件变量的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的方法求解，从而可大量节约计算的时间和费用。,运输问题,一、运输问题的实例和数学模型 1、运输问题的实例 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,例3-1 现有A1，A2，A3三个产粮区，可供应粮

2、食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表31所示，问如何安排一个运输计划，使总的运输费用最少。,运价表（元/T）,表5-1,例3-1【解】 设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型： （1）使总的运输费用最小，则目标函数为：,（4）运量应大于或等于零（非负要求），即,（2）各产地粮的供应量与运出量要平衡:,（3）供给各需求地的供给量与需求量的平衡:,请大家试着写出约束条件的系数矩阵,运输问题,一、运输问题的实例和数学模

3、型 例3-2 某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为：A1-7t，A2-4t，A3-9t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B1-3t，B2-6t，B3-5t，B4-6t。已知从每个加工厂到各销售门市部每吨糖果的运价如表3-2所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少？,运输问题,一、运输问题的实例和数学模型 例3-2,表3-2,练习：请大家自行列出例3-2描述的运输问题的线性规划模型。,约束条件的系数矩阵为：,确定行数=？列数=？,通过实例概括问题： 在线性规划中我们研究的运输

4、问题是：有某种物资需要调运，这种物资的计量单位可以是重量、包装单位或其他。 已知有 m个地点可以供应该种物资（以后统称产地，用i=1，,m表示）；这m个产地的可供量（称为产量）为a1，a2,，am（通写为ai）； 有n个地点需要该种物资（以后统称销地，用j=1，n表示）；这n个销地的需要量（通称为销量）分别为b1，b2，bn（通写为bj）； 从第i个产地到第j个销地的单位物资运价为cij。 怎样调运这些物品才能使总运费最小？ 上面这些数据通常用产销平衡表5-3和单位运价表5-4来表示。,表3-3 产销平衡表,表3-4 单位运价表,一、运输问题的实例和数学模型 2、运输问题的数学模型 如果用xi

5、j代表从第i个产地调运给第j个销地的物资的单位数量，那么在产销平衡的条件下，使总的运费支出最小，可以表示为数学形式：,这就是运输问题的数学模型，包含： mn个变量 m+n个约束条件 约束条件的系数矩阵A有 m+n行mn列,所有销地的某物资的运输量之和=该物资在某产地的供给量（产量）,某销地的所有物资的运输量之和=该物资在某销地的需求量（销售量）,一、运输问题的实例和数学模型 2、运输问题的数学模型 建立了运输问题的数学模型，我们发现运输问题的数学模型仍然是线性规划模型，但是与我们以前所学习的模型相比，又有它独有的一些特点。 自己总结一下。,那么如何来求解运输问题呢？ 我们的思路与一般的线性规划

6、问题的求解思路是一样的。即： 寻找基及基解判断是否最优否则继续寻找下一个基及基本解重复直到最优解找到或确定无最优解。,一、运输问题的实例和数学模型 2、运输问题的数学模型 从单纯形法中，我们了解到：寻找初始基及基本解，要从约束条件的系数矩阵出发，确定系数矩阵的秩，并在系数矩阵中确定满秩的单位子矩阵，从而确定初始基本解。 运输问题也是线性规划问题，我们根据以往的经验来看看它的系数矩阵、系数矩阵的秩等有什么特点。,这就是运输问题的数学模型，包含： mn个变量 m+n个约束条件 约束条件的系数矩阵A有 m+n行mn列:,运输问题模型的系数矩阵有m+n行、mn列，那么系数矩阵的秩=？ 因为m+nmn，

7、所以系数矩阵的秩应m+n 同时，因为有 ，所以系数矩阵中线性 独立的列向量的最大个数为（m+n-1）个，即运输问题系数矩阵的秩为（m+n-1），运输问题的解中的基变量数一般为（m+n-1）个。 如何理解？ 我们通过一个定理的证明和实例3-2来理解。,【证】因为产销平衡，即 ，将前m个约束方程两边相加得,再将后n个约束相加得,显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵,【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,所有的运输量之和=所有产地的供给量之和,所有的运输量之和=所有销地的需求量之和,中任意m+n阶子式等于零，取第一行

8、到m+n1行与 对应的列（共m+n-1列）组成的m+n1阶子式,m 行,n 行,故r(A)=m+n1,所以运输问题有m+n1个基变量。,为了在mn个变量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量。,m 行,n-1 行,一、运输问题的实例和数学模型 为了在mn个变量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量。 在系数矩阵中如何表示列向量？ 怎样才能在A中找出m+n-1个线性无关的列向量作为基呢？,运输问题,一、运输问题的实例和数学模型 在系数矩阵中如何表示列向量？ 运输问题约束系数矩阵中，变量xij对应的系数列向量可以表

9、示为：,ei和em+j分别为第i个和第（m+j）个分量为1的单位向量。,例如：,3行,4行,怎样才能在A中找出m+n-1个线性无关的列向量作为基呢？ 我们将通过实例介绍寻找基的方法。 二、表上作业法-运输问题的求解 上一节已经分析了，对于产销平衡问题，我们关心的量均可以表示在产销平衡表中。因此可以建立基于产销平衡表的求解运输问题的方法表上作业法。,运输问题,二、表上作业法-运输问题的求解 求解运输问题的思想和单纯形法完全类似，即首先确定一个初始基本可行解，然后根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束；如果不是，则进行换基，直至求出最优解为止。,例3-2 用表上作业法

10、求解 计算之前，首先列出这个问题的产销平衡表和单位运价表，如表3-5 和表3-6,表3-5 产销平衡表,例3-2 用表上作业法求解 计算之前，首先列出这个问题的产销平衡表和单位运价表，如表3-5 和表3-6,表3-6 单位运价表,也可以将产销平衡表和运价表合二为一,二、表上作业法-运输问题的求解,2.1 初始方案的给定 1、最小元素法 2、Vogel法 3、左上角法 2.2 最优性检验 1、闭回路法 2、位势法 2.3 调整调运方案 确定换入基的变量和换出基的变量,二、表上作业法-运输问题的求解,2.1 初始方案的给定 方法很多，一般来说，方法要简单可行，并能给出较好的方案，减少迭代的次数。

11、1、最小元素法 2、Vogel法（元素差额法） 3、左上角法,二、表上作业法-运输问题的求解,2.1 初始方案的给定 方法很多，一般来说，方法要简单可行，并能给出较好的方案，减少迭代的次数。 1、最小元素法 基本思想：就近供应，即从单位运价表中最小的运价处开始确定供销关系，以此类推，一直到给出全部方案为止。 以例3-2说明最小元素法的步骤：,例3-2 运输问题的产销平衡表/运价表,表3-7,调运方案,以上为例3-2 运输问题的初始基本解 确定初始基中的基变量和初始基本解(以矩阵的方式写),表3-7,调运方案的说明,称为有数字的格，对应运输问题解中的基变量取值,空格，对应解中的非基变量,练习：请

12、大家在下表中用最小元素法确定调运方案。,因运输问题中基变量数一般为（m+n-1）个，所以调运方案中有数字的格也为（m+n-1）个。用最小元素法给出初始方案时，一般调运方案表中每填一个数后，划去该元素所在表中的一行或一列。但往往出现下述情况： 当选定最小元素后，发现该元素所在行的产地产量等于所在列的销地的销量，这时在产销平衡表上填写一个数，运价表上就要同时划去一行和一列。为了使调运方案中的有数字格仍为（m+n-1）个，需要在同时划去的该行或该列的任一空格位置补填一个0。,为了使有数字的格不减少，可以在空格（A1，B2）、 （A2，B2）、 （A3，B3）、 （A3，B4）中任选一格填写一个“0”

13、。同样，这个填写0的格被当作有数字的格看待。,0,0,0,0,3,6,4,1,6,二、表上作业法-运输问题的求解,2.1 初始方案的给定 1、最小元素法： 用最小元素法给定初始方案只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远，有时为了节省某一处的运费，可能会导致其他处运费很大。,例3-2,初始调运方案,3,6,4,1,3,3,2.1 初始方案的给定 2、Vogel法（元素差额法） 元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。,前一种按最小元素法求得，总运费是 Z1=108+52

14、+151=105 后一种方案考虑到C11与C21之间的差额是82=6，先调运x21，再是x22，其次是x12这时总运费 Z2=105+152+51=85Z1。,实例： 从表3-6运价表中找出每行与每列最小两个元素之差，分别列于表的右端与下端，见表5-8,表3-6,再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列。重复！,表3-8,6,再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列。重复！,Vogel法实现的初始调运方案,最小元素法

15、实现的初始调运方案,请写出两种求得的初始基及基本解、目标函数值？,最小元素法实现的初始调运方案,3,1,7,11,9,4,3,2,10,10,8,5,3,1,7,11,9,4,3,2,10,10,8,5,Vogel法实现的初始调运方案,二、表上作业法-运输问题的求解,2.1 初始方案的给定 2、Vogel法 一般当产销地的数量不多时，Vogel法给出的初始方案有时就是最优方案，所以Vogel法有时就用作求运输问题最优方案的近似解。,练习： 用元素差额法求表所示运输问题的初始基本可行解。,初始调运方案,【 】,5,初始调运方案,20,0,【 】,20,0,【 】,10,20,5,初始调运方案,初

16、始基本可行解为,总运费Z=108+201+52+208=270。,2.1 初始方案的给定 1、最小元素法 2、Vogel法（元素差额法） 3、 左上角法 左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕。 当出现同时分配完一行和一列时，仍然应在打“”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n1 。,例3-4 用左上角法求例3-3中的初始基本可行解,30,30,15,15,10,二、表上作业法-运输问题的求解,2.1 初始方案的给定 4、闭回路相关概念 （1）闭回路定义 凡是能排列成 形式

17、的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点。,（其中 互不相同， 互不相同）,凡是能排列成,（其中 互不相同， 互不相同）,形式的变量集合，称为一个闭回路，其中诸变量称为 这个闭回路的顶点.,如：,变量集合,变量集合,2.1 初始方案的给定 3、闭回路相关概念 （1）闭回路定义 闭回路的几何特征： 每一个顶点格子都是 90转角点； 每一行（或列）若有闭回路的顶点，则有两个顶点； 每两个顶点格子的连线都是水平的或垂直的； 闭回路中顶点的个数必为偶数。,（2）孤立点:若变量组 中某一变量是它所在行或所在列中出现的唯一变量，则称这个变量是关于变量组的孤立点。 （3）闭回路与基变量之间

18、的关系是什么？ 实例3-2中基变量与基变量作为顶点的闭回路的关系如何？,定理：m+n-1个变量构成的基变量的充分必要条件：它不包含任何闭回路。 定理对我们的启示： 告诉了一个求基变量的简单方法，同时也可以判断一组基变量是否可以作为某个运输问题的基变量。 这种方法直接在运价表中进行，不需要在系数矩阵A中去寻找，从而给运输问题求初始基本解带来极大的方便。,例如，m=3,n=4，将xij与运价Cij放在同一张表中，如表所示。,运输问题的基变量个数=？,例如，m=3,n=4，将xij与运价Cij放在同一张表中，如表所示。,6个,变量组中能否构成一个基？,变量组中能否构成一个基？,变量组中能否构成一个基

19、？,二、表上作业法-运输问题的求解,2.1 初始方案的给定 2.2 最优性检验-用检验数来判断 最小元素法或Vogel法给出的是一个运输问题的基可行解，需通过最优性检验判别该解的目标函数值是否最优，当为否定时，应进行调整得到优化。 1、闭回路法求检验数 2、位势法求检验数 假设xij的检验数为ij,二、表上作业法-运输问题的求解,2.2 最优性检验 1、闭回路法求检验数 构建闭回路的目的是要计算解中非基变量（对应空格）的检验数。 求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以

20、这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。,实例3-2的最优性检验,例3-2 初始基的检验数表,练习：求下列运输问题的一个初始基、基本解及其检验数。,70 50 20,10 60 40 30,2.2 最优性检验 1、闭回路法求检验数 2、位势法求检验数 要判断一个方案是否最优，需要通过每一个空格寻找闭回路，以及根据闭回路求出每个空格的检验数。当一个运输问题的产地和销地数很多时，用这个方法计算检验数的工作量十分繁重。 下面以实例3-2介绍位势法！,例3-2 运输问题的数学模型,请写出它的对偶形式,练习：用位势法求出初始基本可行解的检验数。,10 60 40 30,2.1 初始

21、方案的给定 2.2 最优性检验-用检验数来判断 2.3 调整运量,前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是: (下页),2.3调整运量,第一步：确定进基变量,第二步：确定出基变量 在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。,第三步：调整运量 在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。,例3-2 初始基本解,例3-2 初始基的检验数

22、表,总结归纳： 用表上作业法求解运输问题的步骤如图表示：,分析实际问题 列出产销平衡表 及单位运价表,确定初始调运方案 （最小元素法 或Vogel法）,求检验数 （闭回路法或位势法）,所有检验数0,得到最优方案 算出总的运价,是,否,找出绝对值最大的负 检验数用闭回路调整 ，得出新的调运方案,三、产销不平衡的运输问题及其应用,前面讲的表上作业法的计算和理论，都是以产销平衡为前提的，（即 ） 但实际问题中产销往往是不平衡的，为了应用表上作业法计算，就需要把产销不平衡的问题化成产销平衡的问题。,三、产销不平衡的运输问题及其应用,1、当产量大于销量 时，运输问题的数学模型可写为：,产销平衡数学模型,

23、三、产销不平衡的运输问题及其应用,例3-3 设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销地需要该种物资，销量分别是2t、3t、4t、6t，又知各产销地之间的单位运价表，试决定总运费最少的调运方案。,表3-3 表1运价表 单位：元/t,例3-2 求解 【解】 产地总产量为19t，销地总销量为15t，所以这是一个产大于销的运输问题。按前述方法转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见表2和表1。,例3-3表2 产销平衡表,例3-2 求解 【解】 产地总产量为19t，销地总销量为15t，所以这是一个产大于销的运输问题。按前述方法转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见表3。,例3-3表3,例3-2 求解 【解】 对表可以用表上作业法计算出最优方案，如表4所示。,例3-3表4 调运方案,三、产销不平衡的运输问题及其应用,2、当销量