用Octave计算线性规划问题（内点法）（障碍函数法）
广告
{{v.name}}
内点法（Interior-Point Method）是求解大规模线性规划问题的最高效算法之一。与单纯形法在可行域顶点上移动不同，它从可行域内部出发，沿着一条 “中心路径”（Central Path）迭代逼近最优解，理论复杂度为多项式级（O (n³)），在变量 / 约束极多时，速度远快于单纯形法。
一、线性规划的标准形式（内点法专用）
内点法要求问题必须转化为标准型（等式约束 + 变量非负）：
\( \begin{aligned} \min & \quad c^T x \\ \text{s.t.} & \quad A x = b \\ & \quad x \ge 0 \end{aligned} \)
其中：
- \(x \in \mathbb{R}^n\)：决策变量（待求）
- \(c \in \mathbb{R}^n\)：目标函数系数
- \(A \in \mathbb{R}^{m \times n}\)：约束矩阵（\(m < n\)，满秩）
- \(b \in \mathbb{R}^m\)：约束右端项（\(b \ge 0\)）
- \(x \ge 0\)：所有变量严格大于0（内点法要求初始点在内部）
转化技巧：
- 不等式约束 \(a_i^T x \le b_i\)：引入松弛变量 \(s_i \ge 0\)，变为 \(a_i^T x + s_i = b_i\)。
- 自由变量（无正负约束）：拆分为 \(x = x^+ - x^-\)，其中 \(x^+ \ge 0, x^- \ge 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 = 2;
定义单纯形法迭代次数为最大100次，代码如下：
>> param.itlim = 100;
求解，代码如下：
>> [xmin, fmin, status, extra] = ...
   glpk (c, A, b, lb, ub, ctype, vartype, s, param)
xmin =

   3.3333e+01
   6.6667e+01
   3.9749e-07

fmin = 733.33
status = 0
extra =

  scalar structure containing the fields:

    lambda =

       3.3333e+00
       6.6667e-01
      -2.4413e-10

    redcosts =

       1.1508e-08
       1.6599e-08
      -2.6667e+00

    time = 0
    status = 5
友链