免费角点计算器

理解线性规划问题

线性规划问题（LPP）是一种约束优化模型，其目标是在一组线性约束下找到最佳结果——最大化或最小化。每个这样的模型包含三个基本组成部分：

• 决策变量：代表我们选择的变量。通常用符号表示，如 $x_1, x_2, \dots$，在处理二维问题时简单表示为 $x$ 和 $y$。
• 目标函数：包含决策变量的线性表达式，我们希望最大化（例如利润）或最小化（例如成本）。
• 约束条件：限制决策变量允许值的线性不等式或等式系统。它们代表现实世界的限制，如资源可用性、生产能力或预算限制。

要成为线性规划模型，必须满足两个条件：(1) 决策变量在指定范围内必须是连续的；(2) 目标函数和每个约束的左侧都必须是线性的。数学形式上，一个典型的两变量LPP可以表示为：

$$\begin{aligned} \text{Maximize (or Minimize)} &\quad P = p_x x + p_y y \\ \text{subject to} &\quad a_1 x + b_1 y \leq c_1 \\ &\quad a_2 x + b_2 y \leq c_2 \\ &\quad \vdots \\ &\quad a_n x + b_n y \leq c_n \\ &\quad x \geq 0,\; y \geq 0 \end{aligned}$$

这里，$p_x$ 和 $p_y$ 是目标函数的系数，$a_i, b_i$ 是约束系数，$c_i$ 是右侧常数。非负条件 $x \geq 0, y \geq 0$ 通常自动包含在内。

可行域与角点

满足所有约束的所有点 $(x, y)$ 的集合称为可行集。在图形上绘制时，所有不等式重叠的区域形成可行域。这个区域可以是有界（封闭多边形）或无界的，但它总是至少有一个角点。

角点——也称为极点——是两个或多个约束的交点。线性规划的一个基本定理表明，如果存在最优解，它必然出现在这些角点中的一个（或多个）上。这一性质是角点法的基础。

代数法寻找角点

一种系统化定位角点的方法是求解由约束导出的方程组。步骤如下：

1. 将每个不等式替换为等式。例如，$2x + 3y \leq 18$ 变为 $2x + 3y = 18$。
2. 任选两个方程并联立求解得到交点。对每对方程重复此操作。
3. 从得到的交点集中，只保留满足所有原始不等式约束的点。这些就是可行域的角点。

考虑以下LPP：

$$\begin{aligned} \text{Maximize } P &= 30x + 40y \\ \text{subject to } &\quad 2x + 3y \leq 18 \\ &\quad x + y \leq 9 \\ &\quad x + 2y \leq 16 \\ &\quad x \geq 0,\; y \geq 0 \end{aligned}$$

将不等式转换为等式得到：

$$2x + 3y = 18,\quad x + y = 9,\quad x + 2y = 16,\quad x = 0,\quad y = 0$$

求解每对方程得到多个交点。例如，解 $2x + 3y = 18$ 和 $x + y = 9$ 得到 $(9, 0)$；解 $x + 2y = 16$ 和 $x = 0$ 得到 $(0, 8)$；等等。应用所有约束后，只保留满足每个不等式的点。在这个例子中，角点是 $(0, 0)$、$(0, 6)$ 和 $(9, 0)$。

你可以使用方程组求解器来加速代数步骤，但筛选仍必须对照原始不等式进行。

图解法寻找角点

对于两变量问题，可视化方法通常更简单。请遵循以下步骤：

1. 将每个约束不等式转换为等式以得到边界线。
2. 在图形上绘制这些线。一种便捷的方法是计算 x 轴截距（设 $y = 0$）和 y 轴截距（设 $x = 0$）。
3. 阴影化满足所有不等式的区域。阴影区域的交集就是可行域。
4. 确定该区域的顶点——这些就是角点。

对于之前使用的同一LPP，绘制线 $2x + 3y = 18$、$x + y = 9$ 和 $x + 2y = 16$ 以及坐标轴，产生一个顶点为 $(0,0)$、$(0,6)$ 和 $(9,0)$ 的可行域。这些就是将在下一步中评估的角点。

确定最优解

一旦知道角点，计算每个点处目标函数的值。最大值表明最大化（如果问题是最大化问题），最小值表明最小化（如果是最小化问题）。如果目标是最大化，则给出最大函数值的角点是最优解。

继续该示例：

角点	$P = 30x + 40y$
$(0, 0)$	$0$
$(0, 6)$	$240$
$(9, 0)$	$270$ (最大值)

因此，最优解出现在 $(9, 0)$，最大值为 270。

有可能——尽管不太常见——两个不同的角点产生相同的最优值。在这种情况下，它们之间的整个线段也是最优的。

如何使用角点计算器

这款在线LP求解器使整个过程变得简单。它最多处理五个约束和两个决策变量。使用方法如下：

1. 输入目标函数的系数 $p_x$ 和 $p_y$。
2. 选择要最大化还是最小化。
3. 选择约束数量（最多 5 个）。
4. 对于每个约束，输入系数 $a$、$b$ 和常数项 $c$。
5. 计算器将生成完整的角点表格并高亮显示最优解。

要添加非负约束 $x \geq 0$ 或 $y \geq 0$，将相应系数设置为 $1$ 和 $0$，常数设为 $0$，并选择 $\geq$ 符号。例如，要强制 $x \geq 0$，输入 $a = 1$、$b = 0$、$c = 0$ 且符号为 $\geq$。

如果工具返回无角点，则意味着问题不可行——约束条件无法同时满足。考虑放宽一些约束以形成可行域。

角点计算器既是一个实用的线性规划计算器，也是一个可行域计算器和优化计算器，集于一体。通过自动化角点法，它将繁琐的手动过程转变为快速可靠的任务。