The Cassowary linear arithmetic constraint solving algorithm

一、约束层次

Cassowary 引入了约束层次的概念，将约束分成不同的强度：

required：必须满足的约束；
strong、medium、weak：不同强度的偏好约束。

通过加权求和比较器（weighted-sum-better comparator），系统可以在满足所有required约束的前提下，优先满足强度更高的约束。每个约束的偏差用误差变量表示，目标是最小化加权误差和。

二、单纯形法

单纯形法（Simplex Method）是线性规划领域的经典数值求解算法，核心用于求解线性目标函数在线性等式/不等式约束下的最优解（最大值或最小值），也是 Cassowary 算法实现的核心基础。

该算法是一种迭代式的搜索算法，核心思想是从线性规划问题的可行域（满足所有约束条件的解的集合，为凸多面体）的一个 顶点（极点） 出发，通过 枢轴运算（Pivoting） 不断迭代移动到相邻的、使目标函数值更优的顶点，直到找到最优顶点（线性规划的最优解必出现在可行域的顶点上），或判定问题无界/无解。

1. 核心适用场景

仅适用于线性规划问题，需满足两个核心条件：

目标函数是线性的（如 $\min z=a_1x_1+a_2x_2+\cdots+a_nx_n$ ）；
约束条件由线性等式/线性不等式组成（如 $a_1x_1+a_2x_2\leq b,xi\geq 0$ ）。

这与 Cassowary 算法处理的用户界面线性算术约束高度契合，也是其被选为 Cassowary 底层基础的关键原因。

2. 基本求解步骤

线性规划问题需先转化为标准型（约束为等式、变量非负、目标函数求最小/最大值），再执行迭代，核心分为两大阶段：

第一阶段：寻找初始可行顶点

若原问题无明显的可行顶点，通过引入人工变量构造辅助线性规划问题，求解得到原问题的初始可行解（可行域顶点），若辅助问题无解，则原问题无可行解。
第二阶段：迭代寻找最优解

从初始可行顶点出发，通过检验数判断当前顶点是否为最优解：
- 若检验数均满足最优性条件（如求最小值时检验数 $\geq$ 0），当前顶点即为最优解；
- 若不满足，选择进基变量（使目标函数更优的非基变量）和出基变量（保证迭代后解仍可行的基变量），通过枢轴变换得到新的可行顶点，重复检验与迭代，直至找到最优解。

3. 什么是标准型

标准型有四个硬性条件：

目标函数：统一为求最小值（也可定义为求最大值，行业无绝对统一，Cassowary 算法均为最小化误差目标函数）
约束条件：全部为等式约束（无 $\leq$ 、 $\geq$ ，只有 $=$ ）
变量取值：所有决策变量非负（ $x_i\geq0$ ，无自由变量、无负取值）
等式右侧：所有约束等式的常数项非负（ $b_i\geq0$ ，不能为负数）

即标准型满足以下形式：

\begin{align} & \min z = c_1x_1+c_2x_2+\cdots+c_nx_n \\ s.t. & \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} \\ & x_1,x_2,\cdots,x_n \geq 0,b_1,b_2,\cdots,b_m \geq 0 \end{align}

如何将任意线性规划问题转换为标准型：

目标函数统一为求最小：若原目标是求最大值 $\max z=\sum c_ix_i$ ，则等价于 $\min z'=-\sum c_ix_i$ （求解后还原： $z=-z'$ ）
约束常数项非负：若某约束等式/不等式右侧 $b_i<0$ ，则两边同时乘以-1（注意：乘-1后，不等式符号要反向，如 $≤$ 变 $≥$ 、 $≥$ 变 $≤$ ）
不等式约束转等式约束：核心引入松弛变量/剩余变量（Cassowary算法中核心复用该操作，对应论文中的slack variable），规则：
- 对于 $≤$ 型约束： $a_1x_1+a_2x_2≤b$ →加松弛变量 $s$ （ $s≥0$ ），变为 $a_1x_1+a_2x_2+s=b$
- 对于 $≥$ 型约束： $a_1x_1+a_2x_2\geq b$ →减剩余变量 $s$ （ $s≥0$ ），变为 $a_1x_1+a_2x_2-s=b$
  
  （松弛/剩余变量仅起补全等式作用，目标函数中系数为0，不影响目标函数值）
