《运筹学-ch3 运输问题（讲义6）-精品文档整理.ppt》由会员分享，可在线阅读，更多相关《运筹学-ch3 运输问题（讲义6）-精品文档整理.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter3 运输规划运输规划(Transportation Problem)(Transportation Problem)运输规划问题的数学模型运输规划问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用 本章主要内容：本章主要内容：本章主要内容：本章主要内容：Page 2运输规划问题的数学模型运输规划问题的数学模型例例3.1 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总地每件物品的运费如下表
2、所示，问：应如何调运可使总运输费用最小？运输费用最小？B1B2B3产量产量A1646200A2655300销量销量150150200Page 3运输规划问题的数学模型运输规划问题的数学模型解：产销平衡问题：总产量解：产销平衡问题：总产量=总销量总销量500 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输的运输量，得到下列运输量表：量表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200Min C=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x
3、23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2；j=1、2、3）Page 4运输规划问题的数学模型运输规划问题的数学模型运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、A2、Am 表示某物资的表示某物资的m个产地个产地；B1、B2、Bn 表示某物质的表示某物质的n个销地个销地；ai 表示产地表示产地Ai的产量；的产量；bj 表示销地表示销地Bj 的销量；的销量；cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。的单位运价。设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，的运输
4、量，得到下列一般运输量问题的模型：得到下列一般运输量问题的模型：Page 5运输规划问题的数学模型运输规划问题的数学模型Page 6运输规划问题的数学模型运输规划问题的数学模型变化：变化：1）有时目标函数求最大。如求利润最大或营业额最大等；）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。地（产大于销时）。定理定理:设有
5、设有m个产地个产地,n个销地个销地,且产销平衡的运输问题且产销平衡的运输问题,则基变量数至多为则基变量数至多为m+n-1。Page 7表上作业法表上作业法表上作业法是一种求解运输问题的特殊方法，其表上作业法是一种求解运输问题的特殊方法，其实质是实质是单纯形法。单纯形法。步骤步骤描述描述方法方法第一步第一步求初始基可行解（初始调运方案）求初始基可行解（初始调运方案）最小元素法、最小元素法、元素差额法、元素差额法、第二步第二步求检验数并判断是否得到最优解当非基变量的求检验数并判断是否得到最优解当非基变量的检验数检验数 ij ij全都非负时得到最优解，若存在检验全都非负时得到最优解，若存在检验数数
6、ij ij 00，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。闭回路法和位闭回路法和位势法势法第三步第三步调整运量，即换基，选一个变量出基，对原运调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步量进行调整得到新的基可行解，转入第二步Page 8表上作业法表上作业法例例3.2 3.2 某运输资料如下表所示：某运输资料如下表所示：单位单位 销地销地 运价运价 产地产地产量产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量销量3 36 65 56 6问：应如何调运可使总运输费用最小？问：应如何调运可
7、使总运输费用最小？Page 9表上作业法表上作业法解：第解：第1步步 求初始方案求初始方案方法方法1：最小元素法：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调运）基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。，然后次小，直到最后供完为止。B1B2B3B4产量产量A17A2 4A39销量销量3656311310192741058341633Page 10表上作业法表上作业法方法方法2：Vogel法法1）从运价表中分别计算出各行和各列的最小运费和次最小运）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。
8、费的差额，并填入该表的最右列和最下行。B1B2B3B4产量产量行差额行差额行差额行差额A170 0A2 41 1A391 1销量销量3656列差额列差额列差额列差额2 25 51 13 3311310192741058Page 11表上作业法表上作业法2）再从差值最大的行或列中找出最小运价确定供需关系和）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。重复重复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B4产
9、量产量行差额行差额行差额行差额A170 0A2 41 1A3 91 1销量销量3656列差额列差额列差额列差额2 25 51 13 33113101927410586Page 12表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额01135216Page 13表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差额311310719284741059销量销量3656列差额列差额02312163Page 14表上作业法表上作业法单位单位 销地销地 运价运价 产地产地产量产量行差额行差
10、额311310719284741059销量销量3656列差额列差额536312该方案的总运费该方案的总运费:(13)(46)(35)(210)(18)(35)85元元Page 15表上作业法表上作业法第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都
11、非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种：闭回路法闭回路法 位势法（位势法（）Page 16表上作业法表上作业法闭回路的概念闭回路的概念 从某一空格出发，用水平或垂直的线向前划，碰到一个从某一空格出发，用水平或垂直的线向前划，碰到一个合适的合适的有数格就转有数格就转90度，继续向前，直到回到起始空格为止。度，继续向前，直到回到起始空格为止。注：注：1、闭回路没有方向性；、闭回路没有方向性；2、每一空格有且仅有一条闭回路。、每一空格有且仅有一条闭回路。（除起点和终点是同一空格以外，其余顶点都是有数格的（除起点和终点是同一空格以外，其
12、余顶点都是有数格的曲折闭合多边形。）曲折闭合多边形。）Page 17表上作业法表上作业法闭回路闭回路B1B2B3A1X11X12A2 *A3 X32X33A4X41X43空格的检验数空格的检验数 =奇数奇数顶点单位运价顶点单位运价偶数偶数顶点单位运价顶点单位运价Page 18表上作业法表上作业法用用位势法位势法对初始方案进行最优性检验：对初始方案进行最优性检验：1）由）由 ij=Cij-（Ui+Vj）计算位势）计算位势Ui，Vj，因对基变量而言有，因对基变量而言有 ij=0，即即Cij-（Ui+Vj）=0，令，令U1=02）再由）再由 ij=Cij-（Ui+Vj）计算非基变量的检验数）计算非基
13、变量的检验数 ijB1B2B3B4UiA1A2A3Vj3113101927410584363130 0-1-1-5-53 310102 29 9（1 1）（2 2）（1 1）（-1-1）（1010）（1212）当存在非基当存在非基变量的检验变量的检验数数 kl 0，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。Page 19表上作业法表上作业法第第3步步 调整（闭回路调整）调整（闭回路调整）1.调整量调整量 ：取闭回路上偶数顶点最小运量；取闭回路上偶数顶点最小运量；2.步骤步骤：奇数顶点：奇数顶点 ，偶数顶点，偶数顶点Page 2
14、0表上作业法表上作业法B1B2B3B4A1A2A34 4363 31 13 3()()()()1 12 25 5Page 21表上作业法表上作业法当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：Z=(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj3113101927410585363120 0-2-2-5-53 310103 39 9（0 0）（2 2）（2 2）（1 1）（1212）（9 9）Page 22表上作业法表上作业法表上作业法
15、的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价是是否否Page 23例例2：求下列运输问题的最优运输方案：求下列运输问题的最优运输方案单位单位 销地销地 运价运价 产地产地产量产量4 412124 4111116162 210103 3
16、9 910108 85 511116 62222销量销量8 8141412121414表上作业法表上作业法Page 24练习：求下列运输问题的最优运输方案练习：求下列运输问题的最优运输方案单位单位 销地销地 运价运价 产地产地产量产量6 65 54 415153 37 72 22525销量销量202010101010表上作业法表上作业法Page 25例例3：求下列运输问题的最优运输方案：求下列运输问题的最优运输方案单位单位 销地销地 运价运价 产地产地产量产量3 36 62 24 470705 53 33 34 480801 17 75 52 25050销量销量4040303070706060
17、表上作业法表上作业法Page 26表上作业法表上作业法表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的
18、ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。Page 27表上作业法表上作业法（3）退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个时则需要同时划去一行和一列，这时需要补一个0，以保证，以保证有有(m+n-1)个数字格作为基变量。一般可在划去的行和列的个数字格作为基变量。一般可在划去的行和列的任意空格处加一个任意空格处加一个0即可。即可。Page 28作业：求下列运输问题的最优运输方案作业：求下列运输问题的最优运输方案单位单位 销地销地 运价运价 产地产地产量产量1818141
19、4171712121001005 58 81313151510010017177 712129 95050销量销量5050606060608080表上作业法表上作业法Page 29运输问题的应用运输问题的应用1.产销不平衡的运输问题产销不平衡的运输问题 当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这这类运输问题在实际中常常碰到类运输问题在实际中常常碰到,它的求解方法是将不平衡它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。问题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：Page 30运输问题的应用
20、运输问题的应用由于总产量大于总销量，必有部分产地的产量不能全部运送完，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，必须就地库存，即每个产地设一个仓库，假设该仓库为一个假设该仓库为一个虚虚拟销地拟销地Bn+1，bn+1作为一个虚设销地作为一个虚设销地Bn+1的销量的销量(即库存量即库存量)。各。各产地产地Ai到到Bn+1的运价为零，即的运价为零，即Ci,n+1=0,（i=1，m）。则平衡）。则平衡问题的数学模型为：问题的数学模型为：具体求解时具体求解时,只在只在运价表右端增加运价表右端增加一列一列B Bn n+1+1，运价，运价为零为零,销量为销量
21、为b bn n+1+1即可即可Page 31运输问题的应用运输问题的应用 当销大于产时，即：当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求地故一定有些需求地不完全满足不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量，产量为：为：Page 32例例4：求下列运输问题的最优运输方案：求下列运输问题的最优运输方案单位单位 销地销地 运价运价 产地产地产量产量2 211113 34 47 710103 35 59 95 57 78 81 12 27 7销量销量2 23 34 46 6 19 191515表上作业法表上作业法Page 33解：
22、增加虚拟销地解：增加虚拟销地 ，销量为，销量为4，相应运价均为，相应运价均为0单位单位 销地销地 运价运价 产地产地产量产量2 211113 34 40 07 710103 35 59 90 05 57 78 81 12 20 07 7销量销量2 23 34 46 64 4表上作业法表上作业法（建议用最小元素法）（建议用最小元素法）Page 34运输问题的应用运输问题的应用例例5 求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：因为有：Page 3
23、5运输问题的应用运输问题的应用所以是一个产大于销的运输问题。表中所以是一个产大于销的运输问题。表中A2不可达不可达B1，用一，用一个很大的正数个很大的正数M表示运价表示运价C21。虚设一个销量为。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，表的右边增添一列，得到新的，得到新的运价表。运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180Page 36运输问题的应用运输问题的应用下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没有运出。
24、个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180Page 37例例6：化肥厂运输问题：化肥厂运输问题单位单位 销地销地 运价运价 化肥厂化肥厂甲甲乙乙丙丙丁丁产量产量1616131322221717505014141313191915156060191920202323-5050最低需求最低需求303070700 01010最高需求最高需求505070703030不限不限运输问题的应用运输问题的应用Page 38运输问题的应用运输问题的应用2.2.求极大值求极大值求极大值求极大值问题问题问题问题目标函数求利润
25、最大或营业额最大等问题。目标函数求利润最大或营业额最大等问题。Page 39运输问题的应用运输问题的应用求解方法：求解方法：将极大化问题转化为极小化问题。设极大化问题的运价将极大化问题转化为极小化问题。设极大化问题的运价表为表为C，用一个较大的数，用一个较大的数 h（hmaxcij）去减每一个）去减每一个cij得得到矩阵到矩阵C，其中，其中C=（hcij）0,将将C作为极小化问题的作为极小化问题的运价表，用表上用业法求出最优解。运价表，用表上用业法求出最优解。Page 40运输问题的应用运输问题的应用例例7 下下列列矩矩阵阵C是是Ai（I=1，2，3）到到Bj的的吨吨公公里里利利润润,运运输输
26、部部门如何安排运输方案使总利润最大门如何安排运输方案使总利润最大.销地销地产地产地B1B2B3产量产量A12589A2910710A365412销量销量8149Page 41运输问题的应用运输问题的应用 销地销地产地产地B1B2B3产量产量A18529A210310A345612销量销量8149得到新的最小化运输问题，用表上作业法求解即可。得到新的最小化运输问题，用表上作业法求解即可。Page 42运输问题的应用运输问题的应用3.生产与储存问题生产与储存问题例例8 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂
27、各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元任务任务2510.8103511.1153011251011.320Page 43运输问题的应用运输问题的应用解：解：设设 xij为第为第 i
28、季度生产的第季度生产的第 j 季度交货的柴油机数目，那季度交货的柴油机数目，那么应满足：么应满足：交货：交货：x11 =10 生产：生产：x11+x12+x13+x14 25 x12+x22 =15 x22+x23+x24 35 x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44 =20 x44 10把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的产量；把第个生产厂的产量；把第 j 季季度交货的柴油机数目看作第度交货的柴油机数目看作第 j 个销售点的销量；设个销售点的销量；设cij是第是第i季度生季度生产的第产的第j季度交货的
29、每台柴油机的实际成本，应该等于该季度单位季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：成本加上储存、维护等费用。可构造下列产销平衡问题：Page 44运输问题的应用运输问题的应用 ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量10152520 10070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。Page 45运输问题的应用运输问题的应用该问题的
30、数学模型：该问题的数学模型：Min f=10.8 x11+10.95 x12+11.1 x13+11.25 x14+11.1 x22+11.25 x23 +11.4 x24 +11.0 x33+11.15 x34 +11.3 x44 jiD产量产量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010销量销量1015252030 100100Page 46运输问题的应用运输问题的应用 jiD产量产量1015025053035255301010销量销量1015252030 100100最优生产决策如下表，最小费用最优生
31、产决策如下表，最小费用z773万元。万元。Page 47思考题：下列运输问题的最优运输方案如下表所示。思考题：下列运输问题的最优运输方案如下表所示。单位单位 销地销地 运价运价 产地产地产量产量10101 120201111151512127 79 9202025252 2141416168 85 5销量销量5 5151515151010运输问题的应用运输问题的应用 销地销地 运量运量 产地产地产量产量5 5101015150 01010151525255 55 5销量销量5 5151515151010问：单位运价问：单位运价 变为何值时，有无穷多最优方案？请再写出两变为何值时，有无穷多最优方案？请再写出两个个.