How to solve linear programming model in R

Question

I need to solve the following microeconomic problem:

• I have six assets I can produce (asset 1 - 6) across five years (2011 - 2015).
• Each asset can only be produced during one year.
• Each asset must be produced in my five year period.
• Production is not mutually exclusive; I can produce more than one good in a year without affecting the production of either.
• Each asset has a fixed cost of production equal to 30.
• I must have non-negative profit in each year; revenues must be at least 30.

Below is a matrix representing my potential revenue for producing each asset (i) in a given year (j).

          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*

The asterisks (*) represent what should be the optimal solution set.

我如何使用 R 来求解生产计划，以在规定的约束条件下最大化我的收入（以及利润）。0我的输出应该是由 和1组成的类似 6x5 矩阵，其中1代表选择在给定年份生产商品。

Answer 1

这是一个经典问题，需要重新表述。

首先重新表述你的问题

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] + ... = 1等等x_[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，阅读本文，它指出

逻辑：所有变量都应该是二进制的吗？默认值：假。

因此，由于所有变量不是 1 就是 0，我们只需将该值设置为TRUE。在继续之前，让我们将条件组合成一个矩阵

cond <- rbind(cond1, cond2)

现在 RHS 和方向都只是从这 2 个条件中获取。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。