决策变量非负化：
- 若变量 $x≥0$ ：无需处理
- 若变量 $x≤0$ ：令 $x\prime=−x$ ，则 $x\prime≥0$ ，代入模型替换所有 $x$ ；
- 若变量 $x$ 无约束（自由变量，Cassowary算法中界面坐标变量常为自由变量）：令 $x=x_1−x_2(x_1,x_2≥0)$ ，代入模型替换。

4. 人工变量

人工变量是为构造单纯形法的初始可行基，在标准型线性规划的等式约束中人为引入的非负辅助变量，记为 $a_i$ （满足 $a_i \ge 0$ ）。该变量无任何实际物理意义，仅作为单纯形法迭代的桥梁，求解完成后需强制令其取值为0；若迭代后人工变量无法取0，说明原线性规划问题无可行解。

之所以要引入人工变量，是因为单纯形法的迭代必须从初始可行基开始，而基变量的核心要求是：每个等式约束中存在且仅存在一个基变量，该变量仅在本约束中系数为1，在其他所有约束中系数为0（即基变量的系数构成单位矩阵）。

人工变量的引入，仅针对无天然基变量的等式约束，分两类场景：

原问题为 $≥$ 型不等式约束，转标准型时减剩余变量后，无天然基变量；
原问题本身就是等式约束，且决策变量无法构成单位矩阵，无天然基变量。

而 $≤$ 型不等式约束转标准型时加的松弛变量，天然满足“仅在本约束系数为1、其余为0”，可直接作为基变量，无需引入人工变量——这也是Cassowary算法中UI布局约束（多为 $≤$ 型）极少引入人工变量的原因。

那么如何引入人工变量呢？

引入人工变量，首先要将线性规划问题需先转换为标准型，再对无天然基变量的等式约束引入人工变量，规则为3条：

对无天然基变量的等式约束 $a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n = b_i$ ，在等式左侧直接添加人工变量 $a_i$ ，变为 $a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n + a_i = b_i$ ；
人工变量的取值必须满足非负约束，即 $a_i \ge 0$ ；
人工变量需加入目标函数，且系数为罚数 $+M$ （ $M$ 为充分大的正数，工程中可取1000、10000等）——目的是让算法惩罚人工变量的非零取值：若人工变量 $a_i>0$ ，目标函数值会趋近于正无穷，单纯形法会自然迭代至 $a_i=0$ ，若无法实现则判定原问题无解。

举个例子：

要求最小化两个界面元素的坐标和，同时满足“元素1在元素2左侧”“两元素坐标和不小于8”，决策变量为元素1右侧坐标 $x_1$ 、元素2左侧坐标 $x_2$ （均为像素，非负），数学模型为：

$\min \ z = x_1 + x_2$

$\text{s.t.} \ \begin{cases} x_1 - x_2 \le 0 \\ x_1 + x_2 \ge 8\\ x_1, x_2 \ge 0\end{cases}$

步骤1：将原问题转换为线性规划标准型

目标函数：已为求最小，无需处理；
$≤$ 型约束转等式： $x_1 - x_2 \le 0$ 加松弛变量 $s_1 \ge 0$ ，变为 $x_1 - x_2 + s_1 = 0$ （ $s_1$ 为天然基变量）；
$≥$ 型约束转等式： $x_1 + x_2 \ge 8$ 减剩余变量 $s_2 \ge 0$ ，变为 $x_1 + x_2 - s_2 = 8$ （无天然基变量）；
变量与约束右侧：均满足非负/非负要求，无需处理。

标准型为：

$\min \ z = x_1 + x_2 + 0·s_1 + 0·s_2$

$\text{s.t.} \ \begin{cases} x_1 - x_2 + s_1 = 0 \\ x_1 + x_2 - s_2 = 8 \\ x_1, x_2, s_1, s_2 \ge 0 \end{cases}$

步骤2：对无天然基变量的约束引入人工变量

