物流运筹培训教材课件

物流运筹上海第二工业大学管理工程研究所

物流运筹上海第二工业大学管理工程研究所2001年4月国家颁布《物流术语》（GB/T18354Z－2001），同年8月实施。物流是“物品从供应地向接受地的实体流动过程。根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合”。运筹学是物流技术的数学基础。物流运筹是指物流技术中的运筹学。物流运筹2001年4月国家颁布《物流术语》（

运筹学（OperationsResearch），应用数学最优化（方法、理论），管理，软科学

•数学规划

•图、网络与网络技术

•对策论

•组合最优化

•决策分析

•动态规划

•随机服务系统物流运筹运筹学（OperationsResearch），应《物流运筹》课程的性质和任务

《物流运筹》是物流专业的一门公共课，4学分，72学时，其中理论教学38学时，习题课20学时，上机14学时。通过本课程的学习，特别是通过上机实验和实际计算，使学生掌握运筹学中最基本的模型化技术、数量化分析和最优化方法等，学会使用计算机软件解最基本的运筹学问题，培养学生运用定量化方法解决实际问题的能力，为学习后继课程，学习职业基础课和职业技术课打下基础，提供必要的工具和方法。物流运筹《物流运筹》课程的性质和任务物流运筹《物流运筹》课程的主要内容包括线性规划、单纯形法、人工变量法、对偶问题、灵敏度分析、对偶变量的经济解释、运输问题、指派问题、最小支撑树问题、最短路问题、最大流问题、网络计划（PERT）等。物流运筹《物流运筹》课程的主要内容物流运筹《物流运筹》课程的上机实验和实际计算美国WinQsb教学软件物流运筹《物流运筹》课程的物流运筹1.数学规划线性规划运输问题2.图、网络与网络技术哥尼斯堡七座桥问题最小支撑树、最短路问题、网络上的最大流问题、网络计划（PERT、关键路线法）3.对策论田忌赛马和孙膑献策4.组合最优化怎么样把20个人排成一行都列出来——《排序论》初步装卸工问题物流运筹1.数学规划物流运筹1.数学规划数学规划

•线性规划、运输问题、指派问题

•非线性规划

•目标规划线性规划线性的约束线性的目标函数1.数学规划数学规划线性规划1.数学规划

例1.1-1:某工厂生产I、II两种饼干，需用A、B、C三种类型的设备。每吨饼干在生产中需要占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：

饼干I饼干II工时数设备A（搅拌机）3515设备B（成形机）215设备C（烘箱）2211利润（百元/吨）54

1.数学规划例1.1-1:某工厂生产I、II两种1.数学规划

问题：工厂应如何安排生产可获得最大的利润？解：设变量xi为第i种（甲、乙）产品的每天的生产量（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：

maxz=5x1+4x2

s.t.3x1+5x2≤152x1+x2≤52x1+2x2

≤11

x1,x2≥01.数学规划问题：工厂应如何安排生产可获得最大1.数学规划一般形式

目标函数：min(max)z=c1x1+c2x2+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn(*)b1a21x1+a22x2+…+a2nxn(*)b2(1.6)...am1x1+am2x2+…+amnxn(*)bmx1

，x2

，…，xn≥01.数学规划一般形式约束条件：1.数学规划运输问题一般的运输问题就是要解决把某种产品从若干个产地（发点）调运到若干个销地（收点），在每个产地的供应量（发量）与每个销地的需求量（收量）已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1.数学规划运输问题1.数学规划

收点发点B1B2…Bn发量A1

x11c11x12c12

…x1nc1n

a1A2x21c21

x22c22

…x2nc2n

a2┇┇┇┇┇┇Amxm1cm1

xm2cm2

…xmncmn

am收量b1b2…bn

ab1.数学规划收点B1B2…Bn发量A1x11.数学规划线性规划单纯形法内点法初始解（两阶段法，大M法），迭代运输问题位势法初始解（西北角法，最小元素法），迭代1.数学规划线性规划1.数学规划

