第3章 整数线性规划3.3分枝定界法补充：舍入法
第3章 整数线性规划 3.3 分枝定界法 补充：舍入法
分枝定界法的基本思想-分枝将状态空间U一分为二。一■状态空间可以取IP的可行域，或者比其更大。进入一个状态空间U'。若判定在U'内不可能找到比当前已知解更好的解，则摒弃该搜索空间。一—剪枝若在状态空间U’内能够找到更好的解，则用新的解代替当前的已知解。一—定界若在状态空间U’内已经找到了最好的解，则结束对U'的搜索。否则对状态空间U’继续分枝。22026/9/22山东大学软件学院
2026/9/22 山东大学 软件学院 2 分枝定界法的基本思想 将状态空间U 一分为二。——分枝 ▪ 状态空间可以取 IP 的可行域，或者比其更大。 进入一个状态空间U’。若判定在U’ 内不可能找到比当前 已知解更好的解，则摒弃该搜索空间。——剪枝 若在状态空间U’ 内能够找到更好的解，则用新的解代替当 前的已知解。——定界 若在状态空间U’ 内已经找到了最好的解，则结束对U’ 的 搜索。 否则对状态空间U’ 继续分枝
整数规划的情形考虑整数规划问题IPo，其松弛记为LPo:cTxcTxminminAx=bAx= bs.t.s.t.x≥0,整数x≥0●求LP的最优解，记为x°。若x°为整数解，则已经求到了IP的最优解。·否则设x不为整数。向IP。中分别加入两个约束x,≤[x」和x,≥|xl，得到两个整数规划问题 IP,和 IP2:cTxcTxminminAx=bAx = bs.t.s.t.x,≥[x9]x, ≤[x]x≥0,整数x≥0,整数32026/9/22山东大学软件学院
2026/9/22 山东大学 软件学院 3 整数规划的情形 ⚫考虑整数规划问题 IP0，其松弛记为 LP0： 0,整数 s.t. min T = x Ax b c x ， 0 s.t. min T = x Ax b c x 。 ⚫求 LP0 的最优解，记为 x 0。若 x 0 为整数解，则已经求到了 IP0 的最优解。 ⚫否则设 0 i x 不为整数。向 IP0 中分别加入两个约束 0 i i x x 和 0 i i x x ，得到两个整数规划问题 IP1和 IP2： 0,整数 s.t. min 0 T = x x x Ax b c x i i ， 0,整数 s.t. min 0 T = x x x Ax b c x i i
整数规划的情形显然，若IP.有最优解，则其最优解必定或者在IP上取得，或者在IPz上取得。●解LPi，若其最优解不是整数解，则对IPi继续进行分枝.解LP，若其最优解不是整数解，则对IP继续进行分枝●在这个过程中，若对某个LPk，其最优解xk为整数解，且解值比当前已知的IP。的整数解x*的解值还要好，则将xk作为IP的当前已知最好解。●若LPk的最优解不是整数解，且其解值cx比当前已知的IPo的最好的整数解的解值cTx*还要差（即，cTx≥cTx*），则放弃对LPk的搜索。2026/9/22山东大学软件学院
2026/9/22 山东大学 软件学院 4 整数规划的情形 ⚫显然，若 IP0有最优解，则其最优解必定或者在 IP1上取得， 或者在 IP2上取得。 ⚫解 LP1，若其最优解不是整数解，则对 IP1继续进行分枝.； 解 LP2，若其最优解不是整数解，则对 IP2继续进行分枝.。 ⚫在这个过程中，若对某个 LPk，其最优解 x k为整数解，且解 值比当前已知的 IP0的整数解 x*的解值还要好，则将 x k作为 IP0的当前已知最好解。 ⚫若 LPk的最优解不是整数解，且其解值 c T x k比当前已知的 IP0 的最好的整数解的解值 c T x*还要差（即，c T x k c T x*），则放 弃对 LPk的搜索
整数规划的情形重复上述过程，当整个状态空间（或者由于求到了整数解，或者由于剪枝）都搜索完毕后，当前已知IPo最好的解x*就是IP.的最优解。52026/9/22山东大学软件学院
2026/9/22 山东大学 软件学院 5 整数规划的情形 ⚫重复上述过程，当整个状态空间（或者由于求到了整数解， 或者由于剪枝）都搜索完毕后，当前已知 IP0 最好的解 x* 就是 IP0的最优解