专栏文章

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

kk_Sword
个人记录参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqw2j7m
此快照首次捕获于
2025/12/04 11:41
3 个月前
此快照最后确认于
2025/12/04 11:41
3 个月前
查看原文
前情提要：我没脑子。

1.什么是线性规划

虽然都叫规划，但其实这东西跟 dp 没什么关系。
线性规划有以下几个要素：
一、两个变量（通常非负）
二、一个需要极大化/极小化的二元函数
三、几个线性约束条件
这么说很抽象，直接看书上例题：
已知 x,yx,y 满足
{2x+y−2≤0x−2y+4≥03x−y−3≤0 \left\{ \begin{aligned} 2x+y-2\leq 0 & \\ x-2y+4\geq 0 & \\ 3x-y-3\leq 0 & \end{aligned} \right.
（1）求 x+yx+y 的最大值
（2）求 x−yx-y 的最大值
（3）求 x2+y2x^2+y^2 的最小值
（4）求 yx−1(x≠1)\dfrac{y}{x-1}(x\neq 1) 的取值范围
这个问题显然不能直接导。我们需要一些新的方法来解决这类问题。
看到二元一次不难想到直线，因此我们使用解析几何来解决。

2.解决线性规划问题的一般步骤

我们知道一个二元一次方程可以描述一条直线，那么二元一次不等式呢？
我们考虑把直线方程写成更为直观的形式：y=kx+by=kx+b
那么对于同一个 xx， y≤kx+by\leq kx+b 的 yy 要在给定直线的下方，也就是说，y≤kx+by\leq kx+b 描述的就是平面处于直线下方的部分，说人话就是半平面。
而对于多个这样的不等式，其限制的部分就是半平面交。
接下来，既然我们已经找出了限制的几何意义，不妨把所求的函数也用几何来表示。
比方说，对于例题的问题（1），我们考虑构造直线 z=x+yz=x+y
我们知道，对于这样一个直线方程，zz 增大的过程就是直线上移的过程。因此，我们考虑将构造的直线不断上移，直至和限制的半平面交只有一个公共点。不难发现答案为 55
问题（2）可以用同样的方式解决。
接下来考虑问题（3），我们知道 x2+y2=zx^2+y^2=z 是一个圆。其中 zz 表示半径的平方。不难发现 zminz_{min} 即为以原点为圆心的与半平面交有公共点的最小圆的半径平方。
注意到这时这个圆必然与限制直线中的 2x+y−2=02x+y-2=0 相切，答案即为 45\dfrac{4}{5}
考虑问题（4），我们构造直线 y=k(x−1)y=k(x-1)，所要求的即为这个直线的斜率的范围。考虑从该直线必过点 (1,0)(1,0) 作直线，极限情况即为过半平面交两个边界点的情况。答案为 (−∞,−2]∪[3,+∞)(-\infty,-2]\cup [3,+\infty)
于是，解决这类问题的一般步骤可以总结为：

一、在坐标系中作出限制的半平面交

二、作出所求函数

三、通过位移变换求解

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

3.小清新练习题

已知 x,yx,y 满足
{x+y−6≤02x−y−1≤03x−y−2≥0 \left\{ \begin{aligned} x+y-6\leq 0 & \\ 2x-y-1\leq 0 & \\ 3x-y-2\geq 0 & \end{aligned} \right.
若 z=ax+yz=ax+y 的最大值为 2a+42a+4，最小值为 a+1a+1 ，求 aa 的取值范围。
这题变化在于给定了极值求参数。实际上思路是一样的。
先按不等式限制作出半平面交。我们知道极值一定在某个点上取到，按题意，极大值的点是 (2,4)(2,4)，极小值的点是 (1,1)(1,1)。
因此，我们考虑对所要求的 aa，也就是斜率分类讨论。
若 a=0a=0，由于这两个边界点分别是 yy 最大和最小的，所以有解。
若 a<0a<0，由于需要保证 (2,4)(2,4) 是最优点，因此斜率必须 ≥2\geq 2，否则最优点就不是 (2,4)(2,4)
若 a>0a>0，同理得到斜率必须 ≤1\leq 1
答案即为 [−2,1][-2,1]

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...