（初始）解是否是最优解？停止是否改进（初始）解最优化问题的求解思路1.数学规划（初始）解是否是停止是否改进（初始1.哥尼斯堡七座桥问题德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。

2.图、网络与网络技术1.哥尼斯堡七座桥问题2.图、网络与网络技术

2.图、网络与网络技术ABABCD

2.图、网络与网络技术ABABCD

当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉把这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是经典图论中的第一个著名问题。2.图、网络与网络技术

当地的居民热衷于这样一个问题，一个漫步者如何

2.图、网络与网络技术ACDB

2.图、网络与网络技术ACDB2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术

最小支撑树

在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。2.图、网络与网络技术

最小支撑树2.图、网络与网络技术Kruskal算法

步骤1.把图中所有的边，按照每一条边的权从小到大的次序排列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从排列中划去。

2.图、网络与网络技术Kruskal算法2.图、网络与网络技术

Kruskal算法

步骤2.

如果排列中已经没有边，那么得到的支撑树就是最小支撑树，算法终止；否则，检查排列中最前面的一条边，转步骤3。2.图、网络与网络技术

Kruskal算法2.图、网络与网络技术

Kruskal算法

步骤3.

如果选取最前面的边与已经有的支撑树不会形成圈，就把它加到支撑树中去，并把它从排列中划去；否则，直接把它从排列中划去，转步骤2。2.图、网络与网络技术

Kruskal算法2.图、网络与网络技术2.图、网络与网络技术v6v5v2v3v46275354411，2，3，4，4，5，5，6，7v1v3v212.图、网络与网络技术v6v5v2v3v4627535442.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4122.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v53122.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v6v531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v6v531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v1v4v6v5531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术v3v2v1v4v6v5531421，2，3，4，4，5，5，6，7

已经得到最小支撑树，最小支撑树的权=1+2+3+4+5=15。在一棵树中点的个数为n，边的个数为n-1。如果再加一条边，一定会产生圈。v6v5v2v3v4627535441v12.图、网络与网络技术v3v2v1v4v6v5531421网络计划技术PERT(ProgramEvaluationandReviewTechnique)

网络图是一种网络。网络图中每一条弧（有向边）表示工程的一个活动，点表示事项。一个活动相关联的两个点（事项）中一个是开工事项，另一个是完工事项。紧前活动和紧后活动。2.图、网络与网络技术网络计划技术PERT2.图、网络与网络技术网络弧：(工程)活动点：事项、结点活动名称

ij

活动时间2.图、网络与网络技术网络2.图、网络与网络技术活动名称:市场调研活动代号：A活动表示：(1,2)活动时间：8（天）紧前活动：-

A1282.图、网络与网络技术活动名称:市场调研2.图、网络与网络技术网络图的一些规定（1）两个活动有相同的开工事项和完工事项时要引入虚活动，避免这种情况发生。（2）不能有缺口，只能有一个起点和一个终点。没有紧前活动的用虚活动合并成一个起点，没有紧后活动用虚活动合并成一个终点。2.图、网络与网络技术网络图的一些规定2.图、网络与网络技术

（3）活动用名称A,B…来表示，也可以相关联的两个点（事项）来表示。（4）对点进行编号时不一定要连号，但对每一个活动来讲开工事项的编号必须小于完工事项的编号。（5）虚活动画成虚箭头，只表示活动之间的衔接关系，活动时间等于零。通常用O来表示。2.图、网络与网络技术（3）活动用名称A,B…来表示，也可以BABAO112322.图、网络与网络技术BABAO112322.图、网络与网络技术B,CCGD活动代号紧前活动GCDBC2.图、网络与网络技术B,CCGD活动代号紧前活动GCDBC2.图、网络与网B,CCGD活动代号紧前活动GCDBO2.图、网络与网络技术B,CCGD活动代号紧前活动GCDBO2.图、网络与网IBEDCAGFHJ2.图、网络与网络技术IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ123456782.图、网络与网络技术结点编号IBEDCAGFHJ123456782.图、网络与活动代号

紧前活动A—BACADAE—F—HD，EIFJFKC，H，ILB，KMC，H，I，J活动代号紧前活动A—BACADAE—F—HD，EIFJFK

