运输问题表述课件.ppt

《运输问题表述课件.ppt》由会员分享，可在线阅读，更多相关《运输问题表述课件.ppt（67页珍藏版）》请在三一文库上搜索。

1、1,第三章 运输问题,本章主要内容： 运输问题的数学模型 运输问题的求解表上作业法 运输问题应用建模,2,第一节 运输问题的数学模型 第二节 表上作业法 第三节 产销不平衡的运输问题 第四节 应用举例,3,第一节 运输问题的数学模型,一、数学模型,例1,产地：货物发出的地点 销地：货物接收的地点 产量：各产地的可供货量 销量：各销地的货物需求量,运输问题就是研究如何组织调运，既满足各产地的产量和各销地的需求，又使得总运费最小。,4,二、运输问题的一般数学模型,设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费,令a1, a2, , am表示各产地产量, b1, b2, ,

2、bn表示各销地的销量,有m个地区生产某种物资，有n个地区需要该类物资,产销平衡表,单位运价表,5,一般满足产销平衡：,产量约束：由某一产地运往各个销售地的物品数 量之和等于该产地的产量。,销量约束：由各个产地运往某一销售地的物品数 量之和等于该销售地的销量。,6,产大于销,7,产小于销（销大于产）,8,定理1 运输问题的数学模型必有最优解。 首先，运输问题一定有可行解；其次，任何单位运价cij0，从而对于任一可行解，必有目标函数值大于或等于零，即目标函数有下界。 所以，求解运输问题时，不需要进行无最优解的判别。,产量平衡（m个）,销量平衡（n个）,9,在例1中，运输问题的系数矩阵为：,1.一般

3、情况下,运输问题 决策变量xij的系数列向量为:,三、变量xij的系数列向量的特征,2.系数矩阵的元素等于0或1。,10,3.运输问题系数矩阵的秩为m+n-1。,3.运输问题基变量的个数为m+n-1。,11,概念,例2,1)数字格,2)空格,3)闭回路,四、闭回路,闭回路：以某空格为起点，用水平或垂直线划，只有当碰到某恰当的数字格后，才能转900继续前进，直到回到起始空格为止。,12,13,14,15,16,17,18,2.闭回路与变量所对应的系数列向量组线性相关性的关系,结论1 运输问题一组变量构成闭回路的充要条件是这组变量所对应的系数列向量线性相关,例如，闭回路（x11, x21, x23

4、, x13）,19,闭回路与变量所对应的系数列向量组线性相关性的关系,结论2 运输问题的一个可行解是基可行解的充要条件是：,1）数字格的个数为m+n-1个；,2） 这m+n-1个数字格不构成闭回路。,结论3 对每一个空格处，有且仅有一条闭回路。,20,一、表上作业法的步骤,第二节 表上作业法,最优性检验,结 束,Y,调 整,N,确定初始 基可行解,在mn维产销平衡表上找到m+n-1个数字格,确定进基变量和出基变量,21,表上作业法步骤：初始方案、最优性检验、改进方案 一、初始方案的确定 1.最小元素法 2.伏格尔法 二、最优性检验 1.闭回路法 2.位势法 三、改进方案 在闭回路内改进,22,

5、1.最小元素法(就近供应) 就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为止。,例3,二、初始基可行解的确定,23,例3,最小元素法给出的初始解是运输问题的基可行解。,24,2.伏格尔法（Vogel）,第一步：求出每行次小运价与最小运价之差；同时求出每列次小运价和最小运价之差； 第二步：找出所有行、列差额的最大值，差额最大值所对应的行或列中的最小运价处先调运； 第三步：这时必有一列或一行调运完毕，划去该列或该行，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，得到一个调运方案。,25,2.伏格尔法（Vogel）,例4,2

6、6,在以上两种方法中，有几点需要注意：,这两种方法得出的解均为初始可行解。,一般由伏格尔法得出的解比最小元素法得出的解更接近最优解。,在以上方法过程中，不可同时划去行和列。,27,1.闭回路法 例5,注: 1)数字格检验数均为0,显然该问题至此尚未达到最优解。,三、求检验数并进行最优解的判定,1,2,1,-1,10,12,28,29,30,31,32,33,34,2.位势法,例6 由最小元素法得出初始解,如下表,3）行势、列势可不唯一，但检验数是一致的。,35,位势法的计算过程,令u1=0,按ui+vj=cij相继确定其他数字格的ui和vj,计算空格的检验数。如 11=3-(0+2)=1,因为

7、24=-10,因而该问题至此尚未达到最优解.,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,36,位势法的理论依据（互补松弛定理）,37,位势法的理论依据,运输问题,设B为一可行基，则相应的基可行解的各变量的检验数为,运输问题的对偶问题,由对偶理论有 Y=CBB-1,基变量的检验数等于0,（I：基变量下标集）,38,位势法的步骤,对于每一个基变量（数字格）都按照公式 ui+vj=cij 列出一个位势方程，形成位势方程组（m+n1个）； 任意决定其中一个位势的数值，然后求出其他位势的数值； 按照公式 计算非基变量（空格处）的检验数（mn-(m+n1)个）。,39,从最小负检验数

