本教材主要介绍管理决策基础概念以及管理决策的定量分析技术。主要内容包括决策过程、线性规划、整数规划、运输问题、图与网络、*短路线、网络计划技术、存贮论和博弈论初步知识。本教材突出应用问题和案例,强调管理决策方法应用,并强调应用计算机软件求解问题。

第3章 图 与 网 络



图论(Graph Theory)所研究的对象是自然界和人类社会中包含二元关系的系统,其方法是将一个系统抽象为点和边构成的图,点表示事物,边表示事物之间的联系,然后根据图的性质进行分析。图论中的图与我们通常熟悉的几何学、解析几何和微积分中的图形不同。图论中不考虑点的位置和连接线的曲直长短,而只关心哪些点之间有线连接。
图论的研究源于欧拉(Euler)在1736年解决了当时闻名的哥尼斯堡七桥问题。欧拉被公认为是图论的奠基人。1847年,基尔赫夫(Kirchhoff)在研究电网时奠定了树的概念和理论。1857年,凯莱(Cayley)在研究饱和氢化合物同分异构体的结构时,独立地引入了树形图。早期的图论也与数学游戏有密切联系,如哈密顿(Hamilton)周游世界问题。20世纪后,图论的应用渗透到许多其他学科领域,如物理、化学、运筹学、社会学等。从20世纪50年代以后,由于计算机的迅速发展,有力推动了图论的发展,使图论成为数学领域中发展*快的分支之一。
图论提供了一个自然的结构,由此而产生的数学模型几乎适合于所有科学(自然科学和社会科学)领域,只要这个领域研究的主题是“对象”和“对象”之间的关系。
本章从七桥问题出发,生动形象地引出图论的基本概念。对图论中的几个经典问题,如*短路问题、*小支撑树问题和*大流问题的基本概念和求解方法进行介绍。
3.1 哥尼斯堡七桥问题
哥尼斯堡(K?nigsberg)是18世纪欧洲东普鲁士的一个风景秀丽的小城。有一条叫普莱格尔(Pregel)的河流经哥尼���堡。河的中间有两个小岛,河的两岸与两岛之间共建有七座桥(图3-1)。人们长期通过七座桥,来往于河的两岸和两岛。
有**,有人提出这样一个问题:“有没有办法从某处出发,经过每座桥一次且仅一次,*后回到原地呢?”这个经典问题就是“哥尼斯堡七桥问题”。
哥尼斯堡七桥问题一经提出,就吸引了当时无数居民,谁都想试一试。然而,走来走去,竟无一人获得成功。一些人除了亲自走一走外,还利用画图来寻找符合条件的漫步途径,但同样以失败而告终。

图3-1 哥尼斯堡七桥
我们也来试试看,能不能找到一种不重复走过每座桥,又能回到出发地的走法呢?还可以试试看,如果不要求回到出发点,只要求走遍所有的桥(当然,每座桥只许走一次),行不行呢?
我们知道随便试是不能解决这个问题,但我们可以通过以下几个步骤解决这个问题。
(1)编号:我们可以给七座轿都编上号。例如,编成1号桥、2号桥,…,7号桥,如图3-2所示。
(2)排列:如果有一种走遍七座桥的走法,那么这种走法一定是按照某一顺序走 的。例如,先走1号桥,然后依次2~7号,*后回到1号桥。我们可以把按照上述顺序的走法记作:1 2 3 4 5 6 7。这其实就是1,2,…,7这7个数字的一个排列。因此,如果存在一种走法,那么其走法一定是与一个排列对应的。我们可以把1,2,…,7的所有排列都写出来,这种排列共有7!=5 040个。
(3)判断可行:我们再来研究每一个排列,看看这个排列相对应的走法是否可行。例如,对于1 2 3 4 5 6 7这种走法,我们可以从岛上出发,或者从陆地出发,但从图3-2可以看出,不论从哪里出发,要想按1 2 3 4 5 6 7的顺序不重复地走遍七座桥是不可能的。对于其他排列,也可以用类似的方法来试验,如果把5040个排列都试完了,就能知道是否能够找到一条符合要求的走法。

