什么是混合整数线性规划(MILP)模型?

Question

如题所述

Answer 1

混合整数线性规划模型的含义：

线性规划模型(Linear Programming, LP)：LP的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。如果在线性规划问题中有部分决策变量要求必须是整数， 那么这时的规划问题就转变成混合整数线性规划问题了。

也就是说优化问题不止有条件约束，还有整数约束。

要了解什么是混合整数线性规划模型，第一步是要了解什么是线性规划模型(Linear Programming, LP)。LP的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。

举个例子：

超市里头有卖3种食品，玉米，牛奶和面包，价格，所含的维他命A和卡路里的信息见上表。现在的问题是买多少份的玉米，牛奶，面包，使得总价格最低，而维他命A的总摄取量不小于500但不大于50000，卡路里的总摄取量不小于2000但不大于2250。

现在回到之前的问题，如果在线性规划问题中有部分决策变量，比如上面的X_corn要求必须是整数， 那么这时的规划问题就转变成混合整数线性规划问题了。