标准型中第二个约束 $x_1 + x_2 - s_2 = 8$ 无天然基变量，需添加人工变量 $a \ge 0$ ，并将其加入目标函数（系数为罚数 $M$ ，取 $M=100$ ），最终带人工变量的标准型为：

$\min \ z = x_1 + x_2 + 0·s_1 + 0·s_2 + 100a$

$\text{s.t.} \ \begin{cases} x_1 - x_2 + s_1 = 0\\ x_1 + x_2 - s_2 + a = 8 \\ x_1, x_2, s_1, s_2, a \ge 0 \end{cases}$

此时，两个约束的基变量 $s_1$ 和 $a$ 的系数构成2阶单位矩阵： $\begin{bmatrix}1&0\\0&1\end{bmatrix}$ ，满足单纯形法初始可行基的要求，可正式开始迭代求解。

步骤3：人工变量的最终判定

后续通过单纯形法迭代后，若人工变量 $a=0$ ，则剔除人工变量，得到原问题的可行解；若 $a>0$ ，则说明原UI约束存在矛盾，判定为无可行解。

5. 检验数

检验数是单纯形法中判断当前基可行解是否为最优解的核心量化指标，记为 $\sigma_j$ （对应第 $j$ 个变量），本质是目标函数中非基变量的系数经过基变量替换后的剩余系数。

从物理意义上理解：检验数 $\sigma_j$ 表示当某一非基变量的取值增加1个单位（其他非基变量保持0）时，目标函数值的变化量。对于目标函数求最小的场景，变化量越小越优，这也是检验数作为最优性判断依据的核心逻辑。

检验数的核心作用仅有两个，且贯穿单纯形法的整个迭代过程：

判断当前解是否为最优解：根据目标函数类型（求最小/最大），通过检验数的符号判定，若满足最优性条件则停止迭代，否则继续；
选择进基变量：若当前解非最优，选择检验数最劣的非基变量作为进基变量（即将该变量从非基变量转为基变量），进行枢轴运算。

基变量的检验数恒为0，因此仅需计算非基变量的检验数即可，无需对所有变量计算，简化求解步骤。

检验数的计算是基于单纯形表的核心参数，公式为线性规划通用形式，无语法错误，可直接手算或编程实现，目标函数求最小/最大均适用。

我们设线性规划标准型的约束系数矩阵为 $A$ ，目标函数系数向量为 $C$ ，定义3个核心参数：

$C_B$ ：基变量的目标函数系数向量，按基变量在约束中的顺序排列，维度为 $m×1$ （ $m$ 为约束个数）；
$P_j$ ：第 $j$ 个变量在约束系数矩阵中的列向量，维度为 $m×1$ ，包含该变量在所有约束中的系数；
$c_j$ ：第 $j$ 个变量的原始目标函数系数，即向量 $C$ 中的第 $j$ 个元素。

检验数的公式为第 $j$ 个变量的检验数 $\sigma_j$ 计算公式为：

$\sigma_j = c_j - C_B \cdot P_j$

其中， $C_B \cdot P_j$ 为向量点积，计算规则为： $C_B \cdot P_j = \sum_{i=1}^m C_{Bi} \cdot P_{ij}$ （ $C_{Bi}$ 为 $C_B$ 的第 $i$ 个元素， $P_{ij}$ 为 $P_j$ 的第 $i$ 个元素）。

检验数的最优性判断严格依赖目标函数的类型，无通用准则，Cassowary算法因需最小化“约束误差和”，仅使用目标求最小的准则，以下为两类核心准则，均为线性规划行业标准：

目标函数求最小值（Cassowary算法/绝大多数工程场景）：若所有非基变量的检验数 $\sigma_j \ge 0$ ，则当前基可行解为最优解；

逻辑：非基变量检验数≥0，说明其取值增加会导致目标函数值增大，无优化空间，当前解即为最优。

目标函数求最大值：若所有非基变量的检验数 $\sigma_j \le 0$ ，则当前基可行解为最优解；

逻辑：非基变量检验数≤0，说明其取值增加会导致目标函数值减小，无优化空间，当前解即为最优。

