### 单纯形算法MATLAB编程报告
#### 概述
本报告主要介绍了一种用于求解线性规划问题的经典算法——单纯形算法，并通过MATLAB编程实现了该算法。线性规划是在一组线性等式或不等式的约束条件下，求解线性目标函数最大值或最小值的问题。单纯形算法是一种有效解决这类问题的方法，它通过迭代的方式逐步改善解的质量，最终找到最优解。
#### 单纯形算法简介
单纯形算法的基本思想是通过在可行域内的顶点间移动来寻找最优解。对于一个标准线性规划问题（例如求极小问题），其数学模型可以表示为：
\[ \min z = c^T x \]
\[ s.t. Ax = b, x \geq 0 \]
其中，\( A \) 是系数矩阵，\( b \) 是右端项向量，\( c \) 是成本向量，而 \( x \) 是决策变量向量。单纯形算法的步骤如下：
1. **初始化**：给定一个初始基本可行解，通常选择由松弛变量组成的初始基。
2. **计算检验数**：对于当前基本可行解，计算检验数 \( \Delta_j \)，检验数决定了解是否已经是最优解。
3. **确定进基变量**：如果存在某个检验数 \( \Delta_j > 0 \)，则选择最大的 \( \Delta_j \) 对应的变量作为进基变量。
4. **确定离基变量**：通过计算最小比值规则确定离基变量，以保持解的可行性。
5. **更新基**：通过高斯消元法更新基，得到新的基本可行解。
6. **重复步骤2-5**，直到所有检验数均小于等于0，此时得到的是最优解。
#### 算法实现
MATLAB代码如下所示：
```matlab
clear; clc;
A = input('A=');
b = input('b=');
c = input('c=');
format rat;
[m, n] = size(A);
E = 1:m; E = E';
F = n-m+1:n; F = F';
D = [E, F];
X = zeros(1, n);
if (n < m)
fprintf('不符合标准形式需引入松弛变量\n');
flag = 0;
else
flag = 1;
B = A(:, n-m+1:n);
cB = c(n-m+1:n);
while flag
w = cB / B;
panbieshu = w * A - c;
[z, k] = max(panbieshu);
if (z < 0)
flag = 0;
fprintf('已找到最优解!\n');
xB = (B \ b')';
f = cB * xB';
for i = 1:n
mark = 0;
for j = 1:m
if (D(j, 2) == i)
mark = 1;
X(i) = xB(D(j, 1));
end
end
if (mark == 0)
X(i) = 0;
end
end
fprintf('基向量为: %s\n', X);
fprintf('目标函数值为: %s\n', f);
else
if (B \ A(:, k) <= 0)
flag = 0;
fprintf('此问题不存在最优解!\n');
else
b1 = B \ b';
temp = inf;
for i = 1:m
if ((A(i, k) > 0) && (b1(i) / (A(i, k) + eps) < temp))
temp = b1(i) / A(i, k);
r = i;
end
end
fprintf('x(%d) 进基，x(%d) 离基\n', k, D(r, 2));
B(:, r) = A(:, k);
cB(r) = c(k);
D(r, 2) = k;
end
end
end
end
```
#### 使用方法及实例
在MATLAB命令窗口中，首先运行 `rundanchunxing11zly` 函数，然后根据提示输入矩阵 `A`、向量 `b` 和向量 `c`。
**示例**:
假设我们要求解以下线性规划问题：
\[ \min z = x_1 - 2x_2 \]
\[ s.t. x_1 + x_2 - 2x_3 + x_4 = 10 \]
\[ 2x_1 - x_2 + 4x_5 = 8 \]
\[ -x_1 + 2x_2 - 4x_6 = 4 \]
\[ x_i \geq 0, i = 1, 2, 3, 4, 5, 6 \]
输入矩阵：
```matlab
A = [1 1 -2 1 0 0; 2 -1 4 0 1 0; -1 2 -4 0 0 1];
b = [10; 8; 4];
c = [1 -2 1 0 0 0];
```
运行程序后，得到的结果为：
```
w =
0 0 0
panbieshu =
-1 -2 -1 0 0 0
z =
2
k =
2
确定下标并选择进基变量和离基变量为
ans =
10
-8
2
x(2) 进基，x(6) 离基
B =
1 0 1
0 1 -1
0 0 2
cB =
0 0 -2
w =
0 0 -1
panbieshu =
0 0 3 0 0 -1
z =
3
k =
3
确定下标并选择进基变量和离基变量为
ans =
1/0
4
-2
x(3) 进基，x(5) 离基
B =
1 -2 1
0 4 -1
0 -4 2
cB =
0 1 -2
w =
0 -3/2 -7/4
panbieshu =
-9/4 0 0 0 -3/2 -7/4
```
由此可以看出，经过几次迭代后找到了最优解，目标函数的最小值为 \(-9/4\)，相应的最优解为 \(x_1 = 1/0\)，\(x_2 = 4\)，\(x_3 = -2\)（注意这里 \(x_1\) 的值应该是 0），其余变量为 0。
VIP享7折，此内容立减5.97元 