图3-2 试走哥尼斯堡七桥
我们用的编号、排列,判断可行的这套方法,实质上就是“枚举法”。那么这种方法好吗?
这种方法当然要比乱试好,只要有时间,慢慢地试下去,总是可以找出答案的。但是,这种方法还不是很理想,因为如果再碰到一个问题,有?20座桥,也要找一条每座桥只走一次的走法,那就要试个20!=2432902008176640000排列,每个排列即使只算1分钟,我们一辈子也算不完。
可见,枚举法求解费时,而且即使解出,结论也不具有一般意义。
对于看似简单,实则复杂的哥尼斯堡七桥问题,有没有更具一般性的解决方法?
1735年8月26日,瑞士数学家欧拉向当时的俄国圣彼得堡科学院提交了一篇名为《有关位置几何的一个问题的解》的论文①,阐述了他对哥尼斯堡七桥问题的否定解答。
在文中,欧拉还就此类问题进行了一般性意义的讨论:“若连接奇数座桥的地点多于两个,则找不到符合要求的路线;若仅有两个地点与奇数座桥相连,则可从这两个地点的任意一个出发,找出符合要求的路线;若没有一个地点是通往奇数座桥的,则无论从哪个地点出发,都能找到所要求的路线。”
1892年英国数学家罗兹·鲍尔出版的《数学游戏与古今问题》中,将哥尼斯堡七桥问题中所见到的陆地和桥分别抽象为点和线。
为了弄清楚这个抽象化的过程,我们可以这样想,对于七桥问题来说,桥的长度显然是不起作用的,岛的大小、岸的宽窄等因素也是不起作用的,因此可以把图3-1重新画一下,把桥画得长一些,把岛画得小一些,即画成图3-3的样子。请大家把图3-1与图3-3对比一下,不难看出,在图3-3上研究“能否不重复地走遍七座桥”和在图3-1中研究是完全一样的。
然后,我们把岛和岸再缩小一些,缩小成一个点,就可以得到图3-4。这样,我们就把原来的那张由岛、岸和桥等构成的图抽象成了一张由点和线构成的新图。


图3-3 哥尼斯堡七桥问题
图3-4 哥尼斯堡七桥问题点线图
进一步,我们可以知道,解答以下这两个问题是一样的:“有没有办法从某处出发,经过每座桥一次且仅一次,*后回到原地呢?”和“能不能从图3-4中某一个顶点开始,把图3-4不重复地一笔画出来,*后又回到起点?”。
这里我们说的一笔画,指的是用笔不离纸的方式来画图,且每条线都只能画一次而不能重复。
那么一个图形在满足什么条件时才可以用“一笔画”的方式画出?
在一笔画中,我们把与奇数条边相连的点称为奇点;与偶数条边相连的点称为偶 点。欧拉在这两个简单概念的基础上,找到了一笔画定理,可以鉴别任一图形能不能一笔画出。②
一笔画定理:
(1)可以一笔画成的图形,与偶点个数无关,与奇点个数有关。其奇点个数是0或2。
(2)若奇点个数为0,可选任一个点做起点,且一笔画后可以回到起点。
(3)若奇点个数为2,可选其中一个奇点做起点,而终点一定是另一个奇点,即一笔画后不可以回到起点。
应用一笔画定理,我们可以知道,在哥尼斯堡七桥问题中是没有办法从某处出发,经过每座桥一次且仅一次,*后回到原地的。
一笔画问题显然是一个几何问题。但是,一笔画问题却是欧几里得几何学所没有研究过的。欧几里得几何学(即中学里的平面几何和立体几何)研究的图形,都由点、线和面组成,讨论的是长度、角度、面积等的性质。
一笔画问题里线条的长短曲直无关紧要,点的位置大小无关紧要。在一笔画中,要紧的只是点线之间的相关位置,或相互联结的情况。所以欧拉把这类几何问题的研究称为位置几何学。
虽然,欧拉在解决哥尼斯堡七桥问题时并未用到现代意义的“图”,但欧拉解决这一问题的论文是图论史上的**篇重要文献。
3.2 图论的基本概念
在实际问题中,人们常用图来表示所研究的对象及这些研究对象之间的某种特定 关系。
在图论中,点和线的位置是按照研究方便而随意放置的,点的位置并不是实际的地理位置,边的形状也不是实际的形状,边的长度并不是按照实际的比例绘制的。图论中所说的图,与我们以前接触过的几何图形、函数图形、机械制图、建筑设计图都是不同的。我们所关注的是图中有多少个点,这些点之间的连接形式如何。
图论中的图的基本要素就是点和连接点的线。
1. 图的基本概念和定义
设V={v_1,v_2,?,v_n }是n个元素的非空集合,E={e_1,e_2,?,e_m }是m个元素的集合,若对于任一e_k∈E,均有v_i,v_j∈V与之对应,则称V∪E为图,记为G=(V,E)。
2. 顶点、边、端点、关联边
在G中,称v_i为G的顶点,e_k为G的边,并记为e_k=(v_i,v_j )=(v_j,v_i ),称v_i、v_j是e_k的端点,e_k是v_i和v_j关联的边。
图3-5用数学定义描述为G=(V,E),且V={v_1,v_2,v_3,v_4,v_5 },E={e1, e2, e3, e4, e5, e6, e7},e_1=(v_1,v_2 ),e_2=(v_1,v_3 ),e_3=(v_1,v_3 ),e_4=(v_2,v_3 ),e_5=(v_2,v_4 ),e_6=(v_3,v_4 ),e_7=(v_4,v_4 )

