# 可行域 (Feasible Region)
可行域 (Feasible Region)，也被称为 可行集 (Feasible Set)，是{{{优化理论}}}和{{{运筹学}}}中的一个基本概念。它指的是在一个数学{{{优化问题}}}中，由所有{{{约束}}}条件所定义的一组解的集合。换言之，可行域包含了所有满足问题给定限制条件的可能解。
一个典型的优化问题旨在寻找一个能使{{{目标函数}}}达到最大值或最小值的解，而这个解必须来自于可行域。因此，可行域构成了我们寻找最优解的“搜索空间”。如果一个问题没有满足所有约束的解，那么其可行域为空，该问题被称为{{{不可行问题}}} (Infeasible Problem)。
## 形式化定义
一个标准的优化问题可以表示为以下形式：
最大化 或 最小化: $$ f(x_1, x_2, \ldots, x_n) $$
约束于 (Subject to): $$ g_i(x_1, x_2, \ldots, x_n) \le b_i, \quad i = 1, \ldots, m \quad (\text{不等式约束}) $$ $$ h_j(x_1, x_2, \ldots, x_n) = c_j, \quad j = 1, \ldots, p \quad (\text{等式约束}) $$
在这里： * $x = (x_1, x_2, \ldots, x_n)$ 是一个包含 $n$ 个{{{决策变量}}}的向量。 * $f(x)$ 是需要被优化的{{{目标函数}}} (Objective Function)。 * $g_i(x) \le b_i$ 和 $h_j(x) = c_j$ 是定义问题边界的{{{约束}}} (Constraints)。
可行域 $S$ 就是满足所有这些约束的决策变量向量 $x$ 的集合： $$ S = \{ x \in \mathbb{R}^n \mid g_i(x) \le b_i, \forall i=1, \ldots, m; \quad h_j(x) = c_j, \forall j=1, \ldots, p \} $$
任何一个点 $x \in S$ 都被称为一个可行解 (Feasible Solution)。优化算法的目标就是在集合 $S$ 中找到一个点 $x^*$，使得 $f(x^*)$ 的值是所有可行解中最大或最小的。
## 可行域的性质
可行域的几何与拓扑性质对于理解和解决优化问题至关重要。
1. {{{凸性}}} (Convexity) 一个集合如果其中任意两点的连线段上的所有点都仍然在该集合内，则称该集合为{{{凸集}}} (Convex Set)。在{{{线性规划}}} (Linear Programming) 问题中，由于所有约束都是线性的，其可行域是由多个{{{半平面}}}或{{{半空间}}}的交集构成的，因此它总是一个凸多面体（或更一般地，一个{{{凸集}}}）。这一性质是线性规划理论的基石，因为它保证了如果存在最优解，那么至少有一个最优解位于可行域的{{{顶点}}}（角点）上。在{{{非线性规划}}} (Nonlinear Programming) 中，可行域不一定是凸的，这使得问题求解变得更加复杂。
2. 闭合性与有界性 (Closedness and Boundedness) * {{{闭集}}} (Closed Set): 如果一个可行域包含了它所有的边界点（例如，约束条件是 $\le$ 或 $\ge$ 而不是 $<$ 或 $>$），那么它是一个闭集。大多数优化问题中的可行域都是闭集。 * {{{有界集}}} (Bounded Set): 如果可行域可以被一个有限大小的“盒子”或球体完全包含，那么它是有界的。 * {{{紧集}}} (Compact Set): 如果可行域既是闭集也是有界集，则称其为紧集。根据{{{魏尔斯特拉斯极值定理}}} (Weierstrass Extreme Value Theorem)，一个定义在非空紧集上的连续目标函数，必然在该集合上能够取得其最大值和最小值。这保证了对于许多优化问题，最优解是存在的。
3. 连通性 (Connectedness) 一个连通的可行域意味着域内的任意两点都可以通过一条完全位于域内的路径连接起来。如果可行域不是连通的，它可能由多个分离的“岛屿”组成，这会增加寻找全局最优解的难度，因为算法可能会陷入一个局部最优解所在的区域。
## 示例：二维线性规划中的可行域
为了直观地理解可行域，我们考虑一个简单的二维{{{线性规划}}}问题。
最大化: $$ Z = 4x + 5y $$
约束于: 1. $x + 2y \le 10$ 2. $3x + y \le 9$ 3. $x \ge 0$ 4. $y \ge 0$
这里的决策变量是 $x$ 和 $y$。$x \ge 0$ 和 $y \ge 0$ 是非负约束，它们将可行域限制在笛卡尔坐标系的第一象限。
构建可行域的步骤：
1. 绘制约束边界线：将每个不等式约束视为等式，绘制对应的直线。 * $x + 2y = 10$ * $3x + y = 9$ * $x = 0$ (即 Y 轴) * $y = 0$ (即 X 轴)
2. 确定每个约束的有效区域：对于每个不等式，确定它所代表的平面区域。通常可以通过测试原点 $(0,0)$ 来判断。 * 对于 $x + 2y \le 10$，代入 $(0,0)$ 得到 $0 \le 10$，成立。所以该约束的有效区域是包含原点的一侧。 * 对于 $3x + y \le 9$，代入 $(0,0)$ 得到 $0 \le 9$，成立。所以该约束的有效区域也是包含原点的一侧。
3. 找到交集：可行域是所有这些有效区域的共同交集。在这个例子中，它是一个由四个顶点构成的封闭多边形。
4. 确定顶点 (角点)：可行域的顶点是约束边界线的交点。 * A: $(0, 0)$ （$x=0$ 和 $y=0$ 的交点） * B: $(3, 0)$ （$y=0$ 和 $3x + y = 9$ 的交点） * C: $(1.6, 4.2)$ （$x + 2y = 10$ 和 $3x + y = 9$ 的交点） * D: $(0, 5)$ （$x=0$ 和 $x + 2y = 10$ 的交点）
这个由点 A, B, C, D 围成的多边形区域，包括其边界和内部，就是这个问题的可行域。
## 在优化中的重要性
* 解的存在性：可行域的性质（如是否为空集、是否为紧集）直接关系到问题是否存在最优解。 * 算法选择：可行域的结构（如凸性、线性）决定了哪种{{{优化算法}}}（如{{{单纯形法}}}、{{{内点法}}}、梯度下降法）更有效。 * 最优解的位置：对于线性规划，基本定理指出，如果存在最优解，则必然可以在可行域的某个{{{顶点}}}上找到。这极大地缩小了搜索范围，我们只需检查有限个顶点，而不是无限个可行点。对于非线性问题，最优解可能位于可行域的内部或边界上的任何一点。