视频字幕
整数规划是在线性规划基础上，要求部分或全部决策变量取整数值的优化问题。与线性规划的连续可行域不同，整数规划的可行解是离散的整数点。根据整数约束的范围，可分为纯整数规划、混合整数规划和0-1整数规划三种类型。图中蓝色区域表示线性规划的连续可行域，红色点表示满足整数约束的可行解。
整数规划属于NP-hard问题，其求解难度远超线性规划。线性规划可在多项式时间内求解，复杂度为O(n³)，而整数规划需要指数时间，复杂度为O(2ⁿ)。随着变量数量增加，可能的整数解组合数呈指数级增长。当变量数为n时，二进制变量的组合数为2ⁿ，这使得大规模整数规划问题极难求解。
分支定界法是求解整数规划的重要精确算法。其核心思想包括三个步骤：分支、定界和剪枝。首先求解线性松弛问题获得上界，然后选择非整数变量进行分支，创建子问题。通过计算各节点的界限值，可以剪除那些不可能包含最优解的分支，从而减少搜索空间。算法通过树状结构系统地搜索，直到找到最优整数解。
通过具体例子演示分支定界法求解过程。问题是最大化3x₁+2x₂，约束条件为x₁+x₂≤4和2x₁+x₂≤6，变量为非负整数。首先求解线性松弛得到z=10，最优解为(2,2)。由于解不是整数，选择x₁进行分支，创建x₁≤2和x₁≥3两个子问题。计算后发现右分支的整数解(3,0)目标值为9，成为最优解。左分支进一步分支后被剪枝。
割平面法是另一种重要的整数规划精确求解方法。其基本思想是通过添加线性约束来逐步缩小可行域，直到线性松弛的最优解恰好是整数解。算法从求解线性松弛开始，如果最优解不是整数，就构造一个割平面约束，这个约束能够切掉当前的非整数最优解，但不会切掉任何整数可行解。重复这个过程直到获得整数最优解。