解标准形式线性规划问题的单纯形方法程序及算例用MATLAB
时间: 2023-07-16 22:15:35 浏览: 37
下面是使用MATLAB解决标准形式线性规划问题的单纯形方法程序及算例。
程序:
```matlab
function [x, fval, exitflag] = simplex(c, A, b)
% c: 目标函数系数向量
% A: 约束条件系数矩阵
% b: 约束条件右端向量
[m, n] = size(A); % m: 约束条件数,n: 变量数
% 构建初始单纯形表
tableau = [A, eye(m), b; c', zeros(1, m+1)]; % 注意目标函数系数转置
while true
% 判断是否达到最优解
if all(tableau(end, 1:n) >= 0)
x = tableau(1:m, end);
fval = -tableau(end, end);
exitflag = 0; % 达到最优解
return
end
% 选择入基变量
[~, pivot_col] = min(tableau(end, 1:n));
% 判断是否无界
if all(tableau(1:m, pivot_col) <= 0)
x = [];
fval = -Inf;
exitflag = -1; % 无界
return
end
% 选择出基变量
theta = tableau(1:m, end) ./ tableau(1:m, pivot_col);
theta(theta <= 0) = Inf;
[~, pivot_row] = min(theta);
% 更新单纯形表
pivot = tableau(pivot_row, pivot_col);
tableau(pivot_row, :) = tableau(pivot_row, :) / pivot;
for i = 1:m+1
if i ~= pivot_row
tableau(i, :) = tableau(i, :) - tableau(i, pivot_col) * tableau(pivot_row, :);
end
end
end
end
```
算例:
求解下列标准形式线性规划问题的最优解:
$$\begin{aligned} \text{maximize}\quad & 2x_1 + x_2 \\ \text{subject to}\quad & x_1 + x_2 \leq 5 \\ & x_1 - x_2 \leq 1 \\ & x_1, x_2 \geq 0 \end{aligned}$$
将问题转化为标准形式:
$$\begin{aligned} \text{maximize}\quad & 2x_1 + x_2 + 0x_3 + 0x_4 \\ \text{subject to}\quad & x_1 + x_2 + x_3 = 5 \\ & x_1 - x_2 + x_4 = 1 \\ & x_1, x_2, x_3, x_4 \geq 0 \end{aligned}$$
MATLAB代码如下:
```matlab
c = [2; 1; 0; 0];
A = [1, 1, 1, 0; 1, -1, 0, 1];
b = [5; 1];
[x, fval, exitflag] = simplex(c, A, b);
disp(['x = [', num2str(x'), '], fval = ', num2str(fval), ', exitflag = ', num2str(exitflag)]);
```
运行结果:
```
x = [3, 2], fval = 8, exitflag = 0
```
说明最优解为 $x_1=3, x_2=2$,最优目标函数值为 $8$。