整数规划

解决整数约束下的优化问题

整数规划算法使受等式、不等式和整数约束的函数最小化或最大化。整数约束限制优化问题中的部分或所有变量只接受整数值。这使得涉及离散量(例如股票的份额或电池中的单元)或是或否决策的问题能够精确建模。当仅对某些变量有整数约束时,该问题被称为混合整数程序(MIP)。整数规划问题的例子包括投资组合优化在金融领域,发电机组最优调度(单位承诺)在能源生产中,优化设计在工程领域,以及运输和供应链中的调度和路由应用。

整数规划是一个数学问题,寻找一个向量\(x\),使函数最小化:

\ [\ min_x f (x) \]

受约束条件:

\[\begin{eqnarray}g(x) \leq 0 & \quad & \text{(不等式约束)}\\h(x) = 0 & \quad & \text{(不等式约束)}\\ x_i \in \mathbb{Z} & \quad & \text{(整数约束)}\end{eqnarray}\]

这是整数规划最一般的形式,被称为混合整数非线性规划(MINLP)。

许多问题只需要线性目标和约束条件就可以表述出来。在这种情况下,整数规划被称为混合整数线性规划(MILP),并被写为:

\ [\ min_ {x} \左\ {f ^ {\ mathsf {T}} x \ \} \]

受约束条件:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(不等式约束)}\\A_{eq}x = b_{eq} & \quad & \text{(等式约束)}\\lb \leq x \leq ub & \quad & \text{(绑定约束)}\\ x_i \in \mathbb{Z} & \quad & \text{(整数约束)}\end{eqnarray}\]

MATLAB中的混合整数线性规划

整数规划算法可以在软件中实现,如MATLAB®。求解milp通常需要使用组合技术来缩小解空间,找到整数可行解,并丢弃解空间中不包含更好的整数可行解的部分。整数规划的常用技术包括:

MILP解算器优化工具箱™实现这些技术。

MATLAB混合整数非线性规划

一些MINLPs可以通过将这些整数规划技术应用到非线性函数或通过将非线性函数线性化并求解milp序列来解决。当非线性函数只能在积分点上求值时,就需要使用其他技术。中实现了适用于这类整数程序的两种算法全局优化工具箱

  • 遗传算法:模拟一个自然选择过程,反复修改一个被限制为整数值的个体解的种群。
  • 代理优化:自动构建可以放松的问题代理模型,然后通过将MILP技术适配到MINLP来解决。

有关整数规划的更多信息,请参见优化工具箱全局优化工具箱



用例


混合整数线性规划示例



参见:优化工具箱,全局优化工具箱,线性规划,二次规划,非线性规划,遗传算法,投资管理,能源交易,规范的分析,代理优化,电力系统仿真与优化

Baidu
map