运输问题模型.

Presentation on theme: "运输问题模型."— Presentation transcript:

1 运输问题模型

2 主 要 内 容 运输问题基本描述及解决方法 运输问题的EXCEL求解方法 运输问题的扩展案例分析求解 人员指派问题及EXCEL求解方法

3 运输问题基本描述及解决方法 运输：实体的空间移动，是物流的主要功能和中心活动。运输费用一般占物流总成本的35%-50%。
运输问题：解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量、每个销地的需求量以及各地的运输单价已知的前提下，确定一个使得总的运输费用最小的方案。 随着现代物流业的发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，具有重要的现实意义。 物流运输问题主要解决运输工具的选择、运输线路的选择、运输人员的安排。但不只局限于上述问题，凡是其数学模型符合“运输”特点的问题，都可采用运输问题的方法加以解决。

4 运输问题基本描述及解决方法 案例:湖南欣利食品公司主要生产食品罐头，有橘子、竹笋、野山菌三个罐头厂。三个工厂的厂址分别在A、B、C三个靠近不同原料产地的城镇，每个工厂都能生产不同品种的罐头，但每个工厂生产不同品种罐头的产能不同，各工厂生产与阐明相同的罐头的设计产能要大一些。2009年6月份来自深圳、武汉、成都和西安的四个配送中心的野山菌罐头订单和各工厂的野山菌罐头的计划产量见表。 厂址 产量 配送中心 订单需求 A（橘子） 80 深圳 85 B（竹笋） 100 武汉 110 C（野山菌） 220 成都 75 西安 130 合计 400

5 运输问题基本描述及解决方法 由于从各罐头工厂到各配送中心的运输距离不同，可以采用的运输方式、运输工具、与物流公司签订的运输合同等也不相同，因此，每箱野山菌罐头从各个工厂到各个配送中心的运费不相同。下表为本次生产计划、订单情况和不同运输线路上的成本。求运输成本最小的运输方案。 厂址 配送中心 深圳 武汉 成都 西安 A（橘子） 78 45 86 110 B（竹笋） 84 41 79 103 C（野山菌） 80 53 76 118

6 运输问题基本描述及解决方法 产销平衡表： 销地 产地 B1 B2 B3 … Bn 产量 A1 c11 c12 c13 c1n a1 A2
Am cm1 cm2 cm3 cmn am 销量 b1 b2 b3 bn

7 运输问题基本描述及解决方法 数学模型：（属于一类特殊的线性规划模型）

8 运输问题基本描述及解决方法 例：某公司有三个加工厂A1 、A2 、A3生产某产品，每日的产量分别为7、4、9吨；该公司把这些产品分别运往四个销售点B1 、B2、B3、B4，各销售点每日销量分别为3、6、5、6吨；从各工厂到各销售点的单位产品运价见表。问：公司该如何调运这些产品，在满足销售点需求的前提下，使总运费最小？ 销地 产地 B1 B2 B3 B4 产量 A1 3 11 10 7 A2 1 9 2 8 4 A3 5 销量 6

9 运输问题基本描述及解决方法 主要解决方法——表上作业法 解题思路： 关键环节：
找出初始基本可行解：在产销平衡表上给出（m+n-1)个有数字的格，行和等于产量，列和等于销售量，但他们不能构成闭回路； 求检验数：求出所有空格的检验数，判断其是否达到最优； 确定换入变量和换出变量，找出一组新解； 重复前面步骤，直到找到最优解。 关键环节： 找基本可行解 求检验数 调整解的方案

10 运输问题基本描述及解决方法 —找基本可行解： 一组基本可行解的基本条件：个数为m+n-1；不能构成闭回路；行和等于产量、列和等于销量。
基本可行解的寻找方法：最小元素法、伏格尔法。 最小元素法：运价最便宜的优先供应。每次找最小运价，满足需求，同时划去一行（或一列），直到把所有的行列划完为止。缺点距最优方案较远。 伏格尔法：计算各行和各列最小与次小运价的差额。选择差额最大者所在行（或列）中的最小元素进行运输。划去该行（或列）继续。该方法距离最优解较近。 如前例

