机队分配利润最大化的优化问题，给定飞机类型的盈利矩阵到航线和限制小时数

Question

我正在尝试创建一种优化算法，以最有效地将飞机类型分配到我的航线以进行机队优化。

我的输入：一个 150 x 6 的矩阵，其中有 150 条必须全部飞行的航线，以及 6 种可能的飞机类型，变量是每条航线的利润。作为约束，我有必须使用的每条路线的轮挡小时数（以满足需求）和每种飞机类型的最大轮挡小时数。输出应该是一个 150 x 6 的矩阵，告诉我哪架飞机应该在哪条航线上飞行多少小时。

我尝试了树和线性 ROI 优化，但到目前为止没有成功。

Answer 1

到目前为止我已经试过了：

# Define the input matrix of profits
profits <- matrix(c(1, 1, 3, 232791.79,
                    1, 1, -1, 114218.04,
                    1, 2, -1, 1,
                    1, 4, 1, 42145.69,
                    -1, -1, 1, -520264.48,
                    2, -1, 1, 3134.91), 
                  nrow = 6, ncol = 4, byrow = TRUE)

# Define the available hours matrix
bhr <- matrix(c(400, 400, 500, 500), 
              nrow = 1, ncol = 4)

# Define the matrix of constraints A_eq
n_planes <- ncol(profits)
n_routes <- nrow(profits)

# Create a matrix with the correct dimensions
A_eq <- matrix(0, nrow = n_routes + 1 + n_planes, ncol = n_planes * n_routes)

# Set the first set of constraints
for (i in 1:n_routes) {
  A_eq[i, ((i-1)*n_planes+1):(i*n_planes)] <- 1
}

# Set the second set of constraints
A_eq[n_routes+1,] <- rep(1, n_planes * n_routes)

# Set the third set of constraints
for (i in 1:n_planes) {
  A_eq[n_routes+1+i, seq(i, by = n_planes, length.out = n_routes)] <- 1
}

A_eq[n_routes + 1 + n_planes + (1:n_routes), ] <- -profits
# Set the fourth set of constraints
A_eq[n_routes+1+n_planes+1:n_routes,] <- -profits

# Convert A_eq to a sparse matrix
A_eq <- as.matrix(sparse.model.matrix(~ -1 + A_eq))

for (i in 1:n_routes) {
  A_ub[i, (i - 1) * n_planes + 1:(i * n_planes)] <- as.vector(profits[i, ])
}

A <- rbind(A_eq, A_ub)

# Set the constraint vector b
b_eq <- matrix(c(rep(bhr, n_routes), n_routes, rep(0, n_routes)), ncol = 1)
b_ub <- matrix(rep(0, n_routes), ncol = 1)

b <- rbind(b_eq, b_ub)

# Add the constraints to the LP problem
add.constraint(lprec, A_eq, "=", b_eq)
add.constraint(lprec, A_ub, "<=", b_ub)

# Set the solver to use the simplex algorithm
set.verbose(lprec, 0)
set.type(lprec, 1:(n_planes * n_routes), "binary")
solve(lprec)

# Get the solution
solution <- get.variables(lprec)

# Print the results
cat("Optimal Profit: $", round(-get.objective(lprec)), "\n")
cat("Plane Allocation:\n")
for (i in 1:n_routes) {
  cat(paste0("Route ", i, ": "))
  for (j in 1:n_planes) {
    if (solution[(i - 1) * n_planes + j] == 1) {
      cat(colnames(profits)[j], " ")
    }
  }
  cat("\n")
}