3第三章_运输问题.ppt

《3第三章_运输问题.ppt》由会员分享，可在线阅读，更多相关《3第三章_运输问题.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 运输问题运输问题 运输问题的数学建模及表上作业法运输问题的数学建模及表上作业法不平衡问题的数学处理不平衡问题的数学处理3.1、运输问题的数学模型、运输问题的数学模型 在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资,在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：运输问题：假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,m；有n个销售地，用Bj表示，j=1,2,n；产地的产量和销售地的销售量分别为ai,i=1,2,m和bj，j=1,2

2、,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如表3.1。表3.1 销地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bn要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，即 则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。下面建立在产销平衡情况下的运输问题的数学模型。解:假设 xij 表示从Ai到 Bj 的运量,则所求的数学模型为:在该模型中，目标函数表示运输总费用，要求其极小化；第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往

3、销地的物品数量之和等于该产地的产量；第三个约束条件表示变量的非负条件。设有三个电视机厂。生产同一种彩色电视机，日设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：生产能力分别是：50，60，50，供应四个门市，供应四个门市部，日销售量分别是：部，日销售量分别是：40，40，60，20台，从台，从各分厂运往个门市部的运费如表各分厂运往个门市部的运费如表1-23所示，试所示，试安排一个运费最低的运输计划。安排一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40406020供求平衡的运输问题：供：供求平衡的运输问题：供：50+60+50

4、=160 需：需：40+40+60+20=160数学模型设有三个电视机厂。生产同一种彩色电视机，日设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：生产能力分别是：50，80，50，供应四个门市，供应四个门市部，日销售量分别是：部，日销售量分别是：40，40，60，20台，从台，从各分厂运往个门市部的运费如表所示，试安排各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。一个运费最低的运输计划。门市部工厂1234供应12397612359796711508050需求40406020供应量供应量180，需求量，需求量160，供需不平衡，供大于求。，供需不平衡，供大于求。数学模

5、型？供大于求的情况数学模型特点与处理办法特点处理办法：设置一个虚销售点n+1，使且 ，因而化为平衡问题。设有三个电视机厂。生产同一种彩色电视机，日设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：生产能力分别是：50，80，50，供应四个门市，供应四个门市部，日销售量分别是：部，日销售量分别是：40，40，60，20台，从台，从各分厂运往个门市部的运费如表所示，试安排各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。一个运费最低的运输计划。门市部工厂12345供应总计12397612359796711000508050需求总计4040602020供应量180，需求量180

6、，供需平衡。设有三个电视机厂。生产同一种彩色电视机，日设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：生产能力分别是：50，60，50，供应四个门市，供应四个门市部，日销售量分别是：部，日销售量分别是：40，70，60，20台，从台，从各分厂运往个门市部的运费如表所示，试安排各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。一个运费最低的运输计划。门市部工厂1234供应总计12397612359796711506050需求总计40706020供应量供应量160，需求量，需求量190，供需不平衡，需求大于供应。，供需不平衡，需求大于供应。求大于供数学模型特点与处理办法特点

7、处理办法：增加一个虚产地m+1，使且 ，化为平衡问题。设有三个电视机厂。生产同一种彩色电视机，日设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：生产能力分别是：50，60，50，供应四个门市，供应四个门市部，日销售量分别是：部，日销售量分别是：40，70，60，20台，从台，从各分厂运往个门市部的运费如表所示，试安排各分厂运往个门市部的运费如表所示，试安排一个运费最低的运输计划。一个运费最低的运输计划。门市部门市部工厂工厂1234供应总计供应总计123497601235097906711050605030需求总计需求总计40706020供应量供应量190，需求量，需求量190，供需平

