《运输问题2ppt课件》由会员分享，可在线阅读，更多相关《运输问题2ppt课件（42页珍藏版）》请在金锄头文库上搜索。
1、第三章 运输问题运输问题的典例和数学模型表上作业法产销不平衡的运输问题运用举例本章主要内容：本章主要内容：运输问题的典例和数学模型 例例1 某食品公司从三个加工厂某食品公司从三个加工厂A1、A2 、 A3将其将其消费的糖果运往四个门市部消费的糖果运往四个门市部B1 、B2 、 B3 、 B4销售，各加工厂每天的消费量、各门市部每天的销售销售，各加工厂每天的消费量、各门市部每天的销售量和各加工厂运往各门市部每吨糖果的运价如下表所量和各加工厂运往各门市部每吨糖果的运价如下表所示，问：该食品公司应如何调运可使总运输费用最小示，问：该食品公司应如何调运可使总运输费用最小？B1B2B3B4产量量A131
2、13107A219284A3741059销量量3656运输问题的典例和数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量 = = 总销量总销量2020 设设 xij xij 为从产地为从产地AiAi运往销地运往销地BjBj的运输量，得到以下运的运输量，得到以下运输量表：输量表：Min Z = 3x11+ 11x12+ 3x13 + 10x14 + x21+ 9x22+ 2x23 +8 x24 + 7x31+ 4x32+ 10x33 +5 x34 B1B2B3B4产量量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349销量量3656s.t. x11+
3、 x12 + x13 +x14 = 7 x21 + x22+ x23 +x24 = 4 x31 + x32+ x33 +x34 = 9x11 + x21+ x31=3x12 + x22 +x32= 6x13 + x23 +x33= 5x14 + x24 +x34= 6 xij 0 ( i = 1 , , 3；j = 1, ,4运输问题的典例和数学模型 运输问题的普通方式：产销平衡运输问题的普通方式：产销平衡A1、 A2、 Am 表示某物表示某物资的的m个个产地；地； B1、B2、Bn 表表示某物示某物资的的n个个销地；地；ai 表示表示产地地Ai的的产量；量； bj 表示表示销地地Bj 的的销
4、量；量； cij 表示把物表示把物资从从产地地Ai运往运往销地地Bj的的单位运价。位运价。设 xij 为从从产地地Ai运往运往销地地Bj的运的运输量，得到以下普通运量，得到以下普通运输量量问题的模型：的模型：运输问题的典例和数学模型变化：变化： 1有时目的函数求最大。如求利润最大或营业额最大等；有时目的函数求最大。如求利润最大或营业额最大等； 2当某些运输线路上的才干有限制时，在模型中直接参与当某些运输线路上的才干有限制时，在模型中直接参与约束条件等式或不等式约束约束条件等式或不等式约束)； 3产销不平衡时，可参与假想的产地销大于产时或销产销不平衡时，可参与假想的产地销大于产时或销地产大于销时
5、。地产大于销时。定理定理: : 设有设有m m个产地个产地n n个销地且产销平衡的运输问题，那么基个销地且产销平衡的运输问题，那么基变量数为变量数为m+n-1m+n-1。学习要点：学习要点：1.掌握运输问题模型构造；掌握运输问题模型构造； 2.了解运输问题模型特点。了解运输问题模型特点。 运输问题的典例和数学模型表上作业法 表上作业法是一种求解运输问题的特殊方法，其本质是单表上作业法是一种求解运输问题的特殊方法，其本质是单纯形法。纯形法。步步骤描画描画方法方法第一步第一步求初始根本可行解初始求初始根本可行解初始调运方案运方案最小元素法、最小元素法、元素差元素差额法、法、第二步第二步求求检验数并
6、判数并判别能否得到最能否得到最优解当非基解当非基变量的量的检验数数ijij全都非全都非负时得到最得到最优解，解，假假设存在存在检验数数ij 0ij 0，阐明明还没有到达没有到达最最优，转第三步。第三步。闭回路法和位回路法和位势法法第三步第三步调整运量，即整运量，即换基，基，选一个一个变量出基，量出基，对原运量原运量进展展调整得到新的基可行解，整得到新的基可行解，转入入第二步第二步表上作业法例例 用表上作业法求解例用表上作业法求解例1 1中的问题：中的问题：单位位 销地地 运价运价 产地地产量量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量量
7、3 36 65 56 6问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？表上作业法解：第解：第1步步 求初始方案求初始方案方法方法1：最小元素法：最小元素法 根本思想是就近供应，即从运价最小的地方开场供应调运根本思想是就近供应，即从运价最小的地方开场供应调运，然后次小，直到最后供完为止。，然后次小，直到最后供完为止。B1B2B3B4产量量A17A2 4A39销量量3656311310192741058341633表上作业法总的运的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元元元素差额法对最小元素法进展了改良，思索到产地到销地元素差额法对最小
8、元素法进展了改良，思索到产地到销地的最小运价和次小运价之间的差额，假设差额很大，就选最小的最小运价和次小运价之间的差额，假设差额很大，就选最小运价先调运，否那么会添加总运费。例如下面两种运输方案。运价先调运，否那么会添加总运费。例如下面两种运输方案。85102120151515510总运运费是是z=108+52+151=105最小元素法：最小元素法：表上作业法85102120151551510总运运费z=105+152+51=85后一种方案思索到后一种方案思索到C11与与C21之之间的差的差额是是82=6，假，假设不先不先调运运x21，到后来就有能，到后来就有能够x110，这样会使会使总运运费
9、添加添加较大，从而大，从而先先调运运x21，再是，再是x22，其次是，其次是x12用元素差用元素差额法求得的根本可行解更接近最法求得的根本可行解更接近最优解，所解，所以也称以也称为近似方案。近似方案。表上作业法方法方法2：Vogel法法1从运价表中分别计算出各行和各列的最小运费和次最小运从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。费的差额，并填入该表的最右列和最下行。B1B2B3B4产量量行差行差行差行差额额A177 7A2 41 1A391 1销量量3656列差列差列差列差额额2 25 51 13 3311310192741058表上作业法2再从差
10、值最大的行或列中找出最小运价确定供需关系和再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应终了或得到满足供需数量。当产地或销地中有一方数量供应终了或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。反复反复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B4产量量行差行差行差行差额额A170 0A2 41 1A3 91 1销量量3656列差列差列差列差额额2 25 51 13 33113101927410586 6表上作业法单位位 销地地 运价运价 产地地产量量行差行差额311310719284741059销量量365
11、6列差列差额01135216表上作业法单位位 销地地 运价运价 产地地产量量行差行差额311310719284741059销量量3656列差列差额02132163表上作业法单位位 销地地 运价运价 产地地产量量行差行差额311310719284741059销量量3656列差列差额01221633表上作业法单位位 销地地 运价运价 产地地产量量行差行差额311310719284741059销量量3656列差列差额71266335表上作业法单位位 销地地 运价运价 产地地产量量行差行差额311310719284741059销量量3656列差列差额63351表上作业法第第第第2 2步步步步 最最最最
12、优优解的判解的判解的判解的判别别检验检验数的求法数的求法数的求法数的求法求求出出一一组基基可可行行解解后后，判判别能能否否为最最优解解，依依然然是是用用检验数数来来判判别，记xij的的检验数数为ij由由第第一一章章知知，求求最最小小值的的运运输问题的最的最优判判别准那么是：准那么是：一一切切非非基基变变量量的的检检验验数数都都非非负负，那那么么运运输输方方案案最最优优求求检验数的方法有两种：数的方法有两种： 闭回路法回路法 位位势法法表上作业法n闭回路的概念闭回路的概念为一个闭回路为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边
13、。如下表量的连线为闭回路的边。如下表表上作业法例例 下表中闭回路的变量集合是下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35, x31共有共有8个个顶点，这顶点，这8个顶点间用程度或垂直线段衔接起来，个顶点间用程度或垂直线段衔接起来，组成一条封锁的回路。组成一条封锁的回路。 B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一条回路中的一条回路中的顶点数一定是偶数，回路遇到点数一定是偶数，回路遇到顶点必需点必需转90度与另一度与另一顶点点衔接，表接，表33中的中的变量量x 32及及x33不是不是闭回路的回路的顶点，只是点，只是连
14、线的交点。的交点。 表上作业法闭回路闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组例如变量组 不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组 变量数是奇数，显然不变量数是奇数，显然不是闭回路，也不含有闭回路；是闭回路，也不含有闭回路； 表上作业法用位势法对初始方案进展最优性检验：用位势法对初始方案进展最优性检验：1由由 ij=Cij-Ui+Vj计算位势计算位势Ui ， Vj ，因对基变量而言有，因对基变量而言有 ij=0，即即Cij-Ui+Vj = 0，令，令U1=02再由再由 ij=Cij-Ui+Vj计算非基算非基变
15、量的量的检验数数 ijB1B2B3B4UiA1A2A3Vj3113101927410584363130 0-1-1-5-53 310102 29 91 12 21 1-1-110101212当存在非基当存在非基变量的量的检验数数 kl 0，阐明明现行方行方案案为最最优方方案，否那么案，否那么目的本目的本钱还可以可以进一步一步减小。减小。表上作业法当存在非基当存在非基变量的量的检验数数 kl 0 且且 kl =min ij时，令令Xkl 进基。从表中知可基。从表中知可选X24进基。基。第第3步步 确定换入基的变量确定换入基的变量第第4步步 确定换出基的变量确定换出基的变量以以进基基变量量xik为
16、起点的起点的闭回路中，回路中，标有有负号的最小运量作号的最小运量作为调整量整量，对应的基的基变量量为出基出基变量，并打上量，并打上“以示以示换出作出作为非基非基变量。量。表上作业法B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3( () )( () )( () )( () )调整步整步骤为：在：在进基基变量的量的闭回路中回路中标有正号的有正号的变量加上量加上调整量整量，标有有负号的号的变量减去量减去调整量整量，其他，其他变量不量不变，得到一，得到一组新新的基可行解。然后求一切非基的基可行解。然后求一切非基变量的量的检验数重新
17、数重新检验。1 12 25 5表上作业法当一切非基当一切非基变量的量的检验数均非数均非负时，那么当前，那么当前调运方案即运方案即为最最优方案，如表此方案，如表此时最小最小总运运费：Z =(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj3113101927410585363120 0-2-2-5-53 310103 39 90 02 22 21 112129 9表上作业法表上作业法表上作业法的计算步骤：的计算步骤：分析实践问题列出产销平分析实践问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案最小确定初始调运方案最小元素法或元素法或Vog
18、el法法求检验数位势法求检验数位势法一切一切检验数数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价表上作业法表上作表上作表上作表上作业业法法法法计计算中的算中的算中的算中的问题问题：1假假设运运输问题的某一基可行解有多个非基的某一基可行解有多个非基变量的量的检验数数为负，在，在继续迭代迭代时，取它，取它们中任一中任一变量量为换入入变量均可量均可使目的函数使目的函数值得到改善，但通常取得到改善，但通常取ij0中最小者中最小者对应的的变量量为换入入变量。量。2无无穷多最多最优解解
19、产销平衡的运平衡的运输问题必定存最必定存最优解。假解。假设非基非基变量的量的ij0，那么，那么该问题有无有无穷多最多最优解。解。表上作业法3 退化解：退化解： 表格中普通要有表格中普通要有(m+n-1)个数字格。但有个数字格。但有时在分配运量在分配运量时那么需求同那么需求同时划去一行和一列，划去一行和一列，这时需求需求补一个一个0，以保，以保证有有(m+n-1)个数字格作个数字格作为基基变量。普通可在划去的行和列量。普通可在划去的行和列的恣意空格的恣意空格处加一个加一个0即可。即可。 利用利用进基基变量的量的闭回路回路对解解进展展调整整时，标有有负号的号的最小运量超越最小运量超越2个最小个最小
20、值作作为调整量整量，选择恣意一个最恣意一个最小运量小运量对应的基的基变量作量作为出基出基变量，并打上量，并打上“以示作以示作为非非基基变量。量。表上作业法 销地地产地地B1B2B3B4产量产量A116A210A322销量量81412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数是数是 0，经过调整，可得到另一个最整，可得到另一个最优解。解。 表上作业法 销地地产地地B1B2B3B4产量产量A17A24A39销量量365620114431377821063 34 41 16 6 06 6在在x12、x2
21、2、x33、x34中任中任选一个一个变量作量作为基基变量，例如量，例如选x34例：用最小元素法求初始可行解例：用最小元素法求初始可行解表上作业法 销地地产地地 B1B1B2B2B3B3B4B4产量量A1A18 84 41 12 24 4A2A26 69 94 47 72525A3A35 53 34 43 32626销量量1010101020201515练习练习学习要点：学习要点：1.掌握表上作业法的根本原理；掌握表上作业法的根本原理； 2.能熟练运用表上作业法求解；能熟练运用表上作业法求解； 3.了解表上作业法与单纯形法的联络。了解表上作业法与单纯形法的联络。作业：作业： P101 3.1 表
22、表3-35表上作业法产销不平衡的运输问题及其运用 当总产量与总销量不相等时，称为不平衡运输问题。这当总产量与总销量不相等时，称为不平衡运输问题。这类运输问题在实践中经常碰到，它的求解方法是将不平衡问类运输问题在实践中经常碰到，它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。题化为平衡问题再按平衡问题求解。 当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：产销不平衡的运输问题及其运用 由于由于总产量大于量大于总销量，必有部分量，必有部分产地的地的产量不能全部运送完，量不能全部运送完，必需就地必需就地库存，即每个存，即每个产地地设一个一个仓库，假，假设该仓库为一个虚一个虚拟销地
23、地Bn+1， bn+1作作为一个虚一个虚设销地地Bn+1的的销量量(即即库存量存量)。各。各产地地Ai到到Bn+1的运价的运价为零，即零，即Ci,n+1=0,i=1，m。那么平衡。那么平衡问题的数学模型的数学模型为：详细求解求解时, ,只在只在运价表右端添加运价表右端添加一列一列Bn+1Bn+1，运价，运价为零零, ,销量量为bn+1bn+1即可即可产销不平衡的运输问题及其运用 当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于由于总销量大于量大于总产量，故一定有些需求量，故一定有些需求地不完全地不完全满足足,这时虚虚设一个一个产地地Am+1，产量量为：产销不平衡的运输问题及其运
24、用销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为 ：详细计算时，在运价表的下方添加一行详细计算时，在运价表的下方添加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。 产销不平衡的运输问题及其运用例例2 2 求以下表中极小化运输问题的最优解。求以下表中极小化运输问题的最优解。 B1B2B3B4aiA1211347A2103595A378127bj2346 19 15由于有：由于有：产销不平衡的运输问题及其运用 所以是一个产大于销的运输问题。虚设一个销所以是一个产大于销的运输问题。虚设一个销量为量为B5=19-15=4B5=19-15=4，Ci5=0Ci5=0
25、，i=1,2,3i=1,2,3，表的右边增添一列，表的右边增添一列 ，得到新的运价表。，得到新的运价表。B1B2B3B4B5aiA12113407A21035905A3781207bj23464 19 19产销不平衡的运输问题及其运用例例3 3 设有设有A A、B B、C C三个化肥厂供应三个化肥厂供应1 1、2 2、3 3、4 4四个地域四个地域的农用化肥。假设效果一样，有关数据如下表。试求的农用化肥。假设效果一样，有关数据如下表。试求总费用为最低的化肥调拨方案。总费用为最低的化肥调拨方案。1234产量A1613221750B1413191560C192023-50最低需求量3070010最
26、高需求量507030不限产销不平衡的运输问题及其运用解：根据题意，作出产销平衡与运价表解：根据题意，作出产销平衡与运价表: :最低要求必需满足，最低要求必需满足，因此把相应的虚设产地运费取为因此把相应的虚设产地运费取为 M MM M 代表一个很大的正数，代表一个很大的正数，其作用是强迫相应的其作用是强迫相应的 x x取值为取值为0 0。 而最高要求与最低要求而最高要求与最低要求的差允许按需求安排，因此把相应的虚设产地运费取为的差允许按需求安排，因此把相应的虚设产地运费取为 0 0 。对应。对应 4 4的销量的销量 50 50 是思索问题本身适当取的数据，根据是思索问题本身适当取的数据，根据产销
27、平衡要求确定产销平衡要求确定 D D的产量为的产量为 50 50。112344产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050学习要点：学习要点：1.掌握产销不平衡运输问题的模型构造；掌握产销不平衡运输问题的模型构造； 2.掌握表上作业法求解产销不平衡问题时的处置掌握表上作业法求解产销不平衡问题时的处置方法；方法； 3.可以建立产销不平衡运输问题的数学模型，列可以建立产销不平衡运输问题的数学模型，列产销平衡表。产销平衡表。作业：作业：P102 3.1 表表3-36，P103 3.6 产销不平衡的运输问题及其运用