沿用人工变量部分的UI约束实例（带人工变量的标准型），全程手算检验数，并完成最优性判断，步骤清晰可复现。

接着上面人工变量的例子：

$\min \ z = x_1 + x_2 + 0·s_1 + 0·s_2 + 100a$

$\text{s.t.} \ \begin{cases} x_1 - x_2 + s_1 = 0 \\ x_1 + x_2 - s_2 + a = 8 \\ x_1, x_2, s_1, s_2, a \ge 0 \end{cases}$

基变量： $s_1$ 、 $a$ （按约束顺序）；非基变量： $x_1$ 、 $x_2$ 、 $s_2$ ；罚数 $M=100$ 。

步骤1：确定计算所需的核心参数

基变量系数向量 $C_B$ ：基变量为 $s_1$ （ $c_j=0$ ）、 $a$ （ $c_j=100$ ），因此 $C_B = \begin{bmatrix}0\\100\end{bmatrix}$ ；
所有变量的原始目标函数系数 $c_j$ ：按 $x_1、x_2、s_1、s_2、a$ 顺序， $c_j = [1, 1, 0, 0, 100]$ ；
各变量的约束系数列向量 $P_j$ （按变量顺序）：
- $P_1$ （ $x_1$ ）： $\begin{bmatrix}1\\1\end{bmatrix}$ ， $P_2$ （ $x_2$ ）： $\begin{bmatrix}-1\\1\end{bmatrix}$ ， $P_3$ （ $s_1$ ）： $\begin{bmatrix}1\\0\end{bmatrix}$ ；
- $P_4$ （ $s_2$ ）： $\begin{bmatrix}0 \\ -1\end{bmatrix}$ ， $P_5$ （ $a$ ）： $\begin{bmatrix}0\\1\end{bmatrix}$ 。

步骤2：按公式计算所有变量的检验数

基变量检验数恒为0，此处仍全量计算，验证公式的正确性：

$\sigma_1 (x_1)$ ： $\sigma_1 = c_1 - C_B·P_1 = 1 - (0×1 + 100×1) = -99$ ；
$\sigma_2 (x_2)$ ： $\sigma_2 = c_2 - C_B·P_2 = 1 - (0×(-1) + 100×1) = -99$ ；
$\sigma_3 (s_1)$ ： $\sigma_3 = c_3 - C_B·P_3 = 0 - (0×1 + 100×0) = 0$ （基变量，验证为0）；
$\sigma_4 (s_2)$ ： $\sigma_4 = c_4 - C_B·P_4 = 0 - (0×0 + 100×(-1)) = 100$ ；
$\sigma_5 (a)$ ： $\sigma_5 = c_5 - C_B·P_5 = 100 - (0×0 + 100×1) = 0$ （基变量，验证为0）。

步骤3：最优性判断（目标求最小）

最优性条件：所有非基变量的检验数 $\sigma_j \ge 0$ ；

本实例非基变量为 $x_1(\sigma=-99)$ 、 $x_2(\sigma=-99)$ 、 $s_2(\sigma=100)$ ，其中 $x_1$ 和 $x_2$ 的检验数小于0，不满足最优性条件，因此当前解非最优，需要继续迭代。

步骤4：选择进基变量

选择检验数最小的非基变量作为进基变量，本实例中 $\sigma_1=\sigma_2=-99$ ，可任意选择（如选 $x_1$ ），将其从非基变量转为基变量，再通过枢轴运算确定出基变量，完成一次迭代，之后重新计算检验数并判断最优性，直至满足条件。

6. 枢轴变换

枢轴变换中的核心概念：

枢纽元素：记为 $a_{ij}$ ，是约束系数矩阵中，进基变量列与出基变量行的交叉位置的系数，是枢轴变换的运算核心，所有行变换均围绕该元素展开，要求枢轴元素 $≠$ 0（若为0无法完成变换）
进基变量：从非基变量中选定的、即将转为基变量的变量，选择依据由检验数决定（目标求最小选检验数最小的非基变量，目标求最大选检验数最大的非基变量）
出基变量：从基变量中选定的、即将转为非基变量的变量，选择依据由最小比值法则决定（保证变换后约束右侧 $b_i≥0$ ，解仍可行），核心是避免变量取负值违反非负约束

