14.2 整数规划
14.2.1 一般整数规划
\[\begin{equation*} \begin{array}{l} \max_x \quad 0.2x_1 + 0.6x_2 \\ s.t.\left\{ \begin{array}{l} 5x_1 + 3x_2 \leq 250\\ -3x_1 + 2x_2 \leq 4\\ x_1,x_2 \geq 0, \quad x_1,x_2 \in \mathbb{Z} \end{array} \right. \end{array} \end{equation*}\]# 目标
f.obj <- c(0.2, 0.6)
# 约束
f.con <- matrix(c(5, 3, -3, 2), nrow = 2, byrow = TRUE)
# 方向
f.dir <- c("<=", "<=")
# 右手边
f.rhs <- c(250, 4)
# 限制两个变量都是整数
res <- lp("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:2)
res$objval## [1] 29.2res$solution## [1] 26 4014.2.2 0-1 整数规划
\[\begin{equation*} \begin{array}{l} \max_x \quad 0.2x_1 + 0.6x_2 \\ s.t.\left\{ \begin{array}{l} 5x_1 + 3x_2 \leq 250\\ -3x_1 + 2x_2 \leq 4\\ x_1,x_2 \in \{0,1\} \end{array} \right. \end{array} \end{equation*}\]# 目标
f.obj <- c(0.2, 0.6)
# 约束
f.con <- matrix(c(5, 3, -3, 2), nrow = 2, byrow = TRUE)
# 方向
f.dir <- c("<=", "<=")
# 右手边
f.rhs <- c(250, 4)
# 限制两个变量都是0-1整数
res <- lp("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:2, all.bin = TRUE)
res$objval## [1] 0.8res$solution## [1] 1 114.2.3 混合整数规划
Rsymphony 是混合整数规划求解器 SYMPHONY 的 R 语言接口44。
library(Rsymphony)
## Simple linear program.
## maximize: 2 x_1 + 4 x_2 + 3 x_3
## subject to: 3 x_1 + 4 x_2 + 2 x_3 <= 60
## 2 x_1 + x_2 + x_3 <= 40
## x_1 + 3 x_2 + 2 x_3 <= 80
## x_1, x_2, x_3 are non-negative real numbers
# 简单线性规划
obj <- c(2, 4, 3)
mat <- matrix(c(3, 2, 1, 4, 1, 3, 2, 1, 2), nrow = 3)
dir <- c("<=", "<=", "<=")
rhs <- c(60, 40, 80)
max <- TRUE
Rsymphony_solve_LP(obj, mat, dir, rhs, max = max)
# 混合整数规划
obj <- c(3, 1, 3)
mat <- matrix(c(-1, 0, 1, 2, 4, -3, 1, -3, 2), nrow = 3)
dir <- c("<=", "<=", "<=")
rhs <- c(4, 2, 3)
max <- TRUE
types <- c("I", "C", "I")
Rsymphony_solve_LP(obj, mat, dir, rhs, types = types, max = max)
# 有边界约束的混合整数规划
## Same as before but with bounds replaced by
## -Inf < x_1 <= 4
## 0 <= x_2 <= 100
## 2 <= x_3 < Inf
bounds <- list(
lower = list(ind = c(1L, 3L), val = c(-Inf, 2)),
upper = list(ind = c(1L, 2L), val = c(4, 100))
)
Rsymphony_solve_LP(obj, mat, dir, rhs,
types = types, max = max,
bounds = bounds
)一部分变量要求是整数
\[\begin{equation*} \begin{array}{l} \max_x \quad 3x_1 + 7x_2 - 12x_3 \\ s.t.\left\{ \begin{array}{l} 5x_1 + 7x_2 + 2x_3 \leq 61\\ 3x_1 + 2x_2 - 9x_3 \leq 35\\ x_1 + 3x_2 + x_3 \leq 31\\ x_1,x_2 \geq 0, \quad x_2, x_3 \in \mathbb{Z}, \quad x_3 \in [-10, 10] \end{array} \right. \end{array} \end{equation*}\]矩阵形式如下
\[\begin{equation*} \begin{array}{l} \min_x \quad \begin{bmatrix} 3 \\ 7 \\ -12 \end{bmatrix} ^{T} x \\ s.t.\left\{ \begin{array}{l} \begin{bmatrix} 5 & 7 & 2 \\ 3 & 2 & -9\\ 1 & 3 & 1 \end{bmatrix} x \leq \begin{bmatrix} 61 \\ 35 \\ 31 \end{bmatrix} \end{array} \right. \end{array} \end{equation*}\]op <- OP(
objective = L_objective(c(3, 7, -12)),
# 指定变量类型：第1个变量是连续值，第2、3个变量是整数
types = c("C", "I", "I"),
constraints = L_constraint(
L = matrix(c(
5, 7, 2,
3, 2, -9,
1, 3, 1
), ncol = 3, byrow = TRUE),
dir = c("<=", "<=", "<="),
rhs = c(61, 35, 31)
),
# 添加约束：第3个变量的下、上界分别是 -10 和 10
bounds = V_bound(li = 3, ui = 3, lb = -10, ub = 10, nobj = 3),
maximum = TRUE
)
op## ROI Optimization Problem:
##
## Maximize a linear objective function of length 3 with
## - 1 continuous objective variable,
## - 2 integer objective variables,
##
## subject to
## - 3 constraints of type linear.
## - 1 lower and 1 upper non-standard variable bound.res <- ROI_solve(op, solver = "lpsolve")
res$solution## [1] 0.3333333 8.0000000 -2.0000000res$objval## [1] 81