《运筹学课件第三章运输问题解读》由会员分享，可在线阅读，更多相关《运筹学课件第三章运输问题解读（77页珍藏版）》请在金锄头文库上搜索。
1、第三章 运输问题,一、运输问题及其数学模型 二、表上作业法 三、运输问题的进一步讨论 四、应用举例,一、运输问题及其数学模型,供应地,运价,需求地,引例：,运输问题网络图,供应地约束,需求地约束,一、运输问题及其数学模型,运输问题的描述： 设某种物品有m个产地A1,A2,.,Am，各产地的产量分别是a1,a2,.,am；有n个销地B1,B2,.,Bn，各销地的销量分别为b1,b2,bn。假定从产地Ai(i=1,2,m)向销地出Bj(jl,2,.n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?,一、运输问题及其数学模型,运价表,一、运输问题及其数学模型,产销平衡运输问题的数学
2、模型表示：,一、运输问题及其数学模型,该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如3个产地，4个销地。变量数目会有19个之多。 因此应该寻求更简便的解法。 为了说明适于求解运输问题的更好的解法，先分析运输问题数学模型的特点。,一、运输问题及其数学模型,运输问题数学模型的特点： 1运输问题有有限最优解,是一个可行解。同时，目标函数有下界，且不会趋于负无穷。所以，必存在有限最优解。,一、运输问题及其数学模型,2运输问题约束条件的系数矩阵,n 行,m 行,系数列向量：,一、运输问题及其数学模型,由此可知，运输问题具有下述特点： (1)约束条件系数矩阵的元素等于0或1； (2)
3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次； 对产销平衡运输问题，除上述两个特点外，还有以下特点： (3)所有结构约束条件都是等式约束； (4)各产地产量之和等于各销地销量之和。 秩 ( A) =m+n-1 运输问题的基可行解中应包含m+n-1个基变量.,一、运输问题及其数学模型,3.运输问题的解 (1)解x必须满足模型中的所有约束条件； (2)基变量对应的约束方程组的系数列向量线性无关； (3)解中非零变量xij的个数不能大于(m+n-1)个，原因是运输问题中虽有(m+n)个结构约束条件，但由于总产量等于总销量，故只有(
4、m+n-1)个结构约束条件是线性独立的； (4)为使迭代顺利进行，基变量的个数在迭代过程中保持为 (m+n-1)个。 运输问题解的每一个分量，都唯一对应其运输表中的一个格 填有数字的格 或 空格,一、运输问题及其数学模型,下表给出了例1的一个解。,一、运输问题及其数学模型,二、表上作业法,表上作业法是一种迭代法，迭代步骤为： 1、先按某种规则找出一个初始解(初始调运方案)； 2、再对现行解作最优性判别； 3、若这个解不是最优解，就在运输表上对它进行调整改进，得出个新解； 4、再判别，再改进； 5、直至得到运输问题的最优解为止。 迭代过程中得出的所有解都要求是运输问题的基可行解。,例1：,二、表
5、上作业法,8,2,10,14,8,6,所以，初始基可行解为：目标函数值Z246,二、表上作业法,1、初始基可行解最小元素法,在满足约束条件下尽可能的给最左上角的变量最大值.,8,8,6,4,8,14,所以，初始基可行解为：目标函数值Z372,1、初始基可行解西北角法,二、表上作业法,沃格尔法计算步骤： 1) 分别算出各行、各列的罚数。 2) 从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。 3) 对剩余行、列再分别计算各行、列的差额。返回1)、2)。,二、表上作业法,1、初始基可行解沃格尔法,14,所以，初始基可行解为：目标函数值Z244,8,8,12,2,4,二、表上作
6、业法,4-4=0,3-2=1,6-5=1,4-2=2,10-5=5,4-3=1,9-6=3,0,1,8-6=2,4-2=2,4-3=1,9-6=3,8,2,10,14,8,6,1,2,1,10,12,-1,二、表上作业法,2、解的最优性检验闭回路法,某空格的检验数是以该空格为第一个顶点，某回路的奇数顶点运价和减去其偶数顶点运价和。,原问题,设其对偶变量为：,2、解的最优性检验对偶变量法,二、表上作业法,对偶问题:,考虑原问题变量xj的检验数为：,二、表上作业法,假设已得到一个基可行解，其基变量为：,则有：,s=m+n-1,则运输问题变量xij的检验数为：,二、表上作业法,方程组有m+n-1个方
7、程。 因为运输表中每行和每列均有基变量，因此上面方程组含有全部m+n个对偶变量。 故解不唯一，其解称为位势。 若上述方程的某组解满足对偶问题的所有条件，即：,此时，原问题与对偶问题均可行，故达到最优。 其解分别为：,二、表上作业法,例：,8,2,10,14,8,6,二、表上作业法,1,0,-4,2,9,3,10,1,2,1,-1,10,12,改进的方法是在运输表中找出这个空格对应的闭回路，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。,3、解的改进闭回路调整法,二、表上作业法,解改进的具体步骤 (1)以xij为换入变量，找出它在运
8、输表中的闭回路； (2)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号； (3)在闭回路上的所有偶数顶点中，找出运输量最小的顶点(格子)，以该格中的变量为换出变量； (4)以换出变量的运输量为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。 然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。,二、表上作业法,例：,二、表上作业法,min(6,2)=2,2-2=0
9、,0+2=2,6-2=4,10+2=12,例：,8,2,12,14,8,4,0,2,2,9,12,1,由于所有非基变量的检验数全非负，故这个解为最优解。 又由于非基变量有零检验数，所以有无穷多最优解。,二、表上作业法,练习题,二、表上作业法,练习题,练习题,二、表上作业法,练习题,练习题,二、表上作业法,答案,二、表上作业法,1）若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取小于零的检验数中最小者对应的变量为换入变量。 2）当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重(
10、无穷多)最优解。,4、需要说明的几个问题,二、表上作业法,3）（二 ）退化 某一基变量 的值为0 初始解 在确定初始解的供需关系时，若在确定（i, j ） 的数字时，要划去第i行,第j列。为使在产销平衡表上有m+n-1个数字格，须在第i 行或j列中 （ 非i,j ) 选一数字格为0。 退化解 闭回路中有（ - ）标记中有两个或以上相等的最小数。调整后出现退化解，必须在一数字格中填入0，以表明其为基变量。,二、表上作业法,三、运输问题的进一步讨论,上一节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实际上，在很多运输问题中，总产量不等于总销量。,表上作业法 以产销平衡 为前提。
11、,1、产销不平衡的运输问题,三、运输问题的进一步讨论,2,3,2,1,3,4,1,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,例：假设供应量大于需求量,+5,5,d5=5,假想销地,0 0 0,s3=24,三、运输问题的进一步讨论,产大于销,产销不平衡,产销平衡,模型：,三、运输问题的进一步讨论,设 为Ai的贮存量。,将多余物原地贮存。,令：,三、运输问题的进一步讨论,理解： 产 销 假想有一销地 j=n+1 销量为 运价,模型：,三、运输问题的进一步讨论,三、运输问
12、题的进一步讨论,例： 某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸厂到各用户的单位运价如表315所示，请确定总运费最少的调运方案。,三、运输问题的进一步讨论,解：由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。增加一假想销地B5，用表上作业法求解。,三、运输问题的进一步讨论,三、运输问题的进一步讨论,2、有转运的运输问题,在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运列某个中间转运站(可能是另外的产地、销地或中间转
13、运仓库)，然后再转运到销售目的地。有时，经转运比直接运到目的地更为经济。因此，在决定运输方案时有必要把转运也考虑进去。,三、运输问题的进一步讨论,2、有转运的运输问题,转运量 t1 t2 t3 t4 t5 t6 t7,供应量,需求量,xij,转运量 t1 t2 t3 t4 t5 t6 t7,假设单位运转费用为ti，则线性规划模型为：,三、运输问题的进一步讨论,第二项为常数，对求解结果无影响，可去掉。,模型变为下列形式：,这是一个产销平衡运输问题的数学模型。可以列出其运价表，用表上作业法求解。,其运价表形式如下（注意其中对角线上的运价值）：,建立一般意义上的数学模型，设： ai：第i个产地的产量
14、(净供应量)； bj：第j个销地的销量(净需要量)； xij：由第i个发送地运到第j个接收地的物品数量； cij：由第i个发送地到第j个接收地的单位运价， ti：第i个地点转运物品的数量； ci：第i个地点转运单位物品的费用。 将产地和销地统一编号，并把产地排在前面。销地排在后面，则有：,令：,建立数学模型：,注：所有i=j，cij=-ci,a1a5 b1b5 Q c1c5 c11c55,例：如图所示是一个运输系统，它包括二个产地（1和2）、二个销地(4和5)及一个中间转运站(3)，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的
15、转运单价，试确定最优运输方案。,运用最小元素法，求初始运输方案，如下表：,最优运输方案如下表：,一、回答问题 1、在运输问题数学模型中，为什么模型的(m+n)个约束中最多只有(m+n-1)个是独立的? 2试述用最小元素法确定运输问题的初始基可行解的基本思路。 3如何用闭回路法求检验数？ 4 沃格尔法的基本思想是什么？什么是罚数？ 5在解的改进过程中，如何确定调整量？ 6如何把一个产销不平衡的运输问题(含产大于销和销大于产)转化为产销平衡的运输问题。,练习题,二、判断下列说法是否正确 (1)运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无
16、界解，无可行解； (2)在运输问题中，只要给出一组合(m+n-1)个非零的xij，且满足xij=ai， xij=bj，就可以作为一个初始基可行解； (3)表上作业法实质上就是求解运输问题的单纯形法； (4)按最小元素法(或伏格尔法)给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；,练习题,(5)如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k，最优调运方案将不会发生变化； (6)如果运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k，最优调运方案将不会发生变化； (7)当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值,1，2，6不对,练习题,三、用位势法（对偶变量法）求其检验数。,练习题,四、运用举例,例 1 、某
