写在前面的

这个是个好东西啊,好东西啊(神志不清)。这个方法可以非常简单的求出多元函数的条件最值,而且不需要动脑子,会求导就完了。

引入

的最小值。其中

  • 如果使用柯西不等式就一步。

  • 拉格朗日乘数法的大体步骤为。

    • 令条件函数,和目标函数。
    • 分别对所有变量求出偏导。
    • 令偏导为 ,解方程。
    • 代入目标函数,得出最值。
  • 但是为了讲解拉格朗日乘数法,我们令 那么定义 。那么 。现在令,所有偏导为零。可以解得方程 。最后检验得到

  • 证明,不太会。但是可以感性理解一下,如果希望有完整证明的,可以看这个 。大概就是,在两个函数相切时。在切点处,两个函数的梯度向量是平行的,根据比例列出方程 。 。细心的朋友也行已经发现了,其实拉格朗日乘数法求出的并不是最值,而是两个函数的相切点。但是 中的函数比较平滑,直接乱搞。

    例题

    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;
    }