差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:2sozx:数学:知识点 [2020/06/12 20:48]
2sozx [证明]
+++ 2020-2021:teams:farmer_john:2sozx:数学:知识点 [2020/06/12 22:13] (当前版本)
2sozx [NOI2012骑行川藏]
@@ 行 32: / 行 32: @@
 将 $\left(4\right),\left(5\right)$ 写成分量形式再加上约束条件即可证明。
 =====拉格朗日乘子法=====
-构造函数 $F(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_m)=f(\mathbf{x})+\sum_{j=1}^m \lambda_j\varphi_j(\mathbf{x})$ ，则上述求条件极值点的必要条件形式转化为 $F$ 的通常极值的必要条件 $$\begin{cases}\frac{\partial{F(\mathbf{x_0})}}{\partial{x_i}}=0\quad(i=1,2,\cdots,n)\\ \frac{\partial{F(\mathbf{x_0})}}{\partial{\lambda_j}}=0\quad(j=1,2,\cdots,m)\end{cases}$$
+构造函数 $F(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_m)=f(\boldsymbol{x})+\sum_{j=1}^m \lambda_j\varphi_j(\boldsymbol{x})$ ，则上述求条件极值点的必要条件形式转化为 $F$ 的通常极值的必要条件 $$\begin{cases}\frac{\partial{F(\boldsymbol{x_0})}}{\partial{x_i}}=0\quad(i=1,2,\cdots,n)\\ \frac{\partial{F(\boldsymbol{x_0})}}{\partial{\lambda_j}}=0\quad(j=1,2,\cdots,m)\end{cases}$$
 此即拉格朗日乘子法
+=====例题=====
+====CF813C====
+  * 题意：给定整数 $a,b,c,s$ ，求使得 $x^ay^bz^c$ 最大的实数 $x,y,z$ ，其中 $x+y+z\le s(1\le s \le 10^3,0\le a,b,c \le 10^3)$
+  * 题解:对于 $x,y,z > 0$ 时显然取 $x+y+z=s$ 时会比 $x+y+z<s$ 时更优；对于 $xyz=0$ 时取 $x+y+z=s$ 不会比 $x+y+z<s$ 劣。因此可以将限制条件改为 $x+y+z=s$ 即可。令 $G(x,y,z)=x+y+z-s，F(x,y,z)=a\ln x+b\ln y+c\ln z，H(x,y,z)=F(x,y,z)+\lambda G(x,y,z)$ 套用拉格朗日乘子法即可得到 $$x=\frac{as}{a+b+c},y=\frac{bs}{a+b+c},z=\frac{cs}{a+b+c}$$ 注意 $a+b+c=0$ 时需要特判。
+  * 对于所求表达式为乘积的形式时，可以取对数，如上题中 $F(x,y,z)=a\ln x+b\ln y+c\ln z$ ，此时求出的极值点依旧为原表达式的极值点，具体问题需要具体分析。
+  * 一般来说使用拉格朗日乘子法时需要注意边界条件，此题 $x,y,z$ 为边界条件时表达式值一定不会优于最大值，所以可以不考虑边界。注意边界值并不是 $0$。
+====一道没有来源的题目====
+  * 题意：平面上有$n(n{\le}8)$个点，告诉你每个点距离原点的距离,求这$n$个点所围成的凸包的最大面积
+  * 题解：枚举哪些点在凸包上,并且这些点极角排序后的顺序。假设极径依次为$r_1,r_2,⋯,r_n$。\\ 面积$S={\frac{1}{2}}(r_1r_2sinθ_1+r_2r_3sinθ_2+⋯+r_nr_1sinθ_n)$并且${\sum_{i=1}^n}{\theta}_i=2\pi$。\\ 令$F(θ_1,θ_2,⋯,θ_n)=S+{\lambda}g(θ_1,θ_2,⋯,θ_n)$,其中$g(θ_1,θ_2,⋯,θ_n)={\sum_{i=1}^n}{\theta}_i-2\pi$.\\ 由拉格朗日乘子法，解得$−λ=r_1r_2cosθ_1=r_2r_3cosθ_2=⋯=r_nr_1cosθ_n$,可二分$λ$,求出满足$g=0$的解，此时对应的$\theta$就是当前条件下面积的最大值。
+  * 注：其实枚举点在凸包上时这些点并非一定会构成凸包，但是这样的面积一定不会是最大的，对于答案并没有影响。
+  * 这道题是同学出的，并没有具体数据。
+====NOI2012骑行川藏====
+  * 题意：$n$ 段路，每段路有三个参数 $s_i,k_i,v_i'$,其中 $s_i $ ，表示这段路的长度，$k_i$ ，表示这段路的风阻系数，$v_i'$ 表示这段路上的风速。若在一段路上的速度为 $v_i$ ，消耗的能量为 $E_i=k_i(v_i-v_i')^2s_i$。初始有体能值 $E_U$ 问在有限的体力内到达目的地的最短时间是多少。
+  * 题解：显然体能值要尽量用光会更优。若 $v_i<v_i'$ 则取 $V=2v_i'-v_i$ ，两个速度消耗的能量是相同的，而且 $V$ 优于 $v_i$ ，因此我们可以默认一段路的 $v_i\ge v_i'$。题目即求在 $\sum_{i=1}^{n}E_i=E_U$ 的条件下 $T=\sum_{i=1}^{n}\frac{s_i}{v_i}$ 的最小值。套用拉格朗日乘子法可知 $$\lambda=\frac{1}{2k_i v_i (v_i-v_i')^2}$$ 根据假设 $v_i\ge v_i'$ 可知 $\frac{1}{2k_i v_i (v_i-v_i')^2}$ 单调，因此可以通过二分 $\lambda$ 来求解答案。

CVBB ACM Team

用户工具

站点工具

差别

页面工具