管理学运输问题

会计学1管理学运输问题管理学运输问题3.1.13.1.1运输问题的提出运输问题的提出2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14675384275910 6第1页/共88页3.1.13.1.1运输问题的提出运输问题的提出n n单位运输费用以及供应量和需求量如下表 需求供应需求1需求2需求3需求4供应量供应量供应1675314供应2842727供应35910619需求量需求量2213121360=60第2页/共88页3.1.13.1.1运输问题的提出运输问题的提出n n设从设从 i i 地到地到 j j 地的运输量为地的运输量为x xij ij，则运费最小的则运费最小的LPLP模型是：模型是：第3页/共88页3.1.13.1.1运输问题的提出运输问题的提出第4页/共88页3.1.23.1.2运输问题的一般模型运输问题的一般模型n n有有 mm 个生产地，用个生产地，用 A Ai i 表示，表示，i i=1,2,=1,2,mm，产量为产量为a ai i n n有有 n n 个销售地，用个销售地，用 B Bj j 表示，表示，j j=1,2,=1,2,n n，销量为销量为b bj j n n从从 A Ai i到到 B Bj j运输单位物资的运价为运输单位物资的运价为 c cij ij n n假设产销平衡假设产销平衡,即即n n求运费最小的调运方案？求运费最小的调运方案？第5页/共88页3.1.23.1.2运输问题的一般模型运输问题的一般模型n n设从设从i i 地到地到 j j 地的运输量为地的运输量为x xij ij，则运费最小的则运费最小的LPLP模型是模型是第6页/共88页3.1.23.1.2运输问题的一般模型运输问题的一般模型n n这个线性规划问题的系数矩阵A=有mn个决策变量m+n个约束条件矩阵的秩为m+n-1基变量个数为m+n-1第7页/共88页3.1.23.1.2运输问题的一般模型运输问题的一般模型第8页/共88页33运输问题运输问题n n3.1运输问题及其数学模型n n3.2表上作业法求解运输问题n n3.3运输问题的进一步讨论n n3.4运输问题的应用第9页/共88页表上作业法的步骤表上作业法的步骤n n初始的基础可行解n n求非基变量的检验数n n迭代调整出更好的基础可行解n n重复循环进行直到所有检验数大于等于0第10页/共88页3.2.13.2.1初始调运方案初始调运方案n n西北角法：最简单，距离最优解较远n n最小元素法：稍复杂，距离最优解较近n n伏格尔法：最复杂，距离最优解最近第11页/共88页西北角法西北角法813131466第12页/共88页最小元素法（最小元素法（1 1）第13页/共88页最小元素法（最小元素法（2 2）第14页/共88页最小元素法（最小元素法（3 3）第15页/共88页最小元素法（最小元素法（4 4）第16页/共88页最小元素法（最小元素法（5 5）第17页/共88页最小元素法（最小元素法（6 6）第18页/共88页伏格尔法伏格尔法差额法（差额法（1 1）13第19页/共88页伏格尔法伏格尔法差额法（差额法（2 2）1312第20页/共88页伏格尔法伏格尔法差额法（差额法（3 3）131213第21页/共88页伏格尔法伏格尔法差额法（差额法（4 4）1312132第22页/共88页伏格尔法伏格尔法差额法（差额法（5 5）13121321第23页/共88页伏格尔法伏格尔法差额法（差额法（6 6）1312132119第24页/共88页3.2.23.2.2求检验数求检验数n n闭回路法：比较复杂，不推荐，理论基础直观n n位势法：简单，原理是对偶理论第25页/共88页闭回路闭回路n n凡是能排列成如下形式的变量组称为一个闭回路。其中凡是能排列成如下形式的变量组称为一个闭回路。其中i i1 1,i i2 2,i is s互不相同，互不相同，j j1 1,j j2 2,j js s互不相同互不相同ABDC第26页/共88页闭回路闭回路ABFECD第27页/共88页闭回路法计算检验数（闭回路法计算检验数（1 1）5第28页/共88页闭回路法计算检验数（闭回路法计算检验数（2 2）5第29页/共88页闭回路法计算检验数（闭回路法计算检验数（3 3）7第30页/共88页闭回路法计算检验数（闭回路法计算检验数（4 4）5-3579-11第31页/共88页位势位势n n运输问题的对偶问题第32页/共88页位势位势n n根据对偶问题的性质，检验数 j=cj-CBB-1Pj=cj-Ypjn n运输问题的检验数 ij=cij-(u1,u2,um,v1,v2,vn)Pij=cij-(ui+vj)n n根据基变量的检验数等于0第33页/共88页行位势与列位势行位势与列位势第34页/共88页行位势与列位势行位势与列位势第35页/共88页行位势与列位势行位势与列位势第36页/共88页行位势与列位势行位势与列位势第37页/共88页行位势与列位势行位势与列位势第38页/共88页行位势与列位势行位势与列位势第39页/共88页行位势与列位势行位势与列位势第40页/共88页位势法求检验数（位势法求检验数（1 1）5第41页/共88页位势法求检验数（位势法求检验数（2 2）-5第42页/共88页位势法求检验数（位势法求检验数（3 3）-35579-11第43页/共88页3.2.33.2.3解的优化迭代解的优化迭代n n如果检验数中有负数，则当前的调运方案不是最优，可以迭代得到运费更低的方案n n闭回路迭代方法n n选择进基变量：最负的检验数对应的变量选择进基变量：最负的检验数对应的变量n n找到闭回路：以基变量为踏石的闭回路是唯一找到闭回路：以基变量为踏石的闭回路是唯一的的n n选择出基变量：闭回路上最小的偶数踏石对应选择出基变量：闭回路上最小的偶数踏石对应的变量的变量n n基础可行解的迭代：调整闭回路上所有的数值基础可行解的迭代：调整闭回路上所有的数值第44页/共88页解的改进解的改进闭回路法闭回路法n n选择进基变量和出基变量-35579-11第45页/共88页解的改进解的改进闭回路法闭回路法n n闭回路上奇数顶点闭回路上奇数顶点+，偶数顶点偶数顶点-，得到新的解得到新的解第46页/共88页解的迭代解的迭代n n重新计算检验数重新计算检验数，如果所有检验数大于等于如果所有检验数大于等于0 0，则得到最优解，则得到最优解n n如果有负的检验数，则继续迭代，直到得到最优解如果有负的检验数，则继续迭代，直到得到最优解1155-4-28第47页/共88页解的迭代解的迭代1155482第48页/共88页运输问题表上作业法的总结运输问题表上作业法的总结分析实际问题 建立运输表 求出初始方案（最小元素法）求出检验数（位势法）找出绝对值最大的负检验 调整得新方案得最优方案算出运费终止所有检验数0？第49页/共88页作业：第作业：第104104页第页第7 7题题n n用表上作业法求下表中给出的运输问题的最优解用表上作业法求下表中给出的运输问题的最优解1234产量141468212508337514销量6563 2020第50页/共88页33运输问题运输问题n n3.1运输问题及其数学模型n n3.2表上作业法求解运输问题n n3.3运输问题的进一步讨论n n3.4运输问题的应用第51页/共88页3.3.13.3.1运输问题的解运输问题的解n n运输问题一定存在最优解n n运输问题可能存在无穷多最优解n n迭代过程结束获得最优解时，如果出现非基变迭代过程结束获得最优解时，如果出现非基变量检验数量检验数=0=0，则以此非基变量为进基变量进行，则以此非基变量为进基变量进行解的迭代，可以得到另一个最优解。它们有相解的迭代，可以得到另一个最优解。它们有相同的目标函数值同的目标函数值n n两个最优解的线性组合都是运输问题的最优解两个最优解的线性组合都是运输问题的最优解第52页/共88页3.3.23.3.2解的退化解的退化n n如果运输问题的某个基变量xj=0，则出现退化解n n出现退化解的两种情况n n初始退化初始退化n n迭代过程中出现退化迭代过程中出现退化第53页/共88页初始退化初始退化3-5-4-071第54页/共88页迭代过程中出现退化迭代过程中出现退化74-16113第55页/共88页迭代过程中出现退化迭代过程中出现退化-4第56页/共88页迭代过程中出现退化迭代过程中出现退化第57页/共88页3.3.23.3.2产销不平衡运输问题产销不平衡运输问题（1 1）n n假设产品供给量大于需求量，则相应的模型为假设产品供给量大于需求量，则相应的模型为n n增加约束条件的松弛变量增加约束条件的松弛变量x xi,ni,n+1+1，成为标准的运输问题成为标准的运输问题第58页/共88页3.3.23.3.2产销不平衡运输问题产销不平衡运输问题（2 2）n n增加一个假想的销售地增加一个假想的销售地B Bn n+1+1，销售地的需求量为货物供销售地的需求量为货物供求差额求差额d dn n+1+1，产地产地A Ai i调运到假想销售地的数量为调运到假想销售地的数量为x xi,ni,n+1+1。其其实就是各产地的剩余货物，其单位运输费用实就是各产地的剩余货物，其单位运输费用c ci,ni,n+1+1=0=0第59页/共88页3.3.23.3.2产销不平衡运输问题产销不平衡运输问题（3 3）n n如果SD，增加一个假想的销地，其需求量为产量剩余，调运至该假想地的数量表示各产地的剩余存货，运输费用为0，如果有存储费用则可以把存储费用看作是运输费用n n如果SD，增加一个假想的产地，其产量为缺货数额，该假想地调运各地的数量表示各地的缺货数量，运输费用为0，如果有缺货费用则可以把缺货费用看作是运输费用第60页/共88页供小于求（供小于求（1 1）需求1需求2需求3需求4产量供给15011365供给25910210供给31874113销量331212 2830第61页/共88页供小于求（供小于求（2 2）需求1需求2需求3需求4产量供给15011365供给25910210供给31874113供给400002销量331212 3030第62页/共88页供大于求（供大于求（1 1）n n某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产量A1646300A2655300销量150150200 600500 第63页/共88页供大于求（供大于求（2 2）B1B2B3虚拟4产量A16460300A26550300销量150150200100 600600 第64页/共88页3.3.3.3.3 转运问题转运问题n n转运问题是运输问题的扩展，即在运输问题中增加了被称为中转站的运输节转运问题是运输问题的扩展，即在运输问题中增加了被称为中转站的运输节点，比如从生产企业到零售企业中间增加了代理商点，比如从生产企业到零售企业中间增加了代理商n n运输可以发生在所有节点中的任意两个节点。从起始节点到转载节点再到终运输可以发生在所有节点中的任意两个节点。从起始节点到转载节点再到终止节点、从一个起始节点到另一个起始节点，从一个转载节点到另一个转载止节点、从一个起始节点到另一个起始节点，从一个转载节点到另一个转载节点，从一个终止节点到另一个终止节点，从一个起始节点直接到一个终止节点，从一个终止节点到另一个终止节点，从一个起始节点直接到一个终止节点节点n n转运问题就是确定在每一条运输路径中应该运输多少单位，使得所有终止节转运问题就是确定在每一条运输路径中应该运输多少单位，使得所有终止节点的需求得到满足，并使得运输成本最小化点的需求得到满足，并使得运输成本最小化n n转运问题可以转换成一个简单的运输问题然后求解，也可以使用线性规划求转运问题可以转换成一个简单的运输问题然后求解，也可以使用线性规划求解解第65页/共88页转运问题转运问题 23456 7 1 8c c1313=2=25 53 31 16 63 32 26 63 36 64 44 4600=600=s s1 1d d1 1=200=200d d2 2=150=150400=400=s s2 2d d3 3=350=350d d4 4=300=300第66页/共88页转运问题转运问题n n设xij表示从i到j的运输量，其中转运节点可以是起点也可以是终点n n目标函数是最小化运输费用min=2x13+3x14+3x23+x24+2x35+6x36 +3x37+6x38+4x45+4x46+6x47+5x48第67页/共88页转运问题转运问题n n约束条件包括每个节点的运输量产地产地1:1:x x1313+x x1414 600 600产地产地2:2:x x2323+x x2424 0第68页/共88页转运问题转运问题min=2min=2x x1313+3+3x x1414+3+3x x2323+x x2424+2+2x x3535+6+6x x3636+3+3x x3737+6+6x x3838+4+4x x45 45+4+4x x4646+6+6x x47 47+5+5x x4848 s.t.s.t.x x1313+x x14 14 600600 x x2323+x x24 24 400400 x x1313+x x2323-x x3535-x x3636-x x3737 x x3838=0=0 x x1414+x x2424-x x4545-x x4646-x x4747 x x4848=0=0 x x3535+x x4545=200=200 x x3636+x x4646 =150 =150 x x3737+x x4747 =350 =350 x x3838+x x4848 =30 =30 x xij ij 0 0第69页/共88页转运问题转运问题n n转运的一般模型：设 xij 表示从 i 到j运输量 min min c cij ijx xij ij i j i j s.t.s.t.x xij ij 0 0第70页/共88页转运问题转运问题 23456 7 1 8c c1313=2=25 53 31 16 63 32 26 63 36 64 44 4600=600=s s1 1d d1 1=200=200d d2 2=150=150400=400=s s2 2d d3 3=350=350d d4 4=300=3004 41 1第71页/共88页33运输问题运输问题n n3.1运输问题及其数学模型n n3.2表上作业法求解运输问题n n3.3运输问题的进一步讨论n n3.4运输问题的应用第72页/共88页运输问题运输问题n n设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表。试求出总运费最节省的化肥调拨方案。到各地区运送单位化肥的运价如下表。试求出总运费最节省的化肥调拨方案。需求地化肥厂IIIIIIIV产量A1613221750B1413191560C192023M50最低需求最高需求3050707003010不限第73页/共88页 需求地化肥厂II*IIIIIIVIV*产量A16161322171750B14141319151560C19192023MM50DM0M0M050需求302070301050路线容量路线容量第74页/共88页1234s116161322171750500214141319151560201030319192023MM5030204M0M0M0503020d302070301050路线容量路线容量第75页/共88页生产存储问题的运输化生产存储问题的运输化n n某企业和用户签订了设备交货合同，已知该企业每个季某企业和用户签订了设备交货合同，已知该企业每个季度的生产能力、生产成本和每季度的交货量如下表。若度的生产能力、生产成本和每季度的交货量如下表。若生产的设备当季度不交货，每台设备每季度支付保管费生产的设备当季度不交货，每台设备每季度支付保管费0.10.1万元，请问在遵守合同的条件下，企业应如何安排生万元，请问在遵守合同的条件下，企业应如何安排生产计划，才能使年度消耗费用最优产计划，才能使年度消耗费用最优季度工厂生产能力（台）交货量（台）单位成本（万元/台）125151223520113302511.54202012.5第76页/共88页生产存储问题的运输化生产存储问题的运输化第一季第一季度生产度生产第二季第二季度生产度生产第三季第三季度生产度生产第四季第四季度生产度生产第四季第四季度需求度需求第三季第三季度需求度需求第二季第二季度需求度需求第一季第一季度需求度需求250.10.112.511.51112203035152025200.1第77页/共88页生产存储问题的运输化生产存储问题的运输化第1季度 第2季度 第3季度 第4季度生产量第1季度1212.112.212.325第2季度M11.011.111.235第3季度MM11.511.630第4季度MMM12.520交货量15202520第78页/共88页第1季度第2季度第3季度第4季度 能力过剩 生产量第1季度1212.112.212.3025第2季度M11.011.111.2035第3季度MM11.511.6030第4季度MMM12.5020交货量1520252030生产存储问题的运输化生产存储问题的运输化第79页/共88页生产问题生产问题n n光明仪器厂生产电脑绣花机是以产定销的。已知光明仪器厂生产电脑绣花机是以产定销的。已知1 1至至6 6月月份各月的生产能力、合同销量和单台生产费用见下表份各月的生产能力、合同销量和单台生产费用见下表生产能力生产能力加班生产能力加班生产能力销售量销售量单台费用单台费用Jan601010415Feb50107514Mar902011513.5Apr1004016013May1004010313Jun80407013.5第80页/共88页生产问题生产问题n n已知上年末库存已知上年末库存103103台绣花机台绣花机n n如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本成本0.10.1万元万元,每台机器每月的平均仓储费、维护费为每台机器每月的平均仓储费、维护费为0.20.2万元万元n n在在7-87-8月份销售淡季，全厂停产月份销售淡季，全厂停产1 1个月，因此在个月，因此在6 6月份完成销售合同后还要留月份完成销售合同后还要留出库存出库存8080台台n n加班生产机器每台增加成本加班生产机器每台增加成本1 1万元万元n n问应如何安排问应如何安排1-61-6月份的生产，可使总的生产费用（包括运输、仓储、维护）月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？最少？第81页/共88页n n这个生产计划安排问题可以看作是运输问题。把每个月的生产看作是生产地，这个生产计划安排问题可以看作是运输问题。把每个月的生产看作是生产地，把每个月的需求看作是需求地把每个月的需求看作是需求地n n六个月的生产能力六个月的生产能力+加班生产能力加班生产能力+上年末库存上年末库存=743=743n n六个月的销售六个月的销售+七八月份的库存需求七八月份的库存需求=707=707n n供求不平衡问题，假设一个虚拟的销售地，销售量供求不平衡问题，假设一个虚拟的销售地，销售量=36=36n n六月份的需求量六月份的需求量=六月份销售六月份销售+七八月库存七八月库存=150=150n n上年末的库存看作是第一个供给地，单位运输费用上年末的库存看作是第一个供给地，单位运输费用=库存费用库存费用+维护费用维护费用n n每个月的生产分为两个需求地，分别为正常生产能力和加班生产能力每个月的生产分为两个需求地，分别为正常生产能力和加班生产能力n n不能发生的运输路径，单位运输费用不能发生的运输路径，单位运输费用=MM生产问题生产问题第82页/共88页JanFebMarAprMayJun虚拟虚拟生产量生产量上年库存上年库存0.30.50.70.91.11.31.51031月正常月正常1515.315.515.715.916.10601月加班月加班1616.316.516.716.917.10102月正常月正常M1414.314.514.714.90502月加班月加班M1515.315.515.715.90103月正常月正常MM13.513.81414.20903月加班月加班MM14.514.81515.20204月正常月正常MMM1313.313.501004月加班月加班MMM1414.314.50405月正常月正常MMMM1313.301005月加班月加班MMMM1414.30406月正常月正常MMMMM13.50806月加班月加班MMMMM14.5040销售量销售量1047511516010315036生产问题生产问题第83页/共88页练习练习n n在运输问题中，只要给出一组含m+n-1个非零的可行解，就可以作为一个初始基础可行n n运输问题是一种特殊的线性规划模型，因而求解结果可能出现下列四种情况之一：唯一、无穷、无界和无可行第84页/共88页作业：第作业：第104104页第页第7 7题题n n用表上作业法求下表中给出的运输问题的最优解 销地产地甲乙丙丁1376452243223438563322第85页/共88页作业：第作业：第104104页第页第8 8题题n n某企业和用户签订了设备交货合同，已知该企业个季度某企业和用户签订了设备交货合同，已知该企业个季度的生产能力、每台设备的生产成本和每季度的交货量如的生产能力、每台设备的生产成本和每季度的交货量如下表。若生产的设备当季度不交货，每台设备每季度支下表。若生产的设备当季度不交货，每台设备每季度支付保管费付保管费0.10.1万元，请问在遵守合同的条件下，企业应如万元，请问在遵守合同的条件下，企业应如何安排生产计划，才能使年度消耗费用最优？（列出模何安排生产计划，才能使年度消耗费用最优？（列出模型即可）型即可）季度工厂生产能力（台）交货量（台）单位成本（万元/台）125151223520113302511.54202012.5第86页/共88页The End第87页/共88页