11 运输问题基本描述及解决方法 —求检验数： 计算表格中所有空格（非基变量）的检验数。可采用位势法。当所有检验数均大于等于零。该解为最优解。
位势法：令数字格xij所在行的位势为ui，所在列的位势为vj，位势满足ui+vj=cij。令u1=0，得出所有ui、vj。然后根据σij=cij-(ui+vj)，计算出所有检验数。

12 运输问题基本描述及解决方法 —调整解的方案：
当全部检验数均大于等于0，该方案即为最优方案。若至少有一个检验数小于零，选择最小的负检验数进行调整。调整方法为闭回路法。 闭回路法：将该空格与其它数字格的运量组成一条闭回路，找出偶数点最小者为调整量，对闭回路上各点进行调整，其中偶数点减调整量，奇数点加调整量。 如前例

13 运输问题基本描述及解决方法 特殊运输问题及处理方法： 当产大于销时。需要在产销平衡表中增加一列，即虚销地，消化多于的产量。
当销大于产时。需要在产销平衡表中增加一行，即虚产地，作为多余销量的来源。 存在转运环节时。将每一个产地、中转地和销地都既看成一个“产地”，也看成是一个“销地”。

14 运输问题的EXCEL求解方法 产销平衡运输问题：如前例

15 运输问题的EXCEL求解方法 •产销不平衡运输问题例：
某公司从两个产地A1 、A2将物品运往三个销地B1、B2、B3，从各产地到各销地的单位产品运价、产量及销量见表。问：公司该如何调运这些产品，在满足销售点需求的前提下，使总运费最小？ •在前例中，若橘子厂的野山菌罐头产量增加到120箱，而配送中心的订单不变。求解该问题的运输方案。 销地 产地 B1 B2 B3 产量 A1 13 15 12 78 A2 11 29 22 45 销量 53 36 65 销大于产

16 运输问题的EXCEL求解方法 练习：某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、600箱。需要供应四个地方销售。这四地的产品需求分别为300箱、200箱、500箱、100箱。从三个分厂到四个销地的单位运价见表。 问： （1）如何安排运输方案，使总运费最小。 （2）如果2分厂的产量从400箱提高到600箱，那么如何安排运输方案，使总运费最小？ （3）如果销地甲的需求从400箱提高到500箱，其他情况同（1），如何安排总运费最小的方案。 甲 乙 丙 丁 产量 1分厂 21 17 23 25 300 2分厂 10 15 30 19 400 3分厂 20 22 600 销量 200 500 100

17 运输问题的EXCEL求解方法 •带有约束的不平衡运输问题例：
某公司在三个工厂中专门生产一种产品.在未来的四个月中,有四个不同区域的潜在顾客很可能大量订购.顾客1是公司最好的顾客,他的全部订单都要满足;顾客2、顾客3是重要顾客，至少要满足他们订单的1/3；顾客4不需要特殊考虑。问应该供应给每一个顾客多少货物，公司总利润最大。 顾客 工厂 单位利润（元） 产量 1 2 3 4 55 42 46 53 8000 37 18 32 48 5000 29 59 51 35 7000 最小采购量 3000 2000 要求采购量 9000 6000

18 运输问题的EXCEL求解方法 •带有约束的不平衡运输问题例：
某市拟开办第三所小学，需要为该市内的所有小学重新划定服务区域。该市大致分为6个城区，每一城区内小学生数量以及到各小学的近似距离见表。学校的招生数量视具体情况可在一定范围内变动。服务区域的划分目标是使学生到学校的平均距离最短。试寻找最优划分方案。 学校 区域 距离学校距离（千米） 学生数量 （人） 1 2 3 1.1 1.6 400 1.2 0.7 1.8 700 1.3 1.4 350 4 0.5 1.9 0.6 300 5 2.2 0.8 2.6 6 1.5 最小招生数（人） 600 最大招生数（人） 900 1000

19 运输问题的EXCEL求解方法 •转运运输问题例：
某公司在北京和广州有两个工厂，北京工厂每月生产400台产品，广州分厂每月生产600台产品。该公司在重庆与西安有两个销售公司负责对武汉、济南、贵阳与呼和浩特4个城市的产品供应。又因为北京与呼和浩特有较近的直达交通线，公司同意北京分厂也可以向呼和浩特直接供货，这些城市间的每台产品的运输费用见表。问：如何调运产品，使总的运输费用最低? 广州 北京 重庆 西安 武汉 济南 贵阳 呼和 浩特 600 400 200 150 350 300 100 500

