如何证明我们不能在 LP 中有 X(j)+ 和 X(j) - 同时为正数？
How to prove that that we can not have X(j)+ and X(j) - simultaneously positive in an LP?
众所周知，在线性规划问题中，任何变量x(j)都可以用2个非负变量之间的差来代替。
X(j) = X(j)+ - X(j)-
我们怎么知道在基本解决方案中，我们永远不可能同时使 X(j)+ 和 X(j)- 严格为正？
我是否需要假设一个问题并通过将每个变量拆分为 x+ - x- 来解决它？但这最终不会向我证明任何事情..
首先：教科书通常说Simplex方法只能处理non-negative个变量。这是错误的：LP 求解器可以直接处理自由变量。即使我们可以使用自由变量，我们仍然可以在一些有趣的建模案例中使用变量拆分。
如果 objective 最小化 |X|（即它最小化 Xplus + Xmin），我们知道 Xplus 和 Xmin 不能都为非零。
还有一个更奇特的论点。如果 LP 矩阵列 Xplus 和 Xmin 除了符号相同，它们不能同时出现在基中（如果出现，基矩阵 B 将是奇异的）。这个说法当然跟单纯形法有关。
但有些情况下 Xplus 和 Xmin 都可以是非零的。这有时称为 non-convexity。在那种情况下，需要添加一个二进制变量 B with:
Xplus <= M*B
Xmin <= M*(1-B)
通常这无关紧要：因为您对 x 的值感兴趣，例如 (5, 5) 和 (0, 0) 都是同一解 x=0 的有效表示。
为什么需要其中一个值为 0？
众所周知，在线性规划问题中，任何变量x(j)都可以用2个非负变量之间的差来代替。
X(j) = X(j)+ - X(j)-
我们怎么知道在基本解决方案中，我们永远不可能同时使 X(j)+ 和 X(j)- 严格为正？
我是否需要假设一个问题并通过将每个变量拆分为 x+ - x- 来解决它？但这最终不会向我证明任何事情..
首先：教科书通常说Simplex方法只能处理non-negative个变量。这是错误的：LP 求解器可以直接处理自由变量。即使我们可以使用自由变量，我们仍然可以在一些有趣的建模案例中使用变量拆分。
如果 objective 最小化 |X|（即它最小化 Xplus + Xmin），我们知道 Xplus 和 Xmin 不能都为非零。
还有一个更奇特的论点。如果 LP 矩阵列 Xplus 和 Xmin 除了符号相同，它们不能同时出现在基中（如果出现，基矩阵 B 将是奇异的）。这个说法当然跟单纯形法有关。
但有些情况下 Xplus 和 Xmin 都可以是非零的。这有时称为 non-convexity。在那种情况下，需要添加一个二进制变量 B with:
Xplus <= M*B
Xmin <= M*(1-B)
通常这无关紧要：因为您对 x 的值感兴趣，例如 (5, 5) 和 (0, 0) 都是同一解 x=0 的有效表示。
为什么需要其中一个值为 0？