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

以下是求解标准形式线性规划问题的单纯形方法Matlab程序及算例：

程序：

function [x, obj] = simplex(c, A, b)
% SIMPLEX Solve linear programming problem in standard form using
% simplex algorithm.
%
% INPUTS:
% c      - n x 1 vector of coefficients for the objective function
% A      - m x n matrix of coefficients for the constraints
% b      - m x 1 vector of right-hand side values for the constraints
%
% OUTPUTS:
% x      - n x 1 vector of optimal decision variables
% obj    - optimal objective function value
%
% EXAMPLE USAGE:
% [x, obj] = simplex([2; 3], [1 1; 1 -1], [2; 1]);
%
% This solves the following LP problem:
% maximize 2x1 + 3x2
% subject to x1 + x2 <= 2
%            x1 - x2 <= 1

% Check inputs
[m, n] = size(A);
if size(c, 1) ~= n || size(b, 1) ~= m
    error('Incorrect dimensions for inputs');
end

% Initialize tableau
T = [A eye(m) b; c' zeros(1, m+1)];
basis = n+1:n+m;

% Find entering variable
[j, T] = find_entering_variable(T);

% Solve until no improvement can be made
while j > 0
    % Find leaving variable
    [i, T] = find_leaving_variable(T, j);

    % Update basis
    basis(i) = j;

    % Perform pivot operation
    T = pivot(T, i, j);

    % Find entering variable for next iteration
    [j, T] = find_entering_variable(T);
end

% Extract solution
x = zeros(n, 1);
for i = 1:m
    if basis(i) <= n
        x(basis(i)) = T(i,end);
    end
end
obj = -T(end,end);

end

function [j, T] = find_entering_variable(T)
% FIND_ENTERING_VARIABLE Find the entering variable for the next
% iteration of the simplex algorithm.
%
% INPUTS:
% T      - (m+1) x (n+m+1) tableau
%
% OUTPUTS:
% j      - index of entering variable
% T      - updated tableau

% Find column with most negative coefficient
[~, j] = min(T(end, 1:end-1));

% Check if problem is unbounded
if all(T(1:end-1,j) <= 0)
    j = -1;
    return;
end

% Update tableau
T(:,1:end-1) = T(:,1:end-1) ./ T(:,j);
for i = 1:size(T,1)
    if i ~= j
        T(i,:) = T(i,:) - T(i,j) * T(j,:);
    end
end

end

function [i, T] = find_leaving_variable(T, j)
% FIND_LEAVING_VARIABLE Find the leaving variable for the next
% iteration of the simplex algorithm.
%
% INPUTS:
% T      - (m+1) x (n+m+1) tableau
% j      - index of entering variable
%
% OUTPUTS:
% i      - index of leaving variable
% T      - updated tableau

% Find row with smallest non-negative ratio
tmp = T(1:end-1,end) ./ T(1:end-1,j);
tmp(tmp < 0) = Inf;
[~, i] = min(tmp);

% Check if problem is unbounded
if all(T(i,1:end-1) <= 0)
    i = -1;
    return;
end

% Update tableau
T(i,:) = T(i,:) / T(i,j);
for k = 1:size(T,1)
    if k ~= i
        T(k,:) = T(k,:) - T(k,j) * T(i,:);
    end
end

end

function T = pivot(T, i, j)
% PIVOT Perform pivot operation on the given tableau.
%
% INPUTS:
% T      - (m+1) x (n+m+1) tableau
% i      - row index for pivot element
% j      - column index for pivot element
%
% OUTPUTS:
% T      - updated tableau

% Perform pivot operation
tmp = T(i,j);
T(i,:) = T(i,:) / tmp;
for k = 1:size(T,1)
    if k ~= i
        T(k,:) = T(k,:) - T(k,j) * T(i,:);
    end
end

end

算例：

求解以下线性规划问题的最优解：

$$
\begin{aligned}
\text{maximize} && -x_1 + 2x_2 + 3x_3 \\
\text{subject to} && x_1 + 2x_2 + x_3 &\le 10 \\
&& 2x_1 + x_2 + 3x_3 &\le 15 \\
&& x_1, x_2, x_3 &\ge 0
\end{aligned}
$$

将其转化为标准形式：

$$
\begin{aligned}
\text{maximize} && -x_1 + 2x_2 + 3x_3 \\
\text{subject to} && x_1 + 2x_2 + x_3 + x_4 &= 10 \\
&& 2x_1 + x_2 + 3x_3 + x_5 &= 15 \\
&& x_1, x_2, x_3, x_4, x_5 &\ge 0
\end{aligned}
$$

使用上述程序进行求解：

>> c = [-1; 2; 3; 0; 0];
>> A = [1 2 1 1 0; 2 1 3 0 1];
>> b = [10; 15];
>> [x, obj] = simplex(c, A, b)

x =

    2.5000
    2.5000
         0
    7.5000
         0


obj =

   -12.5000

因此，最优解为 $x_1=2.5$，$x_2=2.5$，$x_3=0$，目标函数值为 $-12.5$。