图3-5 图的基本要素
3. 环、多重边、简单图
如果图中某一边的两个端点相同,则称为环,如图3-5中的e_7。如果图中两边(或多边)具有相同的一对端点,则称为多重边(或平行边),如图3-5中的e_2和e_3。
无环和无多重边的图,称为简单图。我们后面讨论的都是简单图。
4. 次数、孤立点、奇点、偶点
与顶点v相关联的边数称为v的次数,记为d(v),图3-5中d(v_1 )=3,d(v_2 )=3,d(v_3 )=4,d(v_4 )=4,d(v_5 )=0。次数为零的顶点称为孤立点,如v_5;次数为奇数的顶点称为奇点,如v_1和v_2;次数为偶数的顶点为偶点,如v_3和v_4。
定理1:任一图中顶点次数之和等于边数的2倍,即
(v)=2m
定理2:任一图中奇点的个数必为偶数。
5. 链
在图G中,从一个顶点出发,经过边、点、边、点、…,*后到达某一点,称为G中的一条链,用经过这条链的顶点或边表示。如图3-5中(v_1,v_2,v_3,v_4 )是一条链,也可以表示为(e_1,e_4,e_6 )。
6. 圈
链(v_1,v_2,?,v_n )中,若v_1=v_n,则称此链为一个圈。
7. 连通图、不连通图
在一个图中,若任意两个顶点之间至少存在一条链,则称该图为连通图,否则就是不连通图。如图3-6所示,就是一个连通图。



图3-6 连通图
8. 无向图、有向图、弧
无向图中,图是没有方向的,即e_k=(v_i,v_j )=(v_j,v_i )。上述讨论的图都是无向图。但还有许多实际问题是无向图所不能描述的,如交通图中的单行道、一项工作的各工序之间的先后顺序,这些都需要用有向图来描述。
设V={v_1,v_2,?,v_n }是n个元素的非空集合,A={a_1,a_2,?,a_m }是m个元素的集合,若对于任一a_k∈A,均有有序对(v_i,v_j )与之对应,则称V∪A为有向图,记为D=(V,A)。我们称v_i为顶点,a_k为弧,记为a_k=(v_i,v_j )。

