物流运筹ppt课件

1、物流运筹上海第二工业大学管理工程研讨所 2001年4月国家公布GB/T18354Z2001，同年8月实施。 物流是“物品从供应地向接受地的实体流动过程。根据实践需求，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处置等根本功能实施有机结合 。 运筹学是物流技术的数学根底。物流运筹是指物流技术中的运筹学。物流运筹 运筹学Operations Research，运用数学 最优化方法、实际，管理，软科学 数学规划 图、网络与网络技术 对策论 组合最优化 决策分析 动态规划 随机效力系统物流运筹课程的性质和义务 是物流专业的一门公共课，4学分，72学时，其中实际教学38学时，习题课20学时，上机

2、14学时。经过本课程的学习，特别是经过上机实验和实践计算，使学生掌握运筹学中最根本的模型化技术、数量化分析和最优化方法等，学会运用计算机软件解最根本的运筹学问题，培育学生运用定量化方法处理实践问题的才干，为学习后继课程，学习职业根底课和职业技术课打下根底，提供必要的工具和方法。物流运筹课程的主要内容 包括线性规划、单纯形法、人工变量法、对偶问题、灵敏度分析、对偶变量的经济解释、运输问题、指派问题、最小支撑树问题、最短路问题、最大流问题、网络方案PERT等。物流运筹课程的上机实验和实践计算美国WinQsb教学软件物流运筹1.数学规划线性规划运输问题2.图、网络与网络技术哥尼斯堡七座桥问题最小支撑

3、树、最短路问题、网络上的最大流问题、网络方案PERT、关键道路法3.对策论田忌赛马和孙膑献策4.组合最优化怎样样把20个人排成一行都列出来初步装卸工问题物流运筹1. 数学规划数学规划 线性规划、运输问题、指派问题 非线性规划 目的规划线性规划线性的约束线性的目的函数1. 数学规划 例1.1-1:某工厂消费I、II两种饼干，需用A、B、C三种类型的设备。每吨饼干在消费中需求占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：饼干I饼干II工时数设备A搅拌机3515设备B成形机215设备C烘箱2211利润百元/吨541. 数学规划 问题：工厂应如何安排消费可获得最大的利润

4、？ 解：设变量xi为第i种甲、乙产品的每天的消费量i1，2。根据前面分析，可以建立如下的线性规划模型： max z = 5 x1 + 4x2 s.t. 3x1+ 5x2 15 2x1+ x2 5 2x1+ 2x2 11 x1, x2 01. 数学规划普通方式 目的函数：min(max)z = c1x1 + c2x2 + + cnxn 约束条件： a11x1+a12x2+a1nxn ( * )b1a21x1+a22x2+a2nxn ( * )b2 (1.6) . . . am1x1+am2x2 +amnxn ( * )bm x1 ，x2 ， ，xn 01. 数学规划运输问题 普通的运输问题就是要

5、处理把某种产品从假设干个产地发点调运到假设干个销地收点，在每个产地的供应量发量与每个销地的需求量收量知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1. 数学规划 收点发点B1B2Bn发量A1 x11c11 x12 c12 x1n c1n a1 A2 x21 c21 x22 c22 x2n c2n a2 Am xm1cm1 xm2 cm2 xmn cmn am收量b1b2bnab1. 数学规划线性规划单纯形法内点法初始解两阶段法，大M法，迭代运输问题位势法初始解西北角法，最小元素法，迭代1. 数学规划 初始解能否是最优解？停顿是否改良初始解最优化问题的求解思绪1.

6、哥尼斯堡七座桥问题 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互衔接，如以下图所示。 2. 图、网络与网络技术2. 图、网络与网络技术ABABCD 当地的居民热衷于这样一个问题，一个散步者如何可以走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。虽然实验者很多，但是都没有胜利。 为了寻觅答案，1736年欧拉把这个问题笼统成一笔画问题，即能否从某一点开场不反复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不能够的，由于这个图形中每一个顶点都与奇数条边相衔接，不能够将它一笔画出，这就是经典图论中的第一个著名问题。2. 图、网络与网络技术2.

7、图、网络与网络技术ACDB2. 图、网络与网络技术2. 图、网络与网络技术2. 图、网络与网络技术最小支撑树 在知的几个城市之间结合线网，要求总长度最短和总建立费用最少，可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归结为这一类问题。2. 图、网络与网络技术Kruskal算法 步骤1. 把图中一切的边，按照每一条边的权从小到大的次序陈列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从陈列中划去。2. 图、网络与网络技术Kruskal算法 步骤2. 假设陈列中曾经没有边，那么得到的支撑树就是最小支撑树，算法终止；否那么，检查陈列中最前面的一条边，转步骤3。2. 图、网络与

