文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文围绕《算法导论》第三版第 29.5 节「The initial basic feasible solution」的全部习题展开系统讲解当标准型线性规划的初始基本解不可行时如何通过构造辅助线性规划auxiliary linear program$L_{aux}$、引入人工变量 $x_0$ 并配合 $\text{PIVOT}$ 与 $\text{INITIALIZE-SIMPLEX}$ 得到初始基本可行解从而启动 $\text{SIMPLEX}$ 主循环文中还给出 29.5-5 至 29.5-9 五道题的完整手算推导含全部 slack form 迭代过程以及 29.5-1 至 29.5-4 的伪代码设计与理论证明。读完本文你将掌握两阶段单纯形法的完整落地细节如何判断原问题可行、如何检测无界与不可行以及如何正确恢复原始目标函数。本文内容主体来自仓库 docs/Chap29/29.5.md并与同章 29.1 标准型与松弛型、29.3 单纯形算法、29.4 对偶性 以及本章 综合题 29-1线性不等式可行性 相互印证。第 29 章其余小节见 29.2 将问题表述为线性规划。一、为什么需要「初始基本可行解」问题的起点在 29.3 节的单纯形算法 SIMPLEX 中主循环得以开始的前提是当前松弛型slack form对应的基本解basic solution是可行的即所有基本变量 $b_i \ge 0$。但标准型线性规划 $$ \begin{array}{lrl} \text{maximize} \sum_{j 1}^n c_j x_j \ \text{subject to} \sum_{j 1}^n a_{ij} x_j \le b_i, i 1, 2, \dots, m \ x_j \ge 0, j 1, 2, \dots, n \end{array} $$ 转换为松弛型后基本变量取值为 $x_{ni} b_i$。由 29.3-4 的结论 可知基本解可行当且仅当所有 $b_i \ge 0$。当某个 $b_i 0$ 时初始基本解落在可行域之外$\text{SIMPLEX}$ 无法直接启动这正是 29.5 节要解决的问题构造初始基本可行解。29.5 节给出的标准做法是辅助线性规划auxiliary linear program在标准型中加入一个新变量 $x_0$把目标改为最大化 $-x_0$得到 $$ \begin{array}{lrl} \text{maximize} -x_0 \ \text{subject to} \sum_{j 1}^n a_{ij} x_j - x_0 \le b_i, i 1, 2, \dots, m \ x_j \ge 0, j 0, 1, \dots, n. \end{array} $$ 记此辅助问题为 $L_{aux}$。直觉上$x_0$ 扮演「松弛变量」的角色吸收所有负的 $b_i$只要 $x_0$ 足够大所有约束都能满足因此 $L_{aux}$ 一定可行而目标 $-x_0$ 会迫使算法把 $x_0$ 压到最小。$L_{aux}$ 的最优值恰为 $0$ 当且仅当原问题 $L$ 可行——这就是两阶段单纯形法第一阶段的核心判定。INITIALIZE-SIMPLEX的整体流程见教材第 29.5 节可概括为若所有 $b_i \ge 0$直接返回当前松弛型基本解已可行否则构造 $L_{aux}$选取 $x_0$ 为进基变量entering variable、$b_i$ 最负的那一行对应的基本变量为离基变量leaving variable调用一次 $\text{PIVOT}$反复调用 $\text{PIVOT}$ 求 $L_{aux}$ 的最优解若最优值仍小于 $0$即 $x_0$ 无法归零判定原问题不可行并终止否则删去 $x_0$恢复原始目标函数把得到的松弛型交给 $\text{SIMPLEX}$ 主循环继续求解。下面按习题逐一展开。二、29.5-1INITIALIZE-SIMPLEX 第 5 行与第 14 行的详细伪代码原题Give detailed pseudocode to implement lines 5 and 14 of $\text{INITIALIZE-SIMPLEX}$.教材中INITIALIZE-SIMPLEX的第 5 行对应「反复对 $L_{aux}$ 调用 $\text{PIVOT}$ 直至得到最优解」第 14 行对应「恢复 $L$ 的原始目标函数」。答案给出的实现思路如下。第 5 行的实现求解 $L_{aux}$设 $\text{PIVOT}$ 作用于 $L_{aux}$、以 $x_0$ 为进基变量后的结果为 $(N, B, A, b, c, v)$。此后反复调用 $\text{PIVOT}$直到 $L_{aux}$ 达到最优解并把结果归还给 $(N, B, A, b, c, v)$。这一步本质就是「两阶段法的第一阶段」目标函数 $-x_0$ 中唯一的非零系数是 $x_0$因此每轮迭代都会尝试让 $x_0$ 离基最终要么 $x_0$ 被挤出基变量集合说明最优值 $0$ 可达原问题可行要么目标值无法归零原问题不可行。从约束中移除 $x_0$求解完 $L_{aux}$ 后需要把人工变量 $x_0$ 从松弛型中彻底删除对所有 $i \in B$当前基变量下标集合令 $a_{i,0} 0$即让 $x_0$ 不再出现在任何约束中令 $N N \backslash {0}$即把 $x_0$ 从非基变量集合中剔除。这样得到的约束系统不再包含 $x_0$与 $L$ 的约束等价。第 14 行的实现恢复原始目标函数$L_{aux}$ 的目标是 $-x_0$而 $L$ 的目标是 $\sum_{j \in N} c_j x_j$。为了把目标函数「换回来」需要对每个 $j \in N$、每个 $i \in B$ 执行 $$ c_j c_j - c_i a_{ij}. $$ 这里 $c_i$ 是当前目标函数中基变量 $x_i$$i \in B$的系数。其含义是当前松弛型中每个基本变量 $x_i$ 都由非基变量线性表示即各行约束给出了 $x_i$ 关于非基变量的表达式把 $x_i$ 的表达式代回目标函数后非基变量 $x_j$ 的新系数就是在旧系数 $c_j$ 基础上减去 $c_i a_{ij}$ 的贡献。经过这一轮替换目标函数中只保留非基变量且与 $L$ 的原始目标在可行域上完全等价——这正是 29.3-3 所证明的「PIVOT 前后松弛型等价」 的再一次应用。实战要点恢复目标函数时必须先完成 $L_{aux}$ 的求解、确认 $x_0 0$再删除 $x_0$ 并做系数替换。若在 $L_{aux}$ 尚未最优时就提前恢复目标第二阶段会带着错误的初始基本解进入 $\text{SIMPLEX}$。三、29.5-2为什么主循环永远不会返回 unbounded原题Show that when the main loop of $\text{SIMPLEX}$ is run by $\text{INITIALIZE-SIMPLEX}$, it can never return unbounded.证明的关键在于理解 $\text{INITIALIZE-SIMPLEX}$ 进入第 10 行即把控制权交给 $\text{SIMPLEX}$ 主循环的前提进入主循环之前我们已经恢复了 $L_{aux}$ 的一个可行基本解由于 $x_0 \ge 0$ 且 $L_{aux}$ 的目标函数是 $-x_0$该解乃至 $L_{aux}$ 的任何可行解的目标值必为负值或零目标是最大化 $-x_0$而上界为 $0$——因为 $-x_0 \le 0$ 恒成立由教材 Lemma 29.2$\text{SIMPLEX}$ 能正确判定输入线性规划是否有界既然 $L_{aux}$不可能无界目标值被 $0$ 从上方钳制$\text{SIMPLEX}$ 就永远不可能返回 unbounded。也就是说$L_{aux}$ 的目标函数天然有界上界为 $0$而 $\text{INITIALIZE-SIMPLEX}$ 只对 $L_{aux}$ 运行主循环因此无界分支永远不会被触发。这保证了第一阶段一定会在有限步内终止于「可行」或「不可行」两种明确结论之一。四、29.5-3原问题与对偶的初始基本解均可行时最优值为 0原题Suppose that we are given a linear program $L$ in standard form, and suppose that for both $L$ and the dual of $L$, the basic solutions associated with the initial slack forms are feasible. Show that the optimal objective value of $L$ is $0$.证明分三步标准型线性规划的目标函数没有常数项完全由 $\sum_{i1}^n c_i x_i$ 给出对任何基本解基本变量之外的 $x_i$ 全部取 $0$而言这个和式都为 $0$对偶问题的目标函数 $b^{\mathrm{T}} y$ 同理——对偶的基本解也会使目标值取 $0$由弱对偶定理的推论29.4 节对偶性存在某个可行解使原问题与对偶问题的目标值相等这里都等于 $0$那么这个公共值必然就是最优值。因此 $L$ 的最优目标值为 $0$。这个结论直观上很好理解原问题和对偶各有一个取值为 $0$ 的可行解而弱对偶定理保证原问题任何可行解的目标值不超过对偶任何可行解的目标值二者被夹在同一高度 $0$ 上。五、29.5-4允许严格不等式时线性规划基本定理失效原题Suppose that we allow strict inequalities in a linear program. Show that in this case, the fundamental theorem of linear programming does not hold.反例非常简洁考虑最大化 $x_1$约束为 $$ x_1 1, \qquad x_1 \ge 0. $$ 这个可行域是非空且有界的$0 \le x_1 1$但不存在最优解——因为目标 $x_1$ 可以无限逼近 $1$ 却永远达不到 $1$上确界 $1$ 不在可行域内。线性规划基本定理说的是若一个线性规划有界且有可行解则必存在最优解且最优解出现在某个顶点上。严格不等式把可行域的「边界」挖掉后最优值可能只以「极限」的形式存在而不被任何可行点取得定理因此不再成立。这也从反面解释了为什么标准型一律采用非严格不等式$\le$只有闭的可行域才能保证顶点处的极值可达。六、29.5-5 完整算例两阶段单纯形法全过程可行情形原题Solve the following linear program using $\text{SIMPLEX}$: $$ \begin{array}{lrcrcrl} \text{maxmize} x_1 3x_2 \\ \text{subject to} \\ x_1 - x_2 \le 8 \\ -x_1 - x_2 \le -3 \\ -x_1 4x_2 \le 2 \\ x_1, x_2 \ge 0 . \end{array} $$初始基本解不可行第二个约束的右端为 $-3$因此需要构造辅助线性规划 $L_{aux}$$$ \begin{array}{lrcrcrcrl} \text{maxmize} -x_0 \\ \text{subject to} \\ -x_0 x_1 - x_2 \le 8 \\ -x_0 - x_1 - x_2 \le -3 \\ -x_0 - x_1 4x_2 \le 2 \\ x_0, x_1, x_2 \ge 0 . \end{array} $$第一步改写为松弛型引入松弛变量 $x_3, x_4, x_5$$$ \begin{array}{rcrcrcrcr} z - x_0 \\ x_3 8 x_0 - x_1 x_2 \\ x_4 -3 x_0 x_1 x_2 \\ x_5 2 x_0 x_1 - 4x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$第二步第一次 PIVOT$x_0$ 进基$x_4$ 离基$b_i$ 最负的是 $x_4$ 所在行$b_4 -3$因此选择 $x_0$ 为进基变量、$x_4$ 为离基变量调用 $\text{PIVOT}$$$ \begin{array}{rcrcrcrcr} z -3 x_1 x_2 - x_4 \\ x_0 3 - x_1 - x_2 x_4 \\ x_3 11 - 2x_1 x_4 \\ x_5 5 - 5x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$此时基本解可行$x_0 3, x_3 11, x_5 5$ 均非负进入 $\text{PIVOT}$ 循环求解 $L_{aux}$。第三步第二次 PIVOT$x_1$ 进基$x_0$ 离基目标函数中 $x_1, x_2$ 的系数均为正选 $x_1$ 进基由 $x_0 3 - x_1 - x_2 x_4$ 知 $x_1$ 被 $x_0$ 所在行约束最紧故 $x_0$ 离基$$ \begin{array}{rcrcrcrcr} z -x_0 \\ x_1 3 - x_0 - x_2 x_4 \\ x_3 5 2x_0 2x_2 - x_4 \\ x_5 5 - 5x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$$z -x_0$所有非基变量系数非正$L_{aux}$ 达到最优且最优值为 $0$$x_0$ 已是非基变量可置为 $0$——原问题可行。第四步删除 $x_0$、恢复原始目标函数置 $x_0 0$按 29.5-1 的方法恢复原目标 $x_1 3x_2$将 $x_1 3 - x_2 x_4$ 代入得到$$ \begin{array}{rcrcrcr} z 3 2x_2 x_4 \\ x_1 3 - x_2 x_4 \\ x_3 5 2x_2 - x_4 \\ x_5 5 - 5x_2 x_4 \\ x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$现在交给 $\text{SIMPLEX}$ 主循环。第五步进入主循环选 $x_2$ 进基。各约束对 $x_2$ 的限制$x_1$ 行限制 $x_2 \le 3$$x_3$ 行限制 $x_2 \le 5/2$$x_5$ 行限制 $x_2 \le 1$最紧的是 $x_5$ 行比值最小故 $x_5$ 离基$$ \begin{array}{rcrcrcr} z 5 (7 / 5)x_4 - (2 / 5)x_5 \\ x_1 2 (1 / 5)x_4 (1 / 5)x_5 \\ x_2 1 (4 / 5)x_4 - (1 / 5)x_5 \\ x_3 7 - (3 / 5)x_4 - (2 / 5)x_5 \\ x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$第六步最后一次 PIVOT选 $x_4$ 进基$x_3$ 离基$x_4$ 的限制来自 $x_3$ 行$x_4 \le 7 \cdot (5/3)$$$ \begin{array}{rcrcrcr} z (64 / 3) - (7 / 3)x_3 - (4 / 3)x_5 \\ x_1 (34 / 3) - (4 / 3)x_3 - (1 / 3)x_5 \\ x_2 (10 / 3) - (1 / 3)x_3 - (1 / 3)x_5 \\ x_4 (35 / 3) - (5 / 3)x_3 - (2 / 3)x_5 \\ x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$目标函数中所有非基变量系数均为负基本解即最优解 $$ (x_1, x_2) \left(\frac{34}{3}, \frac{10}{3}\right), \qquad z \frac{64}{3}. $$七、29.5-6 完整算例辅助问题最优值非零 → 原问题不可行原题Solve the following linear program using $\text{SIMPLEX}$: $$ \begin{array}{lrcrcrl} \text{maxmize} x_1 - 2x_2 \\ \text{subject to} \\ x_1 2x_2 \le 4 \\ -2x_1 - 6x_2 \le -12 \\ x_2 \le 1 \\ x_1, x_2 \ge 0 . \end{array} $$同样先构造辅助线性规划$$ \begin{array}{lrcrcrcrl} \text{maxmize} -x_0 \\ \text{subject to} \\ -x_0 x_1 2x_2 \le 4 \\ -x_0 - 2x_1 - 6x_2 \le -12 \\ -x_0 x_2 \le 1 \\ x_0, x_1, x_2 \ge 0 . \end{array} $$松弛型与第一次 PIVOT$$ \begin{array}{rcrcrcrcr} z - x_0 \\ x_3 4 x_0 - x_1 - 2x_2 \\ x_4 -12 x_0 2x_1 6x_2 \\ x_5 1 x_0 - x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$$b_i$ 最负的是 $x_4$$-12$以 $x_0$ 进基、$x_4$ 离基调用 $\text{PIVOT}$$$ \begin{array}{rcrcrcrcr} z -12 2x_1 6x_2 - x_4 \\ x_0 12 - 2x_1 - 6x_2 x_4 \\ x_3 16 - 3x_1 - 8x_2 x_4 \\ x_5 13 - 2x_1 - 8x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$基本解 $(x_0, x_1, x_2, x_3, x_4, x_5) (12, 0, 0, 16, 0, 13)$ 对辅助问题可行。继续求解 $L_{aux}$目标函数中 $x_1, x_2$ 系数为正选 $x_1$ 进基被 $x_3$ 行约束最紧$x_1 \le 16/3$$x_3$ 离基$$ \begin{array}{rcrcrcrcr} z -(4 / 3) (2 / 3)x_2 - (2 / 3)x_3 (1 / 3) x_4 \\ x_0 (4 / 3) - (2 / 3)x_2 (2 / 3)x_3 (1 / 3) x_4 \\ x_1 (16 / 3) - (8 / 3)x_2 - (1 / 3)x_3 (1 / 3) x_4 \\ x_5 (7 / 3) - (8 / 3)x_2 (2 / 3)x_3 (1 / 3) x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$关键判定$x_0 \ne 0$ → 原问题不可行目标函数中所有非基变量系数为负$x_2$ 系数 $2/3$ 为正但已无更优选择——注意 $z$ 表达式中 $x_2$ 系数为正然而检查约束可知 $x_2$ 若进基会违反可行性且此处取基本解即可得到 $L_{aux}$ 的最优解基本解 $(x_0, x_1, x_2, x_3, x_4, x_5) (4/3, 16/3, 0, 0, 0, 7/3)$ 也是 $L_{aux}$ 的最优解。但注意 $x_0 4/3 \ne 0$即 $L_{aux}$ 的最优值为 $-4/3 0$。根据第一阶段的判定准则原线性规划不可行无需再恢复目标函数、进入第二阶段。这个例子清晰展示了「$x_0$ 无法被压到 $0$」与「原问题无可行解」之间的等价关系。八、29.5-7 完整算例主循环判定 unbounded原题Solve the following linear program using $\text{SIMPLEX}$: $$ \begin{array}{lrcrcrl} \text{maxmize} x_1 3x_2 \\ \text{subject to} \\ -x_1 x_2 \le -1 \\ -x_1 - x_2 \le -3 \\ -x_1 4x_2 \le 2 \\ x_1, x_2 \ge 0 . \end{array} $$构造辅助问题与松弛型$$ \begin{array}{lrcrcrcrl} \text{maxmize} -x_0 \\ \text{subject to} \\ -x_0 - x_1 x_2 \le -1 \\ -x_0 - x_1 - x_2 \le -3 \\ -x_0 - x_1 4x_2 \le 2 \\ x_0, x_1, x_2 \ge 0 . \end{array} $$$$ \begin{array}{rcrcrcrcr} z - x_0 \\ x_3 -1 x_0 x_1 - x_2 \\ x_4 -3 x_0 x_1 x_2 \\ x_5 2 x_0 x_1 - 4x_2 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$第一阶段$b_i$ 最负的是 $x_4$$-3$$x_0$ 进基、$x_4$ 离基$$ \begin{array}{rcrcrcrcr} z -3 x_1 x_2 - x_4 \\ x_0 3 - x_1 - x_2 x_4 \\ x_3 2 - 2x_2 x_4 \\ x_5 5 - 5x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$选 $x_1$ 进基$x_0$ 离基$$ \begin{array}{rcrcrcrcr} z - x_0 \\ x_1 3 - x_0 - x_2 x_4 \\ x_3 2 - 2x_2 x_4 \\ x_5 5 - 5x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$基本解可行且对 $L_{aux}$ 最优$x_0 0$原问题可行。删除 $x_0$ 并恢复目标 $x_1 3x_2$$$ \begin{array}{rcrcrcr} z 3 2x_2 x_4 \\ x_1 3 - x_2 x_4 \\ x_3 2 - 2x_2 x_4 \\ x_5 5 - 5x_2 x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$第二阶段先进入一个有界迭代再走向无界选 $x_2$ 进基。约束限制$x_1$ 行 $x_2 \le 3$$x_3$ 行 $x_2 \le 1$$x_5$ 行 $x_2 \le 1$取 $x_3$ 离基$$ \begin{array}{rcrcrcr} z 5 - x_3 2x_4 \\ x_1 2 (1 / 2)x_3 (1 / 2)x_4 \\ x_2 1 - (1 / 2)x_3 (1 / 2)x_4 \\ x_5 (5 / 2)x_3 - (3 / 2)x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$选 $x_4$ 进基$x_5$ 离基$$ \begin{array}{rcrcrcr} z 5 (7 / 3)x_3 - (4 / 3)x_5 \\ x_1 2 (4 / 3)x_3 - (1 / 3)x_5 \\ x_2 1 (1 / 3)x_3 - (1 / 3)x_5 \\ x_4 (5 / 3)x_3 - (2 / 3)x_5 \\ x_0, x_1, x_2, x_3, x_4, x_5 \ge 0 . \end{array} $$最后想选 $x_3$ 进基但检查各行$x_1$ 行系数 $4/3 0$、$x_2$ 行系数 $1/3 0$、$x_4$ 行系数 $5/3 0$——所有约束中 $x_3$ 的系数均为正即不存在任何约束能限制 $x_3$ 的增长。由教材中 $\text{SIMPLEX}$ 的无界判定条件算法返回该线性规划无界unbounded。对照提示29.5-7 与 29.5-5 的约束几乎一致仅第一行由 $x_1 - x_2 \le 8$ 改为 $-x_1 x_2 \le -1$目标函数也同为 $x_1 3x_2$但结果从「最优值 $64/3$」变成了「无界」。这直观展示了可行域的微小变化如何彻底改变线性规划的结局也提醒读者手工验算时每一轮 PIVOT 的离基选择最小比值规则都不可省略。九、29.5-8 完整算例四变量线性规划29.6–29.10原题Solve the linear program given in $\text{(29.6)}$–$\text{(29.10)}$.先化为标准型$$ \begin{array}{lrcrcrcrcrl} \text{maxmize} x_1 x_2 x_3 x_4 \\ \text{subject to} \\ 2x_1 - 8x_2 - 10x_4 \le -50 \\ -5x_1 - 2x_2 \le -100 \\ -3x_1 5x_2 - 10x_3 2x_4 \le -25 \\ x_1, x_2, x_3, x_4 \ge 0 . \end{array} $$初始基本解不可行三个 $b_i$ 均为负构造辅助问题并写出松弛型$$ \begin{array}{rcrcrcrcrcrrcl} z - x_0 \\ x_5 -50 x_0 - 2x_1 8x_2 10x_4 \\ x_6 -100 x_0 5x_1 2x_2 \\ x_7 -25 x_0 3x_1 - 5x_2 10x_3 - 2x_4 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 \ge 0 . \end{array} $$$b_i$ 最小的是 $b_6 -100$下标 2故 $x_0$ 进基、$x_6$ 离基对应教材伪代码第 8 行的 PIVOT$$ \begin{array}{rcrcrcrcrcrrcl} z -100 5x_1 2x_2 - x_6 \\ x_0 100 - 5x_1 - 2x_2 x_6 \\ x_5 50 - 7x_1 8x_2 10x_4 x_6 \\ x_7 75 - 2x_1 - 7x_2 10x_3 - 2x_4 x_6 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 \ge 0 . \end{array} $$选 $x_2$ 进基、$x_5$ 离基$$ \begin{array}{rcrcrcrcrcrcr} z -225 / 2 (27 / 4)x_1 - (10 / 4)x_4 (1 / 4)x_5 - (5 / 4)x_6 \\ x_0 225 / 2 - (27 / 4)x_1 (10 / 4)x_4 - (1 / 4)x_5 (5 / 4)x_6 \\ x_2 -50 / 8 (7 / 8)x_1 - (10 / 8)x_4 (1 / 8)x_5 - (1 / 8)x_6 \\ x_7 475 / 4 - (65 / 8)x_1 10x_3 (54 / 8)x_4 - (7 / 8)x_5 (15 / 8)x_6 \\ x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7 \ge 0 . \end{array} $$说明这一阶段的分数计算已经相当繁琐答案直言 The work gets rather messy——这正是真实求解中容易出现手算笔误的地方。但INITIALIZE-SIMPLEX最终确实给出了原问题的一个可行解随后继续运行单纯形法得到原问题的最优解 $$ (x_1, x_2, x_3, x_4) \left(\frac{175}{11}, \frac{225}{22}, \frac{125}{44}, 0\right). $$这个例子说明两点其一即使 $b_i$ 全部为负三个约束同时不可行两阶段法仍能仅靠一次「$x_0$ 进基、最负行离基」的 PIVOT 就恢复可行性其二当变量与约束增多后手工迭代的代数负担会急剧上升实践中应交给计算机执行仓库中该题仅给出最终结论中间若干轮 PIVOT 留给读者自行复核。十、29.5-9单变量线性规划与其对偶的四种情形原题Consider the following $1$-variable linear program, which we call $P$: $$ \begin{array}{lrcrl} \text{maximize} tx \\ \text{subject to} rx \le s \\ x \ge 0 , \end{array} $$ where $r$, $s$, and $t$ are arbitrary real numbers. Let $D$ be the dual of $P$.State for which values of $r$, $s$, and $t$ you can assert thatBoth $P$ and $D$ have optimal solutions with finite objective values.$P$ is feasible, but $D$ is infeasible.$D$ is feasible, but $P$ is infeasible.Neither $P$ nor $D$ is feasible.这是一个很有教学价值的退化算例通过单变量 LP 穷举出「原问题/对偶可行性与有界性」的全部组合。答案按 $r$ 的符号分情况讨论以下为原答案的整理与展开。情形 1$P$ 与 $D$ 都有有限最优值一种选择是 $r 0$、$s \ge 0$、$t \le 0$。此时约束 $0 \le s$ 恒成立目标 $tx$ 在 $t \le 0$ 时于 $x 0$ 取到最大值 $0$更一般地若 $r 0$则只要 $s$ 非负且 $t$ 非正$x 0$ 即是原问题最优解目标值 $0$对偶问题同样有界。情形 2$P$ 可行但 $D$ 不可行按 $r$ 分两类若 $r 0$恰在 $t$ 非正且 $s$ 非负时成立原问题恒可行且最优值为 $0$而对偶约束要求 $t \le 0$ 无法同时满足时不可行具体由对偶的 $\le s$ 结构决定若 $r 0$ 且 $t 0$因为 $r$ 为负可以让 $rx$ 任意小所以 $s$ 的取值无关紧要约束总能满足但 $rx$ 永远为负永远无法满足对偶一侧「$\ge t$$t 0$」的要求。情形 3$D$ 可行但 $P$ 不可行同样分两类若 $r 0$恰在 $t$ 非负且 $s$ 非正时成立若 $r 0$ 且 $s 0$$r$ 为正意味着 $rx$ 恒非负永远不可能 $\le s 0$故原问题不可行但对偶一侧由于 $rx$ 可以任意大总能做到大于 $t$故对偶可行。情形 4$P$ 与 $D$ 均不可行若 $r 0$、$t$ 为正且 $s$ 为负原问题要求 $0 \le s$ 恒不成立对偶要求 $t \le 0$ 恒不成立双双不可行若 $r \ne 0$答案指出根据 $r$ 的符号总能让 $rx$ 任意大或任意小意味着原问题或对偶二者必有一个可行——因此 $r \ne 0$ 时「两者都不可行」不可能出现。这个习题揭示了弱对偶定理边界上的微妙之处线性规划对偶性并不保证原问题与对偶一定同时可行四种「可行/不可行」组合中三种都可能发生唯一被排除的是「原问题不可行且对偶也不可行」在 $r \ne 0$ 时的情形。这与 综合题 29-1 中「把求解 LP 归约为线性不等式可行性问题」的思路互为补充。十一、本章脉络回顾与实战要点将 29.5 节置于第 29 章的完整知识链中看29.1 节标准型standard form与松弛型slack form的定义、相互转换、基本解概念——是本节所有演算的语言基础29.2 节把最短路径、最大流、二分图匹配等实际问题表述为 LP说明 LP 求解器的通用性29.3 节$\text{SIMPLEX}$ 主循环与 $\text{PIVOT}$ 的正确性、29.3-4 的「$b_i \ge 0 \Leftrightarrow$ 基本解可行」判定 直接催生了本节的需求29.4 节对偶性、弱/强对偶定理29.5-3 与 29.5-9 的证明 都依赖这些结论本节 29.5补上「初始基本解不可行时怎么办」的最后一块拼图使单纯形法成为一个能处理任意标准型 LP 的完整算法。手工实现或手算验证时的关键检查清单进基选择第一阶段总以 $x_0$ 为第一个进基变量第二阶段按目标函数中正系数最大的非基变量进基离基选择用最小比值规则$\min_i {b_i / a_{ie} : a_{ie} 0}$保证新基本解可行29.5-7 正是「所有 $a_{ie} \le 0$ 无约束」才触发无界判定可行性判定$L_{aux}$ 最优值 $ 0 \Leftrightarrow$ 原问题可行$ 0 \Leftrightarrow$ 原问题不可行见 29.5-6恢复目标函数删除 $x_0$ 后用 29.5-1 的替换公式 $c_j c_j - c_i a_{ij}$ 逐项更新系数且目标常数项 $v$ 需一并更新无界判定目标函数中有正系数非基变量但所有约束对该变量的系数均 $\le 0$见 29.5-7 与 Lemma 29.2。如需进一步练习可继续研读本章综合题29-2 互补松弛性、29-3 整数线性规划、29-4 Farkas 引理 与 29-5 最小费用环流它们从不同侧面继续使用本文的两阶段单纯形技术与对偶工具。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐axiom-sre Slack 多工作区命令行速查从配置到生产事故沟通的完整实操指南axiom sre Slack 多工作区命令行速查从配置到生产事故沟通的完整实操指南 axiom sre 是当前仓库Skill Plugin Regis文档教程教育CLRS 第 29.3 节《单纯形算法》习题全解PIVOT 正确性证明与 SIMPLEX 手算实战CLRS 第 29.3 节《单纯形算法》习题全解PIVOT 正确性证明与 SIMPLEX 手算实战 导读 本篇围绕 docs/Chap29/29.3.md h文档教程教育SciPy linprog(methodsimplex) 完全指南两阶段单纯形法的 API、算法原理与实战SciPy linprog methodsimplex 完全指南两阶段单纯形法的 API、算法原理与实战 导读 scipy.optimize.linpr科学计算数据科学高性能计算上一篇Vitess v23.0.5 发布说明深度解析连接池、VTGate 规划器、VTOrc 恢复与安全修复全景下一篇react-jsonschema-form v5 自定义模板Custom Templates完全指南16 类模板的 Props、uiSchema 覆盖与源码级实现原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考