1) 如何选择出基变量

选择出基变量要参看最小比值法则：

设进基变量为 $x_k$ ，其在约束中的系数列为 $P_k = [a_{1k}, a_{2k}, ..., a_{mk}]^T$ ，约束右侧常数列为 $b = [b_1, b_2, ..., b_m]^T$ ，则：

仅考虑 $a_{ik} > 0$ 的行（目标求最小，对偶单纯形法为 $a_{ik} < 0$ ，核心是保证比值为正）；
计算每一行的比值： $\theta_i = \frac{b_i}{a_{ik}}$ ；
选择比值最小的行对应的基变量为出基变量，该行即为枢轴行，进基变量列即为枢轴列，交叉点为枢轴元素。

它的作用是保证枢轴变换后，所有约束右侧的常数项 $b_i≥0$ ，满足变量非负约束，解仍为可行解。

2) 枢轴变换的运算法则

枢轴变换本质是对单纯形表进行初等行变换，分为两步核心操作，所有行变换均不改变约束等式的等价性（变换前后解一致），适用于所有单纯形法迭代场景。

设枢轴元素为 $a_{pq}$ （第 $p$ 行，第 $q$ 列），枢轴行为第 $p$ 行，枢轴列为第 $q$ 列：

步骤1：归一化枢轴行（让枢轴元素变为1）

将枢轴行的所有元素（包括约束右侧的 $b_p$ ）除以枢轴元素 $a_{pq}$ ，得到新的枢轴行 $L_p'$ ：

$L_p' = \frac{1}{a_{pq}} × L_p$

目的是让进基变量在枢轴行的系数变为1，满足基变量“所在行系数为1”的要求。

步骤2：消去其他行的枢轴列元素（让进基变量仅在枢轴行出现）

对除枢轴行外的每一行 $L_i$ （ $i≠p$ ），执行行变换：

$L_i' = L_i - a_{iq} × L_p'$

其中 $a_{iq}$ 是第 $i$ 行、枢轴列 $q$ 的系数；

目的是让进基变量在其他所有行的系数变为0，满足基变量“仅在本约束出现，其他约束系数为0”的核心要求。

变换完成后有以下结论：

进基变量成为新的基变量，其系数列变为单位列向量（枢轴行系数1，其他行系数0）；
出基变量成为新的非基变量，其系数列不再是单位列向量；
所有约束等式保持等价，约束右侧 $b_i≥0$ ，解仍可行；
目标函数值会向更优方向变化（目标求最小则减小，目标求最大则增大）。

举个例子：

在本例中，目标是最小化两个界面元素的坐标和，带松弛变量、剩余变量、人工变量，已计算检验数，确定当前解非最优：

$\min \ z = x_1 + x_2 + 0·s_1 + 0·s_2 + 100a$

$\text{s.t.} \ \begin{cases} 1·x_1 - 1·x_2 + 1·s_1 + 0·s_2 + 0·a = 0 \quad (1) \\ 1·x_1 + 1·x_2 + 0·s_1 - 1·s_2 + 1·a = 8 \quad (2) \\ x_1, x_2, s_1, s_2, a ≥ 0 \end{cases}$

已知条件：

基变量： $s_1$ （行1）、 $a$ （行2）；非基变量： $x_1、x_2、s_2$ ；
检验数： $\sigma_{x1}=-99$ ， $\sigma_{x2}=-99$ ， $\sigma_{s2}=100$ ， $\sigma_{s1}=0$ ， $\sigma_a=0$ ；
约束右侧 $b$ ： $b_1=0$ ， $b_2=8$ ；

步骤1：选择进基变量（检验数准则）

目标函数求最小值，进基变量选检验数最小的非基变量；

本实例中 $\sigma_{x1}=\sigma_{x2}=-99$ （最小），任意选择 $x_1$ 作为进基变量，枢轴列为 $x_1$ 对应的列（系数列： $[1, 1]^T$ ）。

