用Octave计算线性规划问题（单纯形法）
广告
{{v.name}}
单纯形法（适用于 n 个决策变量）
当变量数 \(\ge 3\) 时，图解法失效，此时必须用单纯形法，核心思想是从可行域的一个顶点出发，迭代到更优的顶点，直到找到最优解。
核心步骤
1. 将问题转化为标准形式：添加松弛/剩余/人工变量，确保约束为等式且 \(b_i \ge 0\)
2. 构建初始单纯形表
| 基变量 | \(x_1\) | \(x_2\) | ... | \(x_n\) | 松弛变量 | RHS（\(b_i\)） | 比值 |
|--------|-------|-------|-----|-------|----------|-------------|------|
| \(x_{B1}\)| \(a_{11}\)|\(a_{12}\)|...|\(a_{1n}\)|...|\(b_1\)|\(b_1/a_{1k}\)（\(a_{1k}>0\)）|
| ... | ... | ... | ... | ... | ... | ... | ... |
| \(Z\) | \(-c_1\)|\(-c_2\)|...|\(-c_n\)|...|\(0\)| - |
其中 \(Z\) 行的系数称为检验数 \(\sigma_j = c_B a_{Bj} - c_j\)
3. 最优性检验
- 若所有检验数 \(\sigma_j \le 0\)，当前解就是最优解
- 若存在 \(\sigma_j > 0\)，需要进行迭代
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;
定义单纯形法迭代次数为最大100次，代码如下：
>> param.itlim = 100;
求解，代码如下：
>> [xmin, fmin, status, extra] = ...
   glpk (c, A, b, lb, ub, ctype, vartype, s, param)
xmin =

   33.3333
   66.6667
         0

fmin = 733.33
status = 0
extra =

  scalar structure containing the fields:

    lambda =

       3.3333
       0.6667
            0

    redcosts =

            0
            0
      -2.6667

    time = 0
    status = 5
友链