运输问题模型.

Slides:



Advertisements
Similar presentations
质数和合数 中心小学 顾禹 人教版小学五年级数学下册 一、激趣导入 提示:密码是一个三位 数,它既是一个偶数, 又是 5 的倍数;最高位是 9 的最大因数;中间一位 是最小的质数。你能打 开密码锁吗?
Advertisements

因数与倍数 2 、 5 的倍数的特征
摆一摆,想一想. 棋子个数数的个数 摆出的数 、 10 2 、 11 、 20 3 、 12 、 21 、 30 4 、 13 、 22 、 31 、 40 5 、 14 、 23 、 32 、 41 、
3 的倍数特征 抢三十
质数和合数 富县北教场小学 潘小娟 1 、什么叫因数? 2 、自然数分几类? 奇数和偶数. 3 、自然数还有一种新的分类方法, 就是按一个数的因数个数来分. 4 、写出 1—20 的因数。 前置性作业.

3 的倍数的特征 的倍数有 : 。 5 的倍数有 : 。 既是 2 的倍数又是 5 的倍数有 : 。 12 , 18 , 20 , 48 , 60 , 72 , , 25 , 60 ,
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
冀教版四年级数学上册 本节课我们主要来学习 2 、 3 、 5 的倍数特征,同学们要注意观察 和总结规律,掌握 2 、 3 、 5 的倍 数分别有什么特点,并且能够按 要求找出符合条件的数。
新人教版四年级数学上册 笔算除法 森村中心学校 江国飞 1 、口算。 360÷30= 840÷40= 200÷50= 270÷90= 40÷20= ÷40=3600÷19≈30 90÷30=3 900÷31≈30.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
绩效考评表格设计 班级:15服务4班 姓名:杨冬茜.
§2线性规划问题及其数学模型 线性规划作为运筹学的一人重要分支,是研究较早,理论较完善,应用最广泛的一门科学。它所研究的问题主要包括两个方面:一是在一项任务确定后,如何以最低限度和成本(如人力、物力、资金和时间等)去完成这一任务;二是如何在现有条件下进行组织和安排,以完成更多的工作。因此,线性规划就是求一组变量的值,使它满足一组线性式子,并使一个线性函数的值最大(或最小)的数学方法。
第四章 运输问题 4.1 运输问题 4.2 运输问题的表上作业法 4.3 运输问题的进一步讨论.
第二章 工程经济分析的基本要素 教师:武科 副教授.
活动课 有趣的组合.
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
小学生游戏.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
直线和圆的位置关系.
探索三角形相似的条件(2).
学习情境九 物流运输决策.
Harvard ManageMentor®
第 3 章 基本概念.
元素替换法 ——行列式按行(列)展开(推论)
段磊 王慧锋 TEL: qq群: 数据库系统原理课程设计 实验环节2 段磊 王慧锋 TEL: qq群:
Online job scheduling in Distributed Machine Learning Clusters
大作业要求 1、按照选题要求设计电路,并仿真、下载,实现电路。 2、撰写综合报告.
Transportation Problem
动态规划(Dynamic Programming)
绿色圃中小学教育网 比例 比例的意义 绿色圃中小学教育网
本节内容 平行线的性质 4.3.
2.1.2 空间中直线与直线 之间的位置关系.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
解决变化问题的自底向上 流程建模方法 严志民 徐玮.
线段的有关计算.
线性规 Linear Programming
(Integer Programming)
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
统筹安排   成本最低.
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
运输问题 运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论 指派问题 数学试验.
用计算器开方.
统筹安排   成本最低.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
iSIGHT 基本培训 使用 Excel的栅栏问题
用穷举法设计程序 南京师范大学 教育技术系 倪佳慧
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
数据集的抽取式摘要 程龚, 徐丹云.
1.非线性规划模型 2.非线性规划的Matlab形式
海报题目 简介: 介绍此项仿真工作的目标和需要解决的问题。 可以添加合适的图片。
第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化
2014年终总结.
《工程制图基础》 第五讲 投影变换.
分数再认识三 真假带分数的练习课.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
导 言 经济学的基本问题 经济学的基本研究方法 需求和供给.
§2 方阵的特征值与特征向量.
2、5、3的倍数的特征.
投资建议书 XXX有限公司 制作人: 制作日期: mp2_v_styleguide_ ppt 1.
基于列存储的RDF数据管理 朱敏
任选四个不同的数字,组成一个最大的数和一个最小的数。用最大的数减去最小的数。用所得结果的四位数重复上述过程,最多七步,必得6174
线性规划 Linear Programming
§4.5 最大公因式的矩阵求法( Ⅱ ).
一元一次方程的解法(-).
海报题目 简介: 介绍此项仿真工作的目标和需要解决的问题。 可以添加合适的图片。
Presentation transcript:

运输问题模型

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

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

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

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

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

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

运输问题基本描述及解决方法 例:某公司有三个加工厂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

运输问题基本描述及解决方法 主要解决方法——表上作业法 解题思路: 关键环节: 找出初始基本可行解:在产销平衡表上给出(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箱,而配送中心的订单不变。求解该问题的运输方案。 销地 产地 B1 B2 B3 产量 A1 13 15 12 78 A2 11 29 22 45 销量 53 36 65 销大于产

运输问题的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

运输问题的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

运输问题的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

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

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

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

运输问题的扩展案例分析求解 例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

运输问题的扩展案例分析求解 例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

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

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

人员指派问题及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

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

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

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

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

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

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

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

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

人员指派问题及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