线性规划 (GNU Octave(版本11.1.0))

25.1 线性规划¶

Octave 可以使用 glpk 函数求解线性规划问题。即 Octave 可以求解

min C'*x

满足线性约束 A*x = b 且 x ≥ 0。

glpk 函数也支持该问题的变体。

[xopt, fmin, errnum, extra] = glpk (c, A, b, lb, ub, ctype, vartype, sense, param) ¶

使用 GNU GLPK 库求解线性规划。

给定三个参数时，glpk 求解以下标准 LP：

min C'*x

约束条件为

A*x  = b
  x >= 0

但也可以求解以下形式的问题

[ min | max ] C'*x

约束条件为

A*x [ "=" | "<=" | ">=" ] b
  x >= LB
  x <= UB

输入参数：

c

包含目标函数系数的列数组。

A

包含约束系数的矩阵。

b

包含约束矩阵中每个约束右侧值的列数组。

lb

包含每个变量下界的数组。如果未提供 lb，则变量的默认下界为零。

ub

包含每个变量上界的数组。如果未提供 ub，则默认上界假定为无穷大。

ctype

包含约束矩阵中每个约束意义的字符数组。数组的每个元素可以是以下值之一

"F": 自由（无界）约束（该约束被忽略）。
"U": 具有上界的不等式约束（A(i,:)*x <= b(i)）。
"S": 等式约束（A(i,:)*x = b(i)）。
"L": 具有下界的不等式约束（A(i,:)*x >= b(i)）。
"D": 同时具有上界和下界的不等式约束（A(i,:)*x >= -b(i)）且（A(i,:)*x <= b(i)）。

vartype

包含变量类型的列数组。

"C": 连续变量。
"I": 整数变量。

sense

如果 sense 为 1，则问题为最小化；如果 sense 为 -1，则问题为最大化。默认值为 1。

param

包含以下参数的结构体，用于定义求解器的行为。结构体中缺失的元素采用默认值，因此您只需设置希望更改的默认值元素。

整数参数：

msglev (default: 1)

求解器例程输出的消息级别：

0 (GLP_MSG_OFF): 无输出。
1 (GLP_MSG_ERR): 仅错误和警告消息。
2 (GLP_MSG_ON): 正常输出。
3 (GLP_MSG_ALL): 完整输出（包括信息性消息）。

scale (default: 16)

缩放选项。这些值可以通过按位 OR 运算符组合，可以是以下值：

1 (GLP_SF_GM): 几何平均缩放。
16 (GLP_SF_EQ): 均衡缩放。
32 (GLP_SF_2N): 将比例因子舍入为 2 的幂。
64 (GLP_SF_SKIP): 若问题已良好缩放则跳过。

或者，也可以指定值 128 (GLP_SF_AUTO)，此时例程会自动选择缩放选项。

dual (default: 1)

单纯形方法选项：

1 (GLP_PRIMAL): 使用两阶段原始单纯形法。
2 (GLP_DUALP): 使用两阶段对偶单纯形法，若失败则切换为原始单纯形法。
3 (GLP_DUAL): 使用两阶段对偶单纯形法。

price (default: 34)

定价选项（适用于原始单纯形和对偶单纯形）：

17 (GLP_PT_STD): 教科书定价。
34 (GLP_PT_PSE): 最陡边定价。

itlim (default: intmax)

单纯形迭代限制。每次执行一次单纯形迭代时减少一，达到零时表示求解器停止搜索。

outfrq (default: 200)

输出频率，以迭代次数为单位。此参数指定求解器将有关解的信息发送到标准输出的频率。

branch (default: 4)

分支技术选项（仅适用于 MIP）：

1 (GLP_BR_FFV): 第一个分式变量。
2 (GLP_BR_LFV): 最后一个分式变量。
3 (GLP_BR_MFV): 最分式变量。
4 (GLP_BR_DTH): Driebeck 和 Tomlin 启发式。
5 (GLP_BR_PCH): 混合伪成本启发式。

btrack (default: 4)

回溯技术选项（仅适用于 MIP）：

1 (GLP_BT_DFS): 深度优先搜索。
2 (GLP_BT_BFS): 广度优先搜索。
3 (GLP_BT_BLB): 最佳局部界。
4 (GLP_BT_BPH): 最佳投影启发式。

