物流运筹学预备知识.ppt

第二章　预备知识 第一节　矩阵及其运算 一、引例 某厂2007、2008两年生产Ｘ、Ｙ、Ｚ三种型号的电脑，每年产量如表2-1 二、矩阵的概念 一、引例 求： 各型号的两年总产量 每年的总成本、总产值、总利润 两年来的总成本、总产值、总利润 分析：抽取单位我们可以概括地指出 本引例中的每个表格可表示为一个矩阵 上面的三个问题的实质分别是：矩阵的加法（向量的加法）、乘法及混合代数运算。 二、矩阵的概念 矩阵的定义： 由m×n个数据按m行n列作有序排列而成的矩形数表，称为m行n列矩阵，或称m×n矩阵，记为Ａm×n。 m×n称为矩阵的容量。其中每一个数称为矩阵的元素，位于第i行第j列的元素记为aij. 特殊矩阵 二、矩阵的概念 矩阵的数乘 矩阵的加法 矩阵的加法练习 矩阵的乘法 矩阵的转置 作业： Ｐ26:１、２、３ 第二节　图与网络 点与线路 上图是广州地铁线路图，该图是由站与线路（地铁铁路）组成。类似的例子有很多。 如：铁路网中的火车站与铁路、公路网中的汽车站与公路、电话线路网中的电话局与电话线…… 我们把这些站、局等对象加以抽象，称之为点，把铁路、公路、电话线路等对象加以抽象，称之为线，而把同相应的点和线组成的图形称之为图。 图的概念 孤立点：不与任何边关联的点 （例如右图中的Ｖ5） 简单图与多重图 简单图、多重图：不含环与多重边的图称为简单图，含有多重边的图称为多重图， 完全图 每一对不同的顶点都有一条边相连的简单图称为完全图。有n个顶点的完全图一般记为Kn 二分图 二分图 G=(N,E)：存在的一个二分划(S,T)，使得G的每条边有一个端点在S中，另一个端点在T中 完全二分图 G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图 奇点与偶点 设v∈V是图Ｇ＝（Ｖ，Ｅ）的一个顶点，则称Ｇ中与顶点v关联的边的个数为顶点v的度，记为dG(v).度为奇数的顶点称为奇点；度为偶数的顶点称为偶点。 在任何图中，各点度的总和必是该图边数的２倍。在任何图中奇点的个数必为偶数。 子图与支撑子图 权 为了更好地描述事物，在图的边的上往往有一些描述的数量指标，称之为权。权可以代表距离、费用、通过能力等。 网络 各边带有一个非负实数权的图称为网络或者赋权图。边e旁边的非负实数称为边e的权，一般记为W(e).例如某配送中心Ｖs与各门店v1、v2、v3、v4之间的公路网络，每条边的权数就是两个端点之间的里程数。 简单图网络的邻接权矩阵 设简单图网络Ｄ＝（Ｖ，Ｅ，Ｗ（Ｅ）），具有||Ｖ||＝n个顶点，网络Ｄ的邻接权矩阵Ｗ（Ｄ）是一个n阶方阵（wij)nXn.其中，当顶点vi与顶点vj相邻接时，wij是顶点vi和顶点vj的邻接边上的权值；当顶点vi和顶点vj不相邻接时，wij取∞。 无向图与有向图 无向图：图G= (V,E)中，若对所有的边均有ek=(vi , vj) = (vj , vi) ，则称G为无向图，记为G= (V,E) 。 有向图若图中边(vi , vj)的端点是有序的，即以vi为来点vj为去点，则称该图为有向图，记为D= (V,A) 。在有向图中，把边改称为弧，A为D中弧的集合，边可以看成两条方向相反的弧。 出度与入度 设v是有向图Ｄ＝（Ｖ，Ｅ）的一个顶点，则称以v为始点的弧的数目为点v的出度，记为 ,称以v为终点的弧的数目为点v的入度，记为 有向网络 每条弧都有一个非负实数的有向图被称为有向网络，或者有向赋权图；每条弧的旁边的非负实数称为该弧的权。 第三节　路和回路 链与简单链 路 点边序列中只有重复的点而无重复边的链称为简单链； 点边序列中没有重复的点和重复边者称为初等链； 首尾相接的链称为圈。 一条没有重复顶点的的链Ｐ则称为路Ｐ； 回路 闭链:无向图 G =（ V , E ）中首尾顶点相同的一条链称为 G 的闭链。 简单闭链: G 中首尾顶点相同的一条简单链称为 G 的简单闭链。 回路:G 中首尾顶点相同的一条路称为 G 的回路 例如，在图 2-6 中的图 G 中,（v2v3v4v2v5v4v2）是一条闭链，而（ v2v3v4v5v2 ) 是一条回路。 有向路 设有向图 D＝（ V , E ）中存在一个由顶点和弧构成的交替序列Ｐ＝ ( v0e1vle2v2 … vk-1ekvk），使得其中每一条弧前面的那个顶点恰好是该弧的始点，后面的那个顶点恰好是该弧的终点，则称P是有向图 D 的一条从顶点v0到顶点vk的有向链，或称为（v0,vk）有向链。若有向链Ｐ中没有重复出现的弧，则称 P 是简单有向链；若有向链Ｐ中没有重复出现的顶点，则称Ｐ是有向路。 例如，在图2-8的有向图 D 中，Ｐ1＝(vsv2v1v5v2vlv4vt ）是一条从vs到vt的有向链，但不是简单有向链，因为弧（v