如何在 MATLAB 中获得 LP 的最优基矩阵 B？
How to obtain optimal basis matrix B for LP in MATLAB?
我正在解决一个标准的 LP 问题：
min C'*x
S.t. A*x=b;x>=0;
通过linprog得到解后，想得到那个解对应的最优基B。非 MATLAB 提供的单纯形代码对于大规模问题非常慢。
我的问题有退化。
非退化 LP 的最佳基础由 lambda = 0 给出，其中 lambda 是拉格朗日乘数。在 MATLAB 中，lambda 可用作最终输出，即
[x,fval,exitflag,output,lambda] = linprog(___)
所以要找到基础，只需键入 k = find(lambda == 0)。
但是，从数值的角度来看，零的值是有问题的（在浮点运算中几乎没有什么是完全为 0 的），因此您可能想要解决 k = find(lambda <= 1e-5) 这样的问题。但是，同样，根据问题（以及它的表现如何），这也可能不正确。
那么，你能做什么？基本上有两种解决方法：
- 使用商业求解器：商业求解器在拉格朗日乘数的准确性方面往往要好得多，尤其是对于定义不当的问题。试试 Gurobi 或 CPLEX，如果你是大学生，它们都是免费的。他们有类似的方法来获取 lambda，但根据我的经验，它们更可靠。
- 使用约束值：你基本上做
k = find(x > 1e-5)，然后看看它给你的结果。这会遇到与使用拉格朗日量相同的挫折，但它可能会有所帮助。
但是，如果发生原始退化和双重退化，您仍然需要处理。不要深入太多，但基本上你需要始终检查你是否有 n 个活动约束（n 是优化变量的数量）。如果您的数量多于或少于该数量，那么您就有问题了，您需要为此对您的代码进行适当的检查。
我正在解决一个标准的 LP 问题：
min C'*x
S.t. A*x=b;x>=0;
通过linprog得到解后，想得到那个解对应的最优基B。非 MATLAB 提供的单纯形代码对于大规模问题非常慢。
我的问题有退化。
非退化 LP 的最佳基础由 lambda = 0 给出，其中 lambda 是拉格朗日乘数。在 MATLAB 中，lambda 可用作最终输出，即
[x,fval,exitflag,output,lambda] = linprog(___)
所以要找到基础，只需键入 k = find(lambda == 0)。
但是，从数值的角度来看，零的值是有问题的（在浮点运算中几乎没有什么是完全为 0 的），因此您可能想要解决 k = find(lambda <= 1e-5) 这样的问题。但是，同样，根据问题（以及它的表现如何），这也可能不正确。
那么，你能做什么？基本上有两种解决方法：
- 使用商业求解器：商业求解器在拉格朗日乘数的准确性方面往往要好得多，尤其是对于定义不当的问题。试试 Gurobi 或 CPLEX，如果你是大学生，它们都是免费的。他们有类似的方法来获取 lambda，但根据我的经验，它们更可靠。
- 使用约束值：你基本上做
k = find(x > 1e-5)，然后看看它给你的结果。这会遇到与使用拉格朗日量相同的挫折，但它可能会有所帮助。
但是，如果发生原始退化和双重退化，您仍然需要处理。不要深入太多，但基本上你需要始终检查你是否有 n 个活动约束（n 是优化变量的数量）。如果您的数量多于或少于该数量，那么您就有问题了，您需要为此对您的代码进行适当的检查。