写在前面的
这个是个好东西啊,好东西啊(神志不清)。这个方法可以非常简单的求出多元函数的条件最值,而且不需要动脑子,会求导就完了。
引入
求 的最小值。其中 。
如果使用柯西不等式就一步。 。
拉格朗日乘数法的大体步骤为。
- 令条件函数,和目标函数。
- 分别对所有变量求出偏导。
- 令偏导为 ,解方程。
- 代入目标函数,得出最值。
但是为了讲解拉格朗日乘数法,我们令 那么定义 。那么 。现在令,所有偏导为零。可以解得方程 。最后检验得到 。
证明,不太会。但是可以感性理解一下,如果希望有完整证明的,可以看这个 。大概就是,在两个函数相切时。在切点处,两个函数的梯度向量是平行的,根据比例列出方程 。 。细心的朋友也行已经发现了,其实拉格朗日乘数法求出的并不是最值,而是两个函数的相切点。但是 中的函数比较平滑,直接乱搞。
例题
NOI2012骑行川藏
分析
比较模板的条件最值。我们先令出目标函数 而条件函数为 。然后就可以对这模板冲就可以了。最后列出的方程组为 。由于可以比较轻松的分析出 的单调性。所以我们考虑二分 来检验 。而 的值,通过单调性也可以二分得到。那么总复杂度为 。
代码
#include<bits/stdc++.h> using namespace std; #define db double const int N = 1e4 + 100; const db eps = 1e-13; int n; db s[N],k[N],v[N],V[N],eU; db solve(db vi,int id,db r) { return (vi * vi * (vi - v[id]) * 2.0 * r * k[id]); } bool check(db m) { db e = 0; for(int i = 1;i <= n;i++) { db l = max(v[i],0.0),r = 1e7; while(l + eps <= r) { db mid = (l + r) / 2.0; if(solve(mid,i,m) <= 1.0) l = mid; else r = mid; } V[i] = l; e += k[i] * (V[i] - v[i]) * (V[i] - v[i]) * s[i]; } // printf("e: %.10f\n",e); return e <= eU; } int main() { scanf("%d%lf",&n,&eU); for(int i = 1;i <= n;i++) scanf("%lf%lf%lf",&s[i],&k[i],&v[i]); double l = 0,r = 1e7; while(l + eps <= r) { db mid = (l + r) / 2.0; if(check(mid)) r = mid; else l = mid; } // printf("%.10f %.10f\n",l,r); db ans = 0; for(int i = 1;i <= n;i++) {ans += s[i] / V[i];} printf("%.9f\n",ans); return 0; }