8、衡。，供需平衡。n这就是运输问题的数学模型，它包含这就是运输问题的数学模型，它包含m n个变量，个变量，m+n个约束条件，是一个线性规划问题。个约束条件，是一个线性规划问题。n如果用单纯形法求解，首先应在每个约束条件上如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量加入一个人工变量(以便求出初始基可行解以便求出初始基可行解)。即使。即使是是m=4，n=5这样的简单问题这样的简单问题,变量个数就有变量个数就有29个个之多，利用单纯形法进行计算是非常复杂的。之多，利用单纯形法进行计算是非常复杂的。n有必要针对运输问题的某些特点，来寻求更为简有必要针对运输问题的某些特点，来寻求更为简单方便

9、的求解方法。单方便的求解方法。3.2、表上作业法、表上作业法 1、表上作业法的基本概念与重要结论表上作业法的基本概念与重要结论针对运输问题的数学模型结构的特殊性，它的约针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特点：束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素等于）在该矩阵中，它的元素等于0或或1；（2）每列只有两个元素为）每列只有两个元素为1，其余都是，其余都是0；（3）对应于每一个变量，在前）对应于每一个变量，在前m个约束方程中只个约束方程中只出现一次，在后出现一次，在后n个约束方程中也只出现一次。根个约束方程中也只出现一次。根据这个特点，在单纯形法

10、的基础上，下面设计出据这个特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题的方法，称为表上作一种专门用来求解运输问题的方法，称为表上作业法。业法。运输问题的解代表着一个运输方案，其中每一个变运输问题的解代表着一个运输方案，其中每一个变量量xij的值表示由的值表示由Ai调运数量为调运数量为xij的物品给的物品给Bj。当用单纯形法进行求解时，当用单纯形法进行求解时，首先首先应当知道它的基变应当知道它的基变量的个数；量的个数；其次其次，要知道这样一组基变量应当是由，要知道这样一组基变量应当是由哪些变量来组成。哪些变量来组成。运输问题的解运输问题的解X必须要满足模型中的所有约束条件；必须要

11、满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性基变量对应的约束方程组的系数列向量必须是线性无关的；解中基变量应由无关的；解中基变量应由 m+n-1个变量组成个变量组成(即基变即基变量的个数量的个数=产地个数产地个数+销售地个数销售地个数 1)，原因是在，原因是在运输问题中虽然有运输问题中虽然有m+n个约束条件，个约束条件，但由于总产量但由于总产量等于总销量等于总销量，有，有m+n-1个约束条件是线性独立的。个约束条件是线性独立的。怎样的怎样的 m+n-1个变量会构成一组基变量？个变量会构成一组基变量？需要引入一些基本概念，通过对这些基本概念的需要引入一些基本概念，通过对

12、这些基本概念的分析和讨论，结合单纯形算法的基本结果，便可分析和讨论，结合单纯形算法的基本结果，便可得出所需要的结论。得出所需要的结论。凡是能排成 互不相同，且 形成的变量的集合称之为一个闭回路。而把出现形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶点。在闭回路中的变量称为这个闭回路的顶点。例例3.1 设设 m=3，n=4，如表，如表3.2所示。所示。销地产地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21 构成一个闭回路。构成一个闭回路。这里有：这里有：i1=1，i2=3，i3=2；j1=1，j2=2，

13、j3=4。若把闭回路的顶点在表中画出，并且把相邻两个。若把闭回路的顶点在表中画出，并且把相邻两个变量用一条直线相连（今后就称这些直线为闭回路变量用一条直线相连（今后就称这些直线为闭回路的边）。而表的边）。而表3.3，即顶点为，即顶点为 x12、x32、x34、x14 和表和表3.4，即顶点为，即顶点为 x11、x12、x22、x24、x34、x31 也分别构成两个闭回路。也分别构成两个闭回路。例3.1 设 m=3，n=4，如表3.2所示。表3.3 销地产地B1B2B3B4A1x12x14A2A3x32x34表3.4 销地产地B1B2B3B4A1x11x12A2x22x24A3x31x34从上面