20 运输问题的EXCEL求解方法 重庆 西安 贵阳 呼和浩特 广州 北京 500 150 •转运运输问题平衡表： 武汉 济南 生产总量 （台）
200 300 M 600 北京 100 400 1000 500 交付总量（台） 150 350 3000

21 运输问题的EXCEL求解方法 •转运运输问题例：
前例中，运输部杨经理在寻找最节省的运费过程中，发现了位于长沙市和郑州市的两个物流中心，能以较低的运价提供从工厂到配送中心的运输服务。经过洽谈，这两个物流中心给杨经理的报价见表。同时公司仍然可以利用其它运输公司以前为他提供的从工厂到配送中心的直达运输服务。杨经理应该如何决策？ 厂址 物流中心 长沙 郑州 A（橘子） 17 60 B（竹笋） 20 52 C（野山菌） 15 62 物流中心 配送中心 深圳 武汉 成都 西安 长沙 52 19 68 90 郑州 80 28 54 32

22 运输问题的扩展案例分析求解 例1：某农民承包了五块土地共206亩，打算种小麦、玉米和蔬菜三种农作物，各类农作物的计划播种面积（亩）以及每块土地种植各种不同农作物的亩产数量（公斤）见下表。问如何安排种植计划，可使总产量达到最高？ 种类、土地 1 2 3 4 5 计划播种面积 小麦 500 600 650 1050 800 86 玉米 850 700 900 950 70 蔬菜 1000 550 50 土地亩数 36 48 44 32 46

23 运输问题的扩展案例分析求解 例2： 某厂生产设备是以销定产的。已知1-6月份的生产能力、合同销量和单台设备的平均生产费用见表。如果上年末库存103台，当月生产的设备当月不交货，则需要运到库房，每台增加运输费0.1万元、每台每月仓储费0.2万元。7-8月份为销售淡季，全厂停产1个月。因此在6月份完成销售合同后还要留出库存80台。加班生产设备每台增加成本1万元。问：如何安排1-6月份的生产，使总的生产费用最少？ 月份 正常生产能力（台） 加班生产能力（台） 销量（台） 单台费用（万元） 1月 60 10 104 15 2月 50 75 14 3月 90 20 115 13.5 4月 100 40 160 13 5月 103 6月 80 70

24 人员指派问题及EXCEL求解方法 指派问题(Assignment Problem)：即分配问题。主要研究人和工作（任务）间如何分配，以使所有工作完成的效率实现最优化。即确定指派哪个人去完成哪项工作。 基本描述： 人的数量和任务数量相等 每个人只能完成一项工作 每项任务只能由一个人来完成 每个人和每项任务的组合都对应一个相关的成本 目标是确定如何指派才能使总成本最小

25 人员指派问题及EXCEL求解方法 数学模型：

26 人员指派问题及EXCEL求解方法 例：某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘、小赵五人，每个人负责完成下面的一项工作A、B、C、D、E。问如何指派，才能使总时间最短。 人员 每一项工作所需时间（小时） A B C D E 小张 25 29 31 42 18 小王 22 19 35 20 小李 39 38 26 24 小刘 34 27 28 40 小赵 23 36

27 人员指派问题及EXCEL求解方法 指派问题的求解方法——匈牙利法 库恩（W.W.Kuhn)1955年提出。
基本思路：修改系数矩阵的行或列，使得每一行（或）列中至少有一个为零的元素，直到在不同行、不同列中至少有一个零元素，从而得到与这些零元素相对应的最优分配方案。 基本条件： 系数矩阵cij必须为方阵 系数矩阵中的元素cij>=0 目标函数求极小

28 人员指派问题及EXCEL求解方法 匈牙利法求解步骤：
使系数矩阵的每一行、每一列都至少有一个零元素。（从矩阵的每行元素减去该行的最小元素，对没有零元素的列再减去该列的最小元素）。 求最优解。（从有零元素最少的行（或列）开始，圈出一个零元素，然后划去同行同列的其它零元素。若得到不同行、不同列的n个圈出的零，则得到最优解。相对应于圈出零的位置为1，其余位置为0）。 若所圈出的零元素不够n个，则需要做出进一步调整。（对没有圈0的行打√；对打√行所有未圈0元素所在列打√；在对打√列圈0的行打√；对没打√的行画横线，对打√的列画纵线）。 增加零矩阵。（从没被直线覆盖的所有元素找出最小元素；对没画直线的行减去最小元素；对画直线的列加上最小元素；重复第二步）。 如前例