8、网络技术 Kruskal算法 步骤3. 假设选取最前面的边与曾经有的支撑树不会构成圈，就把它加到支撑树中去， 并把它从陈列中划去；否那么，直接把它从陈列中划去，转步骤2。2. 图、网络与网络技术2. 图、网络与网络技术v6v5v2v3v46275354411，2，3，4，4，5，5，6，7v1v3v212. 图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4122. 图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v53122. 图、网络与网络技术1，2，3，4，4，5，5，6，7

9、v6v5v2v3v4627535441v1v3v2v4v6v531422. 图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v6v531422. 图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v1v4v6v5531422. 图、网络与网络技术v3v2v1v4v6v5531421，2，3，4，4，5，5，6，7 曾经得到最小支撑树，最小支撑树的权=1+2+3+4+5=15。 在一棵树中点的个数为n，边的个数为n-1。假设再加一条边，一定会产生圈。v6v5v2v3v4627535441

10、v1网络方案技术PERT(Program Evaluation and Review Technique) 网络图是一种网络。网络图中每一条弧有向边表示工程的一个活动，点表示事项。一个活动相关联的两个点事项中一个是开工事项，另一个是完工事项。紧前活动和紧后活动。2. 图、网络与网络技术网络弧：(工程)活动点：事项、结点 活动称号 i j 活动时间2. 图、网络与网络技术活动称号:市场调研活动代号：A活动表示：(1,2)活动时间：8天紧前活动：- A 1 2 82. 图、网络与网络技术网络图的一些规定 1两个活动有一样的开工事项和完工事项时要引入虚活动，防止这种情况发生。 2不能有缺口，只能有一

11、个起点和一个终点。没有紧前活动的用虚活动合并成一个起点，没有紧后活动用虚活动合并成一个终点。2. 图、网络与网络技术 3活动用称号A,B来表示，也可以相关联的两个点事项 来表示。 4对点进展编号时不一定要连号，但对每一个活动来讲开工事项的编号必需小于完工事项的编号。 5虚活动画成虚箭头，只表示活动之间的衔接关系，活动时间等于零。通常用O来表示。2. 图、网络与网络技术BABAO112322. 图、网络与网络技术B,CCGD活动代号 紧前活动 GCDBC2. 图、网络与网络技术B,CCGD活动代号 紧前活动 GCDBO2. 图、网络与网络技术IBEDCAGFHJ2. 图、网络与网络技术结点编号I

12、BEDCAGFHJ2. 图、网络与网络技术结点编号IBEDCAGFHJ12. 图、网络与网络技术结点编号IBEDCAGFHJ12. 图、网络与网络技术结点编号IBEDCAGFHJ122. 图、网络与网络技术结点编号IBEDCAGFHJ122. 图、网络与网络技术结点编号IBEDCAGFHJ1232. 图、网络与网络技术结点编号IBEDCAGFHJ1232. 图、网络与网络技术结点编号IBEDCAGFHJ123456782. 图、网络与网络技术活动代号 紧前活动ABACADAEFHD，EIFJFKC，H，ILB，KMC，H，I，J 紧前活动为的合并成为网络图的起点，紧前活动栏中没有出现字母的合并

13、成为网络图的和终点。2. 图、网络与网络技术EAFLMIBEDCAKFH12345678JLMO2. 图、网络与网络技术活动代号紧前活动活动代号紧前活动AMEBND，ECBXHDBPFEBRNFCWMGCZX，P，RHA，GBAZW2. 图、网络与网络技术NBEDCAPFH12345678XZMO9101112GRW2. 图、网络与网络技术结点的两个时间参数 1结点i的最早时间TE(i)：从头开场顺向计算 ，进来取最大。 2结点i的最迟时间TL(i) ：从尾开场逆向计算 ，出去取最小。结点编号最早时间最迟时间iTE(i)TL(i)2. 图、网络与网络技术 工程的总工期：最后一个结点的最早时间

