在数学优化领域中，单纯形法是一种经典且高效的算法，主要用于解决线性规划问题。它通过逐步迭代的方式，在可行解空间内寻找目标函数的最优值。本文将介绍如何利用MATLAB编写一个基于单纯形法的程序，并提供详细的代码实现。
一、理论基础
单纯形法的核心思想是通过一系列基变换操作，从一个初始的基本可行解出发，逐步逼近最优解。其基本步骤包括：
1. 初始化：构造初始的基本可行解。
2. 检验数计算：判断当前解是否为最优解。
3. 选择入基变量：选取具有最大正检验数的变量作为入基变量。
4. 确定出基变量：根据最小比值规则确定出基变量。
5. 基变换：更新基矩阵并重新计算新的解。
6. 终止条件：当所有检验数均非正时，停止迭代。
二、MATLAB实现
以下是一个完整的MATLAB程序示例，用于求解标准形式下的线性规划问题：
```matlab
function [x, fval] = simplex_method(c, A, b)
% 输入参数:
% c - 目标函数系数向量 (行向量)
% A - 约束矩阵 (二维数组)
% b - 约束右侧常数向量 (列向量)
m = size(A, 1); % 约束方程的数量
n = size(A, 2); % 决策变量的数量
% 构造增广矩阵
B = eye(m);
A_aug = [A, B];
c_aug = [c, zeros(1, m)];
% 初始化变量
x = zeros(n + m, 1);
basis = (n + 1):(n + m);
while true
% 计算检验数
N = setdiff(1:(n + m), basis);
c_N = c_aug(N);
c_B = c_aug(basis);
invB = inv(A_aug(:, basis));
d = c_N - c_B invB A_aug(:, N)';
% 检查是否达到最优
if all(d <= 0)
break;
end
% 选择入基变量
[~, k] = max(d);
j = N(k);
% 计算最小比值
ratios = inf ones(m, 1);
for i = 1:m
if A_aug(i, j) > 0
ratios(i) = b(i) / A_aug(i, j);
end
end
[~, l] = min(ratios);
% 更新基变量
old_basis = basis(l);
basis(l) = j;
% 基变换
pivot_col = A_aug(:, j);
pivot_row = invB(l, :);
pivot_value = A_aug(l, j);
A_aug = A_aug - pivot_row' pivot_col / pivot_value;
A_aug(l, :) = pivot_row / pivot_value;
end
% 提取最优解
x(basis) = inv(A_aug(:, basis)) b;
fval = c_aug x;
end
```
三、应用实例
假设我们有如下线性规划问题：
\[
\text{minimize } z = 3x_1 + 2x_2
\]
\[
\text{subject to: }
\begin{cases}
x_1 + x_2 \leq 4 \\
2x_1 + x_2 \leq 5 \\
x_1, x_2 \geq 0
\end{cases}
\]
对应的MATLAB调用方式如下：
```matlab
c = [3, 2]; % 目标函数系数
A = [1, 1; 2, 1]; % 约束矩阵
b = [4; 5]; % 约束右侧常数
[x, fval] = simplex_method(c, A, b);
disp('Optimal Solution:');
disp(x);
disp(['Objective Value: ', num2str(fval)]);
```
运行结果将输出最优解及其对应的目标函数值。
四、总结
通过上述方法，我们可以轻松地在MATLAB环境中实现单纯形法，从而解决各种线性规划问题。该程序结构清晰，易于扩展，适用于教学和实际工程中的多种场景。希望本文能为读者提供有益的帮助！
