资源描述
1第四章第四章 运输问题运输问题2一、运输问题的数学模型一、运输问题的数学模型3 问题的提出问题的提出 在许多大型连锁超市的商品供应在许多大型连锁超市的商品供应,物流公司的物资供物流公司的物资供应都牵涉到众多货物的运输问题应都牵涉到众多货物的运输问题.这些问题最终都面临这些问题最终都面临一个如何降低货物运输成本的问题一个如何降低货物运输成本的问题.该问题可用下面的该问题可用下面的方式加以描述方式加以描述:4 问题问题 设有某种物资设有某种物资,该物资共有该物资共有 个产地个产地,产地产地 的产量的产量miA的需求量为的需求量为 且产量和需求量为相等且产量和需求量为相等.,1,2,jbjn 分析分析 一个合适的运输方案即是要确定从第一个合适的运输方案即是要确定从第 个产地个产地i,1,2,iaimjBn为为 该物资另有该物资另有 个销售点个销售点,销售点销售点iAjB,ijc从产地从产地 到销售点到销售点 的单位运输成本为的单位运输成本为 求一个运输求一个运输方案方案,使总运输费用为最小使总运输费用为最小.jjB,ijx到第到第 个需求点个需求点 的物资供应量的物资供应量.假设供应量为假设供应量为 则则5问题的约束条件为问题的约束条件为0.1,2,;1,2,ijxim jn1,1,2,.nijijxaim1,1,2,.mijjixbjns.t.而相应的总运输成本为而相应的总运输成本为.ijijzc x6从而得到问题的数学模型从而得到问题的数学模型0.1,2,;1,2,ijxim jn1,1,2,.nijijxaim1,1,2,.mijjixbjns.t.min .ijijzc x7例例1 试对下面的运输问题建立相应的数学模型试对下面的运输问题建立相应的数学模型.20055655030需求量需求量60158610408104121002012614产量产量销地销地产地产地1B2B3B4B1A2A3A8解解 由前面的讨论容易得到相应的数学模型由前面的讨论容易得到相应的数学模型:1112131421min 146122012zxxxxx222324313233344108106815,xxxxxxx111213142122232431323334100,40,60,xxxxxxxxxxxx11213112223230,50,xxxxxxs.t.913233314243465,55,xxxxxx0,1,2,3;1,2,3,4.ijxij10注注:前面所讨论的是产销平衡的运输问题前面所讨论的是产销平衡的运输问题.若产销不平若产销不平0.1,2,;1,2,ijxim jn1,1,2,.nijijxaim1,1,2,.mijjixbjns.t.min .ijijzc x衡时衡时,相应的模型将分为产大于销或销大于产的运输问相应的模型将分为产大于销或销大于产的运输问题题.当产大于销时当产大于销时,则问题的模型为则问题的模型为:11而当需求量大于供应量时而当需求量大于供应量时,相应的模型为相应的模型为0.1,2,;1,2,ijxim jn1,1,2,.nijijxaim1,1,2,.mijjixbjns.t.min .ijijzc x12二、表上作业法二、表上作业法13 在上面的例中可以看到在上面的例中可以看到:运输问题的数学模型最终归运输问题的数学模型最终归结为一个线性规划的模型结为一个线性规划的模型,并可用相应的解法加以求解并可用相应的解法加以求解,但即使是一个简单的运输问题但即使是一个简单的运输问题,涉及到的变量也是比较涉及到的变量也是比较多的多的,因而求解也较为困难因而求解也较为困难.这里将介绍一种新的解法这里将介绍一种新的解法:表上作业法表上作业法.14 表上作业法的求解步骤表上作业法的求解步骤:求出一个初始可行解求出一个初始可行解;判定当前解是否为最优解判定当前解是否为最优解;解的调整解的调整.15 求初始基可行解求初始基可行解 1.西北角法西北角法 用西北角法求运输问题的初始解的要点是用西北角法求运输问题的初始解的要点是:从西北角从西北角开始按最大可能进行分配开始按最大可能进行分配,直到完成所有分配直到完成所有分配.16例例2 用西北角法求下面运输问题的初始解用西北角法求下面运输问题的初始解.销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020017销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200解解 由西北角法由西北角法,首先分配首先分配 得得1121500,100,xx50010018再对第二列及第三列进行分配再对第二列及第三列进行分配,即有下表即有下表销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010019销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400100100200最后对第三行进行分配最后对第三行进行分配,得下表得下表,20由此得初始解为由此得初始解为112122500,100,400,xxx233334100,100,200.xxx此时对应的运输成本为此时对应的运输成本为 6000.z 21注注 1.用西北角法所得到问题的解与表中的单位运输成用西北角法所得到问题的解与表中的单位运输成2.在表格中在表格中,凡填入数据的单元凡填入数据的单元 称为称为基变量基变量,否则称否则称ijx3.基变量的个数应基变量的个数应 当等式不成立时当等式不成立时,则称该则称该1,mn本无关本无关,因而该解一般与最优解的距离较因而该解一般与最优解的距离较“远远”;为非基变量为非基变量.解是退化的解是退化的.对退化问题对退化问题,需要虚拟基变量来补充基变量需要虚拟基变量来补充基变量的个数的个数,其取值为其取值为0.22例例3 用西北角法求下面问题的初始解用西北角法求下面问题的初始解销地销地产地产地1234产量产量131131072192843741059需求量需求量38542023解解 由西北角法由西北角法,容易得到问题的初始解容易得到问题的初始解销地销地产地产地1234产量产量131131072192843741059需求量需求量385420344542411122233343,4,4,5,4.xxxxx即即:问题的初始解为问题的初始解为并注意到该解是退化的并注意到该解是退化的.此时可令此时可令230 x来增加基变来增加基变 量的个数量的个数.25 2.最小元素法最小元素法 最小元素法的基本想法是最小元素法的基本想法是:按最小成本进行分配按最小成本进行分配.26例例4 用最小元素法求下面运输问题的初始解用最小元素法求下面运输问题的初始解.销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020027销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300解解 由最小元素法由最小元素法,最小成本为最小成本为 故故31300,x311,c28剩下的最小成本分别为剩下的最小成本分别为12232,2,cc1223400,200,xx销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030040020029销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300400200最后有最后有112124100,200,200.xxx10020020030由此得到问题的初始解由此得到问题的初始解111221100,400,200,xxx232431200,200,300.xxx此时对应的运输成本为此时对应的运输成本为3800.z 31例例5 用最小元素法求下面运输问题的初始解用最小元素法求下面运输问题的初始解.销地销地产地产地1234产量产量131131072192843741059需求量需求量38542032解解 由最小元素法得由最小元素法得:销地销地产地产地1234产量产量131131072192843741059需求量需求量38542031483133即即:初始解为初始解为1314212332344,3,3,1,8,1.xxxxxx34 最优解的判定最优解的判定 为判断当前解是否为最优解为判断当前解是否为最优解,需要建立相应的位势需要建立相应的位势.,.1,2,1,2,iju vim jn.ijijcuvijx 若若 为基变量为基变量,则有则有因基变量的个数为因基变量的个数为 故令故令 由此得到所有由此得到所有1,mn10.u 为此定义位势为此定义位势 的位势的位势.35例例6 求下面运输问题的初始解所对应的位势求下面运输问题的初始解所对应的位势.销地销地产地产地1234产量产量132765001004002752360020020020031546300300需求量需求量60040020020036解解 由位势的定义由位势的定义,及及 是基变量是基变量,11x10,u 1111,cuv由此得到由此得到 同样有同样有13.v 1212,cuv得得 再由再由 及及 得得 同理同理22.v 2121cuv13,v 24.u 3432,1,2.vvu 即有下表即有下表:又又可得其它位势可得其它位势:37销地销地产地产地1234产量产量132765001004002752360020020020031546300300需求量需求量60040020020010u 13v 22v 24u 32u 32v 41v 38例例7 求下面运输问题的初始解所对应的位势求下面运输问题的初始解所对应的位势销地销地产地产地1234产量产量131131074321928431374105981需求量需求量38542039解解 由位势的定义可分别得到由位势的定义可分别得到40销地销地产地产地1234产量产量131131072192843741059需求量需求量38542031483110u 33v 410v 21u 12v 35u 29v 41 下面的例子说明对退化问题的处理方式下面的例子说明对退化问题的处理方式42例例8 求下面运输问题的初始解所对应的位势求下面运输问题的初始解所对应的位势销地销地产地产地1234产量产量13113107342192844374105954需求量需求量38542043解解 由位势的定义可分别得到由位势的定义可分别得到44销地销地产地产地1234产量产量13113107342192844374105954需求量需求量38542010u 211v 13v 22u 45此时此时,因基变量的个数因基变量的个数1.mn230,x计算下去计算下去.为此为此,虚拟基变量虚拟基变量势势:故位势无法再继续故位势无法再继续再进一步计算位再进一步计算位46销地销地产地产地1234产量产量131131072192843741059需求量需求量3854203445410u 211v 13v 22u 034v 36u 41v 47 由位势由位势,再定义再定义影响系数影响系数 其定义关系为其定义关系为:若若 为为,ijijx.ijijijcuv非基变量非基变量,则则48例例9 对下面问题求相应的影响系数对下面问题求相应的影响系数.49645132576723200200400600需求量需求量300360025001产量产量4321销地销地产地产地30040020010020020010u 13v 22v 24u 32u 32u 31u 50解解 因因 为非基变量为非基变量,由影响系数的定义由影响系数的定义,有有13x13149,7,51销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030040020010020020010u 13v 22v 24u 32u 32v 31v 97158952 最优解判定方法最优解判定方法 当前解是最优解当前解是最优解0.ij53 解的调整解的调整 若当前解不是最优解若当前解不是最优解,则要进行适当的解的调整则要进行适当的解的调整,以以 1.确定进基变量确定进基变量 :stxmin0.stijijij 2.对当前进基变量对当前进基变量 构造一条闭回路构造一条闭回路:,stx降低运输费用降低运输费用.其具体步骤为其具体步骤为54 闭回路闭回路:从当前非基变量出发从当前非基变量出发,以直线方式向前（后以直线方式向前（后,注意到在闭回路上注意到在闭回路上,除出发顶点外除出发顶点外,其余顶点均为基其余顶点均为基左左,右）前进右）前进,遇到某一个基变量变向遇到某一个基变量变向,直到回到起点直到回到起点.变量顶点变量顶点.55常见的几种闭回路形式常见的几种闭回路形式56 3.在闭回路上确定最大调整量在闭回路上确定最大调整量M.首先在闭回路上给各顶点以编号首先在闭回路上给各顶点以编号:出发顶点标号为出发顶点标号为0,012345依次类推依次类推.例如在下面的回路中例如在下面的回路中,各个顶点的编号为各个顶点的编号为:57 最大调整量最大调整量 闭回路上编号为奇数顶点的最小运输闭回路上编号为奇数顶点的最小运输M=012345150280200 例如在下面问题中例如在下面问题中,则最大调整量则最大调整量M=150.量量.58 4.求出新解求出新解 在闭回路上进行解的调整在闭回路上进行解的调整:偶数顶点偶数顶点+奇数顶点奇数顶点M,M.59 由此得到求解运输问题的具体方法由此得到求解运输问题的具体方法:1.求出问题的初始解（一般用最小元素法）求出问题的初始解（一般用最小元素法）;2.求出位势及影响系数求出位势及影响系数,从而判定是否为最优解从而判定是否为最优解;3.若不是最优解若不是最优解,则进行解的调整则进行解的调整;4.重新进行判定重新进行判定.60例例10 求下面运输问题的最小成本解求下面运输问题的最小成本解销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020061解解 由西北角法得到问题的初始解由西北角法得到问题的初始解:销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010010020062再求出相应的位势及影响系数再求出相应的位势及影响系数.63销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010010020010u 13v 24u 21v 32v 36u 40v 641213141,9,6,2431321,8,2,即有下表即有下表65销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010010020010u 13v 24u 21v 32v 36u 40v 19618266由于由于 是最小的负数是最小的负数,故以故以 为进基变量为进基变量,构构318 31x3133232131,xxxxx即即造闭回路造闭回路:67销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010010020010u 13v 24u 21v 32v 36u 40v 19618268由此得最大调整量由此得最大调整量 从而得到新解从而得到新解.注意到该解注意到该解M100,210,x是退化的是退化的,因而需要虚拟基变量因而需要虚拟基变量:令并进一步计令并进一步计算位势和影响系数算位势和影响系数:69销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010010020070销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200071销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 24u 32u 32v 48v 21v 19296872最小影响系数为最小影响系数为249,闭回路为闭回路为:2434312124,xxxxx最大调整量最大调整量 即有即有M0,73销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200074销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200075销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 25u 32u 37v 48v 210v 80231976最小影响系数为最小影响系数为128,12222434311112,xxxxxxx构造闭回路构造闭回路:77销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200010u 13v 25u 32u 37v 48v 210v 80231978最大调整量最大调整量 由此得到新解由此得到新解:M200,79销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400200200020020080销地销地产地产地1234产量产量132765003002002752360020020020031546300300需求量需求量60040020020081再一次计算位势和影响系数再一次计算位势和影响系数,得得82销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030030020020020020010u 13v 23u 32u 31v 40v 22v 86571883由于由于 故当前解为最优解故当前解为最优解,最优解值最优解值0,ij3600.ijijzc x84注注 由于在上题的解题中的初始解是通过西北角法得到由于在上题的解题中的初始解是通过西北角法得到的的,因而求解过程比较烦琐因而求解过程比较烦琐.下面我们用最小元素法求下面我们用最小元素法求解该问题解该问题.85例例11 求下面问题的最小成本解求下面问题的最小成本解销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020086解解 由最小元素法得问题的初始解由最小元素法得问题的初始解销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030040020010020020087进一步求出位势及影响系数进一步求出位势及影响系数:88销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030040020010020020010u 13v 22v 24u 32u 32v 41v 97158989最小影响系数为最小影响系数为 闭回路为闭回路为221,2221111222,xxxxx最大调整量最大调整量 由此得到新解由此得到新解:M200,90销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030040020010020020020091销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020030030020020020020092注意到该解即为用西北角法求解过程中所得到的最优解注意到该解即为用西北角法求解过程中所得到的最优解.此例说明用最小元素法所得到的初始解一般情况下比此例说明用最小元素法所得到的初始解一般情况下比用西北角法得到的初始解更为优越用西北角法得到的初始解更为优越.93例例12 求下面运输问题的最小成本解求下面运输问题的最小成本解.销地销地产地产地1234产量产量137641522432123438513需求量需求量11101094094销地销地产地产地1234产量产量137641522432123438513需求量需求量111010940解解 由最小元素法得到问题的初始解由最小元素法得到问题的初始解:1117810395对此初始解对此初始解,再求相应的位势和影响系数再求相应的位势和影响系数:96销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量11101094010u 36v 44v 22u 32u 14v 21v 16512197最小影响系数最小影响系数312,31331314242131,xxxxxxx即有下表即有下表:闭回路为闭回路为98销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量11101094010u 36v 44v 22u 32u 14v 21v 16512199最大调整量为最大调整量为 由此得到新解由此得到新解M3,销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量1110109403310010358344234825410673409101011需求量需求量133122151产量产量4321销地销地产地产地101计算相应的位势及影响系数计算相应的位势及影响系数:102销地销地产地产地1234产量产量13764151052243212843438513310需求量需求量11101094010u 36v 44v 22u 30u 14v 23v 143112103最小影响系数最小影响系数 取取 为进基变量为进基变量,则闭回则闭回11231,23x2324141323,xxxxxM4,最大调整量为最大调整量为 由此得到新解由此得到新解:路为路为104销地销地产地产地1234产量产量13764151052243212843438513310需求量需求量1110109404105销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量111010940106再计算位势及影响系数再计算位势及影响系数:107销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量11101094010u 36v 44v 23u 31u 15v 24v 232313108最小影响系数最小影响系数 取取 为进基变量为进基变量,则闭回路为则闭回路为112,11x1113232111,xxxxxM6,最大调整量为最大调整量为109销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量1110109406110销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量111010940111进一步计算位势和影响系数进一步计算位势和影响系数112销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量11101094010u 34v 44v 21u 31u 13v 22v 303152113最小影响系数最小影响系数 回路回路241,2414112124,xxxxx最大调整量为最大调整量为 从而得到新解从而得到新解:M2,114销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量1110109402115销地销地产地产地1234产量产量13764158722432121023438513310需求量需求量111010940116计算位势和影响系数计算位势和影响系数,得得117销地销地产地产地1234产量产量13764158722432121023438513310需求量需求量11101094010u 13v 44v 22u 35v 22v 31u 511420118因因 故当前解为最优解故当前解为最优解,且最小成本为且最小成本为 0,ij128.z 119例例13 求解下面的运输问题求解下面的运输问题:销地销地产地产地1234产量产量1347128251357395285需求量需求量549220120解解 由最小元素法得初始解由最小元素法得初始解:销地销地产地产地1234产量产量1347128251357395285需求量需求量549220453512121计算位势计算位势,得得销地销地产地产地1234产量产量1347128512251357433952855需求量需求量54922010u 13v 37v 412v 24u 35u 25v 1631151122此时最小影响系数此时最小影响系数 回路为回路为243,2423131424,xxxxx最大调整量最大调整量 由此得到新解由此得到新解M2,123销地销地产地产地1234产量产量1347128512251357433952855需求量需求量549220124销地销地产地产地1234产量产量1347128512251357433952855需求量需求量5492202125销地销地产地产地1234产量产量1347128532513574123952855需求量需求量549220126再计算位势和影响系数再计算位势和影响系数,得得127销地销地产地产地1234产量产量1347128532513574123952855需求量需求量54922010u 13v 37v 49v 24u 35u 25v 1631154128此时最小影响系数此时最小影响系数 回路为回路为121,1213232212,xxxxx最大调整量最大调整量 由此得到新解由此得到新解M3,129销地销地产地产地1234产量产量1347128532513574123952855需求量需求量549220130销地销地产地产地1234产量产量1347128532513574123952855需求量需求量5492203131销地销地产地产地1234产量产量1347128532513571423952855需求量需求量549220132再计算位势和影响系数再计算位势和影响系数,得得133销地销地产地产地1234产量产量1347128532513571423952855需求量需求量54922010u 13v 36v 48v 23u 34u 24v 5410541134因因 故当前解为最优解故当前解为最优解,且最小成本为且最小成本为 0,ij60z 135三、几类特殊的运输问题三、几类特殊的运输问题136 在前面所讨论的是产销平衡的运输问题在前面所讨论的是产销平衡的运输问题,实际工作中实际工作中遇到的更多的是产销不平衡的运输问题遇到的更多的是产销不平衡的运输问题.由于在处理中由于在处理中是把产销不平衡的运输问题化为产销平衡的运输问题加是把产销不平衡的运输问题化为产销平衡的运输问题加以解决以解决,故本段中我们将其归为特殊的运输问题来解决故本段中我们将其归为特殊的运输问题来解决.137 1.产销不平衡的运输问题产销不平衡的运输问题 产大于销的运输问题产大于销的运输问题 设运输问题中设运输问题中,产量总和大于需求量的总和产量总和大于需求量的总和,即有即有11.mnijijab为此为此,虚拟需求点虚拟需求点 需求量为需求量为1,nB111.mnnijijbab138运输成本均为运输成本均为 从而将问题转化为产销平衡从而将问题转化为产销平衡,10.i nc的问题的问题.139销地销地产地产地123产量产量1295352461015需求量需求量1510155040例例14 求解运输问题求解运输问题140解解 虚拟第四个需求点虚拟第四个需求点,由此得下表由此得下表销地销地产地产地1234产量产量129503524610015需求量需求量1510151050141由最小元素法由最小元素法,容易得到问题的初始解容易得到问题的初始解:销地销地产地产地1234产量产量129503524610015需求量需求量1510151050计算位势和影响系数得计算位势和影响系数得:101015105142销地销地产地产地1234产量产量129503515101024610015105需求量需求量151015105010u 25u 12v 21v 35v 40v 835143最小影响系数最小影响系数 回路回路245,2414132324,xxxxx最大调整量最大调整量 由此得到新解由此得到新解M5,144销地销地产地产地1234产量产量129503515101024610015105需求量需求量15101510505145销地销地产地产地1234产量产量12950351515524610015105需求量需求量1510151050146相应的位势和影响系数为相应的位势和影响系数为销地销地产地产地1234产量产量12950351515524610015105需求量需求量151015105010u 12v 26v 35v 40v 20u 325147因因 故当前解为最优解故当前解为最优解,且最小成本为且最小成本为 0,ij165.z 148 销大于产的运输问题销大于产的运输问题11.nmjijiba为此为此,虚拟产地虚拟产地 产量为产量为1,mA111.nmmjijiaba 设运输问题中设运输问题中,需求量总和大于产量的总和需求量总和大于产量的总和,即有即有运输成本均为运输成本均为1,M.mjc的问题的问题.从而将问题转化为产销平衡从而将问题转化为产销平衡149例例15 求下面运输问题的最小费用解求下面运输问题的最小费用解.销地销地产地产地123产量产量18561202151012803391080需求量需求量1407090 280300150解解 由前面讨论由前面讨论,虚拟产地虚拟产地 产量为产量为4,A3341120.jijiaba则有下表则有下表:151销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300152由最小元素法得问题的初始解由最小元素法得问题的初始解,并计算位势和影响系数并计算位势和影响系数153销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208070504040154销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 2080705010u 19v 25v 36v 26u 36u 114040101049uM43155最小影响系数最小影响系数 回路回路111,1113232111,xxxxx最大调整量最大调整量 由此得到新解由此得到新解M40,156销地销地产地产地123产量产量1856120407010215101280803391080804MMM2020需求量需求量1407090300157销地销地产地产地123产量产量1856120407010215101280803391080804MMM2020需求量需求量140709030010u 18v 26u 35u 25v 36v 119948uM32158最小影响系数最小影响系数 回路回路221,2223131222.xxxxx最大调整量最大调整量 由此得到新解由此得到新解:M70,159销地销地产地产地123产量产量1856120408021510128070103391080804MMM2020需求量需求量1407090300160销地销地产地产地123产量产量1856120408021510128070103391080804MMM2020需求量需求量140709030010u 18v 26u 35u 24v 36v 1109148uM42161因因 故当前解为最优解故当前解为最优解,且最小成本为且最小成本为 0,ij1860.z 162 注注:在上题中在上题中,若先分配若先分配4220,x由此得到初始解由此得到初始解:163销地销地产地产地123产量产量1856120507021510128060203391080804MMM2020需求量需求量1407090300164再计算相应的位势再计算相应的位势,有有165销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v 36v 26u 36u 112060101045uM41166最小影响系数为最小影响系数为414,闭回路为闭回路为41421213232141,xxxxxxx167销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v 36v 26u 36u 112060101045uM41168此时最大调整量为此时最大调整量为20,继续迭代继续迭代,所得到的解即为前面所得到的解即为前面解法中的初始解解法中的初始解.169销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 2080507010u 19v 25v 36v 26u 36u 112060101045uM41170销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208070504040171 2.存在无通行路的运输问题存在无通行路的运输问题 所谓存在无通行路的运输问题是指在一个运输问题中所谓存在无通行路的运输问题是指在一个运输问题中,分析分析:对所给条件对所给条件,为使为使 不能成为基变量不能成为基变量,可使相可使相ijxiAjB产地产地 与需求点与需求点 之间不存在相应的运输线路之间不存在相应的运输线路.在此种在此种情况下情况下,求运输方案求运输方案.,ijcM应的运输成本为最大的应的运输成本为最大的.为此可设为此可设 再由前面所再由前面所提供的方法求出最优解提供的方法求出最优解.172例例16 求解下面的运输问题求解下面的运输问题:销地销地产地产地1234产量产量17654502973650387350需求量需求量20403060150173销地销地产地产地1234产量产量1765450297365038M7350需求量需求量20403060150解解 由最小元素法得初始解由最小元素法得初始解5010304020174注意到该解是退化的注意到该解是退化的,故需虚拟基变量故需虚拟基变量.但基变量需在但基变量需在求位势的过程中加以解决求位势的过程中加以解决.先求位势先求位势:175销地销地产地产地1234产量产量176545040102973650203038M735050需求量需求量2040306015010u 26v 44v 31u 176此时此时,位势计算中断位势计算中断,问题在于初始解退化问题在于初始解退化.为此为此,虚拟虚拟220,x基变量基变量,令令 则有则有177销地销地产地产地1234产量产量1765450401029736502003038M735050需求量需求量2040306015010u 26v 44v 31u 21u 18v 32v 13116178此时最小影响系数此时最小影响系数 回路为回路为111,1112222111,xxxxx最大调整量最大调整量 由此得到新解由此得到新解M20,179销地销地产地产地1234产量产量17654502020102973650203038M735050需求量需求量20403060150180计算位势和影响系数后得计算位势和影响系数后得:181销地销地产地产地1234产量产量17654502020102973650203038M735050需求量需求量2040306015010u 26v 44v 31u 21u 17v 32v 31261182因因 故当前解为最优解故当前解为最优解,且最小成本为且最小成本为 0,ij680.z 183例例17 有三个化肥厂供应四个地区农用化肥有三个化肥厂供应四个地区农用化肥.假设等量假设等量的化肥在这些地区使用效果相同的化肥在这些地区使用效果相同.各化肥厂的年产量各化肥厂的年产量,各各地区的需要量和各厂到各地的单位运价如下表所示地区的需要量和各厂到各地的单位运价如下表所示,求求总运费最省的调运方案总运费最省的调运方案.184不限不限307050最高需求最高需求1007030最低需求最低需求50_23201936015191314250172213161产量产量4321 地区地区化肥厂化肥厂185解解 此为产销不平衡的运输问题此为产销不平衡的运输问题.总产量为总产量为160,四个地区的最低需求量为四个地区的最低需求量为110,最高需最高需求量可以设为求量可以设为210.因而是需求量大于产量的问题因而是需求量大于产量的问题.为此为此虚设工厂虚设工厂.再注意到各地区的需求量分为两部分再注意到各地区的需求量分为两部分,一部分一部分是必须满足的是必须满足的,另一部分是可以不满足的另一部分是可以不满足的.由此产生表由此产生表格格.1860M0M0MMM23201919151519171722131613141416210501030702030504503602501443211187 注意对表中第四行中单位成本的理解注意对表中第四行中单位成本的理解.由最小元素法得到问题的初始解由最小元素法得到问题的初始解:18811234411616132217175050214141319151560301020319192023MM501010304M0M0M050302030207030105021018911234411616132217175050214141319151560301020319192023MM501010304M0M0M050302030207030105021010u 213v 114v 35vM20u 114v 35u 45vM45vM45uM190再计算相应的影响系数再计算相应的影响系数:111113142,2,27,22,MM1423242422,24,20,MMM3132330,5,13,M 414142219,19,225,MMM430.191此时此时 为进基变量为进基变量,由此得新解由此得新解33x19211234411616132217175050214141319151560301020319192023MM501030104M0M0M3005020302070301050210193再一次计算位势和影响系数有再一次计算位势和影响系数有19411234411616132217175050214141319151560301020319192023MM501010304M0M0M050302030207030105021010u 213v 114v 35vM20u 114v 35u 45vM45vM45uM195再计算相应的影响系数再计算相应的影响系数111113142,2,17,12,MM1423242412,14,10,MMM3132331,2,23,M 414142219,19,225,MMM40.j以以 为进基变量为进基变量,则有新解则有新解24x19611234411616132217175050214141319151560302010319192023MM5020304M0M0M0503020302070301050210197经过数次换基后得到问题的最优解经过数次换基后得到问题的最优解:122224315,20,40,50.xxxx198 4.具有中转站的运输问题具有中转站的运输问题 某类物资有某类物资有 个产地个产地,产地产地 的产地为的产地为m,iaiA对该类物对该类物资有资有 个需求点个需求点,第第 个需求点的需求量为个需求点的需求量为nj.jb 从产地到达需求点都需经过从产地到达需求点都需经过 个中转站中的某个中转个中转站中的某个中转p站站.启动第启动第 个中转站将发生固定费用个中转站将发生固定费用k,kf相应的单位相应的单位费用分别为费用分别为,.ikkjcd 求运输方案求运输方案,使总运费为最小使总运费为最小.中转站的最大转运量为中转站的最大转运量为.kc199 引入引入 变量变量 0 1,1kkxx,ikkjxy表示启用第表示启用第 个中转站个中转站,k表示经过从表示经过从 个产地到第个产地到第 个中转站及从第个中转站及从第 个中转站到个中转站到ikk第第 个需求点的运输量个需求点的运输量,则问题的目标函数为则问题的目标函数为j11111,pppmnkkikikkjkjkikkjzf xc xd y产量限制产量限制:1,1,2,pikikxaim2001,1,2,mikkkixc xkp 中转站能力限制中转站能力限制:需求量限制：需求量限制：1,1,2,pkjjkybjn 供需平衡限制供需平衡限制:11.1,2,mnikkjijxykp201 由此得到该问题的数学模型由此得到该问题的数学模型:11111min,pppmnkkikikkjkjkikkjzf xc xd y20211111,1,2,1,2,1,2,.1,2,pikikmikkkipkjjkmnikkjijxaimxc xkpybjnxykp20301,1,2,0,0.kikkjxkpxy204四、指派问题四、指派问题205 1.指派问题的数学模型指派问题的数学模型 问题问题 设有设有 项工作项工作,交给交给 个人去完成个人去完成.每个人只能每个人只能nn 如此的问题即称为如此的问题即称为指派问题指派问题.完成其中的一项完成其中的一项.又每人完成其中任何一项工作的代价又每人完成其中任何一项工作的代价为已知为已知,求这样的任务分配方案求这样的任务分配方案,使完成这些工作的总使完成这些工作的总代价为最小代价为最小.206 以以 表示第表示第 人完成第人完成第 项工作所需的代价项工作所需的代价,由此得由此得ijcij111212122212.nnnnnnccccccCccc 如此的矩阵称为指派问题中的如此的矩阵称为指派问题中的代价矩阵代价矩阵.到矩阵到矩阵:207 引入决策变量引入决策变量 :ijx10ijx第第 人完成第人完成第 项工作项工作;ij第第 项工作由其他人完成项工作由其他人完成.j由此得到矩阵由此得到矩阵 注意到注意到:由于每项工作只能由由于每项工作只能由.ijXx一人完成及每人只能完成一项工作一人完成及每人只能完成一项工作,故在矩阵中每行和故在矩阵中每行和每列只能有一个每列只能有一个1,其余均为其余均为0.如此的矩阵称为指派问题中的如此的矩阵称为指派问题中的指派矩阵指派矩阵.208例例17 设指派问题中的代价矩阵为设指派问题中的代价矩阵为151812111316109,131710811 1889C则下列矩阵则下列矩阵 121000010001001000,0010000100010010XX209均为指派矩阵均为指派矩阵,其代价分别为其代价分别为 而矩阵而矩阵50,47.310000100,00010001X则不是指派矩阵则不是指派矩阵.所谓求解指派问题的最小值解所谓求解指派问题的最小值解,即为求解这样的矩阵即为求解这样的矩阵,使对应的代价为最小使对应的代价为最小.210 分析分析 条件条件:矩阵中每行每列的元素只有一个是矩阵中每行每列的元素只有一个是1,其余均为其余均为11 1,2,.nijjxin行行:列列:11 1,2,.nijixjn01.ijijxx零的数学表达式为零的数学表达式为:211,1.nijiji jzc x由此得到问题的模型为由此得到问题的模型为:而相应的代价为而相应的代价为212111 1,2,.1 1,2,.nijjnijixinxjns.t.min,1.nijiji jzc x01.,1,2,.ijijxxi jn213 2.指派问题的求解方法指派问题的求解方法 设代价矩阵为设代价矩阵为 我们用下面的方法求其最我们用下面的方法求其最,ijnnCc 每行减去该行的最小数每行减去该行的最小数;每列减去该列的最小数每列减去该列的最小数;每行每列至少一个零每行每列至少一个零.判断是否有判断是否有 个独立的零个独立的零,若有若有,则在指派矩阵中则在指派矩阵中,n小值解小值解:相应元素取相应元素取1,其余为其余为0.214 所谓有所谓有 个独立的零个独立的零,即指这些零应分布在不同的行即指这些零应分布在不同的行n判断方法判断方法:用最少的横线和竖线将所有的零划去用最少的横线和竖线将所有的零划去,若最若最列上列上.,nn少的线数为少的线数为 则一定有则一定有 个独立的零个独立的零.215例例18 求下面指派问题中的最小值解求下面指派问题中的最小值解.272225202826.283230C解解272225202826283230行行503086042列列501084040216注意到在最后表中注意到在最后表中,每行每列都有零的存在每行每列都有零的存在.501084040 在下面矩阵中在下面矩阵中,选独立的零选独立的零:则问题的最优解为则问题的最优解为 其余其余1221331,xxx0.ijx 即相应的指派矩阵为即相应的指派矩阵为217010100,001X最小代价为最小代价为22203072.z 218例例19 求下面指派问题的最小值解求下面指派问题的最小值解:14171820121519201617201819212023C解解14171820121519201617201819212023行行0346037801420214列列0234026600300102219注意到注意到,对表对表0234026600300102可以用可以用3条线将所有的零划去条线将所有的零划去,因而没有因而没有4个独立的零个独立的零.对此我们有下面的迭代次序对此我们有下面的迭代次序:220在所有未划去的数中找最小数在所有未划去的数中找最小数;未划去的数减去该数未划去的数减去该数;交叉点加上该数交叉点加上该数,其余不变其余不变;继续判定继续判定.在上例中在上例中:2210234026600300102最小数为最小数为2,由此得由此得:0012004420302102此时有此时有4个独立的零个独立的零,122134431,xxxx因而最优解为因而最优解为 222其余其余 最小代价为最小代价为0.ijx 67.z 注意到该问题的最优解是不唯一的注意到该问题的最优解是不唯一的.但最小值相同但最小值相同.2232024222634364039.3831353212181716C例例20 求指派问题的最小值解求指派问题的最小值解:解解0426026570410654行行20242226343640393831353212181716列列04050244702006332240405024470200633最小数为最小数为2,继续迭代继续迭代2405002290200411最优解为最优解为 其余其余 最小最小132234411,xxxx0.ijx 225代价为代价
展开阅读全文