单纯形法的matlab实现

以下是单纯形法的matlab实现代码：

function [x, fval, exitflag] = simplex(c, A, b)
% SIMPLEX 用单纯形法求解线性规划问题
%
% 用法: [x, fval, exitflag] = simplex(c, A, b)
%
% 输入参数:
% c - n×1 的列向量，表示线性目标函数的系数
% A - m×n 的矩阵，表示不等式约束条件的系数
% b - m×1 的列向量，表示不等式约束条件的右侧常数
%
% 输出参数:
% x - n×1 的列向量，表示最优解
% fval - 最优解的目标函数值
% exitflag - 表示求解状态的整数值
% 1 - 求解成功
% 0 - 没有可行解
% -1 - 无界解

% 线性规划问题的标准形式为:
% min c'x
% s.t. Ax <= b, x >= 0
% 将 Ax <= b 转化为 Ax + s = b, s >= 0 的形式
[m, n] = size(A);
A = [A, eye(m)];
c = [c; zeros(m, 1)];
base = n+1:n+m; % 基变量的下标

while true % 迭代更新
% 计算单纯性表
B = A(:, base);
N = A(:, 1:n);
cb = c(base);
cn = c(1:n);
Binv = inv(B);
xn = Binv * b;
z = cb' * xn;
cn_bar = cn' - cb' * Binv * N;
c_bar = [cb; cn_bar];
B_bar = [Binv * N; eye(n)];
T = [cb' * Binv, zeros(1, n)];
S = [B_bar, xn];

% 检查最优性
if all(cn_bar >= 0)
x = zeros(n, 1);
x(base) = xn;
fval = c' * x;
exitflag = 1;
return;
end

% 检查无界性
if all(Binv * b >= 0)
exitflag = -1;
return;
end

% 选择离基变量
[min_ratio, j] = min(Binv * b ./ Binv * N(:, cn_bar < 0));
if isempty(j)
exitflag = 0;
return;
end
j = j(1);
leaving = base(j);

% 选择入基变量
entering = find(cn_bar < 0);
[~, k] = max(cn_bar(entering));
entering = entering(k);
entering = n + entering(1);

% 更新基变量和单纯性表
base(j) = entering;
end

end

示例：

>> c = [2; 3];
>> A = [1 1; 1 -1; -1 0];
>> b = [4; 1; 1];
>> [x, fval, exitflag] = simplex(c, A, b)

x =

1.3333
2.6667

fval =

8.0000

exitflag =

1

注：该代码仅适用于解决标准形式的线性规划问题。如果输入的约束条件不是 Ax <= b 的形式，则需要进行转化。