实现单纯形法无限循环

Question

我正在尝试按照优化课程中给出的规则实施单纯形算法。问题是

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

假设所有向量都是列，'表示转置。该算法还应该return对偶LP的解决方案。遵循的规则是：

这里，A_J 表示 A 中索引在 J 中的列，x_J，x_K 分别表示向量 x 中索引在 J 或 K 中的元素。向量a_s是矩阵A的第s列。

现在我不明白这个算法是如何处理条件 x >= 0，但我决定试一试并逐步遵循它。我为此使用了 Matlab 并得到了以下代码。

X = zeros(n, 1);
Y = zeros(m, 1);

% i. Choose starting basis J and K = {1,2,...,n} \ J
J = [4 5 6]  % for our problem
K = setdiff(1:n, J)

% this while is for goto
while 1
    % ii. Solve system A_J*\bar{x}_J = b.
    xbar = A(:,J) \ b

    % iii. Calculate value of criterion function with respect to current x_J.
    fval = c(J)' * xbar

    % iv. Calculate dual solution y from A_J^T*y = c_J.
    y = A(:,J)' \ c(J)

    % v. Calculate \bar{c}^T = c_K^T - u^T A_K. If \bar{c}^T >= 0, we have
    % found the optimal solution. If not, select the smallest s \in K, such
    % that c_s < 0. Variable x_s enters basis.
    cbar = c(K)' - c(J)' * inv(A(:,J)) * A(:,K)
    cbar = cbar'

    tmp = findnegative(cbar)
    if tmp == -1  % we have found the optimal solution since cbar >= 0
        X(J) = xbar;
        Y = y;
        FVAL = fval;
        return
    end

    s = findnegative(c, K)  %x_s enters basis

    % vi. Solve system A_J*\bar{a} = a_s. If \bar{a} <= 0, then the problem is
    % unbounded.
    abar = A(:,J) \ A(:,s)

    if findpositive(abar) == -1  % we failed to find positive number
        disp('The problem is unbounded.')
        return;
    end

    % vii. Calculate v = \bar{x}_J / \bar{a} and find the smallest rho \in J,
    % such that v_rho > 0. Variable x_rho exits basis.
    v = xbar ./ abar
    rho = J(findpositive(v))

    % viii. Update J and K and goto ii.
    J = setdiff(J, rho)
    J = union(J, s)
    K = setdiff(K, s)
    K = union(K, rho)
end

函数 findpositive(x) 和 findnegative(x, S) return x 中正值或负值的第一个索引。 S 是我们查看的索引集。如果省略 S，则检查整个向量。出于调试目的省略了分号。

我测试这段代码的问题是

c = [-3 -1 -3 zeros(1,3)];
A = [2 1 1; 1 2 3; 2 2 1];
A = [A eye(3)];
b = [2; 5; 6];

zeros(1,3)和eye(3)的原因是问题是不平等，我们需要松弛变量。我已将起始基础设置为 [4 5 6]，因为注释中说起始基础应设置为松弛变量。

现在，执行期间发生的事情是，在 while 的第一个运行处，索引为 1 的变量进入基础（在 Matlab 中，索引从 1 开始）和 4 退出它，这是合理的。在第二个运行上，2 进入基础（因为它是 c(idx) < 0 和 1 离开它的最小索引。但是现在在下一次迭代中，1 再次进入 basis，我理解它为什么进入，因为它是最小的索引，例如 c(idx) < 0。但是循环从这里开始。我认为这不应该发生，但是按照规则我看不出如何防止这种情况。

我猜我对笔记的理解一定有问题，但我就是看不出我错在哪里。我还记得当我们在论文中解决 LP 时，我们每次都在更新我们的主观函数，因为当一个变量进入 basis 时，我们将它从主观函数中移除并在 subj 中表达该变量。使用等式之一的表达式函数，但我认为这是不同的算法。

任何评论或帮助将不胜感激。

Answer 1

问题已解决。原来笔记中的第7点是错误的。相反，第 7 点应该是

实现单纯形法无限循环

Implementing Simplex Method infinite loop

matlab

linear-programming

simplex-algorithm