14、的例子中不难看出，如果把一个闭回路的所有从上面的例子中不难看出，如果把一个闭回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一连接起来，就可以得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。条边或者是水平的，或者是垂直的。定理定理3.1：m+n-1个变量个变量 构成基变量的充分必要条件是构成基变量的充分必要条件是它不包含有任何闭回它不包含有任何闭回路路。该定理给出了该定理给出了运输问题基运输问题基的一个重要特征，因的一个重要特征，因为利用它可以判断为利用它可以判断 m+n-1个变量是

15、否构成基变量，个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组是否它比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。线性无关要简单和直观。2、表上作业法表上作业法 表上作业法是单纯形法在求解运输问题时的一表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：术语有所不同，可归纳为：（1）找出初始基可行解；）找出初始基可行解；（2）求各非基变量的检验数；）求各非基变量的检验数；（3）确定换入变量和换出变量，找出新基可行解。）确定换入变量和换出变量，找出新基可行解。（

16、4）重复（）重复（2）、（）、（3）步，直到求得最优解为止。）步，直到求得最优解为止。（1）、）、确定初始基可行解确定初始基可行解确定初始基可行解即首先给出初始的调运方案，介绍其中的确定初始基可行解即首先给出初始的调运方案，介绍其中的两种方法：两种方法：方法一：最小元素法：方法一：最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的具为止。下面由例题来说明最小元素法确定初始基可行

17、解的具体步骤。体步骤。例例3.2：某公司有：某公司有3个生产同类产品的工厂，生产的产品由个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表工厂到各销售点的单位产品运价如表3.5所示。问该公司应所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。运费为最小。初始可行解（最小元素法）门市工厂1234供应123403020301030506050需求40306030就近供应的思想：就近供应的思想：从单

18、位运价表中选取最低运从单位运价表中选取最低运价的空格开始供求分配。供价的空格开始供求分配。供应量大于需求量，取值为需应量大于需求量，取值为需求量，划去该空格的列；供求量，划去该空格的列；供应量小于需求量，取值供应应量小于需求量，取值供应量，划去该空格的行。然后量，划去该空格的行。然后根据划去一列或行的单位运根据划去一列或行的单位运价表，再选择最小运价的空价表，再选择最小运价的空格进行。格进行。门市工厂1234供应12397612359796711506050需求40306030表3.5 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656解：第一步：从单位运