步骤2：选择出基变量（最小比值法则）

进基变量为 $x_1$ ，其系数列 $P_{x1} = [1, 1]^T$ ，约束右侧 $b = [0, 8]^T$ ；

筛选 $a_{ik} > 0$ 的行：两行系数均为1 $>$ 0，全部保留；
计算比值 $\theta_i = \dfrac{b_i}{a_{ik}}$ ：
- 行1（基变量 $s_1$ ）： $\theta_1 = \dfrac{0}{1} = 0$ ；
- 行2（基变量 $a$ ）： $\theta_2 = \dfrac{8}{1} = 8$ ；
选择比值最小的行：行1（ $\theta_1=0$ ），对应的基变量 $s_1$ 为出基变量，枢轴行为行1。

步骤3：确定枢轴元素

枢轴列（ $x_1$ 列）与枢轴行（行1）的交叉位置系数： $a_{11}=1$ ，即枢轴元素 $=$ 1。

步骤4：执行枢轴变换（初等行变换）

围绕枢轴元素 $a_{11}=1$ ，按“归一化枢轴行→消去其他行枢轴列元素”执行变换，先构造单纯形表（更直观，行：约束1、约束2；列：变量+ $b$ ；最后一行暂不考虑目标函数）：

基变量	$x_1$	$x_2$	$s_1$	$s_2$	$a$	$b$
$s_1$	1	-1	1	0	0	0
$a$	1	1	0	-1	1	8

变换1：归一化枢轴行（行1）

枢轴元素 $a_{11}=1$ ，因此行1保持不变（除以1后与原行一致）：

$L_1' = L_1 = [1, -1, 1, 0, 0, 0]$

变换2：消去其他行（行2）的枢轴列元素

行2的枢轴列系数 $a_{21}=1$ ，执行行变换： $L_2' = L_2 - 1×L_1'$

逐元素计算：

$x_1$ ： $1 - 1×1 = 0$ ；
$x_2$ ： $1 - 1×(-1) = 2$ ；
$s_1$ ： $0 - 1×1 = -1$ ；
$s_2$ ： $-1 - 1×0 = -1$ ；
$a$ ： $1 - 1×0 = 1$ ；
$b$ ： $8 - 1×0 = 8$ ；

得到新行2： $L_2' = [0, 2, -1, -1, 1, 8]$ 。

步骤5：变换后结果（新的约束体系+基/非基变量更新）

将变换后的行1、行2替换原约束，得到等价的新约束体系：

$\begin{cases} 1·x_1 - 1·x_2 + 1·s_1 + 0·s_2 + 0·a = 0 \quad (1') \\ 0·x_1 + 2·x_2 - 1·s_1 - 1·s_2 + 1·a = 8 \quad (2') \end{cases}$

基/非基变量更新：

新基变量： $x_1$ （行1）、 $a$ （行2）（进基变量 $x_1$ 替换出基变量 $s_1$ ）；
新非基变量： $s_1、x_2、s_2$ （出基变量 $s_1$ 转为非基变量）；

关键验证：

进基变量 $x_1$ 的系数列为 $[1, 0]^T$ （单位列向量），满足基变量要求；
约束右侧 $b_1=0$ 、 $b_2=8$ ，均≥0，解仍可行；
约束等式与原等式等价，未改变问题的解。

步骤6：后续迭代（简要说明）

变换完成后，重新计算新的检验数，再次判断是否满足最优性条件（所有非基变量 $\sigma_j≥0$ ）：

若满足，停止迭代，得到最优解；
若不满足，重复“选进基→选出基→枢轴变换”步骤，直至满足最优性条件。

本实例中，变换后需重新计算检验数，若仍有非基变量检验数 $<$ 0，则继续以新的基/非基变量执行枢轴变换，最终会迭代至人工变量 $a=0$ ，得到原UI约束的最优解。

3) 枢轴变换的本质与核心作用

