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

单纯形法是一种常用的求解标准形式线性规划问题的方法。下面是一个 Matlab 程序示例，用于求解标准形式线性规划问题：

function [x_opt, f_opt, status] = simplex(A, b, c)
% 求解标准形式线性规划问题
%
% min cx
% s.t. Ax = b, x >= 0
%
% 输入参数：
% A：约束矩阵，大小为 m x n
% b：右侧常数向量，大小为 m x 1
% c：目标函数系数向量，大小为 n x 1
%
% 输出参数：
% x_opt：最优解向量，大小为 n x 1
% f_opt：最优解，标量
% status：求解状态，0 表示成功，1 表示无界，2 表示无解

% 初始化
[m, n] = size(A);
B = eye(m);
N = setdiff(1:n, 1:m);
x_B = b;
x_N = zeros(n-m, 1);
c_B = zeros(m, 1);
c_N = c(N);
f_val = c_B' * x_B;
max_iter = 100;

% 迭代
for iter = 1:max_iter
    % 计算单纯形乘子
    c_B = c(N)' / B * A - c(N)';
    delta_x_B = B \ b;
    delta_x_N = zeros(n-m, 1);
    dual = c_B' * delta_x_B;

    % 检查是否达到最优解
    if all(delta_x_N <= 0)
        x_opt = [x_B; x_N];
        f_opt = f_val;
        status = 0;
        return;
    end

    % 计算入基变量
    [theta, j] = max(-dual);
    if theta <= 0
        status = 1;
        return;
    end

    % 计算出基变量
    delta_x = zeros(n, 1);
    delta_x(N(j)) = theta;
    delta_x_B = B \ (b - A * delta_x);

    % 更新基和非基变量
    x_B = x_B + delta_x_B;
    x_N = x_N + theta * delta_x(N);
    B(:, j) = A(:, N(j));
    N(j) = setdiff(find(~ismember(1:n, N)), find(~ismember(1:n, 1:m)));
    c_B = c(N)' / B * A - c(N)';
    f_val = c_B' * x_B;
end

status = 2;
end

这个程序使用了单纯形法的标准流程，包括初始化、计算单纯形乘子、检查是否达到最优解、计算入基变量、计算出基变量、更新基和非基变量等步骤。程序中的注释解释了每个步骤的作用。