运筹学4.整数规划

文章目录

• 引言

  • 利用分枝定界的策略用于解决整数规划问题

  • 对于整数规划问题进行系统性分析与处理

    • 研究整数规划解法的基本框架与核心思路
    • 具体阐述分支定界法的工作原理及应用范围

  • 4.2 0-1整数规划

  • • 0-1整数规划的数学模型
    • 隐枚举法求解0-1规划问题

第4.3节 分配问题与 hungarian algorithm

引言

在规划问题中，若决策变量全部或部分被限定为取自一个离散集合（如非负整数值），则称其为离散优化问题的一种——混合整型组合最优化模型。根据变量的性质不同，则可分为全离散型组合最优化模型、混合离散型组合最优化模型以及0-1型组合最优化模型等多种类型。对于纯离散型组合最优化模型而言，在所有决策变量上施加取值范围限制后得到的结果即为此类问题的解；而对于混合离散型组合最优化模型，则仅对部分决策变量进行取值范围限定。特别地，在这种情况下称作0-1型离散优化模型（简称0-1模型）。值得注意的是，在此之外的非线性组合优化问题同样面临较大的计算难度，并未找到通用的有效解决方案。

4.1 分枝定界方法求解整数规划问题

整数规划的分类

整数规划是决策变量部分或全部取整数的规划问题，有以下分类：

整数线性规划(ILP)
目标函数是线性的
约束条件均为线性方