这是与基矩阵的逆相乘的几何解释。
我正在阅读标题为Dasgupta-Papadimitriou-Vairani的算法的教科书中的单纯形算法
在每次迭代中，单纯形都有两个任务：1.检查当前顶点是否最佳（如果是，则停止）。2.确定下一步要移动的位置。
我们将看到，如果顶点恰好位于起源。如果顶点在其他地方，我们将变换坐标系统将其移动到原点！
首先让我们看看为什么原点这么方便。假设我们有一些通用LP
最大c转置* x Ax <= b x> = 0
其中x是变量的向量，x =（x1;：：：; xn）。假设起源是可行的。那肯定是一个顶点，因为它是n个不等式{x1> = 0，...，xn> = 0}的唯一点紧。
现在让我们解决两个任务。任务1：
当且仅当所有ci <= 0时，原点才是最佳的”>
如果所有ci <= 0，则考虑约束x> = 0，我们不能希望以获得更好的客观价值。相反，如果某些ci> 0，则原点不是最佳的，因为我们可以通过增加目标函数养xi。
因此，对于任务2，我们可以通过增加ci> 0的xi来移动。我们可以增加多少？直到我们遇到其他限制。那是，我们释放紧约束xi> = 0并增加xi直到以前不那么宽松的其他不平等现在变得更加严峻。
那时，我们又恰好有n个严密的不等式，所以我们是在一个新的顶点。
例如，假设我们正在处理以下线性程序。
> max 2x1 + 5x2 2x1 - x2 <= 4 ----> Eq 1 x1 + 2x2 <= 9 ----> Eq 2 > -x1 + x2 <= 3 -----> Eq 3 x1 >= 0 -----------> Eq 4 x2 >= 0 -----------> Eq 5
Simplex可以从原点开始，这由约束条件指定4和5。要移动，我们释放紧约束x2> =0。因为x2是逐渐增加，遇到的第一个约束是-x1 + x2 <=3，因此它必须在x2 = 3处停止，此时新不平等现象严峻。因此，新顶点由等式3和等式给出4。
所以我们知道如果我们在原点，该怎么办。但是如果我们当前顶点u在其他地方吗？诀窍是通过以下方式将u转换为原点将坐标系从通常的（x1，...，xn）移至您的本地视图这些局部坐标由（适当地与n个超平面（不等式）的距离y1，...，yn定义并包含u：
u / \ / \ / /\ / /y1\ /----x \ y2具体来说，如果这些封闭不等式之一是ai * x <= bi，那么从点x到特定“墙”的距离为yi =bi-ai * x
此类型的n个方程，每壁一个，将yi定义为线性的功能，这种关系可以反过来将xi表示为yi的线性函数。这样我们可以重写整个LP的y值。这从根本上没有改变它（例如，最优值保持不变），但将其表示出来在不同的坐标系中。修改后的本地LP具有以下三个属性：
修订后的本地LP具有以下三个属性：1.它包括不等式y> = 0，它们只是定义u的不等式的变换形式。2. u本身是y空间的原点。3.成本函数变为max cu +〜cT * y，其中cu是目标函数在u处的值，而〜c是转换后的成本向量。
我难以理解下面提到的上述陈述中的技巧：
诀窍是通过将坐标系从通常从您到本地视图（x1，...，xn）。这些局部坐标由（适当地y y，...，y y定义和包围u的n个超平面（不等式）： 作者在上述陈述中将坐标系从“ u”移到局部视图是什么意思？ 局部坐标由到n个超平面的距离组成是什么意思？
请解释
提前感谢您的时间和帮助
[我正在阅读标题为Dasgupta-Papadimitriou-Vairani的算法的教科书中的单纯形算法。在每次迭代中，单纯形都有两个任务：1.检查当前顶点是否是最优的（如果是，...
这是与基矩阵的逆相乘的几何解释。
这是与基矩阵的逆相乘的几何解释。