29 人员指派问题及EXCEL求解方法 指派问题EXCEL求解：

30 人员指派问题及EXCEL求解方法 指派问题例2:
一家制药公司,为提升竞争力,决定加大科研力度,选择了五位科学家开发五个项目.为了保证科学家都能获得他们感兴趣的项目,进行了一个投标选择.每位科学家都有1000点的投标点.他们向每一个项目投标,并且把较多的投标点投向自己感兴趣的项目.五位科学家的投标结果如下.根据投标结果,决定每位科学家负责的项目,使总满意度最高. 投标点 A项目 B项目 C项目 D项目 E项目 李尔博士 100 400 200 朱诺博士 800 刘哲博士 600 王凯博士 267 153 99 451 30 罗林博士 33 34

31 人员指派问题及EXCEL求解方法 问: 根据投标结果,决定每一位科学家负责一个项目,使总满意度最高.
罗林博士接到其他任务需要离开,公司只有放弃一个缺乏热情的项目,应当放弃哪一个. 如果公司不想放弃任何一个项目,决定让朱诺博士或者王凯博士同时领导两个项目,如何安排? 假如受到资金的限制,希望从五个项目中选取三个,让三位最有热情的科学家来领导,此时应该选取哪三个项目和哪三位科学家?

32 人员指派问题及EXCEL求解方法 如果五位科学家中有三位科学家不能领导几个特定的项目，具体见下表。由于不能领导，需要重新调整这三位科学家的投标点，具体的调整方法是将不能领导的投标点全部投到他自己感兴趣的项目上。在这种情况下，让哪位科学家领导哪个项目才能使得对项目的总热情最高？ 投标点 A项目 B项目 C项目 D项目 E项目 李尔博士 100 700 200 不能领导 朱诺博士 800 刘哲博士 600 王凯博士 871 99 30 罗林博士 33 34 900

33 人员指派问题及EXCEL求解方法 公司觉得D项目和E项目太复杂，各让一位科学家分别进行领导不太合适。因此决定这两个项目都要指派两位科学家进行领导。故需要雇佣更多的科学家来领导所有的项目：陈加博士和郑斯博士。由于身体原因，这两位新加入的科学家都不能领导C项目。下表为两位科学家的投标情况。 投标点 A项目 B项目 C项目 D项目 E项目 陈加博士 250 不能领导 郑斯博士 111 1 333 555

34 人员指派问题及EXCEL求解方法 运输问题综合练习1—营销总监安排:
D公司准备向华中、华南、华北、东北、西北、西南六区各派一位营销总监。现有四位人选，他们分别是张、王、李、赵。由于他们对各地区的文化、市场、媒体等熟悉程度不同，筹建所需时间也不同。考虑到张先生业务最熟练，最多可以负责三个区的建设。王先生的业务也比较熟练，最多可以负责两个区的建设。为了避免多头领导，每个地区只派一位营销总监进行筹建工作。表中为各位营销总监在不同地区建分公司预计所用时间及月薪。问：如何指派，才能使总工资成本最低？ 人员 所用筹建时间（月） 月薪 （万元） 华中 华南 华北 东北 西北 西南 张 3 4 3.5 6 8 2.5 王 7 2.1 李 5.5 5 9 1.8 赵 7.5 1.6

35 人员指派问题及EXCEL求解方法 运输问题综合练习2:
某电子公司制造四种不同型号的电子计算器：C1、C2、C3、C4。他们可以分别有五个不同的生产车间单独制造D1、D2、D3、D4、D5。该公司规定：C1的生产数不能多于1400个；C2的生产数至少为300个，但不能超过800个；C3的生产数不能超过8000个；C4的生产数至少为700个。财务人员报告：四种型号产品的利润分别为：25、20、17、11元。请做一个生产方案，使得该公司总利润最大。 型号 所需时间（分钟） D1 D2 D3 D4 D5 C1 5 6 4 3 2 C2 7 - C3 C4 车间 D1 D2 D3 D4 D5 可用时间（分钟） 18000 15000 14000 12000 10000