MiaC.+ Ax'≤b (13) (x}为整数， j=1,2n 这里， 1 0 0 海象 0 0 1 0 0 A=AB] B1= 一i行 -q1 -q2 -93 ”14◆ -9。 0 0 0 4中0。 1) i列 此时lr<|C,lj≠i 故每进行一次这样的变换，目标函数中，非零的绝对值最小的系数至少下降1，故经若千次 这样的变换，必能化为情况(1)，定理证华。 2模式化算法 模式化算法，下面以2·表示 step1求解(2)的松弛问题 MinC:y. (14) By≤b 如果(14)无解，则(2)无解，停： 如果(14)有最优解y°=(yi,y,…y)r 若y(j=1,2…n)皆为整数，则y·为(2)的最优解，停； 若y·不为整数，则给定目标函数的初始上界M:=+∞，下界m: Ciy? y”为整数 m:= C:(Cy)+1)y非整数 转step2 step2分枝 (1)若y?是整数，且存在j≠：y?不是整数，则将相应的整数规划分枝，在两个分 枝规划上分别加上约束y1≤〔y)；y,≥〔y)+1； (2)若y:不是整数，且存在j≠，y不是整数，则在两个分枝规划上分别加上约束 y,≤Cy门，y:≥〔y门+1；y≥〔y)+1,y:≥〔y)+1； (3)若y不是整数，y?j≠i均为整数，则在相应整数规划上加上约束y,≥〔y)+1, 仅得一个分枝规划。 step3求解分枝整数规则的松弛问题 如果无解，则进行step4 396‘ 习 ， 了 劣 产 镇 了为整数 ， ， ， 这里 一 丁 丁 一 一 “ “ 。 “ 。 此时 ， 。 笋 故每进行一次这样的变换 ， 目标 函数 中 ， 非零的绝对值最小 的系数 至少 下降 ， 故经 若干次 这样的变换 ， 必能化为情况 ， 定 理证华 。 模式化算法 模 式化算法 ， 下面以 ’ 表示 求解 的松 弛 问厄 ‘ ‘ 簇 如果 无解 ， 则 无解 ， 停多 如果 有最优解 贯 ， 穿 ， … 忿 若 少 ， “ 皆为整数 ， 则 为 的最优解 ， 停 若 不为格数 ， 则给定 目标 函数 的初始上界 ， 下 界 。 ‘ 〔 乍〕 ，为整数 兮非整 数 转 分技 若 甲是整数 ， 且存在 笋 ‘ 萝不是整数 ， 则 将相应 的整数规翅分枝 ， 在 两 个 分 枝规划 上分别加上约束 二簇 〔 ，〕 ， 〔 ，〕 若 不是整数 ， 且存 在 笋 ， 夕，不是整数 ， 则在两个分 枝规翅上分别加 上 约 束 夕 ，簇 〔少 ， 〕 ， 夕 ‘ 〔夕，〕 夕 ， 〔夕亨〕 ， 夕 ‘ 〔夕兮〕 若 了不是整数 ， 萝 笋 均 为整数 ， 则在相应整数规划上加上约 束 ， 〔 匀 十 ， 仅得一个分 枝 规划 。 求解分技整橄规 划的松 弛 问 皿 如果无解 ， 则进行