运筹学 第三章 运输问题

1、2020/7/17,1,运筹学OPERATIONS RESEARCH,2020/7/17,2,第三章 运输问题,运输问题的数学模型 表上作业法 产销不平衡的运输问题及应用,2020/7/17,3,1 运输问题的典例及数学模型,一、 引例,某公司从三个产地 ， ， 将产品运往四个销地 ， ， ，各产地的产量，各销地的销量，及各产地往各销 地的运费单价如表所示。应如何调运可使运费最小？,2020/7/17,4,解：从表中可知：总产量 = 总销量。这是一个产销平衡的 运输问题。假设 表示从产地 运往销地 的产 品数量， 建立如下表格：,于是可建立如下的数学模型：,2020/7/17,5,目标函数：,

2、约束条件：,产量约束,销量约束,20,20,2020/7/17,6,设有m个产地，分别为 ; n 个销地，分别是 ； 从产地 运往销地 的单位运价是 ，运量 是产地 的产量； 是销地 的销量。,二、一般运输问题数学模型,则该运输问题的模型如下：,2020/7/17,7,说明：当 时，称其为产销平衡的运输问题， 否则产销不平衡。,2020/7/17,8,说明：从上述模型可以看出： （1）这是一个线性规划的模型； （2）变量有mn个； （3）约束条件有 m+n 个； （4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1), 而非m+n 。,若直接用单纯形法求解，显然单纯形表比较庞大，于是在 单纯

3、形法的基础上创建了表上作业法求解运输问题这一特 殊的线性规划问题,2020/7/17,9,从第一节的运输问题的数学模型可知，运输问题实际上 也属于线性规划，但由于运输问题的特殊性（变量个数较多， 系数矩阵的特点），如果用单纯形表格方法迭代，计算量很 大。今天介绍的 “表上作业法”，是针对运输问题的特殊求解 方法，实质还是单纯形法，但减少了计算量。 表上作业法适用于求解产销平衡的运输问题。（产销不平 衡的问题可转化为平衡问题）,2 运输问题的表上作业法,2020/7/17,10,表上作业法 一般步骤： 1、找出初始基本可行解； 2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；

4、否则 转第三步； 3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可 行解； 4、重复第二、第三步，直至得到最优解。,2020/7/17,11,一、确定初始基本可行解： 对于有m个产地n个销地的产销平衡问题，有m个关于产量 的约束方程和n个关于销量的约束方程。表面上，共有m+n个 约束方程。 但由于产销平衡，其模型最多只有m+n-1个独立的约束方 程，所以运输问题实际上有m+n-1个基变量。在mn的产销 平衡表上给出m+n-1个数字格，其相对应的调运量的值即为 基变量的值。,2020/7/17,12,那么在该例中，应有 3+4-1=6个基变量。,2020/7/17,13,1.最小元

5、素法 最小元素法的思想是就近供应，即对单位运价最小的变量分配运输量。 在表上找到单位运价最小的x21，并使x21取尽可能大 的值，即x21=3,把A1的产量改为1，B1的销量改为0，并 把B1列划去。在剩下的33矩阵中再找最小运价，同 理可得其他的基本可行解。,3,11,3,10,8,5,10,2,9,4,7,1,2020/7/17,15,表中填有数字的格对应于基变量(取值即为格中数字），而空格对应的是非基变量（取值为零）. 在求初始基本可行解时要注意的一个问题： 当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。

6、（或者在同时划去Ai行与Bj列时，在该行或该列的任意空格处填加一个0。） 这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。,2020/7/17,16,2.Vogel法 Vogel法的思想是:一地的产品如果不能按照最小运费就近供应，就考虑次小运费，这就有差额，差额越大，说明不能按最小运费调运时，运费增加得越多。因而差额越大处，就应当采用最小运费调运。,2020/7/17,17,3,11,3,10,2,9,4,7,1,10,8,5,2020/7/17,18,二、最优解的判别 判别解的最优性需要：计算检验数。方法有两种,闭回路：是在已给出的调运方案的运输表上从一个代表非基

7、变量的空格出发，沿水平或垂直方向前进，遇到代表基变量的填入数字的格可转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。,1.闭回路法,因为任意非基向量均可表示为基向量的唯一线性组合，因此对于任意空格都能够找到、并且只能找到唯一的一条闭回路。,2020/7/17,20,从非基变量 出发，找到一个闭回路如上表所示。回路有四个顶点，除 外，其余都为基变量。 调整调运量： ，运费增加了3元； ，运费减少3元 ，运费增加2元； ，运费减少1元 调整后，总运费增加：3-3+2-1=1元。 说明如果让 为基变量，运费就会增

8、加，其增加值1作为 的检验数，,2020/7/17,21,闭回路法计算检验数：就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,必须对这个空格的闭回路中的各顶点的调运量加上或减少1。最后计算出由这些变化给整个运输方案的总运输费带来的变化。以这个变化的数值，作为各空格（非基变量）的检验数。 判别最优解准则：如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解；否则继续改进找出最优解。,2020/7/17,22,2.位势法 （1）对运输表上的每一行赋予一个数值 ，对每一列赋予一个数值 ，称为行（列)位势。 （2）行（列)位势的数值是由基变量的检验数所决