图3-7 有向图
如图?3-7?的有向图中,V={v_1,v_2,v_3,v_4,v_5 },A={a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8 },a_1=(v_1,v_2 ),a_2=(v_1,v_3 ),a_3=(v_1,v_4 ),a_4=(v_2,v_4 ),a_5=(v_3,v_4 ),a_6=(v_5,v_3 ),a_7=(v_3,v_5 ),a_8=(v_4,v_5 )。
9. 赋权图
如果对于给定的图G=(V,E)的任意一边e∈E,有一实数w(e)与之对应,则称G为赋权图,称w(e)为边e的权。
图?3-8?表示的是一个赋权图,权数标于对应边的边上,其中w(v_1,v_2 )=5,w(v_1,v_3 )=7,w(v_2,v_4 )=4,w(v_3,v_4 )=3,w(v_4,v_5 )=1,w(v_4,v_6 )=9,w(v_3,v_6 )=6,w(v_5,v_7 )=2,w(v_6,v_7 )=8。

图3-8 赋权图


3.3 *短路问题
给定一个赋权有向图G=(V,E),对于每一个弧e_ij=(v_i,v_j ),相应有一个权数w_ij。v_s、v_t是G中给定的起点与终点,设P_k是G中从v_s到v_t的一条路,定义路P_k的权是P_k中所有弧的权之和,记作w(P_k )。*短路问题就是要从v_s到v_t的路P_k中,寻找一个权*小的路P_0,使w(P_0 )=min?(w(P_k))。
弧的权数根据具体问题的要求可以是路程的长度、成本的花费等。有些问题如仓库和商场选址、输油管线的铺设、设备更新、连续投资等都可转化为*短路问题予以研究。因此,在实际中有广泛的应用。
*短路的问题有多种求解方法,下面介绍的Dijkstra算法就是其中的一种简便、快捷的方法。
3.3.1 Dijkstra算法简介
Dijkstra算法是由荷兰计算机科学家E.W.Dijkstra于1959年提出的。Dijkstra算法解决的是每条弧的权数都大于零的情况。
Dijkstra算法也称为双标号法,所谓双标号,也就是对图中的点v_i赋予两个标号(d(v_i ),λ_i );**个标号d(v_i )表示从起点v_s~v_i的*短路的长度;第二个标号λ_i表示在 v_s~v_i的*短路上v_i前面一个邻点的下标,即用来表示路径,从而可以对终点到起点进行反向追踪,找到v_s到v_i的*短路。
Dijkstra算法的计算步骤如下。
步骤1 给起点v_s标号[0,s]。
步骤2 找出已标号的点的集合I,未标号的点的集合J,求出弧集A={(v_i?, v_j)| v_i?I, v_i?J},这个弧集是指所有从已标号的点到未标号的点的集合。
步骤3 若上述弧集A=?,表示从所有已经赋予标号的点出发不存在有另一个点没有标号的弧,此时计算结束。对于已有标号的点,存在从v_s到达这个点的*短路;对于没有标号的顶点,则不存在从v_s到达这个顶点的路。
上述弧集A≠?,转下一步。
步骤4 若弧集A中的每一条弧(v_i,v_j),计算T_ij=d(v_i ) w_ij。在所有的T_ij中,找到其值为*小的弧,假设为(v_B,v_F )。需要注意的是,若上述T_ij值为*小的弧有多条,且这些弧的第二个点v_j相同,则表明存在多条*优路径,因此v_j应得到多个双标号。
步骤5 给弧(v_B,v_F )的端点v_F赋予双标号[T_BF,B],返回步骤2。
经上述循环的计算,求出点v_s到任意点v_j的*短路及其长度。
3.3.2 有向图上的Dijkstra算法
例3-1 校园道路网络图如图3-9所示。其中v_1表示教师办公楼,v_2~v_7表示教学楼。用Dijkstra算法求解下图中从v_1到其他各点的*短路。