紧前活动为—的合并成为网络图的起点，紧前活动栏中没有出现字母的合并成为网络图的和终点。2.图、网络与网络技术紧前活动为—的合并成为网络图的起点，紧前活动栏中EAFLMEAFLMIBEDCAKFH12345678JLMO2.图、网络与网络技术IBEDCAKFH12345678JLMO2.图、网络与网活动代号紧前活动活动代号紧前活动A—MEB—ND，ECBXHDBPFEBRNFCWMGCZX，P，RHA，G活动代号紧前活动活动代号紧前活动A—MEB—ND，ECBXHBAZW2.图、网络与网络技术BAZW2.图、网络与网络技术NBEDCAPFH12345678XZMO9101112GRW2.图、网络与网络技术NBEDCAPFH12345678XZMO9101112GR结点的两个时间参数

（1）结点i的最早时间TE(i)：从头开始顺向计算，进来取最大。（2）结点i的最迟时间TL(i)

：从尾开始逆向计算，出去取最小。结点编号最早时间最迟时间iTE(i)TL(i)2.图、网络与网络技术结点的两个时间参数结点编号最早最迟iTE(i)TL(i)2.

工程的总工期：最后一个结点的最早时间活动表示(i,j)

活动时间tij2.图、网络与网络技术2.图、网络与网络技术活动代号紧前活动活动时间A—5B—6CA3DA2EB，C4FB，C7GD，E4HD，E6IG3JF，G，H5O02.图、网络与网络技术活动代号紧前活动活动时间A—5B—6CA3DA2EB，C4FIBEDCAGFH32345671234567OJ46052.图、网络与网络技术IBEDCAGFH32345671234567OJ46052IBEDCAGFH32345671234567OJ460502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605052.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ46050582.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058122.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058121618232.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823232.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ46050581216182323182.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058121618232318182.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818122.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050活动6个时间参数（1）活动(i,j)的最早开工时间TES(i,j)＝开工事项(结点)i的最早时间TE(i)。（2）活动(i,j)的最早完工时间TEF(i,j)＝开工事项(结点)i的最早时间TE(i)

＋活动时间tij活动6个时间参数（3）活动(i,j)的最迟开工时间TLS(i,j)＝完工事项(结点)j的最迟时间TL(j)

－活动时间tij（4）活动(i,j)的最迟完工时间TLF(i,j)＝完工事项(结点)j的最迟时间TL(j)2.图、网络与网络技术（3）活动(i,j)的最迟开工时间TLS(i,j)2.（5）活动(i,j)的总时差R(i,j)，即不推迟总工期的前提下活动(i,j)完工的机动时间＝活动(i,j)的最迟完工时间TLF(i,j)－活动(i,j)的最早完工时间TEF(i,j)从表格中计算2.图、网络与网络技术（5）活动(i,j)的总时差R(i,j)，即不推迟总工期（6）活动(i,j)的单时差r(i,j)，即不推迟紧后活动最早开工的前提下活动(i,j)完工的机动时间＝结点j的最早时间TE(j)－活动(i,j)的最早完工时间TEF(i,j)=结点j的最早时间TE(j)－结点i的最早时间TE(i)－活动时间tij从图中计算（6）活动(i,j)的单时差r(i,j)，即不推迟紧后

关键活动：总时差为0的活动。用*来表示。

关键路线：网络图中从起点到终点的一条路全部是由关键活动所组成。用双线（或粗线）来表示。2.图、网络与网络技术关键活动：总时差为0的活动。用*来表示。2活动代号紧前活动活动表示活动时间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*0O01616181822活动代号紧前活动活动表示活动时间最早时间最迟时间总时差单时差IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050

关键路线是A—C—E—H—J。总工期是23。2.图、网络与网络技术关键路线是A—C—E—H—J。2.图、网络与小结“最早”是由“前面”决定的；“最迟”是由“后面”决定的。“最早”表示可以，推迟不会影响总工期；“最迟”表示必须，推迟必定影响总工期。

