MO学习笔记——解析几何中的线性规划问题

k_Sword · 2024-12-03 23:10:57 · 个人记录

前情提要：我没脑子。

1.什么是线性规划

虽然都叫规划，但其实这东西跟 dp 没什么关系。

线性规划有以下几个要素：

一、两个变量（通常非负）

二、一个需要极大化/极小化的二元函数

三、几个线性约束条件

这么说很抽象，直接看书上例题：

已知 x,y 满足
\left\{ \begin{aligned} 2x+y-2\leq 0 & \\ x-2y+4\geq 0 & \\ 3x-y-3\leq 0 & \end{aligned} \right.

（1）求 x+y 的最大值

（2）求 x-y 的最大值

（3）求 x^2+y^2 的最小值

（4）求 \dfrac{y}{x-1}(x\neq 1) 的取值范围

这个问题显然不能直接导。我们需要一些新的方法来解决这类问题。

看到二元一次不难想到直线，因此我们使用解析几何来解决。

我们知道一个二元一次方程可以描述一条直线，那么二元一次不等式呢？

我们考虑把直线方程写成更为直观的形式：y=kx+b

那么对于同一个 x， y\leq kx+b 的 y 要在给定直线的下方，也就是说，y\leq kx+b 描述的就是平面处于直线下方的部分，说人话就是半平面。

而对于多个这样的不等式，其限制的部分就是半平面交。

接下来，既然我们已经找出了限制的几何意义，不妨把所求的函数也用几何来表示。

比方说，对于例题的问题（1），我们考虑构造直线 z=x+y

我们知道，对于这样一个直线方程，z 增大的过程就是直线上移的过程。因此，我们考虑将构造的直线不断上移，直至和限制的半平面交只有一个公共点。不难发现答案为 5

问题（2）可以用同样的方式解决。

接下来考虑问题（3），我们知道 x^2+y^2=z 是一个圆。其中 z 表示半径的平方。不难发现 z_{min} 即为以原点为圆心的与半平面交有公共点的最小圆的半径平方。

注意到这时这个圆必然与限制直线中的 2x+y-2=0 相切，答案即为 \dfrac{4}{5}

考虑问题（4），我们构造直线 y=k(x-1)，所要求的即为这个直线的斜率的范围。考虑从该直线必过点 (1,0) 作直线，极限情况即为过半平面交两个边界点的情况。答案为 (-\infty,-2]\cup [3,+\infty)

于是，解决这类问题的一般步骤可以总结为：

众所周知题是会变化的，所以我们来道练习题。

已知 x,y 满足
\left\{ \begin{aligned} x+y-6\leq 0 & \\ 2x-y-1\leq 0 & \\ 3x-y-2\geq 0 & \end{aligned} \right.
若 z=ax+y 的最大值为 2a+4，最小值为 a+1 ，求 a 的取值范围。

这题变化在于给定了极值求参数。实际上思路是一样的。

先按不等式限制作出半平面交。我们知道极值一定在某个点上取到，按题意，极大值的点是 (2,4)，极小值的点是 (1,1)。

因此，我们考虑对所要求的 a，也就是斜率分类讨论。

若 a=0，由于这两个边界点分别是 y 最大和最小的，所以有解。

若 a<0，由于需要保证 (2,4) 是最优点，因此斜率必须 \geq 2，否则最优点就不是 (2,4)

若 a>0，同理得到斜率必须 \leq 1

答案即为 [-2,1]