《第八章图与网络.ppt》由会员分享，可在线阅读，更多相关《第八章图与网络.ppt（130页珍藏版）》请在三一办公上搜索。
1、第 八 章 图 与 网 络 分 析,教学目的：让学生了解图论的基本知识，掌握用网络表示所研究问题、对象的基本属性及其解决方法。教学内容：基本概念、树、最短路、最大流、最小费用最大流等。教学难点：建立网络图的技巧和各种方法产生的思路。学时安排：810学时。,第一节 图与网络的基本知识,1、18世纪哥尼斯堡城中普雷格尔河中有两个小岛C、D，它们之间与两岸A、B共有七座桥相连。,一、图论形成的历史回顾,A,B,当地人热衷于这样的游戏：一个人怎样才能一次连续走过七桥且每桥只走一次，再回到出发点。,1736年，著名数学家欧拉把此问题简化为图，并发表了论文：“依据几何位置的解题方法”。,能否从某一点开始不
2、重复地一笔画出这个图形，最终回到原点?,2、1847年，物理学家基尔霍夫为解决有关线性方程组而发展了“树”的理论。他将网络中的电感、电容、电阻等抽象为点和线，得到一简单的组合结构。这种结构便于运算，不必指明为何种元素。,3、1857年，凯莱研究饱和烃链CnH2n+2的同分异构体时，又一次引入树状结构，例如，C4H10。,5、1857年，英国数学家哈密尔顿发明了一个游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上的20个城市，要求寻找一条路径：由某个城市出发每城市仅去一次，最终回到出发点。,1、有向图与无向图：如果顶点之间的连线皆是无方向的（称为边，边的集合记为E），此
3、时图G称为无向图，记为G=（V，E）；如果顶点之间的连线有方向，即有向边（或称为弧，弧的集合记为A），此时图G称为有向图，记为 D=（V，A）。用m(D)=E（A）表示图D 中边（弧）的数量；用n(D)=V表示图D中顶点的数量。,一个图是由点集V=vi和V中元素（顶点）之间的连线所组成。,二、图与网络的基本概念,G=（V，E）V=A，B，C，D，N，F，G，H，ME=A,A,A,B,A,C,H,Mm(G)=12；n(G)=9,边,端点,端点,D=（V，A）V=M，N，F，GA=M,G,G,F,M,N,N,F,弧,始点,终点,2、如果一条边的两端点相同，此边称为环，两点之间多于一条边的，称为多重
4、边。,3、简单图：无多重边和环的图；多重图：有多重边，无环的图。,4、链：点、边交替的序列（V1,e1,V2,e2,Vi,ei)；简单链：边不重复，A,C,D,B,G,D,N;初等链：点、边不重复，A,B,G,F,N;。,5、圈：链上首、尾节点是同一节点时，称为圈；简单圈：圈中没有重复的边；(A,B,G,B,D,C,A)初等圈：既无重复点，也无重复边;(A,B,D,C,A),路：链上边方向一致时，称为路；回路：路上首、尾节点是同一节点时，称为回路。,6、顶点的次：以点vi为端点的边数，记为d(vi)。,如图中d(A)=2（用于无向图）。,出次：以点vi为始点的边数，用d+(vi)表示。入次：以
5、点vi为终点的边数，用d-(vi)表示。d+(vi)+d-(vi)=d(vi)（用于有向图）。,d+(D)=1d-(D)=1d(D)=2,偶点：d(v)=偶数；奇点：d(v)=奇数悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图,7、连通图：图G=（V,E）中任意两点间至少有一条链。子图：G=（V,E），其中 VV，E E。,支撑（生成）子图：对于子图G=（V，E），当V=V时，且与图G=（V，E）的连通性相同的子图称为支撑子图，或生成子图。,8、完全图：任意两点间皆有边相连的无向简单图。,9、基础图：将有向图中弧去掉其方向所形成的无向图，称为原有向图的
6、基础图。网络：给图的边或点赋予某些数量指标（我们称之为“权”），这种赋权图又称为网络。,10、图的矩阵表示：邻接矩阵与权矩阵,（1）邻接矩阵：图G=(V，E)，V=n，构造一个矩阵邻接矩阵A=(aij)nn，其中,（2）权矩阵：图G=(V，E)，V=n，边（vi，vj)有权ij，构造矩阵权矩阵B=(bij)nn，其中,定理1 任何图中，顶点次的总和等于边数的2倍。,三、基本理论,d(G)=2;d(D)=2;d(N)=2;d(F)=2;,次为奇数的点为奇点，次为偶数的点为偶点。奇点的集合可记为V1，偶点的集合记为V2。,定理2 任何图中，次为奇数的顶点必为偶数个。,四、欧拉回路与道路定义：连通图
7、G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（图）。,定理：无向连通图G是欧拉图，当且仅当G中无奇点。,推论无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。推论无向连通图有欧拉道路，当且仅当中恰有两个奇点。定理：连通有向图是欧拉图，当且仅当它每个顶点的出次等于入次。,五、中国邮路问题(Chinese postman problem),一个邮递员如何选择一条道路，是他能从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程为最短。给定一个连通图，每边有非负权l(e)
8、，要求一条回路过每边至少一次，且满足总权最小。中国邮路问题可用于邮政部门、扫雪车路线、洒水车路线、警车巡逻路线、(计算机绘图)如何节约画笔的空走问题、(计算机制造工业)如何将激光刻制用于集成电路加工的模具等。定理：已知图G*=G+E1，无奇点，则L(E1)=l(e)最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。奇偶点图上作业法。,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,第 二 节 树,主要内容：1.树的概念与性质2.最小生成树及其算法,1.树连通且不含圈的
9、无向图称为树。树中次为1的点为树叶，次大于1的点称为分枝点。,一、树的概念与性质,2.生成树若图G的生成子图是一棵树，则称该树为G的生成树（或支撑树）。简称为图G的树。图中属于生成树的边叫树枝,不在生成树的边叫弦。,树枝,树枝,树枝,树枝,树枝,弦,弦,弦,弦,3.最小生成树连通图G=(V，E)，每条边上有非负权L(e)。一棵生成树所有树枝上权的总和称为这棵生成树的权。具有最小权的生成树称为最小生成树（最小支撑树），简称最小树。,定理3 设图G（V，E）是一棵树，n(G)2，则G中至少有两个悬挂点,（1）T无圈，且m=（n-1）。,定理4 图T=(V，E)，V=n，E=m，若T是一棵树，则下列
10、关于树的说法是等价的。,（2）T连通，且m=（n-1）。（3）T无圈，但每加一新边即得唯一一个圈。,（4）T连通，但任舍去一边就不连通。(5)T中任意两点，有唯一链相连。,定理5：图G有支撑树的充要条件为G是连通图。,该定理的证明给出了求生成树的方法：每步选出一条边，使它与已经选出的边不形成圈，直至选出（n-1）条边为止。,(1)支撑树的求法:破圈法,（1）避圈法每步从未选的边中选取e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够（n-1）条边为止。,（2）破圈法每步从未破掉的圈中任选一个圈，将该圈的边中权最大的一条边e去掉，直到图中无圈为止。,例82 一个乡有9个自然村，其间道路
11、及各道路长度如下图所示，各边上的权表示距离，问如何拉电缆线才能使用线总长度最短。,解：这是一个最小生成树问题。具体解法如下：,二、最小生成树的算法,最小树权值为W(T)=5+2+3+2+3+4+6+1=26。,1,2,3,3,4,5,6,2,第 三 节 最 短 路 问 题,一、问题的提出,二、最短路的定义,设D=（V，A）为一个赋权有向图，图中各弧（vi，vj）有权lij0，vs、vt为图中任意两点，求一条路P0，它是从vs 到 vt的所有路P中总权最小的路。w(p0)=min w(p),P=(v1,v2,v4,v5),(v1,v3,v5),P0=(v1,v2,v4,v5),w(p0)=14,
12、三、Dijkstra算法(1959年),用于求解指定两点间的最短路，或从指定点到其余各点的最短路。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等，是目前被认为求无负权网络最短路问题的最好方法。其采用的是贪心法的算法策略。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。,1、算法思路,(1)当lij0时，若从vi 出发的弧中权值最小者是（vi，vk）那么，从vi至 vk的最短路长必然是lik。,(2)若序列v1，v2，vk，vn 是从v1 至 vn 的一个最短路，则序列v1，v2，vk是从
13、v1至 vk的一个最短路程。即，全局最优，一定是局部最优的。,序列v1，v4，v5 是从v1 至 vn 的一个最短路,则序列v1，v4是从v1 至 v4 的一个最短路,从vs出发，给从vs 到 vk 最短路长的点 vk 赋予固定标号P(permanent label)标号，并记下相应的最短路长（真实的长度）；而未得到P标号的点，赋予试探性(临时性标号)标号T(tentative label)标号，表示从vs 到vk 点的最短路长的上界。,（3）标记：,P(v1)=0,T(v2)=3,T(v4)=8,T(v6)=14,(1)给vs以P标号，P(vs)=0，其余各点均给T类标号，T(vi)=+(2
14、)若vi点为刚得到P标号的点,考虑这样的点vj：(vi，vj)E,且vj为T标号,对其T标号进行如下更改：T(vj)=min T(vj),P(v i)+lij(3)比较所有具有T标号的点,把最小者vk改为P标号：P(vk)=min T(vk)若vt得到固定标号则停止,否则用vk 代替vi,转回(2)。,2、算法的步骤,P(v1)=0,T(v3)=+,T(v2)=+,T(v4)=+,T(v2)=3,T(v3)=1,P(v3)=1,T(v4)=4,T(v2)=2,P(v2)=2,P(v4)=4,(vi)=vm:表示从v1到vi的最短路上,vi的前一个点是vm,(v2)=,v3,(v4)=,v3,S
15、:已获得固定标号的点的集合,例85 用Dijkstra算法求下图中vs 到 vt点的最短路。,3、举例,P(vs)=0,T(v1)=+,T(v3)=+,T(v5)=+,T(v2)=+,T(v4)=+,T(v6)=+,T(vt)=+,T(v1)=4,T(v2)=6,P(v1)=4,T(v3)=9,T(v4)=8,P(v2)=6,P(v4)=8,T(v5)=13,T(v6)=14,P(v3)=9,P(v5)=13,T(vt)=17,P(v6)=14,P(vt)=15,(vt)=v6,T=+,P=0,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=+,T=2,T=8,P=2,T=
16、3,P=3,T=4,P=4,T=10,T=11,T=6,P=6,P=8,T=15,P=10,T=14,P=11,P=14,T=15,P=15,P=15,四、带有负权网络的最短路解法 逐次逼近法,（1）基本思想：若v1 到 vj 的最短路总是沿着该路 从v1 到某一点vi，然后再沿着边（vi，vj）到 vj。则从v1 到点vi的这条路，也是从v1 到点vi的最短路。如果令P1i为从v1 到点vi的最短路长，则下列方程成立：P1j=minP1i+lij i=1,2,n 该方程表明：v1到 vj的最短路要依次考察网络中的所有点vi i=1,2,n。当改变 vj时，可以求出从v1到其它各个点的最短路。
17、,v4,（2）迭代公式：,P1j(1)=0，3，1，,P1j(2)=minP1i(1)+lij=minP11(1)+l1j，P12(1)+l2j，P13(1)+l3j，P14(1)+l4j,P14(2)=minP1i(1)+li4=minP11(1)+l14，P12(1)+l24，P13(1)+l34，P14(1)+l44=min0+，3+5，1+3，+0=4,P14(2)=4,(v4)=v3,P1j(3)=minP1i(2)+lij=minP11(2)+l1j，P12(2)+l2j，P13(2)+l3j，P14(2)+l4j,P14(3)=minP1i(2)+li4=minP11(2)+l1
18、4，P12(2)+l24，P13(2)+l34，P14(2)+l44=min0+，2+5，1+3，4+0=4,P14(2)=4,(v4)=v3,例8-6:求v1到各点的最短路。,第一步：初始条件为：P1j(1)=0，2，5，-3，,第二步：第一次迭代（k=2）P11(2)=minP11(1)，P12(1)，P13(1)，P14(1)，P15(1)，P16(1)，P17(1)，P18(1),+l11+l21+l31+l41+l5 1+l61+l71+l81,=min(0+0,2+,5+,-3+,)=0,P12(2)=minP11(1)，P12(1)，P13(1），P14(1)，P15(1)，P1
19、6(1)，P17(1)，P18(1),+l12+l22+l32+l42+l52+l62+l72+l82,=min(0+2,2+0,5+,-3+,)=2,V1V2V3V4V5V6V7V8,i,j,lij,v1 v2 v3 v4 v5 v6 v7 v8,0,2 0,5-2 0 4,-307,4 0-3 3,602,0-1,40,P1j(1),P1j(2),P1j(3),P1j(4),P1j(5),0 2 5-3,0 2 0-3 6 11,0 2 0-3 6 6 15,0 2 0-3 3 61410,0 2 0-3 3 6 910,P1j(6),0 2 0-3 3 6 910,最短路径可采取“反向追
20、踪”的方法，依据：,P1j=minP1i+lij i=1,2,n,P1j(k)=minP1i(k-1)+lij,五、求任意两点间最短距离(Floyd algorithm),1、权矩阵：图G=(V，E)，V=n，边（vi，vj)有权lij，则权矩阵 D=(dij)nn被定义为：,2、步骤：（1）输入权矩阵 D（0）=D；（2）D(k)=(dij(k)nn dij(k)=min(dij(k-1),dik(k-1)+dkj(k-1)(3)k=n，迭代结束，D(n)中即为任意两点间最短路。,Floyd算法又称插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。,注意：（1）dij(1)表示从vi
21、到vj，借助于v1或不借助于v1到达vj时的 最短路。同理，dij(k)表示从vi 到 vj，借助于k个中间点v1、v2、vk 到达vj的最短路。由于在第一次迭代时v1已经使用过，第二次迭代只需增加一个新点v2。依次类推，增加 v3、v4等等。（2）当图中不存在负回路(即回路上边的权之和为负数)时，两点间的最短路径最多不超过n步。（3）如果有无向边，要理解为存在方向相反的两条边。（4）如果要知道最短路径的信息，则要保留有关下标的信息。,优点：容易理解，可以算出任意两个节点之间的最短距离，稠密图效果最佳，边权可正可负，代码编写简单；算法描述 a)初始化：Du,v=Au,v b)For k:=1
22、to n For i:=1 to n For j:=1 to n If Di,jDi,k+Dk,j Then DI,j:=DI,k+Dk,j;c)算法结束：D即为所有点对的最短路径矩阵缺点：时间复杂度比较高O(n3)，不适合计算大量数据。,例：求图中任意两点间的距离,10,6,7,7,3,7,7,5,4,6,6,6,6,第 四 节 最 大 流 问 题,一、问题的提出,3,3,2,1,4,1.网络与流（1）网络:设有向连通图D=(V，A)，D的每条弧(vi，vj)上有非负数 cij 称为弧的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0 的点 vt 称为收点(汇)，其余点为中间点，这
23、样的网络D称为容量网络，常记为D=(V，A，C)。,二、有关概念,发点,收点,中间点,中间点,(容量),(容量),(容量),(容量),(容量),（1）网络,容量网络,（2）流,对任一D中的弧(vi，vj)有流量fij，称集合f=fij 为网络G上的一个流。,称满足下列两个条件的流 f 为可行流。容量限制条件：对D中每条弧(vi，vj)，有0 fij cij,w为网络流的总流量。,对中间点vi，有,对收、发点vt、vs，有,平衡条件,一个流 f=fij，当 fij=cij，则称流 f 对弧(vi，vj)是饱和的，简称(vi，vj)是饱和弧；当 fij 0，则称弧(vi，vj)是非零流弧。,饱和弧
24、、零流弧,最大流问题,最大流问题就是求一个流fij使其流量w最大，并且满足容量限制条件和平衡条件。,3.可增广链,若是网络中联结发点和收点的一条链,定义链的方向为从发点到收点,则链上的弧分为两类：一类是弧的方向与链的方向一致,称为前向弧(+)；另一类是弧的方向与链的方向相反(-)，称为后向弧。,链=（v1,v2,v3,v4）,+=(v1,v2),(v3,v4),-=(v2,v3),可增广链：,设f是一个可行流,是从vs到vt的一条链,若满足下列条件,称为（关于可行流）的可增广链：在弧（vi,vj）+上，0f ijc ij，即+中每一条弧是非饱和弧；在弧（vi,vj）-上，0 f ij c ij
25、，即-中每一条弧是非零流弧,链=（v1,v2,v3,v4）,容量网络D=(V，A，C)，若有弧集A为A的子集，将D分为两个彼此独立的子图D1、D2，其顶点集合分别为V1、V2，V1 V2=V，V1 V2=，满足：（1）vsV1，vtV2；（2）D*=(V，A-A)不连通；而A中任一真子集A，D*=(V，A-A)仍连通。则称弧集A为D的截集(割集）。截集中弧的容量之和称为截集的容量，简称截量，记为C(V1,V2),4、截集、截量、最小截集,A=(v1,v2),(v3,v2),(v3,v4),三、有关理论,定理10：设 f 为网络D=(V，A，C)的任一可行流，流量为w，（V1，V2）是D的任一截
26、集，则有 w C(V1，V2),任一个网络D 中，从vs 到 vt的最大流的流量等于分离vs、vt的最小截集的容量。,定理11(最大流最小截集定理),证明：设 f*是一个最大流，流量为w，用下面的方法定义点集V1：令vsV1；若点vi V1，且 fij0，则令 vjV1。反复上面步骤，直到V1无法再扩充为止。在这种定义下，vt一定不属于V1。否则，若vtV1，根据V1的定义，可得到从vs到vt的一条链，规定上凡与同向的边称为前向弧，凡与反向称为后向弧。显然，所有前向弧有fij0。我们令,我们把 f*修改为 f1*：,不难验证 f1*仍为可行流，但 f1*的总流量却比 f*多了，这与 f*是最大
27、流矛盾。故vt不属于V1。,令V2=V-V1，我们有vtV2。于是我们得到一个截集（V1，V2），并且有,但流量又满足,所以，最大流的流量等于最小截集的容量。,容量网络D，若为网络中从vs到vt的一条链，给定向为从vs 到 vt，上的边凡与同向称为前向弧，凡与反向称为后向弧，其集合分别用+和-表示，f 是一个可行流，如果满足：（1）上的所有前向弧皆是非饱和弧；（2）上的所有后向弧皆是非零流弧，则称为从vs到vt 的（关于可行流 f 的）可增广链。,推论 可行流是最大流的充要条件是不存在从vs到vt 的（关于f 的）可增广链。,四、最大流判别,1、首先给定一可行流。2、然后，开始标号过程。（1）
28、给发点vs标号（，+）。其中第一项表示与何点连接，第二项表示可通过的流量。（2）选择一个已经标号的vi点，对于它的所有未标号邻接点vj按下列规则处理：,五、求最大流标号算法（Ford-Fulkerson),(a)在弧(vi，vj)上，如果 fij0，则给vj标号（-vi，j）。j=min i,fji 若vt得不到标号，则不存在可增广链，此时的流为最大流。否则，转向调整过程。3、调整过程。如果vt得到了标号，则当前流不是最大流，存在从发点到收点的增广链=+，-。,令vt 标号的第二项为，即 t=，可以 对当前可行流做如下调整：,4、对新的可行流重复标号和调整过程，直至得到最大流。,例:,下图给出
29、一个网络及其初始可行流，每条边上的有序数表示的是（cij，fij），试求这个网络的最大流。,（1）先给vs标号（，+）。,(,+),（2）检查这个标号点相邻的顶点v1,v2,v3,弧（vs,v1）已经饱和,其它两点满足前向弧流量小于容量的标号条件。,(vs,1),(vs,2),(,+),v2:（vs,2）=（vs,2）,2=min s,cs2-fs2=2 v3:（vs,3）=（vs,1）,3=mins,cs3-fs3=1,先考察与v3相邻的点v6，其弧已饱和。所以，转而考察另一个已标号点v2。根据标号条件，v5 得标号（v2，5）=（v2，2）。,(v2,2),(vs,2),(vs,1),vt
30、从v5得不到标号,而在(v1,v5)上,f15 0,所以,v1可以得到标号,由于与行进方向相反,1=min5,f15=2,v1标号为（-v5,1）=（-v5，2）,(-v5,2),(v2,2),(v1,2),(v4,2),（3）由于vt得到了标号，所以，当前的流不是最大流，需要调整。在已经找到的增广链上（见图中粉红线）：,（4）调整:前向弧流量加上vt标号第二项的值（2）；反向弧减去第二项的值（2）,(4,4),(3,2),(3,1),(5,4),(4,4),经检查，此时的可行流是最大流，流量为11。,(,+),(vs,1),例:,下图给出一个网络及其初始可行流，每条边上的有序数表示的是（ci
31、j，fij），试求这个网络的最大流。,(,+),(vs,4),(,+),(-v1,1),(vs,4),(v2,1),(-v2,1),(-v1,1),(v3,1),(5,2),(1,0),(1,0),(2,2),(,+),(vs,3),w=fs2+fs1=f4t+f3t=5,(8,3),(7,3),(6,5),(5,5),(10,5),(15,15),(6,6),(9,9),(10,2),(11,11),(9,7),(18,7),(7,7),(,+),(vs,5),(vs,5),(,+),(v1,4),(vs,5),(v4,1),(v4,2),(-v4,4),(v4,4),(v1,4),(v4,
32、1),(-v4,4),(v4,4),(v6,2),(v4,2),(v8,2),(v6,2),(v7,2),(8,5),(7,5),(9,9),(18,9),(12,2),(15,2),(,+),(vs,5),(vs,5),(v4,1),(v4,5),(-v4,5),第五节 最小费用流问题,已知容量网络G=(V,E,C)，每条边(vi,vj)除了已给的容量cij外，还给出了单位流量的费用dij(0)，记G=(V,E,C,d)，求G的一个可行流f=(fij)，使得流量W(f)=v，且总费用最小。当要求f为最大流时，此问题即为最小费用最大流问题求解方法：原始算法、对偶算法。,定义：已知网络G=(V,
33、E,C)，f是G上的一个可行流，为从vi 到vj的（关于f的）可增广链，称为链的费用。,链=（v1,v2,v3,v4）,d()=(4+3)-1=6,-=(v2,v3),+=(v1,v2),(v3,v4),对偶算法的基本思路：,先找一个流量为w(f(0)v的最小费用流，然后寻找从vi 到vj的可增广链，用最大流的方法将f(0)调整到f(1)，使f(1)流量为W(f(0)+，且保证f(1)是在W(f(0)+流量下的最小 费用流，不断进行到W(f(k)=v为止。,第六节 中国邮路问题,一、欧拉回路与道路定义：连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过
34、每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（图）。,定理：无向连通图G是欧拉图，当且仅当G中无奇点。,推论无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。推论无向连通图有欧拉道路，当且仅当中恰有两个奇点。定理：连通有向图是欧拉图，当且仅当它每个顶点的出次等于入次。,二、中国邮路问题,给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。定理：已知图G*=G+E1，无奇点，则L(E1)=l(e)最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。奇偶点图上作业法。,v5,v6
35、,v9,v8,v7,5,4,3,6,3,4,4,v5,v6,v9,v8,v7,5,4,3,6,3,4,4,max z=x1+2x2+3x3,x1-x2+x3-93 x1+2x2-4x3 7 x12x2+3x3-6 x1 0,x2 0,x3 无约束。,1、将下列线性规划化为标准形式,2、写出下列线性规划问题的对偶问题。,3已知四个产地和三个销售地的运输问题，有关数据如下，求最小运费。,4、用单纯形方法求解下面的线性规划问题，并指出有唯一最优解、无穷最优解、无界解还是无解,5、用图解法求解下面的规划问题,max z=2x1+3 x2+5 x3,x1+2 x2 8 4x1 16 4 x2 12 x1
36、,x2 0,6.给出下列线性规划问题,试分析下列各种条件下最优解（基）的变化1根据该规划问题的模型与最优单纯形表，求B，B-1，Y2目标函数中变量x1的系数变为5时，求最优解。3目标函数中变量x2的系数在何范围变动时，最优解不变4约束条件右端项由（1 3）T变为（6 3）T时，求最优解5增加一个新的变量x6，P 6=（1 2）T，C6=5，求最优解,X=(x1,x2,x3)T=(0,50,50,)T,9.已知线性规划问题 其对偶问题最优解如下，试求根据对偶理论直接求出原问题最优解。,10、用单纯形法计算某整数规划问题的松弛问题的最终单纯形表如下，用割平面法求出整数规划问题的最优解。,CB,XB,b,x1,x2,x3,x4,x5,x1,x2,x3,11、求解下面的最大化指派问题,12、用分支定界法求解下面的整数规划问题,13、用Dijkstra算法求下图中vs 到 vt点的最短路。图中数据为各点间的路径长。,14、求下面网络的最大流，图中数据为cij,15、求下面图的最小生成树，图中数据为权值。,
