组合优化问题简介课件

关秀翠东南大学数学系组合优化问题

(CombinatorialOptimizationProblems)关秀翠东南大学数学系组合优化问题

(Combinatoria运筹帷幄之中决胜千里之外运筹学(OperationsResearch)绪论Introduction运筹帷幄之中决胜千里之引入数学方法解决实际问题

--定性与定量方法结合系统与整体性

--从全局考察问题应用性

--源于实践、为了实践、服务于实践交叉学科

--涉及经济、管理、数学、工程和系统等多学科开放性

--不断产生新的问题和学科分支多分支

--问题的复杂性和多样性运筹学的性质与特点引入数学方法解决实际问题运筹学的性质与特点线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容线性规划数非线性规划整数规划动态规划学多目标规划双层规划组最1在数学学科中的地位运筹数学1在系统科学中的地位系统工程1在管理科学中的地位管理与运筹学1与经济学的关系问题与方法1与工程科学的关系方法与应用1与计算机科学的关系核心算法与工具基础理论应用理论应用技术运筹学运筹学的学科地位1在数学学科中的地位运筹数学1在系统科学中的地位系统工程1在模型要素

变量—可控因素目标—优化的动力和依据约束—内部条件和外部约束研究方法

建模最优性条件算法灵敏度分析最优化模型模型要素建模最优性条件算法灵敏度分析最优化模型组合优化问题简介线性规划问题几种组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题最小费用流问题算法复杂性简介组合优化问题简介线性规划问题几种组合优化问题最短路问题最小支什么是计算？分析问题：抓住本质（抽象法）一些符号记在某种器具上，计算的行为随着作为各步结果的各种特定符号而变化。因此计算可抽象成在线性带上的0、1串执行以下指令：1.写符号0；2.

写符号1；3.

向左移一格；4.

向右移一格；5.

观察当前符号以确定下一步；6.

停止。一个线性的纸带或磁带，带中可加格子实质是或者在格子里写0或1，或者移到另一格子8什么是计算？分析问题：抓住本质（抽象法）因此计算可抽象成在线Church-TuringThesisEveryeffectivecomputationoralgorithmcanbecarriedoutbyaTuringMachine.Turing,Alan(1912-1954)EffectiveComputationAlgorithmAnycomputerprogramTruingMachine9Church-TuringThesisEveryeffeWhatCanbeDonebyaComputer?ProblemSolvabilityWhatcomputerscan?Whatcomputerscan't?10WhatCanbeDonebyaComputer11Analgorithmisafinite

sequenceof

unambiguousinstructionsforsolvingawell-specifiedcomputationalproblem.ImportantFeatures:Finiteness.Definiteness.Effectiveness.AlgorithmInputOutputWhatisanAlgorithm?11AnalgorithmisafiniteseqBruteforceDivideandconquerDecreaseandconquerTransformandconquerSpaceandtimetradeoffsGreedyapproachDynamicprogrammingBacktrackingBranchandboundTwomainissuesrelatedtoalgorithmsHowtodesignalgorithms?Howtoanalyzeanalgorithm?1.Isitcorrect?2.Howarethetimeandspaceefficienciesofthealgorithm?3.Andcanwedobetter?BruteforceGreedyapproachTwoT(n)≈copC(n)Runningtimeexpressionshouldbemachine-independent.MostuseRandomAccessMachine(RAM)model.Runningtime

ofanalgorithmforagiveninputisthenumberofstepsexecutedbythealgorithmonthatinput.RunningTime13runningtimeexecutiontimeforthebasicoperationNo.oftimesthebasicoperationisexecutedinputsizeWorstCaseEfficiency:

Thealgorithmrunsthelongestamongallpossibleinputsofsizen.Considertheleadingterm,ignoretheconstantcoefficient.denotedbyO(g(n)):

classoffunctionsf(n)thatgrownofasterthang(n).

T(n)≈copC(n)Runningtimeex14OrdersofGrowthExponential-growthfunctionspolynomialfunctions14OrdersofGrowthExponential-

旅行商问题（Traveling

Salesman

Problem）一位旅行售货员要到城市

进行商品销售，已知

的距离为

他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？路线有（n-1)!种旅行商问题（TravelingSalesman

旅行商问题（Traveling

Salesman

Problem）一位旅行售货员要到城市

进行商品销售，已知

的距离为

他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？TSP：以计算机1秒可完成24个城市所有路径枚举(23!种)城市数2425262728