图3-9 校园道路网络图
分析:
(1)给起点v_1标号[0,s]。
(2)标号点的集合I={v_1 },未标号点的集合J={v_2,v_3,v_4,v_5,v_6,v_7 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_2 ),(v_1,v_3 ),(v_1,v_4 ) }。
T_12=d(v_1 ) w_12=0 12=12;T_13=d(v_1 ) w_13=0 17=17;T_14=d(v_1 ) w_14=0 10=10。
可知min{T_12,T_13,T_14 }=min{12,17,10}=T_14=10,则弧(v_1,v_4 )的端点v_4标号为[10,1]。
(3)标号点的集合I={v_1,v_4 },未标号点的集合J={v_2,v_3,v_5,v_6,v_7 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_2 ),(v_1,v_3 ) }。
可知min{T_12,T_13 }=min{12,17}=T_12=12,则弧(v_1,v_2 )的端点v_2标号为[12,1]。
(4)标号点的集合I={v_1,v_4,v_2 },未标号点的集合J={v_3,v_5,v_6,v_7 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_3 ),(v_2,v_3 ),(v_2,v_5 ) }。
T_23=d(v_2 ) w_23=12 4=16;T_25=d(v_2 ) w_25=12 8=20。
可知min{T_13,T_23,T_25 }=min{17,16,20}=T_23=16,则弧(v_2,v_3 )的端点v_3标号为[16,2]。
(5)标号点的集合I={v_1,v_4,v_2,v_3 },未标号点的集合J={v_5,v_6,v_7 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_2,v_5 ) }。
可知T_25=20,则弧(v_2,v_5 )的端点v_5标号为[20,2]。
(6)标号点的集合I={v_1,v_4,v_2,v_3,v_5 },未标号点的集合J={v_6,v_7 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_5,v_7 ) }。
可知T_57=d(v_5 ) w_57=20 22=42。则弧(v_5,v_7 )的端点v_7标号为[42,5]。
(7)标号点的集合{v_1,v_4,v_2,v_3,v_5,v_7 },未标号点的集合J={v_6 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}=Φ,计算结束,此时J={v_6 },说明不存在v_1到v_6的路。
因此,可以得到从v_1到其他各点的*短路如表3-1所示。
表3-1 校园道路系统中教学楼到其他各点的*短路
目标点
*短路
*短距离
v_2
v_1→v_2
12
v_3
v_1→v_3
16
??????????????????????????????????????????续表??
目标点
*短路
*短距离
v_4
v_1→v_4
10
v_5
v_1→v_2→v_5
20
v_6
没有路
/
v_7
v_1→v_2→v_5→v_7
42例3-2 图3-10表示石油流向的管网示意图,v_1表示石油开采地,v_8表示石油的汇集地,箭头旁的数字表示管线的长度,现在要从v_1调运石油到v_8,怎样选择管线可以使路径*短?

