云南师范大学：《数学建模与数学实验》课程PPT教学讲义_第5讲 整数规划（费培之）

(数学模型 对每个子问题P,不外乎有以下三种可能情况: (1)不可行,则剪枝; (2)其最优解X为整数解,则剪枝,且 当目标值<当前上界时,则换界; 当目标值≥当前上界时,则不换界。 (3)其最优解X;为非整数解,则 当目标值>当前上界时,则剪枝; 当目标值z≤当前上界时,则分枝。 注:对于极大化问题,则是定下界,最大下界对应 的整数解为所求 0<1<…<z≤z≤ 0 则 k g X"=Ⅹ

对每个子问题 ，不外乎有以下三种可能情况: Pi （1） 不可行，则剪枝； （2）其最优解 Xi 为整数解，则剪枝，且 • 当目标值 zi  当前上界时，则换界； • 当目标值 zi  当前上界时，则不换界。 （3）其最优解 Xi 为非整数解，则 • 当目标值 zi  当前上界时，则剪枝； • 当目标值 zi  当前上界时，则分枝。 注：对于极大化问题，则是定下界，最大下界对应 的整数解为所求。 1 0 z z z z −     k     则 k X Xk z = z =   , 归纳起来:

(数学模型 例求解minz=-3x-4x2 st2x1+5x,≤15(2 2x1-2x2≤53 > 且为整数 5 解松弛问题P可用 3 图解法 X0(39,14) 01234567 3x1-4x2 目标函数等值线

例 求解 min 3x1 4x2 z = − − s.t 2x1 + 5x2  15 2x1 − 2x2  5 x1 , x2  0 且为整数 1 2 3 4 5 1 2 3    1 2 3 4 5 6 7         1 x 2 x 0      解松弛问题P0 可用 图解法 S0 − x − x = z 3 1 4 2 目标函数等值线 (3.9, 1.4) X0 • S1 S2