14、活动表示(i, j) 活动时间tij2. 图、网络与网络技术活动代号紧前活动活动时间A5B6CA3DA2EB，C4FB，C7GD，E4HD，E6IG3JF，G，H5O02. 图、网络与网络技术IBEDCAGFH32345671234567OJ46052. 图、网络与网络技术IBEDCAGFH32345671234567OJ460502. 图、网络与网络技术IBEDCAGFH32345671234567OJ4605052. 图、网络与网络技术IBEDCAGFH32345671234567OJ46050582. 图、网络与网络技术IBEDCAGFH32345671234567OJ460505812

15、2. 图、网络与网络技术IBEDCAGFH32345671234567OJ4605058121618232. 图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823232. 图、网络与网络技术IBEDCAGFH32345671234567OJ46050581216182323182. 图、网络与网络技术IBEDCAGFH32345671234567OJ4605058121618232318182. 图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823231818122. 图、网络与网络技术IBEDCAGF

16、H32345671234567OJ460505812161823231818128502. 图、网络与网络技术活动6个时间参数1活动(i, j)的最早开工时间TES(i, j)开工事项(结点)i的最早时间TE(i) 。2活动(i, j)的最早完工时间TEF(i, j)开工事项(结点)i的最早时间TE(i) 活动时间tij3活动(i, j)的最迟开工时间TLS(i, j)完工事项(结点)j的最迟时间TL(j) 活动时间tij4活动(i, j)的最迟完工时间TLF(i, j)完工事项(结点)j的最迟时间TL(j)2. 图、网络与网络技术5活动(i, j)的总时差R(i, j)，即不推迟总工期的前提

17、下活动(i, j)完工的机动时间活动(i, j)的最迟完工时间TLF(i, j) 活动(i, j)的最早完工时间TEF(i, j)从表格中计算2. 图、网络与网络技术6活动(i, j)的单时差r(i, j) ，即不推迟紧后活动最早开工的前提下活动(i, j)完工的机动时间结点 j的最早时间TE(j)活动(i, j)的最早完工时间TEF(i, j)=结点 j的最早时间TE(j) 结点 i的最早时间TE(i) 活动时间tij从图中计算 关键活动：总时差为0的活动。用*来表示。 关键道路：网络图中从起点到终点的一条路全部是由关键活动所组成。用双线或粗线来表示。2. 图、网络与网络技术活动代号紧前活动

18、活动表示活动时间tij最早时间最迟时间总时差R单时差r开工ES完工EF开工LS完工LFA(1, 2)505050*0B(1, 3)6062822CA(2, 3)358580*0DA(2, 4)257101255EB, C(3, 4)48128120*0FB, C(3, 6)7815111833GD, E(4, 5)41216141820HD, E(4, 6)6121812180*0IG(5, 7)31619202344JF, G, H(6, 7)5182318230*0O01616181822IBEDCAGFH32345671234567OJ46050581216182323181812850

19、2. 图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823231818128502. 图、网络与网络技术 关键道路是ACEHJ。 总工期是23。2. 图、网络与网络技术小结“最早是由“前面决议的；“最迟是由“后面决议的。“最早表示可以，推迟不会影响总工期；“最迟表示必需，推迟必定影响总工期。 2. 图、网络与网络技术 例如，结点的最早时间是从“头网络的起点开场，顺向计算；结点的最迟时间是从“尾网络的终点开场，逆向计算。 又如，活动(i, j)的最早开工时间和最早完工时间是由前面的结点i的最早时间决议，也就是由“前面决议的；活动(i, j)的最迟开工

20、时间和最迟完工时间是由后面的结点j的最迟时间决议的，也是“后面决议的。2. 图、网络与网络技术 总时差和单时差表示活动完工时间的机动时间。 总时差是不推迟总工期的前提下，活动完工时间的机动时间； 单时差是不推迟紧后活动最早开工的前提下，活动完工时间的机动时间。2. 图、网络与网络技术 田忌赛马和孙膑献策 公元前4世纪战国时期齐国的将领田忌经常与齐王和公子们赛马。有一次齐王要与田忌赛马，齐王的马都比田忌的马要强，但相差不多。在齐王宣布三次出场马的次序为上中下后，假设田忌也以他本人的上中下出场，那么势必三场皆输。孙膑献策，以田忌的下马对齐王的上马，田忌的上马对齐王的中马，田忌的中马对齐王的下马，结

