【R语言在最优化中的应用】用goalprog包求解 线性目标规划

标规划问题及其数学模型

目标规划(goal programming) 是运筹学中的一个重要分支，它是为解决多目标决策问题而发展起来的一种数学方法。目标规划可以按照确定的若干目标值及其实现的优先次序，在给定约束条件下寻找偏离目标值最小的解的数学方法。它在处理实际决策问题时，承认各项决策要求 (即使是冲突的)的存在有合理性；在做最终决策时，不强调其绝对意义上的最优性。由于目标规划在一定程度上弥补了线性规划的局限性，因此，目标规划被认为是一种较之线性规划更接近于实际决策工程的工具。

目标规划数学模型的一般形式为：

(2)

模型2的约束条件中，第一行有偏差变量，为目标约束，第二行没有偏差变量，同线性规划里的约束条件一样，为绝对约束。可以证明，在模型2有解的情况下，可以将其化为只含有目标约束的目标规划问题，方法是给所有的绝对约束赋予足够高级别的优先因子，从这个角度来看，线性规划为目标规划的特殊情况，而目标规划则为线性规划的自然推广。根据以上分析，可将模型 (2) 简化并用矩阵和向量记为：

(3)

模型(3)中，所有的约束都为目标约束，每一个目标约束都对应一对偏差变量。

用goalprog包求解目标规划

R中，goalprog包 (Novomestky, 2008) 可以求解形式为模型(3) 的目标规划问题，核心函数为llgp()，用法如下：

llgp(coefficients, targets,achievements, maxiter = 1000, verbose = FALSE)

参数中，

coefficients为约束变量(不包括偏差变量) 的系数矩阵，即模型 (3) 中的矩阵 A。

targets为系数矩阵对应的约束向量，即模型 (3) 中的向量 g。

achievements为关于目标函数 (默认求最小值) 的数据框，是由 4 个向量构成：objective、priority、p和 n。其中数据框的每一行对应一个软约束条件，objective和 priority 为正整数，分别表示针对第几对偏差变量 (第 n 对偏差变量必须出现在第 n 个目标约束中) 和该偏差变量的优先级别，p 和 n 分别表示 d+(正偏差变量)、d−(负偏差变量) 的权系数。

maxiter为最大迭代次数，取正整数，默认为 1000。

verbose为逻辑变量(取 TRUE或 FALSE )，决定是否输出中间过程，默认不输出。

例

某工厂生产两种产品，受到原材料供应和设备工时的限制，在单位利润等有关数据已知的条件下，要求制定一个获利最大的生产计划，具体数据见表在决策时，按重要程度的先后顺序，要考虑如下意见：

1.原材料严重短缺，生产中应避免浪费，不得突破使用限额；

2.由于产品 B 销售疲软，故希望产品 B 的产量不超过产品 A 的一半；

3.最好能节约 4 h 的设备工时；

4.计划利润不少于 48 元。

以上四条意见中，显然第一条为绝对约束，第二至四条为目标约束。请根据这些要求决定两种产品生产量。

解:

这是典型的多目标规划问题，建立目标规划模型如下：

该模型中含绝对约束条件，将绝对约束条件转化为一级目标约束条件，得到模型如下：

该模型符合模型 (3) 的形式，可以直接调用 llgp() 函数来求解该问题，注意：R中根据achievements数据框中的 priority 来判断绝对优先级别，不用再设置 P1，P2，P3。R代码和部分输出结果如下：

> library(goalprog) > coefficients=matrix(c(5,1,4,6,10,-2,4,8),4) > targets=c(60,0,36,48) > achievements=data.frame(objective=1:4,priority=c(1,2,3,4),p=c(1,0,1,0),n=c(0,1,0,1)) > soln=llgp(coefficients,targets,achievements) > soln$converged [1] TRUE > soln$out Decision variables X X1 4.800000e+00 X2 2.400000e+00

观察输出结果，可以知道该问题已经得到最优解 (soln$converged 为 TRUE 时，表示最优解已经

找到)，此时 x1，x2分别取 4.8，2.4，即应生产 A 产品 4.8 个单位，B 产品 2.4 个单位。需要说明的是，由于约束较少，本题有四个满意解，这里仅仅得到一个。此外，程序结果输出较多，上面的soln$out 仅选取了一部分。

下面再看一个稍微复杂的例子。

求下列目标规划问题：

解：这是一个多目标规划问题，可以直接调用 llgp() 函数求解。R代码及运行结果如下 (为了便于展示，输出了一些参数的信息):

> library(goalprog)

> coefficients=matrix(c(1,1,5,1,1,0,3,1),4)

> targets=c(10,4,56,12)

> achievements=data.frame(objective=1:4,priority=c(1,1,2,3),p=c(2,3,0,1),n=c(0,0,1,0))

> soln=llgp(coefficients,targets,achievements)

> soln$converged

[1] TRUE

> soln$out

Decision variables

                X

X1   4.000000e+00

X2   6.000000e+00

析输出结果，可以知道该问题已经得到最优解，此时 x1，x2分别为 4，6。

求个红包