解决R中的LP最大化问题(使用lpSolve软件包)

问题描述 投票:1回答:1

我需要解决以下微观经济问题:

  • 我有五年(2011年至2015年)可以生产(资产1-6)六项资产。
  • 每个资产只能在一年内生产。
  • 每个资产必须在我的五年期内生产。
  • 生产不是相互排斥的;我一年可以生产一种以上的商品,而不会影响任何一种的生产。
  • 每个资产的固定生产成本等于30。
  • 我每年必须有非负利润;收入必须至少为30。

下面是代表我在给定年份(j)中生产每种资产(i)的潜在收入的矩阵。

          2011 2012 2013 2014 2015
  Asset1    35* 37  39  42  45
  Asset2    16  17  18  19  20*
  Asset3    125 130 136*139 144
  Asset4    15  27  29  30* 33
  Asset5    14  43* 46  50  52
  Asset6    5   7   8   10  11*

星号(*)代表什么是最佳解集。

我如何使用R来解决生产计划,以在概述的约束条件下最大化我的收入(并因此获得利润)。我的输出应该是01的类似6x5矩阵,其中1代表选择在给定年份内生产商品。

r matrix linear-programming
1个回答
3
投票

这是一个经典的问题,需要重新制定。

重新开始您的问题

Max( sum_[i,t] (pi_[i,t] - C_[i,t]) * x_[i,t]) 
Sd. 
sum_t x_[i,t] = 1 [ for all i ]
sum_i x_[i,t] >= 30 [ for all t ]
x_[i,t] >= 0 [for all i, t]

lpSolve包中的最大化问题以线性表示形式给出,例如非矩阵格式。让我们从制作代表我们的x_[i,t]的向量开始。为方便起见,让我们为其命名(尽管未使用),以便我们跟踪。

n <- 6
t <- 5
#x ordered by column. 
x <- c(35, 16, 125, 15, 14, 5, 37, 17, 130, 27, 43, 7, 39, 18, 136, 29, 46, 8, 42, 19, 139, 30, 50, 10, 45, 20, 144, 33, 52, 11)
# if x is matrix use:
# x <- as.vector(x)
names(x) <- paste0('x_[', seq(n), ',', rep(seq(t), each = n), ']')
head(x, n * 2)
x_[1,1] x_[2,1] x_[3,1] x_[4,1] x_[5,1] x_[6,1] x_[1,2] x_[2,2] x_[3,2] x_[4,2] x_[5,2] x_[6,2] 
     35      16     125      15      14       5      37      17     130      27      43       7
length(x)
[1] 30

现在我们需要创造条件。从第一个条件开始>

sum_t x_[i,t] = 1 [ for all i ]

我们可以相当简单地创建它。需要注意的是,尺寸必须正确。我们有一个长度为30的向量,因此我们需要我们的条件矩阵具有30列。此外,我们有6个资产,因此对于这种情况我们将需要6行。再次让我们命名行和列以跟踪自己。

cond1 <- matrix(0, ncol = t * n, 
                nrow = n, 
                dimnames = list(paste0('x_[', seq(n), ',t]'),
                                names(x)))
cond1[, seq(n + 1)]
        x_[1,1] x_[2,1] x_[3,1] x_[4,1] x_[5,1] x_[6,1] x_[1,2]
x_[1,t]       0       0       0       0       0       0       0
x_[2,t]       0       0       0       0       0       0       0
x_[3,t]       0       0       0       0       0       0       0
x_[4,t]       0       0       0       0       0       0       0
x_[5,t]       0       0       0       0       0       0       0
x_[6,t]       0       0       0       0       0       0       0

接下来,我们填写正确的字段。 x_[1,1] + x[1, 2] + ... = 1x_[2,1] + x_[2,2] + ... = 1等。对于这个问题,使用for循环是最简单的]

for(i in seq(n)){
  cond1[i, seq(i, 30, n)] <- 1
}
cond1[, seq(n + 1)]
        x_[1,1] x_[2,1] x_[3,1] x_[4,1] x_[5,1] x_[6,1] x_[1,2]
x_[1,t]       1       0       0       0       0       0       1
x_[2,t]       0       1       0       0       0       0       0
x_[3,t]       0       0       1       0       0       0       0
x_[4,t]       0       0       0       1       0       0       0
x_[5,t]       0       0       0       0       1       0       0
x_[6,t]       0       0       0       0       0       1       0

我们仍然必须创建RHS并指定方向,但是我现在将等待。因此,接下来让我们为第二个条件创建矩阵

sum_i x_[i,t] >= 30 [ for all t ]

此过程非常相似,但是现在每个周期都需要一行,因此矩阵的尺寸为5x30。这里的主要区别是,我们需要插入x_[i, t]

的值
cond2 <- matrix(0, ncol = t * n, 
                nrow = t, 
                dimnames = list(paste0('t=', seq(t)),
                                names(x)))
