如何使用R最小化线性规划模型中的设置成本

Question

假设我们有一个矩阵m：

> m
   C1 C2
M1 70 80
M2 50 61
M3 45 40

机器M1-M3和客户C1-C2。这些值表示每台机器可以为特定客户生产的产品数量，例如，如果使用M1，它将为C1生产70件产品，为C2生产80件产品。

我只想使用以下约束将满足需求所需的所有机器的设置成本降至最低：

每客户需求>= 120；如果用于任何客户，则每台机器的设置成本=1，否则为0。

对于这个简单的示例，解决方案是使用机器M1和M2 (为C1生产120台，为C2生产141台)，总设置成本为2。另一种可行的选择是使用机器M1、M2和M3，但这将导致设置成本为3，因此不是最优的。

如何使用R来解决这个问题？我看了一些使用lpSolve的例子，但我很难对设置成本进行建模，如果机器产生任何东西，它们就是1，否则就是0。

Answer 1

请阅读MOSEK modeling manualhttp://docs.mosek.com/generic/modeling-letter.pdf的第6章，特别是第6.2节，以及其中的示例6.1。它准确地告诉您如何使用二进制变量对您的情况进行建模。然后在lpsolve中实现这种方法，它允许使用所需的二进制变量。

Answer 2

诀窍是为每台机器的设置成本创建一个二进制变量。(它是一个指示符变量。)

用英语

如果机器2产生任何结果，则二进制变量setup_2 =1

如果机器2不产生任何结果，则setup_2 =0

每台机器都需要一个这样的二进制变量。

设置约束(公式)

让BigM是一个很大的数字。设X_mj是机器m为客户j执行的作业数。

Sum(over all jobs) X_machine_job - BigM * setup_machine <= 0

如果任何X_mj变量为非零，则强制setup_machine变量变为1，这正是我们想要的。

这是唯一的诀窍。其余的公式都是例行公事。下面是使用lpSolveAPI.的完整示例

R代码

(代码未优化。这样写起来更容易理解。)

library(lpSolveAPI)
lpAssign <- make.lp(ncol=9) #3 columns for SETUP variable (Binary) + 6 columns: 3 machines * 2 customers
#The first 3 columns are the setup variables (binary)
set.type(lpAssign, c(1,2,3), "binary")
add.constraint(lpAssign, c(1,1,1), type=">=", rhs=120, indices=c(4,6,8)) #meet demand for customer 1
add.constraint(lpAssign, c(1,1,1), type=">=", rhs=120, indices=c(5,7,9))

#capacity constraints (6 of them)
add.constraint(lpAssign, 1, type="<=", rhs=70, indices=c(4))
add.constraint(lpAssign, 1, type="<=", rhs=80, indices=c(5))
add.constraint(lpAssign, 1, type="<=", rhs=50, indices=c(6))
add.constraint(lpAssign, 1, type="<=", rhs=61, indices=c(7))
add.constraint(lpAssign, 1, type="<=", rhs=45, indices=c(8))
add.constraint(lpAssign, 1, type="<=", rhs=40, indices=c(9))

#setup cost variable constraint for each machine 
BigM <- 1e6
add.constraint(lpAssign, c(-1*BigM,1,1), type="<=", rhs=0, indices=c(1,4,5))
add.constraint(lpAssign, c(-1*BigM,1,1), type="<=", rhs=0, indices=c(2,6,7))
add.constraint(lpAssign, c(-1*BigM,1,1), type="<=", rhs=0, indices=c(3,8,9))

set.objfn(lpAssign, c(1,1,1,0,0,0,0,0,0)) #All we care about is SET UP cost minimization

write.lp(lpAssign, "MinSetupLp.lp", "lp")#write it out

验证

> solve(lpAssign)
[1] 0
> sol <- get.variables(lpAssign)
> sol
[1]  1  1  0 70 80 50 40  0  0
> get.objective(lpAssign)
[1] 2