presol (default: 1)

如果设置了此标志，则单纯形求解器使用内置的 LP 预求解器。否则不使用 LP 预求解器。

lpsolver (default: 1)

选择使用的求解器。如果问题是 MIP 问题，则忽略此标志。

1: 改进单纯形法。
2: 内点法。

rtest (default: 34)

比率测试技术：

17 (GLP_RT_STD): 标准（"教科书"）。
34 (GLP_RT_HAR): Harris 两遍比率测试。

tmlim (default: intmax)

搜索时间限制，以毫秒为单位。

outdly (default: 0)

输出延迟，以秒为单位。此参数指定求解器延迟向标准输出发送解信息的时间。

save (default: 0)

如果此参数非零，则将问题的副本以 CPLEX LP 格式保存到文件 "outpb.lp"。当前无法更改输出文件的名称。

实数参数：

tolbnd (default: 1e-7): 用于检查当前基本解是否为原始可行的相对容差。除非您详细了解其用途，否则不建议更改此参数。
toldj (default: 1e-7): 用于检查当前基本解是否为对偶可行的绝对容差。除非您详细了解其用途，否则不建议更改此参数。
tolpiv (default: 1e-9): 用于选择单纯形表中合格主元元素的相对容差。除非您详细了解其用途，否则不建议更改此参数。
objll (default: -DBL_MAX): 目标函数的下限。如果目标函数达到此限制并继续减小，求解器将停止搜索。此参数仅用于对偶单纯形法。
objul (default: +DBL_MAX): 目标函数的上限。如果目标函数达到此限制并继续增加，求解器将停止搜索。此参数仅用于对偶单纯形法。
tolint (default: 1e-5): 用于检查当前基本解是否为整数可行的相对容差。除非您详细了解其用途，否则不建议更改此参数。
tolobj (default: 1e-7): 用于检查目标函数值是否不优于最佳已知整数可行解的相对容差。除非您详细了解其用途，否则不建议更改此参数。

输出值：

xopt

最优解（决策变量在最优点的取值）。

fopt

目标函数的最优值。

errnum

错误代码。

0: 没有错误。
1 (GLP_EBADB): 无效基。
2 (GLP_ESING): 奇异矩阵。
3 (GLP_ECOND): 病态矩阵。
4 (GLP_EBOUND): 无效边界。
5 (GLP_EFAIL): 求解器失败。
6 (GLP_EOBJLL): 目标函数达到下限。
7 (GLP_EOBJUL): 目标函数达到上限。
8 (GLP_EITLIM): 迭代次数限制已耗尽。
9 (GLP_ETMLIM): 时间限制已耗尽。
10 (GLP_ENOPFS): 无原始可行解。
11 (GLP_ENODFS): 无对偶可行解。
12 (GLP_EROOT): 未提供根节点 LP 最优解。
13 (GLP_ESTOP): 搜索被应用程序终止。
14 (GLP_EMIPGAP): 达到相对 MIP 间隙容限。
15 (GLP_ENOFEAS): 无原始/对偶可行解。
16 (GLP_ENOCVG): 未收敛。
17 (GLP_EINSTAB): 数值不稳定。
18 (GLP_EDATA): 无效数据。
19 (GLP_ERANGE): 结果超出范围。

extra

包含以下字段的数据结构：

lambda

对偶变量。

redcosts

缩减成本。

time

用于求解 LP/MIP 问题的时间（秒）。

status

优化状态。

1 (GLP_UNDEF): 解状态未定义。
2 (GLP_FEAS): 解可行。
3 (GLP_INFEAS): 解不可行。
4 (GLP_NOFEAS): 问题无可行解。
5 (GLP_OPT): 解为最优。
6 (GLP_UNBND): 问题无界。

示例：

c = [10, 6, 4]';
A = [ 1, 1, 1;
     10, 4, 5;
      2, 2, 6];
b = [100, 600, 300]';
lb = [0, 0, 0]';
ub = [];
ctype = "UUU";
vartype = "CCC";
s = -1;

param.msglev = 1;
param.itlim = 100;

[xmin, fmin, status, extra] = ...
   glpk (c, A, b, lb, ub, ctype, vartype, s, param);