第三部分 图与网络分析
图与网络分析部分内容框架
图与网络的基本概念图 连通图图的矩阵表示树与最小树
最短路问题图论在网络分析的应用 最大流问题
最小费用最大流问题
第四章 图与网络分析
§1,图与网络的基本概念一、图及其分类本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。下面介绍有关图的基本概念。
1.图，图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为G=(V,E)，其中V={v1,v2,…vp}是p个点的集合，E={e1,e2,…eq}是q条边的集合。V中的元素vi称为顶点，E中的元素ek称为边。
如图1所示：
图1
V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6}
其中 e1={v1,v1},e2={v1,v2},e3={v1,v3}
e4={v3,v4},e5={v3,v4},e6={v1,v4}
对于边(vi,vj)，则称vi,vj两点相邻，也称vi,vj为边(vi,vj)的端点。
若两条边有一个公共端点u，则称这两边是相邻的，也称这两边为点u的关联边。
若两端之间多于一条边的，称为多重边。如图1中的e4、e5。
若一条边的两个端点相同，则称此为环（自回路）。如图1中的e1。
2.简单图与多重图，不含环和多重边的图称为简单图，含有多重边的图称为多重图。上图就是一个多重图。
3.无向图与有向图。G=(V,E)中，若所有的边均有ek=(vi,vj)=(vj,vi),k=1,2,…q，则称G为无向图，记为G=(V,E)。若图中边(vi,vj)的端点是有序的，即表示以vi为始点vj为终点。则称该图为有向图，记为D=(V,A)。在有向图中，把边称为弧。因此，A表示G中弧的集合。
4.图的同构。
v1 v4
v2 v3
(a) (b)
上面图(a)与图(b)初看起来似乎是不同的两个图，如果我们正确的确定它们顶点之间的对应关系：
v1 vc,v2 vb,v3 vd,v4 va
那么，它们边与边间的对应关系就有：
(v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va),
(v2,v3) (vb,vd),(v3,v4) (vd,va)。
从以上分析可以得出：图(a)和图(b)实质上是一个图，只不过表现的形式不同。
设图G=(V,E)与G(=(V(,E()，若它们的顶点存在一一对应，且保持同样相邻关系，则称G和G(同构，记为。
5.顶点的次。以点v为端点的边数称为点v的次，记为d(v)。图1中，d(v2)=1,d(v3)=3,d(v1)=5。
次数为1的点称为悬挂点，连结悬挂点的边称为悬挂边。
次数为0的点称为孤立点，如图1中的点v5。
次为奇数的点称为奇点，次为偶数的点称为偶点。
在任何图中，顶点的次数与边数有如下性质：
(1) （其中p为G中顶点数，q为边数）
(2)次为奇数的顶点必为偶数个。
在有向图D=(V,A)中，以vi为始点的边数称为点vi的出次，记为d+(vi),以vi为终点的边数称为点vi的入次，记为d-(vi)。显然d(vi)=d+(vi)+d-(vi)。且。
5.网络。在实际问题中，只用图来描述所研究对象之间的关系往往是不够的。与图联系在一起，通常还有与点或边有关的某些数量指标，通常称之为“权”。权可以表示为：距离、费用、通过能力（数量）等。称含有数量指标的赋权图为网络。与无向图和有向图相对应，网络可分为无向网络和有向网络，分别记为G=(V,E,W)和D=(V,A,W)。
二、连通图
1.链。在无向图G=(V,E)，称一个点和边交替的序列{vi1,ei1,vi2,ei2,…vit-1,vit}为连接vi1和vit的一条链。简记为{vi1,vi2,…vit}。其中eik=(vik,vik+1),k=1,2,…t-1。
点边序列中只有重复的点而无重复边者称为简单链。
点边序列中没有重复的点和重复边者称为初等链。
v1 v2 v1 v2
v5 v4 v5 v4
图3 图4
如图3中：S1={v6,v5,v1,v5,v4,v3}是一条连结v6和v3简单链。
S2={v6,v5,v1,v4,v3}是一条条连结v6和v3的初等链。
首尾相接的链称为圈。
2.路。在有向图D=(V,A)中，称链{vi1,vi2,…vit}为一条从vi1到vit的路。若vi1=vit，则称之为回路。
在图4中 S1={v6,v5,v1,v5,v4,v3}是一条从v6和v3的路。
S2={v1,v2,v4,v5,v1}是一条回路。
3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为连通图。
任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。图5中的(b)就是(a)的三个分图。
(a) (b)
图5 图6
三、图的矩阵表示用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表示方法有多种，这里介绍其中两种常用矩阵。
1.权矩阵。网络G=(V,E,W)，其边(vi,vj)的权重为Wij，构造矩阵A=(aij)nxn，其中
称矩阵A为网络G的权矩阵。其中主对角线上的元素aij均为零。
如图6的权矩阵为
2.邻接矩阵。对于图G=(V,E)构造一个矩阵A=(aij)nxn，
其中
则称矩阵A为图G的邻接矩阵。当G为无向图时,邻接矩阵为对称的。
v2 v4
v3 v5
图7
如图7的邻接矩阵为
给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩阵中得到图的很多重要性质。如
（1）A=(aij)中第i行中的1的数目等于vi点的出次d+(vi)，第j列中1的数目等于vi点的入次d-(vi)。
（2）路径问题。如果图7是路径图，则由邻接矩阵就可算出G中任一点与其它点之间是否有路可通？若有路，走几步可以达到该点？
下面通过邻接矩阵的计算来求解v1(v5和v1(v6有无路可能。
先求A2
其中。
可以理解ai1a1j=1时，当且仅当ai1和a1j同时等于1，所以ai1a1j=1表示从vi到vj有一条路，而A2=aij(2)则表示从vi到vj可两步到达。
a15(2)=1，说明v1到v5有一条路，可两步到达。
a16(2)=0，表明v1到v6两步不能到达。继续计算A3
由于a16(3)=1，表明从v1三步可达v6，若要了解这条路沿途经过哪些顶点到达v6，只要回溯前面计算过程中的a16(3)这个数是怎样产生的，就可知道。因为a16(3)是由A2中的第一行与A中的第六列相应各数乘加而得，即是由a15(2)=1和a56=1相乘而得。同理a15(2)=1是由a13=1与a35=1相乘而得。因此有v1(v3(v5(v6。
§2,树与最小树
一、树及其性质
连通且不含圈的无向图称为树，记为T(V,E)。
设图T=(V,E)，顶点数为P，边数为q，则以下关于树的说法是等价的。
1.T是一棵树；
2.T无圈，且q=p－1；
3.T连通，且q=p－1；
4.T无圈，但每加一新边即得唯一的一个圈；
5.T连通，但每舍去一边就不连通；
6.T中任意两点，有唯一链相连。
二、图的生成树若图G的生成子图是一棵树，则称该树为G的生成树。
(a) (b)
图8
图8中(b)就是(a)的生成树。
图G=(V,E)有生成树的充要条件是G为连通图。
三、最小树问题在给定连通赋权无向图G=(V,E,W)中，求G的生成树T=(V,E()，使E(各边权Wij((0)的总和最小的问题称为最小树问题。其数学模型为：
(vi,vj)(T
其中T*称为最小树。
许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。求最小树有以下两种方法：
（1）用“避圈法”(Kruskal算法)求最小树。其基本思想是：开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q－1条边止。
（2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是：
1°先从图G任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。
2°在余下的子圈中，重复上述步骤，直至没有圈止。
例
§3,最短路问题最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本方程较困难，而图论方法则直观有效。
给定D=(V,A,W)，其中wij(W，表示弧(vi,vj)的权（可以是费用、时间、距离等）。设vs和vt是D中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。其数学模型为：
(vi,vj)(P
一、Wij(0情况下，求最短路的Dijkstra标号法
1.该法的基本思想是基于以下原理：若序列{vs,vi1,…vik,…vt}是从vs到vt的最短路，则序列{vs,vi1,…vik}必为从vs到vik的最短路。
2.Dijkstra标号法的基本思想是采用两种标号：T标号与P标号，T标号为临时性标号(Temporary Label)，P标号为永久性标号(Permanent Label)。从vs开始，逐步向外探寻最短路。给vi点P标号时，表示从vs到vi点的最短路权，vi的标号不再改变。给vi点T标号时，表示从vs到vi点的最短路权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把某一T标号点改为P标号，当终点vt得到P标号时，计算全部结束。如果点vj不能由T标号变为P标号，则说明vs到vj不存在路。
3.步骤：
(1)给vs以P标号，P(vs)=0，其余各点给T标号，且T(vi)=+(。
(2)若vi点为刚得到P标号的点，考虑T标号点vj,(vi,vj)(A。对vj的T标号进行如下的更改：
T(vj)=min{T(vj),P(vi)+wij} (4.1)
(3)比较所有具有T标号点，把最小者改为P标号，即
P(vjo)=min{T(vj)}
vj为T标号
若全部点均为P标号。则停止。否则以vjo代vi，返回(2)
例，用Dijkstra标号法求下图由v1到各顶点的最短路。
v2 v5
v1
v3 v6
（图9）
解：标号过程如图10中(a)－(e)，其中方框表示P标号，里面的数字表示从v1到该点的最短路长。圆圈表示T标号，其中的数字表示从v1到该点最短路长的上界。
v2 +( v2 +(
v1 v1
v3 +( v3 +(
(a) P(v1)=0,T(v2)=1 (b)P(v1)=0,P(v2)=1
T(v3)=4 T(v3)=3,T(v4)=4
v2 +( v2 +(
v1 v1
v3 v6 v3 v6
(c) P(v1)=0,T(v2)=1 (d)P(v1)=0,P(v2)=1
P(v3)=3,T(v4)=4 P(v3)=3,P(v4)=4
T(v6)=5 T(v6)5
v2 v5
v1
v3 v6
(e) P(v1)=0,P(v2)=1
P(v3)=3,P(v4)=4
P(v6)=5
（图10）
此时仍有T标号点v5不能改为P标号，说明不存在从v1到v5的路，所以计算终止。图(e)中各方框的数字表示从v1到各点的最短路长。
D氏标号法只适用于全部权为非负情况。如果网络中含有负权的弧，则算法失效，应改用其它算法。
二、求网络中任意两点意最短路的Floyd算法对求网络中任意两点间的最短路，当然可用改变起始点的办法，采用D氏标号法达到目的，但显然较繁。Floyd算法却可直接求出网络中任意两点间的最短路，且wij的正负不受限制。
Floyd方法的具体步骤如下：
开始(k=0)，作距离矩阵L(o)=(Lij(o))和序号矩阵((o)=((ij(o))
其中，
(ij(o)=j (i,j=1,2,…p)
第一步：k=r(1(r(p)时，L(k)中第k行和第k列元素保持不变，其它元素按下式计算，并填入L(k)=(Lij(k))中：
Lij(k)=min{Lij(k-1),Lik(k-1)+Lkj(k-1)} (4.2)
相应地，((k)的各元素按下式变化：
(4.3)
第二步：若存在Lii<0(1(i(p)，计算终止，即说明D中存在一条含有顶点vi的负回路Q，(即dii=W(Q)<0的回路)，并由(ij(k)(i,j=1,2,…p)，找出此回路。否则，置k=k+1。
第三步：当k=p，计算终止。若Lij(p)=+(，则说明D中不存在从vi到vj的路；否则，记dij=Lij(p)，表示由vi到vj的最短路长，相应的最短路可由(ij(p)(i,j=1,2,…p)找出。
例 用Floyd方法求图11中各顶点间的最短路，其中弧（边）旁的数字表示弧（边）长。
（图11）
解：k=0，把图11中的两条边看作长度相等，方向相反的两条弧。即有(14=(41=9，(25=(52=2。根据图11中的数据，作L(o)=(Lij(o))同时作((0)=((ij(o))，如表中k=0所示。
k=1，将L(1)中第1行和第1列的元素保持不变（在表中用虚线将其覆盖），其它元素按(4.2)式进行计算，例如
L42(1)=min{L42(o),L41(o)+L12(o)}=min{(,9+3}=12
L43(1)=min{L43(o),L41(o)+L13(o)}=min{(,9+4}=13
其余元素经计算不变。对更新数字的元素均加上圆圈。
同时，在k=1的序数矩阵中，按(4.3)式有(42(1)=(41(o)=1，(43(o)=(41(o)=1，并加上圆圈。如表中k=1所示。
k=2，将L(2)的第2行和第2列的元素保持不变，按(4.2)式计算：
L13(2)=min{L13(1),L12(1)+L23(1)}=min{4,3+(-4)}=-1
L15(2)=min{L15(1),L12(1)+L25(1)}=min{(,3+2}=5
L43(2)=min{L43(1),L42(1)+L23(1)}=min{13,12+(-4)}=8
L53(2)=min{L53(1),L52(1)+L23(1)}=min{(,2+(-4)}=-2
其余元素未变，并对L13(2)，L15(2)，L43(2)，L53(2)加圈。
同时在((2)中,按(4.3)式有
(13(2)=(12(1)=2,(15(2)=(12(1),(43(2)=(42(1)=1,(53=(52(1)=2，并加圈。如表中k=2所示。
k=3,4,5的结果均在表中给出，过程从略。
L(5)=(Lij(5))给出了图11中各点之间的最短路长，((5)=((ij(5))给出了从vi到vj的最短路必须经过点的下标，并由此可找出最短路。例如从v1到v5的最短路长为1(L15(5)=1),最短路由(15(5)=2（即必经过v2），又由(25(5)=3（即经过v3），再由(35(5)=4（即必经过v4），最后由(45(5)=5,可知从v1到v5的最短路是(v1,v2,v3,v4,v5)。同样，从v5到v1的最短路长为10，最短路为(v5,v2,v3,v4,v1)。
表
k=0
k=1
k=2
k=3
k=4
k=5
[Lij(k)]
[(ij(k)]
例 用Flogd方法求图12中各顶点之间的最短路，其中各弧旁的数据表示弧长。
（图12）
解：k=0，由6.18中的数据作L(o)=[lij(o)]和((o)=[(ij(o)],按(6.5)式计算及按(6.6)式得表6-2(k=0,1,2)如下：
表6—2
k=0
k=1
k=2
[Lij(k)]
[(ij(k)]
由于L44(2)=-3<0，说明图12中含有顶点v4的负回路Q，由[(ij(2)]中的(44(2)=1,(14(2)=2,(24(2)=4可知，负回路Q={v4,v1,v2,v4}，d44=L44(2)=-3，计算终止。否则，继续计算下去，则会出现更多的负回路，且随着计算次数增多，含有负回路P的长dij(-(。因此，本题不存在从vi到vj的最短路(i,j=1,2,3,4)。
§4,最大流问题最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流、车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络中信息流……等。五十年代，Ford(福特)、Fulkerson(富克逊)建立的“网络流理论”，是网络应用的重要组成部分。
一、网络与流的概念对于有向图D=(V,A)，如果V中有一发点vs（亦称源还有一收点（亦称为汇）记为vt其余均为中间点，且对A中的每条弧均有权W(vi,vj)(0（简记为Wij，并称为弧容量），则称这样的赋权有向图D为容量网络，记为D=(V,A,W)。通过D中弧(vi,vj)的物流量fij，称为弧(vi,vj)的流量。所有弧上流量的集合f={fij}称为该网络D的一个流。
在图13中，弧旁括号中的两个数字(Wij,fij)，第1个数字表示弧容量，第二个数字表示通过该弧的流量。弧(vs,v1)上的(8,6)，前者是弧容量，表示可通过该弧最大流量的能力为8，后者是目前通过该弧的实际流量为6。
v1 v4
v2 v3
（图13）
从图13中可见：（1）通过每弧的流量均不超过弧容量（2）发点vs流出的总量为6+3=9,等于流入收点vt的总量5+4=0；（3）各中间点的流出量等于其流入量。各中间点v2的流出量减去其流入量等于0,即4－(3+1)=0
一般地，在容量网络D=(V,A,W)中，满足以下条件的流f，称为可行流：
（1）弧流量限制条件 0(fij(cij (vi,vj)(A
（2）平衡条件
式中v(f)为该可行流的流量，即发点的净输出量，或收点的净输入量。对于网络的流，可行流总是在存在的。如f={0}。
二、最大流问题最大流问题就是在容量网络D中，求一个可行流f={fij}，使其流量v(f)达到最大。其数学模型为
maxv(f)
满足
显然，最大流问题是个特殊的LP问题可用单纯形法或表上作业法求解，但利用它与图的紧密关系，能更为直观简便地求解。
三、求网络最大流的有关概念与原理
1.增广链。设D=(V,A,C)中，有一可行流f={fij}，按每条弧上流量的多少，可将弧分四种类型：
饱和弧(即fij=wij) 非饱和弧(即fij<wij)
零流弧(即fij=0) 非零流弧(即fij>0)
如图13中，(v1,v4)是饱和弧，又是非零流弧，其它各弧均为非饱和弧，也是非零流弧。
设(是中D中从vs别vt的一条链，沿此方向，从上各弧可分为两类：
正向弧（与链的方向一致的弧），其集合记为(+
反向弧（与链的方向相反的弧），其集合记为(-
如图13，在(={v1,v2,v3,v4,vt}中，(+={(vs,v2),(v1,v4),(v3,vt)},
(-={(v2,v1),(v4,v3)}
对于可行流f,(是一条从vs到vt的链，若(+中的每弧均为非饱和弧，(-中的每弧均为非零流弧，是称链(是关于f的增广链。
2.截集（割集）
若将D=(V,A,W)的V为两部分Vs和,使vs(Vs,vt(,且，则把从vs指向的弧的全体称为截集。记为()即。
截集的截量──截集中所有容量之和称为该截集的截量。记为W()举例说明，不同截集的截量不同。
可以理解，任何可行流的流量v(f)(W(Vs.)
3,最大流最小截量定理：
任一网络D中，最大流的流量=最小截集的截量。
四、求最大流的方法(Ford-Fulkerson标号法)
从以上概念及定理可知，要判断可行流f是否最大流有两种途径：
1）能否找出可行流f的增广链，若能，则f不是最大流，否则f是最大流。
2）V(f)是否等于最小截量，若等，则f是最大流，否则f不是最大流。
1,标号法的基本思想：从可行流f出发，由Vs开始，用对D中的每个顶点进行标号的办法找f的增广链(。若无，则f为所求的最大流。否则，在增广链上进行调整。
调整理：
调整方法：
2.步骤
（1）给出初始可行流f(如f=0)
（2）给顶点标号，寻找增广链。标号(vi,L(vi))的第一个标号表示vi点而来，第二个标号L(vi)表示增广链上中该弧允许的调整量。
在标号过程中，每个属于且仅属于下列集合之一：
Vo──已标号未检验点集，Vs──已标号已检验的点集，──未标号点集。
首先给vs标号(0,+()，此时，Vo={Vs}((,={V1…Vt}。
（3）若Vo非空，则反复按以下①②进行，否则按第(5)步：
①在Vo中任选vi，检查vi到的弧(vi,vj)，或中的点vj到vi的弧(vj,vi)，满足以下条件者给vj标号。
i)对正向弧(vi,vj)，若非饱和，则给点vj标以(vi,l(vj))，其中l(Vj)=min{l(vj),(wij－fij)}
同时把Vj从中除去，归入Vo，若Vt∈Vo说明已找出f的增广链(按(4)。
ii)对反向弧(vj,vi)，若非零流，则给点Vj标以(-vi,l(Vj))，其中l(Vj)=min{l(vj),fij}
同时把Vj从中除去，归入Vo
②把已检验的点vi，归入Vs
（4）在增广链(上调整，得新可行流f(。返回(2)。
（5）写出最大流f*={fij}的流量v(f*)，和最小截集W(Vs*,)，终止。
例 用Ford—Fulkerson标号法求下图的最大流
调整后为：
（图14）
由于标号进行不下去(即Vo=()，因此，目前可行流就是最大流。
最小截集：(Vs*,)={(vs,v1),(v2,v3)}──瓶颈（扩大流量的关链）最大流量V(f*)=6+7=13。
§5,最小费用最大流问题（详见书）
第四部分 对策论模型
§1,两人有限零和对策模型及其解法
一、对策现象的三要素由引例《齐王赛马》导出对策现象的三要素：
1.局中人：对策中有权决定自己行动方案的参加者，称为局中人。通常用I表示局中人集合。如果有n个局中人，则I={1,2,…n}。一般要求一个对策中至少有两个局中人。
局中人总是被假定是聪明且有理智的。
2.策略集：对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）策略；参加对策的每一局中人i(I的策略集记为Si。一般每一局中人的策略集中至少应包括两个（纯）策略。
如《齐王赛马》中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。齐王与田忌的策略集中，各自都有六个纯策略：S1,S2={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上)}
3.赢得函数（支付函数）
（1）局势：对策中，每一局中人所选定策略形成的策略组合称一个局势。设局中人1从自己的策略集S1={(1,(2 …,(m}中选定策略(i，局中人2从自己的策略集S2={(1,(2 …,(n}选定策略(j，则((i,(j)就构成两人对策中的一个局势。
在n个对策中，设si表示第i局中人的一个策略，则n个局中人的策略组合形成的局势为S=(s1,s2,…sn)。
（2）赢得函数：当一个局势S出现后，各局中人都有自己的结果（得失），记为Hi(S)，它表示第i局中人的赢得（支付）值。显然Hi(S)是局势的函数。
例如在“齐王赛马”中，局中人集合I={1,2}，齐王和田忌的策略集分别用S1={(1,…(6}和S2={(1,…(6}表示。在(1=(上、中、下)，(1=(上、中、下)构成的局势S1={(1,(1}下，齐王的赢得为H1(S)=3，田忌的赢得为H2(S)=-3。
二、对策的分类 完全信息静态对策，不完全信息静态对策完全信息动态对策，不完全信息动态对策
三、两人有限零和对策的数学模型两人有限零和对策，又称为矩阵对策。其数学模型为：
={Ⅰ,Ⅱ;S1,S2,A}或={S1,S2;A}
其中策略集S1={(1,(2,…,(m}，S2={(1,(2,…,(n}分别为局中人Ⅰ和Ⅱ的策略集，A=(aij)mxn为局中人Ⅰ的赢得矩阵，由于假定对策的结果为零和，所以局中人Ⅱ的羸得矩阵为-A。
四、在纯策略下有解的矩阵对策的解法
1.解法的思想：双方都立足在不利的情况下争取最好的结果──最大最小原则。
例 求解矩阵对策={S1,S2;A}，其中，
解
16 2 5
，，
即=
2.在矩阵对策中，若=ai*j*成立，则称ai*j*为对策的值，记为V=ai*j*。称使上式成立的纯局势((i*,(j*)为对策在纯策略下的解（亦称均衡局势）。(i*和(j*分别称为局中人Ⅰ和Ⅱ的最优纯策略。
3.方法步骤：
上例可求解过程可简单的表述如下：
其步骤是：
第一步：分别确定A各行中的最小值，并在该数字上加圈表示；
第二步：分别确定A各列中的最大值，并在该数字上加框表示；
第三步：若A中的某元素同时被圈和框住，则该元素即为对策的值，该元素所在的行和列对应的策略则分别为局中人Ⅰ和Ⅱ的最优纯策略，并由最优纯策略组成了对策的解。
因此上例对策的值V=2，对策的解为((2,(2)，(2,(2分别是局中人Ⅰ和Ⅱ的最优纯策略。
在纯策略下有解的矩阵对策中，值ai*j*既是所在行的最小值，又是所在列的最大值，称其为鞍点。所以这类矩阵对策又称为鞍点的对策。这个事实可推广到一般，即在纯策略下矩阵对策={S1,S2;A}有解的充要条件是：存在纯局势((i*,(j*)，使得对于一切的i=1,2…m,j=1,2…n均有
aij*(ai*j*(ai*j
矩阵对策的解可以不唯一。
五、具有混合策略的矩阵对策在具有鞍点的对策中，局中人Ⅰ的赢得，局中人Ⅱ的损失，且。但一般情况下却总有。
例如
该矩阵对策在纯策略下无解。此时，用最大最小原则来选取各自的纯策略都不会是稳定的，因为各局中人可以选取其它的纯策略来改善自己的赢得值。
在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自己的期望赢得（损失）。按概率分布，上例局中人的期望赢得为
=8xy－6y－x+8
=
这就是说，局中人分别以概率选用(1,(2时，至少赢得，同理，局中人Ⅱ分别以概率选用策略(1,(2，至多损失。但当或时，则会受到更大的损失。
1.混合策略和混合局势的概念
2.混合扩充和混合策略下的解的概念（详见书）
在纯策略下矩阵对策的解是混合策略下矩阵对策解的特殊情况。
3.基本定理（不加证明）
（1）在混合扩充下，任何矩阵对策必有解；
（2）在混合策略下，(X*,Y*)是对策解的充要条件是：
E(X,Y*)(E(X*,Y*)(E(X*,Y)
其等价形式是
E(i,Y*)(E(X*,Y*)(E(X*,j)
其中E(i,Y*)表示当局中人Ⅰ取纯策略(i，局中人Ⅱ取最优混合策略时，局中人Ⅰ的期望赢得 即E(i,Y*)=。
E(X*,j)表示当局中人Ⅱ取纯策略(j，局中人Ⅰ取最优混合策略时，局中人Ⅰ的期望赢得 即E(X*,j)=。
作为应用，给出（2）的另一等价形式：
（3）(X*,Y*)为对策的解的充要条件是存在数v，使X*,Y*分别是下面两个不等式组的解：
(1°) (2°)
六、矩阵对策的一般解法
1.LP法（详见书）
应当指出，在未求解(P)和(D)之前，V的正负是未知的。当V=v(0时，可以v>0或v<0。
（1）若A=(aij)mxn中所有元素均为正值，则必有v>0，此时建立的LP模型(P)和(D)所用单纯形法求解，且X*(0,Y*(0。
（2）若A=(aij)mxn中含有负元素时，则有可能出现v(0，由此而可能出现无解，这与基本定理相矛盾。此时，可根据下述定理进行处理：
定理：设对策={SⅠSⅡA}和对策(={SⅠSⅡA(}，其中A=(aij)mxn，
A(=(aij+k)mxn,k为任一常数，则与(的解相同，且V=V(－k。
其方法是先对含有负元素的A加上正数k,k=-min{aij}，构成一个新的赢得矩阵A(，再用LP法进行求解，所得的解就是原对策的解,但V=V(－k。
2.2×n对策的解法赢得矩阵形为的对策称为2×n对策。
(1) 2×2对策的公式法由于在纯策略下无解的2×2对策，其最优混合策略(x1*,x2*)>0，(y1*,y2*)>0，所以由LP对偶理论中的互补松驰性知，基本定理(3)的两组不等式均可取等式。且
(1°) (2°)
有唯一解：
(2)2×n对策的代数解法：
对2×n对策，可先将2×n对策转化为Cn2个2×2子对策，再利用2×2对策的公式法，分别求出各子对策的值，最后从中解出2×n对策的解，其步骤如下：
第一步：由2×n阶矩阵A分别写出Cn2个2×2阶子矩阵Ai；
第二步：分别求出各Ai相应子对策的值Vi；
第三步：取V=min{Vi}=Vk,1(k(N，其中N=Cn2,Ak是由A中的两列所构成；
第四步：求出Ak相应子对策k的解X(o)、Y(o)，取X*=Xo，同时在Y(o)中添加n－2个0分量在对应列的位置上，构成Y*，则(X*Y*)就是原2×n对策的解。
例 已知赢得矩阵为试用代数法求解此对策。
(3)2×n对策的图解法（详见书）
3.迭代法（详见书）
七、求解矩阵对策中的计算技巧
1.用优超原则简化赢得矩阵例
优超原则：在A=(aij)mxn中
(1)若第k行与第l行的各元素均有
akj(alj (j=1,2…n)
则称局中人Ⅰ的纯策略(k优超于纯策略(l，此时在最优混合策略中必有Xi*=0。（即可在A中删去第l行）。
(2)若第p列与第q列的各元素均有
aip(aiq (i=1,2…m)
则称局中人Ⅱ的纯策略(p优超于纯策略(q，此时在最优混合策略中必有yq*=0（即可在A中删去第q列）。
值得指出的是，对于A中的纯策略(i1(或(j1)不为纯策略(i2…(im(或(j2…(jm)所优超。但被它们的凸组合所优超，即
(或)
此时，同样可在A删去第i1行(或第j1列)，对策的解不变。
2.若两个矩阵对策1={SⅠ,SⅡ,A1}，2={SⅠ,SⅡ,A2}且满足A1=A2+k(k为任一常数)，则V1=V2+k，且它们有相同的解。
3.若两个矩阵对策1和2满足A1=kA2(k为任一常数)，则V1=kV2，且它们有相同的解。
4.设A为n个阶对角矩阵（即主对角线上的元素为a11,a22…ann，其余元素均为0）。若a11,a22…ann符号相同，则
且VG=(。其中
例 两小孩猜扑克牌花色，游戏规定：由甲小孩每次从4种花色的牌中拿出一张牌给乙小孩猜，猜对花色，甲付给乙小石子三个；猜不对，乙付给甲一个石子，试求游戏的解。
解 据题意，该游戏可归结为矩阵模型G={S甲,S乙,A}，其中甲小孩的赢得
显然该对策无鞍点，为简化计算，对A中各元素减1，得
于是有,且(=-1，
X*=Y*=(1/4,1/4,1/4,1/4)。
即甲、乙两小孩应以1/4的概率出（或猜）各种花色的牌，互不吃亏。
5.设A为n阶矩阵。若,则X*=Y*=(1/n,1/n,1/n,1/n)，且VG=b/n。
“齐王赛马”的羸得矩阵满足上述条件，故由此可得
X*=Y*=(1/6,1/6,1/6,1/6)，且VG=6/6=1。
对于矩阵对策，该选用哪种方法进行求解？一般可按以下顺序进行考虑：
1°首先，用最大最小原则试求鞍点。若无，则考虑以下方法；
2°若A为特殊矩阵，则可选用上述4,5给出的结论，直接求解；
3°对3×3阶以上的赢得矩阵A，试用优超法将A降价；
4°对2×n对策，可转化为Cn2个2×2对策，分别用公式法求解，并从中求出原对策的解；
5°以上方法均不可行时，则可用LP法或迭代法求解。
§2,两人有限非零和对策（详见书）
图与网络分析部分内容框架
图与网络的基本概念图 连通图图的矩阵表示树与最小树
最短路问题图论在网络分析的应用 最大流问题
最小费用最大流问题
第四章 图与网络分析
§1,图与网络的基本概念一、图及其分类本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。下面介绍有关图的基本概念。
1.图，图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为G=(V,E)，其中V={v1,v2,…vp}是p个点的集合，E={e1,e2,…eq}是q条边的集合。V中的元素vi称为顶点，E中的元素ek称为边。
如图1所示：
图1
V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6}
其中 e1={v1,v1},e2={v1,v2},e3={v1,v3}
e4={v3,v4},e5={v3,v4},e6={v1,v4}
对于边(vi,vj)，则称vi,vj两点相邻，也称vi,vj为边(vi,vj)的端点。
若两条边有一个公共端点u，则称这两边是相邻的，也称这两边为点u的关联边。
若两端之间多于一条边的，称为多重边。如图1中的e4、e5。
若一条边的两个端点相同，则称此为环（自回路）。如图1中的e1。
2.简单图与多重图，不含环和多重边的图称为简单图，含有多重边的图称为多重图。上图就是一个多重图。
3.无向图与有向图。G=(V,E)中，若所有的边均有ek=(vi,vj)=(vj,vi),k=1,2,…q，则称G为无向图，记为G=(V,E)。若图中边(vi,vj)的端点是有序的，即表示以vi为始点vj为终点。则称该图为有向图，记为D=(V,A)。在有向图中，把边称为弧。因此，A表示G中弧的集合。
4.图的同构。
v1 v4
v2 v3
(a) (b)
上面图(a)与图(b)初看起来似乎是不同的两个图，如果我们正确的确定它们顶点之间的对应关系：
v1 vc,v2 vb,v3 vd,v4 va
那么，它们边与边间的对应关系就有：
(v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va),
(v2,v3) (vb,vd),(v3,v4) (vd,va)。
从以上分析可以得出：图(a)和图(b)实质上是一个图，只不过表现的形式不同。
设图G=(V,E)与G(=(V(,E()，若它们的顶点存在一一对应，且保持同样相邻关系，则称G和G(同构，记为。
5.顶点的次。以点v为端点的边数称为点v的次，记为d(v)。图1中，d(v2)=1,d(v3)=3,d(v1)=5。
次数为1的点称为悬挂点，连结悬挂点的边称为悬挂边。
次数为0的点称为孤立点，如图1中的点v5。
次为奇数的点称为奇点，次为偶数的点称为偶点。
在任何图中，顶点的次数与边数有如下性质：
(1) （其中p为G中顶点数，q为边数）
(2)次为奇数的顶点必为偶数个。
在有向图D=(V,A)中，以vi为始点的边数称为点vi的出次，记为d+(vi),以vi为终点的边数称为点vi的入次，记为d-(vi)。显然d(vi)=d+(vi)+d-(vi)。且。
5.网络。在实际问题中，只用图来描述所研究对象之间的关系往往是不够的。与图联系在一起，通常还有与点或边有关的某些数量指标，通常称之为“权”。权可以表示为：距离、费用、通过能力（数量）等。称含有数量指标的赋权图为网络。与无向图和有向图相对应，网络可分为无向网络和有向网络，分别记为G=(V,E,W)和D=(V,A,W)。
二、连通图
1.链。在无向图G=(V,E)，称一个点和边交替的序列{vi1,ei1,vi2,ei2,…vit-1,vit}为连接vi1和vit的一条链。简记为{vi1,vi2,…vit}。其中eik=(vik,vik+1),k=1,2,…t-1。
点边序列中只有重复的点而无重复边者称为简单链。
点边序列中没有重复的点和重复边者称为初等链。
v1 v2 v1 v2
v5 v4 v5 v4
图3 图4
如图3中：S1={v6,v5,v1,v5,v4,v3}是一条连结v6和v3简单链。
S2={v6,v5,v1,v4,v3}是一条条连结v6和v3的初等链。
首尾相接的链称为圈。
2.路。在有向图D=(V,A)中，称链{vi1,vi2,…vit}为一条从vi1到vit的路。若vi1=vit，则称之为回路。
在图4中 S1={v6,v5,v1,v5,v4,v3}是一条从v6和v3的路。
S2={v1,v2,v4,v5,v1}是一条回路。
3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为连通图。
任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。图5中的(b)就是(a)的三个分图。
(a) (b)
图5 图6
三、图的矩阵表示用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表示方法有多种，这里介绍其中两种常用矩阵。
1.权矩阵。网络G=(V,E,W)，其边(vi,vj)的权重为Wij，构造矩阵A=(aij)nxn，其中
称矩阵A为网络G的权矩阵。其中主对角线上的元素aij均为零。
如图6的权矩阵为
2.邻接矩阵。对于图G=(V,E)构造一个矩阵A=(aij)nxn，
其中
则称矩阵A为图G的邻接矩阵。当G为无向图时,邻接矩阵为对称的。
v2 v4
v3 v5
图7
如图7的邻接矩阵为
给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩阵中得到图的很多重要性质。如
（1）A=(aij)中第i行中的1的数目等于vi点的出次d+(vi)，第j列中1的数目等于vi点的入次d-(vi)。
（2）路径问题。如果图7是路径图，则由邻接矩阵就可算出G中任一点与其它点之间是否有路可通？若有路，走几步可以达到该点？
下面通过邻接矩阵的计算来求解v1(v5和v1(v6有无路可能。
先求A2
其中。
可以理解ai1a1j=1时，当且仅当ai1和a1j同时等于1，所以ai1a1j=1表示从vi到vj有一条路，而A2=aij(2)则表示从vi到vj可两步到达。
a15(2)=1，说明v1到v5有一条路，可两步到达。
a16(2)=0，表明v1到v6两步不能到达。继续计算A3
由于a16(3)=1，表明从v1三步可达v6，若要了解这条路沿途经过哪些顶点到达v6，只要回溯前面计算过程中的a16(3)这个数是怎样产生的，就可知道。因为a16(3)是由A2中的第一行与A中的第六列相应各数乘加而得，即是由a15(2)=1和a56=1相乘而得。同理a15(2)=1是由a13=1与a35=1相乘而得。因此有v1(v3(v5(v6。
§2,树与最小树
一、树及其性质
连通且不含圈的无向图称为树，记为T(V,E)。
设图T=(V,E)，顶点数为P，边数为q，则以下关于树的说法是等价的。
1.T是一棵树；
2.T无圈，且q=p－1；
3.T连通，且q=p－1；
4.T无圈，但每加一新边即得唯一的一个圈；
5.T连通，但每舍去一边就不连通；
6.T中任意两点，有唯一链相连。
二、图的生成树若图G的生成子图是一棵树，则称该树为G的生成树。
(a) (b)
图8
图8中(b)就是(a)的生成树。
图G=(V,E)有生成树的充要条件是G为连通图。
三、最小树问题在给定连通赋权无向图G=(V,E,W)中，求G的生成树T=(V,E()，使E(各边权Wij((0)的总和最小的问题称为最小树问题。其数学模型为：
(vi,vj)(T
其中T*称为最小树。
许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。求最小树有以下两种方法：
（1）用“避圈法”(Kruskal算法)求最小树。其基本思想是：开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q－1条边止。
（2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是：
1°先从图G任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。
2°在余下的子圈中，重复上述步骤，直至没有圈止。
例
§3,最短路问题最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本方程较困难，而图论方法则直观有效。
给定D=(V,A,W)，其中wij(W，表示弧(vi,vj)的权（可以是费用、时间、距离等）。设vs和vt是D中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。其数学模型为：
(vi,vj)(P
一、Wij(0情况下，求最短路的Dijkstra标号法
1.该法的基本思想是基于以下原理：若序列{vs,vi1,…vik,…vt}是从vs到vt的最短路，则序列{vs,vi1,…vik}必为从vs到vik的最短路。
2.Dijkstra标号法的基本思想是采用两种标号：T标号与P标号，T标号为临时性标号(Temporary Label)，P标号为永久性标号(Permanent Label)。从vs开始，逐步向外探寻最短路。给vi点P标号时，表示从vs到vi点的最短路权，vi的标号不再改变。给vi点T标号时，表示从vs到vi点的最短路权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把某一T标号点改为P标号，当终点vt得到P标号时，计算全部结束。如果点vj不能由T标号变为P标号，则说明vs到vj不存在路。
3.步骤：
(1)给vs以P标号，P(vs)=0，其余各点给T标号，且T(vi)=+(。
(2)若vi点为刚得到P标号的点，考虑T标号点vj,(vi,vj)(A。对vj的T标号进行如下的更改：
T(vj)=min{T(vj),P(vi)+wij} (4.1)
(3)比较所有具有T标号点，把最小者改为P标号，即
P(vjo)=min{T(vj)}
vj为T标号
若全部点均为P标号。则停止。否则以vjo代vi，返回(2)
例，用Dijkstra标号法求下图由v1到各顶点的最短路。
v2 v5
v1
v3 v6
（图9）
解：标号过程如图10中(a)－(e)，其中方框表示P标号，里面的数字表示从v1到该点的最短路长。圆圈表示T标号，其中的数字表示从v1到该点最短路长的上界。
v2 +( v2 +(
v1 v1
v3 +( v3 +(
(a) P(v1)=0,T(v2)=1 (b)P(v1)=0,P(v2)=1
T(v3)=4 T(v3)=3,T(v4)=4
v2 +( v2 +(
v1 v1
v3 v6 v3 v6
(c) P(v1)=0,T(v2)=1 (d)P(v1)=0,P(v2)=1
P(v3)=3,T(v4)=4 P(v3)=3,P(v4)=4
T(v6)=5 T(v6)5
v2 v5
v1
v3 v6
(e) P(v1)=0,P(v2)=1
P(v3)=3,P(v4)=4
P(v6)=5
（图10）
此时仍有T标号点v5不能改为P标号，说明不存在从v1到v5的路，所以计算终止。图(e)中各方框的数字表示从v1到各点的最短路长。
D氏标号法只适用于全部权为非负情况。如果网络中含有负权的弧，则算法失效，应改用其它算法。
二、求网络中任意两点意最短路的Floyd算法对求网络中任意两点间的最短路，当然可用改变起始点的办法，采用D氏标号法达到目的，但显然较繁。Floyd算法却可直接求出网络中任意两点间的最短路，且wij的正负不受限制。
Floyd方法的具体步骤如下：
开始(k=0)，作距离矩阵L(o)=(Lij(o))和序号矩阵((o)=((ij(o))
其中，
(ij(o)=j (i,j=1,2,…p)
第一步：k=r(1(r(p)时，L(k)中第k行和第k列元素保持不变，其它元素按下式计算，并填入L(k)=(Lij(k))中：
Lij(k)=min{Lij(k-1),Lik(k-1)+Lkj(k-1)} (4.2)
相应地，((k)的各元素按下式变化：
(4.3)
第二步：若存在Lii<0(1(i(p)，计算终止，即说明D中存在一条含有顶点vi的负回路Q，(即dii=W(Q)<0的回路)，并由(ij(k)(i,j=1,2,…p)，找出此回路。否则，置k=k+1。
第三步：当k=p，计算终止。若Lij(p)=+(，则说明D中不存在从vi到vj的路；否则，记dij=Lij(p)，表示由vi到vj的最短路长，相应的最短路可由(ij(p)(i,j=1,2,…p)找出。
例 用Floyd方法求图11中各顶点间的最短路，其中弧（边）旁的数字表示弧（边）长。
（图11）
解：k=0，把图11中的两条边看作长度相等，方向相反的两条弧。即有(14=(41=9，(25=(52=2。根据图11中的数据，作L(o)=(Lij(o))同时作((0)=((ij(o))，如表中k=0所示。
k=1，将L(1)中第1行和第1列的元素保持不变（在表中用虚线将其覆盖），其它元素按(4.2)式进行计算，例如
L42(1)=min{L42(o),L41(o)+L12(o)}=min{(,9+3}=12
L43(1)=min{L43(o),L41(o)+L13(o)}=min{(,9+4}=13
其余元素经计算不变。对更新数字的元素均加上圆圈。
同时，在k=1的序数矩阵中，按(4.3)式有(42(1)=(41(o)=1，(43(o)=(41(o)=1，并加上圆圈。如表中k=1所示。
k=2，将L(2)的第2行和第2列的元素保持不变，按(4.2)式计算：
L13(2)=min{L13(1),L12(1)+L23(1)}=min{4,3+(-4)}=-1
L15(2)=min{L15(1),L12(1)+L25(1)}=min{(,3+2}=5
L43(2)=min{L43(1),L42(1)+L23(1)}=min{13,12+(-4)}=8
L53(2)=min{L53(1),L52(1)+L23(1)}=min{(,2+(-4)}=-2
其余元素未变，并对L13(2)，L15(2)，L43(2)，L53(2)加圈。
同时在((2)中,按(4.3)式有
(13(2)=(12(1)=2,(15(2)=(12(1),(43(2)=(42(1)=1,(53=(52(1)=2，并加圈。如表中k=2所示。
k=3,4,5的结果均在表中给出，过程从略。
L(5)=(Lij(5))给出了图11中各点之间的最短路长，((5)=((ij(5))给出了从vi到vj的最短路必须经过点的下标，并由此可找出最短路。例如从v1到v5的最短路长为1(L15(5)=1),最短路由(15(5)=2（即必经过v2），又由(25(5)=3（即经过v3），再由(35(5)=4（即必经过v4），最后由(45(5)=5,可知从v1到v5的最短路是(v1,v2,v3,v4,v5)。同样，从v5到v1的最短路长为10，最短路为(v5,v2,v3,v4,v1)。
表
k=0
k=1
k=2
k=3
k=4
k=5
[Lij(k)]
[(ij(k)]
例 用Flogd方法求图12中各顶点之间的最短路，其中各弧旁的数据表示弧长。
（图12）
解：k=0，由6.18中的数据作L(o)=[lij(o)]和((o)=[(ij(o)],按(6.5)式计算及按(6.6)式得表6-2(k=0,1,2)如下：
表6—2
k=0
k=1
k=2
[Lij(k)]
[(ij(k)]
由于L44(2)=-3<0，说明图12中含有顶点v4的负回路Q，由[(ij(2)]中的(44(2)=1,(14(2)=2,(24(2)=4可知，负回路Q={v4,v1,v2,v4}，d44=L44(2)=-3，计算终止。否则，继续计算下去，则会出现更多的负回路，且随着计算次数增多，含有负回路P的长dij(-(。因此，本题不存在从vi到vj的最短路(i,j=1,2,3,4)。
§4,最大流问题最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流、车流、货物流、供水网络中有水流、金融系统中有现金流、通讯网络中信息流……等。五十年代，Ford(福特)、Fulkerson(富克逊)建立的“网络流理论”，是网络应用的重要组成部分。
一、网络与流的概念对于有向图D=(V,A)，如果V中有一发点vs（亦称源还有一收点（亦称为汇）记为vt其余均为中间点，且对A中的每条弧均有权W(vi,vj)(0（简记为Wij，并称为弧容量），则称这样的赋权有向图D为容量网络，记为D=(V,A,W)。通过D中弧(vi,vj)的物流量fij，称为弧(vi,vj)的流量。所有弧上流量的集合f={fij}称为该网络D的一个流。
在图13中，弧旁括号中的两个数字(Wij,fij)，第1个数字表示弧容量，第二个数字表示通过该弧的流量。弧(vs,v1)上的(8,6)，前者是弧容量，表示可通过该弧最大流量的能力为8，后者是目前通过该弧的实际流量为6。
v1 v4
v2 v3
（图13）
从图13中可见：（1）通过每弧的流量均不超过弧容量（2）发点vs流出的总量为6+3=9,等于流入收点vt的总量5+4=0；（3）各中间点的流出量等于其流入量。各中间点v2的流出量减去其流入量等于0,即4－(3+1)=0
一般地，在容量网络D=(V,A,W)中，满足以下条件的流f，称为可行流：
（1）弧流量限制条件 0(fij(cij (vi,vj)(A
（2）平衡条件
式中v(f)为该可行流的流量，即发点的净输出量，或收点的净输入量。对于网络的流，可行流总是在存在的。如f={0}。
二、最大流问题最大流问题就是在容量网络D中，求一个可行流f={fij}，使其流量v(f)达到最大。其数学模型为
maxv(f)
满足
显然，最大流问题是个特殊的LP问题可用单纯形法或表上作业法求解，但利用它与图的紧密关系，能更为直观简便地求解。
三、求网络最大流的有关概念与原理
1.增广链。设D=(V,A,C)中，有一可行流f={fij}，按每条弧上流量的多少，可将弧分四种类型：
饱和弧(即fij=wij) 非饱和弧(即fij<wij)
零流弧(即fij=0) 非零流弧(即fij>0)
如图13中，(v1,v4)是饱和弧，又是非零流弧，其它各弧均为非饱和弧，也是非零流弧。
设(是中D中从vs别vt的一条链，沿此方向，从上各弧可分为两类：
正向弧（与链的方向一致的弧），其集合记为(+
反向弧（与链的方向相反的弧），其集合记为(-
如图13，在(={v1,v2,v3,v4,vt}中，(+={(vs,v2),(v1,v4),(v3,vt)},
(-={(v2,v1),(v4,v3)}
对于可行流f,(是一条从vs到vt的链，若(+中的每弧均为非饱和弧，(-中的每弧均为非零流弧，是称链(是关于f的增广链。
2.截集（割集）
若将D=(V,A,W)的V为两部分Vs和,使vs(Vs,vt(,且，则把从vs指向的弧的全体称为截集。记为()即。
截集的截量──截集中所有容量之和称为该截集的截量。记为W()举例说明，不同截集的截量不同。
可以理解，任何可行流的流量v(f)(W(Vs.)
3,最大流最小截量定理：
任一网络D中，最大流的流量=最小截集的截量。
四、求最大流的方法(Ford-Fulkerson标号法)
从以上概念及定理可知，要判断可行流f是否最大流有两种途径：
1）能否找出可行流f的增广链，若能，则f不是最大流，否则f是最大流。
2）V(f)是否等于最小截量，若等，则f是最大流，否则f不是最大流。
1,标号法的基本思想：从可行流f出发，由Vs开始，用对D中的每个顶点进行标号的办法找f的增广链(。若无，则f为所求的最大流。否则，在增广链上进行调整。
调整理：
调整方法：
2.步骤
（1）给出初始可行流f(如f=0)
（2）给顶点标号，寻找增广链。标号(vi,L(vi))的第一个标号表示vi点而来，第二个标号L(vi)表示增广链上中该弧允许的调整量。
在标号过程中，每个属于且仅属于下列集合之一：
Vo──已标号未检验点集，Vs──已标号已检验的点集，──未标号点集。
首先给vs标号(0,+()，此时，Vo={Vs}((,={V1…Vt}。
（3）若Vo非空，则反复按以下①②进行，否则按第(5)步：
①在Vo中任选vi，检查vi到的弧(vi,vj)，或中的点vj到vi的弧(vj,vi)，满足以下条件者给vj标号。
i)对正向弧(vi,vj)，若非饱和，则给点vj标以(vi,l(vj))，其中l(Vj)=min{l(vj),(wij－fij)}
同时把Vj从中除去，归入Vo，若Vt∈Vo说明已找出f的增广链(按(4)。
ii)对反向弧(vj,vi)，若非零流，则给点Vj标以(-vi,l(Vj))，其中l(Vj)=min{l(vj),fij}
同时把Vj从中除去，归入Vo
②把已检验的点vi，归入Vs
（4）在增广链(上调整，得新可行流f(。返回(2)。
（5）写出最大流f*={fij}的流量v(f*)，和最小截集W(Vs*,)，终止。
例 用Ford—Fulkerson标号法求下图的最大流
调整后为：
（图14）
由于标号进行不下去(即Vo=()，因此，目前可行流就是最大流。
最小截集：(Vs*,)={(vs,v1),(v2,v3)}──瓶颈（扩大流量的关链）最大流量V(f*)=6+7=13。
§5,最小费用最大流问题（详见书）
第四部分 对策论模型
§1,两人有限零和对策模型及其解法
一、对策现象的三要素由引例《齐王赛马》导出对策现象的三要素：
1.局中人：对策中有权决定自己行动方案的参加者，称为局中人。通常用I表示局中人集合。如果有n个局中人，则I={1,2,…n}。一般要求一个对策中至少有两个局中人。
局中人总是被假定是聪明且有理智的。
2.策略集：对策中可供局中人选择的一个实际可行的完整的行动方案，称为一个（纯）策略；参加对策的每一局中人i(I的策略集记为Si。一般每一局中人的策略集中至少应包括两个（纯）策略。
如《齐王赛马》中，若用（上、中、下）表示以上马、中马、下马依次参赛，就是一个纯策略。齐王与田忌的策略集中，各自都有六个纯策略：S1,S2={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、上、中),(下、中、上)}
3.赢得函数（支付函数）
（1）局势：对策中，每一局中人所选定策略形成的策略组合称一个局势。设局中人1从自己的策略集S1={(1,(2 …,(m}中选定策略(i，局中人2从自己的策略集S2={(1,(2 …,(n}选定策略(j，则((i,(j)就构成两人对策中的一个局势。
在n个对策中，设si表示第i局中人的一个策略，则n个局中人的策略组合形成的局势为S=(s1,s2,…sn)。
（2）赢得函数：当一个局势S出现后，各局中人都有自己的结果（得失），记为Hi(S)，它表示第i局中人的赢得（支付）值。显然Hi(S)是局势的函数。
例如在“齐王赛马”中，局中人集合I={1,2}，齐王和田忌的策略集分别用S1={(1,…(6}和S2={(1,…(6}表示。在(1=(上、中、下)，(1=(上、中、下)构成的局势S1={(1,(1}下，齐王的赢得为H1(S)=3，田忌的赢得为H2(S)=-3。
二、对策的分类 完全信息静态对策，不完全信息静态对策完全信息动态对策，不完全信息动态对策
三、两人有限零和对策的数学模型两人有限零和对策，又称为矩阵对策。其数学模型为：
={Ⅰ,Ⅱ;S1,S2,A}或={S1,S2;A}
其中策略集S1={(1,(2,…,(m}，S2={(1,(2,…,(n}分别为局中人Ⅰ和Ⅱ的策略集，A=(aij)mxn为局中人Ⅰ的赢得矩阵，由于假定对策的结果为零和，所以局中人Ⅱ的羸得矩阵为-A。
四、在纯策略下有解的矩阵对策的解法
1.解法的思想：双方都立足在不利的情况下争取最好的结果──最大最小原则。
例 求解矩阵对策={S1,S2;A}，其中，
解
16 2 5
，，
即=
2.在矩阵对策中，若=ai*j*成立，则称ai*j*为对策的值，记为V=ai*j*。称使上式成立的纯局势((i*,(j*)为对策在纯策略下的解（亦称均衡局势）。(i*和(j*分别称为局中人Ⅰ和Ⅱ的最优纯策略。
3.方法步骤：
上例可求解过程可简单的表述如下：
其步骤是：
第一步：分别确定A各行中的最小值，并在该数字上加圈表示；
第二步：分别确定A各列中的最大值，并在该数字上加框表示；
第三步：若A中的某元素同时被圈和框住，则该元素即为对策的值，该元素所在的行和列对应的策略则分别为局中人Ⅰ和Ⅱ的最优纯策略，并由最优纯策略组成了对策的解。
因此上例对策的值V=2，对策的解为((2,(2)，(2,(2分别是局中人Ⅰ和Ⅱ的最优纯策略。
在纯策略下有解的矩阵对策中，值ai*j*既是所在行的最小值，又是所在列的最大值，称其为鞍点。所以这类矩阵对策又称为鞍点的对策。这个事实可推广到一般，即在纯策略下矩阵对策={S1,S2;A}有解的充要条件是：存在纯局势((i*,(j*)，使得对于一切的i=1,2…m,j=1,2…n均有
aij*(ai*j*(ai*j
矩阵对策的解可以不唯一。
五、具有混合策略的矩阵对策在具有鞍点的对策中，局中人Ⅰ的赢得，局中人Ⅱ的损失，且。但一般情况下却总有。
例如
该矩阵对策在纯策略下无解。此时，用最大最小原则来选取各自的纯策略都不会是稳定的，因为各局中人可以选取其它的纯策略来改善自己的赢得值。
在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自己的期望赢得（损失）。按概率分布，上例局中人的期望赢得为
=8xy－6y－x+8
=
这就是说，局中人分别以概率选用(1,(2时，至少赢得，同理，局中人Ⅱ分别以概率选用策略(1,(2，至多损失。但当或时，则会受到更大的损失。
1.混合策略和混合局势的概念
2.混合扩充和混合策略下的解的概念（详见书）
在纯策略下矩阵对策的解是混合策略下矩阵对策解的特殊情况。
3.基本定理（不加证明）
（1）在混合扩充下，任何矩阵对策必有解；
（2）在混合策略下，(X*,Y*)是对策解的充要条件是：
E(X,Y*)(E(X*,Y*)(E(X*,Y)
其等价形式是
E(i,Y*)(E(X*,Y*)(E(X*,j)
其中E(i,Y*)表示当局中人Ⅰ取纯策略(i，局中人Ⅱ取最优混合策略时，局中人Ⅰ的期望赢得 即E(i,Y*)=。
E(X*,j)表示当局中人Ⅱ取纯策略(j，局中人Ⅰ取最优混合策略时，局中人Ⅰ的期望赢得 即E(X*,j)=。
作为应用，给出（2）的另一等价形式：
（3）(X*,Y*)为对策的解的充要条件是存在数v，使X*,Y*分别是下面两个不等式组的解：
(1°) (2°)
六、矩阵对策的一般解法
1.LP法（详见书）
应当指出，在未求解(P)和(D)之前，V的正负是未知的。当V=v(0时，可以v>0或v<0。
（1）若A=(aij)mxn中所有元素均为正值，则必有v>0，此时建立的LP模型(P)和(D)所用单纯形法求解，且X*(0,Y*(0。
（2）若A=(aij)mxn中含有负元素时，则有可能出现v(0，由此而可能出现无解，这与基本定理相矛盾。此时，可根据下述定理进行处理：
定理：设对策={SⅠSⅡA}和对策(={SⅠSⅡA(}，其中A=(aij)mxn，
A(=(aij+k)mxn,k为任一常数，则与(的解相同，且V=V(－k。
其方法是先对含有负元素的A加上正数k,k=-min{aij}，构成一个新的赢得矩阵A(，再用LP法进行求解，所得的解就是原对策的解,但V=V(－k。
2.2×n对策的解法赢得矩阵形为的对策称为2×n对策。
(1) 2×2对策的公式法由于在纯策略下无解的2×2对策，其最优混合策略(x1*,x2*)>0，(y1*,y2*)>0，所以由LP对偶理论中的互补松驰性知，基本定理(3)的两组不等式均可取等式。且
(1°) (2°)
有唯一解：
(2)2×n对策的代数解法：
对2×n对策，可先将2×n对策转化为Cn2个2×2子对策，再利用2×2对策的公式法，分别求出各子对策的值，最后从中解出2×n对策的解，其步骤如下：
第一步：由2×n阶矩阵A分别写出Cn2个2×2阶子矩阵Ai；
第二步：分别求出各Ai相应子对策的值Vi；
第三步：取V=min{Vi}=Vk,1(k(N，其中N=Cn2,Ak是由A中的两列所构成；
第四步：求出Ak相应子对策k的解X(o)、Y(o)，取X*=Xo，同时在Y(o)中添加n－2个0分量在对应列的位置上，构成Y*，则(X*Y*)就是原2×n对策的解。
例 已知赢得矩阵为试用代数法求解此对策。
(3)2×n对策的图解法（详见书）
3.迭代法（详见书）
七、求解矩阵对策中的计算技巧
1.用优超原则简化赢得矩阵例
优超原则：在A=(aij)mxn中
(1)若第k行与第l行的各元素均有
akj(alj (j=1,2…n)
则称局中人Ⅰ的纯策略(k优超于纯策略(l，此时在最优混合策略中必有Xi*=0。（即可在A中删去第l行）。
(2)若第p列与第q列的各元素均有
aip(aiq (i=1,2…m)
则称局中人Ⅱ的纯策略(p优超于纯策略(q，此时在最优混合策略中必有yq*=0（即可在A中删去第q列）。
值得指出的是，对于A中的纯策略(i1(或(j1)不为纯策略(i2…(im(或(j2…(jm)所优超。但被它们的凸组合所优超，即
(或)
此时，同样可在A删去第i1行(或第j1列)，对策的解不变。
2.若两个矩阵对策1={SⅠ,SⅡ,A1}，2={SⅠ,SⅡ,A2}且满足A1=A2+k(k为任一常数)，则V1=V2+k，且它们有相同的解。
3.若两个矩阵对策1和2满足A1=kA2(k为任一常数)，则V1=kV2，且它们有相同的解。
4.设A为n个阶对角矩阵（即主对角线上的元素为a11,a22…ann，其余元素均为0）。若a11,a22…ann符号相同，则
且VG=(。其中
例 两小孩猜扑克牌花色，游戏规定：由甲小孩每次从4种花色的牌中拿出一张牌给乙小孩猜，猜对花色，甲付给乙小石子三个；猜不对，乙付给甲一个石子，试求游戏的解。
解 据题意，该游戏可归结为矩阵模型G={S甲,S乙,A}，其中甲小孩的赢得
显然该对策无鞍点，为简化计算，对A中各元素减1，得
于是有,且(=-1，
X*=Y*=(1/4,1/4,1/4,1/4)。
即甲、乙两小孩应以1/4的概率出（或猜）各种花色的牌，互不吃亏。
5.设A为n阶矩阵。若,则X*=Y*=(1/n,1/n,1/n,1/n)，且VG=b/n。
“齐王赛马”的羸得矩阵满足上述条件，故由此可得
X*=Y*=(1/6,1/6,1/6,1/6)，且VG=6/6=1。
对于矩阵对策，该选用哪种方法进行求解？一般可按以下顺序进行考虑：
1°首先，用最大最小原则试求鞍点。若无，则考虑以下方法；
2°若A为特殊矩阵，则可选用上述4,5给出的结论，直接求解；
3°对3×3阶以上的赢得矩阵A，试用优超法将A降价；
4°对2×n对策，可转化为Cn2个2×2对策，分别用公式法求解，并从中求出原对策的解；
5°以上方法均不可行时，则可用LP法或迭代法求解。
§2,两人有限非零和对策（详见书）
