7章整数规划1.pptVIP

在之前研究的线性规划问题中，最优解有的是小数，有的是整数，而对于某些实际问题，如求解的是人数、机器台数等，要求得到的解必须是整数解，过去采取的方法通常是四舍五入或取整的方法，但用这些方法得到的整数解可能会丧失最优性，我们需要对此类求最优整数解的问题另行研究，我们称这样的问题为整数规划（Integer Programming）。 整数规划分类:纯整数规划, 混合整数规划, 0-1整数规划 第一节???? 整数规划的图解法 与LP问题类似，对于简单的IP问题也可以用图解法来进行求解. LP是在可行域内寻找最优解，而IP是在可行点上寻找最优解。 从该例可以看出，对于某个整数规划来讲，与其对 应的线性规划的可行域包含了整数规划的所有可行点， 则： 对于MAX：LP的最优目标函数值为IP目标函数值的上界 对于M I N：LP的最优目标函数值为IP目标函数值的下界 第二节???? 整数规划的分枝定界法? 对于变量较少，较简单的整数规划可以用穷解法——将各整数点逐一代入求得的最优解，对于大多数IP问题则采用分枝定解法求解。 分枝定界法即可以解决纯IP问题，也可以解决混合IP ，也可以解决0-1整数规划问题. 一、基本思想： 求出与IP对应的LP的最优解，若该最优解不满足整数约束，则以该解为出发点，将原LP问题分解为两个枝问题（即“分枝”），且每个枝问题增加一个新约束，新约束的增加可以使原可行域变小，并且在新枝中，先前未取得整数解的变量会取得整数解，直到求解出最优整数解为止，分枝结束。 此外，在每次分枝过程中都要重新确定新线性规划问题的目标函数Z的上界和下界（即定界）。 最终，Z的上界和下界相等时，对应的整数解便为原IP问题的最优解。 二、解题步骤： 将原整数规划问题称为A问题，将与A组对应的线性规划问题称为问题B 第一步：求解与A相对的B问题的最优解. 若问题B无最优解，IP问题A也无最优解； 若问题B的最优解为整数解，该组解也是IP问题A的最优解； 若问题B有最优解，但不满足非负整数约束，则需要以B为出发点进行分枝定界求解； 第二步：分枝 在B0的最优解中任选一个不符合整数条件的变量Xi ,若Xi的值为di，则对di进行取整，[di]表示小于di的最大整数. 构造两个新约束条件Xi≤ [di] 和Xi ≥ [di]+1;将两个新约束条件分别引入原线性规划问题B中，得到两个新的线性规划问题，并对其求解，判断其是否满足整数约束。 定界: 对求最大化问题，令B0的解为初始上界Z，一般取Xi=0，对应的函数值Z=0为下界Z（可以取任意一组整数可行解作为初始下界），分枝后需重新定界，选择各分枝中目标函数最大者为新上界；选择符合整数约束的分枝中，目标函数较大者为新下界，若无符合整数约束的分枝，则延用先前下界。（称为第一次秩代） 练习 * * 第七章? ? 整 数 规 划 如果在约束方程组中增加一项约束：X1, X2为整数，那么说明求解的最优解必须为整数。此时，该模型即为整数规划模型。 可见，IP与LP的区别仅在于一个整数约束条件，即一个IP－A当其去掉整数约束时，即变为一个LP－B，我们称这个线性规划问题B为与原整数规划问题A相对应的线性规划问题。 x2 可行域 6 4 -8 0 x1 x2 x1 x2 x1 第三步：比较剪枝。 将各分枝的目标函数值与下界Z比较，若小于Z，则将其剪掉不再研究，若大于 Z则选择其中目标函数值最大枝，再重新开始分枝定界，直到上界和下界相等，此时得到的整数解即为最优解。