9、定的，即基变量要满足： 非基变量 的检验数就可以用公式 求出。,2020/7/17,24,我们先给u1赋个任意数值，不妨设u1=0，则从基变量x11的检验数求得 v3=c13-u1=3-0=3 。 同理可以求得 v4=10，u2= -1，等等见上表。 检验数的求法，即用公式 ， 如 。,2020/7/17,25,位势法计算检验数： 检验数：,又因为基变量的检验数为0，于是由（m+n-1)个基变 量的检验数 可解出 ，进而计算其他非基变量的检验数。,其中,第i个分量,第m+j个分量,2020/7/17,26,三、改进运输方案的办法闭回路调整法,当表中的某个检验数小于零时，方案不为最优，需要调整。

10、方法是：选取所有负检验数中最小的非基变量作为入基变量，以求尽快实现最优。,（1）确定调整量：例：取 ，表明增加一个单位的 运输量，可使得总运费减少1。在以 为出发点的闭回路中，找出所有偶数顶点的调运量： ， 则调整量 （2）调整方法：把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。,2020/7/17,27,调整运量后的新方案：,2020/7/17,29,对上表用位势法进行检验如下表，可知已达最优解。,2020/7/17,30,表上作业法的一般步骤： 1、用最小元素法或Vogel法确定初始基可行解； 2、判断是否为最优：用闭回路法或位势法计算空格检验数，若

11、所有检验数均非负，则已得到最优解；否则进入第三步； 3、 从所有负检验数中选择最小者对应空格作为进基变量，从此点出发作闭回路，确定调整量 ，奇点处增加 ，偶点处减少 。,2020/7/17,31,例：用表上作业法，求解下面的 运输问题 ：,解:用最小元素法确定初始基可行解，如下表所示：,2020/7/17,32,+,+,-,-,2020/7/17,33,+,+,-,-,2020/7/17,34,此时所有非基变量的检验数均非负，故已达最优解。,2020/7/17,35,一、产销不平衡的运输问题,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各

12、销地的运费单价如表所示。 应如何调运可使运费最小？,3 产销不平衡的运输问题及应用,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,例1：某公司从两个产地 ， ，将产品运往三个销地 ，

13、， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,例1：某公司从两个产地 ， ，将产品运往三个销地 ， ， ， 各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。 应如何调运可使运费最小？,2020/7/17,36,易知这个问题中：总产量总销量，即,这时可考虑增加一个假想产地，其产量是（总销量总产量150) 他到各销地的单位运费是于是得到如下的表格：,2020/7/17,37,例

14、2：某单位有三个区，一区、二区、三区；每年需要生活 用煤和取暖用煤各3000吨，1000吨，2000吨；由河北临城、 山西盂县两处煤矿负责供应，两地价格和煤质相同，两煤 矿的供应能力分别是1500吨，和4000吨。由煤矿至该单位 三个区的单位运价如表所示。,由于供应能力限制，经研究决定，一区供应量可减少0300吨， 二区全部满足，三区不能少于1500吨，试求使得运费最小的运 输方案？,2020/7/17,38,根据题意，添加虚拟产地后，可作出产销平衡的运价表：,2020/7/17,39,例：设有三个化肥厂供应四个地区的化肥，假设等量的化 肥在这个地区的使用效果相同。各厂的产量、各地区的需 要量

15、、单位运价如表所示。求出运费最省的调拨方案。,2020/7/17,40,解：无论考虑需求的上限还是下限，这都是一个产销不平衡的问题。 当考虑下限时，产销；当考虑需求上限时，产销。 于是可以考虑在满足最低需求的情况下，兼顾最高需求。即将每 个地区的需求分为最低需求和（最高-最低）需求，最低部分必须 满足，高出的部分可满足也可不满足。虽然销地的需求无上限， 但根据生产能力，最多可以给她分配60万吨。 另外若将最高需求考虑进来，则需添加虚拟产地D，其产量应为 50万吨。 于是可给出如下的产销平衡及运价表。,2020/7/17,41,2020/7/17,42,二、生产与存储问题,例4：某厂按照合同规定

16、须于当年每季度末分别提供10， 15，25，20台同一规格的柴油机。已知该厂各季度的生 产能力及生产每台柴油机的成本如表所示。又如果生产 出来的柴油机当季不交货，每台每积压一个季度，存储 维护费用0.15万元。要求在完成合同的情况下，使得全 年生产（存储）费用最小的决策。,2020/7/17,43,注意：单位运价如何确定,故设： 表示第 季度生产，用于第 季度交货的产品数量。可建立数学 模型。,2020/7/17,44,三、转运问题,以本章引例为例，产品从3个产地运往4个销地。现考虑; 1、各产地的产品不一定直接运往销地，可以将产品集中后再一起运； 2、运往个销地的产品也可先运给其中几个，再转运给其他销地； 3、除产、销地外还可以有几个中间转运站，在产地之间、销地之间、或产地与销地之间进行转运； 已知单位运价表如下，问在考虑产销地之间直接运输和非直接运输的各种可能方案下，如何安排运输方案，可使总运费最小？,2