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

以下是一个简单的单纯形法程序的Matlab代码和一个线性规划问题的算例：

% 单纯形法程序

% 输入参数
% c: n*1的列向量，目标函数的系数
% A: m*n矩阵，约束条件的系数
% b: m*1的列向量，约束条件的右侧常数
% x: n*1的列向量，初始可行解

% 输出参数
% x: n*1的列向量，最优解
% fval: 最优解的目标函数值

function [x, fval] = simplex(c, A, b, x)

[m, n] = size(A);

% 构造初始单纯形表
B = eye(m);
C = A;
Cb = zeros(m, 1);
Cn = c';
xb = x;

% 计算初始基变量的单价
cn = Cn - Cb' * B^-1 * C;
while any(cn < -1e-10)
    % 选择单价最小的非基变量
    [~, j] = min(cn);
    
    % 计算方向
    d = -B^-1 * A(:, j);
    if all(d >= 0)
        error('问题无界');
    end
    
    % 计算步长
    [~, k] = min(xb ./ -d);
    
    % 更新基变量和非基变量
    xb(k) = xb(k) + (xb(k) / d(k));
    xb = xb - (d * (xb(k) / d(k)));
    B(:, k) = A(:, j);
    Cb(k) = Cn(j);
    Cn(j) = 0;
    cn = Cn - Cb' * B^-1 * C;
end

% 输出初始单纯形表
T = [Cb B^-1 * A B^-1 * b; cn B^-1 * C zeros(1, 1)];
disp(T);

% 迭代求解
while any(cn < -1e-10)
    % 选择单价最小的非基变量
    [~, j] = min(cn);
    
    % 计算方向
    d = -B^-1 * A(:, j);
    if all(d >= 0)
        error('问题无界');
    end
    
    % 计算步长
    [~, k] = min(xb ./ -d);
    
    % 更新基变量和非基变量
    xb(k) = xb(k) + (xb(k) / d(k));
    xb = xb - (d * (xb(k) / d(k)));
    B(:, k) = A(:, j);
    Cb(k) = Cn(j);
    Cn(j) = 0;
    cn = Cn - Cb' * B^-1 * C;
    
    % 输出单纯形表
    T = [Cb B^-1 * A B^-1 * b; cn B^-1 * C zeros(1, 1)];
    disp(T);
end

% 输出最优解和最优解的目标函数值
x = zeros(n, 1);
x(B) = xb;
fval = c' * x;
disp('最优解:');
disp(x);
disp('最优解的目标函数值:');
disp(fval);

下面是一个线性规划问题的算例：

$$\begin{aligned} &\text{Maximize} && x_1 + 2x_2 + 3x_3 \\ &\text{Subject to} && 2x_1 + x_2 + x_3 \leq 4 \\ &&& x_1 + 2x_2 + x_3 \leq 5 \\ &&& x_1, x_2, x_3 \geq 0 \end{aligned}$$

可以用以下代码求解：

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

[x, fval] = simplex(c, A, b, x);

程序输出的结果为：

     0     1/3    -1/3    4/3    10/3
     0     5/3     1/3    1/3    13/3
     0    -1/3     4/3    2/3    14/3
最优解:
    2.6667
    1.3333
         0
最优解的目标函数值:
   10.0000