运筹学第3章运输问题.

Chapter3运输问题(TransportationProblem)运输问题的数学模型表上作业法运输问题的应用本章主要内容：2从m个发点向n个收点发送某种货物.发点的发量为，收点的收量为。由运往单位货物的运费为，问如何调配，才能使运费最省？问题的提出mAAA,,21nBBB,,21jBiAiajbiAjBjic.题否则称为非平衡运输问运输问题，，称此运输问题为平衡若jiba3表1产销平衡表销地产地12…n产量1a12a2┆┆mam销量b1b2…bn上述数据可以汇总于表格中,如下:表2单位运价表销地产地12…n1c11c12…c1n2c21c22…c2n┆┆┆┆mcm1cm2…cmn4运输问题的数学模型设xij代表为从第i个产地调运给第j个销地的物资的数量.在产销平衡的条件下，即使总的运费支出最小，可以表为以下数学形式：njjmiiba110,,1,,1..min1111ijjmiijinjijminjijijxnjbxmiaxtsxcz5运输问题的约束方程组系数矩阵及特征11121212221211.......111.......1.........11.......111111............................1111nnmmmnxxxxxxxxxA1.矩阵A是一个m+n行mn列的矩阵，它的秩为m+n-1。2.运输问题应该有m+n-1个基变量。3.xij的系数列向量为：m行n行(0....1...0....1...0)TijimjPee6表上作业法7表上作业法的基本思路：确定初始调运方案最优性检验改进方案81确定初始基可行解运输问题确定初始基可行解，就是求出运输问题的初始调运方案.确定初始基可行解的方法有最小元素法伏格尔法9【例2-1】某公司经销甲产品,下设3个加工厂A1、A2、A3，产品分别运往销售点B1、B2、B3、B4，各工厂的日产量和各销售点的日需求量及各工厂到各销售点的运价如下表所示：（运输问题供需平衡表和运价表如下），求总运费最少的调运方案。销地产地B1B2B3B4发量（T）A13113107A219284A3741059收量（T）3656表3-310思路：为了减少运费，应优先考虑单位运价最小(或运距最短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、最小元素法111.最小元素法销产B1B2B3B4产量311310A171928A2474105A39销量3656314633Z=4×3+3×10+3×1+1×2+6×4+3×5=86该方案总运费：（思想：就近供应）不能同时划去行和列保证填有运量的格子为m+n-1表3-412最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能在其他供销点多花几倍的运费，从而使整个运输费用增加。55552.沃格尔法沃格尔法考虑到：一个产地的产品假如不能按照最小运费就近供应，就考虑次小运费，这就有个差额。如果差额不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果差额很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。13沃格尔法计算步骤：1)分别算出各行、各列的最小运费与次小运费的差额。2)从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。142.伏格尔法销地产地B1B2B3B4产量A17A24A39销量3656两最小元素之差产地销地B1B2B3B4A1311310A21928A374105两最小元素之差①2513①011表3-6[]6②213②0123③212③01[][]3④12④76[]521表3-5Z=85151若有两个以上相同的最大差值，可任取其一。2剩下一行或者一列有空格，填数字，不能划掉。3计算行差，列差时，已经划去的列或者行不再考虑。16销产B1B2B3产量A151812A224114A33674销量91011例用伏格尔法求初始调运方案17销产B1B2B3产量A121012A231114A344销量91011初始调运方案182.2最优解的判别判别办法是计算空格(非基变量)的检验数,因为运输问题的目标函数是实现最小化,所以当所有空格处的检验数大于等于零时,为最优解.下面分别介绍两种计算检验数的方法:(1)闭回路法(2)位势法19①闭回路法闭回路：从空格出发画水平(或垂直)直线，遇到填有运量的方格（数字格）可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格一定存在唯一闭回路。销产B1B2B3B4供量A1527A2314A3639销量3656表3-72051047A38291A2103113A1B4B3B2B1销地产地633431计算最小元素法得到的初始基可行解的检验数(+1)(-1)(+1)(-1)(+1)×3+(-1)×3+(+1)×2+(-1)×1=1调整后总运费增加：空格处检验数为1表3-82151047A38291A2103113A1B4B3B2B1销地产地633431(+1)(-1)(+1)(-1)7-5+10-3+2-1=10调整后总运费增加：空格处检验数为10(-1)(+1)表3-922销地产地B1B2B3B4A1A2A3检验数表110121-12因为存在小于零的检验数,所以最小元素法给出的方案不是最优方案.表3-10232.位势法位势：运输问题的对偶变量称为位势。因为m个供应点n个需求点的运输问题有m+n个约束，因此运输问题就有m+n个位势。行位势:关于供应点Ai的约束对应的对偶变量，记为ui,i=1,2,…m。列位势:关于需求点Bj的约束对应的对偶变量，记为vj,j=1,2,…,n。24定理：运输问题变量xij的检验数ijijijcuv11101(,...,,...)10ijijBijijmnijijcCBPcuuvvcuv证明：25位势法求检验数的步骤:1.在表中下面和右面增加一行和一列,列中添入ui,行中添入vj,令u1=0,按照,根据表中已有的数字确定所有的ui及vj;jiijvuC2.计算所有空格处的检验数.)vu(Cjiijij26B1B2B3B4ui311310A11928A274105A3vj2-13010-59检验数表121-1101224=-1＜0，当前方案不是最优方案。最优方案判别准则表3-12272.3闭回路调整法改进方案xpq为换入变量=min{1，3}=1从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。销地产地B1B2B3B4产量A1A2A3364(+1)…┇1(-1)……3(-1)┇…(+1)3749销量3656pqij0min表3-1328找到最小调整量以后,按照闭回路上的正、负号，分别加上和减去此值，得到新的运输方案。销产B1B2B3B4供量A1527A2314A3639销量3656再用闭回路法或者位势法求检验数，得到下表:表3-1429销产B1B2B3B4供量A1027A2214A39129销量3656这时所有的检验数都非负，表中的解就是最优解.表3-1530销产B1B2B3B4供量A137645A224322A343853销量3322例求该运输问题的最优解31表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或伏格尔法）求检验数闭回路或位势法所有检验数≥0找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价32表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij0中最小者对应的变量为换入变量。（2）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。33⑵退化解：※表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。※利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为换出变量，而经调整后，得到退化解。这时另一个数字格必须填入一个“0”以示它为基变量。34销地产地B1B2B3B4产量A116A210A322销量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11检验数是0，经过调整，可得到另一个最优解。其中绿色是非基变量检验数，红色为分配量。35销地产地B1B2B3B4产量A17A24A39销量36562011443137782106341606在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34例：用最小元素法求初始可行解36第三节产销不平衡的运输问题及其求解方法表上作业法是以产销平衡为前提的：11mnijijab实际中，往往遇到产销不平衡的运输问题1.产大于销（供过于求）11mnijijab2.销大于产（供不应求）11mnijijab37产销不平衡运输问题向产销平衡运输问题的转化产大于销的运输问题：11mnijijab1111min(1,2,......)..(1,2,......)0,1,2,......,1,2,......mnijijijnijijmijjiijzcxxaimstxbjnximjn数学模型38设xin+1是产地Ai的储存量，化成标准形111111min(1,2,......)..(1,2,......,1)0,1,2,......,1,2,......1mnijijijnijijmijjiijzcxxaimstxbjnnximjn其中,11110,1,...inmnnijijcimbab引入虚拟的销地(储存地)（需求量为），并令各个产地到虚拟销地的单位运费为0。11mnijijab39产小于销的运输问题：11mnijijab引入一个虚拟的产地（产量等于），并令该虚拟产地到各销地的单位运费为0。11nmjijiba40总供应量为19千吨，而总需求量为15千吨例2：A1、A2、A3三个蔬菜生产地生产的蔬菜主要供应B1、B2、B3、B4四个城市。已知三个产地今年的蔬菜产量预计分别为7千吨、5千吨和7千吨；四个城市今年的蔬菜需求量分别为2千吨、3千吨、4千吨和6千吨；从每个蔬菜产地平均运输1千吨蔬菜到各个城市的单位费用(万元)见下表，你能否替他们编制一个总运费最省的蔬菜调运方案？单位运费B1B2B3B4供应量A1211347A2103595A378127需求量234641需求地生产地B1B2B3B4B5供应量A12113407A21035905A3781207需求量2346400-220430825723343222387最优解中x15=2,x25=2，表示两个产地没有运出去的蔬菜量。42假如例2中各产地的蔬菜总产量不是1