图3-10 石油流向的管网
分析:
(1)给起点v_1进行标号[0,s]。
(2)标号点的集合I={v_1 },未标号点的集合J={v_2,v_3,v_4,v_5,v_6,v_7,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_2 ),(v_1,v_3 ) }。
T_12=d(v_1 ) w_12=0 18=18;T_13=d(v_1 ) w_13=0 13=13。
可知min{T_12,T_13 }=min{18,13}=T_13=13,则弧(v_1,v_3 )的端点v_3标号为[13,1]。
(3)标号点的集合I={v_1,v_3 },未标号点的集合J={v_2,v_4,v_5,v_6,v_7,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_2 ),(v_3,v_4 ),(v_3,v_7 ) }。
T_34=d(v_3 ) w_34=13 8=21; T_37=d(v_3 ) w_37=13 4=17。
可知min{T_12,T_34,T_37 }=min{18,21,17}=T_37=17,则弧(v_3,v_7 )的端点v_7标号为[17,3]。
(4)标号点的集合I={v_1,v_3,v_7 },未标号点的集合J={v_2,v_4,v_5,v_6,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_1,v_2 ),(v_3,v_4 ),(v_7,v_8 ) }。
T_78=d(v_7 ) w_78=17 18=35。
可知min{T_12,T_34,T_78 }=min{18,21,35}=T_12=18,则弧(v_1,v_2 )的端点v_2标号为[18,1]。
(5)标号点的集合I={v_1,v_3,v_7,v_2 },未标号点的集合J={v_4,v_5,v_6,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_3,v_4 ),(v_7,v_8 ),(v_2,v_4 ),(v_2,v_5 ) }。
T_24=d(v_2 ) w_24=18 6=24;T_25=d(v_2 ) w_25=18 22=40。
可知min{T_34,T_78,T_24,T_25 }=min{21,35,24,40}=T_34=21,则弧(v_3,v_4 )的端点v_4标号为[21,3]。
(6)标号点的集合I={v_1,v_3,v_7,v_2,v_4 },未标号点的集合J={v_5,v_6,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_7,v_8 ),(v_2,v_5 ),(v_4,v_6 ) }。
T_46=d(v_4 ) w_46=21 6=27。
可知min{T_78,T_25,T_46 }=min{35,40,27}=T_46=27,则弧(v_4,v_6 )的端点v_6标号为[27,4]。
(7)标号点的集合I={v_1,v_3,v_7,v_2,v_4,v_6 },未标号点的集合J={v_5,v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_7,v_8 ),(v_2,v_5 ),(v_6,v_5 ),(v_6,v_8 ) }。
T_65=d(v_6 ) w_65=27 7=34;T_68=d(v_6 ) w_68=27 15=42。
可知min{T_78,T_25,T_65,T_68 }=min{35,40,34,42}=T_65=34,则弧(v_6,v_5 )的端点v_5标号为[34,6]。
(8)标号点的集合I={v_1,v_3,v_7,v_2,v_4,v_6,v_5 },未标号点的集合J={v_8 },弧集A={(v_i,v_j)|v_i∈I,v_j∈J}={(v_7,v_8 ),(v_6,v_8 ),(v_5,v_8 ) }。
T_58=d(v_5 ) w_58=34 9=43。
可知min{T_78,T_68,T_58 }=min{35,42,43}=T_78=35,则弧(v_7,v_8 )的端点v_8标号为[35,7]。
至此,全部顶点都已经得到标号,计算结束,得到石油开采地v_1到汇集地v_7的*短路径,可根据v_7的第二个标号由端点到始点进行反向追踪,得到v_1→v_3→v_7→v_8,该*短路径的管道长度为35。
3.3.3 无向图上的Dijkstra算法
无向图上的任一条边[v_i,v_j ]均可用方向相反的两条弧(v_i,v_j )和(v_j,v_i )来代替,把原来的无向图变成有向图后,即可用Dijkstra算法进行求解。当然,也可以直接在原来的无向图上用Dijkstra算法求解。在无向图上求解与在有向图上求解的区别主要在于寻找邻点时可能不同:在无向图中,只要两个顶点之间有连线,就是邻点,因此,在无向图上的求解和在相应的有向图上求解相比,计算过程中的邻点个数可能增多,弧集合中的弧数可能增多。计算结束时,一定是所有的点都得到了标号,且其*优结果不会劣于相应有向图的*优结果。
例3-3 某电信公司准备在甲、乙两地沿路架一条光缆线,如何才能使其光缆线路*短?图3-11给出了甲、乙两地的交通图,权数表示两地间公路的长度(单位:千米)。

图3-11 甲、乙两地的交通图