19、价表中找出最小运价为解：第一步：从单位运价表中找出最小运价为1，这表示先将，这表示先将 A2 的产品供应给的产品供应给 B1。由于。由于A2 每天生产每天生产4吨，吨，B1 每天只需要每天只需要 3吨，即吨，即 A2 除每日能满足除每日能满足B1 的需要外还余的需要外还余1吨。因此在产销平吨。因此在产销平衡表衡表(A2,B1)交叉处交叉处填上填上3，表示，表示 A2 调运调运3吨给吨给B1，再在单位，再在单位运价表中将运价表中将B1 这一列这一列运价划去运价划去，表示，表示 B1 的需求已满足，不需的需求已满足，不需要继续调运要继续调运(即即x21=3=min(a2,b1)=min(4,3)。

20、第二步第二步:从上述从上述未划去未划去的单位运价表的元素中找出的单位运价表的元素中找出最小最小的的运价运价2，即，即A2 把剩余的产品供应给把剩余的产品供应给B3；B3 每天需要每天需要5 吨，吨，A2 只剩余只剩余 1 吨，因此在上述产销平衡表的吨，因此在上述产销平衡表的(A2,B3)交叉交叉处填上处填上 1，划去上述运价表中，划去上述运价表中A2 这一行运价，表示这一行运价，表示 A2的产的产品品已分配完毕已分配完毕。表3.6 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656第三步第三步:从上述第二步所得的单位运价表未划去的元素中找出最从上述第二步所

21、得的单位运价表未划去的元素中找出最小元素为小元素为 3。这表示将。这表示将 A1 的产品供应的产品供应 B3，A1 每天生产每天生产7 吨，吨，B3 尚缺尚缺 4 吨，因此在产销平衡表的吨，因此在产销平衡表的(A1,B3)交叉处填上交叉处填上 4，由于，由于B3 的需求已满足，将单位运价表中的的需求已满足，将单位运价表中的 B3 这一列运价划去。这一列运价划去。如此，一步步进行下去，直到单位运价表中所有元素都划去为如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为方案的

22、总运费为 86 元，如表元，如表3.7所示。所示。销地产地B1B2B3B4产量A1437A2314A3639销量3656两种特殊情况：一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小有多个元素同时达到最小，这时从这些最小元素中任意选择任意选择一个作为基变量；二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该元剩余产量等于该元素所在列的剩余销售量素所在列的剩余销售量。这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n 1）个，需要在同时划去的行或列的任一空格位置添上一

23、个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化退化的基可行解。例3.3：某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.8所示。利用最小元素法，求该公司的初始调运方案。销地产地B1B2B3B4产量A1531049A216964A32010577销量3584解：第一步：从单位运价表中找出最小运价为解：第一步：从单位运价表中找出最小运价为1，这表示先，这表示先将将 A2 的产品供应的产品供应 B1。由于。由于A2 每天生产每天生产4吨，吨，B1 每天只需要每天只需要 3吨，因

24、此在产销平衡表吨，因此在产销平衡表(A2,B1)交叉处填上交叉处填上3，同时将单，同时将单位运价表中的位运价表中的B1 这一列运价划去。这一列运价划去。第二步第二步:从上述未划去的单位运价表的元素中找出最小的从上述未划去的单位运价表的元素中找出最小的运价运价3，即，即A1的产品供应供应给的产品供应供应给B2；B2 每天需要每天需要5 吨，由吨，由于于A1每天生产每天生产9吨，因此在上述产销平衡表的吨，因此在上述产销平衡表的(A1,B2)交交叉处填上叉处填上 5，划去上述运价表中，划去上述运价表中B2这一列运价。这一列运价。第三步第三步:从上述第二步所得的单位运价表未划去的元素中从上述第二步所得

25、的单位运价表未划去的元素中找出最小元素为找出最小元素为 4。这表示将。这表示将 A1 把剩余的产品供应给把剩余的产品供应给B4；B4 每天需要每天需要4吨，吨，A1 正好剩余正好剩余 4 吨，因此在上述产销平吨，因此在上述产销平衡表的衡表的(A1,B4)交叉处填上交叉处填上 4，这时，这时A1的产品已分配完毕，的产品已分配完毕，同时同时B4 的需求已满足，因此划去上述运价表中的需求已满足，因此划去上述运价表中A1 这一行这一行和和B4 这一列运价。这一列运价。为了使有数字的格不减少，(有数字的格的总数应为m+n 1个)可以在空格(A1,B1)、(A1,B3)、(A2,B4)、(A3,B4)中任

26、选一个格添加一个“0”；同样，这个添加的“0”格当作基变量，取值为0。这里我们在(A1,B3)处填0（即初始调运方案是一个退化的基可行解），表示为基变量。如此，进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。如表3.9、表3.10所示。表3.9 销地产地B1B2B3B4产量A1531049A216964A32010577销量3584表3.10 销地产地B1B2B3B4产量A15049A2314A377销量3584用最小元素法确定初始基可行解 门市门市工厂工厂1234供应供应123317119432101085749需求需求2657 门市部门市部工厂工

27、厂1234供应供应12392612359796711506050需求总计需求总计40703020 门市部门市部工厂工厂1234供应供应123157612359714711508030需求需求40406020 方法二、伏格尔法：方法二、伏格尔法：最小元素法的缺点是，为了节省一处的费用，有时造成在其最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运

28、时，运费增加个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最小运费调运。就越多。因此，对于差额最大处，就优先采用最小运费调运。我们还是用例我们还是用例3.2 来说明伏格尔法的具体实施过程，步骤如下：来说明伏格尔法的具体实施过程，步骤如下：第一步：在单位运价表中增加一行和一列，列的格位置相第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为应填入该行的次小运费与最小运费之差，我们称之为行差行差额额。行的格位置相应填入该列的次小运费与最小运费之差，。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为我

29、们称之为列差额列差额。如此可得表。如此可得表3.10：表3.10 销地产地B1B2B3B4行差额A13113100A219281A3741051列差额2513第二步：从行差额和列差额中选出第二步：从行差额和列差额中选出最大者最大者，选择它所在的，选择它所在的行或列中的行或列中的最小元素最小元素。比较该元素所在的行和列的产量，。比较该元素所在的行和列的产量，取它们最小者填入产销平衡表相应的位置。同时在单位运取它们最小者填入产销平衡表相应的位置。同时在单位运价表中划去一行或一列。由于价表中划去一行或一列。由于B2 的列差额最大。的列差额最大。B2 列中列中最小元素为最小元素为 4（即（即 A3 行

30、），可确定行），可确定 A3 产品优先供应产品优先供应 B2。比较它们的产量和销量，可知在单位运价表中划去。比较它们的产量和销量，可知在单位运价表中划去 B2 列。在产销平衡表的列。在产销平衡表的(A3,B2)空格处填入空格处填入 6。第三步：对上述未划去的元素第三步：对上述未划去的元素再比较出各行、各列再比较出各行、各列的差额。的差额。重复第一、二步的工作，直到给出初始解为止。重复第一、二步的工作，直到给出初始解为止。本问题利用伏格尔方法给出的初始调运方案如下表本问题利用伏格尔方法给出的初始调运方案如下表3.11所所示。示。表3.11 销地产地B1B2B3B4产量A1527A2314A363

31、9销量3656由以上可见：伏格尔方法同最小元素法除在确定供求关系由以上可见：伏格尔方法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同，因而给出的初始调运方的原则上不同外，其余步骤相同，因而给出的初始调运方案也是基可行解。且一般来说，用伏格尔方法比用最小元案也是基可行解。且一般来说，用伏格尔方法比用最小元素法所求出的初始解更接近于最优解。本例用伏格尔方法素法所求出的初始解更接近于最优解。本例用伏格尔方法给出的初始解的总运费为给出的初始解的总运费为 85元。元。（2）、）、最优解的判别最优解的判别得到运输问题的初始基可行解后就要判别这个解是否为最优得到运输问题的初始基可行解后就要判别这个

32、解是否为最优解，判别的方法是计算解，判别的方法是计算非基变量非基变量即空格的检验数。因运输问即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于验数全都大于等于 0 时为最优解。下面介绍两种求空格检验时为最优解。下面介绍两种求空格检验数的方法。数的方法。、方法一：闭回路法、方法一：闭回路法在给出调运方案的计算表上，如表在给出调运方案的计算表上，如表3.7，从每一空格出发，从每一空格出发，找一条找一条闭回路闭回路。它是以它是以空格为起点，用水平线或垂直线向空格为起点，用水平线或垂直线向前划，每碰到一数字格

33、就转前划，每碰到一数字格就转 90 度后继续前进。直到回到度后继续前进。直到回到起始空格处为止。起始空格处为止。每个空格每个空格都存在都存在唯一唯一的闭回路。的闭回路。(A1,B1)空格与空格与(A1,B4)、(A2,B4)和和(A2,B1)三个有数字三个有数字的格构成一闭回路，如此等等。的格构成一闭回路，如此等等。闭回路计算检验数的经济解释为：在已给出初始解的表中，闭回路计算检验数的经济解释为：在已给出初始解的表中，可以从任一空格出发，如从可以从任一空格出发，如从(A1,B1)出发，若让出发，若让 A1 的产品的产品调调 1 吨给吨给B1，为了保持产销平衡，就要依次作调整：在，为了保持产销平

34、衡，就要依次作调整：在(A1,B3)处减少处减少 1 吨，吨，(A2,B3)处增加处增加 1 吨，吨，(A2,B1)处减少处减少 1 吨，即构成了以吨，即构成了以(A1,B1)空格为起点，其它为有数字的格空格为起点，其它为有数字的格的闭回路。如表的闭回路。如表3.12中的直线所示。各顶点所在格的右上角中的直线所示。各顶点所在格的右上角的数字是单位运价。的数字是单位运价。可见这一调整方案使运费增加了：可见这一调整方案使运费增加了：(+1)3+(-1)3+(+1)2+(-1)1=1(元元)这表明若这样调整运输方式将增加运费。将这表明若这样调整运输方式将增加运费。将“1”这个数填这个数填入入(A1,

35、B1)格，这就是检验数。格，这就是检验数。表3.12 销地产地B1B2B3B4产量A1437A2314A3639销量3656 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656按以上所述，就可以找出按以上所述，就可以找出 所有空格的检验数，见如下表所有空格的检验数，见如下表3.13。表表3.13空 格闭 回 路检验数(A1,B1)(1,1)(1,3)(2,3)(2,1)(1,1)1(A1,B2)(1,2)(1,4)(3,4)(3,2)(1,2)2(A2,B2)(2,2)(2,3)(1,3)(1,4)(3,4)(3,2)(2,2)1(A2,B4)(2,4)(

36、2,3)(3,3)(1,4)(2,4)-1(A3,B1)(3,1)(3,4)(1,4)(1,3)(2,3)(2,1)(3,1)10(A3,B3)(3,3)(3,4)(1,4)(1,3)(3,3)12这时检验数还存在负数，因为这时检验数还存在负数，因为(A2,B4)空格的检验数为空格的检验数为 1，这说明表，这说明表3.7给出的方案还不是最优解，还需要进一给出的方案还不是最优解，还需要进一步改进，改进方法见本节后面的基可行解的改进方法。步改进，改进方法见本节后面的基可行解的改进方法。、方法二：位势法方法二：位势法对偶数学模型？对偶数学模型？检验数检验数符号如何时，取得最优解？当 时，取得最优解。

37、基变量检验数目标函数取最小如何表达？是多少？计算检验数（位势法）基变量的方程共有m+n-1个方程，但有m+n个变量，一般令 。因此可求得这些变量。称 分别为产地位势和销地位势。对于本例：解得：因而可计算得计算检验数（位势法）门市门市部部工厂工厂1234供应总供应总计计191296U1 401027377U23030365911u32030v1v2v3v4位势法求检验数位势法求检验数 门市部工厂1234供应总计191296U130 20 27377U22040365911u34010v1v2v3v4令令U1=0,能否令能否令U2,U3=0,或或V1,V2,V3,V4=0？上述各种方法求得到的检验

38、数关系？上述各种方法求得到的检验数关系？与闭合回路法求得到的检验数的关系？与闭合回路法求得到的检验数的关系？、基可行解改进的方法基可行解改进的方法闭闭回路调整法回路调整法取负检验数中绝对值最大的空格作回路。取负检验数中绝对值最大的空格作回路。从空格开始依次给回路顶点格标从空格开始依次给回路顶点格标“+”和和“-”找出找出“-”格中运量最小者，作为调整量，格中运量最小者，作为调整量，将每个将每个“+”格的运量加上该调整量，每个格的运量加上该调整量，每个“-”格的运量减去该调整量。格的运量减去该调整量。即得新的基本可行解。即得新的基本可行解。再计算空格检验数和调整基本解，直到检再计算空格检验数和调

39、整基本解，直到检验数非负为止。验数非负为止。出基变量？初始解的调整初始解的调整 门市部工厂1234供应总计19129650 +4010-273776030-30+3659115020 -30+需求总计40406020 应当指出的是，产销平衡的运输问题应当指出的是，产销平衡的运输问题必定存在最必定存在最优解优解。那么有唯一最优解还是无穷多个最优解？依据仍。那么有唯一最优解还是无穷多个最优解？依据仍然是看然是看非基变量（即空格处）的检验数是否有为非基变量（即空格处）的检验数是否有为0的。的。若有，则存在无穷多个最优解；否则，只有唯一最优解。若有，则存在无穷多个最优解；否则，只有唯一最优解。无穷多最

40、优解线性规划问题无穷多最优解的判定方法？因为 ，因此最优解有无穷多个。如何求其它最优解？以检验数为0的格为调入格，作闭回路，调整得最优解。门市部工厂1234供应总计1912965030 20（3）（7）273776020（3）（3）4036591150（5）40（0）10需求总计40406020P 79 例3.2 P80例.33.3 几种特殊的情况1）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；4）其它几种情况。某供应地不能供应某销地；对策：对策：1）在对应的运价表格中，运价做）在对应的运价表格中，运价做+处理，处理，（一般用（一般用M表示，如何处理呢？

41、）。表示，如何处理呢？）。几种特殊几种特殊情况的处理情况的处理有一批物资在三个供应点，供应给四个需求点，运价如表所示，第三供应点不能向第四需求点运送该物资，求总运费最少调运方案。1234s1231614191313202219231715M506050d30705010特殊情况1举例1）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：对策：2）在对应供应地和需求地，同时减去）在对应供应地和需求地，同时减去A。几种特殊几种特殊情况的处理情况的处理有一批物资在三个供应点，供应给四个需求点，运价如表所示，第3供应点必须调拨20单位物资给需求点2，求总运费最少

42、的调运方案。1234s123161419131320221923171516506050（30）d3070（50）5010特殊情况2举例某玩具公司生产三种新某玩具公司生产三种新型玩具（型玩具（A,B,C），供），供量分别为：量分别为：1000，2000，2000件，三个件，三个百货公司百货公司(甲，乙，丙甲，乙，丙)销量均为销量均为1500件。由于件。由于经营等原因，各公司销经营等原因，各公司销售盈利额不同（见下表）售盈利额不同（见下表），又丙百货点要求至少，又丙百货点要求至少供应供应C玩具玩具1000件，而件，而拒绝进拒绝进A玩具，求满足玩具，求满足盈利额最大的供应方案。盈利额最大的供应方案

43、。甲乙丙供A54-1000B16892000C12101120001）某供应地不能供应某销地；2）某供应地至少供应某销地量A；3）某销地至少获得供应量B；对策：对策：3）供不应求，增加一个虚拟供地。）供不应求，增加一个虚拟供地。增加一个虚拟销地，其需要量为增加一个虚拟销地，其需要量为B。从各产。从各产地至其（虚拟销地）的运价与原运价相同，而地至其（虚拟销地）的运价与原运价相同，而从虚拟供地至其的运价为从虚拟供地至其的运价为+。几种特殊几种特殊情况的处理情况的处理有甲、乙、丙三个城市，每年煤炭需求320，250，350单位，由A和B两个煤矿负责供应，两矿的产量分别为400和450单位，矿到各城市

44、的运价如下表。经过协商，丙城市必须得到320单位的供应，试求将两矿煤炭分配出去的总运费最低的调运方案。甲乙丙A151822B212526虚拟销地的理解 某销地至少获得供应量B，最多需要量B；对策：对策：供不应求，增加一个虚拟供地。供不应求，增加一个虚拟供地。增加一个虚拟销地，其需要量为增加一个虚拟销地，其需要量为B。从。从各产地至其（虚拟销地）的运价与原运价各产地至其（虚拟销地）的运价与原运价相同，而从虚拟供地至其的运价为相同，而从虚拟供地至其的运价为+。情况情况3的推广的推广有一批物资在三个供应点供应给四个需求点，运价如表所示，求总运费最少的调运方案。1234s123161419131320

45、221923171516506050dmin3070010dmax507030不限4需求点的最高需求为多少？第四需求点的最大供应量：160-100=60吨按最大需求计算，需求为：150+60=210吨设置虚第四供应点，供应量：50吨1234s1231614191614191313202219231715M1715M5060504M0M0M050d302070301050某产地至少运出量A对策：供大于求的情况。对策：供大于求的情况。该产地分为产地该产地分为产地1和产地和产地1，产地，产地1的产量为的产量为A，产地，产地1的产量的产量C-A。增加虚拟。增加虚拟销地，产地销地，产地1到虚拟销地到虚拟

46、销地的运费为的运费为M，产地，产地1到虚到虚拟销地的运费为拟销地的运费为0。如表所示的运输问题。假如表所示的运输问题。假定产地定产地2的物资至少运出的物资至少运出38个单位，产地个单位，产地3的物资的物资至少运出至少运出27个单位。求此个单位。求此运输问题的最优解。运输问题的最优解。ABC产112220214540323330销302020举一反三：供大于求时，存在储存费用如表所示的运输问题，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为3，7，5。求此运输问题的最优解（含运输费和储存费）。举一反三：ABC产112220214540323330销302

47、020供不应求时，存在需求不足的损失费如表所示的运输问题，若需地缺少一个单位物资，则将发生损失费用。假定A，B，C需地单位物资需求不足的损失费用分别为5，3，7。求此运输问题的最优解（含运输费和损失费）。举一反三：ABC产112220214520323330销303030转运问题运输规划问题灵敏度分析已知某运输问题产销平衡，运价表：门市工厂1234供应12397612359796711506050需求404060201.求最优运输调运方案；2.单位运价表中，运价系数cij分别在什么范围之内变化，上面求出的最优调拨方案不变。已知某运输问题的产销平衡表，最优调运方案及单位运价表如下表。由于从产地2

48、到销地B的道路因故暂时封闭，故需调整最优调拨方案，试用尽可能简单的方法重新找出最优调运方案。ABCDE110 20 59102210 10 30 63120 710 4ABCDE产1459244331138销 35463运输问题的应用某厂按合同规定必须当年每个季度末分别提供10，15，25，20台同一规格的机器，该厂生产能力及生产每台机器的成本见下表。如果生产出的机器不当季交货，每台每积压一个季度需要储存和维护费0.15万，要求在完成合同情况下，做出使该厂全年生产费用（含储存和维护费）最小的决策。季度生产能力（台）单位成本(万)12510.823511.13301141011.3解：由于每个季

49、度生解：由于每个季度生产产出来的柴油机不一定当季交出来的柴油机不一定当季交货货，所，所以以设设 xij 表示表示为为第第i季度生季度生产产的用于第的用于第j季度交季度交货货的柴油机数。的柴油机数。根据合同要求，必根据合同要求，必须满须满足：足：x11 =10 x12+x22 =15 x13+x23+x33 =25 x14+x24+x34+x44=20又每季度生又每季度生产产的用于当季和以后各季交的用于当季和以后各季交货货的柴油机数不可的柴油机数不可能超能超过该过该季度的生季度的生产产能力，故又有：能力，故又有：x11+x12+x13+x14 25 x22+x23+x24 35 x33+x34

50、30 x44 10第第 i 季度生季度生产产的用于第的用于第 j 季度交季度交货货的每台柴油机的的每台柴油机的实际实际成本成本 cij 应该应该是是该该季度季度单单位成本加上位成本加上储储存、存、维护维护等等费费用。用。cij 的具体的具体数数值见值见表表190。表190 交货生产IIIIIIIVI10.810.9511.1011.25II11.1011.2511.40III11.0011.15IV11.30设用 ai 表示该厂第 i 季度生产能力，bj 表示第 j 季度的合同供应量，则问题可写成：显然这是一个产大于销的运输问题模型。注意到这个问题中当 i j 时，xij=0，所以应该令对应的