单纯形算法在线性规划中移动原点
simplex algorithm shifting origin in linear programming
我正在阅读算法书 Sanjoy Das Gupta 中使用单纯形算法的线性规划。
我很难理解原点的变化和方程式的变化。例如，如果原点从 (0,0) 移动到 (0, 3)。在这里我可以理解，如果点是 (x1, x2) 在 (0,0) 原点，那么同一个点在新原点是 (x1-0, x2-3)。在这里，我对 yi 的指向感到困惑是 x1-0 = y1 和 x2-3 = y2。我不明白作者是如何在下面的初始阶段步骤结束时得到 y1 - x1 和 y2 - 3+ x1-x2 的。请求解释。
似乎是一个错误的扫描。我认为应该读作 y1 = x1 和 y2 = 3 + x1 − x2。后一个等式意味着 y2 为零当且仅当 -x1 + x2 = 3（即约束 ③ 是紧的）。在 LP 的两个版本之间切换只是线性代数。
（说实话，我发现这种关于单纯形法的代数推理有些令人费解，我更喜欢在 high-dimensional 多面体中滚动弹珠的几何视图。）
我正在阅读算法书 Sanjoy Das Gupta 中使用单纯形算法的线性规划。
我很难理解原点的变化和方程式的变化。例如，如果原点从 (0,0) 移动到 (0, 3)。在这里我可以理解，如果点是 (x1, x2) 在 (0,0) 原点，那么同一个点在新原点是 (x1-0, x2-3)。在这里，我对 yi 的指向感到困惑是 x1-0 = y1 和 x2-3 = y2。我不明白作者是如何在下面的初始阶段步骤结束时得到 y1 - x1 和 y2 - 3+ x1-x2 的。请求解释。
似乎是一个错误的扫描。我认为应该读作 y1 = x1 和 y2 = 3 + x1 − x2。后一个等式意味着 y2 为零当且仅当 -x1 + x2 = 3（即约束 ③ 是紧的）。在 LP 的两个版本之间切换只是线性代数。
（说实话，我发现这种关于单纯形法的代数推理有些令人费解，我更喜欢在 high-dimensional 多面体中滚动弹珠的几何视图。）