29

30

31计算时间1s24s10min4.3h4.9d

136.5d10.8y

325y旅行商问题（TravelingSalesman17OrdersofGrowthExponential-growthfunctionspolynomialfunctionsTSP：以计算机1秒可完成24个城市所有路径枚举(23!种)城市数2425262728

29

30

31计算时间1s24s10min4.3h4.9d

136.5d10.8y

325y17OrdersofGrowthExponential-TimeComplexity18PolynomialTimeSolvableProblemsNon-deterministicPolynomial-time(NP)SolvableProblemsNP类问题：可以在多项式时间内验证其解是否正确的问题。P类问题：可以在多项式时间内求解的问题。TimeComplexity18PolynomialTNPPandNPP19SolvableNPPandNPP19SolvableSolvableNPPandNPPPolynomial-TimeSolvableNondeterministicPolynomial-TimeSolvable20SolvableNPPandNPPPolynomial-SolvableNPPP=NP?Noanswer,now.21Polynomial-TimeSolvableNondeterministicPolynomial-TimeSolvable$1,000,000QuestionSolvableNPPP=NP?Noanswer,NPPP=NP?Noanswer,now.22NP-Complete假设P

NPNPPP=NP?Noanswer,now.22NPComplexityofaProblem23ComplexityofaProblem2324242525CopingwithNP-CompleteProblems

ExactAlgorithm

itmighttakeanabsurdlylongtime(e.g.,300centuries)tofindtheoptimalsolutionfortheproblem.Pseudo-polynomialAlgorithmEg.KnapsackProblem,(DynamicProgram)O(nW)

ApproximationAlgorithmIftheoptimalsolutionisunattainablethenitisreasonabletosacrificeoptimalityandsettlefora“good”(closetooptimal)feasiblesolutionthatcanbecomputed.HeuristicAlgorithmGeneticAlgorithm,SimulatedAnnealingAlgorithmArtificialNeuralNetwork,TabuSearchEvolutionaryAlgorithm,AntAlgorithms26CopingwithNP-CompleteProble组合优化问题简介线性规划问题几种组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题最小费用流问题算法复杂性简介组合优化问题简介线性规划问题几种组合优化问题最短路问题最小支TheDietProblemUnitPrice200400300300RequiredUnitsVA5000IUCa1000mgDietary_Fiber100gFood...Nutrient...Thegoalofthedietproblemistofindthecheapestcombinationoffoodsthatwillsatisfyallthedailynutritionalrequirementsofaperson.TheDietProblemUnit2004003003TheDietProblemFoodsPrice$SizeCaloriesCHOmgFatgNamgCarbo.gD_FibergProt.gVAIUVCIUCamgFemgChicken.841lb277.4129.910.8125.60042.277.4021.91.8Beef.271F.141.827.412.8461.70.805.4010.890.6Lettuce.021Leaf2.6001.80.40.30.2660.83.80.1Potato.221Oz139.209.2212.6151.22.261.59.614.20.5Milk.131C85.54.40.4126.211.908.4499.82.4302.30.1Tomato.27125.800.411.15.71.41766.323.56.20.6Lowerbound200010020200100255050005080010TheDietProblemFoodsPrice$SiTheDietProblemFoodsPrice$SizeCaloriesCHOmgFatgNamgCarbo.gD_FibergProt.gVAIUVCIUCamgFemgChicken.841lb277.4129.910.8125.60042.277.4021.91.8Beef.271F.141.827.412.8461.70.805.4010.890.6Lettuce.021Leaf2.6001.80.40.30.2660.83.80.1Potato.221Oz139.209.2212.6151.22.261.59.614.20.5Milk.131C85.54.40.4126.211.908.4499.82.4302.30.1Tomato.27125.800.411.15.71.41766.323.56.20.6Lowerbound200010020200100255050005080010aij:No.ofunitsofnutrientiinoneunitfoodj.6kindsoffoods11kindsofnutrientsaij

xj:No.ofunitsoffoodjinthediet.cjbi:Lowerboundofnutrientiinthediet.

