离散优化数学建模 (2).ppt

《离散优化数学建模 (2).ppt》由会员分享，可在线阅读，更多相关《离散优化数学建模 (2).ppt（102页珍藏版）》请在三一办公上搜索。

1、,赛题发展的特点：,1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成;某些问题需要使用计算机软件，如01A;问题的数据读取需要计算机技术，如04A（数据库数据，数据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果,如09B，11B。2.赛题的开放性增大:题意的开放性，思路的开放性，方法的开放性，结果的开放性。开放性还表现在对模型假设和对数据处理上。如10B,2008年B题 高等教育学费标准探讨,请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、

2、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。,3.试题向大规模数据处理方向发展:从05年开始，基本上每年都有一大数据量的赛题；数据结构的复杂性：数据的真实性，数据的海量性，数据的不完备性，数据的冗余性 4.求解算法和各类现代算法的融合；如：11B 5.实用性：问题和数据来自于实际，解决方法切合于实际，模型和结果可以应用于实际。6.即时性：国内外的大事，社会的热点，生活的焦点，近期发生和即将发生被关注的问题。,拿到赛题后大家需要思考的问题 题目属于哪种类型：连续的

3、、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等；将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。,1、数学建模的过程,(2)整个数学建模过程应当由三个阶段：1.建立模型：实际问题数学问题；2.数学解答：数学问题数学解；3.模型检验：数学解实际问题的解决。,解决问题涉及到的计算软件分析,重要的是参赛选手具备编程计算、计算机仿真、模拟能力。,赛题常用的计算软件：Matlab,SPSS，EXCEL等,参考网站,1 全国大学生数学建模竞赛网：2 数学中国网站 http:/3 中国数学建模网站：http:/,从问题的解决方法上分析,涉及到的数学建模方法：几何理论、组合概率、统

4、计(回归)分析;优化方法（规划）、图论与网络优化、层次分析;差分方法、微分方程、模糊数学、随机决策、多目标决策;插值与拟合、灰色系统理论、神经网络、时间序列;综合评价、机理分析等方法;,用的最多的方法是优化方法和概率统计用到优化方法的共有26个题，其中整数规划4个，线性规划7个，非线性规划14个,多目标规划6个。用到概率统计方法的有21个题，平均每年至少有一个题目用到概率统计的方法。用到图论与网络优化方法的问题有6个；用到层次分析方法的问题有个；,用到插值拟合的问题有6个；用灰色系统理论的4个;用到时间序列分析的至少2个;用到综合评价方法的至少3个；大部分题目都可以用两种以上的方法来解决,即综

5、合性较强的题目有26个,最优化概论,从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。,一、最优化概念,所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规

6、划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。,数学建模竞赛中的优化问题,2000B 钢管订购和运输问题 组合优化2001B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析,07B 乘公交，看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交

7、巡警服务平台的设置与调度图论 多目标规划12B 太阳能小屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化,从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题，就是一般最优问题的数学模型,无约束最优化问题,目标函数,二、最优化问题的一般形式,约束最优化问题,约束函数,最优解；最优值,三、最优化问题分类,分类1

8、：无约束最优化 约束最优化,非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数；,线性规划：目标函数与约束函数均为线性函数；,分类2：线性规划 非线性规划,三、最优化问题分类,分类3（根据决策变量、目标函数和要求不同）,整数规划动态规划网络规划随机规划多目标规划,三、最优化问题分类,函数最优化组合最优化,分类,函数最优化：决策变量是一定区间内的连续变量,组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合,最优化方法解决问题的步骤,（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽

9、量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。,Chapter1 线性规划(Linear Programming),LP的数学模型 LP模型的应用,本章主要内容：,线性规划问题的数学模型,1.规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标,（2）在一定的资源条件限制下，如何组织安排

10、生产获得最好的经济效益（如产品量最多、利润最大.）,线性规划问题的数学模型,例1 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,线性规划问题的数学模型,解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z

11、达到最大的x1,x2 的取值。,线性规划问题的数学模型,2.线性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function约束条件 Constraints,其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,线性规划问题的数学模型,目标函数：,约束条件：,3.线性规划数学模型的一般形式,简写为：,线性规划问题的数学模型,矩阵形式：,其中：,线性规划问题的数学模型,3.线性规划问题的标准形式,特点：(1)目标函

