运输问题1

运输问题模型主要内容运输问题基本描述及解决方法运输问题的EXCEL求解方法运输问题的扩展案例分析求解人员指派问题及EXCEL求解方法运输问题基本描述及解决方法•运输：实体的空间移动，是物流的主要功能和中心活动。运输费用一般占物流总成本的35%-50%。•运输问题：解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量、每个销地的需求量以及各地的运输单价已知的前提下，确定一个使得总的运输费用最小的方案。•随着现代物流业的发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，具有重要的现实意义。•物流运输问题主要解决运输工具的选择、运输线路的选择、运输人员的安排。但不只局限于上述问题，凡是其数学模型符合“运输”特点的问题，都可采用运输问题的方法加以解决。运输问题基本描述及解决方法•案例:湖南欣利食品公司主要生产食品罐头，有橘子、竹笋、野山菌三个罐头厂。三个工厂的厂址分别在A、B、C三个靠近不同原料产地的城镇，每个工厂都能生产不同品种的罐头，但每个工厂生产不同品种罐头的产能不同，各工厂生产与阐明相同的罐头的设计产能要大一些。2009年6月份来自深圳、武汉、成都和西安的四个配送中心的野山菌罐头订单和各工厂的野山菌罐头的计划产量见表。厂址产量配送中心订单需求A（橘子）80深圳85B（竹笋）100武汉110C（野山菌）220成都75西安130合计400合计400运输问题基本描述及解决方法由于从各罐头工厂到各配送中心的运输距离不同，可以采用的运输方式、运输工具、与物流公司签订的运输合同等也不相同，因此，每箱野山菌罐头从各个工厂到各个配送中心的运费不相同。下表为本次生产计划、订单情况和不同运输线路上的成本。求运输成本最小的运输方案。厂址配送中心深圳武汉成都西安A（橘子）784586110B（竹笋）844179103C（野山菌）805376118运输问题基本描述及解决方法•产销平衡表：销地产地B1B2B3…Bn产量A1c11c12c13…c1na1A2c21c22c23…c2na2…………………Amcm1cm2cm3…cmnam销量b1b2b3…bn运输问题基本描述及解决方法•数学模型：（属于一类特殊的线性规划模型）minjijijxcMinZ11njiijax1),(mijijbx1),(0ijx运输问题基本描述及解决方法例：某公司有三个加工厂A1、A2、A3生产某产品，每日的产量分别为7、4、9吨；该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点每日销量分别为3、6、5、6吨；从各工厂到各销售点的单位产品运价见表。问：公司该如何调运这些产品，在满足销售点需求的前提下，使总运费最小？销地产地B1B2B3B4产量A13113107A219284A3741059销量3656运输问题基本描述及解决方法•主要解决方法——表上作业法•解题思路：–找出初始基本可行解：在产销平衡表上给出（m+n-1)个有数字的格，行和等于产量，列和等于销售量，但他们不能构成闭回路；–求检验数：求出所有空格的检验数，判断其是否达到最优；–确定换入变量和换出变量，找出一组新解；–重复前面步骤，直到找到最优解。•关键环节：–找基本可行解–求检验数–调整解的方案运输问题基本描述及解决方法—找基本可行解：•一组基本可行解的基本条件：个数为m+n-1；不能构成闭回路；行和等于产量、列和等于销量。•基本可行解的寻找方法：最小元素法、伏格尔法。–最小元素法：运价最便宜的优先供应。每次找最小运价，满足需求，同时划去一行（或一列），直到把所有的行列划完为止。缺点距最优方案较远。–伏格尔法：计算各行和各列最小与次小运价的差额。选择差额最大者所在行（或列）中的最小元素进行运输。划去该行（或列）继续。该方法距离最优解较近。•如前例运输问题基本描述及解决方法—求检验数：•计算表格中所有空格（非基变量）的检验数。可采用位势法。当所有检验数均大于等于零。该解为最优解。•位势法：令数字格xij所在行的位势为ui，所在列的位势为vj，位势满足ui+vj=cij。令u1=0，得出所有ui、vj。然后根据σij=cij-(ui+vj)，计算出所有检验数。运输问题基本描述及解决方法—调整解的方案：•当全部检验数均大于等于0，该方案即为最优方案。若至少有一个检验数小于零，选择最小的负检验数进行调整。调整方法为闭回路法。•闭回路法：将该空格与其它数字格的运量组成一条闭回路，找出偶数点最小者为调整量，对闭回路上各点进行调整，其中偶数点减调整量，奇数点加调整量。•如前例运输问题基本描述及解决方法•特殊运输问题及处理方法：–当产大于销时。需要在产销平衡表中增加一列，即虚销地，消化多于的产量。–当销大于产时。需要在产销平衡表中增加一行，即虚产地，作为多余销量的来源。–存在转运环节时。将每一个产地、中转地和销地都既看成一个“产地”，也看成是一个“销地”。运输问题的EXCEL求解方法•产销平衡运输问题：如前例运输问题的EXCEL求解方法•产销不平衡运输问题例：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，从各产地到各销地的单位产品运价、产量及销量见表。问：公司该如何调运这些产品，在满足销售点需求的前提下，使总运费最小？•在前例中，若橘子厂的野山菌罐头产量增加到120箱，而配送中心的订单不变。求解该问题的运输方案。销地产地B1B2B3产量A113151278A211292245销量533665销大于产运输问题的EXCEL求解方法练习：某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、600箱。需要供应四个地方销售。这四地的产品需求分别为300箱、200箱、500箱、100箱。从三个分厂到四个销地的单位运价见表。问：（1）如何安排运输方案，使总运费最小。（2）如果2分厂的产量从400箱提高到600箱，那么如何安排运输方案，使总运费最小？（3）如果销地甲的需求从400箱提高到500箱，其他情况同（1），如何安排总运费最小的方案。甲乙丙丁产量1分厂211723253002分厂101530194003分厂23212022600销量300200500100运输问题的EXCEL求解方法•带有约束的不平衡运输问题例：某公司在三个工厂中专门生产一种产品.在未来的四个月中,有四个不同区域的潜在顾客很可能大量订购.顾客1是公司最好的顾客,他的全部订单都要满足;顾客2、顾客3是重要顾客，至少要满足他们订单的1/3；顾客4不需要特殊考虑。问应该供应给每一个顾客多少货物，公司总利润最大。顾客工厂单位利润（元）产量1234155424653800023718324850003295951357000最小采购量7000300020000要求采购量7000900060008000运输问题的EXCEL求解方法•带有约束的不平衡运输问题例：某市拟开办第三所小学，需要为该市内的所有小学重新划定服务区域。该市大致分为6个城区，每一城区内小学生数量以及到各小学的近似距离见表。学校的招生数量视具体情况可在一定范围内变动。服务区域的划分目标是使学生到学校的平均距离最短。试寻找最优划分方案。学校区域距离学校距离（千米）学生数量（人）12311.111.640021.20.71.870031.321.435040.51.90.630052.20.82.640061.61.31.5350最小招生数（人）600700300最大招生数（人）9001000700运输问题的EXCEL求解方法•转运运输问题例：某公司在北京和广州有两个工厂，北京工厂每月生产400台产品，广州分厂每月生产600台产品。该公司在重庆与西安有两个销售公司负责对武汉、济南、贵阳与呼和浩特4个城市的产品供应。又因为北京与呼和浩特有较近的直达交通线，公司同意北京分厂也可以向呼和浩特直接供货，这些城市间的每台产品的运输费用见表。问：如何调运产品，使总的运输费用最低?广州北京重庆西安武汉济南贵阳呼和浩特600400200150350300200300300100400200600300600400400600500运输问题的EXCEL求解方法•转运运输问题平衡表：重庆西安武汉济南贵阳呼和浩特生产总量（台）广州200300MMMM600北京300100MMM400400重庆0M2006003006001000西安M04004006005001000交付总量（台）100010002001503503003000运输问题的EXCEL求解方法•转运运输问题例：前例中，运输部杨经理在寻找最节省的运费过程中，发现了位于长沙市和郑州市的两个物流中心，能以较低的运价提供从工厂到配送中心的运输服务。经过洽谈，这两个物流中心给杨经理的报价见表。同时公司仍然可以利用其它运输公司以前为他提供的从工厂到配送中心的直达运输服务。杨经理应该如何决策？厂址物流中心长沙郑州A（橘子）1760B（竹笋）2052C（野山菌）1562物流中心配送中心深圳武汉成都西安长沙52196890郑州80285432运输问题的扩展案例分析求解例1：某农民承包了五块土地共206亩，打算种小麦、玉米和蔬菜三种农作物，各类农作物的计划播种面积（亩）以及每块土地种植各种不同农作物的亩产数量（公斤）见下表。问如何安排种植计划，可使总产量达到最高？种类、土地12345计划播种面积小麦500600650105080086玉米85080070090095070蔬菜100095085055070050土地亩数3648443246运输问题的扩展案例分析求解例2：某厂生产设备是以销定产的。已知1-6月份的生产能力、合同销量和单台设备的平均生产费用见表。如果上年末库存103台，当月生产的设备当月不交货，则需要运到库房，每台增加运输费0.1万元、每台每月仓储费0.2万元。7-8月份为销售淡季，全厂停产1个月。因此在6月份完成销售合同后还要留出库存80台。加班生产设备每台增加成本1万元。问：如何安排1-6月份的生产，使总的生产费用最少？月份正常生产能力（台）加班生产能力（台）销量（台）单台费用（万元）1月6010104152月501075143月902011513.54月10040160135月10040103136月80407013.5人员指派问题及EXCEL求解方法•指派问题(AssignmentProblem)：即分配问题。主要研究人和工作（任务）间如何分配，以使所有工作完成的效率实现最优化。即确定指派哪个人去完成哪项工作。•基本描述：–人的数量和任务数量相等–每个人只能完成一项工作–每项任务只能由一个人来完成–每个人和每项任务的组合都对应一个相关的成本–目标是确定如何指派才能使总成本最小人员指派问题及EXCEL求解方法•数学模型：ninjijijxcMinZ11njijx11niijx110ijx人员指派问题及EXCEL求解方法•例：某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘、小赵五人，每个人负责完成下面的一项工作A、B、C、D、E。问如何指派，才能使总时间最短。人员每一项工作所需时间（小时）ABCDE小张2529314218小王2219351820小李3938262024小刘3427284031小赵2342362435人员指派问题及EXCEL求解方法•指派问题的求解方法——匈牙利法库恩（W.W.Kuhn)1955年提出。•基本思路：修改系数矩阵的行或列，使得每一行（或）列中至少有一个为零的元素，直到在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的最优分配方案。•基本条件：–系数矩阵cij必须为方阵–系数矩阵中的元素cij=0–目标函数求极小人员指派问题及EXCEL求解方法•匈牙利法求解步骤：–使系数矩阵的每一行、每一列都至少有一个零元素。（从矩阵的每行元素减去该行的最小元素，对没有零元素的列再减去该列的最小元素）。–求最优解。（