运筹学 - 整数线性规划

搜索树解LP，得到分数解rcTx2≥cx*，剪枝。PIP2IPx!IP4IP3IP5IP6-3IP7IPs解LP4，得到整数解x4解LP，得到整数解7cTx4≤cTx*， x*=x4。x*=x7。62026/9/22山东大学软件学院

2026/9/22 山东大学 软件学院 6 搜索树 IP0 IP1 IP2 IP3 IP4 IP5 IP6 IP7 IP8   0 i i x  x   0 i i x  x   1 j j x  x   1 j j x  x   3 k k   x  x 3 k k x  x 解LP7，得到整数解x 7 ， x* = x 7 。 解LP4，得到整数解x 4 ， c Tx 4  c Tx* ，x* = x 4 。 解LP2，得到分数解x 2 ， c Tx 2  c Tx*，剪枝

例子-(x+x2)min- 4x +2x2 ≤-1s.t.4x, +2x2 ≤111X ≥解整数规划：o2Xi,≥0,整数5)3U2），最优解值z°=cx°=-4。解LPo，最优解为.2●在x上进行分枝，得到两个约束：xi≤1和xi≥2。2026/9/22山东大学软件学院

2026/9/22 山东大学 软件学院 7 例子 解整数规划： ( ) , 0,整数 2 1 4 2 11 s.t. 4 2 1 min 1 2 2 1 2 1 2 1 2   +  − +  − − + x x x x x x x x x 。 ⚫解 LP0，最优解为 T 0 2 5 2 3       x = ，最优解值 z 0 = c T x 0 = −4。 ⚫在 0 1 x 上进行分枝，得到两个约束：x1  1 和 x1  2