在了解增广拉格朗日乘子法之前，先了解一下拉格朗日乘子法和罚函数。拉格朗日乘子法基本的拉格朗日乘子法(又称为拉格朗日乘数法)，就是求函数f(x1,x2,...)在约束条件下极值的方法。其主要思想是引入一个新的参数λ(即拉格朗日乘子)，将约束条件函数与原函数联系到一起，使能配成与变量数量相等的等式方程，从而求出得到原函数极值的各个变量的解。假设目标函数为，约束条件为其中l表示有l个约束条件。在这里我们举一个例子进行理解。假设有一个方程为的椭球，我们要求这个椭球内接长方体的最大体积。那么也就是说我们要在的条件下，求的最大值。现在我们定义一个拉格朗日函数：其中是各个约束条件的待定系数。接下来求偏导为0

目录(1)定义:(2)结论:(3)证明:(4)例题:看了往上诸多博客,感觉讲的稍有欠缺,于是自己写了一篇(耐心浏览)最小点覆盖:(1)定义:假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。(2)结论:最小点覆盖=最大匹配数(3)证明:先了解一些概念匹配点:匹配边两端的端点增广路径,即:一边的非匹配点到另一边的非匹配点的一条非匹配边和匹配边交替经过的路径.(开头和结尾一定是非匹配点且不在一个集合中)如图绿色的线就是增广路径: 然后简单说一下匈牙利算法:(1)找出一条增广路，通过将增广路取反，得到新的M’来代替原M，新的匹配数相对于原匹配数多1(2)重复

目录(1)定义:(2)结论:(3)证明:(4)例题:看了往上诸多博客,感觉讲的稍有欠缺,于是自己写了一篇(耐心浏览)最小点覆盖:(1)定义:假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。(2)结论:最小点覆盖=最大匹配数(3)证明:先了解一些概念匹配点:匹配边两端的端点增广路径,即:一边的非匹配点到另一边的非匹配点的一条非匹配边和匹配边交替经过的路径.(开头和结尾一定是非匹配点且不在一个集合中)如图绿色的线就是增广路径: 然后简单说一下匈牙利算法:(1)找出一条增广路，通过将增广路取反，得到新的M’来代替原M，新的匹配数相对于原匹配数多1(2)重复