21、果一负两胜。 上下齐胜、中上田胜、下中田胜3. 对策论 现代对策论博弈论的根本思想是不能求大胜时，要保不大败，不恋部分败负，务操全局胜算。在两千多年前，我国古代就有这样的运筹学思想并用于实际是很了不起的成就。 经典对策论，下棋、竞赛、战争，局中人，零和博弈 双赢3. 对策论 有三个工件要在一台机器上加工：工件称号 j 1 2 3加工时间 pj 8 2 5 完工时间 Cj 4. 组合最优化 C1= 8, C2= 8+2=10, C3= 8+2+5=15 平均完工时间 = (C1 + C2+ C3) / 3 =33/3=11C2= 2, C3= 2+5=7, C1= 2+5+8=15 平均完工时间

22、 = (C2 + C3+ C1) / 3 =24/3=85.怎样样把20个人排成一行都列出来初步 20!=2.43290201018 1年=365246060秒=3.1536107秒 每秒运算10亿次=109次/秒 20!/(1年10亿次/秒)=7.7年最优化方法：初始排法，改良，直到最优。4. 组合最优化工件称号 j 1 2 就绪时间 rj 0 1 加工时间 pj 5 2 应交货时间 dj 7.5 3.5完工时间 Cj延误时间 Tj= maxCj- dj , 0 4. 组合最优化4. 组合最优化d2=3.5d1=7.5T1=0, T2= (5+2) - 3.5=3.5T1 +T2=0+3.5

23、=3.5T2=0, T1=(1+2+5) 7.5=0.5T1 +T2=0+0.5=0.5T2=0, T1=0T1 +T2=0+0=0 排序scheduling既有“分配allocation的作用，是把被加工的对象“工件分配给提供加工的对象“机器以便进展加工；又有“排序的功能，有被加工的对象“工件的次序和提供加工的对象“机器的次序这两类次序的安排；还有“调度的效果，是在于把“机器和“工件按时间进展调度. “工件何时就绪，何时安装，何时开场加工，何时中断加工preempt，何时改换“工件，何时再继续加工原“工件，直到何时终了加工；“机器何时就绪，何时进展加工，何时空闲idle，何时改换“机器等等.

24、 这些都是按时间进展“分配、“排序和“调度. 4. 组合最优化“上海科技专著出版资金唐国春、张峰、罗守成、刘丽丽2003年5月第一次印刷，1100册2003年12月第二次印刷，1100册台湾78元4. 组合最优化可控排序成组分批排序在线排序同时加工排序准时排序和窗时排序不同时开工排序资源受限排序随机排序模糊排序多目的排序4. 组合最优化 设运输公司有m辆货车Ai (i = 1, 2, , m)要向n个站点Bj (j = 1, 2, , n)装卸货物. 运输公司要在每辆货车上安排跟车的装卸工，也可以在每个站点上雇佣当地的装卸工. 货车Ai上跟车的装卸工必需装卸向一切n个站点装卸的货物，最多可以跟

25、车的装卸工人数是ci，支付给每位跟车装卸工的费用是pi；在站点Bj处雇佣的装卸工必需装卸一切m辆货车到这个站点上装卸的货物，最多可以雇佣的装卸工人数是dj，支付给每位雇佣装卸工的费用是qj. 假设用xi表示在货车Ai上跟车装卸工的人数，用yj表示在站点Bj处雇佣当地装卸工的人数，又知货车Ai在站点Bj处执行装卸义务时需求装卸工的最少人数是eij，那么对i = 1, 2, , m， j = 1, 2, , n必需满足xi + tjyj eij， 其中tj 是描画在站点Bj处雇佣的装卸工在才干和素质上与运输公司跟车装卸工的差别. 试求在每辆车Ai上跟车装卸工的人数xi和在每个站点Bj处雇佣装卸工的

26、人数yj，使总的装卸费用为最小. 装卸工问题装卸工问题min s.t. xi + tjyj eij, i = 1, ., m; j = 1, ., n xi ci, i = 1, ., m yj dj, j = 1, ., n xi 0, 整数，i = 1, ., m yj 0, 整数，j = 1, ., n min s.t. sixi + tjyj eij, i = 1, ., m；j = 1, ., nxi ci, i = 1, ., m P1yj dj, j = 1, ., nxi 0, 整数，i = 1, ., myj 0, 整数，j = 1, ., n装卸工问题写成比较对称的方式装卸工问题 问题P1作为整数规划，可以讨论参数ci, dj, si, tj, pi, qj, eij中取值为零或负数的情况，但从装卸工问题的实践背景出发，我们假设参数ci, dj, si, tj,