12、数求最大值。(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,线性规划问题的数学模型,（2）如何化标准形式,目标函数的转换,如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令，可得到上式。,即,若存在取值无约束的变量,可令 其中：,变量的变换,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令,线性规划问题的数学模型,4.线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,线性规划问题的数学模

13、型,可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。线性规划解的情况：有唯一最优解；有无穷多最优解；无界解；无可行解,建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确所有的约束条件并用决策变量的线性等式或不等式表示出来；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。求解方法：用MATLAB软件直接求解。,Chapter2 运输问题(Transportation Problem),运输问题的数学模型运输问题的应用,本章主要内容：,1.运输问

14、题模型及有关概念,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,运输问题的数学模型,例2.1 某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,运输问题的数学模型,解：产销平衡问题：总产量=总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,Min C=6x11+4x12+6x13+6x21+5x22+5

15、x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0(i=1、2；j=1、2、3）,运输问题的数学模型,运输问题的一般形式：产销平衡,A1、A2、Am 表示某物资的m个产地；B1、B2、Bn 表示某物质的n个销地；ai 表示产地Ai的产量；bj 表示销地Bj 的销量；cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：,运输问题的数学模型,变化：1）有时目标函数为求最大值。如求利润最大或营业额最大；2）当某些运

16、输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。,运输问题的应用,产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,当产大于销时，即：,数学模型为：,运输问题的应用,由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1

17、，m）。则平衡问题的数学模型为：,运输问题的应用,当销大于产时，即：,数学模型为：,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：,运输问题的应用,销大于产化为平衡问题的数学模型为：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,Chapter3 整数规划(Integer Programming),整数规划的特点及应用指配问题与匈牙利法,本章主要内容：,引言,整数规划是规划论中近几十年才发展起来的一个重要分支，主要是由于经济管理中的大量问题在抽象成模型时，人们发现许多量具有不可分割性，因此当它们被作为变量引入到规划中时，常要求

18、满足取整条件.如生产计划中，生产机器多少台(整数)；人力资源管理中，招聘员工多少人(整数)；运输问题中，从一个港口到另一个港口的集装箱调运数量(整数)；另外，运作管理中的决策问题：如工厂选址、人员的工作指派、设备购置和配置等.,一辆车最大装载重量为7吨，容量为12立方米。现有两种物品，每种物品数量无限。各种物品每件的体积、重量、价格如下表：,求这辆车中装入每种物品各多少件，使物品总价值最高。,背包问题,设三种物品的件数各为x1，x2件，总价值为z max z=4x1+3x2 s.t.3x1+4x212 4x1+2x2 7 x1，x20，x1，x2为整数,整数规划的特点及应用,整数规划（简称：I

19、P）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。,整数线性规划数学模型的一般形式：,整数规划的特点及应用,整数规划问题的种类：,纯整数规划：指全部决策变量都必须取整数值的整数规划。混合整数规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数规划。0-1型整数规划：决策变量只能取值0或1的整数规划。,整数规划的特点及应用,整数规划问题解的特征：,整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一

20、定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。,0-1整数规划,0-1整数规划是整数规划中的特殊情形，它的变量仅取值0或者1，我们通常称为0-1变量或逻辑变量.在实践中，许多问题只回答是或否.例如，对某个项目是否投资，对某个应聘者是否聘用，对某种新产品是否研发等，这类问题都可以用0-1变量来描绘.,整数规划的特点及应用,整数规划问题的求解方法：,分支定界法和割平面法 匈牙利法（指派问题）,求解整数规划模型的数学软件有：Lindo,Lingo和Matlab,其中Lindo和Lingo是

21、专业的优化软件.,指派问题 Assignment Problem,在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可以承担这些任务.一项任务只能由一个人完成，一个人只能完成一项任务。由于每人的专长不同，每个人完成各项任务的效率不同.于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小，费用最低）。,指派问题,指派问题的数学模型的标准形式：,设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的 时间或费用为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率最高？,设决策

22、变量,指派问题的数学模型为：,整数规划的特点及应用,例2 指派问题：人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。,整数规划的特点及应用,设,数学模型如下：,要求每人做一项工作，约束条件为：,整数规划的特点及应用,每项工作只能安排一人，约束条件为：,变量约束：,对于指派问题等 0-1 整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。,多目标规划模型,在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标

23、最优化问题或多目标规划问题.我们先来看一个生产计划的例子.,Chapter4 图与网络分析(Graph Theory and Network Analysis),图的基本概念与模型树与图的最小树最短路问题网络的最大流,本章主要内容：,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,图的基本概念与模型,Knigsberg桥对应的图,图的基本概念与模型,图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长

24、短曲直，对于反映对象之间的关系并不是重要的。,图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：,其中:V点集 E边集,图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。,图的基本概念与模型,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示。,图的基本概念与模型,定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;,端点,关联边,相邻,若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联

25、边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,图的基本概念与模型,环,多重边,简单图,如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。,图的基本概念与模型,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次:一个图的次等于各点的次之和。,图的基本概

26、念与模型,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。,图的基本概念与模型,二部图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。,图的基本概念与模型,子图，部分图(支撑子图),图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子

27、图。若有，则称G1是G2的一个部分图(支撑子图)。,(a),(b),（G图）,图的基本概念与模型,网络（赋权图）,设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。,图的基本概念与模型,出次与入次,有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。,有向图中，所有顶点的入次之和等于所有顶点的出次之

28、和。,图的基本概念与模型,图的模型应用,例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,图的基本概念与模型,解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A,图的基本概念与模型,图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但

29、最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。,1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中,图的基本概念与模型,例6.2 下图所表示的图可以构造邻接矩阵A如下,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：,图的基本概念与模型,2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:,3.权矩阵,树与图的最小树,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例6.2 乒乓求单打比赛抽签后，

30、可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,例6.3 某企业的组织机构图也可用树图表示。,树与图的最小树,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,最短路问题,问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中

31、得到广泛应用。,最短路问题,求最短路有两种算法:,狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法,最短路问题,狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs,v1.vn-1,vn 是从vs到vt间的最短路，则序列 vs,v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,最短路问题,求网络图的最短路，设图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为(i,j)距离为dij,P标号(点标号)：b(j)起点vs到点vj的最短路长；T标

32、号(边标号)：k(i,j)=b(i)+dij，,步骤：,1.令起点的标号；b(s)0。,2.找出所有vi已标号vj未标号的弧集合 B=(i,j)如果这样的弧不存在或vt已标号则计算结束；,3.计算集合B中弧k(i，j)=b(i)+dij的标号,4.选一个点标号 在终点vl处标号b(l),返回到第2步。,最短路问题,例6.5 求下图v1到v7的最短路长及最短路线,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已标号，计算结束。从v1到v7的最短路长是 11,最短路线：v1 v4 v6 v7,网络的最大流,基本概念：1.容量网络：队网络上的每条弧(vi,vj)都给出

33、一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,网络的最大流,2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从st的流量，则有：,网络的最大流,结论：任何网络上一定存在可行流。（零流

34、即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。,网络的最大流,割与割集,割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。,如下图中，AA将网络上的点分割成 两个集合。并有，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。,网络的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(3),7(6),A,A,B,B,网络的最大流,定理1 设网络N中一个从 s 到 t 的流 f 的流量为v(f)，(V,V

35、)为任意一个割集，则 v(f)=f(V,V)f(V,V),推论1 对网络 N中任意流量v(f)和割集(V,V)，有v(f)c(V,V),证明 w=f(V,V)f(V,V)f(V,V)c(V,V),推论2 最大流量v(f)不大于最小割集的容量，即：v(f)minc(V,V),定理2 在网络中st的最大流量等于它的最小割集的容量，即：v(f)=c(V,V),网络的最大流,求网络最大流的标号算法：基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,基本方法,找出第一个可行流，（例如所有弧的流量fij=0。）用标号的方法找一条增广链,首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：,网络的最大流,如果弧的起点为vi，并且有fij0，则vj标号(fji),(3)重复第(2)步，可能出现两种结局：,标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步,