0

我在 Matlab/Octave 中实现(双)单纯形算法。

我的算法适用于一个小的测试问题,但是一旦我尝试像 afiro.mps 这样更大的问题(来自http://www.netlib.org/lp/data/),我就会收到警告“matrix single to machine精度,rcond=0" 和 octave 会引发错误(或不终止)。确切的命令是:

x = zeros(n,1);
x(B) = A(:,B) \ b; % Compute primal variables
y = A(:,B)' \ c(B); % Compute dual variables

问题是标准形式

min c*x
s.t. Ax=b
x>=0

A 是一个 mxn 矩阵,B 是非活动约束(基本变量)的索引向量。当我在做一个两阶段单纯形时,我选择 1:size(A,1) 作为对偶单纯形的初始基础。

该问题是通过自编码阅读器从 mps 文件中读取的。我希望正确读取 mps 文件,因为当 glpk 函数将 A、b、c 作为输入参数时,它可以正确解决问题。

有什么方法可以避免警告还是我的编码有错误?

4

1 回答 1

0

The basis matrices of linear programming problems usually have very bad condition numbers. This is one the difficulties when implementing a stable simplex algorithm.

You should have a look at this paper that explains this phenomenon: On the Factorization of Simplex Basis Matrices

于 2015-11-10T07:28:39.720 回答