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

Chapter3 运输运输问题问题(Transportation Problem)运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用 本章主要内容：本章主要内容：本章主要内容：本章主要内容：1 从从m个发点个发点 向向n个收点个收点 发送某种货物发送某种货物.发点的发发点的发量为量为 ，收点的收量为收点的收量为 。由。由 运运往往 单位货物的运费为单位货物的运费为 ，问如何调配，问如何调配，才能使运费最省？才能使运费最省？问题的提出问题的提出2.表表1 产销平衡表产销平衡表 上述数据可以汇总于上述数据可以汇总于表格中表格中,如下如下:表表2 单位运价表单位运价表 3.运输问题的数学模型 设设xij代表为从第代表为从第i个产地调运给第个产地调运给第j个销地的物资个销地的物资的数量的数量.在产销平衡的条件下，即在产销平衡的条件下，即 使总的运费支出最小，可以表为以下数学形式：使总的运费支出最小，可以表为以下数学形式：4.运输问题的约束方程组系数矩阵及特征运输问题的约束方程组系数矩阵及特征1.矩阵矩阵A是一个是一个m+n行行mn列的矩阵，它的秩为列的矩阵，它的秩为m+n-1。2.运输问题应该有运输问题应该有m+n-1个基变量。个基变量。3.3.xij的系数列向量为：的系数列向量为：m行n行5.表上作业法表上作业法6.表上作业法的基本思路：表上作业法的基本思路：确定初始调运方案确定初始调运方案最优性检验最优性检验改进方案改进方案 7.1 确定初始基可行解确定初始基可行解 运输问题确定初始基可行解，就是求出运输问运输问题确定初始基可行解，就是求出运输问题的初始调运方案题的初始调运方案.确定初始基可行解的方法有确定初始基可行解的方法有最小元素法最小元素法伏格尔法伏格尔法8.【例例2-12-1】某公司经销甲产品某公司经销甲产品,下设下设3 3个加工厂个加工厂A A1 1、A A2 2、A A3 3，产品分别运往销售点，产品分别运往销售点B1、B2、B3、B4，各工厂，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示的运价如下表所示：（：（运输问题供需平衡表和运价表运输问题供需平衡表和运价表如下），求总运费最少的调运方案。如下），求总运费最少的调运方案。销地产地B1B2B3B4发量（T）A13113107A219284A3741059收量（T）3656表3-39.思路：思路：为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、最小元素法、最小元素法10.1.最小最小元素法元素法314633Z=43+310+31+12+64+35=86Z=43+310+31+12+64+35=86该方案总运费：该方案总运费：（思想：就近供应）（思想：就近供应）不不能能同同时时划划去去行行和和列列保证填保证填有运量有运量的格子的格子为为m+n-1表3-411.最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多花几倍的运费，从而使整个运输费用增加。55552.沃格尔法沃格尔法沃格尔法考虑到：一个产地的产品假如不能按照最小运费就近供应，就考虑次小运费，这就有个差额。如果差额不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果差额很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。12.沃格尔法计算步骤：沃格尔法计算步骤：1)分别算出各行、各列的最小运费与次小运费的差额。2)从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。13.2.伏格尔法伏格尔法 2 5 1 3 0 1 1 表表3-66 2 1 3 0 1 2 3 2 1 2 0 1 3 1 2 7 6 521表3-5Z=8514.v1 若有两个以上相同的最大差值，可任取其一。v2 剩下一行或者一列有空格，填数字，不能划掉。v3 计算行差，列差时，已经划去的列或者行不再考虑。15.销产B1B2B3产量A151 812A224114A33 674销量 91011例例例例用用用用伏格尔法伏格尔法伏格尔法伏格尔法求初始调运方案求初始调运方案求初始调运方案求初始调运方案16.销产B1B2B3产量A1210 12A231114A34 4销量 91011初始调运方案初始调运方案17.2.2 最优解的判别最优解的判别 判别办法是计算判别办法是计算空格空格(非基变量非基变量)的检验数的检验数,因为运因为运输问题的目标函数是实现最小化输问题的目标函数是实现最小化,所以当所有空格处所以当所有空格处的的检验数大于等于零检验数大于等于零时时,为最优解为最优解.下面分别介绍两种计算检验数的方法下面分别介绍两种计算检验数的方法:(1)闭回路法闭回路法(2)(2)位势法位势法18.闭回路法闭回路法 闭回路：从闭回路：从空格空格出发画出发画水平水平(或垂直或垂直)直线，遇到直线，遇到填有运量填有运量的方格（数字格）的方格（数字格）可转可转90，然后继续前进，然后继续前进，直到到达出发的空格所形成的闭合回路。直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。调运方案的任意空格一定存在唯一闭回路。销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656表3-719.5 10 4 7A3 8 2 9 1A2 10 3 11 3A1B4B3B2B1 销地产地633431计算最小元素法得到的初始基可行解的检验数计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)3+(-1)3+(+1)2+(-1)1=1(+1)3+(-1)3+(+1)2+(-1)1=1调整后总运费增加：调整后总运费增加：空格处检验数为1表3-820.5 10 4 7A3 8 2 9 1A2 10 3 11 3A1B4B3B2B1 销地产地633431(+1)(-1)(+1)(-1)7-5+10-3+2-1=107-5+10-3+2-1=10调整调整后总运费增加：后总运费增加：空格处检验数为10(-1)(+1)表3-921.检验数表检验数表110121-12 因为存在小于零的检验数因为存在小于零的检验数,所以最小元素法给出的所以最小元素法给出的方案不是最优方案方案不是最优方案.表3-1022.2.位势法位势位势：运输问题的对偶变量称为位势。：运输问题的对偶变量称为位势。因为因为m个供应点个供应点n个需求点的运输问题有个需求点的运输问题有m+n个约束，个约束，因此运输问题就有因此运输问题就有m+n个位势。个位势。行位势行位势:关于供应点关于供应点Ai的约束对应的对偶变量，记为的约束对应的对偶变量，记为 ui,i=1,2,m。列位势列位势:关于需求点关于需求点Bj的约束对应的对偶变量，记为的约束对应的对偶变量，记为vj,j=1,2,n。23.定理定理：运输问题变量运输问题变量xij的检验数的检验数证明：证明：24.位势法位势法求检验数的步骤求检验数的步骤:1.1.在在表表中中下下面面和和右右面面增增加加一一行行和和一一列列,列列中中添添入入ui,行行中中添添入入vj,令令u1=0,按按照照 ,根根据据表表中中已已有有的数字确定所有的的数字确定所有的ui及及vj;2.2.计算所有空格处的检验数计算所有空格处的检验数.25.2 -1 3010-5 9检检验验数数表表121-11012 24=-10，当前方案，当前方案 不是最优方案。不是最优方案。最最优优方方案案判判别别准准则则表3-1226.2.3 2.3 闭回路调整法改进方案闭回路调整法改进方案xpq为换入变量为换入变量 从从(p,qp,q)空格开始画闭回路，其它转角点都是空格开始画闭回路，其它转角点都是填有运量的方格，并从填有运量的方格，并从(p,qp,q)空格开始给闭回路上空格开始给闭回路上的点按的点按+1+1，-1-1，+1+1，-1-1编号，编号，-1-1格的最小运量格的最小运量为调为调整量。整量。表3-1327.找到最小调整量以后找到最小调整量以后,按照闭回路上的正、负按照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。号，分别加上和减去此值，得到新的运输方案。销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656 再用闭回路法或者位势法求检验数，得到下表再用闭回路法或者位势法求检验数，得到下表:表表3-1428.销销产产B1B2B3B4供量供量A102 7A22 14A39 129销量销量 3656这时所有的检验数都非负，表中的解就是最优解这时所有的检验数都非负，表中的解就是最优解.表3-1529.销销产产B1B2B3B4供量供量A137 6 45A224 3 22A34 38 53销量销量 3322例求该运输问题的最优解30.v表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或伏格尔法）元素法或伏格尔法）求检验数闭回路或位势法求检验数闭回路或位势法所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价31.表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取值得到改善，但通常取ij0中最小者对应的变量为换入变量。中最小者对应的变量为换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。则该问题有无穷多最优解。32.退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个时则需要同时划去一行和一列，这时需要补一个0，以保证，以保证有有(m+n-1)个数字格作为基变量。一般可在划去的行和列的个数字格作为基变量。一般可在划去的行和列的任意空格处加一个任意空格处加一个0即可。即可。利用进基变量的闭回路对解进行调整时，标有负号的利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过最小运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最，选择任意一个最小运量对应的基变量作为换出变量，而经调整后，得到退化小运量对应的基变量作为换出变量，而经调整后，得到退化解。这时另一个数字格必须填入一个解。这时另一个数字格必须填入一个“0”以示它为基变量。以示它为基变量。33.销地产地B1B2B3B4产量A116A210A322销量81412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数是检验数是 0，经过调整，可得到另一个最优解。，经过调整，可得到另一个最优解。其中绿色是非基变量检验数，红色为分配量。其中绿色是非基变量检验数，红色为分配量。34.销地产地B1B2B3B4产量A17A24A39销量365620114431377821063 34 41 16 606 6在在x12、x22、x33、x34中任选一个变量作为基变量，例如选中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解35.第三节第三节 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法表上作业法是以产销平衡为前提的：表上作业法是以产销平衡为前提的：实际中，往往遇到产销不平衡的运输问题实际中，往往遇到产销不平衡的运输问题1.1.产大于销（供过于求）产大于销（供过于求）2.2.销大于产（供不应求）销大于产（供不应求）36.产销不平衡运输问题向产销平衡运输问题的转化产销不平衡运输问题向产销平衡运输问题的转化产大于销的运输问题：产大于销的运输问题：数学模型数学模型37.设设xi n+1 是产地是产地Ai 的储存量，化成标准形的储存量，化成标准形其中其中引入虚拟的销地引入虚拟的销地(储存地储存地)（需求量为（需求量为 ），并令），并令各个产地到虚拟销地的单位运费为各个产地到虚拟销地的单位运费为0 0。38.产小于销的运输问题：产小于销的运输问题：引入一个虚拟的产地（产量等于引入一个虚拟的产地（产量等于 ），），并令该虚拟产地到各销地的单位运费为并令该虚拟产地到各销地的单位运费为0 0。39.总供应量为总供应量为1919千吨，而总需求量为千吨，而总需求量为1515千吨千吨例例2：A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分四个城市。已知三个产地今年的蔬菜产量预计分别为别为7千吨、千吨、5千吨和千吨和7千吨；四个城市今年的蔬菜需求量分别千吨；四个城市今年的蔬菜需求量分别为为2千吨、千吨、3千吨、千吨、4千吨和千吨和6千吨；从每个蔬菜产地平均运输千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用千吨蔬菜到各个城市的单位费用(万元万元)见下表，你能否替他见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？们编制一个总运费最省的蔬菜调运方案？单位运费单位运费B1B2B3B4供应量供应量A1211347A2103595A378127需求量需求量234640.需求地需求地生产地生产地B1B2B3B4B5供应量供应量A12113407A21035905A3781207需求量需求量2346400-220430825723343222387最优解中最优解中x15=2,x25=2，表示两个产地没有运出去的蔬菜量。表示两个产地没有运出去的蔬菜量。41.假如例假如例2 2中各产地的蔬菜总产量不是中各产地的蔬菜总产量不是1919千吨，而是千吨，而是1212千吨，就成了一个供不应求的运输问题。千吨，就成了一个供不应求的运输问题。单位运费单位运费B1B2B3B4供应量供应量A1211343A2103594A378125需求量需求量2346单位运费单位运费B1B2B3B4供应量供应量A1211344A2103593A378125A400003需求量需求量2346引入一个虚拟产地引入一个虚拟产地42.例例3 3 设有三个化肥厂供应四个地区的农用化肥。假定等量的设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区年需要量及从各个化肥厂到各地区单位化肥的运价如下表区年需要量及从各个化肥厂到各地区单位化肥的运价如下表所示，试决定使总运费最省的化肥调拨方案。所示，试决定使总运费最省的化肥调拨方案。需求地区需求地区化肥厂化肥厂IIIIIIIV产量产量（万吨）（万吨）A1613221750B1413191560C192023-50最低需求最低需求（万吨）（万吨）3070 010最高需求最高需求（万吨）（万吨）507030不限不限43.这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量160160万吨，四个万吨，四个地区的最低需求量为地区的最低需求量为110110万吨，最高需求为无限。根据现万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到有产量，第四个地区每年最多能分配到6060万吨，这样最高万吨，这样最高需求为需求为210210万吨，大于总产量。为了求得平衡，在产销平万吨，大于总产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂衡表中增加一个假想的化肥厂D D，其产量为，其产量为5050万吨。由于万吨。由于各个地区的需求量包含两部分，其中最低需求量不能由假各个地区的需求量包含两部分，其中最低需求量不能由假想的化肥厂想的化肥厂D D供应，令运价为供应，令运价为M M，而另一部分满足或不满足，而另一部分满足或不满足均可以，故也可以由假想的化肥厂供应，令相应运价为均可以，故也可以由假想的化肥厂供应，令相应运价为0 0。把需求是两种情况的看成两个地区，得到这个问题的产销把需求是两种情况的看成两个地区，得到这个问题的产销平衡表。平衡表。44.需求地区需求地区化肥厂化肥厂IIIIIIIIVIV产量产量（万吨）（万吨）A16161322171750B14141319151560C19192023MM50DM0M0M050需求量需求量（万吨）（万吨）302070 30105045.需求地区需求地区化肥厂化肥厂IIIIIIIIVIV产量产量（万吨）（万吨）A5050B20103060C3020050D302050需求量需求量（万吨）（万吨）302070 301050根据表上作业法可以求得这个问题的最优方案根据表上作业法可以求得这个问题的最优方案46.作业：作业：v课后习题：3.1 表3-423.2 表3-443.3 表3-46、3-483.447.