TheDietProblemFoodsPrice$Si11kindsofnutrientsTheDietProblemFoodsPrice$SizeCaloriesCHOmgFatgNamgCarbo.gD_FibergProt.gVAIUVCIUCamgFemgChicken.841lb277.4129.910.8125.60042.277.4021.91.8Beef.271F.141.827.412.8461.70.805.4010.890.6Lettuce.021Leaf2.6001.80.40.30.2660.83.80.1Potato.221Oz139.209.2212.6151.22.261.59.614.20.5Milk.131C85.54.40.4126.211.908.4499.82.4302.30.1Tomato.27125.800.411.15.71.41766.323.56.20.6Lowerbound200010020200100255050005080010aij:No.ofunitsofnutrientiinoneunitfoodj.6kindsoffoodsaij

xj:No.ofunitsoffoodjinthediet.cjbi:Lowerboundofnutrientiinthediet.

11kindsofnutrientsTheDietTheLinearProgramModel

ofDietProblemaij:No.ofunitsofnutrientiinoneunitfoodj.xj:No.ofunitsoffoodjinthediet.cj:costofoneunitfoodj.bi:Lowerboundofnutrientiinthediet.

Thegoal:findthecheapestcombinationoffoodsthatwillsatisfyallthedailynutritionalrequirements.TheLinearProgramModel

ofDUnitPricec1c2c3cn...RequiredUnitsb1b2bm...Food...Nutrient...MinimizeSubjecttoTheLinearProgramModel

ofDietProblemaij:No.ofunitsofnutrientiinoneunitfoodj.xj:No.ofunitsoffoodjinthediet.Unitc1c2c3cn...Requiredb1b2b线性规划问题(LinearProgram)规范形式：一般形式标准形式：线性规划问题(LinearProgram)规范形式：一般求解线性规划的单纯形方法基本思想：保持原问题的可行性，从凸多面体的一个顶点迭代到另一个更优的顶点。求解线性规划的单纯形方法基本思想：保持原问题的可行性，从凸多研究线性规划的三次高潮单纯形法:(1947Dantzig)椭球算法:(1979苏联青年数学家)Karmarkar内点算法:(1984Karmarkar)实际运算效果非常好平均运算次数是多项式的不是多项式时间算法1972年Klee,Minty给出反例第一个多项式时间算法O(n3(m+n)L)

(L为输入规模)运用求解非线性规划的方法实际运算效果不太好从可行域的内部找到一个迭代点列达到边界O(n3.5L)