8、所对应的空格进行调整,例7 对由最小元素法得出的初始解进行调整,调整方法：,1）找出负检验数所在空格处的闭回路,2）在闭回路上找到偶数点所对应的基变量的最小值,再按调整后的解由位势法计算空格的检验数,四、调整,1,2,1,-1,10,12,x23 x14 x24 x13,3）以此最小值为调整量，在奇数格加上该调整量，在偶数格上减去该调整量,换入变量：x24,换出变量：x23,40,1.由最小元素法求得初始基可行解,五、典型运输问题解题步骤示例,41,2.由位势法求检验数,令u1=0,按ui+vj=cij相继确定其他数字格的ui和vj,计算空格的检验数,因为24=-10,因而该问题至此尚未达到最

9、优解.,0,3,10,-1,-5,2,9,1,2,1,-1,10,12,如11=3-(0+2)=1,42,3.从最小负检验数所对应的空格进行调整,调整方法：,1）找出闭回路,2）使最小负检验数所对应的空格达到最大的调整量1,1,2,1,-1,10,12,43,令u1=0,按ui+vj=cij相继确定其他数字格的ui和vj,计算空格的检验数。如11=3-(3+0)=0,因为所有的ij0,至此该问题已经达到最优解.,4.再按调整后的解由位势法计算空格的检验数,0,3,10,-2,-5,3,9,0,2,2,9,12,1,44,表上作业法的步骤： （1）编制调运表（产销平衡表、单位运价表） （2）在调

10、运表上求出初始基可行解 （3）用位势法或闭回路法计算非基变量的检验数，若所有非基变量的检验数均大于等于0，则已得到问题的最优解 （4）选取小于0的检验数中的最小者所对应的非基变量作为进基变量，用闭回路法进行基可行解的转换，得到新的基可行解，转入步骤（3）。,45,可能出现的几种情况,（1）无穷多最优解 某一个非基变量（空格处）的检验数为0； 以（1,1）为调入格左闭回路（1,1）（1,4）（2,4）（2,1）（1,1），调整量=2,0,2,2,9,12,1,46,7,4,10,5,8,10,1,3,9,11,2,3,A3,A2,A1,B4,B3,B2,B1,销地 产地,2,2,9,12,1,0

11、,47,可能出现的几种情况,（2）退化 同时划去一行和一列； 在用闭回路法调整时，在闭回路上出现有两个或两个以上的偶数顶点数字格具有相等的最小值，这时只能选择其中一个作为调入格，经过调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。,48,练习：下表是一运输问题的表格，其中右上角数字是单位运价，圆圈内是运量。,(1)上表所给方案是否为该问题的可行解，是否为该问题的 基本可行解，为什么？ (2) 上述方案是否是该问题最优解？若不是，如何用表上作 业法继续迭代？,49,一、原理,第三节 产销不平衡的运输问题,50,证明：,51,结论： 1. 运输问题有可行解 产销平衡 2. 运输

12、问题有可行解 运输问题有最优解 3. 运输问题有最优解 产销平衡,52,二、产销不平衡问题的处理,53,m+n+1个约束条件,m(n+1)个决策变量,54,二、产销不平衡问题的处理,55,m+n+1个约束条件,(m+1)n个决策变量,56,例8 求下面运输问题的最优解,这是一个产大于销的运输问题，增加一个假想的销售地，可以将其转化为产销平衡问题。,57,假设“己”的虚拟销量为2，各实际产地到其的运费为0。如下表所示：,用表上作业法可以求出最优解。,注：某列单位运价为0，应该最后考虑,58,例9 产销不平衡问题,在产销平衡表中增加一个假想的化肥厂D，年产量为50万吨；将需求分两种情况的地区，实际

13、按两个地区看待。,59,这样可将该问题化为产销平衡问题：,60,根据表上作业法计算，可得该问题的最优方案，如下表：,61,有三个工厂A、B、C，它们需要同一种资源，数量分别是 300、400、300吨，有两个产地甲、乙可供应该原料500、 400吨，单位运价见表：,将该问题化为平衡问题，建立运输表，要求A地需求必须满足,62,第四节 应用举例,某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使

14、该厂全年生产(包括储存、维护)费用最小的决策 。,例10,63,例10,64,设ai表示第i季度的生产能力，bj表示第j季度的合同供应量，建立数学模型表示为：,设cij为第i季度生产的用于第j季度交货的柴油机的单位实际成本，等于该季度的单位生产成本加上存储、维护等费用。,65,这是一个产大于销的运输问题，增加一个假想的需求D，将问题转化为产销平衡的运输问题。如下表：,66,用表上作业法求解可得多个最优解，下表给出了其中一个最优解 （单位： 台）,按此方案生产，总费用为773万元。,第I季度生产25台，其中有15台用于第II季度的合同； 第II季度生产5台，全部用于第III季度的合同； 第III季度生产30台，其中有10台用于第IV季度的合同； 第IV季度生产10台。,67,练习：有三个工厂B1、B2、B3，它们需要同一种原料，现 有三个产地A1、A2、A3可供应该原料，运用表上作业法求 解最小的调运方案，某步的运算表如下，其中方框中的数 字是运量，括号中的数字是单位运输费用：,（1）求a、b、c、d的值； （2）上述方案是否是该问题最优解？若不是，运用表上作 业法求出最优调运方案。 （3）A3到B1的运费满足什么条件，使得（2）的表格中当前解 为最优解。 （4）A3到B1的运费满足什么条件，使得（2）中求出的最优解 保持不变。,