2.图、网络与网络技术小结2.图、网络与网络技术

例如，结点的最早时间是从“头”（网络的起点）开始，顺向计算；结点的最迟时间是从“尾”（网络的终点）开始，逆向计算。又如，活动(i,j)的最早开工时间和最早完工时间是由前面的结点i的最早时间决定，也就是由“前面”决定的；活动(i,j)的最迟开工时间和最迟完工时间是由后面的结点j的最迟时间决定的，也是“后面”决定的。2.图、网络与网络技术例如，结点的最早时间是从“头”（网络

总时差和单时差表示活动完工时间的机动时间。总时差是不推迟总工期的前提下，活动完工时间的机动时间；单时差是不推迟紧后活动最早开工的前提下，活动完工时间的机动时间。2.图、网络与网络技术总时差和单时差表示活动完工时间的机动

田忌赛马和孙膑献策公元前4世纪战国时期齐国的将领田忌经常与齐王和公子们赛马。有一次齐王要与田忌赛马，齐王的马都比田忌的马要强，但相差不多。在齐王宣布三次出场马的次序为上中下后，如果田忌也以他自己的上中下出场，那么势必三场皆输。孙膑献策，以田忌的下马对齐王的上马，田忌的上马对齐王的中马，田忌的中马对齐王的下马，结果一负两胜。

[上][下]齐胜、[中][上]田胜、[下][中]田胜3.对策论

田忌赛马和孙膑献策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

平均完工时间=(C2+

C3+C1)/3=24/3=8

有三个工件要在一台机器上加工：4.组合最优5.怎么样把20个人排成一行都列出来——《排序论》初步

20!=2.4329020×10181年=365×24×60×60秒=3.1536×107秒每秒运算10亿次=109次/秒

20!/(1年×10亿次/秒)=7.7年

最优化方法：初始排法，改进，直到最优。4.

组合最优化5.怎么样把20个人排成一行都列出来——《排序论》初步4.工件名称j

1

2就绪时间rj

0

1

加工时间pj

5

2

应交货时间dj7.53.5完工时间

Cj延误时间Tj=max{Cj-dj,0}4.

组合最优化工件名称j14.

组合最优化d2=3.5d1=7.5T1=0,T2=(5+2)-3.5=3.5T1+T2=0+3.5=3.5T2=0,T1=(1+2+5)–7.5=0.5T1+T2=0+0.5=0.5T2=0,T1=0T1+T2=0+0=04.组合最优化d2=3.5d1=7.5T1=0,T2=

排序（scheduling）既有“分配（allocation）”的作用，是把被加工的对象“工件”分配给提供加工的对象“机器”以便进行加工；又有“排序”的功能，有被加工的对象“工件”的次序和提供加工的对象“机器”的次序这两类次序的安排；还有“调度”的效果，是在于把“机器”和“工件”按时间进行调度.“工件”何时就绪，何时安装，何时开始加工，何时中断加工（preempt），何时更换“工件”，何时再继续加工原“工件”，直到何时结束加工；“机器”何时就绪，何时进行加工，何时空闲（idle），何时更换“机器”等等.这些都是按时间进行“分配”、“排序”和“调度”.

4.

组合最优化

排序（scheduling）既有“分配（all

《现代排序论》“上海科技专著出版资金”唐国春、张峰、罗守成、刘丽丽2003年5月第一次印刷，1100册2003年12月第二次印刷，1100册台湾78元4.

组合最优化

《现代排序论》4.组合最优化可控排序成组分批排序在线排序同时加工排序准时排序和窗时排序不同时开工排序资源受限排序随机排序模糊排序多目标排序

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+tjyj