实际运算效果较好目前较好O(n3L)研究线性规划的三次高潮单纯形法:(1947Dantzig组合优化问题几种组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题最小费用流问题线性规划问题算法复杂性简介组合优化问题几种组合优化问题最短路问题最小支撑树问题指派问题38哥尼斯堡七桥问题(1736年欧拉)欧拉图：存在经过每条边一次且仅一次的回路一笔画：存在欧拉通(回)路

图连通且没有奇度顶点

图连通,奇度顶点有2,0个d(A)=3d(B)=3d(C)=5d(D)=34238哥尼斯堡七桥问题(1736年欧拉)欧拉图：存在经过每条边39哈密顿环球旅行问题(1857年)

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）39哈密顿环球旅行问题(1857年)哈密顿圈（环球旅行游戏）40中国邮路问题(1962管梅谷)：一邮递员从邮局出发要走遍他负责的每一条街道去送信，最后回到邮局要走的最短路径。还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，这些都引出了许多有实用意义的新问题，开辟了新学科.四色问题(1852年英国，1976美计算机证明)对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.问题就转化为：在一个有奇度结点的赋权连通图中，增加一些平行边，使得新图不含奇度结点，并且增加的边的总权值最小。40中国邮路问题(1962管梅谷)：还有许多诸如迷宫问题、博41图论的基本概念

定义1一个有序二元组(V,E)称为一个图,记为G=(V,E),

其中

①V称为G的顶点集,V≠

,其元素称为顶点;②

E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.顶点v的度数d(v)：G中与顶点v关联的边的数目.欧拉图

图连通且没有奇度顶点41图论的基本概念定义1一个有序二元组(V,E42我们今后只讨论有限简单图：(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.

如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.42我们今后只讨论有限简单图：(1)顶点个数是有限43定义2若图G的每条边e都对应一个实数w(e),则称w(e)为该边的权,称图G=(V,E,w)为赋权图(网络).定义3设G=(V,E)是一个图,v0,v1,…,vk∈V,且

1≤i≤k,vi-1vi∈E,则称v0v1…vk是G的一条通路.如果通路中没有相同的边,则称此通路为道路.始点和终点相同的道路称为圈或回路(cycle).

如果通路中既没有相同的边,又没有相同的顶点,则称此通路为路径,简称路(path).定义4任意两点均有通路的图称为连通图.定义5连通而无圈的图称为树,

常用T表示树(Tree).

43定义2若图G的每条边e都对应一个实数w(e),则称w44赋权图G=(V,E,w)的权矩阵A=(aij)n×n,

有限简单图基本上可用权矩阵来表示.图的权矩阵无向图G的权矩阵A是一个对称矩阵.

44赋权图G=(V,E,w)的权矩阵A=(aij45

例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法.

解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.

由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的.

以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.

根据此图便可找到渡河方法.45例一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过46(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.A1A2A3A4A5A6A7A8A9A1046(1,1,1,1)(1,1,1,0)(1,1,0组合优化问题几种组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题最小费用流问题线性规划问题算法复杂性简介组合优化问题几种组合优化问题最短路问题最小支撑树问题指派问题48最小支撑树问题的例子公路连接问题某地区有n个主要城市，现准备修建高速公路把这些城市连接起来，

使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市i和j之间修建高速公路的成本(费用)wij(>0),那么应任何决定在哪些城市间修建高速公路，使得总成本最小？

高速公路网正好构成这个完全图G的一个连通的支撑子图T.

为了使得总建设成本最小,该子图必须是无圈的

无圈连通图称为树，上类问题称为最小支撑树问题.48最小支撑树问题的例子公路连接问题高速公路网正好构成这个49村庄1电话通讯问题：阿富汗战后建设，30个村庄要通话，已知两两距离，如何用最少的电话线连通30个村庄？村庄4村庄3村庄6村庄2村庄56311598107712最小支撑树问题的例子49村庄1电话通讯问题：阿富汗战后建设，30个村庄要通话50树的基本概念定义：无圈连通图称为树(tree).无圈图(即若干棵树的并)称为森林(forest).引理

图G=(V,E)，|V|=n，则下列命题等价:G是一棵树；G连通，且|E|=n-1；G无圈，且|E|=n-1；G的任何两个顶点之间存在唯一的一条路；G连通，且将G的任何一条弧删去之后，该图成为非连通图；6)G无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈.

50树的基本概念定义：无圈连通图称为树(tree).无圈图51最小支撑树(MinimumSpanningTree)T*是G的一棵支撑树，且对G的任何一棵支撑树T都有w(T*)≤w(T)，则T*为G的最小支撑树.如果一个子图包含图的所有顶点并且是一棵树，则称这棵树为该图的支撑树.G=(V,E,w)为一个无向网络，w为边权函数.如果H=(V1,E1)为G的一个子图，定理:支撑树T*是最小树

e’

G|T*,在T*+e’形成的圈中，e’为最大弧,即w(e’)

w(e),

e

T*.

T*ee’51最小支撑树(MinimumSpanningTree)52求最小支撑树的方法

破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。655172344v1v2v3v4v5v6

避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。v3v21v42v53v64v15Kruskal(1956)O(mn)752求最小支撑树的方法破圈法：在原图中，任选一个圈，从圈53组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题几个典型的图论问题图论的基本概念最小费用流问题53组合优化问题最短路问题最小支撑树问题指派问题最大流最小割54最短路问题

(ShortestPath)若P0(u,v)是G

中连接u,v的路径,且对任意在G

中连接u,v的路径P(u,v)都w(P0)≤w(P),

则称P0(u,v)是G

中连接u,v的最短路.重要性质：最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.54最短路问题(ShortestPath)若P0(u,55求赋权图中任意两点的最短路的Floyd算法(1962)

设A=(aij)n×n为赋权图G=(V,E,w)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号.①赋初值.对所有i,j,dij=aij,rij=j.k=1.②更新dij,rij

.对所有i,j,若dik+dkj＜dij,则令dij=dik+dkj,rij=k,转向③;(求得从vi到vj经过点v1,…,vk的最短路的距离)③终止判断.若k=n终止;否则令k=k+1,转向②.

最短路线可由rij得到.(每次迭代增加一个中间点，逐步更新距离矩阵D)55求赋权图中任意两点的最短路的Floyd算法(1962)56②

计算其中例如：例求下图中任意两点间的最短路.①赋初值56②计算其中例如：例求下图中任意两点间的最短路.①赋57

中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。57中不带角标的元素表示从到的58

中不带角标的元素表示从到的距离（直接有边），带角标的元素表示借为中间点时的最短路长。在放开的基础上，再放开在放开点的基础上，再放开考察最短路。然后,58中不带角标的元素表示从到的59表示任意两点间的最短路长及其路径。比如，表示任意点1到点5之间的最短路长为6，其路径为1325。59表示任意两点间的最短路长及其路径。比如，表示任60设备更新问题

某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少.

已知设备在每年年初的购买费分别为11,11,12,12,13.使用不同时间设备所需的维修费分别为5,6,8,11,18.

解设bi表示设备在第i年年初的购买费,ci表示设备使用i年后的维修费,V={v1,v2,…,v6},点vi表示第i年年初购进一台新设备,虚设一个点v6表示第5年年底.E={vivj|1≤i＜j≤6}.60设备更新问题某企业每年年初,都要作出决定,如果继61

这样上述设备更新问题就变为：在有向赋权图G=(V,E,w)(图解如下)中求v1到v6的最短路问题.

已知设备在每年年初的购买费分别为11,11,12,12,13.使用不同时间设备所需的维修费分别为5,6,8,11,18.61这样上述设备更新问题就变为：在有向赋权图G=(V62

由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.

而这两条路都是v1到v6的最短路，费用为53.62由实际问题可知,设备使用三年后应当更新,因此删除63选址问题(LocationProblem)

现准备在n个居民点v1,v2,…,vn中设置一银行.问设在哪个点,可使最大服务距离最小?若设置两个银行,问设在哪两个点?

模型假设假设各个居民点都有条件设置银行,并有路相连,且路长已知.

模型建立与求解用Floyd算法求出任意两个居民点vi,vj之间的最短距离,并用dij表示.⑴设置一个银行,银行设在vi点的最大服务距离为63选址问题(LocationProblem)64求k,使

即若设置一个银行,则银行设在

vk点,可使最大服务距离最小.⑵设置两个银行,假设银行设在vs,vt点使最大服务距离最小.记则s,t满足：进一步,若设置多个银行呢？64求k,使即若设置一个银行,则银行设在vk点,65用三维数组表示(8升,5升,3升)酒壶的酒量则平分酒的问题化为在该图中求一条从起点到终点的最短路.从图中易得到上下两条路：显然上面一条较短，路长为7;下面一条路长为8.(3,2,3)(5,3,0)(2,5,1)(8,0,0)(0,5,3)(2,3,3)(7,0,1)(7,1,0)(4,1,3)(4,4,0)(1,4,3)(1,5,2)(6,2,0)思考题：某二人有一只8升的酒壶装满了酒,还有两只空壶,分别为5升和3升.问如何尽快将酒平分?(3,5,0)(5,0,3)(6,0,2)65用三维数组表示(8升,5升,3升)酒壶的酒量则平分酒的问66组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题几个典型的图论问题图论的基本概念最小费用流问题设备更新问题选址问题66组合优化问题最短路问题最小支撑树问题指派问题最大流最小割67二部图的匹配及其应用定义设X,Y都是非空有限集,且X∩Y=

,E

{xy|x∈X,y∈Y},称G=(X,Y,E)为二部图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图.若w：E→R+,则称G=(X,Y,E,w)为二部赋权图.67二部图的匹配及其应用定义设X,Y都是非空有限集,且68设G=(X,Y,E)为二部图,且M

E.若M中任意两条边在G中均不邻接,则称M是G的一个匹配.设M是二部图G的一个匹配,如果G的每一个点都是M中边的顶点,则称M是二部图G的完美匹配；如果G中没有另外的匹配M0,使|M0|＞|M|,则称M是二部图G的最大匹配.在二部赋权图G=(X,Y,E,w)中,权值最大的最大匹配M称为二部赋权图G的最佳匹配.68设G=(X,Y,E)为二部图,且ME.若M中69工作安排问题之一

给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.n个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作.问题：对所有的工作人员能不能都分配一件他所能胜任的工作？

构造一个二部图G=(X,Y,E),X={x1,x2,…,xn},Y={y1,y2,…,yn},(xi,yj)

E

人员xi胜任工作yj.问题转化为求二部图的一个完美匹配.因为

|X|=|Y|,所以完美匹配即为最大匹配.69工作安排问题之一给n个工作人员x1,x2,70工作安排问题之二(指派问题)

给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高.构造一个二部赋权图G=(X,Y,E,c),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},cij为工作人员xi胜任工作yj时的工作效率.

则问题转化为：求二部赋权图G的最佳匹配.求G

的最佳匹配,总可假设G为完备二部赋权图.若xi与yj不相邻,可令cij=0.若人员数与工作数不等，可虚设点x或y使|X|=|Y|.70工作安排问题之二(指派问题)给n个工作人员x171指派问题的数学模型及其特点(AssignmentPr.)特点：若从效率矩阵(cij)nxn的一行(列)各元素中分别减去该行(列)的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解.对同一项工作，同时提高或降低每人相同的效率，不影响其最优指派。人员i能否完成工作j人员i只能完成一项工作工作j只能由一个人完成总的工作时间最少71指派问题的数学模型及其特点(AssignmentPr72指派问题的解法——匈牙利法(D.Konig)匈牙利法的基本思想：可以让每行或每列减去一个数后，出现尽可能多的0元素，然后，再给费用为0元素的相应变量指派为1，以使变换后的目标函数为0，从而达到最优。从效率矩阵的一行(列)各元素中分别减去该行(列)的最小元素，不改变原指派问题的最优解.72指派问题的解法——匈牙利法(D.Konig)匈牙利法的基最小覆盖与最大独立集设G=(V,E),称点子集SV是一个覆盖,若E中的每条边都至少有一个顶点在S中.所有覆盖中顶点数最少的称为最小覆盖.最小覆盖的顶点数称为最小覆盖数.73定理:二部图的最小覆盖数=最大匹配数.设G=(V,E),称点子集TV

是一个独立集,若T中的任意两点不相邻.所有独立集中顶点数最多的称为最大独立集.最大独立集的顶点数称为最大独立集.定理:设S是G的一个覆盖，则T=V

S是G的一个独立集.对一般图都是NP-C问题，对二分图与最大匹配问题等价.最小覆盖与最大独立集设G=(V,E),称点子集S例题1

PlacetheRobots（ZOJ1654）问题描述有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。74WallGrassEmpty例题1PlacetheRobots（ZOJ1654）模型一755467832112346578问题转化为求图的最大独立集问题。在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。机器人要放在不相邻的顶点上。模型一755467832112346578问题转化为求图的最例题1

PlacetheRobots（ZOJ）模型一765467832112346578我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：这是NP-C问题！问题转化为求图的最大独立集问题。机器人要放在不相邻的顶点上。例题1PlacetheRobots（ZOJ）模型一7模型二77我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。123451234机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。模型二77我们将每一行，每一列被墙隔开，且包含空地的连续区域例题1

PlacetheRobots（ZOJ）模型二78123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部图：112233445例题1PlacetheRobots（ZOJ）模型二7例题1

PlacetheRobots（ZOJ）模型二79由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以机器人要放在不相邻的边上。123412354112233445问题转化为二部图的最大匹配问题。这是P类问题！例题1PlacetheRobots（ZOJ）模型二7例题1

PlacetheRobots（ZOJ）小结80模型一过于简单，没有给问题的求解带来任何便利；模型二则抓住了问题的内在联系，巧妙地建立了二部图。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。例题1PlacetheRobots（ZOJ）小结80例题2

打猎猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光所有的鸟？建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。该二分图最大匹配数既是最少要打的枪数。81例题2打猎猎人要在n*n的格子里打鸟,他可以在某一行中打例题3

救护伤员（TOJ1148）无情的海啸夺取了无数人的生命.很多的医疗队被派往灾区拯救伤员.就在此时,医疗队突然发现自己带的药品已经不够用了,只剩下了N种。(1<n<=20)，随着病人病情的发展，每种药在每天能获得的效果是不一样的。同时，每天病人只能服用一种药。也就是说，这些药还够支持N天。现在，给出你每种药在每天使用的效果，请你判断当每种药都用完后所有药达到的效果之和最大可以是多少。例题3救护伤员（TOJ1148）无情的海啸夺取了无数人的例题4

最小路径覆盖一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。理清一个关系：最小路径覆盖数＝G的定点数－最小路径覆盖中的边数例题4最小路径覆盖一个不含圈的有向图G中，G的一个路径覆盖例题4

最小路径覆盖试想我们应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。例题4最小路径覆盖试想我们应该使得最小路径覆盖中的边数尽量例题4

最小路径覆盖因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。例题4最小路径覆盖因此，所转化出的二分图的最大匹配数则是原86组合优化问题最短路问题最小支撑树问题指派问题最大流最小割问题几个典型的图论问题图论的基本概念最小费用流问题设备更新问题选址问题二部图的最佳匹配问题七桥问题邮路问题破圈法避圈法86组合优化问题最短路问题最小支撑树问题指派问题最大流最小割87给一个有向图D＝(V,A)，指定两个点，一个称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。

对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij≥0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D＝(V,A,C)。最大流问题(MaximumFlow)351142352vsv2v1v3v4vt在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统有信息流87给一个有向图D＝(V,A)，最大流问题(Max88网络上的流：定义在弧集A上的函数f={f(vi,vj)},并称f(vi,vj)为弧上的流量，简记为fij。可行流的流量:3,15,21,01,04,12,23,15,22,1vsv2v1v3v4vt容量限制：对每一边上都有平衡条件：中间点：流入量等于流出量;

发收点：发出流量等于汇入流量.可行流使流量达到最大的可行流称为最大流.88网络上的流：定义在弧集A上的函数f={f(vi,vj)}89对于可行流f＝{fij}，我们把网络中使fij＝cij的弧称为饱和弧，使fij<cij的弧称为非饱和弧；把使fij＝0的弧称为零弧，使fij>0的弧称为非零弧.增广链

P是从vs到vt的一条链，满足前向弧

fij<

cij,后向弧fij>0。3,15,21,01,04,12,23,15,22,1vsv2v1v3v4vt若P是联结发点vs和收点vt的一条链，规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。一个可行流是最大流

不存在增广链。89对于可行流f＝{fij}，我们把网络中使fij＝cij的90求最大流的标号法思想：从可行流出发，经过标号并检查的过程,得到从vs到vt的增广链;再调整增广链的流量,得到新的可行流.重复直到无增广链时得到最大流.(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(-,+∞)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4(vs,3)(-,+∞)检查vi：对未标号vj；非饱和(vi,vj)，vj标(vi,min[l(vi),cij-fij]),

非零弧(vj,vi)，vj标号(-vi,min[l(vi),fji])调整：在增广链上,前向弧流量增l(vt)，后向弧流量减l(vt).90求最大流的标号法思想：从可行流出发，经过标号并检查的过程91该算法是否一定在有限步内终止呢？如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流

Ford-Fulkerson标号算法标号算法终止时，网络中一定不再含有增广路.

如果所有弧上的容量都是正整数，根据整流定理，最大流v也是整数.实际上，由于割[{s}，V\{s}]中前向弧的条数最多为n条，因此最大流v的上界为nU（U表示网络中弧上的最大容量）.由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过v次，算法一定在有限步内终止.此外，由于每次增广最多需要对所有弧检查一遍，因此算法的复杂度为O（mv），或表示为O（mnU）.

伪多项式时间算法，而不是多项式时间算法.

91该算法是否一定在有限步内终止呢？Ford-Fulkers92Ford-Fulkerson标号算法每次随便找一条增广路进行增广最大容量增广路算法:每次都找一条增广容量最大的增广路进行增广最短增广路算法:每次都找一条包含弧数最少的增广路对于这时特殊的最短路问题,可以采用从节点s或t开始的广度优先搜索方法,则在O(m)内找到一条最短增广路，因此最短增广路算法的复杂度为O(m2n).

从目前已有的理论分析和计算经验来看，最短增广路算法是所有增广路算法中效果最好的算法，可以设计出在O(logn)的平均时间内找到一条最短增广路，即算法复杂度为O(mnlogn)

最短增广路算法最短增广路算法最多经过O(mn)次增广后终止.92Ford-Fulkerson标号算法每次随便找一条增广路93若去掉某一割集的弧，则从vs到vt便不存在路.所以，割集是从vs到vt的必经之路。割集的容量：给定容量网络D=(V,E,C)，如果点集V被剖分成,使得弧集满足：①不连通；②为的真子集，而仍连通，则称为G的割集。(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4(vs,3)(-,+∞)最大流最小割定理：最大流的流量=最小割集的容量vt最小割集93若去掉某一割集的弧，则从vs到vt便不存在路.所以，割集94二部图中最大匹配问题可转化为最大流问题。在二部图中增加两个新点vs,vt分别作为发点，收点。并用有向边把它们与原二部图中顶点相连，令全部边上的容量均为1。当网络流达到最大时，如果(xi,yj)上的流量为1，就让xi做工作yj，此即为最大匹配方案。94二部图中最大匹配问题可转化为最大流问题。例一赛车问题

阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比