25.1线性规划¶

Octave可以使用glpk作用也就是说,Octave可以解决

最小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:

最小C'*x

约束条件为

A*x=bx>=0

但也可以解决形式上的问题

[最小|最大]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

一个连续的变量。

我

一个整数变量。

sense

如果sense是1,问题是最小化。如果sense是-1,问题是一个最大化。默认值为1。

param

包含以下参数的结构体,用于定义解算器的行为。结构体中缺少的元素采用默认值,因此您只需要设置要从默认值更改的元素。

整数参数:

msglev(默认值:1)

解算器子程序输出的消息级别:

0 (GLP_MSG_OFF)

无输出。

1.GLP_MSG_ERR)

仅限错误和警告消息。

2.GLP_MSG_ON)

正常输出。

3.GLP_MSG_ALL)

完整输出(包括信息性消息)。

比例(默认值:16)

缩放参数。这些值可以与按位OR运算符组合,并且可以是以下值:

1.GLP_SF_GM)

几何平均缩放。

16 (GLP_SF_EQ)

均衡缩放。

32 (GLP_SF_2N)

将比例因子舍入为二的幂。

64 (GLP_SF_SKIP)

若问题规模很大,则跳过。

或者,值128(GLP_SF_AUTO)也可以指定,在这种情况下,子程序自动选择缩放参数。

dual(默认值:1)

Simplex方法参数:

1.GLP原始)

使用两阶段原始单纯形。

2.GLP_DUALP)

使用两阶段对偶单纯形,如果失败,则切换到原始单纯形。

3.GLP_DUAL)

使用两相对偶单纯形。

价格(默认值:34)

定价参数(对于原始单纯形和对偶单纯形):

17 (GLP_PT_STD)

教科书定价。

34 (GLP_PT_PSE)

最优惠的价格。

itlim(默认值:intmax)

单纯形迭代限制。每次执行一次简单退出操作时,它会减少一个,达到零值表示解算器停止搜索。

outrq(默认值:200)

输出频率,以迭代为单位。此参数指定解算器将有关解决方案的信息发送到标准输出的频率。

分支(默认值: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(默认值:4)

回溯技术参数(仅适用于MIP):

1.GLP_BT_DFS)

深度优先搜索。

2.GLP_BT_BFS)

广度优先搜索。

3.GLP_BT_BLB)

最佳本地绑定。

4.GLP_BT_BPH)

最佳投影启发式。

presol(默认值:1)

如果设置了此标志,则单纯形解算器将使用内置的LP预解算器。否则,不使用LP预分解器。

lpsolver(默认值:1)

选择要使用的解算器。如果问题是MIP问题,则会忽略此标志。

1

修正单纯形法。

2

内部点方法。

rtest(默认值:34)

比率测试技术:

17 (GLP_RT_STD)

标准(“教科书”)。

34 (GLP_RT_HAR)

哈里斯的两次通过率测试。

tmlim(默认值:intmax)

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

outdly(默认值:0)

输出延迟,以秒为单位。此参数指定解算器将有关解决方案的信息发送到标准输出的延迟时间。

保存(默认值:0)

如果此参数为非零,请将问题的副本以CPLEXP格式保存到文件中outpb.lp。当前无法更改输出文件的名称。

实际参数:

tolbnd(默认值:1e-7)

用于检查当前基本解决方案是否主要可行的相对公差。除非您对其用途有详细的了解,否则不建议您更改此参数。

toldj(默认值:1e-7)

用于检查当前基本解决方案是否可行的绝对公差。除非您对其用途有详细的了解,否则不建议您更改此参数。

tolpiv(默认值:1e-10)

用于选择simplextable的合格关键元素的相对公差。除非您对其用途有详细的了解,否则不建议您更改此参数。

objll(默认值:-DBL_MAX)

目标函数的下限。如果目标函数达到该极限并继续减小,则解算器停止搜索。此参数仅用于对偶单纯形法。

objul(默认值:+DBL_MAX)

目标函数的上限。如果目标函数达到该极限并继续增加,解算器将停止搜索。此参数仅用于对偶单纯形。

tolint(默认值:1e-5)

用于检查当前基本解决方案是否整数可行的相对公差。除非您对其用途有详细的了解,否则不建议您更改此参数。

tolobj(默认值:1e-7)

相对公差用于检查目标函数的值是否不优于最佳已知整数可行解。除非您对其用途有详细的了解,否则不建议您更改此参数。

输出值:

xopt

优化器(处于最佳状态的决策变量的值)。

fopt

目标函数的最优值。

errnum

错误代码。

0

没有错误。

1.GLP_EBADB)

无效的基础。

2.GLP_ESING)

奇异矩阵。

3.GLP秒)

病态矩阵。

4.GLP_EBOUND)

无效的界限。

5.GLP_EFAIL)

解算器失败。

6.GLP_EOBJLL)

达到目标函数下限。

7.GLP_EOBJUL)

达到目标函数上限。

8.GLP_EITLIM)

迭代次数限制已用尽。

9 (GLP_ETMLIM)

时间限制已用尽。

10 (GLP_enofs)

没有原始可行的解决方案。

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)

结果超出范围。

额外的

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

λ

双变量。

红色成本

降低成本。

时间

用于解决LP/MIP问题的时间(秒)。

地位

优化的状态。

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=[1000600300]';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);