eij，其中tj是描述在站点Bj处雇佣的装卸工在能力和素质上与运输公司跟车装卸工的差别.试求在每辆车Ai上跟车装卸工的人数xi和在每个站点Bj处雇佣装卸工的人数yj，使总的装卸费用为最小.装卸工问题设运输公司有m辆货车Ai(装卸工问题mins.t.

xi+tjyj

eij,i=1,...,m;j=1,...,n

xi

ci,i=1,...,m

yj

dj,j=1,...,n

xi0,整数，i=1,...,m

yj0,整数，j=1,...,n装卸工问题min

mins.t.

sixi+tjyj

eij,i=1,...,m；j=1,...,n

xi

ci,i=1,...,m

（P1）

yj

dj,j=1,...,n

xi

0,整数，i=1,...,m

yj

0,整数，j=1,...,n装卸工问题写成比较对称的形式装卸工问题写成比较对称的形式装卸工问题

问题（P1）作为整数规划，可以讨论参数ci,dj,si,tj,pi,qj,eij中取值为零或负数的情况，但从装卸工问题的实际背景出发，我们假设参数ci,dj,si,tj,eij

(i=1,...,m；j=1,...,n)等都是正整数，参数pi,qj

(i=1,...,m；j=1,...,n)等都是正数.参数si和tj是反映货车Ai上和站点Bj处装卸工的工作环境和人员素质；pi和qj是支付给一位装卸工的费用；ci,dj,是货车Ai上和站点Bj处装卸工的人数限制；eij是反映货车Ai上货物到站点Bj处装卸的要求（包括货物的种类、数量）.

装卸工问题问题（P1）作为整数规划，可以讨论参数ci

2.1限制情况下的装卸工问题

mins.t.

sixi+tjyj=eij,i=1,...,m；j=1,...,n

xi

ci,i=1,...,m

（P2）

yj

dj,j=1,...,n

xi

0,整数，i=1,...,m

yj

0,整数，j=1,...,n装卸工问题

2.1限制情况下的装卸工问题装卸工问题

当只有一辆货车的时装卸工问题为：装卸工问题当只有一辆货车的时装卸工问题为：装卸工问题

对一台货车和两个站点的问题可以用图解.

装卸工问题

对一台货车和两个站点的问题可以用图解.装卸

x

y2ocd2装卸工问题y1d1e1e1e2e2可行域是一个8面体.

限制问题的可行域是这个8面体的一条边.

xy2ocd2装卸工问题y1d1e1e1e2e2可行域是

x

y2ocd2装卸工问题y1d1e1e1e2e2可行域是一个8面体.

限制问题的可行域是这个8面体的一条边.

xy2ocd2装卸工问题y1d1e1e1e2e2可行域是

2.2相同装卸工的情况

装卸工问题装卸工问题运输问题的对偶问题

2.2相同装卸工的情况装卸工问题装卸工问题运输问装卸工问题相同装卸工的情况一般装卸工问题装卸工问题相同装卸工的情况一般装卸工问题

2.3装卸工问题的NP难解性

（3）深入研究的方向

3.1除了问题（P2）和（P3）之外，寻找和证明其它特殊的装卸工问题是P问题.3.2寻找性能优良的近似算法.例如，把问题（P2）和（P3）的最优解作为问题（P1）的近似解，可以分析这些近似解的“性态”和估计它们的“界”.装卸工问题

2.3装卸工问题的NP难解性装卸工问题

3.3装卸工问题（P1）的应用研究，寻找和发现在数学、管理、计算机、物流等领域中可以归结为整数规划（P1）的问题.3.4讨论整数规划（P1）中参数ci,dj,si,tj,pi,qj,eij

(i=1,...,m；j=1,...,n)中取值为零或负数的情况.

装卸工问题

3.3装卸工问题（P1）的应用研究，寻找和发现在数学、管1号楼（综合楼）

1309室50214473gctang@

物流运筹1号楼（综合楼）

物流运筹物流运筹谢谢！物流运筹谢谢！

物流运筹上海第二工业大学管理工程研究所

物流运筹上海第二工业大学管理工程研究所2001年4月国家颁布《物流术语》（GB/T18354Z－2001），同年8月实施。物流是“物品从供应地向接受地的实体流动过程。根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机结合”。运筹学是物流技术的数学基础。物流运筹是指物流技术中的运筹学。物流运筹2001年4月国家颁布《物流术语》（

运筹学（OperationsResearch），应用数学最优化（方法、理论），管理，软科学

•数学规划

•图、网络与网络技术

•对策论

•组合最优化

•决策分析

•动态规划

•随机服务系统物流运筹运筹学（OperationsResearch），应《物流运筹》课程的性质和任务

《物流运筹》是物流专业的一门公共课，4学分，72学时，其中理论教学38学时，习题课20学时，上机14学时。通过本课程的学习，特别是通过上机实验和实际计算，使学生掌握运筹学中最基本的模型化技术、数量化分析和最优化方法等，学会使用计算机软件解最基本的运筹学问题，培养学生运用定量化方法解决实际问题的能力，为学习后继课程，学习职业基础课和职业技术课打下基础，提供必要的工具和方法。物流运筹《物流运筹》课程的性质和任务物流运筹《物流运筹》课程的主要内容包括线性规划、单纯形法、人工变量法、对偶问题、灵敏度分析、对偶变量的经济解释、运输问题、指派问题、最小支撑树问题、最短路问题、最大流问题、网络计划（PERT）等。物流运筹《物流运筹》课程的主要内容物流运筹《物流运筹》课程的上机实验和实际计算美国WinQsb教学软件物流运筹《物流运筹》课程的物流运筹1.数学规划线性规划运输问题2.图、网络与网络技术哥尼斯堡七座桥问题最小支撑树、最短路问题、网络上的最大流问题、网络计划（PERT、关键路线法）3.对策论田忌赛马和孙膑献策4.组合最优化怎么样把20个人排成一行都列出来——《排序论》初步装卸工问题物流运筹1.数学规划物流运筹1.数学规划数学规划

•线性规划、运输问题、指派问题

•非线性规划

•目标规划线性规划线性的约束线性的目标函数1.数学规划数学规划线性规划1.数学规划

例1.1-1:某工厂生产I、II两种饼干，需用A、B、C三种类型的设备。每吨饼干在生产中需要占用设备的工时数，每吨饼干可以获得的利润以及三种设备可利用的工时数如下表所示：

饼干I饼干II工时数设备A（搅拌机）3515设备B（成形机）215设备C（烘箱）2211利润（百元/吨）54

1.数学规划例1.1-1:某工厂生产I、II两种1.数学规划

问题：工厂应如何安排生产可获得最大的利润？解：设变量xi为第i种（甲、乙）产品的每天的生产量（i＝1，2）。根据前面分析，可以建立如下的线性规划模型：

maxz=5x1+4x2

s.t.3x1+5x2≤152x1+x2≤52x1+2x2

≤11

x1,x2≥01.数学规划问题：工厂应如何安排生产可获得最大1.数学规划一般形式

目标函数：min(max)z=c1x1+c2x2+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn(*)b1a21x1+a22x2+…+a2nxn(*)b2(1.6)...am1x1+am2x2+…+amnxn(*)bmx1

，x2

，…，xn≥01.数学规划一般形式约束条件：1.数学规划运输问题一般的运输问题就是要解决把某种产品从若干个产地（发点）调运到若干个销地（收点），在每个产地的供应量（发量）与每个销地的需求量（收量）已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1.数学规划运输问题1.数学规划

收点发点B1B2…Bn发量A1

x11c11x12c12

…x1nc1n

a1A2x21c21

x22c22

…x2nc2n

a2┇┇┇┇┇┇Amxm1cm1

xm2cm2

…xmncmn

am收量b1b2…bn

ab1.数学规划收点B1B2…Bn发量A1x11.数学规划线性规划单纯形法内点法初始解（两阶段法，大M法），迭代运输问题位势法初始解（西北角法，最小元素法），迭代1.数学规划线性规划1.数学规划

（初始）解是否是最优解？停止是否改进（初始）解最优化问题的求解思路1.数学规划（初始）解是否是停止是否改进（初始1.哥尼斯堡七座桥问题德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。

2.图、网络与网络技术1.哥尼斯堡七座桥问题2.图、网络与网络技术

2.图、网络与网络技术ABABCD

2.图、网络与网络技术ABABCD

当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉把这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是经典图论中的第一个著名问题。2.图、网络与网络技术

当地的居民热衷于这样一个问题，一个漫步者如何

2.图、网络与网络技术ACDB

2.图、网络与网络技术ACDB2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术2.图、网络与网络技术

最小支撑树

在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这一类问题。2.图、网络与网络技术

最小支撑树2.图、网络与网络技术Kruskal算法

步骤1.把图中所有的边，按照每一条边的权从小到大的次序排列起来，并选取最前面的一条边，作为支撑树的第一条边，把它从排列中划去。

2.图、网络与网络技术Kruskal算法2.图、网络与网络技术

Kruskal算法

步骤2.

如果排列中已经没有边，那么得到的支撑树就是最小支撑树，算法终止；否则，检查排列中最前面的一条边，转步骤3。2.图、网络与网络技术

Kruskal算法2.图、网络与网络技术

Kruskal算法

步骤3.

如果选取最前面的边与已经有的支撑树不会形成圈，就把它加到支撑树中去，并把它从排列中划去；否则，直接把它从排列中划去，转步骤2。2.图、网络与网络技术

Kruskal算法2.图、网络与网络技术2.图、网络与网络技术v6v5v2v3v46275354411，2，3，4，4，5，5，6，7v1v3v212.图、网络与网络技术v6v5v2v3v4627535442.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4122.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v53122.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v6v531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v4v6v531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术1，2，3，4，4，5，5，6，7v6v5v2v3v4627535441v1v3v2v1v4v6v5531422.图、网络与网络技术1，2，3，4，4，5，5，6，7v2.图、网络与网络技术v3v2v1v4v6v5531421，2，3，4，4，5，5，6，7

已经得到最小支撑树，最小支撑树的权=1+2+3+4+5=15。在一棵树中点的个数为n，边的个数为n-1。如果再加一条边，一定会产生圈。v6v5v2v3v4627535441v12.图、网络与网络技术v3v2v1v4v6v5531421网络计划技术PERT(ProgramEvaluationandReviewTechnique)

网络图是一种网络。网络图中每一条弧（有向边）表示工程的一个活动，点表示事项。一个活动相关联的两个点（事项）中一个是开工事项，另一个是完工事项。紧前活动和紧后活动。2.图、网络与网络技术网络计划技术PERT2.图、网络与网络技术网络弧：(工程)活动点：事项、结点活动名称

ij

活动时间2.图、网络与网络技术网络2.图、网络与网络技术活动名称:市场调研活动代号：A活动表示：(1,2)活动时间：8（天）紧前活动：-

A1282.图、网络与网络技术活动名称:市场调研2.图、网络与网络技术网络图的一些规定（1）两个活动有相同的开工事项和完工事项时要引入虚活动，避免这种情况发生。（2）不能有缺口，只能有一个起点和一个终点。没有紧前活动的用虚活动合并成一个起点，没有紧后活动用虚活动合并成一个终点。2.图、网络与网络技术网络图的一些规定2.图、网络与网络技术

（3）活动用名称A,B…来表示，也可以相关联的两个点（事项）来表示。（4）对点进行编号时不一定要连号，但对每一个活动来讲开工事项的编号必须小于完工事项的编号。（5）虚活动画成虚箭头，只表示活动之间的衔接关系，活动时间等于零。通常用O来表示。2.图、网络与网络技术（3）活动用名称A,B…来表示，也可以BABAO112322.图、网络与网络技术BABAO112322.图、网络与网络技术B,CCGD活动代号紧前活动GCDBC2.图、网络与网络技术B,CCGD活动代号紧前活动GCDBC2.图、网络与网B,CCGD活动代号紧前活动GCDBO2.图、网络与网络技术B,CCGD活动代号紧前活动GCDBO2.图、网络与网IBEDCAGFHJ2.图、网络与网络技术IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ2.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ12.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ122.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ1232.图、网络与网络技术结点编号IBEDCAGFHJ123456782.图、网络与网络技术结点编号IBEDCAGFHJ123456782.图、网络与活动代号

紧前活动A—BACADAE—F—HD，EIFJFKC，H，ILB，KMC，H，I，J活动代号紧前活动A—BACADAE—F—HD，EIFJFK

紧前活动为—的合并成为网络图的起点，紧前活动栏中没有出现字母的合并成为网络图的和终点。2.图、网络与网络技术紧前活动为—的合并成为网络图的起点，紧前活动栏中EAFLMEAFLMIBEDCAKFH12345678JLMO2.图、网络与网络技术IBEDCAKFH12345678JLMO2.图、网络与网活动代号紧前活动活动代号紧前活动A—MEB—ND，ECBXHDBPFEBRNFCWMGCZX，P，RHA，G活动代号紧前活动活动代号紧前活动A—MEB—ND，ECBXHBAZW2.图、网络与网络技术BAZW2.图、网络与网络技术NBEDCAPFH12345678XZMO9101112GRW2.图、网络与网络技术NBEDCAPFH12345678XZMO9101112GR结点的两个时间参数

（1）结点i的最早时间TE(i)：从头开始顺向计算，进来取最大。（2）结点i的最迟时间TL(i)

：从尾开始逆向计算，出去取最小。结点编号最早时间最迟时间iTE(i)TL(i)2.图、网络与网络技术结点的两个时间参数结点编号最早最迟iTE(i)TL(i)2.

工程的总工期：最后一个结点的最早时间活动表示(i,j)

活动时间tij2.图、网络与网络技术2.图、网络与网络技术活动代号紧前活动活动时间A—5B—6CA3DA2EB，C4FB，C7GD，E4HD，E6IG3JF，G，H5O02.图、网络与网络技术活动代号紧前活动活动时间A—5B—6CA3DA2EB，C4FIBEDCAGFH32345671234567OJ46052.图、网络与网络技术IBEDCAGFH32345671234567OJ46052IBEDCAGFH32345671234567OJ460502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605052.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ46050582.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058122.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058121618232.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823232.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ46050581216182323182.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ4605058121618232318182.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818122.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050活动6个时间参数（1）活动(i,j)的最早开工时间TES(i,j)＝开工事项(结点)i的最早时间TE(i)。（2）活动(i,j)的最早完工时间TEF(i,j)＝开工事项(结点)i的最早时间TE(i)

＋活动时间tij活动6个时间参数（3）活动(i,j)的最迟开工时间TLS(i,j)＝完工事项(结点)j的最迟时间TL(j)

－活动时间tij（4）活动(i,j)的最迟完工时间TLF(i,j)＝完工事项(结点)j的最迟时间TL(j)2.图、网络与网络技术（3）活动(i,j)的最迟开工时间TLS(i,j)2.（5）活动(i,j)的总时差R(i,j)，即不推迟总工期的前提下活动(i,j)完工的机动时间＝活动(i,j)的最迟完工时间TLF(i,j)－活动(i,j)的最早完工时间TEF(i,j)从表格中计算2.图、网络与网络技术（5）活动(i,j)的总时差R(i,j)，即不推迟总工期（6）活动(i,j)的单时差r(i,j)，即不推迟紧后活动最早开工的前提下活动(i,j)完工的机动时间＝结点j的最早时间TE(j)－活动(i,j)的最早完工时间TEF(i,j)=结点j的最早时间TE(j)－结点i的最早时间TE(i)－活动时间tij从图中计算（6）活动(i,j)的单时差r(i,j)，即不推迟紧后

关键活动：总时差为0的活动。用*来表示。

关键路线：网络图中从起点到终点的一条路全部是由关键活动所组成。用双线（或粗线）来表示。2.图、网络与网络技术关键活动：总时差为0的活动。用*来表示。2活动代号紧前活动活动表示活动时间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*0O01616181822活动代号紧前活动活动表示活动时间最早时间最迟时间总时差单时差IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050IBEDCAGFH32345671234567OJ460505812161823231818128502.图、网络与网络技术IBEDCAGFH32345671234567OJ46050

关键路线是A—C—E—H—J。总工期是23。2.图、网络与网络技术关键路线是A—C—E—H—