物流运筹

物流运筹上海第二工业大学管理工程研究所2001年4月国家颁布《物流术语》（GB/T18354Z－2001），同年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三种类型的设备。每吨饼干在生产中需要占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：饼干I饼干II工时数设备A（搅拌机）3515设备B（成形机）215设备C（烘箱）2211利润（百元/吨）541.数学规划问题：工厂应如何安排生产可获得最大的利润？解：设变量xi为第i种（甲、乙）产品的每天的生产量（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：maxz=5x1+4x2s.t.3x1+5x2≤152x1+x2≤52x1+2x2≤11x1,x2≥01.数学规划•一般形式•目标函数：min(max)z=c1x1+c2x2+…+cnxn•约束条件：a11x1+a12x2+…+a1nxn(*)b1a21x1+a22x2+…+a2nxn(*)b2(1.6)...am1x1+am2x2+…+amnxn(*)bmx1，x2，…，xn≥01.数学规划运输问题一般的运输问题就是要解决把某种产品从若干个产地（发点）调运到若干个销地（收点），在每个产地的供应量（发量）与每个销地的需求量（收量）已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1.数学规划收点发点B1B2…Bn发量A1x11c11x12c12…x1nc1na1A2x21c21x22c22…x2nc2na2┇┇┇┇┇┇Amxm1cm1xm2cm2…xmncmnam收量b1b2…bnab1.数学规划线性规划•单纯形法•内点法•初始解（两阶段法，大M法），迭代运输问题•位势法•初始解（西北角法，最小元素法），迭代1.数学规划（初始）解是否是最优解？停止是否改进（初始）解最优化问题的求解思路1.哥尼斯堡七座桥问题德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。2.图、网络与网络技术2.图、网络与网络技术ABABCD当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉把这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是经典图论中的第一个著名问题。2.图、网络与网络技术2.图、网络与网络技术ACDB2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术最小支撑树在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。2.图、网络与网络技术Kruskal算法步骤1.把图中所有的边，按照每一条边的权从小到大的次序排列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从排列中划去。2.图、网络与网络技术Kruskal算法步骤2.如果排列中已经没有边，那么得到的支撑树就是最小支撑树，算法终止；否则，检查排列中最前面的一条边，转步骤3。2.图、网络与网络技术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，7v6v5v2v3v4627535441v1v3v2v4v6v531422.图、网络与网络技术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。如果再加一条边，一定会产生圈。v6v5v2v3v4627535441v1网络计划技术PERT(ProgramEvaluationandReviewTechnique)网络图是一种网络。网络图中每一条弧（有向边）表示工程的一个活动，点表示事项。一个活动相关联的两个点（事项）中一个是开工事项，另一个是完工事项。紧前活动和紧后活动。2.图、网络与网络技术网络弧：(工程)活动点：事项、结点活动名称ij活动时间2.图、网络与网络技术活动名称:市场调研活动代号：A活动表示：(1,2)活动时间：8（天）紧前活动：-A1282.图、网络与网络技术网络图的一些规定（1）两个活动有相同的开工事项和完工事项时要引入虚活动，避免这种情况发生。（2）不能有缺口，只能有一个起点和一个终点。没有紧前活动的用虚活动合并成一个起点，没有紧后活动用虚活动合并成一个终点。2.图、网络与网络技术（3）活动用名称A,B…来表示，也可以相关联的两个点（事项）来表示。（4）对点进行编号时不一定要连号，但对每一个活动来讲开工事项的编号必须小于完工事项的编号。（5）虚活动画成虚箭头，只表示活动之间的衔接关系，活动时间等于零。通常用O来表示。2.图、网络与网络技术BABAO112322.图、网络与网络技术B,CCGD活动代号紧前活动GCDBC2.图、网络与网络技术B,CCGD活动代号紧前活动GCDBO2.图、网络与网络技术IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ123456782.图、网络与网络技术活动代号紧前活动A—BACADAE—F—HD，EIFJFKC，H，ILB，KMC，H，I，J紧前活动为—的合并成为网络图的起点，紧前活动栏中没有出现字母的合并成为网络图的和终点。2.图、网络与网络技术EAFLMIBEDCAKFH12345678JLMO2.图、网络与网络技术活动代号紧前活动活动代号紧前活动A—MEB—ND，ECBXHDBPFEBRNFCWMGCZX，P，RHA，GBAZW2.图、网络与网络技术NBEDCAPFH12345678XZMO9101112GRW2.图、网络与网络技术结点的两个时间参数（1）结点i的最早时间TE(i)：从头开始顺向计算，进来取最大。（2）结点i的最迟时间TL(i)：从尾开始逆向计算，出去取最小。结点编号最早时间最迟时间iTE(i)TL(i)2.图、网络与网络技术工程的总工期：最后一个结点的最早时间活动表示(i,j)活动时间tij2.图、网络与网络技术活动代号紧前活动活动时间A—5B—6CA3DA2EB，C4FB，C7GD，E4HD，E6IG3JF，G，H5O02.图、网络与网络技术IBEDCAGFH32345671234567OJ46052.图、网络与网络技术IBEDCAGFH32345671234567OJ460502.图、网络与网络技术IBEDCAGFH32345671234567OJ4605052.图、网络与网络技术IBEDCAGFH32345671234567OJ46050582.图、网络与网络技术IBEDCAGFH32345671234567OJ4605058122.图、网络与网络技术IBEDCAGFH32345671234567OJ4605058121618232.图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823232.图、网络与网络技术IBEDCAGFH32345671234567OJ46050581216182323182.图、网络与网络技术IBEDCAGFH32345671234567OJ4605058121618232318182.图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823231818122.图、网络与网络技术IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术活动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的活动。用*来表示。关键路线：网络图中从起点到终点的一条路