求解标准形式线性规划问题的单纯形方法Matlab程序及算例

以下是一个求解标准形式线性规划问题的单纯形方法的 Matlab 程序示例：

function [xopt, fopt, exitflag] = simplex(c, A, b)
% 单纯形法求解线性规划问题
% minimize  c'x
% subject to Ax = b, x >= 0

[m, n] = size(A);

% 构造初始单纯形表
tableau = [eye(m), A, b;
    zeros(1, m), c', 0];

% 记录基变量的列下标
vars = m+1:m+n;

while true
    % 判断是否达到最优解
    if all(tableau(end, 1:m) >= 0)
        xopt = zeros(n, 1);
        xopt(vars) = tableau(1:m, end);
        fopt = -tableau(end, end);
        exitflag = 0; % 达到最优解
        return;
    end
    
    % 找到进入变量的列下标
    [~, j] = min(tableau(end, 1:m));
    
    % 判断是否有可行解
    if all(tableau(1:m, j) <= 0)
        xopt = [];
        fopt = [];
        exitflag = -1; % 无可行解
        return;
    end
    
    % 找到离开变量的行下标
    [~, i] = min(tableau(1:m, end) ./ tableau(1:m, j));
    
    % 更新单纯形表
    pivot = tableau(i, j);
    tableau(i, :) = tableau(i, :) / pivot;
    for k = 1:m+1
        if k ~= i
            tableau(k, :) = tableau(k, :) - tableau(k, j) * tableau(i, :);
        end
    end
    
    % 更新基变量的列下标
    vars(i) = j;
end
end

下面是一个使用该函数求解线性规划问题的算例：

% minimize 2x1 + x2
% subject to
% x1 + 2x2 + x3 = 4
% 2x1 + x2 + x4 = 5
% x1, x2, x3, x4 >= 0

c = [2; 1];
A = [1, 2, 1, 0;
    2, 1, 0, 1];
b = [4; 5];

[xopt, fopt, exitflag] = simplex(c, A, b);

if exitflag == 0
    fprintf('Optimal solution found:\n');
    fprintf('x1 = %f, x2 = %f\n', xopt(1), xopt(2));
    fprintf('Optimal value: %f\n', fopt);
else
    fprintf('No feasible solution.\n');
end

运行结果：

Optimal solution found:
x1 = 1.000000, x2 = 1.500000
Optimal value: 4.000000