for(i in seq(t)){
   cond2[i, seq(n) + n * (i - 1)] <- x[seq(n) + n * (i - 1)]
}
cond2[, seq(1, n * t, n)]
    x_[1,1] x_[1,2] x_[1,3] x_[1,4] x_[1,5]
t=1      35       0       0       0       0
t=2       0      37       0       0       0
t=3       0       0      39       0       0
t=4       0       0       0      42       0
t=5       0       0       0       0      45

请注意,我正在打印x_[1, t]的结果以说明我们做对了。最后,我们有最终条件。为此,我们注意到?lpSolve::lp有一个参数all.bin,并且在读取它时指出

逻辑:所有变量都应为二进制吗?默认值:FALSE。

因此,由于所有变量均为1或0,我们只需将此值设置为TRUE。在继续之前,让我们将条件合并为一个矩阵

cond <- rbind(cond1, cond2)

现在,RHS和方向都简单地从这两个条件中得出。从const.dir参数的文档中

给出约束方向的字符串向量:每个值应为“ ”或“> =”中的一个。 (在每对中,两个值相同。)

[在我们的条件下,我们有6行代表第一个条件,而行又复位了条件2。因此,我们需要n(6)乘以==,而t(5)乘以>=

cond_dir <- c(rep('==', n), rep('>=', t))

以类似方式创建RHS

RHS <- c(rep(1, n), rep(30, t))

就是这样!现在,我们准备使用lpSolve::lp函数来解决我们的问题。

sol = lpSolve::lp(direction = 'max',
                  objective.in = x, 
                  const.mat = cond,
                  const.dir = cond_dir,
                  const.rhs = RHS,
                  all.bin = TRUE)                
sol$objval
[1] 275

解决方案的权重存储在sol$solution

names(sol$solution) <- names(x)
sol$solution
x_[1,1] x_[2,1] x_[3,1] x_[4,1] x_[5,1] x_[6,1] x_[1,2] x_[2,2] x_[3,2] x_[4,2] x_[5,2] x_[6,2] x_[1,3] x_[2,3] x_[3,3] 
      1       0       0       0       0       0       0       0       0       0       1       0       0       0       1 
x_[4,3] x_[5,3] x_[6,3] x_[1,4] x_[2,4] x_[3,4] x_[4,4] x_[5,4] x_[6,4] x_[1,5] x_[2,5] x_[3,5] x_[4,5] x_[5,5] x_[6,5] 
      0       0       0       0       0       0       1       0       0       0       1       0       0       0       1
matrix(sol$solution, 
       ncol = t,
       dimnames = list(rownames(cond1), 
                       rownames(cond2)))
        t=1 t=2 t=3 t=4 t=5
x_[1,t]   1   0   0   0   0
x_[2,t]   0   0   0   0   1
x_[3,t]   0   0   1   0   0
x_[4,t]   0   0   0   1   0
x_[5,t]   0   1   0   0   0
x_[6,t]   0   0   0   0   1

我们很快就会看到这是正确的解决方案。 :-)

费用说明

[可能有人注意到“费用到底去了哪里?”。在这种情况下,成本是固定的,不是很有趣。这意味着我们可以在计算期间忽略这些,因为我们知道总成本将为30 * 6 = 180(必须从目标值中减去)。但是,成本取决于各种因素并可能影响最佳解决方案并不少见。为了说明,我将在此示例中包括如何合并成本。首先,我们必须扩展目标向量,以合并每个时期每个产品的成本

Fixed_C <- -30
x <- c(x, rep(Fixed_C, n * t))

下一步,我们将添加伪约束

x_[i,t] - C_[i,t] = 0 [for all i, t]

此约束确保如果x_[i,t] = 1,则相关成本将添加到问题中。有两种创建此约束的方法。第一种是具有一个矩阵,该矩阵具有n * t行,每个成本和期间一个。另外,我们可以使用我们的第一个约束条件,并且实际上只使用一个常数。

sum_[i,t] x_[i,t] - C_[i,t] = 0

因为我们的第一个约束确保x[1, 1] != x[1, 2]。因此,我们的第三个约束变为

cond3 <- c(rep(1, n * t), rep(-1, n * t))

最后,我们必须扩展RHS以及条件1和2的矩阵。只需将0添加到条件矩阵以使尺寸合适。

cond1 <- cbind(cond1, matrix(0, nrow = n, ncol = n * t))
cond2 <- cbind(cond2, matrix(0, nrow = n, ncol = n * t))
cond <- rbind(cond1, cond2, cond3)
cond_dir <- c(cond_dir, '==')
RHS <- c(RHS, 0)

现在我们可以再次使用lpSolve::lp找到最佳解决方案>

solC = lpSolve::lp(direction = 'max',
                  objective.in = x, 
                  const.mat = cond,
                  const.dir = cond_dir,
                  const.rhs = RHS,
                  all.bin = TRUE)
solC$objval
[1] 95

等于我们之前的值275减去固定费用Fixed_C * n = 180

© www.soinside.com 2019 - 2024. All rights reserved.