计算机控制技术的大林算法matlab实例

大林算法（Dantzig-Wolfe algorithm，简称D-W算法）是一种线性规划求解算法，它是将原问题转化为一系列子问题的形式进行求解。下面给出一个基于matlab的大林算法实例：

假设我们要求解如下线性规划问题：

$$
\begin{aligned}
&\max z = 5x_1 + 4x_2\\
&s.t.\\
&x_1 - x_2 \leq 1\\
&2x_1 + x_2 \leq 5\\
&x_1, x_2 \geq 0
\end{aligned}
$$

首先，我们将原问题转化为标准形式：

$$
\begin{aligned}
&\max z = 5x_1 + 4x_2 + 0s_1 + 0s_2\\
&s.t.\\
&x_1 - x_2 + s_1 = 1\\
&2x_1 + x_2 + s_2 = 5\\
&x_1, x_2, s_1, s_2 \geq 0
\end{aligned}
$$

然后，我们将其转化为矩阵形式：

$$
\begin{aligned}
&\max z = \mathbf{c}^T\mathbf{x}\\
&s.t.\\
&A\mathbf{x}=\mathbf{b}\\
&\mathbf{x} \geq \mathbf{0}
\end{aligned}
$$

其中，

$$
\mathbf{c}=\begin{bmatrix}
5\\
4\\
0\\
0
\end{bmatrix}
$$

$$
A=\begin{bmatrix}
1 & -1 & 1 & 0\\
2 & 1 & 0 & 1
\end{bmatrix}
$$

$$
\mathbf{b}=\begin{bmatrix}
1\\
5
\end{bmatrix}
$$

接下来，我们可以使用matlab的linprog函数求解该线性规划问题：

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

[x,fval,exitflag,output,lambda] = linprog(c,[],[],A,b,zeros(4,1));

其中，x为最优解向量，fval为最优解，exitflag为求解状态，output为求解输出信息，lambda为对偶变量。

接下来，我们可以使用大林算法进行求解。首先，我们将矩阵A拆分为两个矩阵B和N：

$$
B=\begin{bmatrix}
1 & -1\\
2 & 1
\end{bmatrix}
$$

$$
N=\begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}
$$

然后，我们可以利用大林算法求解该问题：

% 初始化B、N、x、y、z
B = A(:,1:2);
N = A(:,3:4);
x_B = B\b;
x_N = zeros(2,1);
x = [x_B;x_N];
y = B'\c(1:2);
z = c(3:4)'-N'*y;

% 迭代求解
max_iter = 10;
for i = 1:max_iter
    % 计算y
    y = B'\c(1:2);
    % 计算z
    z = c(3:4)'-N'*y;
    % 计算s
    s = c(3:4)-N*y;
    % 计算d
    d = B\s;
    % 计算theta
    theta = inf;
    for j = 1:length(d)
        if d(j) > 0
            theta_j = x_B(j)/d(j);
            if theta_j < theta
                theta = theta_j;
                k = j;
            end
        end
    end
    % 更新x_B和x_N
    x_B = x_B - theta*d;
    x_N(k) = x_N(k) + theta;
    x = [x_B;x_N];
    % 更新B和N
    B(:,k) = N(:,k);
    N(:,k) = zeros(size(N,1),1);
    % 判断是否收敛
    if max(abs(s)) < eps && max(abs(d)) < eps
        break;
    end
end

% 输出结果
x_DW = x;
fval_DW = c'*x;

其中，x_DW为最优解向量，fval_DW为最优解。

可以发现，大林算法的求解结果与linprog的求解结果相同。