物流运筹培训教材(PPT 107页).ppt

物流运筹,上海第二工业大学管理工程研究所,2001年4月国家颁布物流术语（GB/T18354Z2001），同年8月实施。物流是“物品从供应地向接受地的实体流动过程。根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合”。运筹学是物流技术的数学基础。物流运筹是指物流技术中的运筹学。,物流运筹,运筹学（OperationsResearch），应用数学最优化（方法、理论），管理，软科学数学规划图、网络与网络技术对策论组合最优化决策分析动态规划随机服务系统,物流运筹,物流运筹课程的性质和任务物流运筹是物流专业的一门公共课，4学分，72学时，其中理论教学38学时，习题课20学时，上机14学时。通过本课程的学习，特别是通过上机实验和实际计算，使学生掌握运筹学中最基本的模型化技术、数量化分析和最优化方法等，学会使用计算机软件解最基本的运筹学问题，培养学生运用定量化方法解决实际问题的能力，为学习后继课程，学习职业基础课和职业技术课打下基础，提供必要的工具和方法。,物流运筹,物流运筹课程的主要内容包括线性规划、单纯形法、人工变量法、对偶问题、灵敏度分析、对偶变量的经济解释、运输问题、指派问题、最小支撑树问题、最短路问题、最大流问题、网络计划（PERT）等。,物流运筹,物流运筹课程的上机实验和实际计算美国WinQsb教学软件,物流运筹,1.数学规划线性规划运输问题2.图、网络与网络技术哥尼斯堡七座桥问题最小支撑树、最短路问题、网络上的最大流问题、网络计划（PERT、关键路线法）3.对策论田忌赛马和孙膑献策4.组合最优化怎么样把20个人排成一行都列出来排序论初步装卸工问题,物流运筹,1.数学规划,数学规划线性规划、运输问题、指派问题非线性规划目标规划,线性规划线性的约束线性的目标函数,1.数学规划,例1.1-1:某工厂生产I、II两种饼干，需用A、B、C三种类型的设备。每吨饼干在生产中需要占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：,1.数学规划,问题：工厂应如何安排生产可获得最大的利润？解：设变量xi为第i种（甲、乙）产品的每天的生产量（i1，2）。根据前面分析，可以建立如下的线性规划模型：maxz=5x1+4x2s.t.3x1+5x2152x1+x252x1+2x211x1,x20,1.数学规划,一般形式目标函数：min(max)z=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn(*)b1a21x1+a22x2+a2nxn(*)b2(1.6).am1x1+am2x2+amnxn(*)bmx1，x2，xn0,1.数学规划,运输问题一般的运输问题就是要解决把某种产品从若干个产地（发点）调运到若干个销地（收点），在每个产地的供应量（发量）与每个销地的需求量（收量）已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,1.数学规划,a,b,1.数学规划,线性规划单纯形法内点法初始解（两阶段法，大M法），迭代运输问题位势法初始解（西北角法，最小元素法），迭代,1.数学规划,（初始）解,是否是最优解？,停止,是,否,改进（初始）解,最优化问题的求解思路,1.哥尼斯堡七座桥问题德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。,2.图、网络与网络技术,2.图、网络与网络技术,A,B,A,B,C,D,当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉把这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是经典图论中的第一个著名问题。,2.图、网络与网络技术,2.图、网络与网络技术,A,C,D,B,2.图、网络与网络技术,2.图、网络与网络技术,2.图、网络与网络技术,最小支撑树在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。,2.图、网络与网络技术,Kruskal算法步骤1.把图中所有的边，按照每一条边的权从小到大的次序排列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从排列中划去。,2.图、网络与网络技术,Kruskal算法步骤2.如果排列中已经没有边，那么得到的支撑树就是最小支撑树，算法终止；否则，检查排列中最前面的一条边，转步骤3。,2.图、网络与网络技术,Kruskal算法步骤3.如果选取最前面的边与已经有的支撑树不会形成圈，就把它加到支撑树中去，并把它从排列中划去；否则，直接把它从排列中划去，转步骤2。,2.图、网络与网络技术,2.图、网络与网络技术,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,1，2，3，4，4，5，5，6，7,v1,v3,v2,1,2.图、网络与网络技术,1，2，3，4，4，5，5，6，7,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,v3,v2,v4,1,2,2.图、网络与网络技术,1，2，3，4，4，5，5，6，7,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,v3,v2,v4,v5,3,1,2,2.图、网络与网络技术,1，2，3，4，4，5，5，6，7,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,v3,v2,v4,v6,v5,3,1,4,2,2.图、网络与网络技术,1，2，3，4，4，5，5，6，7,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,v3,v2,v4,v6,v5,3,1,4,2,2.图、网络与网络技术,1，2，3，4，4，5，5，6，7,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,v3,v2,v1,v4,v6,v5,5,3,1,4,2,2.图、网络与网络技术,v3,v2,v1,v4,v6,v5,5,3,1,4,2,1，2，3，4，4，5，5，6，7,已经得到最小支撑树，最小支撑树的权=1+2+3+4+5=15。在一棵树中点的个数为n，边的个数为n-1。如果再加一条边，一定会产生圈。,v6,v5,v2,v3,v4,6,2,7,5,3,5,4,4,1,v1,网络计划技术PERT(ProgramEvaluationandReviewTechnique)网络图是一种网络。网络图中每一条弧（有向边）表示工程的一个活动，点表示事项。一个活动相关联的两个点（事项）中一个是开工事项，另一个是完工事项。紧前活动和紧后活动。,2.图、网络与网络技术,网络弧：(工程)活动点：事项、结点活动名称ij活动时间,2.图、网络与网络技术,活动名称:市场调研活动代号：A活动表示：(1,2)活动时间：8（天）紧前活动：-A128,2.图、网络与网络技术,网络图的一些规定（1）两个活动有相同的开工事项和完工事项时要引入虚活动，避免这种情况发生。（2）不能有缺口，只能有一个起点和一个终点。没有紧前活动的用虚活动合并成一个起点，没有紧后活动用虚活动合并成一个终点。,2.图、网络与网络技术,（3）活动用名称A,B来表示，也可以相关联的两个点（事项）来表示。（4）对点进行编号时不一定要连号，但对每一个活动来讲开工事项的编号必须小于完工事项的编号。（5）虚活动画成虚箭头，只表示活动之间的衔接关系，活动时间等于零。通常用O来表示。,2.图、网络与网络技术,B,A,B,A,O,1,1,2,3,2,2.图、网络与网络技术,B,C,C,G,D,活动代号,紧前活动,G,C,D,B,C,2.图、网络与网络技术,B,C,C,G,D,活动代号,紧前活动,G,C,D,B,O,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,J,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2,3,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2,3,2.图、网络与网络技术,结点编号,I,B,E,D,C,A,G,F,H,J,1,2,3,4,5,6,7,8,2.图、网络与网络技术,紧前活动为的合并成为网络图的起点，紧前活动栏中没有出现字母的合并成为网络图的和终点。,2.图、网络与网络技术,E,A,F,L,M,I,B,E,D,C,A,K,F,H,1,2,3,4,5,6,7,8,J,L,M,O,2.图、网络与网络技术,B,A,Z,W,2.图、网络与网络技术,N,B,E,D,C,A,P,F,H,1,2,3,4,5,6,7,8,X,Z,M,O,9,10,11,12,G,R,W,2.图、网络与网络技术,结点的两个时间参数（1）结点i的最早时间TE(i)：从头开始顺向计算，进来取最大。（2）结点i的最迟时间TL(i)：从尾开始逆向计算，出去取最小。,结点编号,最早时间,最迟时间,i,TE(i),TL(i),2.图、网络与网络技术,工程的总工期：最后一个结点的最早时间活动表示(i,j)活动时间tij,2.图、网络与网络技术,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,18,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,18,12,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,18,12,8,5,0,2.图、网络与网络技术,活动6个时间参数（1）活动(i,j)的最早开工时间TES(i,j)开工事项(结点)i的最早时间TE(i)。（2）活动(i,j)的最早完工时间TEF(i,j)开工事项(结点)i的最早时间TE(i)活动时间tij,（3）活动(i,j)的最迟开工时间TLS(i,j)完工事项(结点)j的最迟时间TL(j)活动时间tij（4）活动(i,j)的最迟完工时间TLF(i,j)完工事项(结点)j的最迟时间TL(j),2.图、网络与网络技术,（5）活动(i,j)的总时差R(i,j)，即不推迟总工期的前提下活动(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.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,18,12,8,5,0,2.图、网络与网络技术,I,B,E,D,C,A,G,F,H,3,2,3,4,5,6,7,1,2,3,4,5,6,7,O,J,4,6,0,5,0,5,8,12,16,18,23,23,18,18,12,8,5,0,2.图、网络与网络技术,关键路线是ACEHJ。总工期是23。,2.图、网络与网络技术,小结“最早”是由“前面”决定的；“最迟”是由“后面”决定的。“最早”表示可以，推迟不会影响总工期；“最迟”表示必须，推迟必定影响总工期。,2.图、网络与网络技术,例如，结点的最早时间是从“头”（网络的起点）开始，顺向计算；结点的最迟时间是从“尾”（网络的终点）开始，逆向计算。又如，活动(i,j)的最早开工时间和最早完工时间是由前面的结点i的最早时间决定，也就是由“前面”决定的；活动(i,j)的最迟开工时间和最迟完工时间是由后面的结点j的最迟时间决定的，也是“后面”决定的。,2.图、网络与网络技术,总时差和单时差表示活动完工时间的机动时间。总时差是不推迟总工期的前提下，活动完工时间的机动时间；单时差是不推迟紧后活动最早开工的前提下，活动完工时间的机动时间。,2.图、网络与网络技术,田忌赛马和孙膑献策公元前4世纪战国时期齐国的将领田忌经常与齐王和公子们赛马。有一次齐王要与田忌赛马，齐王的马都比田忌的马要强，但相差不多。在齐王宣布三次出场马的次序为上中下后，如果田忌也以他自己的上中下出场，那么势必三场皆输。孙膑献策，以田忌的下马对齐王的上马，田忌的上马对齐王的中马，田忌的中马对齐王的下马，结果一负两胜。上下齐胜、中上田胜、下中田胜,3.对策论,现代对策论（博弈论）的基本思想是不能求大胜时，要保不大败，不恋局部败负，务操全局胜算。在两千多年前，我国古代就有这样的运筹学思想并用于实践是很了不起的成就。经典对策论，下棋、比赛、战争，局中人，零和博弈双赢,3.对策论,有三个工件要在一台机器上加工：工件名称j123加工时间pj825完工时间Cj,4.组合最优化,C1=8,C2=8+2=10,C3=8+2+5=15平均完工时间=(C1+C2+C3)/3=33/3=11,C2=2,C3=2+5=7,C1=2+5+8=15平均完工时间=(C2+C3+C1)/3=24/3=8,5.怎么样把20个人排成一行都列出来排序论初步20!=2.432902010181年=365246060秒=3.1536107秒每秒运算10亿次=109次/秒20!/(1年10亿次/秒)=7.7年最优化方法：初始排法，改进，直到最优。,4.组合最优化,工件名称j12就绪时间rj01加工时间pj52应交货时间dj7.53.5完工时间Cj延误时间Tj=maxCj-dj,0,4.组合最优化,4.组合最优化,d2=3.5,d1=7.5,T1=0,T2=(5+2)-3.5=3.5T1+T2=0+3.5=3.5,T2=0,T1=(1+2+5)7.5=0.5T1+T2=0+0.5=0.5,T2=0,T1=0T1+T2=0+0=0,排序（scheduling）既有“分配（allocation）”的作用，是把被加工的对象“工件”分配给提供加工的对象“机器”以便进行加工；又有“排序”的功能，有被加工的对象“工件”的次序和提供加工的对象“机器”的次序这两类次序的安排；还有“调度”的效果，是在于把“机器”和“工件”按时间进行调度.“工件”何时就绪，何时安装，何时开始加工，何时中断加工（preempt），何时更换“工件”，何时再继续加工原“工件”，直到何时结束加工；“机器”何时就绪，何时进行加工，何时空闲（idle），何时更换“机器”等等.这些都是按时间进行“分配”、“排序”和“调度”.,4.组合最优化,现代排序论“上海科技专著出版资金”唐国春、张峰、罗守成、刘丽丽2003年5月第一次印刷，1100册2003年12月第二次印刷，1100册台湾78元,4.组合最优化,可控排序成组分批排序在线排序同时加工排序准时排序和窗时排序不同时开工排序资源受限排序随机排序模糊排序多目标排序,4.组合最优化,设运输公司有m辆货车Ai(i=1,2,m)要向n个站点Bj(j=1,2,n)装卸货物.运输公司要在每辆货车上安排跟车的装卸工，也可以在每个站点上雇佣当地的装卸工.货车Ai上跟车的装卸工必须装卸向所有n个站点装卸的货物，最多可以跟车的装卸工人数是ci，支付给每位跟车装卸工的费用是pi；在站点Bj处雇佣的装卸工必须装卸所有m辆货车到这个站点上装卸的货物，最多可以雇佣的装卸工人数是dj，支付给每位雇佣装卸工的费用是qj.如果用xi表示在货车Ai上跟车装卸工的人数，用yj表示在站点Bj处雇佣当地装卸工的人数，又已知货车Ai在站点Bj处执行装卸任务时需要装卸工的最少人数是eij，那么对i=1,2,m，j=1,2,n必须满足xi+tjyjeij，其中tj是描述在站点Bj处雇佣的装卸工在能力和素质上与运输公司跟车装卸工的差别.试求在每辆车Ai上跟车装卸工的人数xi和在每个站点Bj处雇佣装卸工的人数yj，使总的装卸费用为最小.,装卸工问题,装卸工问题,mins.t.xi+tjyjeij,i=1,.,m;j=1,.,nxici,i=1,.,myjdj,j=1,.,nxi0,整数，i=1,.,myj0,整数，j=1,.,n,mins.t.sixi+tjyjeij,i=1,.,m；j=1,.,nxici,i=1,.,m（P1）yjdj,j=1,.,nxi0,整数，i=1,.,myj0,整数，j=1,.,n,装卸工问题,写成比较对称的形式,装卸工问题,问题（P1）作为整数规划，可以讨论参数ci,dj,si,tj,pi,qj,ei