目录 第1章 决策概述 1 1.1 决策的定义 1 1.2 决策的特点 3 1.3 决策的类型 4 1.3.1 按决策的主体分类 4 1.3.2 按决策的重要程度分类 4 1.3.3 按决策的重复程度分类 4 1.3.4 按决策条件的可靠程度分类 5 1.4 决策的过程 6 1.4.1 西蒙决策过程 6 1.4.2 管理科学的决策程序 6 1.5 决策分析的方法 10 1.5.1 定量分析方法 10 1.5.2 定性分析方法 11 1.5.3 定量和定性分析方法的关系 12 1.6 决策的影响因素 12 本章要点 13 关键术语 14 思考与练习 14 参考文献 14 第2章 线性规划 15 2.1 线性规划问题 15 2.1.1 线性规划问题的建模 16 2.1.2 线性规划问题的图解法 19 2.1.3 解的灵敏度分析 23 2.2 整数规划问题 30 2.2.1 整数规划问题的建模 30 2.2.2 整数规划问题的分支定界法 31 2.3 0-1整数规划 34 2.4 指派问题 36 2.4.1 标准型指派问题 37 2.4.2 非标准型指派问题 40 2.5 运输问题 43 2.5.1 供需平衡的运输问题 44 2.5.2 供需不平衡的运输问题 48 2.6 Excel线性规划实验 50 本章要点 57 关键术语 57 思考与练习 57 参考文献 59 第3章 图与网络 60 3.1 哥尼斯堡七桥问题 60 3.2 图论的基本概念 63 3.3 *短路问题 66 3.3.1 Dijkstra算法简介 66 3.3.2 有向图上的Dijkstra算法 66 3.3.3 无向图上的Dijkstra算法 69 3.4 *小支撑树问题 72 3.4.1 *小支撑树问题的基本概念 72 3.4.2 *小支撑树问题的Kruskal算法 74 3.4.3 *小支撑树问题的Prim算法 74 3.5 *大流问题 75 3.5.1 *大流问题的基本概念 75 3.5.2 *大流的Ford-Fulkerson标号法 78 本章要点 80 关键术语 81 思考与练习 81 参考文献 83 第4章 网络计划技术 84 4.1 关键线路法和计划评审技术简介 85 4.2 双代号网络图的绘制 86 4.2.1 双代号网络图的基本概念 86 4.2.2 双代号网络图的基本要素 87 4.2.3 双代号网络图的绘制要求 89 4.3 双代号网络图的时间参数计算 94 4.3.1 工作持续时间计算 94 4.3.2 按工作计算法计算时间参数 95 4.3.3 按节点计算法计算时间参数 100 4.4 网络计划的调整与优化 104 4.4.1 工期的调整和优化 105 4.4.2 资源的调整和优化 106 4.4.3 费用的调整和优化 109 4.5 Project网络计划技术实验 113 本章要点 121 关键术语 121 思考与练习 122 参考文献 124 第5章 博弈论初步 125 5.1 博弈论概述 126 5.1.1 博弈论含义和发展 126 5.1.2 博弈经典案例 127 5.1.3 博弈的组成要素 130 5.1.4 博弈的标准式表述 132 5.1.5 博弈的类别 133 5.2 几类特殊策略 134 5.2.1 严格占优策略 134 5.2.2 严格劣策略 135 5.2.3 弱占优策略和弱劣策略 137 5.3 纳什均衡 138 5.3.1 纳什均衡的定义 138 5.3.2 纳什均衡的求解 140 5.4 混合策略纳什均衡 141 5.4.1 混合策略纳什均衡的定义 142 5.4.2 混合策略纳什均衡的求解 143 5.4.3 混合策略下的严格劣策略 148 5.5 多重纳什均衡的筛选 149 5.5.1 帕累托占优均衡 150 5.5.2 风险占优均衡 150 5.5.3 聚点均衡 152 5.5.4 廉价磋商 153 5.5.5 相关均衡 154 5.6 纳什均衡的存在性 156 本章要点 156 关键术语 157 思考与练习 157 参考文献 158 第6章 不确定条件下的决策 159 6.1 期望理论 159 6.2 期望效用理论 161 6.2.1 效用思想的来源 161 6.2.2 效用的含义、计量和分析 162 6.2.3 期望效用和风险偏好 164 6.3 前景理论 169 6.3.1 期望效用理论遇到的挑战 169 6.3.2 前景理论的心理效应基础 171 6.3.3 前景理论的决策框架和评价方法 173 6.3.4 累积前景理论 182 6.3.5 前景理论对于决策现象的解释 187 本章要点 190 关键术语 190 思考与练习 191 参考文献 191 第7章 决策偏差 192 7.1 启发法偏差 192 7.1.1 代表性偏差 192 7.1.2 可得性偏差 195 7.1.3 锚定和调整偏差 196 7.2 知觉效应 199 7.2.1 对比效应 199 7.2.2 首因效应 200 7.2.3 近因效应 201 7.2.4 晕轮效应 201 7.3 统计误区 202 7.3.1 辛普森悖论 202 7.3.2 概率合取谬误 203 7.3.3 条件概率谬误 205 7.3.4 非回归预测 205 7.4 心理倾向 206 7.4.1 框架效应 207 7.4.2 心理账户 209 7.4.3 沉没成本效应 210 7.4.4 过度自信 211 7.4.5 羊群行为 212 本章要点 213 关键术语 213 思考与练习 214 参考文献 214