CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第四章整数规划 整数规划的难度远大于一般线性规划
第四章 整数规划 整数规划的难度远大于一般线性规划 ©管理与人文学院 忻展红 1999，4
41整数规划简介 要求所有x的解为整数,称为纯整数规划 要求部分x的解为整数,称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 ·整数规划的解是可数个的,最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解 max(mm)f(x)=∑cx ∑a1x1≤(=,2)b st J= x1≥0且为整数,j=1,2,…,n
2 4.1 整数规划简介 • 要求所有 xj 的解为整数，称为纯整数规划 • 要求部分 xj 的解为整数，称为混合整数规划 • 对应没有整数解要求的线性规划称之为松弛问题 • 整数规划的解是可数个的，最优解不一定发生在极点 • 整数规划的最优解不会优于其松弛问题的最优解 = = = = = = x j n a x b i m s t f x c x j n j i j j i n j j j 0 , 1,2, , ( , ) , 1,2, , . . max(min) ( ) 1 1 且为整数
42整数规划的分枝定界法 42.1思路与解题步骤 只解松弛问题 1、在全部可行性城上解松弛问题 若松弛问题最优解为整数解,则其也是整数规划的 最优解 分枝过程 若松弛问题最优解中某个x=b不是整数,令Lb」 为b的整数部分 构造两个新的约束条件xsLb」和xk≥LbkH+1,分 别加于原松弛问题,形成两个新的整数规划 3、求解分枝的松弛问题一定界过程 设两个分枝的松弛问题分别为问题1和问题2,它 们的最优解有如下情况
3 4.2 整数规划的分枝定界法 4.2.1 思路与解题步骤 • 只解松弛问题 1、在全部可行性域上解松弛问题 – 若松弛问题最优解为整数解，则其也是整数规划的 最优解 2、分枝过程 – 若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分 – 构造两个新的约束条件 xk bk 和 xk bk +1，分 别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 — 定界过程 – 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它 们的最优解有如下情况
表421分枝问题解可能出现的情况 序号 问题1 问题2 说明 无可行解 无可行解 整数规划无可行解 234 无可行解 整数解 此整数解即最优解 无可行解非整数解对问题2继续分枝 整数解 整数解 较优的一个为最优解 5整数解,目标函非整数解问题1的解即最优解 教优于问题2 整数解非整数解,目标问题1停止分枝(剪 函数优于问题1枝),其整数解为界, 对问题2继续分枝 情况2,4,5找到最优解 情况3在缩减的域上继续分枝定界法 情况6问题1的整数解作为界被保留,用于以后与问题2的后 续分枝所得到的解进行比较,结论如情况4或5
4 表4.2.1 分枝问题解可能出现的情况 序 号 问 题 1 问 题 2 说 明 1 无可行解 无可行解 整数规划无可行解 2 无可行解 整数解 此整数解即最优解 3 无可行解 非整数解 对问题 2 继续分枝 4 整数解 整数解 较优的一个为最优解 5 整数解，目标函 数优于问题 2 非整数解 问 题 1 的解即最优解 6 整数解 非整数解，目标 函数优于问题 1 问 题 1 停 止 分 枝 (剪 枝)，其整数解为界， 对问题 2 继续分枝 情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的解进行比较，结论如情况 4 或 5
422分枝定界法举例 例411maxf(x)=6x1+4x2 2x1+4x2≤13 2x1+x2≤7 x1,x2≥0且为整数 解:松弛问题的最优解为x1=2.5,x2=2,OBJ=23 由x1=25得到两个分枝如下: max f(x)=6x+4x2 maxf(x)=6x+4x 2x1+4x,≤13 2x1+4x2≤13 2x1+x2≤7 2x1+x,≤7 问题I 问题I ≥3 x,x2≥0且为整数 x,x2≥0且为整数
5 4.2.2 分枝定界法举例 例4.1.1 + + = + , 0 且为整数 2 7 2 4 13 max ( ) 6 4 1 2 1 2 1 2 1 2 x x x x x x f x x x 解：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下： + + = + 且为整数 问题 , 0 2 2 7 2 4 13 I max ( ) 6 4 1 2 1 1 2 1 2 1 2 x x x x x x x f x x x + + = + 且为整数 问题 , 0 3 2 7 2 4 13 II max ( ) 6 4 1 2 1 1 2 1 2 1 2 x x x x x x x f x x x