用Octave计算线性规划问题（对偶单纯形法）
广告
{{v.name}}
对偶单纯形法是求解线性规划的经典算法，核心优势是：当线性规划的初始解满足 检验数最优性条件，但约束右端项存在负数（原问题不可行、对偶问题可行）时，无需引入人工变量，可直接迭代求解，效率高于原始单纯形法。
对偶单纯形法的适用条件
线性规划需满足 对偶可行、原不可行 的初始状态：
1. 最优性条件：目标函数的检验数满足 \(\sigma_j \le 0\)（最大化问题），或 \(\sigma_j \ge 0\)（最小化问题）。
2. 不可行条件：约束右端项 \(b_i\) 中存在负数。
对偶单纯形法的迭代步骤（最大化问题）
以标准型线性规划（约束为等式、\(b_i\) 可正可负、\(x_j \ge 0\)）为例，步骤如下：
1. 构建初始单纯形表
表的结构与原始单纯形法一致：
| 基变量 | \(x_1\) | \(x_2\) | ... | \(x_n\) | 右端项 \(b_i\) |
|--------|-------|-------|-----|-------|----------|-------------|------|
| \(x_{B1}\) | \(a_{11}\) | \(a_{12}\) | ... | \(a_{1n}\) | \(b_1\) |
| \(x_{B2}\) | \(a_{21}\) | \(a_{22}\) | ... | \(a_{2n}\) | \(b_2\) |
| ... | ... | ... | ... | ... | ... | ... | ... |
| \(Z\) | \(\sigma_1\) | \(\sigma_2\) | ... | \(\sigma_n\) | \(Z_0\) |
对偶单纯形法的迭代步骤
线性规划需满足 对偶可行、原不可行 的初始状态：
1. 最优性条件：目标函数的检验数满足 \(\sigma_j \le 0\)（最大化问题），或 \(\sigma_j \ge 0\)（最小化问题）。
检查右端项 \(b_i\)：
- 若 所有 \(b_i \ge 0\) → 当前解为原问题最优解，迭代终止。
- 若 存在 \(b_i < 0\) → 进入迭代。
3. 确定出基变量
选择 \(b_i\) 最小的行 对应的基变量为出基变量，记行号为 \(r\)，即：
\(\min\{b_i | i=1,2,...,m\} = b_r\)
4. 确定入基变量和出基变量
- 入基变量：选择检验数 \(\sigma_j\) 最大的非基变量 \(x_k\)
- 出基变量：计算比值 \(\frac{b_i}{a_{ik} }\)（\(a_{ik} > 0\)），选择比值最小的基变量 \(x_r\)
- 入基变量和出基变量的交点 \(a_{rk}\) 称为主元
5. 主元变换（高斯消元）
- 主元行：除以主元 \(a_{rk}\)，使主元变为 1
- 其他行：通过行变换，使主元列的其他元素变为 0
6. 迭代更新单纯形表，重复步骤 3-5，直到满足最优性条件
特殊情况处理
- 无可行解：当迭代结束后，人工变量仍在基变量中
- 无界解：当入基变量对应的列系数全部 \(\le 0\)，比值无意义
例子：
\( \max\ Z = -10x_1 + 6x_2 - 4x_3 \\ \)
\( s.t. \begin{cases} x_1 + x_2 - x_3 \le 100 \\ 10x_1 - 4x_2 + 5x_3 \le 600 \\ -2x_1 + 2x_2 + 6x_3 \le 300 \\ x_1,x_2,x_3 \ge 0 \end{cases} \)
定义目标函数系数（max Z = -10x1 + 6x2 - 4x3），代码如下：
>> c = [-10, 6, -4]';
定义约束系数矩阵 A，代码如下：
>> A = [ 1, 1, -1;
     10, -4, 5;
      -2, 2, 6];
定义约束右端项 b，代码如下：
>> b = [100, 600, 300]';
定义变量下界，代码如下：
>> lb = [0, 0, 0]';
变量无上界，代码如下：
>> ub = [];
定义约束类型：3个约束都是 ≤，对应 'UUU'，代码如下：
>> ctype = "UUU";
定义变量类型：3个变量都是连续变量，对应 'CCC'，代码如下：
>> vartype = "CCC";
定义优化方向：最大化模型（-1），代码如下：
>> s = -1;
定义解算器为单纯形法（默认就是单纯形法），代码如下：
>> param.lpsolver = 1;
使用对偶单纯形法，代码如下：
>> param.dual = 3;
（可选）如果不知道能否使用对偶单纯形法，可以在使用对偶单纯形法失败时自动重试单纯形法，代码如下：
>> # param.dual = 2;
定义单纯形法迭代次数为最大100次，代码如下：
>> param.itlim = 100;
求解，代码如下：
>> [xmin, fmin, status, extra] = ...
   glpk (c, A, b, lb, ub, ctype, vartype, s, param)
xmin =

          0
   112.5000
    12.5000

fmin = 625
status = 0
extra =

  scalar structure containing the fields:

    lambda =

       5.5000
            0
       0.2500

    redcosts =

      -15
        0
        0

    time = 0
    status = 5
友链