数学本质：对线性方程组的初等行变换，仅改变方程组的表达形式，不改变方程组的解，保证约束的等价性；
算法作用：实现基变量与非基变量的交换，让单纯形法从可行域的一个顶点，移动到相邻的、目标函数值更优的顶点（线性规划最优解必在可行域顶点上）；
工程作用：让算法逐步逼近最优解，每次变换仅调整少量变量的身份，无需全量重新求解，这也是Cassowary算法能实现增量式优化的基础。

三、对偶单纯形法

1. 核心思想：与单纯形法完全反向

单纯形法：

始终保持原问题可行（ $b_i \ge 0$ ），逐步让检验数达到最优。
对偶单纯形法：

始终保持检验数最优（对 min 问题： $\sigma_j \ge 0$ ），逐步让原问题变得可行（把负的 $b_i$ 变成非负）。

一句话总结：单纯形法：先可行，再最优。对偶单纯形法：先最优，再可行。

2. 标准前提条件

对偶单纯形法要求初始表格就满足最优性：

对 min 问题：所有检验数 $\sigma_j \ge 0$
对 max 问题：所有检验数 $\sigma_j \le 0$

但允许右端项 $b_i < 0$ （原问题不可行）。

这正是 Cassowary 最常见的场景：约束被临时破坏（拖动、边界碰撞），导致 $b_i < 0$ ，但检验数依然是好的。

3. 迭代步骤（和单纯形法完全反过来）

（1）先选出基变量

看右端项 $b$ 列
选 $b_i < 0$ 且最小（最负） 的那一行
这一行对应的基变量 $=$ 出基变量

（2）再选入基变量

只用这一行里系数 $<$ 的列计算比值：

$\theta = \min \{ \dfrac{\sigma_j}{a_{ij}} \bigg| a_{ij} < 0 \}$

比值最小的列对应的非基变量 = 入基变量

（3）枢轴变换

规则和单纯形法完全一样：

把枢轴元素变成 1
把同列其他元素消成 0

目标：把这一行的 $b_i$ 从负数变回非负，同时保持检验数始终最优。

4. 为什么叫对偶单纯形法？

（1）每个线性规划都有一个「对偶问题」

原问题（Primal）：变量 $x$ ，约束 $A x = b, x\ge 0$
对偶问题（Dual）：变量 $y$ ，约束 $y A \le c$

它们的可行、最优是对称的：

原问题可行 $⇔$ 对偶问题达到最优性
原问题最优 $⇔$ 对偶问题也最优

所以：对偶单纯形法 = 用原问题的不可行性，等价地对对偶问题做单纯形迭代。

这就是它名字的来源：它是“对偶视角”下的单纯形法。

四、Cassowary算法中的适配与应用

Cassowary算法基于对偶单纯形法实现，其枢轴变换的运算规则与标准单纯形法完全一致，仅在进基/出基变量的选择准则上做了适配，以适应用户界面交互式、增量式的约束求解场景，核心差异与应用特点如下：

1. 触发场景极少

Cassowary算法仅在鼠标拖动导致约束暂时不可行（如界面元素触碰到窗口边界，约束右侧 $b_i<0$ ）时，才执行枢轴变换，大多数UI交互操作（如平滑拖动）无需执行，因此运算量极小，保证了界面的实时响应。

2. 基于对偶单纯形法的选择准则

标准单纯形法从可行但非最优的解开始迭代，枢轴变换保证解始终可行；

Cassowary算法的对偶单纯形法从最优但不可行的解开始迭代，进基/出基变量选择准则适配为：

出基变量：选约束右侧 $b_i<0$ 的行对应的基变量（不可行的基变量）；
进基变量：按最小比值法则从非基变量中选择，保证变换后解逐步可行。

3. 仅操作约束表格（Tableau）的局部元素

Cassowary算法将约束体系存储为稀疏表格（Tableau），枢轴变换仅修改表格中枢轴行、枢轴列的局部元素，无需全量更新表格，进一步减少运算量，适配UI交互的低延迟要求。

4. 核心目的：快速修正约束不可行

Cassowary算法中，枢轴变换的核心目的不是“迭代至最优解”，而是快速将“最优但不可行”的解修正为“最优且可行”，让界面元素按约束要求贴靠边界、调整位置，这是与标准单纯形法的核心区别。