使用MATLAB解决标准形式线性规划问题的单纯形方法程序及算例黄金分割法

以下是MATLAB代码实现标准形式线性规划问题的单纯形方法：

function [x, fval, exitflag] = simplex(c, A, b)
% c: n x 1列向量，目标函数系数
% A: m x n矩阵，约束矩阵
% b: m x 1列向量，约束条件的右侧向量

[m, n] = size(A); % m个约束，n个变量

% 添加松弛变量
A = [A eye(m)];
c = [c; zeros(m, 1)];

% 初始基变量下标
B = n+1:n+m;
% 初始非基变量下标
N = 1:n;

while true
    % 计算当前基变量的解
    x = zeros(n+m, 1); % 初始化为0向量
    x(B) = A(:, B) \ b;
    % 计算当前目标函数值
    fval = c(B)' * x(B);
    
    % 判断是否满足终止条件
    if all(A(:, N)' * x(N) <= c(N)') % 所有非基变量的系数都小于等于0
        exitflag = 0; % 最优解
        x = x(1:n); % 去除松弛变量
        return
    end
    
    % 取非基变量中系数最大的作为入基变量
    [~, j] = max(A(:, N)' * x(N) - c(N)');
    
    % 判断是否存在可行解
    if all(A(:, B) \ A(:, N(j)) <= 0) % 所有系数都小于等于0
        exitflag = -1; % 无界解
        x = NaN(n, 1);
        return
    end
    
    % 计算各个变量的变化量
    d = zeros(n+m, 1);
    d(N(j)) = 1; % 入基变量
    d(B) = -A(:, B) \ A(:, N(j)); % 基变量
    
    % 取最小的d(B)作为出基变量
    [~, k] = min(-x(B) ./ d(B));
    
    % 更新基变量和非基变量
    B(k) = N(j);
    N(j) = [];
end

下面是一个算例：

$$
\begin{aligned}
\text{maximize} \quad & 2x_1 + x_2 \\
\text{subject to} \quad & x_1 + 2x_2 \leq 6 \\
& 2x_1 + x_2 \leq 5 \\
& x_1, x_2 \geq 0
\end{aligned}
$$

转化为标准形式：

$$
\begin{aligned}
\text{maximize} \quad & 2x_1 + x_2 \\
\text{subject to} \quad & x_1 + 2x_2 + x_3 = 6 \\
& 2x_1 + x_2 + x_4 = 5 \\
& x_1, x_2, x_3, x_4 \geq 0
\end{aligned}
$$

使用上述函数进行求解：

c = [2; 1; 0; 0];
A = [1 2 1 0; 2 1 0 1];
b = [6; 5];
[x, fval, exitflag] = simplex(c, A, b);
disp(x); % [1; 2]
disp(fval); % 4
disp(exitflag); % 0

因此，最优解为 $x_1=1, x_2=2$，目标函数值为4。