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

以下是使用MATLAB解决标准形式线性规划问题的单纯形方法程序及算例，其中使用了0.618法进行最优解的搜索。

程序：

function simplex_method(A, b, c)
% 单纯形法求解线性规划问题
% min c'x s.t. Ax=b, x>=0
% 输入参数：
% A: m*n的系数矩阵
% b: m*1的常数向量
% c: n*1的目标函数系数向量

[m, n] = size(A);
% 添加人工变量
B = eye(m);
A = [A, B];
c = [c; zeros(m, 1)];
B_inv = inv(B);
x_B = B_inv * b;
x = [x_B; zeros(n, 1)];
iter = 0;

while true
    iter = iter + 1;
    fprintf('Iteration %d:\n', iter);
    fprintf('x_B =\n');
    disp(x_B');
    fprintf('x =\n');
    disp(x');
    % 计算单位向量
    e = zeros(m, 1);
    e(iter) = 1;
    % 计算系数向量
    lambda = c' * B_inv * A - c';
    % 判断是否已达到最优解
    if all(lambda >= 0)
        fprintf('Optimal solution found:\n');
        fprintf('x_B =\n');
        disp(x_B');
        fprintf('x =\n');
        disp(x');
        fprintf('Optimal value = %f\n', c' * x);
        break;
    end
    % 计算进入变量
    [~, j] = min(lambda);
    d = B_inv * A(:, j);
    % 判断是否无界
    if all(d <= 0)
        fprintf('Unbounded solution!\n');
        break;
    end
    % 计算步长
    alpha_max = min(x_B ./ d);
    % 0.618法搜索最优解
    alpha_min = 0;
    alpha = alpha_min + 0.618 * (alpha_max - alpha_min);
    x_B_new = x_B - alpha * d;
    x_new = [x_B_new; zeros(n, 1)];
    while c' * x_new >= c' * x
        alpha_max = alpha;
        alpha = alpha_min + 0.618 * (alpha_max - alpha_min);
        x_B_new = x_B - alpha * d;
        x_new = [x_B_new; zeros(n, 1)];
    end
    % 更新解
    x_B = x_B_new;
    x = [x_B; zeros(n, 1)];
    B_inv = inv(B);
end
end

算例：

求解线性规划问题

$$\begin{aligned} \min \quad & 2x_1+3x_2+4x_3 \\ \text{s.t.} \quad & x_1+x_2+x_3=5 \\ & 2x_1+x_2+3x_3=10 \\ & x_1, x_2, x_3 \geq 0 \end{aligned}$$

将其转化为标准形式

$$\begin{aligned} \min \quad & 2x_1+3x_2+4x_3 \\ \text{s.t.} \quad & x_1+x_2+x_3+x_4=5 \\ & 2x_1+x_2+3x_3+x_5=10 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}$$

则系数矩阵 $A$、常数向量 $b$ 和目标函数系数向量 $c$ 分别为：

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

运行 `simplex_method(A, b, c)` 即可得到最优解和最优值。