Feasible region — 可行域

可行域（Feasible region，或称可行集，feasible set）是在运筹学、最优化和数学建模中，指满足问题所有约束条件的全部可能解（变量值的组合）的集合。

可行域构成了寻找最优解的搜索子空间。任何位于该区域之外的解都是不可行的。

定义与形成

可行域由问题中每个独立约束条件所定义的集合的交集构成。约束条件可以表现为以下形式：

• 不等式： 为变量或其组合的值设定上界或下界（例如，“资源A的消耗量不得超过100个单位”，“产品产量必须不少于50件”）。
• 等式： 要求精确满足某个条件（例如，“总运输量必须等于1000吨”，“流入和流出的平衡为零”）。
• 变量符号条件： 通常要求变量为非负、整数或属于某个特定的离散集。

一个点（或变量值向量）属于可行域，当且仅当它同时满足所有这些约束条件。

几何解释

可行域通常具有直观的几何解释，尤其是在变量数量较少的问题中：

• 在二维空间（2个变量）中： 每个线性不等式约束定义一个半平面。可行域是这些半平面的交集，形成一个凸多边形（可能无界或为空）。
• 在三维空间（3个变量）中： 每个线性不等式约束定义一个半空间。可行域是这些半空间的交集，形成一个凸多面体（polyhedron）。
• 在多维空间中： 由线性约束定义的可行域是一个凸多胞体（polytope）。

对于非线性约束，可行域可能具有更复杂的形状，并且可能不是凸的。

在最优化中的作用

可行域在最优化中扮演着基础性角色：

1. 定义搜索空间： 问题的最优解（如果存在）总是位于可行域内部或其边界上。最优化算法正是在该区域内搜索目标函数的极值。
2. 检验解的存在性： 如果可行域是空集（即约束条件相互矛盾），则问题没有可行解，因此也没有最优解。
3. 对最优解的影响： 可行域的形状和大小直接影响达到目标函数极值的可能性以及该极值的大小。

可行域的性质（在线性规划问题中）

在线性规划（LP）问题中，所有约束条件和目标函数都是线性的，可行域具有以下重要性质：

• 凸性： 如果两个点属于可行域，那么连接这两点的整个线段也属于可行域。该性质保证了最优解（如果存在且唯一）将位于可行域多面体的一个顶点上。
• 闭合性： 可行域包含其边界（由非严格不等式 ≤、≥ 和等式所致）。

可行域可以是：

• 有界（Bounded）： 具有有限的大小。
• 无界（Unbounded）： 在一个或多个方向上无限延伸。
• 空集（Empty）： 不包含任何点。

参考文献

• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
• Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

另见

• 运筹学
• 最优化
• 数学模型
• 约束
• 可行解
• 最优解
• 目标函数
• 线性规划
• 凸集